2025-11-16T09:58:12.370377

Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference

Feng, Lv, Cao et al.
Large Language Models have excelled in various domains but face efficiency challenges due to the growing Key-Value (KV) cache required for long-sequence inference. Recent efforts aim to reduce KV cache size by evicting vast non-critical cache elements during runtime while preserving generation quality. However, these methods typically allocate compression budgets uniformly across all attention heads, ignoring the unique attention patterns of each head. In this paper, we establish a theoretical loss upper bound between pre- and post-eviction attention output, explaining the optimization target of prior cache eviction methods, while guiding the optimization of adaptive budget allocation. Base on this, we propose {\it Ada-KV}, the first head-wise adaptive budget allocation strategy. It offers plug-and-play benefits, enabling seamless integration with prior cache eviction methods. Extensive evaluations on 13 datasets from Ruler and 16 datasets from LongBench, all conducted under both question-aware and question-agnostic scenarios, demonstrate substantial quality improvements over existing methods. Our code is available at https://github.com/FFY0/AdaKV.
academic

Ada-KV: تحسين إخلاء ذاكرة التخزين المؤقت KV من خلال تخصيص الميزانية التكيفية لاستدلال نماذج اللغة الكبيرة الفعال

المعلومات الأساسية

  • معرّف الورقة: 2407.11550
  • العنوان: Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference
  • المؤلفون: Yuan Feng, Junlin Lv, Yukun Cao, Xike Xie, S. Kevin Zhou
  • التصنيف: cs.CL cs.AI
  • وقت النشر/المؤتمر: المؤتمر الـ 39 حول أنظمة معالجة المعلومات العصبية (NeurIPS 2025)
  • رابط الورقة: https://arxiv.org/abs/2407.11550

الملخص

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

الخلفية البحثية والدافع

وصف المشكلة

مع النمو المستمر في طول التسلسل الذي تعالجه نماذج اللغة الكبيرة (مثل GPT يدعم 128K، وClaude3 يدعم 200K، وGemini-Pro-1.5 يدعم 2M tokens)، ينمو الطلب على ذاكرة التخزين المؤقت KV بشكل أسي. بالنسبة لنموذج LLM بـ 8B معاملات، قد تتطلب معالجة تسلسل واحد بـ 2M token ما يصل إلى 256GB من الذاكرة المؤقتة، مما يؤثر بشكل خطير على كفاءة ذاكرة GPU وكفاءة وقت تشغيل الحساب.

قيود الطرق الموجودة

تنقسم طرق إخلاء الذاكرة المؤقتة الموجودة بشكل أساسي إلى فئتين:

  1. طرق إخلاء النافذة المنزلقة: تحتفظ ببساطة بالعناصر الأولية والحديثة من الذاكرة المؤقتة، لكنها تقلل بشكل كبير من جودة التوليد
  2. طرق إخلاء Top-k: تختار عناصر ذاكرة تخزين مؤقت حرجة بناءً على أوزان الانتباه، لكنها توزع الميزانية بشكل موحد عبر جميع رؤوس الانتباه

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

الدافع البحثي

من خلال تحليل نموذج Llama-3.1-8B-Instruct، اكتشف المؤلفون أن معظم رؤوس الانتباه تحتاج فقط إلى نسبة ذاكرة تخزين مؤقت صغيرة (مثل أفضل 5%) للاحتفاظ بجميع أوزان الانتباه تقريباً، بينما تتطلب الرؤوس المتشتتة نسبة ذاكرة تخزين مؤقت أكبر. يوفر هذا النمط غير المتساوي لتركيز الانتباه أساساً نظرياً لتخصيص الميزانية التكيفية.

