🤖 AI

Beyond the Frontier: Stochastic Backtracking for Efficient Test-Time Scaling

تقدم هذه الورقة البحثية تقنية التراجع العشوائي (stochastic backtracking) عبر مجمع مستمر من البوادئ التاريخية، المعززة باختيار المجمعات الفرعية و"مونت كارلو التسلسلية للتراجع القوي" (Power Backtrack Sequential Monte Carlo)، للتغلب على قيود البحث المقتصر على الحدود وتحسين نسبة الدقة إلى كفاءة الرموز (accuracy-to-token efficiency ratio) بشكل كبير في توسيع نطاق النماذج اللغوية أثناء وقت الاختبار.

المؤلفون الأصليون: Dao Tran, Duc Anh Le, Ngoc Luu, Quan Pham, Tung Pham, Hung Bui

نُشر 2026-05-26

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Dao Tran, Duc Anh Le, Ngoc Luu, Quan Pham, Tung Pham, Hung Bui

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

الصورة الكبيرة: مشكلة "المستكشف الذكي"

تخيل أنك ترسل فريقًا من المستكشفين (الذكاء الاصطناعي) إلى كهف شاسع ومظلم (مسألة رياضية معقدة) للبحث عن كنز مخفي (الإجابة الصحيحة).

في الماضي، كان هؤلاء المستكشفون يستخدمون استراتيجية تسمى "البحث عند الحدود فقط" (Frontier-Only Search). وإليك كيف كانت تعمل:

ينقسم الفريق إلى مجموعات، كل منها تسلك مسارًا مختلفًا.
عند كل مفترق طرق، يقوم مرشد (يُسمى نموذج مكافأة العمليات - PRM) بفحص المسار وإعطائه درجة. "هذا المسار يبدو واعدًا! وذاك يبدو طريقًا مسدودًا".
يقوم الفريق فورًا بقطع المسارات ذات الدرجات المنخفضة ويرسل المزيد من الناس فقط في المسارات ذات الدرجات العالية.

المشكلة: المرشد ليس مثاليًا. أحيانًا، يصاب المرشد بالتوتر ويعطي درجة سيئة لمسار يؤدي في الواقع إلى الكنز. ولأن قاعدة "الحدود فقط" تنص على "قطع أي مسار ليس هو الأفضل حاليًا"، فإن الفريق يتخلص من ذلك المسار للأبد. إنهم لا يحصلون على فرصة ثانية لرؤية ما إذا كان ذلك المسار "السيئ" هو في الواقع منجم ذهب. ينتهي بهم الأمر عالقين في مسار يبدو جيدًا ولكنه لا يؤدي إلى شيء، مما يهدر الوقت والطاقة.

الحل الجديد: "المجمع المستمر"

تقدم هذه الورقة البحثية استراتيجية جديدة تسمى "التراجع العشوائي عبر مجمع مستمر" (Stochastic Backtracking over a Persistent Pool).

بدلاً من النظر فقط إلى الخطوط الأمامية الحالية للمستكشفين، يحتفظ الفريق بـ مجمع مستمر (Persistent Pool) — وهو عبارة عن خريطة ضخمة لكل مسار جربوه على الإطلاق، حتى المسارات التي تخلوا عنها.

فكر في الأمر كمتنزه يحمل حقيبة ظهر مليئة بالخرائط القديمة. حتى لو كان يسير حاليًا في المسار (أ)، فإنه يتذكر أن المسار (ب) بدا جيدًا في وقت سابق، وأن المسار (ج) تم التخلي عنه لأن المرشد كان يمر بيوم سيء.

تقترح الورقة طريقتين محددتين لاستخدام "حقيبة الظهر من الخرائط القديمة" للعثين على الكنز بشكل أسرع وبجهد أقل:

1. اختيار المجموعات الفرعية (طريقة "تذكرة اليانصيب")

تخيل أن الفريق لديه 1,000 مسار في حقيبة ظهره. إذا اختاروا فقط أفضل 10 مسارات بناءً على درجة المرشد، فقد يستمرون في اختيار نفس المسارات "المزيفة" ذات الدرجات العالية مرارًا وتكرارًا.

الإصلاح: بدلاً من النظر إلى الحقيبة بأكملها، يأخذ الفريق حفنة عشوائية مكونة من 50 مسارًا (مجموعة فرعية). ثم يختارون الأفضل من بين تلك الحفنة.

لماذا ينجح هذا: هذا يمنح المسارات "المغمورة" (التي أعطاها المرشد درجة منخفضة ظلماً) فرصة ليتم اختيارها. الأمر يشبه اليانصيب حيث لا تشتري تذاكر للمفضلين فقط؛ بل تشتري مزيجًا عشوائيًا، مما يعطي المغمورين فرصة للفوز. هذا يمنع الفريق من العلوق في طريق مسدود واحد مبالغ في تقديره.

