💻 computer science

Trie Automata for Constrained Decoding over Large Finite Sets

تقدم هذه الورقة البحثية "تري أوتوماتون" (trie automaton)، وهي آلية متخصصة تستفيد من مطابقة الأنماط المتعددة لـ "أهو-كوراسيك" (Aho-Corasick) لحساب أقنعة الرموز مسبقاً لفك التشفير المقيد بمجموعات محدودة، مما يحقق إنتاجية أعلى بما يصل إلى 29 ضعفاً وعملية تجميع أسرع بكثير مقارنة بالأنظمة الحالية مثل "إكس جرامر" (XGrammar) مع ضمان صحة المخرجات بنسبة 100%.

المؤلفون الأصليون: Xingzi Xu, Karim Bouyarmane

نُشر 2026-08-14

📖 6 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Xingzi Xu, Karim Bouyarmane

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

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

يعمل هذا بشكل رائع عندما تكون القائمة قصيرة، مثل وصفة تحتوي على ثلاثة مكونات. ولكن ماذا لو كانت القائمة ضخمة؟ تخيل وصفة تقول: "يمكنك استخدام أي من 10,000 نوع مختلف من التوابل في العالم"، أو "يمكنك اختيار أي من 50,000 أداة في ورشة عمل ضخمة". إن فحص قائمة من ثلاثة عناصر أمر سهل، لكن فحص قائمة من 50,000 عنصر في كل مرة يفكر فيها الكمبيوتر في كلمة جديدة يشبه محاولة العثور على إبرة محددة في كومة قش تزداد حجماً باستمرار. يغرق الكمبيوتر في عملية التحقق من القائمة لدرجة أنه يتوقف عن الطهي تماماً، أو يستغرق وقتاً طويلاً جداً لدرجة أن الطعام يبرد. هذه هي المشكلة التي يحاول الباحثون حلها: كيف نحافظ على سرعة ودقة الكمبيوتر حتى عندما تكون "القائمة المحظورة" هائلة.

المكتبة العظمى للكلمات المحظورة

في هذه الورقة البحثية، يقدم الباحثون أداة ذكية جديدة تسمى آلية التري (Trie Automaton). لفهم سبب كونها تغييراً جذرياً، دعونا نرى كيف كانت الطريقة القديمة تعمل. تخيل أن الكمبيوتر هو حارس أمن عند باب مكتبة ضخمة. في كل مرة يريد فيها الكمبيوتر قول كلمة، يتعين على الحارس الركض عبر ممر طويل، والتحقق من سجل ضخم ومغبر (قائمة الـ 10,000 كلمة الصالحة)، ليرى ما إذا كانت الكلمة مسموحة أم لا. إذا كانت القائمة ضخمة، سيقضي الحارس كل وقته في الركض ذهاباً وإياباً، وسيتعطل طابور الناس المنتظرين للدخول (أفكار الكمبيوتر). وهذا ما تسميه الورقة "جدار الكاردينالية" (cardinality wall) — وهي النقطة التي تصبح فيها القائمة كبيرة جداً بحيث ينهار النظام أو يتباطأ بشكل كبير.

أدرك الباحثون أن الطريقة القديمة كانت تعامل كل قائمة كمجموعة عشوائية من الكلمات. لكن في العالم الحقيقي، القوائم ليست عشوائية. فكر في قائمة بأسماء الأدوات: "aws.create_user"، "aws.delete_user"، "aws.list_user". جميعها تبدأ بـ "aws."، ثم تليها "create" أو "delete" أو "list". إنها تشترك في الكثير من الأجزاء الأولى، مثل الفروع في الشجرة. الحارس القديم لم يلاحظ ذلك؛ فقد كان يتحقق من كل كلمة من البداية في كل مرة.

أما آلية التري (Trie Automaton) الجديدة فهي تشبه أميناً ذكياً للمكتبة يبني خريطة خاصة للمكتبة. بدلاً من الممر الطويل، يبني الأمين مساراً على شكل شجرة:

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

النتائج: من حلزون إلى صاروخ