المساهمات الأساسية

  1. استراتيجية تخصيص الميزانية التكيفية: تقترح أول استراتيجية تخصيص ميزانية تكيفية على مستوى الرأس Ada-KV، والتي يمكنها ديناميكياً تعديل تخصيص الميزانية وفقاً لأنماط الانتباه الفريدة لكل رأس انتباه
  2. إنشاء إطار نظري: ينشئ إطار نظري لإخلاء الذاكرة المؤقتة، ويحدد خسارة الإخلاء ويشتق حده الأعلى، مما يشرح الأهداف الحسابية للطرق الموجودة ويوجه تصميم Ada-KV
  3. توافقية الإدراج والتشغيل: يتمتع Ada-KV بخاصية الإدراج والتشغيل، مما يتيح التكامل السلس مع طرق إخلاء الذاكرة المؤقتة الموجودة، والحفاظ على الكفاءة الحسابية من خلال نوى CUDA فعالة
  4. التحقق التجريبي الشامل: إجراء تقييم شامل على 29 مجموعة بيانات من Ruler و LongBench، مما يُظهر تحسينات كبيرة في كل من السيناريوهات التي تدرك المشكلة والسيناريوهات التي لا تدرك المشكلة

شرح الطريقة

تعريف المهمة

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

الأساس النظري

تعريف خسارة الإخلاء L1

يقيس المؤلفون خسارة الإخلاء كمسافة L1 بين مخرجات آلية الانتباه الذاتي قبل وبعد الإخلاء:

خسارة الإخلاء L1=∣∣y−y^∣∣1\text{خسارة الإخلاء L1} = ||y - \hat{y}||_1

حيث yy و y^\hat{y} هما مخرجات الانتباه قبل وبعد الإخلاء على التوالي.

اشتقاق الحد الأعلى للخسارة

النظرية 3.1: يمكن تقييد خسارة الإخلاء L1 بالحد الأعلى ϵ\epsilon:

خسارة الإخلاء L1≤ϵ=2hC−2C∑i∈[1,h]∑j∈[1,n]IijAij\text{خسارة الإخلاء L1} \leq \epsilon = 2hC - 2C\sum_{i \in [1,h]}\sum_{j \in [1,n]} I_i^j A_i^j

حيث C=max⁡{∥ViWiO∥∞}C = \max\{\|V_iW_i^O\|_\infty\} ثابت، IijI_i^j متغير مؤشر قرار الإخلاء، و AijA_i^j وزن الانتباه.

النظرية 3.2: طريقة إخلاء ذاكرة التخزين المؤقت Top-k يمكنها تقليل الحد الأعلى للخسارة بالنظر إلى تخصيص ميزانية معين:

ϵ∗=2hC−2C∑i∈[1,h]∑Aij∈Top-k(Ai,k=Bi)Aij\epsilon^* = 2hC - 2C\sum_{i \in [1,h]}\sum_{A_i^j \in \text{Top-k}(A_i, k=B_i)} A_i^j

خوارزمية Ada-KV

الخوارزمية 1: تخصيص الميزانية التكيفية

الإدخال: الميزانية الإجمالية B، أوزان الانتباه لكل رأس {A_i}
الإخراج: ميزانيات التخصيص {B_i^*}
1. ربط أوزان الانتباه لجميع الرؤوس: A = Cat({A_i})
2. اختر أفضل B وزن من A: Top-k(A, k=B)
3. احسب عدد الأوزان المختارة لكل رأس: {f_i}
4. اضبط ميزانيات التخصيص: {B_i^* = f_i}

المزايا النظرية

النظرية 3.3: يمكن لتخصيص الميزانية التكيفية تحقيق أقل حد أعلى للخسارة:

ϵ∗∗=min⁡{Bi}ϵ∗\epsilon^{**} = \min_{\{B_i\}} \epsilon^*

التكامل مع الطرق الموجودة

يُظهر المؤلفون تكامل Ada-KV مع طريقتي SOTA:

Ada-SnapKV و Ada-Pyramid

من خلال الخوارزمية 2، يمكن لـ Ada-KV التكامل بسلاسة مع SnapKV و Pyramid:

  1. احسب أوزان الانتباه ضمن نافذة المراقبة
  2. استخدم خوارزمية Ada-KV لتخصيص الميزانية
  3. طبّق معامل الحماية الآمن α = 0.2 لمنع التخصيص المفرط للتناثر
  4. نفّذ قرارات إخلاء Top-k

