🤖 AI

Qrita: High-performance Top-k and Top-p using Pivot-based Truncation and Selection

تقدم الورقة البحثية Qrita، وهو خوارزمية عالية الأداء وحتمية لأخذ عينات Top-k وTop-p للمفردات الكبيرة، تستخدم تقنيات التقطيع والاختيار القائمة على المحور لتحقيق تحسن في الإنتاجية يصل إلى 1.4 ضعفاً وتقليلاً في الذاكرة بنسبة 50% مقارنة بنواة وحدات معالجة الرسومات الحالية، مما أدى إلى اعتماده كأداة أخذ العينات الافتراضية في vLLM.

المؤلفون الأصليون: Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica

نُشر 2026-05-27

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

CC BY 4.0

المؤلفون الأصليون: Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica

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

تخيل أنك طاهٍ يدير مطبخاً ضخماً (نموذج لغوي كبير) يحتوي على مخزن به 100,000 مكون مختلف (المفردات). في كل مرة تحتاج فيها إلى طهي طبق ما (توليد كلمة)، يتعين عليك اختيار أفضل بضعة مكونات من هذا المخزن العملاق لضمان أن الوجبة ستكون لذيذة ولكن ليست مملة.

في عالم الذكاء الاصطناعي، تسمى عملية الاختيار هذه Top-k (اختيار أفضل k من المكونات) و Top-p (اختيار أصغر مجموعة من المكونات التي تشكل "درجة نكهة" معينة).

المشكلة: المطبخ البطيء والمزدحم

حالياً، تتعامل معظم المطابخ مع هذا الأمر عن طريق سكب جميع المكونات الـ 100,000 على طاولة ضخمة، ثم ترتيبها حسب "درجة الطعم" من الأفضل إلى الأسوأ، ثم التقاط المكونات الأعلى جودة.

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

الحل: Qrita (مساعد الطاهي الذكي)

يقدم البحث Qrita، وهو طريقة جديدة عالية السرعة لاختيار المكونات. فكر في Qrita كمساعد طاهٍ ذكي للغاية يستخدم خدعتين بارعتين لتجنب عملية الفرز الفوضوية تماماً.

الخدعة الأولى: "التقليم الغاوسي لسيجما" (مرشح الضجيج)

تخيل أنه في مخزن المكونات الذي يحتوي على 100,000 عنصر، هناك 99,000 عنصر هي مجرد "ضجيج" (مثل الملح والسكر والدقيق، وكلها لها طعم باهت متشابه تقريباً). هناك فقط بضع مئات من "المكونات النجمية" (مثل الزعفران أو الكمأة).

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

النتيجة: يتخلص فوراً من 99% من المخزن، تاركاً حوالي 200 جرة مثيرة للاهتمام فقط. يحدث هذا في تمريرة واحدة سريعة كالبرق.

الخدعة الثانية: "البحث الرباعي المحوري" (التقسيم الرباعي)

الآن، أصبح لدى الطاهي كومة صغيرة تضم 200 مكون مثير للاهتمام. لا يزال يتعين عليه العثور على أفضل 50 بالضبط.

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

لماذا يهم هذا الأمر (النتائج)

قام المؤلفون ببناء Qrita باستخدام أداة متخصصة تسمى Triton (لغة لبرمجة بطاقات الرسوميات/GPUs) واختبروه مقابل أفضل الطرق الحالية المستخدمة في محركات الذكاء الاصطنا_ي الكبرى مثل vLLM و SGLang.

السرعة: Qrita أسرع بمقدار يصل إلى 1.4 مرة في سيناريوهات الخدمة الواقعية، وما يصل إلى مرتين في اختبارات السرعة الخام.
الذاكرة: يستخدم نصف الذاكرة لأنه لا يحتاج لتخزين القائمة المرتبة بالكامل لـ 100,000 عنصر.
الدقة: على عكس بعض الطرق السريعة التي تعتمد على التخمين، يعطيك Qrita نفس النتيجة تماماً التي تعطيها طريقة الترتيب البطيئة والمثالية. إنه لا يغير المخرجات؛ بل يجدها فقط بشكل أسرع بكثير.