اختبر الباحثون هذا النظام الجديد مقابل أفضل الطرق الحالية (مثل XGrammar) باستخدام قوائم من الكلمات الصالحة تتراوح من 10 إلى 10,000 عنصر. وكانت النتائج دراماتيكية.

سرعة التجميع (Compilation Speed): عند بناء الخريطة لقائمة تضم 1,000 عنصر، استغرق النظام القديم حوالي 75 مللي ثانية (انتظار بسيط). أما آلية التري الجديدة فقد فعلت ذلك في حوالي 33 مللي ثانية. ولكن عندما نمت القائمة إلى 10,000 عنصر، استغرق النظام القديم ما يقرب من 240 مللي ثانية، بينما ظلت الآلية الجديدة مستقرة تقريباً عند 40 مللي ثانية. كان الأمر كما لو أن النظام القديم يركض في الوحل، بينما يركض النظام الجديد على جهاز جري لا تزداد صعوبته مهما زادت السرعة.
جدار الكاردينالية (The Cardinality Wall): بدأت الأنظمة القديمة في الفشل أو التباطؤ بشكل حاد عندما تجاوزت القائمة بضع مئات من العناصر. أما النظام الجديد فقد تعامل مع قوائم تضم 10,000 عنصر دون أدنى جهد، وأظهر الباحثون أنه يمكنه نظرياً التعامل مع ما يصل إلى 100,000 عنصر.
الخدمة المتزامنة (Batch Serving - الفوز الحقيقي): جاءت المفاجأة الكبرى عندما اختبروا النظام مع العديد من الطلبات في وقت واحد (مثل مطعم مزدحم بـ 256 طلباً). تمكن النظام القديم من معالجة حوالي 7.5 طلبات في الثانية فقط. أما آلية التري الجديدة فقد عالجت 219 طلباً في الثانية. هذا تحسن بمقدار 29 ضعفاً.

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

ماذا يعني هذا؟

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

لقد كان الباحثون حذرين للغاية في ملاحظة أن هذه الطريقة الجديدة لا تجعل الكمبيوتر أكثر ذكاءً أو تغير ما يقوله؛ بل تضمن فقط أنه يقول فقط ما يُفترض به قوله، وتفعل ذلك بسرعة فائقة. لقد قاموا بقياس ذلك على شرائح حاسوبية حقيقية ووجدوا أن الطريقة الجديدة دقيقة بنسبة 100% في اتباع القواعد، تماماً مثل الطريقة القديمة، لكنها تقوم بذلك أسرع بـ 7 مرات لكل كلمة يتم إنتاجها. وعندما تضرب هذه السرعة في مئات الطلبات التي تحدث في وقت واحد، يصبح الفرق هائلاً.

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

ملخص تقني: أتمتة الـ Trie لفك التشفير المقيد عبر مجموعات منتهية ضخمة

1. بيان المشكلة: جدار الكثافة العددية (The Cardinality Wall)

تتطلب النماذج اللغوية الكبيرة (LLMs) بشكل متزايد مخرجات مهيكلة تتوافق مع مخططات محددة مسبقاً، لا سيما اختيار سلسلة نصية من مجموعة منتهية معروفة (مثل أسماء الأدوات، أو الأكواد الطبية، أو تصنيفات المنتجات). تتعامل أنظمة فك التشفير المقيد الحالية، مثل XGrammar وOutlines، مع هذه القيود عن طريق تجميع المخططات في أتمتات عامة الغرض (آلات الحالة المحدودة FSM، أو آلات الدفع لأسفل PDA، أو محركات Earley).

وعلى الرغم من فعالية هذا النهج للغات القواعد المعقدة، إلا أنه يخلق "جدار كثافة عددية" بالنسبة لقيود المجموعات المنتهية البسيطة. فمع نمو عدد السلاسل الصالحة ( $K$ ) لتصل إلى الآلاف، يصبح وقت التجميع وزمن انتقال فك التشفير لكل خطوة بطيئاً بشكل غير مبرر. وتفرض الجهات المزودة الحالية قيوداً صارمة (على سبيل المثال، OpenAI عند 1,000 عنصر تعداد، وGoogle Gemini عند حوالي 120) لأن مسار التجميع القياسي يتوسع بشكل سيء مع زيادة $K$ . تكمن المشكلة الجوهرية في وجود عدم توافق أساسي: حيث تُطبق محركات عامة الغرض على قيود بسيطة (اتحادات منتهية من السلاسل) تمتلك بنية يمكن استغلالها (بادئات مشتركة، عمق محدود، وكثافة عددية معروفة).

