FreeKV: Boosting KV Cache Retrieval for Efficient LLM Inference

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

يتم نشر النماذج اللغوية الكبيرة (LLMs) بشكل متزايد مع نوافذ سياق ضخمة (تصل إلى مليون رمز/token) للتعامل مع المهام المعقدة مثل تحليل المستندات الطويلة والاستدلال متعدد الخطوات. ومع ذلك، يخلق هذا عائقاً حرجاً: حيث ينمو حجم ذاكرة الـ KV (Key-Value) cache خطياً مع طول السياق، مما يؤدي غالباً إلى تجاوز سعة ذاكرة وحدة معالجة الرسومات (GPU) والتسبب في زمن انتقال (latency) شديد مرتبط بحدود الذاكرة أثناء عملية التوليد (decoding).

تنقسم الحلول الحالية إلى فئتين، كلتاهما تعاني من عيوب كبيرة:

• إسقاط الـ KV (KV Dropping): يقوم بطرد الرموز "غير المهمة" بشكل دائم. ورغم كفاءته، إلا أنه يتسبب في تدهور كبير في الدقة، خاصة في مهام التوليد الطويل والاستدلال حيث تكون أهمية الرموز ديناميكية.
• استرجاع الـ KV (KV Retrieval): يحتفظ بكامل ذاكرة الـ KV cache ولكنه يختار مجموعة فرعية فقط لحساب الانتباه (attention). ورغم دقتها، تعاني الطرق الحالية من اختناقات في الكفاءة:
  • تأخير الإخراج (Offloading Latency): ليتناسب مع السياقات الضخمة، غالباً ما يتم نقل ذاكرة الـ KV cache إلى ذاكرة الـ CPU. ويؤدي استدعاء البيانات من الـ CPU إلى الـ GPU إلى تأخير عالٍ بسبب انخفاض عرض نطاق PCIe.
  • عبء الاختيار (Selection Overhead): تقييم (Scoring) السياق بأكمله لاختيار الرموز هو عملية مكلفة حوسبياً.
  • التداخل غير الفعال (Inefficient Overlap): تفشل الطرق الحالية (مثل InfiniGen وShadowKV) في إخفاء زمن انتقال الاستدعاء (recall latency) بالكامل خلف العمليات الحوسبية، مما يؤدي إلى تباطؤ كبير مقارنة باستنتاج الذاكرة الكاملة (full-cache inference).

2. المنهجية: FreeKV

إن FreeKV هو إطار عمل للتنسيق المشترك بين الخوارزمية والنظام (algorithm-system co-optimization framework)، صُمم لتحقيق دقة تقارب الدقة الكاملة مع تعظيم كفاءة الاسترجاع.

أ. الابتكارات الخوارزمية

1. الاسترجاع التخميني (Speculative Retrieval):

   • الملاحظة: لاحظت الورقة أن متجهات الاستعلام ($q$) بين خطوات التوليد المتجاورة تظهر تشابهاً جيبياً (cosine similarity) مرتفعاً للغاية (غالباً >0.9). وبناءً على ذلك، فإن مجموعة رموز KV المختارة لخطوة $i$ من المرجح جداً أن تكون مطابقة للخطوة $i-1$.
   • الآلية: ينقل FreeKV عمليات الاختيار والاستدعاء خارج المسار الحرج (critical path). فبدلاً من اختيار واستدعاء أزواج الـ KV لخطوة $i$ قبل الحساب، فإنه يعيد استخدام أزواج الـ KV التي تم استدعاؤها في الخطوة $i-1$.
   • الفائدة: يسمح هذا بعملية إخفاء كاملة لزمن انتقال عمليات الاختيار والاستدعاء لخطوة $i$ عبر تداخلها مع عمليات حساب الانتباه (attention) والـ FFN للطبقة الحالية.

2. التصحيح دقيق التفاصيل (Fine-Grained Correction):

   • المشكلة: يمكن أن يؤدي إعادة الاستخدام البحت إلى فقدان الدقة إذا تغير توزيع الاستعلام بشكل كبير.
   • الآلية: يقوم FreeKV بمراقبة التشابه الجيبي ($C_i$) بين الاستعلام الحالي واستعلام الخطوة السابقة. إذا انخفضت $C_i$ عن حد معين $\tau$، يتم تفعيل التصحيح.
   • التنفيذ: تخضع رؤوس الـ KV التي تتطلب التصحيح فقط لعمليتي الاختيار والاستدعاء قبل حساب الانتباه. أما الرؤوس التي لم تحتاج لتصحيح، فتستمر في إعادة استخدام بيانات الخطوة السابقة. وهذا يقلل العبء مع ضمان الدقة.

3. الاختيار المتسق للمجموعات (Group-Consistent Selection):

   • لدعم "انتباه الاستعلام المجموعاتي" (GQA) بكفاءة، يضمن FreeKV أن جميع رؤوس الانتباه ضمن مجموعة GQA تختار صفحات الـ KV نفسها. ويحقق ذلك عبر تطبيق "متوسط التجميع" (mean pooling) على أوزان انتباه softmax للمجموعة، مما يقلل عبء الوصول إلى الذاكرة بمعامل قدره $G$ (حجم المجموعة).