الخلاصة

Qrita يشبه الترقية من طاهٍ يقوم بفرز كل توابل العالم يدوياً إلى مساعد ذكي يتجاهل الأشياء المملة فوراً، ويقسم الأشياء المثيرة للاهتمام إلى أربع كومات في آن واحد، ويتعامل مع المكونات المتكررة بشكل مثالي. إنه يجعل توليد الذكاء الاصطناعي أسرع وأكثر كفاءة دون تغيير جودة الإجابات.

ملاحظة: يذكر البحث أن Qrita أصبح الآن الطريقة الافتراضية لمسار وحدة معالجة الرسومات (GPU) في vLLM، وهي أداة شهيرة لتشغيل نماذج الذكاء الاصطناعي، والكود متاح للآخرين لاستخدامه.

ملخص تقني: Qrita - أداء عالٍ لعمليات Top-k و Top-p باستخدام تقنيات التقطيع والاختيار القائمة على المحور (Pivot-based)

بيان المشكلة

لا يزال التنفيذ الفعال لخوارزميات أخذ العينات من نوع Top-k و Top-p لنماذج اللغات الكبيرة (LLMs) ذات المفردات الضخمة (التي تتجاوز غالبًا 100,000 رمز/token) يمثل تحديًا كبيرًا على وحدات معالجة الرسومات (GPUs). تواجه الأساليب الحالية مقايضة بين الكفاءة الحسابية وصحة المخرجات:

الأساليب القائمة على الفرز (Sorting-based methods): تُستخدم في محركات مثل vLLM، وهي توفر نتائج دقيقة وحتمية، ولكنها تسبب عبئًا حسابيًا وذاكرة مرتفعين بسبب فرز المفردات الكاملة والوصول المشتت للذاكرة (strided memory accesses).
الأساليب العشوائية (Stochastic methods): تستخدم مكتبات مثل FlashInfer و SGLang أخذ عينات الرفض (rejection sampling) لتجنب الفرز، مما يوفر إنتاجية عالية. ومع ذلك، فهي تعيد رمزًا واحدًا فقط تم أخذ عينته بدلاً من مجموعة المرشحين الكاملة، مما يجعلها غير متوافقة مع المهام التي تتطلب مجموعات مرشحين حتمية، مثل التحقق من التشفير التخميني (speculative decoding verification) والتعلم التعزيزي (reinforcement learning).
أساليب القطع الإحصائي (Statistical cutoff methods): تلغي أساليب مثل Top-nσ و Min-p عملية الفرز باستخدام عتبات إحصائية (مثل المتوسط والانحراف المعياري). ورغم كفاءتها، إلا أنها تغير توزيع العينات والمخرجات، مما يثير نقاشات حول جودة التوليد والتماسك.

هناك فجوة حرجة لخوارزمية تقدم كفاءة في الذاكرة وسلوكًا حتميًا صارمًا (إعادة مجموعة المرشحين الكاملة) دون التضحية بالدلالات الدقيقة لـ Top-k و Top-p.

المنهجية

يقترح المؤلفون Qrita، وهي خوارزمية عالية الأداء لـ Top-k و Top-p لوحدات معالجة الرسومات تعتمد على التقطيع والاختيار القائم على المحور (pivot-based). تمدد Qrita استراتيجية المحور الخاصة بـ RTop-k (المصممة أصلاً للشبكات العصبية الرسومية) للتعامل مع مفردات LLM الضخمة مع ضمان الحتمية. تعتمد الطريقة على تقنيتين رئيسيتين:

1. التقطيع القائم على التوزيع الطبيعي $\sigma$ -Truncation

إدراكًا بأن قيم الـ logits في LLM تتبع عادةً توزيعًا شبه طبيعي (quasi-Gaussian) حيث تشكل الرموز ذات الاحتمالية العالية قيمًا متطرفة مقابل "ضجيج" خلفي، تستخدم Qrita خطوة تصفية مسبقة.

