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

بيان المشكلة

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

يطرح استنتاج الـ LLM تحديات فريدة مقارنة بأنظمة الطوابير الكلاسيكية:

1. المعالجة ثنائية المرحلة: تمر الطلبات بمرحلة prefill (تعبئة مسبقة) مرتبطة بالحوسبة (لمعالجة توكنات المدخلات وبناء ذاكرة KV cache)، تليها مرحلة decode (فك التشفير) مرتبطة بمدخلات/مخرجات الذاكرة (لتوليد التوكنات بشكل تلقفي).
2. قيود الدفعات (Batching Constraints): لتعظيم استغلال وحدة معالجة الرسومات (GPU)، يتم تجميع الطلبات في دفعات. ومع ذلك، فإن خلط توكنات الـ prefill والـ decode يخلق تداخلاً، كما تفرض الأجهزة حداً لـ ميزانية التوكنات ($b_{max}$) وغالباً قيداً على حجم الدفعة ($k_{max}$).
3. أعباء عمل الوكلاء الذكيين (AI-Agent Workloads): تتضمن التطبيقات الحديثة شبكات من خوادم الـ LLM التي تعالج مهام وكلاء معقدة، والتي قد تتبع طبولوجيا الرسم البياني الموجه غير الدوري (DAG)، أو أنماط (fork-join)، أو تحتوي على توجيه حلقي (cyclic routing).

تستخدم الأنظمة الحالية استراتيجيات متنوعة (مثل FasterTransformer، وvLLM، وOrca، وSarathi-Serve) ذات أولويات متفاوتة (الأولوية للـ prefill مقابل الأولوية للـ decode) وقدرات دفعات مختلفة (مختلطة مقابل منفصلة). ويعتمد الممارسون حالياً على اختبارات أداء مكلفة وخاصة بكل عبء عمل لاختيار الأنظمة، مما يفتقر إلى ضمان نظري للاستقرار أو المثالية في الإنتاجية.

المنهجية

قام المؤلفون بتطوير إطار عمل نظري للطوابير (queueing-theoretic framework) لنمذجة أنظمة استنتاج الـ LLM.

1. النمذجة العشوائية (Stochastic Modeling)

• النموذج الأساسي: يتم نمذجة النظام كـ سلسلة ماركوف زمنية متقطعة (DTMC) تمثل طابور خدمة دفعات ثنائي الفئة.
  • الفئات: توجد الطلبات إما في طابور prefill أو طابور decode.
  • التجميع (Batching): يعالج الخادم دفعة من التوكنات من كلا الطابورين في وقت واحد، مع الخضوع لميزانية توكنات $b_{max}$.
  • عدم التماثل: يمكن معالجة توكنات الـ prefill لطلب واحد في مجموعات ضخمة، بينما تكون توكنات الـ decode متسلسلة بدقة (واحد لكل طلب في كل دفعة).
• نموذج وقت المعالجة: بالاستفادة من الآثار التجريبية، يتم تقريب زمن معالجة الدفعة $t_b$ كدالة ثابتة مجزأة تعتمد على حمل التوكنات $b$:
  $$t_b = c + a \cdot \lceil b/b_0 \rceil$$
  حيث $c$ هي التكلفة الأساسية، و$a$ هي التكلفة الهامشية لكل كتلة من $b_0$ توكنات. هذا النموذج يلتقط هيمنة حسابات الطبقات الخطية في استنتاج الـ LLM.

2. الإطار التحليلي

• تقنية حد السائل (Fluid-Limit Technique): استخدم المؤلفون إطار عمل حد السائل (Dai 1995, Stolyar 1995) لتحليل الاستقرار. وقد أثبتوا أنه تحت ظروف محددة، تتقارب العملية العشوائية الموزونة إلى نموذج سائل حتمي.
• تعريف الاستقرار: يكون النظام مستقراً (متكرر إيجابياً) إذا كان إجمالي التوكنات غير المعالجة لا يتباعد مع اقتراب الزمن من اللانهاية.
• فئة الجدولة: يركز التحليل على الخوارزميات المحافظة على العمل (work-conserving) (التي تملأ الدفعة إلى سعتها $b_{max}$ كلما أمكن ذلك) ويقدم شرط K-FCFS (الخدمة أولاً بأول مع تجاوز محدود) للتعامل مع تعقيدات التجميع المختلط.

3. التوسعات

تم توسيع الإطار ليشمل:

• الخوادم المتوازية: الأنظمة التي تستخدم موازنة الأحمال (عشوائي أو الانضمام لأقصر طابور - Join-the-Shortest-Queue).
• شبكات متعددة الفئات: خوادم مفردة تتعامل مع فئات طلبات متعددة (مثل خطوات وكيل مختلفة).
• طبولوجيا الشبكة: شبكات متعددة الخوادم مع توجيه DAG وأنماط fork-join.
• التوجيه الحلقي (Cyclic Routing): تحليل الشبكات مع حلقات التغذية الراجعة (نمط Rybko–Stolyar).
• قيود حجم الدفعة: تحليل الأنظمة المقيدة بكل من ميزانية التوكنات ($b_{max}$) والحد الأقصى لحجم الدفعة ($k_{max}$).

المساهمات الرئيسية والنتائج

1. مثالية الإنتاجية لجدولة المحافظة على العمل

تضع الورقة مبدأ تصميم جوهري: خوارزميات الجدولة المحافظة على العمل تحقق أقصى إنتاجية لاستنتاج LLM أحادي الخادم والشبكات ذات طبولوجيا DAG أو fork-join.