2. المنهجية: أتمتة الـ Trie

يقدم المؤلفون أتمتة الـ Trie (trie automaton)، وهي خلفية متخصصة لقيود المجموعات المنتهية تحل محل طبقة الـ FSM عامة الغرض. تعتمد هذه الطريقة على بنية مجموعة القيود لتحقيق تجميع دون خطي (sub-linear) وفك تشفير بمرونة زمنية ثابتة لكل خطوة.

الآليات الجوهرية

بناء الـ Trie على مستوى الحروف: بدلاً من استخدام الـ Tries على مستوى الرموز (Tokens) -والتي تفشل في مشاركة البادئات عبر حدود الرموز- أو الـ DFAs العامة، يقوم النظام ببناء Trie على مستوى الحروف مباشرة من مجموعة السلاسل الصالحة. يؤدي هذا إلى دمج البادئات المشتركة، مما يقلل عدد العقد من $O(K \cdot L_{max})$ إلى $O(N_{chars})$ ، حيث $N_{chars}$ هو إجمالي عدد الحروف.
محاذاة BPE-Trie عبر خوارزمية Aho-Corasick: يمثل التحدي المركزي هو محاذاة الـ Trie (على مستوى الحروف) مع مفردات ترميز الـ BPE الخاصة بالنموذج. قد يمتد رمز BPE واحد عبر عدة حواف في الـ Trie. يحل المؤلفون هذه المشكلة عن طريق اختزال المسألة إلى مطابقة السلاسل متعددة الأنماط. يقومون ببناء أتمتة Aho-Corasick من رموز المفردات ويقومون بمسح الـ Trie، مع حساب مسبق لمجموعة الرموز الصالحة (valid[n]) لكل عقدة $n$ في الـ Trie.
الأقنعة المحسوبة مسبقاً (Precomputed Masks): أثناء عملية التجميع، يقوم النظام بحساب valid[n] لجميع العقد. وعند وقت فك التشفير، يقتصر القناع على بحث مباشر بزمن قدره $O(1)$ : $A(s_t) = valid[s_t]$ . هذا يتجاوز الحاجة إلى مسح كامل المفردة أو محاكاة الانتقالات لكل رمز في كل خطوة.

مزايا التعقيد

التجميع (Compilation): تهيمن تكلفة بناء أتمتة AC على العملية، وهي $O((N_{chars} + V) \cdot \ell)$ ، حيث $V$ هو حجم المفردة و $\ell$ هو أقصى طول للرمز. ومن المهم أن هذا مستقل تقريباً عن $K$ بمجرد بناء أتمتة AC، مما يؤدي إلى أوقات تجميع شبه مسطحة (30–67 مللي ثانية) حتى عندما تكون $K=10,000$ .
زمن انتقال الخطوة الواحدة (Per-Step Decoding): تنخفض التكلفة من $O(V \cdot \ell)$ (مسح جميع الرموز) إلى $O(|valid[s_t]|)$ . وبما أن المجموعة الصالحة تتقلص أسياً مع عمق الـ Trie (عادةً 10–100 رمز بعد 3–4 حروف)، فإن التكلفة الفعلية تكون ثابتة ومنخفضة للغاية (0.65 ميكروثانية).
الخدمة عديمة الحالة (Stateless Serving): نظرًا لأن الأقنعة محسوبة مسبقاً، يمكن للـ Trie أن يعمل كـ LogitsProcessor عديم الحالة، متجاوزاً إدارة الحالة في مسار التشفير الموجه وأعباء الجدولة المطلوبة للنهج القائم على FSM.

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