2. التراجع القوي بنموذج مونت كارلو (طريقة "السفر عبر الزمن الموزون")

هذه طريقة أكثر رياضية لقول: "دعونا نعود بالزمن، ولكن بذكاء".

يحتفظ الفريق بقائمة لجميع المسارات الماضية. وعندما يقررون أي مسار سيستكشفونه بعد ذلك، فهم لا يختارون عشوائيًا فحسب. بل يستخدمون صيغة خاصة تقوم بـ:

تضخيم (Amplify) الدرجات الجيدة (لجعل المسارات الجيدة حقًا تبرز أكثر).
إبقاء المسارات القديمة حية في المجمع حتى يمكن زيارتها مرة أخرى.
الموازنة بين تجربة مسارات جديدة وزيارة المسارات القديمة.

فكر في هذا كـ "محقق يسافر عبر الزمن". إذا تعثر المحقق، فإنه لا يستمر في المشي للأمام فحسب. بل يتصفح ملفات قضاياه القديمة (المجمع المستمر)، ويعيد فحص دليل تجاهله بالأمس، ويدرك: "مهلًا، هذا يبدو واعدًا حقًا!" ثم يعود ويتبع ذلك الخيط القديم.

لماذا يهم هذا: توفير "الرموز" (Tokens)

في عالم الذكاء الاصطناعي، "الرموز" (Tokens) هي بمثابة الوقود. كلما فكر الذكاء الاصطناعي أكثر، زاد استهلاك الوقود.

الطريقة القديمة: للوصول إلى الإجابة الصحيحة، كان على الذكاء الاصطناعي حرق الكثير من الوقود (توليد العديد من الرموز) لأنه كان يستمر في السير في طرق مسدودة ولا يمكنه العودة للخلف.
الطريقة الجديدة: نظرًا لأن الذكاء الاصطناعي يمكنه النظر إلى "خريطة مساراته القديمة" والمحاولة مرة أخرى، فإنه يجد الكنز بشكل أسرع بكثير.

النتيجة: تُظهر الورقة أنه باستخدام هذه الطرق الجديدة، يمكن للذكاء الاصطناعي حل المسائل الرياضية الصعبة بـ وقود أقل بكثير (رموز أقل) مع الحصول على نفس الدقة أو دقة أفضل من الطرق القديمة. إنه يشبه قيادة سيارة تستهلك وقودًا أقل بكثير لتصل إلى نفس المسافة، دون الحاجة إلى محرك أكبر.

الملخص

تعالج الورقة خللاً في كيفية استكشاف الذكاء الاصطنانا للمشكلات. فبدلاً من اتباع المسار "الأفضل حاليًا" بشكل أعمى والتخلص من كل شيء آخر، تحتفظ الطريقة الجديدة بسجل لجميع المسارات. وهي تستخدم حيلًا ذكية (أخذ العينات العشوائية والتحرك الذكي عبر الزمن) لإعادة زيارة المسارات القديمة التي ربما تم رفضها بشكل غير عادل. وهذا يسمح للذكاء الاصطناعي بحل المشكلات الصعبة بشكل أسرع، وأرخص، وأكثر دقة.

ملخص تقني: ما وراء الحدود: التراجع العشوائي للخلف (Stochastic Backtracking) من أجل توسيع كفاءة وقت الاختبار

بيان المشكلة

يهدف توسيع وقت الاختبار (TTS) إلى تحسين استدلال النماذج اللغوية الكبيرة (LLMs) من خلال تخصيص حوسبة إضافية أثناء الاستنتاج لاستكشاف مسارات حل متعددة. وبينما برزت نماذج مكافأة العمليات (PRMs) كآلية معيارية لتوجيه هذا البحث عبر تقييم البوادئ (prefixes) الوسيطة، تعاني الأساليب المتطورة الحالية من قصور حرج: وهو البحث المقتصر على الجبهة فقط (frontier-only search).

في أساليب البحث المقتصرة على الجبهة (مثل بحث الشعاع القياسي Beam Search، أو SMC)، تقتصر حالة البحث على العناصر المولدة حديثاً في كل خطوة. ويتم حذف البوادئ التي تم توليدها سابقاً بشكل غير قابل للاسترداد بناءً على درجات PRM مشوبة بالضجيج. وهذا يخلق نمط فشل "الالتزام المبكر":