• النظرية 2: بالنسبة لخادم واحد، إذا كان حمل الوصول $\lambda(m_p + m_d)$ أقل من أقصى معدل معالجة $b_{max}/t_{b_{max}}$، فإن أي خوارزمية K-FCFS محافظة على العمل تعمل على استقرار النظام. وعلى العكس من ذلك، إذا تجاوز الحمل هذا الحد، سيكون النظام غير مستقر تحت أي خوارزمية.
• الآثار المترتبة: يوفر هذا حداً علوياً نظرياً ($b_{max}/t_{b_{max}}$) ويدعم التحول في الصناعة نحو المجدولات المحافظة على العمل.

2. تقييم الأنظمة الحالية

بتطبيق الإطار النظري على خوارزميات العالم الحقيقي، تظهر تصنيفات واضحة:

• مثالية للإنتاجية (محافظة على العمل):
  • Orca: يدعم التجميع المختلط (prefill + decode) مع أولوية للـ prefill.
  • Sarathi-Serve: يدعم الـ chunked prefill مع أولوية للـ decode والتجميع المختلط.
  • أحدث إصدار من vLLM (مع chunked prefill): محافظ على العمل.
• دون المستوى الأمثل/غير مستقرة (غير محافظة على العمل):
  • FasterTransformer: يعطي الأولوية للـ decode ولكنه يمنع التجميع المختلط. يترك وحدة معالجة الرسومات خاملة عندما لا تكفي طلبات الـ decode لملء الدفعة، حتى لو كانت طلبات الـ prefill في الانتظار.
  • vLLM التقليدي (Vanilla): يعطي الأولوية للـ prefill ولكنه يمنع التجميع المختلط. يترك طلبات الـ decode في الانتظار أثناء معالجة دفعات الـ prefill فقط.
• التحقق التجريبي: تؤكد آثار العمل الحقيقية أن الخوارزميات غير المحافظة على العمل (FasterTransformer، وvLLM التقليدي) تصبح غير مستقرة (تضخم الطابور) تحت أحمال متوسطة، بينما تظل الخوارزميات المحافظة على العمل (Sarathi-Serve، وOrca) مستقرة.

3. أعباء عمل الوكلاء الذكيين وطبولوجيا الشبكة

• DAG و Fork-Join: تثبت الورقة أن الجدولة المحافظة على العمل تظل مثالية للإنتاجية لشبكات خوادم الـ LLM المرتبة في طبولوجيا DAG أو fork-join، بشرماً أن يتحقق شرط الحمل في كل خادم.
• التوجيه الحلقي (Rybko–Stolyar Counterexample): يوضح المؤلفون أن الجدولة المحافظة على العمل ليست كافية للشبكات ذات التوجيه الحلقي. لقد صمموا شبكة مكونة من خادمين حيث تؤدي تخصيصات أولويات معينة تحت سياسة محافظة على العمل إلى عدم الاستقرار، حتى عندما يكون إجمالي الحمل أقل من السعة. وهذا يسلط الضوء على الحاجة إلى تصميم دقيق للأولويات أو سياسات غير محافظة على العمل (مثل back-pressure) في الطبولوجيا الحلقية.

4. تأثير قيود حجم الدفعة

عند فرض قيد الحد الأقصى لحجم الدفعة ($k_{max}$) جنباً إلى جنب مع ميزانية التوكنات ($b_{max}$):

• يصبح نطاق الاستقرار عبارة عن غلاف محدب ثنائي الأبعاد في مستوى $(\lambda_{prefill}, \lambda_{decode})$، بدلاً من مجرد عتبة عددية بسيطة.
• نتيجة غير متوقعة: في بعض النظم (تحديداً بالقرب من رأس منطقة الاستقرار المتعلق بالدفعات المختلطة)، قد تفشل الخوارزميات التي تحافظ على العمل بشكل صارم والتي تملأ دائماً إلى $b_{max}$ في تحقيق استقرار النظام. قد يتطلب الاستقرار الأمثل العمل عند حمل توكنات أقل (مثل $b_0$) لموازنة معدلات معالجة توكنات الـ prefill والـ decode. وهذا يشير إلى أنه تحت قيود حجم الدفعة الصارمة، تكون استراتيجيات الجدولة التكيفية ضرورية.

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

تدعي الورقة أنها تقدم أول أساس نظري صارم لطوابير الجدولة لاستنتاج الـ LLM. وتكمن أهميتها في:

1. مبدأ التصميم: إنها تحدد "المحافظة على العمل" كمبدأ تصميم رئيسي للممارسين، مما يوفر ضماناً نظرياً بأن خوارمايات مثل Sarathi-Serve وOrca مثالية للإنتاجية، بينما تحذر من نهج التجميع غير المختلط مثل FasterTransformer وvLLM التقليدي.
2. الربط بين المجتمعات: إنها تخفض حاجز الدخول لمجتمع نظرية الطوابير للمساهمة في أنظمة الـ LLM من خلال تقديم نموذج رسمي يلتقط خصائص المرحلة المزدوجة والتجميع الفريدة للنماذج اللغوية الكبيرة.
3. التوجيه للوكلاء الذكيين: توسع تحليل الاستقرار لتشمل أعباء عمل الوكلاء الذكيين، كاشفة أنه بينما تعد طبولوجيا DAG قوية، فإن الطبولوجيا الحلقية تتطلب جدولة أكثر تطوراً من السياسات البسيطة المحافظة على العمل.
4. القيود الدقيقة: تكشف أن القيود العملية مثل حدود حجم الدفعة يمكن أن تغير جذرياً مناطق الاستقرار، مما يتحدى الافتراض القائل بأن "ملء الدفعة" هو دائماً الخيار الأمثل.

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