ب. تحسينات مستوى النظام

1. تخطيطات هجينة لـ KV (Hybrid KV Layouts):

   • المشكلة: تسبب تخطيطات NHD (الدفعة، الرأس، التسلسل، البعد) القياسية عمليات نقل ذاكرة مجزأة عند استدعاء صفحات محددة لرؤوس مختلفة.
   • الحل: يستخدم FreeKV تخطيط NHD على الـ GPU (لتجنب عبء التحويل Transpose أثناء التوليد) وتخطيط HND على الـ CPU (لضمان كتل ذاكرة متصلة لنقل PCIe فعال). ويتم احتساب تكلفة تحويل التخطيط فقط أثناء عملية الإخراج (offloading)، وليس في كل خطوة.

2. الاستدعاء المتدفق مزدوج التخزين (Double-Buffered Streamed Recall):

   • لمنع تحويل التخطيط ونقل البيانات من عرقلة الحوسبة، يستخدم FreeKV آلية التخزين المزدوج (double-buffering). بينما يتم تحويل أحد المخازن من HND إلى NHD، يتم نقل الصفحة التالية في وقت واحد إلى المخزن الثاني. وهذا يتيح الاستدعاء المتدفق (streamed recall)، مما يحقق تداخلاً كاملاً لحركة البيانات مع حوسبة الـ GPU.

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

• التصميم المشترك بين الخوارزمية والنظام: يعد FreeKV أول إطار عمل يدمج التخزين التخميني (الخوارزمية) مع تخطيطات الذاكرة الهجينة والتخزين المزدوج (النظام) لحل مشكلة كفاءة استرجاع الـ KV.
• الآلية التخمينية: يقدم نهج "الاستدعاء التخميني" المبتكر الذي يستفيد من تشابه الاستعلام لإخفاء زمن انتقال الاختيار/الاستدعاء، مما يلغي الحاجة إلى إعادة الإسقاط المكلفة (على عكس InfiniGen).
  * خالٍ من التدريب (Training-Free): على عكس بعض طرق الضغط القائمة على التعلم، لا يتطلب FreeKV أي إعادة تدريب أو ضبط دقيق للنموذج.
• دقة تقارب الدقة الكاملة: يحافظ على دقة مماثلة لاستنتاج كامل ذاكرة الـ KV عبر مهام متنوعة، بما في ذلك الأسئلة والأجوبة ذات السياق الطويل، التلخيص، والاستدلال المعقد.

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

قيم المؤلفون FreeKV على نماذج مثل Llama-3.1-8B و Qwen-2.5 (7B/14B) و DeepSeek-R1 عبر اختبارات تشمل LongBench v2 و LongGenBench ومجموعات بيانات الاستدلال (MATH500, AIME24, GPQA).

• الدقة:

  • يحقق FreeKV دقة تقارب الدقة الكاملة، وغالباً ما يطابق أو يتفوق قليلاً على خط الأساس (full KV cache).
  • يتفوق بشكل كبير على طرق إسقاط الـ KV (مثل RazorAttention و RaaS) في مهام الاستدلال والتوليد الطويل، حيث تعاني طرق الإسقاط من انخفاض حاد في الدقة.
  • يتفوق على طرق الاسترجاع الأخرى (مثل Quest و ArkVale و ShadowKV و InfiniGen) في الدقة، خاصة في مهام الاستدلال المعقدة.

• الكفاءة:

  • التسريع: يوفر FreeKV تسريعاً يصل إلى 13.7 ضعفاً مقارنة بطرق استرجاع الـ KV الأحدث (مثل ArkVale) وما يصل إلى 8.4 ضعفاً مقارنة بـ ShadowKV.
  • إخفاء زمن الانتقال: يحقق النظام إخفاءً كاملاً لزمن انتقال عمليات الاستدعاء، مما يجعل زمن الانتقال النهائي (end-to-end) مقارباً لطرق إسقاط الـ KV الفعالة مع الاحتفاظ بدقة الاسترجاع الكامل.
  • القابلية للتوسع: يزداد التسريع مع زيادة أحجام الدفعات (batch sizes) وأطوال التوليد، حيث يصبح عبء الاستدعاء أكثر هيمنة في الطرق الأخرى.

5. الأهمية

يعالج FreeKV المقايضة الجوهرية بين الدقة والكفاءة في استنتاج النماذج اللغوية الكبيرة ذات السياق الطويل. ومن خلال إثبات أن الاسترجاع التخميني، مقترناً بتحسينات مستوى النظام، يمكن أن يلغي زمن انتقال استرجاع الـ KV، فإنه يتيح النشر العملي للنماذج اللغوية الكبيرة ذات نوافذ السياق الضخمة على الأجهزة القياسية دون التضحية بأداء النموذج. يضع هذا العمل حدوداً جديدة (Pareto frontier)، موضحاً أن الاسترجاع عالي الدقة يمكن أن يكون سريعاً (أو أسرع) من طرق الإسقاط التقريبية.