💻 computer science

Trie Automata for Constrained Decoding over Large Finite Sets

Cet article présente l'automate de trie, un mécanisme spécialisé qui exploite l'appariement multi-motifs d'Aho-Corasick pour précalculer des masques de jetons pour le décodage contraint par ensemble fini, atteignant un débit jusqu'à 29 fois supérieur et une compilation nettement plus rapide que les systèmes existants comme XGrammar tout en garantissant une validité de sortie de 100 %.

Auteurs originaux : Xingzi Xu, Karim Bouyarmane

Publié 2026-08-14

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Xingzi Xu, Karim Bouyarmane

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un monde où les ordinateurs sont comme des chefs incroyablement talentueux mais légèrement chaotiques. Ils peuvent écrire des histoires, résoudre des problèmes mathématiques et même coder des logiciels, mais ils ont la mauvaise habérie d'inventer des choses. Si vous leur demandez de lister les capitales du monde, ils pourraient inventer avec assurance une ville appelée « Narnia » ou mal orthographier « Paris ». Pour empêcher cela, les scientifiques utilisent une technique appelée décodage contraint. Considérez cela comme si l'on donnait un livre de recettes strict au chef. Au lieu de laisser le chef choisir n'importe quel ingrédient dans tout l'univers, le livre de recettes dit : « Vous ne pouvez utiliser que de la farine, du sucre ou des œufs. » L'ordinateur vérifie chaque mot qu'il veut écrire par rapport à cette liste pour s'assurer qu'il n'invente pas accidentellement un nouvel ingrédient.

Cela fonctionne très bien quand la liste est courte, comme une recette avec trois ingrédients. Mais que se passe-t-il si la liste est énorme ? Imaginez une recette qui dit : « Vous pouvez utiliser n'importe laquelle des 10 000 épices différentes du monde », ou « Vous pouvez choisir parmi les 50 000 outils d'un immense atelier ». Vérifier une liste de trois articles est facile. Vérifier une liste de 50 000 articles chaque fois que l'ordinateur pense à un nouveau mot, c'est comme essayer de trouver une aiguille spécifique dans une botte de foin qui ne cesse de s'agrandir. L'ordinateur s'enlise tellement dans la vérification de la liste qu'il finit par arrêter de cuisiner, ou cela prend tellement de temps que la nourriture refroidit. C'est le problème que les chercheurs tentent de résoudre : comment garder l'ordinateur rapide et précis même lorsque la « liste interdite » est massive.

La Grande Bibliothèque des Mots Interdits

Dans cet article, les chercheurs présentent un nouvel outil ingénieux appelé l'Automate de Trie. Pour comprendre pourquoi c'est un changement radical, regardons comment l'ancienne méthode fonctionnait. Imaginez que l'ordinateur est un garde de sécurité à la porte d'une immense bibliothèque. Chaque fois que l'ordinateur veut dire un mot, le garde doit parcourir un long couloir, consulter un immense registre poussiéreux (la liste des 10 000 mots valides) et voir si le mot est autorisé. Si la liste est énorme, le garde passe tout son temps à faire des allers-retours, et la file de personnes qui attendent à l'entrée (les pensées de l'ordinateur) reste bloquée. C'est ce que l'article appelle le « mur de la cardinalité » — un point où la liste devient si grande que le système plante ou ralentit considérablement.

Les chercheurs ont réalisé que l'ancienne méthode traitait chaque liste comme un mélange aléatoire de mots. Mais dans le monde réel, les listes ne sont pas aléatoires. Pensez à une liste de noms d'outils : « aws.create_user », « aws.delete_user », « aws.list_user ». Ils commencent tous par « aws. ». Ensuite, ils ont tous « create », « delete » ou « list ». Ils partagent beaucoup de parties communes au début, comme des branches sur un arbre. L'ancien garde de sécurité ne le remarquait pas ; il vérifiait chaque mot depuis le début à chaque fois.

Le nouvel Automate de Trie est comme un bibliothécaire super intelligent qui construit une carte spéciale de la bibliothèque. Au lieu d'un long couloir, le bibliothécaire construit un chemin en forme d'arbre.