أتمتة الـ Trie: خلفية متخصصة لفك التشفير المقيد تجمع بين الـ Tries على مستوى الحروف، ومطابقة الأنماط المتعددة Aho-Corasick، وأقنعة الرموز المحسوبة مسبقاً. تحقق $O(|valid[s_t]|)$ لكل خطوة، مما يجعل التكلفة ثابتة فعلياً مقابل تكلفة $O(V \cdot \ell)$ لنهج FSM العام.
حل مشكلة محاذاة BPE-Trie: يعالج البحث تحدياً لم يتم التطرق إليه سابقاً وهو محاذاة مسارات الـ Trie (على مستوى الحروف) مع رموز BPE. من خلال اختزال ذلك إلى مطابقة الأنماط المتعددة، تمكنوا من تحقيق تجميع بأقل من 100 مللي ثانية حتى لـ $K=10,000$ عبر عائلات مختلفة من الـ Tokenizers.
التوصيف التجريبي لجدار الكثافة العددية: يوضح المؤلفون أن مطابقة آليات الإنفاذ مع بنية القيود يتغلب على اختناقات التوسع. ويظهرون أن الأقنعة المحسوبة مسبقاً تمكن مسار خدمة عديم الحالة لا يمكن لنهج FSM استخدامه، مما يضاعف مكاسب السرعة الخوارزمية في الإنتاجية.

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

أُجريت التجارب على وحدات معالجة رسومية NVIDIA A100 باستخدام سبع عائلات من الـ Tokenizers (مفردات تتراوح بين 32K و262K) ونماذج تشمل Qwen3-8B، وMistral، وGemma3.

سرعة التجميع: تحقق أتمتة الـ Trie سرعة تجميع أسرع بـ 2 إلى 6.5 مرة من XGrammar عند $K \ge 300$ . وبينما يتوسع تجميع XGrammar خطياً مع $K$ (يصل إلى 2.7 ثانية عند $K=100,000$ )، يظل الـ Trie مسطحاً عند ~30–67 مللي ثانية.
زمن انتقال الخطوة الواحدة: تحسب الـ Trie أقنعة الرموز الصالحة في 0.65 ميكروثانية، مقارنة بـ 5.8 ميكروثانية لـ XGrammar (تحسن بمقدار 7 أضعاف) و73–141 ميكروثانية لـ LLGuidance (أبطأ بـ 110–215 ضعفاً).
الإنتاجية النهائية (End-to-End Throughput): في الخدمة بالدفعات (vLLM)، تتضاعف الميزة. عند حجم دفعة 256، تحقق الـ Trie نحو 219 طلباً في الثانية مقابل 7.5 طلب/ثانية لـ XGrammar (تحسن بمقدار 29 ضعفاً). تأتي هذه المكاسب من تسريع خوارزمي بمقدار 7 أضعاف بالإضافة إلى التخلص من أعباء مسار التشفير الموجه.
الصلاحية والدقة: تضمن الـ Trie صلاحية مخرجات بنسبة 100%. وفي اختبارات التصنيف (TREC, MASSIVE, Banking77, CLINC150)، تضاهي الـ Trie أو تتفوق على دقة فك التشفير غير المقيد مع القضاء على الهلوسة. بالنسبة للنماذج الأضعف، تعمل الـ Trie كممكن حاسم، حيث رفعت الدقة من 4.8% إلى 24.8% في Banking77 من خلال ضمان المخرجات الصالحة.
القابلية للتوسع: تحافظ الطريقة على تجميع أقل من 100 مللي ثانية وتكلفة خطوة ثابتة حتى $K=10,000$ وما فوق، مما يوسع فعلياً حد الـ enum العملي من ~1,000 إلى ~100,000.

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

يزعم البحث أن أتمتة الـ Trie تحل عدم الكفاءة الجوهري في فك التشفير المقيد: وهو تطبيق الأتمتات عامة الغرض على قيود بسيطة ومنظمة. ومن خلال استغلال البنية المحددة للمجموعات المنتهية (البادئات المشتركة)، يثبت المؤلفون أن:

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

يضع المؤلفون أتمتة الـ Trie ليس كتقريب، بل كبديل متماثل ودقيق لفك التشفير القائم على FSM للمجموعات المنتهية، مما يوفر صلاحية بنسبة 100% مع تحسينات في الأداء بعدة مراتب في سيناريوهات الكثافة العالية.