الآلية: تقرب الخوارزمية توزيع الـ logit كـ $Z \sim \mathcal{N}(\mu, \sigma^2)$ . وتقوم بحساب المتوسط ( $\mu$ ) والانحراف المعياري ( $\sigma$ ) من كتلة عينة، ثم تحسب عتبة التقطيع $t = \mu + \delta \cdot \sigma$ .
جداول البحث (Lookup Tables): يتم تحديد المعامل $\delta$ عبر جداول بحث محسوبة مسبقًا مشتقة من دالة التوزيع الطبيعي الكمي (normal quantile function)، والمصممة خصيصًا لقيم $k$ أو $p$ المستهدفة.
النتيجة: تقوم هذه الخطوة بتقطيع منطقة "الضجيج" الهائلة من المفردات في تمريرة واحدة. إذا تجاوز حجم المجموعة المقطعة $|Z_t|$ القيمة المستهدفة $k$ (وهو ما يسمى "ضربة التقطيع" أو truncation hit)، تستمر عملية البحث فقط على هذا الجزء الأصغر. وإذا لم يكن الأمر كذلك، يتم الرجوع إلى مجموعة الـ logit الكاملة. وهذا يقلل بشكل كبير من مساحة البحث لعملية بحث المحور اللاحقة.

2. البحث الرباعي للمحور مع معالجة التكرار (Quaternary Pivot Search with Duplication Handling)

لإيجاد قيمة المحور $\tau$ الدقيقة (حيث يكون عدد العناصر $\ge \tau$ هو $k$ بالضبط) بكفاءة وحتمية:

البحث الرباعي (Quaternary Search): بدلًا من البحث الثنائي، تقوم Qrita بتقييم ثلاثة محاور (عند المئويات 25 و 50 و 75 من نطاق البحث الحالي) في كل تكرار. هذا يقلل عدد تكرارات البحث إلى النصف مقارنة بالبحث الثنائي.
معالجة التكرار (Duplication Handling): يمكن أن تفشل عمليات بحث المحور القياسية أو تصبح غير حتمية عند وجود قيم logit مكررة (وهو أمر شائع في التوزيعات ذات الدقة المنخفضة أو الذيل الطويل). تتبع Qrita الحد الأدنى لقيمة الـ logit الأكبر من المحور ( $z_{mn}$ ) وعدد تكرارها ( $N_{zmn}$ ).
شرط الإنهاء: ينتهي البحث عندما يتم العثد على محور $\tau_n$ بحيث يكون عدد العناصر الأكبر تمامًا من $\tau_n$ أقل من $k$ ، ولكن عدد العناصر الأكبر من أو المساوية للحد الأدنى من القيمة المكررة $z_{mn}$ هو أكبر من أو يساوي $k$ . يسمح هذا للخوارزمية بتحديد عدد النسخ المكررة من القيمة الحدية التي يجب الاحتفاظ بها بدقة لتحقيق قيد Top-k، مما يضمن مخرجات قابلة للتكريد وحتمية.

تفاصيل التنفيذ

إطار العمل: تم التنفيذ باستخدام Triton، وهي لغة برمجة لوحدات معالجة الرسومات.
الضبط التلقائي (Autotuning): تستخدم استراتيجية "الضبط التلقائي لحجم كتلة Triton متعدد المستويات". نظرًا لأن حجم المتجه يتغير بشكل جذري بين مجموعة الـ logit الكاملة والمجموعة المقطعة، يُسمح للمترجم باختيار أحجام كتل مثالية (على سبيل المثال، كتل أكبر للمجموعات الكاملة، وكتل أصغر للمجموعات المقطعة) لزيادة الاستفادة من الأجهزة.
خط الإنتاج (Pipeline): تعالج الخوارزمية الدفعات بالتوازي، حيث تطبق التقطيع الغاوسي، يليه البحث الرباعي، وأخيرًا توليد قناع معالجة التكرار لإنتاج المخرج النهائي.

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

