ملخص تقني: التوليد والترتيب والتحقق التكيفي (Adaptive Generate-Rank-Verify)

صياغة المشكلة

تتناول الورقة مشكلة تخصيص حسابات وقت الاستدلال الحساسة للتكلفة في النماذج اللغوية الكبيرة (LLMs). غالبًا ما تستخدم مسارات الاستدلال الحديثة نموذج "التوليد-الترتيب-التحقق": يقوم نموذج لغوي كبير بتوليد عدة حلول مرشحة، ثم يقوم نموذج مكافأة (Reward Model) رخيص ولكنه غير دقيق بترتيبها، ثم يقوم مُحقِّق (Verifier) مكلف (مثل تنفيذ الاختبار الخفي في البرمجة أو مطابقة الإجابة الدقيقة في الرياضيات) بالتحقق من المرشحين الأوائل.

التحدي الجوهري هو أن التخصيص الأمثل لموارد الحوسبة (عدد عمليات التوليد مقابل عدد عمليات التحقق) يعتمد على المطالبة (Prompt-dependent). السياسات الثابتة (على سبيل المثال، توليد $N_{rew}$ من العينات والتحقق من أفضل $N_{ver}$) تكون غير فعالة: فهي تفرط في الإنفاق على المطالبات السهلة وتبخل في الإنفاق على المطالبات الصعبة. يصيغ المؤلفون هذا كـ بحث نشط (Active Search)، وهي مشكلة قرار متسلسلة حيث يجب على السياسة أن تتكيف عبر:

1. توليد المرشحين ومراقبة درجات المكافأة الخاصة بهم (تكلفة $c_{rew}$).
2. التحقق من المرشحين المختارين للحصول على تسميات (Labels) الحقيقة الأرضية (تكلفة $c_{ver}$).
3. التوقف فقط عند العثور على استجابة تم التحقق من صحتها.

الهدف هو تقليل التكلفة الإجمالية المتوقعة $J = c_{rew}N_{rew} + c_{ver}N_{ver}$ مع ضمان معدل نجاح بنسبة 100% (إيجاد إجابة صحيحة إذا كانت موجودة في توزيع التوليد).

المنهجية

1. المعيار المدرك للتوزيع (Distribution-Aware Benchmark)

يضع المؤلفون أولاً حداً أدنى نظرياً بافتراض أن السياسة لديها معرفة كاملة بالبيئة:

• $D_x$: توزيع درجات المكافأة للمطالبة $x$.
• $h^*_x(r)$: دالة النجاح الشرطية، والتي تمثل احتمال أن يجتاز مرشح بدرجة $r$ عملية التحقق.

تحدد النظرية 3.2 السياسة المثلى في هذا الإعداد المثالي. وهي تثبت أن الاستراتيجية المثلى هي قاعدة عتبة (Threshold rule): يتم التحقق من المرشح فوراً إذا تجاوزت احتمالية نجاحه الشرطية $h^*_x(r)$ عتبة التعادل المحددة $\tau^*$, ويتم استبعاده بخلاف ذلك. $\tau^*$ هي الحل الفريد للمعادلة $c_{ver} \mathbb{E}[\max\{h^*(R) - \tau^*, 0\}] = \tau^* c_{rew}$.

2. خوارزمية ADAP

في الممارسة العملية، $D_x$ و $h^*_x$ غير معروفين. يقترح المؤلفون ADAP (التوليد والترتيب والتحقق التكيفي)، وهي خوارزمية عبر الإنترنت (Online) تعمل على مستويات (Shellwise) وتعمل دون معرفة مسبقة بتوزيع الدرجات أو دالة النجاح، معتمدة فقط على افتراض الرتابة (Monotonicity assumption) (الدرجات الأعلى في المكافأة هي الأقل احتمالاً للفشل في اجتياز التحقق).

آلية عمل ADAP:

• البحث عبر المستويات (Shellwise Search): تبحث الخوارزمية عبر "مستويات" (Shells) ذات مقاييس ثنائية (Dyadic scales) لعدد العينات ($m$) وعمليات التحقق ($k$). كل مستوى $s$ يقابل نطاق تكلفة $[2^s c_{min}, 2^{s+1} c_{min})$.
• التوسع التدريجي: بدءاً من المستويات الصغيرة، تقوم ADAP بتوليد دفعة من المرشحين الجدد، وإضافتهم إلى مجموعة (Pool)، وترتيب المجموعة بأكملها حسب درجة المكافأة.
• التحقق: تقوم بالتحقق من أفضل $k$ من المرشحين في المجموعة. إذا تم العث Found (إيجاد) تسمية إيجابية، تتوقف. إذا لم يكن الأمر كذلك، تنتقل إلى المستوى التالي بمقدار أكبر من $m$ و $k$.
• كفاءة القائمة (Pool-Based Efficiency): على عكس السياسات المتدفقة (Streaming policies) التي تستبعد المرشحين غير المتحقق منهم، تحتفظ ADAP بقائمة. المرشحون ذوو المكافأة العالية الذين تم توليدهم في المستويات المبكرة يظلون متاحين للتحقق في المستويات اللاحقة إذا لم يتم استعلامهم بعد.

3. الضمانات النظرية

