🤖 machine learning

Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference

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

المؤلفون الأصليون: Saksham Rathi, Preeti, Mythili Vutukuru

نُشر 2026-05-08

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

CC BY 4.0

المؤلفون الأصليون: Saksham Rathi, Preeti, Mythili Vutukuru

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

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

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

إليك قصة حلهم، Feather، مقسمة إلى مفاهيم بسيطة:

1. المشكلة: "الحافلة المزدحمة" مقابل "المجموعة العائلية"

تحاول معظم الأنظمة حالياً حشد أكبر عدد ممكن من الأشخاص في حافلة واحدة (دفعة/batch) لجعل الرحلة فعالة. وهم يستخدمون قاعدة "من يأتي أولاً يُخدم أولاً".

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

الرؤية الجوهرية: من الأفضل أن يكون لديك مجموعة أصغر من الأشخاص ذاهبين إلى نفس المكان بدلاً من مجموعة ضخمة من الأشخاص ذاهبين إلى أماكن مختلفة. وهذا ما يسمى بـ تجانس البادئة (Prefix Homogeneity).

2. الطريقة القديمة: "متسلق الأشجار"

تحاول الأنظمة الحالية (مثل SGLang) العثور على هذه المجموعات من خلال النظر في شجرة عائلة ضخمة ومعقدة (Radix Tree) لمعرفة من يتشاركون نفس الأسلاف.

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

3. الحل: "Feather"

قام المؤلفون ببناء مجدول جديد يسمى Feather يعالج كلتا المشكلتين.

الجزء أ: "شجرة التجزئة المجزأة" (CHT) – قائمة التحقق الذكية

بدلاً من تسلق شجرة العائلة الضخمة، يستخدم Feather اختصاراً ذكياً.

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

الجزء ب: "التعلم التعزيزي" (RL) – الموزع الذكي

لا يكتفي Feather بإيجاد المجموعات المتشابهة فحسب، بل يتعلم متى يتوقف عن إضافة الأشخاص إلى الحافلة.

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

4. النتائج: تسريع المكتبة

عندما اختبر المؤلفون Feather:

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

الملخص

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

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

ملخص تقني: الطلبات تتبع بعضها البعض (Requests of a Feather Must Flock Together)

بيان المشكلة

تعتبر عملية الاستدلال في النماذج اللغوية الكبيرة (LLM) مقيدة بالذاكرة بشكل أساسي خلال مرحلة فك التشفير التكراري (auto-regressive decode). يتطلب كل رمز (token) يتم توليده الانتباه إلى ذاكرة المفتاح-القيمة (KV cache) لجميع الرموز السابقة، مما يستلهب مسحًا كاملاً لذاكرة الـ KV cache في ذاكرة الوصول العشوائي للوحدة الرسومية (GPU) في كل خطوة. وبينما ركزت الأعمال السابقة على تعظيم حجم الدفعة (batch size) لتحسين استغلال الوحدة الرسومية، يحدد هذا البحث مقايضة حرجة تم التغاضي عنها: تجانس البادئة (prefix homogeneity).

في أعباء العمل الواقعية (مثل التلقين بأسلوب القليل من الأمثلة Few-shot prompting، أو مطالبات النظام System prompts، أو RAG)، غالبًا ما تشترك الطلبات في بادئات مشتركة كبيرة. تستخدم محركات الاستدلال الحالية (مثل vLLM وSGLang) أشجار جذور (radix trees) أو هياكل هاش (hash structures) لاكتشاف هذه البادئات المشتركة وإعادة استخدام ذاكرة الـ KV cache، وذلك أساسًا لتقليل بصمة الذاكرة. ومع ذلك، تعطي المجدولات الحالية الأولوية لتعظيم حجم الدفعة أو تقليل عمليات الإخلاء من الذاكرة دون النظر إلى تأثير عدم تجانس البادئة على أنماط الوصول إلى الذاكرة.