القرارات غير القابلة للتراجع: البادئة التي يتم تقييمها منخفضة بشكل صحيح بسبب ضجيج الـ PRM (أو عدم التطابق بين بيانات التدريب الخاصة بالـ PRM والنموذج الأساسي المستخدم) يتم استبعادها نهائياً، حتى لو كانت تؤدي إلى استمرارية صحيحة.
انهيار التنوع: تهيمن البوادئ الخاطئة ذات الدرجات المرتفلة على عملية البحث، مما يتسبب في هدر الحوسبة على مسارات غير منتجة مع فقدان القدرة على الوصول إلى الحالات التاريخية التي قد تكون صحيحة.
عدم الكفاءة: عدم القدرة على إعادة زيارة الحالات التاريخية يجبر النموذج على استهلاك عدد مفرط من الرموز (tokens) للتعافي من أخطاء الحذف المبكر.

المنهجية

تقترح الورقة إطار عمل "التراجع العشوائي للخلف عبر مجمع مستمر" (Stochastic Backtracking over a Persistent Pool)، وهو إطار يحافظ على مجمع خطي الذاكرة من البوادئ التاريخية، مما يسمح للبحث بإعادة زيارة وتوسيع الحالات التي تم توليدها سابقاً بدلاً من الاقتصار على الجبهة الحالية. وقد طبق المؤلفون هذا الإطار من خلال خوارزميتين متكاملتين:

1. اختيار المجمع الفرعي (Subpool Selection - SPS)

يعالج SPS "مشكلة الحائل" (blocker problem) في الاختيار الجشع، حيث تحجب البوادئ الخاطئة ذات الدرجات المرتفعة الوصول إلى البوادئ التاريخية الصحيحة ولكن ذات الدرجات المنخفضة.

الآلية: بدلاً من اختيار أفضل $M$ من المرشحين من كامل المجمع المستمر (وهو ما يفضل الحواجِل ذات الدرجات العالية)، يقوم SPS بإنشاء مجمع فرعي عشوائي $D_t$ بحجم $K_t$ من المجمع التاريخي $P_{t-1}$ .
الاختيار: ثم يختار أفضل $M$ من المرشحين حصرياً داخل هذا المجمع الفرعي العشوائي.
النسبة التكيفية: يتم تحديد حجم المجمع الفرعي من خلال نسبة تكيفية $\rho_t$ ، تُحسب بناءً على متوسط درجة PRM للمجمع الحالي. إذا كان المجمع ذا ثقة منخفضة (متوسط درجة منخفض)، يكون المجمع الفرعي أصغر لتجنب العناصر الخاطئة ذات الدرجات العالية؛ وإلا، يكون أكبر.
الأثر: تمنح هذه العينة العشوائية البوادئ التاريخية "المحظورة" فرصة ليتم اختيارها وتوسيعها، مما يتجاوز هيمنة مرشحي الجبهة ذوي الدرجات المرتفعة.

2. مونت كارلو التسلسلي المدعوم بالتراجع (Power Backtrack Sequential Monte Carlo - PB-SMC)

توسع PB-SMC طرق مونت كارلو التسلسلي (SMC) لتشمل المجمع المستمر، مما يتيح التعافي العشوائي من قرارات الحذف المبكرة.

هدف المجمع المستمر: على عكس SMC القياسي الذي يقصر الجسيمات (particles) على الجبهة الحالية، تحافظ PB-SMC على مجمع يحتوي على كل من العناصر المولدة حديثاً والبادئ التاريخية المحتفظ بها من الخطوات السابقة.
درجات PRM المدعومة (Powered PRM Scores): تطبق الطريقة قوة $\beta_t$ على درجات PRM ( $r_{PRM}(z)^{\beta_t}$ ) لزيادة حدة توزيع المكافأة، مما يبرز البوادئ ذات الدرجات العالية ويقلل من شأن ذات الدرجات المنخفضة.
الأوزان المصححة بالمزيج: تعامل الخوارزمية البحث كمسألة أخذ عينات بأهمية متعددة (MIS). فهي تحدد توزيع اقتراح مزيج $q_{mix}$ $q_{mi x}$ يجمع بين:
- $q_{new}$ : العناصر الجديدة المولدة من الخطوة السابقة.
- $q_{hist}$ : البوادئ التاريخية المحتفظ بها من الخطوات السابقة.
الوزن: تشتق الخوارما خوارزمية أوزان محددة $W_t(z)$ تصحح المزيج المقترح، مما يضمن تقارب المقدر نحو التوزيع المستهدف المدعوم. وهذا يسمح للنظام بإعادة أخذ عينات عشوائية من الجسيمات التاريخية التي تم حذفها سابقاً.

كفاءة الذاكرة والحوسبة

