ملخص تقني: التخزين المؤقت للبادئات المتفرقة لخدمة النماذج اللغوية الكبيرة الهجينة والمتكررة

1. بيان المشكلة

تعتمد أنظمة خدمة النماذج اللغوية الكبيرة (LLM) الحالية بشكل كبير على التخزين المؤقت الكثيف للبادئات (dense prefix caching)، حيث يتم تخزين حالات المفتاح/القيمة (KV) لكل رمز (token) في بادئة مشتركة لتجنب حسابات الـ prefill المكررة. هذا النهج هو المعيار لنماذج Transformer. ومع ذلك، تقدم نماذج فضاء الحالة (SSMs) والبنى الهجينة (التي تجمع بين الانتباه والطبقات المتكررة) عدم تماثل هيكلي: حيث تتطور الطبقة المتكررة في البنى الهجينة حالتها كـ $h_t = F(h_{t-1}, x_t)$، مما يعني أنها تستطيع استئناف الحساب من حالة واحدة مخزنة $h_c$ بدلاً من الحاجة إلى التاريخ الكامل للحالات الوسيطة.

غالباً ما يكون التخزين المؤقت لكل رمز (per-token) للحالات المتكررة غير ضروري ومكلف للغاية. بالنسبة لنماذج مثل Qwen-3.5، يتوسع حجم حالة التكرار لكل رأس (head) كـ $d_{head}^2$، بينما يتوسع تخزين KV للانتباه خطياً. وبناءً على ذلك، فإن تخزين الحالة المتكررة لكل رمز يستهلك ذاكرة أكبر بكثير من ذاكرة تخزين KV للانتباه، ومع ذلك لا يقدم أي فائدة إضافية فوق تخزين مجموعة مختارة من نقاط التحقق (checkpoints).

المشكلة الجوهرية التي يتم معالجتها هي: بالنظر إلى ميزانية ذاكرة قدرها $M$ من خانات نقاط التحقق لبادئة طولها $N$، أين يجب وضع نقاط التحقق لتقليل تكلفة إعادة الحساب المتوقعة تحت توزيع محدد لأعماق تداخل الطلبات المستقبلية؟ هذا التحسين يختلف عن سياسات قبول/طرد التخزين المؤقت؛ فهو يركز على أي الرموز يجب تخزين نقاط تحقق لها ضمن مدخل واحد محفوظ لتعظيم المنفعة لتقاطعات البادئة الجزئية.

2. المنهجية

الصياغة النظرية

يصيغ المؤلفون المشكلة كمسألة k-median موزونة أحادية الجانب على خط مستقيم.

• لتكن $C = \{c_1, \dots, c_M\}$ هي مجموعة مواضع نقاط التحقق.
• لطلب يتداخل مع البادئة حتى العمق $t$، يكون أعمق نقطة تحقق قابلة لإعادة الاستخدام هو $\ell(t; C) = \max(\{0\} \cup \{c \in C : c \le t\})$.
• التكلفة هي عدد الرموز المطلوب إعادة حسابها: $r(t; C) = t - \ell(t; C)$.
• الهدف هو تقليل تكلفة إعادة الحساب المتوقعة $E[r(T; C)]$ بناءً على توزيع عمق التداخل $T$ مع احتمالات $p_t$.

النهج الخوارزمي

1. الوضع المتوازن الأمثل (الموحد/الأسوأ حالاً): يثبت المؤلفون أنه في ظل توزيع تداخل موحد أو في السيناريو الأسوأ، يكون التباعد المتوازن (توزيع نقاط التحقق بالتساوي) هو الأمثل.
2. البرمجة الديناميكية الواعية بالتوزيع (DP): بالنسبة لتوزيعات التداخل غير الموحدة في العالم الحقيقي، يستنتج المؤلفون خوارزمية برمجة ديناميكية دقيقة بزمن $O(NM)$.
   • علاقة التكرار هي: $dp[m, j] = \min_{1 \le s \le j} (dp[m-1, s-1] + w(s, j))$، حيث $w(s, j)$ هي تكلفة استخدام $s$ كأعمق نقطة تحقق للأعماق من $s$ إلى $j$.
   • يتم حل هذه العلاقة بكفاءة باستخدام خدعة الغلاف المحدب الرتيب (monotone convex hull trick)، بالاستفادة من رتابة المجموع التراكمي.
3. التعامل مع انحراف التوزيع: بما أن توزيع التداخل الحقيقي غير معروف ويجب تقديره من البيانات التاريخية، يوفر البحث ضمانات نظرية (عبر Lemma 1 و Theorem 3) بأن دالة القيمة هي متصلة ليبشيتز (Lipschitz continuous) بالنسبة لتوزيع التداخل. وهذا يضمن أن استخدام مدرج تكراري تجريبي (empirical histogram) - أو مدرج تكراري بوزن أسي للتوزيعات المنحرفة - يؤدي إلى جدول زمني قريب من الأمثل مع عدم مثالية محدودة.

استراتيجية التنفيذ

• نقطة التحقق (Checkpointing): يقوم النظام بتخزين حالات متكررة دقيقة في مواضع متفرقة. عند حدوث إصابة في التخزين المؤقت (cache hit)، يستأنف النظام من أعمق نقطة تحقق مخزنة ويعيد حساب اللاحقة (suffix) بدقة.
  else