يوضح المؤلفون أن الدفعات غير المتجانسة (التي تحتوي على طلبات ذات بادئات مختلفة) تعطل الموضعية المكانية والزمانية (spatial and temporal locality) في عمليات الوصول إلى ذاكرة DRAM الخاصة بالوحدة الرسومية، مما يؤدي إلى ضعف استغلال عرض نطاق التردد (bandwidth) وانخفاض الإنتاجية. وعلى العكس من ذلك، فإن الدفعات متجانسة البادئة (حيث تشترك جميع الطلبات في بادئة مشتركة) تسمح بجلب مسبق فعال للأجهزة (hardware prefetching) وإعادة استخدام الذاكرة المخبئية. ويجادل البحث بأن المجدولات الحالية تفشل في إدراك أن دفعة صغيرة نسبيًا ومتجانسة يمكن أن تتفوق على دفعة أكبر وغير متجانسة. علاوة على ذلك، فإن الآليات المستخدمة لاكتشاف مشاركة البادئة (مثل عمليات التتبع في شجرة الجذور - radix tree traversals) تسبب عبئًا مرتفعًا على المعالج (CPU)، وهو عبء قد يقارن أو يتجاوز وقت تنفيذ الوحدة الرسومية.

المنهجية

يقدم البحث Feather، وهو مجدول مدرك للبادئة مصمم لتحسين المقايضة بين حجم الدفعة وتجانس البادئة. يدمج Feather مكونين رئيسيين:

1. شجرة الهاش المجزأة (Chunked Hash Tree - CHT)

لمعالجة العبء المرتفع على المعالج (CPU) الناتج عن عمليات تتبع أشجار الجذور التقليدية، يستخدم Feather هيكل بيانات خفيف الوزن يسمى "شجرة الهاش المجزأة".

الآلية: بدلاً من المقارنات رمزًا تلو الآخر، يتم تمثيل الطلبات كمتجهات من الهاشات التراكمية عبر أجزاء (chunks) ذات أحجام ثابتة.
الكفاءة: تحافظ CHT على "مجموعة عمل" من الهاشات للدفعة النشطة وكومة (min-heap) من الطلبات المنتظرة مرتبة حسب "عدد الأجزاء المفقودة" (عدد الأجزاء التي لم تغطها الدفعة النشطة بعد).
التعقيد: يسمح هذا للمجدول بتحديد أفضل طلب مرشح للإضافة إلى الدفعة في زمن قدره $O(\log W)$ (حيث $W$ هو عدد الطلبات المنتظرة)، وهو تحسن كبير مقارنة بتعقيد $O(W \times T)$ أو $O(E)$ لعمليات تتبع شجرة الجذور بالبحث العميق.
العمليات: تدعم CHT الإضافة الفعالة، وإيجاد أفضل طلب، وإضافة طلب إلى الدفعة النشطة، وإزالة الطلبات المكتملة، باستخدام تحديثات الكومة الكسولة (lazy heap updates) وصيانة الطرف المتغير التدريجي لتقليل العبء.

2. سياسة الدفعات القائمة على التعلم التعزيزي (RL)

يستخدم Feather سياسة قائمة على التعلم التعزيزي (RL) لتحديد نقطة التوقف المثلى لتشكيل الدفعة.

المقايضة: إضافة المزيد من الطلبات تزيد من استغلال الوحدة الرسومية (حجم دفعة أكبر) ولكنها قد تقلل من تجانس البادئة (مما يقلل من موضعية الذاكرة).
الحالة والعمل (State & Action): يراقب المجدول حجم الدفعة الحالي، والخسارة في عمق البادئة المشتركة ( $\Delta$ )، وعدد الطلبات المنتظرة التي تشارك عمق البادئة الجديد ( $w$ ). ويقرر ما إذا كان سيقوم بـ إضافة طلب آخر أو التوقف وإرسال الدفعة.
السياسات: يقيم المؤلفون ثلاث سياسات: استدلال ثابت (static heuristic)، وعصابة سياقية (Contextual Bandit - UCB)، وتعلم الـ Q (Q-Learning). الهدف هو تعظيم المكافأة، والمعرفة هنا هي إنتاجية فك التشفير (decode throughput).
القدرة على التكيف: تتعلم سياسة RL تشكيل دفعات "مثالية تمامًا"—كبيرة بما يكفي لاستغلال الوحدة الرسومية، ومتجانسة بما يكفي لتعظيم موضعية الذاكرة. وتتكيف ديناميكيًا مع كثافة عبء العمل وأنماط مشاركة البادئة.

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