نقاط الابتكار التقني

  1. منظور التحسين العام: ينظر إلى تخصيص الميزانية على مستوى الرأس كمشكلة تحسين عامة وليس محلية
  2. التصميم الموجه نظرياً: يوجه التصميم الخوارزمي بناءً على تحليل نظري صارم
  3. ضمان الكفاءة الحسابية: يحافظ على الكفاءة الحسابية من خلال FlashAttention متغير الطول وتخطيط الذاكرة المؤقتة المسطح
  4. توافقية GQA: يدعم Group Query Attention، مما يحقق ضغط ذاكرة تخزين مؤقت إضافي

إعداد التجارب

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

  • معيار Ruler: 13 مهمة تسلسل طويل، تركز بشكل أساسي على متغيرات اختبار Needle-in-a-Haystack، تقييم بطول 16K
  • معيار LongBench: 16 مجموعة بيانات، تغطي الإجابة على أسئلة المستند الواحد، الإجابة على أسئلة المستندات المتعددة، التلخيص، التعلم بعدد قليل من الأمثلة، المهام الاصطناعية، وتوليد الأكواد

النماذج الأساسية

  • Llama-3.1-8B-Instruct
  • Mistral-7B-instruct-v0.2

مقاييس التقييم

استخدم المقاييس المناسبة حسب نوع المهمة: درجة F1 (مهام الإجابة على الأسئلة)، Rouge-L (مهام التلخيص)، الدقة (مهام التصنيف)، تشابه التحرير (مهام الأكواد)

طرق المقارنة

  • الطرق الأساسية: SnapKV، Pyramid، StreamingLLM
  • النسخ المحسّنة: Ada-SnapKV، Ada-Pyramid

سيناريوهات التجارب

  • الضغط الذي يدرك المشكلة: السيناريو القياسي حيث تكون المشكلة معروفة
  • الضغط الذي لا يدرك المشكلة: سيناريو تطبيق فعلي أكثر تحدياً

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

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

اختبارات معيار Ruler

في سيناريو عدم إدراك المشكلة، باستخدام Llama-3.1-8B-Instruct:

  • ميزانية 80%: ترفع Ada-SnapKV درجة SnapKV من 87.59 إلى 92.67
  • ميزانية 20%: ترفع Ada-SnapKV درجة SnapKV من 44.02 إلى 53.29

اختبارات معيار LongBench

في سيناريو عدم إدراك المشكلة:

  • تحسّن Ada-SnapKV و Ada-Pyramid بشكل مستمر جودة التوليد تحت جميع إعدادات الميزانية الثابتة
  • تقترب من الأداء الخالي من الخسائر عند ميزانية 2048

تحليل المهام الفرعية

في مهام Needle-in-a-Haystack الصعبة:

  • مهمة S-NIAH-3 (ميزانية 80%): ترفع Ada-SnapKV SnapKV من 62.4 إلى 97.6
  • مهمة MK-NIAH-2 (ميزانية 80%): ترفع Ada-SnapKV SnapKV من 85.2 إلى 99.6

الكفاءة الحسابية

Ada-SnapKV عند ميزانية ثابتة 1024:

  • استخدام الذاكرة ذروة مماثل لـ SnapKV الأصلي
  • تأخير فك التشفير مماثل لـ SnapKV الأصلي
  • كلاهما يتفوق بشكل كبير على حالة الذاكرة المؤقتة الكاملة

التحقق من التطبيق الواسع

تم اعتماد استراتيجية Ada-KV من قبل عدة أعمال لاحقة:

  • CriticalKV + Ada-KV: ترفع من 42.99 إلى 43.77 عند ميزانية 20%
  • DefensiveKV + Ada-KV: ترفع من 43.78 إلى 46.68 عند ميزانية 20%

الأعمال ذات الصلة

