ملخص تقني: توسيع نطاق التحقق الوكيل (Agentic Verifier) للبرمجة التنافسية

بيان المشكلة

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

تواجه طرق التحقق الحالية قيوداً كبيرة في سياق البرمجة التแข่งขัน:

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

المنهجية: التحقق الوكيل (Agentic Verifier)

يقترح المؤلفون التحقق الوكيل (Agentic Verifier)، وهو وكيل يعتمد على النماذج اللغوية الكبيرة مصمم للتفكير بنشاط في سلوكيات البرامج والبحث عن مدخلات اختبار تمييزية للغاية تكشف عن التباينات بين الحلول المرشحة.

الآلية الجوهرية

بدلاً من أخذ العينات العشوائية العمياء، ينخرط الوكيل في تفاعل متعدد الجولات مع بيئة تنفيذ الكود:

1. صياغة المهمة: بالنظر إلى مسألة $Q$ وزوج من الحلول المرشحة $(C_a, C_b)$، يكون هدف الوكيل هو توليد برنامج مولد للمدخلات $G$ ينتج مدخلاً صالحاً $x$ حيث يكون $Exec(C_a, x) \neq Exec(C_b, x)$.
2. حلقة التفاعل: يقترح الوكيل المدخلات بشكل تكراري، وينفذ الحلول المرشحة، ويفحص التغذية الراجعة (أخطاء وقت التشغيل، المخرجات)، ويقوم بتحسين فرضياته لاكتشاف الأمثلة المضادة.
3. استراتيجية الاختيار: في وقت الاستدلال، يقوم التحقق المدرب بتوليد مدخلات اختبار مستهدفة لأزواج من الحلول المرحة. تُستخدم هذه المدخلات في استراتيجية تصويت قائمة على التنفيذ لاختيار الحل النهائي.

خط أنابيب التدريب

يتم تدريب المحقق عبر خط أنابيب ثلاثي المراحل قابل للتوسع:

1. تخليق البيانات على نطاق واسع: يبني المؤلفون مجموعة بيانات لمسائل البرمجة التنافسية مع حلول مصنفة. بالنسبة للمسائل التي تفتقر إلى حالات اختبار ذات مخرجات صحيحة، يقومون بتخليق مجموعات اختبار عالية الجودة باستخدام آلية التصويت بالأغلبية القائمة على الإجماع عبر عدة حلول مرجعية لضمان الموثوقية.
2. الضبط الدقيق بالرفض (Rejection Fine-Tuning): باستخدام نموذج معلم قوي (Qwen3-235B)، يجمعون مسارات تفاعل ناجحة متعددة الجولات حيث ينجح الوكيل في توليد مدخلات تمييزية. يتم ضبط النموذج الأساسي بدقة على هذه المسارات عالية الجودة، مع إخفاء المطالبات الأولية والتغذية الراجعة لتعلم أنماط التفاعل الفعالة.
3. التعلم التعزيزي الوكيل (Agentic Reinforcement Learning): يتم تحسين المحقق بشكل أكبر باستخدام خوارزمية GRPO (تحسين السياسة النسبي للمجموعات). دالة المكافأة هي دالة نادرة وقائمة على النتيجة:
   • $+1$: مدخل صالح يميز بين الحلين.
   • $0$: مدخل صالح لا يميز بينهما (الحلول متفقة).
   • $-1$: مدخل غير صالح أو مولد فارغ.
     يعطي المنهج التدريبي الأولوية لأزواج "السلبيات الصعبة" حيث تكون المدخلات التمييزية نادرة، مما يشجع الوكيل على تعلم سلوكيات توليد مستهدفة.

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

1. التحليل التجريبي: تثبت الورقة تجريبياً أن توليد المدخلات العشوائية غير فعال للغاية للتحقق القائم على تنفيذ المدخلات فقط، مما يكشف عن فجوة أداء كبيرة مقارنة بالمدخلات التمييزية.
2. التحقق الوكيل: تقديم وكيل يولد بنشاط مدخلات اختبار تمييزية للغاية من خلال التفاعل متعدد الجولات، متجاوزاً أخذ العينات الثابت أو العشوائي.
3. خط أنابيب تدريب قابل للتوسع: خط أنابيب مبتكر يجمع بين تخليق البيانات، والضبط الدقيق بالرفض، والتعلم التعزيزي الوكيل لتدريب المحقق.
4. توسيع النطاق في وقت الاختبار: إثبات أن الطريقة المقترحة تستفيد باستمرار من زيادة الحوسبة في وقت الاختبار، حيث تتوسع بفعالية مع كل من عدد الحلول المرشحة وعدد المدخلات المولدة.

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

تم تقييم النهج على خمسة معايير للبرمجة التنافسية (USACO, LiveCodeBench, OJBench, ICPC-Eval, ومعيار CodeForces الجديد) باستخدام نموذجي سياسة (Qwen3-30B و Qwen3-235B).

• مكاسب الأداء: تفوق "التحقق الوكيل" باستمرار على النماذج المرجعية القوية، بما في ذلك توليد المدخلات العشوائية، وتوليد حالات الاختبار بواسطة النموذج (CodeT, CodeRM)، والاختيار القائم على نموذج المكافأة.
  • حقق مكاسب مطلقة قدرها +10–15% في دقة Best@k مقارنة بالنماذج القوية القائمة على التنفيذ.
  • في مجموعة OJBench "الصعبة" (Hard)، حسن المحقق 30B المدرب الأداء بنسبة +34.1% مقارنة بالنموذج المرجعي، متفوقاً بشكل كبير على نموذج 235B الذي يعمل بنمط (zero-shot).
• سلوك التوسع: على عكس النماذج المرجعية التي أظهرت تشبعاً مبكراً، أظهر "التحقق الوكيل" سلوك توسع واضح في وقت الاختبار، حيث يتحسن الأداء بثبات مع زيادة عدد مدخلات الاختبار.
• النمط الصفري مقابل المدرب (Zero-Shot vs. Trained): قدمت النماذج اللغوية الكبيرة في النمط الصفري بعض التحسين، لكن المحقق المدرب المخصص للمهمة تفوق عليها بشكل كبير، حتى عندما كان النموذج المدرب أصغر بـ 7 مرات من نظيره في النمط الصفري.

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

تدعي الورقة أن فعالية التصويت القائم على التنفيذ تتحدد أساساً من خلال الجودة التمييزية لمدخلات الاختبار وليس مجرد كميتها.

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