تحديد مقايضة حرجة: يثبت البحث أن تجانس البادئة هو عامل أقوى في تحديد إنتاجية فك التشفير من حجم الدفعة وحده. ويوضح أنه حتى طلب واحد مختلف في الدفعة يمكن أن يخل بالموضعية ويقلل الإنتاجية بنسبة تقارب 2x.
قياس العبء على المعالج (CPU): يكشف المؤلفون أن آليات اكتشاف البادئة المتطورة (مثل تتبع أشجار الجذور في SGLang) تسبب أعباء على المعالج يمكن أن تصل إلى 50-90% من زمن التأخير الإجمالي، مما يلغي فعليًا فوائد إعادة استخدام البادئة.
مجدول Feather: تصميم وتنفيذ مجدول Feather، الذي يدمج هيكل بيانات CHT مع سياسة دفعات قائمة على التعلم التعزيزي (RL). تم دمج Feather في كل من vLLM وSGLang.
الاستقلالية عن الأجهزة: على عكس نوى الانتباه المدركة للبادئة (prefix-aware attention kernels) التي تتطلب ضبطًا خاصًا للأجهزة، يعمل Feather على طبقة الجدولة، مما يجعله متوافقًا مع نوى الانتباه وتكوينات الأجهزة الحالية.

النتائج

أُجري التقييم على وحدات معالجة رسومية من نوع NVIDIA RTX 6000 Ada وA100 باستخدام نماذج مثل Llama 3 8B وQwen وLongChat 13B عبر أعباء عمل متنوعة (L-Eval, LongBench).

مكاسب الإنتاجية: يحقق Feather إنتاجية نهائية أعلى بمقدار 2 إلى 10 أضعاف مقارنة بالمجدولات الحالية (FCFS الخاص بـ vLLM، وLPM/DFS-W الخاص بـ SGLang) في أعباء العمل التي تحتوي على بادئات مشتركة تتراوح بين 1K و10K رمز.
حساسية البادئة: في التجارب التي شملت 800 طلب مقسمة إلى 8 مجموعات بادئة، أدى معالجتها في 8 دفعات متجانسة تضم كل منها 100 طلب إلى إنتاجية أعلى بنسبة 2x تقريبًا مقارنة بمعالجتها في دفعات أكبر وغير متجانسة.
تقليل العبء: تقلل CHT في Feather من عبء اكتشاف البادئة بما يصل إلى 1000 ضعف مقارنة بنهج البحث العمق (DFS) للتسلسلات الطويلة. ويظل عبء الجدولة أقل من 1% من زمن تنفيذ الوحدة الرسومية، بينما يمكن أن تتجاوز النهج الأساسية زمن تنفيذ الوحدة الرسومية.
المتانة: يعمل Feather بمستوى مماثل للوضع الراهن (FCFS) عندما تفتقر أعباء العمل إلى مشاركة البادئة، مما يضمن عدم حدوث أي تدهور في الأداء في السيناريوهات غير المشتركة.
المقارنة مع النوى (Kernels): يتفوق Feather أو يضاهي نوى الانتباه المتخصصة المدركة للبادئة (مثل PAT) رغم عدم تعديله للنواة نفسها، مما يثبت أن التحسينات على مستوى الجدولة يمكن أن تكون فعالة مثل التحسينات على مستوى النواة.

الأهمية

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

يسلط العمل الضوء على أن تكلفة إيجاد البادئات المشتركة (العبء على المعالج) كانت عائقًا خفيًا في الأنظمة الحالية. وتوضح CHT الخفيفة وسياسة RL التكيفية في Feather أنه من الممكن الموازنة ديناميكيًا بين استغلال الحوسبة وموضعية الذاكرة، مما يؤدي إلى تحسينات جوهرية في كل من الإنتاجية وزمن التأخير لأعباء عمل استدلال LLM الواقعية. يخطط المؤلفون لجعل Feather مفتوح المصدر من خلال المساهمة به في مستودعات vLLM وSGLang.