La Carte : Ils dessinent un chemin pour « aws. ». Une fois que vous êtes sur le chemin « aws. », vous n'avez plus besoin de vérifier « aws. ». Vous regardez simplement le prochain embranchement : « create », « delete » ou « list ».
La Pré-vérification : Voici le tour de magie. Avant même que l'ordinateur ne commence à parler, le bibliothécaire pré-calcule exactement quels mots sont autorisés à chaque embranchement de l'arbre. Ils écrivent ces réponses sur des petits post-it et les collent directement sur les branches de l'arbre.
La Vitesse : Désormais, quand l'ordinateur veut parler, le bibliothécaire ne court pas vers le registre. Il regarde simplement le post-it sur la branche actuelle. « Oh, vous êtes sur la branche 'aws.' ? La note dit que vous ne pouvez dire que 'create', 'delete' ou 'list' ensuite. » Cela prend une fraction de seconde.

Les Résultats : D'un Escargot à une Fusée

Les chercheurs ont testé ce nouveau système par rapport aux meilleures méthodes actuelles (comme XGrammar) en utilisant des listes de mots valides allant de 10 à 10 000 éléments. Les résultats ont été spectaculaires.

Vitesse de Compilation : En construisant la carte pour une liste de 1 000 éléments, l'ancien système prenait environ 75 millisecondes (une petite attente). Le nouvel Automate de Trie l'a fait en environ 33 millisecondes. Mais lorsque la liste passait à 10 000 éléments, l'ancien système prenait près de 240 millisecondes, tandis que le nouveau restait presque plat à 40 millisecondes. C'était comme si l'ancien système courait dans la boue, tandis que le nouveau courait sur un tapis roulant qui ne devenait pas plus difficile quelle que soit sa vitesse.
Le « Mur de la Cardinalité » : Les anciens systèmes commençant à échouer ou à ralentir drastiquement lorsque la liste dépassait quelques centaines d'éléments. Le nouveau système a géré des listes de 10 000 éléments sans sourciller, et les chercheurs ont montré qu'il pourrait théoriquement en gérer jusqu'à 100 000.
Le Service par Lot (La vraie victoire) : La plus grande surprise est survenue lorsqu'ils ont testé le système avec de nombreuses requêtes simultanées (comme un restaurant très fréquenté avec 256 commandes). L'ancien système ne pouvait traiter qu'environ 7,5 commandes par seconde. Le nouvel Automate de Trie a traité 219 commandes par seconde. C'est une amélioration de 29 fois.

Pourquoi était-ce si beaucoup plus rapide ? Ce n'était pas seulement la carte ; c'était la façon dont la carte était utilisée. Parce que les réponses étaient pré-écrites sur des post-it, l'ordinateur n'avait pas besoin de faire de réflexions ou de vérifications complexes pendant qu'il parlait. Il pouvait simplement saisir la note et continuer. Cela a permis à l'ordinateur de sauter un grand nombre d'étapes lentes et compliquées que l'ancien système devait effectuer à chaque fois.

Ce que cela signifie

L'article prouve que pour des types spécifiques de listes — comme choisir un outil dans un registre, sélectionner un code médical ou choisir une catégorie de produit — l'ancienne méthode de « tout vérifier » est trop lente. En utilisant la structure des mots (les débuts partagés) et en pré-calculant les réponses, la nouvelle méthode rend le décodage contraint à nouveau rapide et fiable.

Les chercheurs ont été très attentifs à noter que cette nouvelle méthode ne rend pas l'ordinateur plus intelligent ni ne change ce qu'il dit ; elle s'assure simplement qu'il dit uniquement ce qu'il est censé dire, et elle le fait incroyablement vite. Ils ont mesuré cela sur de vraies puces informatiques et ont constaté que la nouvelle méthode est 100 % précise pour suivre les règles, tout comme l'ancienne méthode, mais qu'elle est 7 fois plus rapide pour chaque mot généré. Quand on multiplie cette vitesse par des centaines de requêtes se produisant simultanément, la différence est massive.

En bref, l'article a trouvé un moyen de transformer une recherche chaotique et lente dans une immense botte de foin en une marche rapide et organisée sur un chemin pré-éclairé. Il résout le problème du « mur de la cardinalité », permettant à l'IA de gérer des listes massives d'options sans rester bloquée, ce qui est crucial pour l'avenir des agents d'IA qui doivent choisir parmi des milliers d'outils ou de services instantanément.