• الدقة: نظرًا لأن التحديث المتكرر حتمي، فإن الاستئناف من نقطة تحقق وإعادة تشغيل اللاحقة ينتج مخرجات مطابقة تماماً (bit-identical) لعملية الـ prefull الكاملة.
• التكامل الهجين: بالنسبة للنماذج الهجينة، يخزن النظام ذاكرة KV الكاملة للانتباه (كثيفة) ولكنه يطبق التخزين المؤقت المتفرق فقط على الطبقات المتكررة.

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

1. الأمثلية النظرية: إثبات أن التباعد المتوازن هو الأمثل في ظل التداخل الموحد وظروف الحالة الأسوأ (Theorem 1).
2. خوارزمية دقيقة: صياغة التخزين المؤقت للبادئات المتفرقة كمسألة k-median موزونة وتقديم حل برمجة ديناميكية دقيق بزمن $O(NM)$ (Theorem 2).
3. ضمانات المتانة: إثبات أن الجدول الزمني الأمثل مستقر تحت سوء توصيف التوزيع. يتم تحديد عدم المثالية عبر مسافة التباين الكلي بين التوزيع التجريبي وتوزيع التداخل الحقيقي (Theorem 3)، وتم التوسع في السيناريوهات التي تشهد انحرافاً في التوزيع باستخدام إعادة الوزن الأسي (Theorem 4).
4. التحقق التجريبي: التحقق من الطريقة باستخدام مجموعات بيانات من العالم الحقيقي (QuALITY, NarrativeQA, System Prompts)، مما أظهر تحسينات متسقة مقارنة بالنماذج المرجعية ذات الميزانية الثابتة.

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

مجموعات البيانات والإعدادات

• مجموعات البيانات:
  • QuALITY: وثيقة واحدة مع أسئلة متعددة (تداخل عالٍ بالقرب من الطول الكامل).
  • NarrativeQA: بنية مشابهة مع تداخل متعدد الوسائط واسع.
  • System Prompts: مطالبات النظام الفعلية مدمجة مع استعلامات المستخدم (التداخل يتركز عند الأطوال القصيرة).
• النماذج المرجعية: تمت المقارنة ضد "لا يوجد تخزين مؤقت" (No Cache)، "فقط KV" (KV Only)، "متوازن" (Balanced - تباعد متساوٍ)، "كتلة" (Block - حجم كتلة ثابت)، "لوغاريتمي" (Logarithmic)، واستراتيجية "المتباعدة بـ $\sqrt{L}$".
• الأجهزة: تجارب أولية على NVIDIA RTX 2080 Super مع نموذج Qwen-3.5-0.8B.

النتائج

• توفير الرموز (Tokens): يتفوق الجدول الزمني الأمثل المستمد من البرمجة الديناميكية (DP) باستمرار على النماذج المرجعية الحتمية (Balanced, Block, Logarithmic) من حيث عوامل تقليل العمل المتكرر.
• ميزة الميزانية المنخفضة: الفجوة في الأداء تكون أكبر عند ميزانيات نقاط التحقق المنخفضة حيث يكون توزيع التداخل غير منتظم للغاية. على سبيل المثال، في System Prompts (حيث تكون التداخلات قصيرة)، يضع منهج DP نقاط التحقق بكثافة بالقرب من ذروة التباعد، محققاً نفس زمن التشغيل الذي يحققه تخزين الكتلة (block caching) ولكن بعدد أقل من نقاط التحقق.
• وقت التنفيذ الفعلي (Wall-Clock Time): في QuALITY و System Prompts، يحقق الجدول الزمني المستمد من DP تسريعاً ملموساً في وقت التنفيذ الفعلي على مجموعات الطبقات التمثيلية. يرتبط تقليل وقت التشغيل خطياً بعدد الرموز التي تم توفيرها.
• العبء الإضافي (Overhead): العبء الناتج عن تحميل نقاط التحقق من وحدة المعالجة المركزية (CPU) إلى وحدة معالجة الرسومات (GPU) صغير جداً مقارنة بالتوفير الناتج عن تقليل إعادة الحساب، مما يؤدي إلى تحسن صافٍ في وقت التشغيل.

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

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

• المقايضة بين الذاكرة والحوسبة: يوفر مقايضة بين الذاكرة وإعادة الحساب لا يمكن لتخزين KV الكثيف توفيرها، وتحديداً للبنى التي يمكن استخراج حالتها واستعادتها بدقة.
• الدقة: بخلاف تقنيات ضغط KV التقريبية، تحافظ هذه الطريقة على مخرجات دقيقة دون تغيير نوى الحوسبة المتكررة (recurrent computation kernels).
• القابلية للتطبيق: تكون هذه الطريقة أكثر فائدة لأعباء العمل التي تشترك في بادئة جوهرية ولكن غير متطابقة تماماً (مثل RAG مع أسئلة متغيرة، أو مطالبات نظام متغيرة). وهي لا تقدم فوائد إضافية لأعباء عمل الدردشة التي تعتمد فقط على الإضافة (append-only) (حيث تكون الحالة الأخيرة كافية)، لكنها لا تسبب أي عبء في تلك الحالات.
• العمل المستقبلي: يقر المؤلفون بالتحديات الهندسية، وتحديداً الحاجة إلى واجهات برمجة تطبيقات (APIs) فعالة لاستخراج واستعادة الحالة في بيئات التشغيل الإنتاجية، ودمج استراتيجية الوضع هذه مع سياسات القبول/الطرد (مثل Marconi et al.). كما يشيرون إلى إمكانية توسيع نظرية البادئة الواحدة الحالية لتشمل أشجار البادئات العامة.