ملخص تقني: تصميم خوارزميات مدركة للتوزيع باستخدام وكلاء النماذج اللغوية الكبيرة (LLM Agents)

بيان المشكلة

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

التحدي الجوهري هو تعلم البرامج المدرك للتوزيع (distribution-aware program learning): بالنظر إلى عينات من توزيع نشر غير معروف $D$، يجب على المتعلم إرجاع كود مبرمج متخصص في $D$. الهدف ليس مجرد حل فئة المشكلات المحيطة (مثل SAT عام أو TSP)، بل تعلم خوارطة برمجية يتم تحسين تنفيذها لتناسب التنظيم الهيكلي المحدد للنظام المستهدف. هذا يقع بين تصميم الخوارزميات في الحالة الأسوأ (الذي يفترض عدم وجود معلومات توزيعية) وبين التعقيد في الحالة المتوسطة (الذي يفترض وصفاً تحليلياً للتوزيع).

المنهجية: تجريد تلميح المبرمج (The Solver Hint Abstraction)

تقدم الورقة تجريداً مركزياً يسمى تلميح المبرمج (solver hint): وهو هيكل قابل لإعادة الاستخدام يتم استنتاجه من العينات ويُجمع في كود مبرمج متخصص. تتم عملية التعلم عبر التفكيك التالي: $S \mapsto \hat{h}_S \mapsto \hat{c}_S = \text{Comp}(\hat{h}_S)$:

1. $S$: عينة من الحالات من التوزيع غير المعروف.
2. $\hat{h}_S$: تلميح المبرمج (على سبيل المثال، مجموعة "backdoor" في SAT، أو تفكيك كامن في الرسوم البيانية، أو نمط اختناق الموارد).
3. $\text{Comp}(\hat{h}_S)$: مبرمج مجمع (compiled solver) يستغل هذا التلميح.

من الأهمية بمكان أن الإطار يفصل بين الصحة والحوسبة المتعلمة. غالباً ما تُضمن الصحة عبر العودة إلى مبرمج كامل وعام (fallback). تُستخدم العينة فقط لتحديد أي اختصار حوسبي يجب تجميعه، مما يقلل وقت التشغيل في الحالات المستقبلية.

خط أنابيب التخليق باستخدام LLM

يستخدم المؤلفون هذا الإطار باستخدام وكلاء أكواد النماذج اللغوية الكبيرة (LLM code agents). تتضمن عملية التخليق ثلاث مراحل متتالية لكل مرشح:

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

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

المساهمات النظرية

تقدم الورقة ضمانات رسمية لنظامين:

1. التعظيم التجريبي لزمن التشغيل (ERM) فوق مكتبة ثابتة:
   يثبت المؤلفون أنه إذا كانت مكتبة المبرمجات $\mathcal{C}$ ثابتة، فإن أسرع مبرمج متسق مع العينة من الناحية التجريبية يعمم في كل من الصحة وزمن التشغيل. وتحديداً، باحتمالية عالية، يقترب زمن تشغيل المبرمج المختار من أفضل مبرمج متخصص في التوزيع داخل الفئة، وذلك بحد أقصى يعتمد على حجم المكتبة وعدد العينات. وهذا يثبت أن تقليل زمن التشغيل التجريبي هو استراتيجية صالحة لتحديد المبرمجين المتخصصين في التوزيع عندما يكون التخصص موجوداً في المكتبة.

2. التخليق عبر التلميحات القابلة للتعلم:
   بالنسبة للإعدادات الأكثر ثراءً حيث لا يكون التخصص معداً مسبقاً، تصيغ الورقة عملية استعادة التلميح من فضاء تلميحات محدود $\mathcal{H}$. وتحت فرضية القابلية للتحقيق (حيث يتوافق التوزيع الحقيقي مع $h^* \in \mathcal{H}$) وشرط الهامش (حيث يكون التلميح الحقيقي متميزاً إحصائياً عن غيره)، تثبت الورقة أن $O(\frac{1}{\gamma^2} \log \frac{|\mathcal{H}|}{\delta})$ من العينات تكفي لاستعادة التلميح الصحيح باحتمالية عالية.

   • مثال ملموس: تفصل الورقة نموذج "Hidden SAT Backdoor". هنا، التلميح هو مجموعة من المتغيرات التي، عند تثبيتها، تقلل الصيغة إلى فئة قابلة للحل بسهولة. تظهر النظرية أن إحصائية البروز (salience statistic) يمكنها تحديد هذا الـ "backdoor" من العينات، مما يسمح للمبرمج المجمع بتحقيق تسريع أسي في توزيع النشر مع الحفاظ على الصحة عبر آلية العودة للمبرمج العام (fallback).

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

قيم المؤلفون الإطار على 21 توزيعاً مستهدفاً للمسائل التوافقية المهيكلة عبر سبع فئات من المشكلات: تلوين الرسوم البيانية (Graph Coloring)، MAXSAT، مجموعة المستقل الأقصى (MIS)، المجموعة المهيمنة الدنيا (MDS)، Packing LP، حقيبة الظهر متعددة الأبعاد (MDKP)، ومشكلة البائع المتجول (TSP).

مقاييس الأداء الرئيسية

• الجودة: حققت المبرمجات المُخلّقة متوسط جودة معيارية قدرها 0.971. ويمثل هذا تحسناً قدره +0.224 عن متوسط مجموعة الاستدلالات (heuristics) و +0.098 عن أعلى استدلال من حيث الجودة.
• وقت التشغيل: كانت المبرمجات المُخلّقة أسرع بكثير من الخطوط المرجعية:
  • أسرع بمقدار 336.9 ضعفاً من أفضل استدلال من حيث الجودة.
  • أسرع بمقدار 342.8 ضعفاً من Gurobi (مع حد زمني قدره 10 ثوانٍ).
  • أسرع بمقدار 16.1 ضعفاً من الخلفية الدقيقة المختارة المحددة زمنياً.
• التحقق الخارجي (PACE 2025): في الحالات الخاصة المنشورة لمشكلة "المجموعة المهيمنة" (Dominating Set)، كان المبرمج المُخلّق صالحاً على جميع الرسوم البيوت الـ 100 وكان يعمل أسرع بنحو رتبتين من حيث المقدار من أفضل مبرمجات المسابقة (مثل Fontan–Verger, Root)، وإن كان مع فجوة جودة متوسطة (حجم الحل أكبر بنسبة ~3.3%).

آلية التحسين

يكشف تحليل الكود المولد أن المكاسب تأتي من تغيير النطاق الحوسبي. غالباً ما تستبدل المبرمجات المُخلّقة البحث الأسي المحيط أو التحسين العام لأغراض عامة بعمليات حسابية ذات رتب أدنى ومخصصة للتوزيع. تشمل الأمثلة:

• استبدال البحث $O^*(2^n)$ بالتحقق من القوالب والإصلاح المحدود.
• استخدام فرز الكثافة للموارد النشطة في Packing LP بدلاً من حل LP الكامل.
• استغلال الهياكل الهندسية الكامنة في TSP لبناء مسارات دون الحاجة إلى البرمجة الديناميكية الكاملة.

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

تدعي الورقة أنها تقدم مساراً بنائياً نحو القابلية للتتبع المحددة بالتوزيع. وعلى عكس التحليل الممهد (smoothed analysis) أو التعقيد المعلمي (parameterized complexity)، اللذين يعتمدان على مسارات مصممة يدوياً، يتعلم هذا الإطار المسار مباشرة من العينات.

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

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