Résumé technique : Automates de Trie pour le décodage contraint sur de grands ensembles finis

1. Énoncé du problème : Le mur de la cardinalité

Les modèles de langage de grande taille (LLM) nécessitent de plus en plus de sorties structurées conformes à des schémas prédéfinis, particulièrement pour la sélection d'une chaîne au sein d'un ensemble fini connu (ex: noms d'outils, codes médicaux, taxonomies de produits). Les systèmes actuels de décodage contraint, tels que XGrammar et Outlines, gèrent ces contraintes en compilant les schémas en automates à usage général (automates à états finis, automates à pile ou parseurs Earley).

Bien qu'efficace pour les grammaires complexes, cette approche à usage général crée un « mur de la cardinalité » pour les contraintes d'ensembles finis simples. À mesure que le nombre de chaînes valides ( $K$ ) croît pour atteindre des milliers, le temps de compilation et la latence de décodage par étape deviennent prohibitifs. Les fournisseurs existants imposent des limites strictes (ex: OpenAI à 1 000 énumérations, Google Gemini à environ 120) car le pipeline de compilation standard s'adapte mal à l'augmentation de $K$ . Le problème fondamental est une inadéquation structurelle : des moteurs complexes à usage général sont appliqués à des contraintes simples (unions finies de chaînes) qui possèdent une structure exploitable (préfixes partagés, profondeur bornée, cardinalité connue).

2. Méthodologie : L'automate de Trie

Les auteurs introduisent l'automate de trie, un backend spécialisé pour les contraintes d'ensembles finis qui remplace la couche FSM à usage général. La méthode tire parti de la structure de l'ensemble de contraintes pour atteindre une compilation sous-linéaire et un masquage par étape en temps constant.

Mécanismes fondamentaux

Construction de Trie au niveau des caractères : Au lieu de tries au niveau des tokens (qui échouent à partager des préfixes à travers les frontières de tokens) ou de DFA généraux, le système construit un trie de caractères directement à partir de l'ensemble des chaînes valides. Cela fusionne les préfixes partagés, réduisant le nombre de nœuds de $O(K \cdot L_{max})$ à $O(N_{chars})$ , où $N_{chars}$ est le nombre total de caractères.
Alignement BPE-Trie via Aho-Corasick : Un défi central est l'alignement du trie de caractères avec le vocabulaire BPE (Byte-Pair Encoding) du modèle. Un seul token BPE peut s'étendre sur plusieurs arêtes du trie. Les auteurs résolvent cela en réduisant le problème à la recherche de chaînes multi-motifs. Ils construisent un automate Aho-Corasick (AC) à partir des tokens du vocabulaire et parcourent le trie, précalculant l'ensemble des tokens BPE valides (valid[n]) pour chaque nœud $n$ du trie.
Masques précalculés : Lors de la compilation, le système calcule valid[n] pour tous les nœuds. Au moment du décodage, le masquage se réduit à une recherche directe en $O(1)$ : $A(s_t) = valid[s_t]$ . Cela évite de scanner l'ensemble du vocabulaire ou de simuler des transitions pour chaque token à chaque étape.

Avantages de complexité

Compilation : Le coût est dominé par la construction de l'automate AC sur le vocabulaire, qui est de $O((N_{chars} + V) \cdot \ell)$ , où $V$ est la taille du vocabulaire et $\ell$ la longueur maximale d'un token. Crucialement, cela est largement indépendant de $K$ une fois l'automate AC construit, menant à des temps de compilation quasi-plats (30–67 ms) même pour $K=10\,000$ .
Latence par étape : Le coût chute de $O(V \cdot \ell)$ (scan de tous les tokens) à $O(|valid[s_t]|)$ . Comme l'ensemble valide rétrécit exponentiellement avec la profondeur du trie (typiquement 10–100 tokens après 3–4 caractères), le coût effectif est constant et extrêmement bas (0,65 µs).
Service sans état (Stateless Serving) : Parce que les masques sont précalculés, le trie peut fonctionner comme un LogitsProcessor sans état, contournant la gestion d'état du pipeline de décodage guidé et les surcharges de planification requises par les approches basées sur les FSM.

3. Contributions clés

L'automate de Trie : Un backend de décodage contraint spécialisé qui combine des tries de caractères, la correspondance de motifs multiples Aho-Corasick et des masques de tokens précalculés. Il atteint un masquage par étape de $O(|valid[s_t]|)$ , soit un coût constant par rapport au coût $O(V \cdot \ell)$ des approches FSM générales.
Résolution du problème d'alignement BPE-Trie : L'article traite du défi, jusqu'alors non résolu, de l'alignement des chemins du trie de caractères avec les tokens BPE. En réduisant cela à la recherche de motifs multiples, ils permettent une compilation en moins de 100 ms jusqu'à $K=10\,000$ sur diverses familles de tokeniseurs.
Caractérisation empirique du mur de la cardinalité : Les auteurs démontrent que l'adéquation des mécanismes d'application aux structures de contraintes permet de surmonter les goulots d'étranglement de mise à l'échelle. Ils montrent que les masques précalculés permettent un chemin de service sans état que les approches FSM ne peuvent utiliser, amplifiant les gains algorithmiques en gains massifs de débit.

4. Résultats expérimentaux

Les expériences ont été menées sur des GPU NVIDIA A100 utilisant sept familles de tokeniseurs (vocabulaire de 32K à 262K) et des modèles incluant Qwen3-8B, Mistral et Gemma3.

Vitesse de compilation : L'automate de trie est 2 à 6,5 fois plus rapide pour la compilation que XGrammar pour $K \ge 300$ . Alors que la compilation de XGrammar suit une progression linéaire avec $K$ (atteignant 2,7 s pour $K=100\,000$ ), le trie reste plat autour de 30–67 ms.
Latence par étape : Le trie calcule les masques de tokens valides en 0,65 µs, contre 5,8 µs pour XGrammar (une accélération de 7×) et 73–141 µs pour LLGuidance (110–215× plus lent).
Débit de bout en bout : Dans le cadre du service par lots (batch serving) avec vLLM, l'avantage se cumule. À une taille de lot de 256, le trie atteint 219 req/s contre 7,5 req/s pour XGrammar (amélioration de 29×). Ce gain provient de l'accélération algorithmique de 7× combinée à l'élimination de la surcharge du pipeline de décodage guidé.
Validité et précision : Le trie garantit une validité de sortie de 100 %. Dans les benchmarks de classification (TREC, MASSIVE, Banking77, CLINC150), le décodage contraint avec le trie égale ou dépasse la précision non contrainte tout en éliminant les hallucinations. Pour les modèles plus faibles, le trie agit comme un catalyseur critique, améliorant la précision de 4,8 % à 24,8 % sur Banking77 en garantissant des sorties valides.
Scalabilité : La méthode maintient une compilation inférieure à 100 ms et des coûts par étape plats jusqu'à $K=10\,000$ et au-delà, étendant ainsi efficacement la limite pratique des énumérations de ~1 000 à ~100 000.

5. Signification et affirmations

L'article affirme que l'automate de trie résout une inefficacité fondamentale du décodage contraint : l'application d'automates à usage général à des contraintes simples et structurées. En exploitant la structure spécifique des ensembles finis (préfixes partagés), les auteurs démontrent que :

Efficacité algorithmique : Le trie est l'algorithme efficace pour le précalcul des masques par état sur les ensembles finis, surpassant le précalcul équivalent par FSM de 196× en temps de compilation.
Impact systémique : La capacité de précalculer les masques permet un chemin de service sans état qui contourne le pipeline de décodage guidé, un avantage que seuls les masques précalculés rendent possible. Cela transforme le décodage contraint d'un goulot d'étranglement en un overhead négligeable dans le service par lots.
Généralisabilité : Le principe consistant à faire correspondre les mécanismes d'application aux structures de contraintes (par exemple, utiliser des masques de position de caractères pour des formats fixes) produit des accélérations massives pour toute contrainte possédant une régularité exploitable, pas seulement pour les ensembles finis.

Les auteurs positionnent l'automate de trie non pas comme une approximation, mais comme une alternative exacte et isomorphe au décodage par FSM pour les ensembles finis, offrant une validité de 100 % avec des améliorations de performance de plusieurs ordres de grandeur dans les scénarios à haute cardinalité.