طرق إخلاء الذاكرة المؤقتة

  • طرق النافذة المنزلقة: StreamingLLM وغيرها، بسيطة لكن بخسارة جودة كبيرة
  • طرق Top-k: H2O، SnapKV، Pyramid وغيرها، تختار العناصر الحرجة بناءً على أوزان الانتباه

طرق الانتباه المتناثر

مرتبطة بإخلاء الذاكرة المؤقتة من الناحية المفاهيمية لكن بطرق مختلفة:

  • إخلاء الذاكرة المؤقتة: الاحتفاظ بمجموعة فرعية من ذاكرة التخزين المؤقت KV
  • الانتباه المتناثر: الاحتفاظ بجميع الإدخالات لكن الاستخدام الانتقائي

تقنيات ذات صلة أخرى

  • تكمية ذاكرة التخزين المؤقت KV: تقليل دقة العناصر الفردية
  • فك التشفير المضارب: استخدام نماذج بذاكرة تخزين مؤقت مخفضة لتوليد مسودات
  • الانتباه المقسّم: إدارة الذاكرة الفعالة

الخلاصة والنقاش

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

  1. تقترح Ada-KV للمرة الأولى استراتيجية تخصيص ميزانية تكيفية على مستوى الرأس، مما يحسّن بشكل كبير أداء طرق إخلاء الذاكرة المؤقتة الموجودة
  2. يوفر التحليل النظري إطار عمل صارم لإخلاء الذاكرة المؤقتة، موجهاً تصميم الخوارزمية
  3. يكشف سيناريو الضغط الذي لا يدرك المشكلة عن قيود الطرق الموجودة، وينبغي أن يحظى باهتمام أكبر

القيود

  1. التخصيص على مستوى الرأس الحالي لا يزال محدوداً ضمن طبقة واحدة، لم يتم توسيعه إلى تخصيص عبر الطبقات
  2. معامل الحماية الآمن α يحتاج إلى موازنة الأداء تحت ميزانيات مختلفة
  3. يعتمد التحليل النظري على مسافة L1، وقد لا يعكس بشكل كامل جودة التوليد الفعلية

الاتجاهات المستقبلية

  1. توسيع آلية التخصيص على مستوى الرأس إلى سيناريوهات عبر الطبقات
  2. تطوير تحليل نظري مقابل عبر الطبقات
  3. دمج تحليل أهمية الرأس في وقت التدريب
  4. التحسين المشترك مع تقنيات تحسين أخرى (مثل التكمية والانتباه المتناثر)

التقييم المتعمق

المزايا

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

أوجه القصور

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

التأثير

  1. المساهمة الأكاديمية: توفير اتجاه بحثي جديد لمجال تحسين ذاكرة التخزين المؤقت KV
  2. القيمة العملية: خاصية الإدراج والتشغيل تجعلها سهلة النشر في الأنظمة الفعلية
  3. قابلية إعادة الإنتاج: توفير أكواد مفتوحة المصدر وتفاصيل تنفيذ مفصلة
  4. الإلهام: توفير إطار عمل نظري وإرشادات منهجية للأبحاث اللاحقة

السيناريوهات المناسبة

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

المراجع

تستشهد الورقة بـ 64 مرجعاً ذا صلة، تتضمن بشكل أساسي:

  • الأعمال الأساسية لنماذج اللغة الكبيرة (GPT-4, Claude, Gemini وغيرها)
  • طرق تحسين ذاكرة التخزين المؤقت KV (H2O, SnapKV, Pyramid وغيرها)
  • تحسينات آليات الانتباه (FlashAttention، الانتباه المتناثر وغيرها)
  • معايير معالجة التسلسلات الطويلة (Ruler, LongBench وغيرها)

التقييم الإجمالي: هذه ورقة بحثية عالية الجودة حققت توازناً جيداً بين المساهمات النظرية والقيمة العملية. طريقة Ada-KV بسيطة وفعالة، والتحليل النظري صارم، والتحقق التجريبي شامل. لا تحل الورقة فقط قيوداً مهمة في الطرق الموجودة، بل توفر أيضاً إطار عمل واتجاهات قيمة للأبحاث المستقبلية.