الذاكرة الخطية: يخزن المجمع المستمر حالات نصية ودرجات PRM فقط، وليس مخازن مفاتيح-قيم (KV caches) كاملة. يتم إعادة حساب مخازن KV فقط عند اختيار بادئة تاريخية للتوسيع.
العبء الإضافي: تجادل الورقة بأن عبء الحوسبة الناتج عن إعادة حساب مخازن KV للحالات المتراجعة ضئيل جداً مقارنة بالمكاسب في الدقة وكفاءة الرموز.

المساهمات الرئيسية

تحديد فشل "الجبهة فقط": تحدد الورقة أن الاختيار غير القابل للتراجع المقتصر على الجبهة هو نمط فشل رئيسي في توسيع وقت الاختبار الموجه بـ PRM، حيث تؤدي الدرجات المشوبة بالضجيج إلى فقدان دائم لمسارات الحل الصحيحة.
إطار المجمع المستمر: تقديم بديل خطي الذاكرة يحافظ على البوادئ التاريخية مؤهلة للتوسيع المستقبلي، مما يفصل بين أهلية البحث والجبهة الفورية.
خوارزمان جديدان:
- اختيار المجمع الفرعي (SPS): تحسين للبحث الجشع يستخدم مجمعات فرعية عشوائية لتجاوز الحواجِل ذات الدرجات العالية.
- مونت كارلو التسلسلي المدعوم بالتراجع (PB-SMC): امتداد لـ SMC يستخدم درجات PRM مدعومة وأوزان مصححة بالمزيج لتمكين التراجع العشوائي للخلف.
الضمانات النظرية: إثبات أن PB-SMC تتقارب باحتمالية نحو الهدف الوسيط المدعوم بـ PRM، مما يضمن الصحة التقاربية بالنسبة للهدف الوسيط.

النتائج التجريبية

تم تقييم الطرق على أربعة معايير للاستدلال الرياضي (MATH500, AMC23, AIME24, Minerva Math) باستخدام ثلاثة نماذج لغوية (Qwen2.5-7B, Qwen2.5-3B, Phi-4-mini) ونموذج Qwen2.5-Math-PRM-7B.

كفاءة الرموز: حقق كل من SPS و PB-SMC دقة تنافسية أو متفوقة باستخدام $N=8$ فقط من المرشحين في كل خطوة، بينما تطلبت النماذج القوية (Beam Search, SMC, DVTS) عدد $N=32$ .
- SPS: قلل استهلاك الرموز بنسبة 49.4% في المتوسط مع تحسين الدقة.
- PB-SMC: قلل استهلاك الرموز بنسبة 36.7% في المتوسط مع تحسين الدقة.
مكاسب الدقة:
- على نموذج Qwen2.5-7B-Instruct، حقق SPS دقة متوسطة بلغت 54.66%، متفوقاً على DVTS (51.40%) و Beam Search (52.12%).
- على نموذج Phi-4-mini-Instruct، حققت PB-SMC أعلى دقة إجمالية (48.69%).
دراسات الاستئصال (Ablation Studies):
- التراجع للخلف (Backtracking): أدى إضافة التراجع للخلف إلى SMC (Backtrack SMC) إلى تحسين متوسط الدقة من 49.11% إلى 52.27%.
- العشوائية (Stochasticity): استبدال الاختيار الجشع العالمي باختيار المجمع الفرعي (SPS) حسن متوسط الدقة من 51.61% إلى 54.66%.
وقت التشغيل: رغم العبء المحتمل لإعادة حساب مخازن KV، كانت الطرق أسرع بنحو 2.5 ضعف من Beam Search بسبب تقليل مجموعة المرشحين ( $N=8$ مقابل $N=32$ )، مع عقوبة زمنية ضئيلة (~10%) مقارنة بأقرب النماذج المنافسة.

الأهمية والادعاءات

تدعي الورقة أن التراجع العشوائي للخلف عبر المجمع المستمر يوفر آلية بسيطة وفعالة لتحسين المقايضة بين الدقة والرموز في توسيع وقت الاختبار. تكمن الأهمية الجوهرية في نقل التركيز من مجرد تقييم البوادئ إلى الحفاظ على إمكانية الوصول إليها. ومن خلال السماح للبحث بإعادة زيارة الحالات التاريخية، تخفف هذه الأساليب من مخاطر درجات PRM المشوبة بالضجيج والالتزام المبكر.

يضع المؤلفون عملهم كحل عملي للانتشار في ظل قيود الموارد، موضحين أن توسيع وقت الاختبار الفعال لا يتطلب زيادة هائلة في الحوسبة، بل يتطلب تخصيصاً أكثر ذكاءً للحوسبة المتاحة من خلال بحث واعٍ بالتاريخ. وتشير النتائج إلى أن الوصول التاريخي هو عامل حاسم، وغالباً ما يتم تجاهله، لتعظيم كفاءة الاستدلال في النماذج اللغوية الكبيرة.