أخذ عينات عالي الأداء وحتمي: توفر Qrita مجموعة المرشحين الكاملة لـ Top-k/Top-p (على عكس FlashInfer/SGLang) مع الحفاظ على الدلالات الدقيقة لخوارزميات الفرز، مما يجعلها مناسبة للتشفير التخميني والتعلم التعزيزي.
تقليص مساحة البحث: من خلال الاستفادة من الخصائص الإحصائية للـ logits، يقلل التقطيع الغاوسي $\sigma$ مساحة البحث بشكل كبير، متجنبًا فرز المفردات الكاملة.
بحث محور قوي: يوفر إدخال البحث الرباعي مع معالجة التكرر الصريحة سلوكًا حتميًا ويقلل من عدد التكرارات، مما يعالج عدم كفاءة طرق البحث بالمحور القياسية في المفردات الضخمة.
التكامل: تم تنفيذ Qrita كأخذ عينات افتراضي لـ Top-k و Top-p لمسار تنفيذ وحدة معالجة الرسومات في vLLM.

النتائج

قيم المؤلفون Qrita مقابل خطوط الأساس بما في ذلك فرز PyTorch البدائي، وSampler الخاص بـ vLLM، وFlashInfer، وSGLang على وحدات NVIDIA H100 و RTX4090 و AMD MI355X باستخدام نماذج متنوعة (Llama, Qwen, GPT-OSS, Gemma).

الإنتاجية (Throughput): تحقق Qrita تحسنًا يصل إلى 1.4× في إنتاجية الخدمة النهائية مقارنة بـ vLLM baseline على H100، مع بعض الإعدادات التي تظهر تحسنًا يصل إلى 2× على RTX4090. وهي تتفوق على خطوط الأساس القائمة على الفرز بشكل ملحوظ بينما تطابق مخرجات خوارزميات الفرز.
استخدام الذاكرة: تقلل Qrita استخدام الذاكرة بنسبة تقارب 50% مقارنة بالطرق القائمة على الفرز، وذلك أساسًا عبر تجنب تخصيص مخازن مؤقتة كبيرة مطلوبة للفرز.
دراسات الاستبعاد (Ablation Studies):
- التقطيع الغاوسي (Gaussian Truncation): يوفر أكبر تسريع، حيث يقلل زمن التأخير بنسبة ~74% مقارنة بالبحث في مجموعة الـ logit الكاملة.
- البحث الرباعي (Quaternary Search): رغم أنه أبطأ قليلاً من البحث الثنائي في حالات "ضربة التقطيع" بسبب تقليل مساحة البحث، إلا أنه يوفر تقليلًا كبيرًا في زمن التأخير (~2.3ms) في حالات التراجع حيث يجب البحث في المفردات الكاملة.
- معالجة التكرار (Duplication Handling): تضيف عبئًا طفيفًا (~3.5% زيادة في زمن التأخير) ولكنها حاسمة للصحة والحتمية.
- الضبط التلقائي (Autotuning): يقلل زمن تنفيذ التأخير بنسبة تقارب 30% مقارًا باستخدام حجم كتلة ثابت واحد.

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

يزعم البحث أن Qrita تسد الفجوة بين كفاءة الذاكرة والسلوك الحتمي الصارم لفك التشفير ذي المفردات الكبيرة. وتؤكد أن Qrita، من خلال تجنب فرز المفردات الكاملة والاستفادة من اختيار المحور مع التصفية الإحصائية المسبقة، تقدم حلاً عالي الأداء لفك تشفير LLM يتوافق مع المهام المتقدمة التي تتطلب مجموعات مرشحين كاملة (مثل التشفير التخميني). يضع المؤلفون Qrita ليس كبديل للدلالات الإحصائية لـ Top-k/Top-p، بل كتنفيذ فعال يحافظ عليها بدقة، على عكس طرق القطع الإحصائي التجريبية أو أخذ عينات الرمز الواحد العشوائي. ويؤكد دمجها في vLLM كأخذ عينات افتراضي على فائدتها العملية في بيئات الإنتاج.