• الحد الأعلى: تحت افتراض الرتابة، تثبت النظرية 4.2 أن ADAP تحقق تكلفة متوقعة ضمن عامل ثابت (تحديداً $\le 400$) من المثالية المدركة للتوزيع $J^*$. هذا الضمان يسري بشكل موحد لجميع المطالبات الممكنة والتوزيعات غير المعروفة.
• الحدود الدنيا وضرورة البنية: يوضح المؤلفون أن الافتراضات الهيكلية ضرورية. باستخدام رقم النجمة المركزية (Centered star number) ($s_0$)، وهو مقياس تعقيد نظري للتعلم، تظهر النظرية 6.2 أنه بدون افتراضات حول العلاقة بين الدرجات والتسميات (أي إذا كان $s_0 = \infty$)، لا يمكن لأي سياسة عبر الإنترنت سليمة تحقيق نسبة تنافسية ذات عامل ثابت مقابل الأوراكل (Oracle) المدرك للتوزيع. الفجوة في أسوأ الحالات يمكن أن تتوسع كـ $\Omega(\min\{s_0, c_{ver}/c_{rew}\})$.

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

1. الصياغة: تعريف مسار "التوليد-الترتيب-التحقق" كمسألة بحث نشط حساسة للتكلفة، مع تمييزها عن التعلم النشط القياسي بسبب الحاجة لتوليد المرشحين عبر الإنترنت بدلاً من الاستعلام من قائمة ثابتة.
2. المعيار الأمثل: توصيف السياسة المثلى المدركة للتوزيع كقاعدة عتبة بسيطة بناءً على احتمالية نجاح التعادل.
3. الخوارزمية التكيفية (ADAP): اقتراح خوارزمية عملية عبر الإنترنت، تعمل على توسيع نطاق التوليد والتحقق بشكل تكيفي. وهي توفر ضمانات ثابتة مثبتة بالنسبة للأوراكل الأمثل تحت شرط الرتابة.
4. الحدود النظرية للتعلم: إثبات أن الافتراضات الهيكلية (مثل الرتابة) ليست مجرد تسهيلات تقنية بل هي متطلبات أساسية لتحقيق بحث فعال، والتي تمت صياغتها عبر رقم النجمة المركزية.
5. التحقق التجريبي: التحقق من النهج في مهام الاستدلال الرياضي (HMMT) والبرمجة التنافسية (LiveCodeBench).

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

قيم المؤلفون ADAP مقابل:

• SampleAware: وهو حد أدنى (Oracle) يعتمد على العينات، يختار بأثر رجعي أكثر $(N_{rew}, N_{ver})$ اقتصادية لكل تجربة محددة.
• DAPk: وهو خط أساس تكيفي الصعوبة (Difficulty-adaptive baseline) يقوم بتقسيم المطالبات إلى $k$ من فئات الصعوبة بناءً على معدلات النجاح التاريخية ويخصص استراتيجية ثابتة لكل منها.
• Uniform: سياسة ثابتة تطابق متوسط تكلفة ADAP.

النتائج:

• كفاءة التكلفة: في مجموعة المطالبات الممكنة، حققت ADAP معدل نجاح بنسبة 100% مع متوسط تكلفة أقل بـ 2.9 ضعف من أفضل سياسة ثابتة في المهام الرياضية وأقل بـ 5.5 ضعف في مهام البرمجة.
• المقارنة بـ DAPk: تفوقت ADAP أو تساوت مع DAPk (حتى مع $k=10$) دون الحاجة إلى تسميات صعوبة تاريخية أو ضبط مسبق. في مهام البرمجة، لم تتفوق DAPk أبدًا على ADAP، بينما في المهام الرياضية، اقتربت DAPk من أداء ADAP فقط عندما كانت $k$ كبيرة بما يكفي لتقريب الأوراكل الخاص بكل مسألة.
• المتانة: زادت ميزة ADAP على السياسات الثدة كلما زادت تكلفة التحقق ($c_{ver}$) بالنسبة لتكلفة التوليد ($c_{rew}$).

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

تدعي الورقة أن التكيف عبر الإنترنت والمعتمد على المطالبة يتفوق على السياسات الثابتة أو المضبوطة تاريخيًا لعمليات البحث في وقت الاستدلال. من خلال معاملة المشكلة كبحث نشط والاستفادة من رتابة إشارات المكافأة، يمكن لـ ADAP تخصيص موارد الحوسبة ديناميكيًا لمطابقة صعوبة المطالبات المحددة.

يؤكد المؤلفون أن عملهم يوفر:

• ضمانات مثبتة: تقريب لعامل ثابت للتكلفة المثلى دون معرفة التوزيعات الأساسية.
• كفاءة عملية: تخفيضات كبيرة في تكاليف الحوسبة (زمن الاستجابة، ساعات GPU، الإنفاق على API) لمهام الاستدराण عالية المخاطر.
• الضرورة النظرية: تقديم دليل على أن الافتراضات الهيكلية حول العلاقة بين المكافأة والمُحقِّق ليست مجرد تسهيلات تقنية، بل هي متطلبات لا غنى عنها لتحقيق بحث فعال، مما يجسد الفجوة بين البحث النشط ونظرية التعلم النشط.

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