💻 computer science

Trie Automata for Constrained Decoding over Large Finite Sets

Dieses Paper führt den Trie-Automaten ein, einen spezialisierten Mechanismus, der Aho-Corasick-Multi-Pattern-Matching nutzt, um Token-Masken für die dekodierung mit endlichen Mengen-Beschränkungen vorzuberechnen, wodurch im Vergleich zu bestehenden Systemen wie XGrammar ein bis zu 29-fach höherer Durchsatz und eine signifikant schnellere Kompilierung erreicht werden, während gleichzeitig eine 100%ige Ausgabegültigkeit garantiert wird.

Ursprüngliche Autoren: Xingzi Xu, Karim Bouyarmane

Veröffentlicht 2026-08-14

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Xingzi Xu, Karim Bouyarmane

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine Welt vor, in der Computer wie unglaublich talentierte, aber etwas chaotische Köche sind. Sie können Geschichten schreiben, mathematische Probleme lösen und Software programmieren, aber sie haben die schlechte Angewohnheit, Dinge zu erfinden. Wenn man sie bittet, die Hauptstadtstädte der Welt aufzulisten, könnten sie selbstbewusst eine Stadt namens „Narnia“ erfinden oder die Schreibweise von „Paris“ vertauschen. Um dies zu verhindern, nutzen Wissenschaftler eine Technik namens Constrained Decoding (eingeschränkte Dekodierung). Stellen Sie sich das wie ein strenges Rezeptbuch für den Koch vor. Anstatt dem Koch zu erlauben, beliebige Zutaten aus dem gesamten Universum zu wählen, sagt das Rezeptbuch: „Du darfst nur Mehl, Zucker oder Eier verwenden.“ Der Computer prüft jedes Wort, das er schreiben möchte, gegen diese Liste, um sicherzustellen, dass er nicht versehentlich eine neue Zutat erfindet.

Das funktioniert großartig, wenn die Liste kurz ist, wie bei einem Rezept mit drei Zutaten. Aber was, wenn die Liste riesig ist? Stellen Sie sich ein Rezept vor, das besagt: „Du kannst jede der 10.000 verschiedenen Gewürze der Welt verwenden“, oder: „Du kannst jedes der 50.000 Werkzeuge in einer riesigen Werkstatt auswählen.“ Das Prüfen einer Liste mit drei Artikeln ist einfach. Das Prüfen einer Liste mit 50.000 Artikeln jedes Mal, wenn der Computer an ein neues Wort denkt, ist wie der Versuch, eine bestimmte Nadel in einem Heuhaufen zu finden, der immer größer wird. Der Computer ist dann so sehr mit dem Prüfen der Liste beschäftigt, dass er das Kochen ganz einstellt, oder es dauert so lange, dass das Essen kalt wird. Dies ist das Problem, das Forscher zu lösen versuchen: Wie man den Computer schnell und präzise hält, selbst wenn die „verbotene Liste“ massiv ist.

Die Große Bibliothek der verbotenen Wörter

In dieser Arbeit stellen die Forscher ein cleveres neues Werkzeug namens Trie-Automaton vor. Um zu verstehen, warum es ein Wendepunkt ist, schauen wir uns an, wie die alte Methode funktionierte. Stellen Sie sich vor, der Computer ist ein Sicherheitswachmann am Eingang einer riesigen Bibliothek. Jedes Mal, wenn der Computer ein Wort sagen möchte, muss der Wachmann einen langen Flur entlanglaufen, ein riesiges, staubiges Register (die Liste der 10.000 gültigen Wörter) prüfen und nachsehen, ob das Wort erlaubt ist. Wenn die Liste riesig ist, verbringt der Wachmann seine gesamte Zeit mit dem Hin- und Herlaufen, und die Schlange der Menschen, die eintreten wollen (die Gedanken des Computers), bleibt stecken. Dies ist das, was das Papier die „Kardinalitätswand“ nennt – ein Punkt, an dem die Liste so groß wird, dass das System abstürzt oder extrem langsam wird.

Die Forscher erkannten, dass die alte Methode jede Liste wie ein zufälliges Durcheinander von Wörtern behandelte. Aber in der realen Welt sind Listen nicht zufällig. Denken Sie an eine Liste von Werkzeugnamen: „aws.create_user“, „aws.delete_user“, „aws.list_user“. Sie beginnen alle mit „aws.“. Dann haben sie alle „create“, „delete“ oder „list“. Sie teilen sich viele der gleichen Anfangsteile, wie Zweige an einem Baum. Der alte Sicherheitswachmann bemerkte dies nicht; er prüfte jedes Wort jedes Mal von Grund auf neu.

Der neue Trie-Automaton ist wie ein superintelligenter Bibliothekar, der eine spezielle Karte der Bibliothek erstellt. Anstatt eines langen Flurs baut der Bibliothekar einen baumartigen Pfad.

Die Karte: Er zeichnet einen Pfad für „aws.“. Sob es einmal auf dem „aws.“-Pfad ist, muss man „aws.“ nicht noch einmal prüfen. Man schaut einfach auf die nächste Weggabelung: „create“, „delete“ oder „list“.
Die Vorprüfung: Hier liegt der magische Trick. Bevor der Computer überhaupt anfängt zu sprechen, berechnet der Bibliothekar im Voraus exakt, welche Wörter an jeder einzelnen Weggabelung im Baum erlaubt sind. Er schreibt diese Antworten auf kleine Klebezettel und klebt sie direkt auf die Zweige des Baumes.
Die Geschwindigkeit: Wenn der Computer nun sprechen möchte, rennt der Bibliothekar nicht zum Register. Er schaut einfach auf den Klebezettel am aktuellen Zweig. „Oh, du bist am ‚aws‘-Zweig? Der Zettel sagt, dass du als Nächstes nur ‚create‘, ‚delete‘ oder ‚list‘ sagen darfst.“ Das dauert nur einen Bruchteil einer Sekunde.

Die Ergebnisse: Von einer Schnecke zu einer Rakete

Die Forscher testeten dieses neue System gegen die derzeit besten Methoden (wie XGrammar) mit Listen gültiger Wörter, die von 10 bis 10.000 Artikeln reichten. Die Ergebnisse waren dramatisch.

Kompilierungsgeschwindigkeit: Beim Erstellen der Karte für eine Liste mit 1.000 Artikeln dauerte das alte System etwa 75 Millisekunden (ein wenig Warten). Der neue Trie-Automaton erledigte dies in etwa 33 Millisekunden. Aber als die Liste auf 10.000 Artikel anwuchs, dauerte das alte System fast 240 Millisekunden, während das neue System fast flach bei 40 Millisekunden blieb. Es war, als würde das alte System durch Schlamm laufen, während das neue auf einem Laufband lief, das nicht schwerer wurde, egal wie schnell man war.
Die „Kardinalitätswand“: Die alten Systeme begannen zu versagen oder drastisch langsamer zu werden, wenn die Liste ein paar hundert Artikel überschritt. Das neue System bewältigte Listen von 10.000 Artikeln ohne Mühe, und die Forscher zeigten, dass es theoretisch bis zu 100.000 Artikel bewältigen kann.
Batch Serving (Der wahre Gewinn): Die größte Überraschung kam, als sie das System mit vielen Anfragen gleichzeitig testeten (wie in einem belebten Restaurant mit 256 Bestellungen). Das alte System konnte nur etwa 7,5 Bestellungen pro Sekunde bearbeiten. Der neue Trie-Automaton bewältigte 219 Bestellungen pro Sekunde. Das ist eine Verbesserung um den Faktor 29.

Warum war es so viel schneller? Es war nicht nur die Karte; es war die Art und Weise, wie die Karte genutzt wurde. Da die Antworten vorab aufgeschrieben waren, musste der Computer während des Sprechens keine komplexen Denk- oder Prüfprozesse durchführen. Er konnte einfach den Zettel greifen und weitermachen. Dies ermöglichte es dem Computer, eine ganze Reihe langsamer, komplizierter Schritte zu überspringen, die das alte System jedes Mal durchführen musste.

Was das bedeutet

Das Papier beweist, dass für spezifische Arten von Listen – wie die Auswahl eines Werkzeugs aus einem Register, die Auswahl eines medizinischen Codes oder die Auswahl einer Produktkategorie – die alte „Prüfe alles“-Methode zu langsam ist. Durch die Nutzung der Struktur der Wörter (die gemeinsamen Anfänge) und die Vorausberechnung der Antworten macht die neue Methode das Constrained Decoding wieder schnell und zuverlässig.

Die Forscher stellten sehr sorgfältig fest, dass diese neue Methode den Computer nicht intelligenter macht oder dessen Inhalt verändert; sie stellt lediglich sicher, dass er nur das sagt, was er soll, und das tut sie unglaublich schnell. Sie maßen dies auf echten Computerchips und fanden heraus, dass die neue Methode zu 100 % genau bei der Einhaltung der Regeln ist, genau wie die alte Methode, aber sie erledigt dies 7-mal schneller für jedes einzelne generierte Wort. Wenn man diese Geschwindigkeit mit Hunderten von gleichzeitigen Anfragen multipliziert, ist der Unterschied gewaltig.

Kurz gesagt: Die Forscher haben einen Weg gefunden, eine chaotische, langsame Suche in einem riesigen Heuhaufen in einen schnellen, organisierten Spaziergang auf einem vorbelichteten Pfad zu verwandeln. Es löst das Problem der „Kardinalitätswand“ und ermöglicht es der KI, massive Listen von Optionen zu handhaben, ohne stecken zu bleiben, was entscheidend für die Zukunft von KI-Agenten ist, die tausende von Werkzeugen oder Diensten sofort auswählen müssen.

Technisches Resümee: Trie-Automaten für die eingeschränkte Dekodierung über große endliche Mengen

1. Problemstellung: Die Kardinalitätswand

Große Sprachmodelle (LLMs) erfordern zunehmend strukturierte Ausgaben, die vordefinierten Schemata entsprechen, insbesondere bei der Auswahl eines Strings aus einer bekannten endlichen Menge (z. B. Tool-Namen, medizinische Codes, Produkt-Taxonomien). Aktuelle Systeme zur eingeschränkten Dekodierung, wie XGrammar und Outlines, handhaben diese Einschränkungen durch die Kompilierung von Schemata in allgemeine Automaten (endliche Zustandsautomaten, Kellerautomaten oder Earley-Parser).

Obwohl dieser Ansatz für komplexe Grammatiken effektiv ist, erzeugt er eine „Kardinalitätswand“ für einfache endliche Mengen-Einschränkungen. Wenn die Anzahl der gültigen Strings ( $K$ ) in die Tausende steigt, werden die Kompilierungszeit und die Latenz pro Dekodierungsschritt prohibitiv langsam. Bestehende Anbieter legen strikte Limits fest (z. B. OpenAI bei 1.000 Enums, Google Gemini bei ca. 120), da die standardmäßige Kompilierungspipeline schlecht mit $K$ skaliert. Das Kernproblem ist ein grundlegender Mismatch: Komplexe, allgemeine Engines werden auf einfache Einschränkungen (endliche Vereinigungen von Strings) angewendet, die eine ausnutzbare Struktur besitzen (gemeinsame Präfixe, begrenzte Tiefe, bekannte Kardinalität).

2. Methodik: Der Trie-Automat

Die Autoren führen den Trie-Automaten ein, einen spezialisierten Backend für endliche Mengen-Einschränkungen, der die allgemeine FSM-Schicht ersetzt. Die Methode nutzt die Struktur des Einschränkungssets aus, um eine sublineare Kompilierung und eine konstante Zeit pro Dekodierungsschritt zu erreichen.

Kernmechanismen

Zeichenbasierte Trie-Konstruktion: Anstatt Token-basierte Tries zu verwenden (die keine Präfixe über Token-Grenzen hinweg teilen) oder allgemeine DFAs, baut das System einen zeichenbasierten Trie direkt aus der Menge der gültigen Strings auf. Dies führt gemeinsame Präfixe zusammen und reduziert die Anzahl der Knoten von $O(K \cdot L_{max})$ auf $O(N_{chars})$ , wobei $N_{chars}$ die gesamte Zeichenanzahl ist.
BPE-Trie-Ausrichtung via Aho-Corasick: Eine zentrale Herausforderung besteht darin, den zeichenbasierten Trie mit dem Byte-Pair-Encoding (BPE) Vokabular des Modells abzugleichen. Ein einzelnes BPE-Token kann mehrere Trie-Kanten überspannen. Die Autoren lösen dies, indem sie das Problem auf Multi-Pattern-String-Matching reduzieren. Sie bauen einen Aho-Corasick (AC) Automaten aus den Vokabular-Tokens auf und traversieren den Trie, wobei sie die Menge der gültigen BPE-Tokens (valid[n]) für jeden Trie-Knoten $n$ vorberechnen.
Vorberechnete Masken: Während der Kompilierung berechnet das System valid[n] für alle Knoten. Zur Dekodierungszeit reduziert sich das Masking auf einen direkten $O(1)$ Lookup: $A(s_t) = valid[s_t]$ . Dies umgeht das Scannen des gesamten Vokabulars oder das Simulieren von Übergängen für jedes Token bei jedem Schritt.

Komplexitätsvorteile

Kompilierung: Die Kosten werden durch die Konstruktion des AC-Automaten über das Vokabular dominiert, was $O((N_{chars} + V) \cdot \ell)$ entspricht, wobei $V$ die Vokabulargröße und $\ell$ die maximale Token-Länge ist. Entscheidend ist, dass dies weitgehend unabhängig von $K$ ist, sobald der AC-Automat gebaut wurde, was zu nahezu flachen Kompilierungszeiten (30–67 ms) führt, selbst bei $K=10.000$ .
Per-Step-Dekodierung: Die Kosten sinken von $O(V \cdot \ell)$ (Scannen aller Tokens) auf $O(|valid[s_t]|)$ . Da sich die Menge der gültigen Tokens mit der Trie-Tiefe exponentiell verkleinert (typischerweise 10–100 Tokens nach 3–4 Zeichen), sind die effektiven Kosten konstant und extrem niedrig (0,65 µs).
Stateless Serving: Da Masken vorberechnet sind, kann der Trie als zustandsloser LogitsProcessor operieren, wodurch die Verwaltung des Zustands und der Scheduling-Overhead der geführten Dekodierungspipeline umgangen wird.

3. Wichtigste Beiträge

Der Trie-Automat: Ein spezialisierter Backend für die eingeschränkte Dekodierung, der zeichenbasierte Tries, Aho-Corasick Multi-Pattern-Matching und vorberechnete Token-Masken kombiniert. Er erreicht eine $O(|valid[s_t]|)$ pro-Schritt-Maskierung, was im Vergleich zu den $O(V \cdot \ell)$ Kosten allgemeiner FSM-Ansätze eine konstante Kostenstruktur bedeutet.
Lösung des BPE-Trie-Ausrichtungsproblems: Die Arbeit adressiert die bisher ungelöste Herausforderung, zeichenbasierte Trie-Pfade mit BPE-Tokens abzugleichen. Durch die Reduktion auf Multi-Pattern-Matching ermöglichen sie eine Sub-100ms-Kompilierung bis zu $K=10.000$ über verschiedene Tokenizer-Familien hinweg.
Empirische Charakterisierung der Kardinalitätswand: Die Autoren zeigen, dass die Anpassung der Durchsetzungsmechanismen an die Struktur der Einschränkung die Skalierungsengpässe überwindet. Sie zeigen, dass vorberechnete Masken einen zustandslosen Serving-Pfad ermöglichen, den FSM-basierte Ansätze nicht nutzen können, was die algorithmischen Geschwindigkeitsgewinne in massive Durchsatzsteigerungen verwandelt.

4. Experimentelle Ergebnisse

Die Experimente wurden auf NVIDIA A100 GPUs mit sieben Tokenizer-Familien (32K–262K Vokabular) und Modellen wie Qwen3-8B, Mistral und Gemma3 durchgeführt.

Kompilierungsgeschwindigkeit: Der Trie-Automat erreicht eine 2–6,5-mal schnellere Kompilierung als XGrammar bei $K \ge 300$ . Während die XGrammar-Kompilierung linear mit $K$ skaliert (2,7 s bei $K=100.000$ ), bleibt der Trie flach bei ~30–67 ms.
Per-Step-Latenz: Der Trie berechnet gültige Token-Masken in 0,65 µs, verglichen mit 5,8 µs für XGrammar (ein 7-facher Geschwindigkeitsvorteil) und 73–141 µs für LLGuidance (110–215× langsamer).
End-to-End Durchsatz: In der Batch-Serving-Umgebung (vLLM) potenziert sich der Vorteil. Bei einer Batch-Größe von 256 erreicht der Trie 219 req/s gegenüber 7,5 req/s von XGrammer (29-fache Verbesserung). Dieser Gewinn resultiert aus dem 7-fachen algorithmischen Geschwindigkeitsvorteil plus der Eliminierung des Overheads der geführten Dekodierungspipeline.
Validität und Genauigkeit: Der Trie garantiert 100 % Output-Validität. In Klassifizierungs-Benchmarks (TREC, MASSIVE, Banking77, CLINC150) erreicht die eingeschränkte Dekodierung mit dem Trie eine Genauigkeit, die der unbeschränkten entspricht oder diese übertrifft, während Halluzinationen eliminiert werden. Für schwächere Modelle fungiert der Trie als kritischer Enabler und verbessert die Genauigkeit auf Banking77 von 4,8 % auf 24,8 %, indem er gültige Ausgaben sicherstellt.
Skalierbarkeit: Die Methode hält eine Sub-100ms-Kompilierung und flache Per-Step-Kosten bis zu $K=10.000$ und darüber hinaus auf, was das praktische Enum-Limit effektiv von ~1.000 auf ~100.000 erweitert.

5. Bedeutung und Ansprüche

Das Paper behauptet, dass der Trie-Automat eine fundamentale Ineffizienz in der eingeschränkten Dekodierung löst: die Anwendung allgemeiner Automaten auf einfache, strukturierte Einschränkungen. Durch die Nutzung der spezifischen Struktur endlicher Mengen (gemeinsame Präfixe) demonstrieren die Autoren, dass:

Algorithmische Effizienz: Der Trie ist der effiziente Algorithmus zur Vorberechnung von Per-State-Masken über endliche Mengen, wobei er die äquivalente FSM-basierte Vorberechnung in der Kompilierungszeit um das 196-fache übertrifft.
Systemische Auswirkungen: Die Fähigkeit, Masken vorzuberechnen, ermöglicht einen zustandslosen Serving-Pfad, der die geführte Dekodierungspipeline umgeht – ein Vorteil, der nur durch vorberechnete Masken möglich ist. Dies transformiert die eingeschränkte Dekodierung von einem Flaschenhals in einen vernachlässigbaren Overhead im Batch-Serving.
Generalisierbarkeit: Das Prinzip, Durchsetzungsmechanismen an die Struktur der Einschränkung anzupassen (z. B. die Verwendung von Zeichen-Positions-Masken für feste Formate), liefert große Geschwindigkeitsgewinne für jede Einschränkung mit ausnutzbarer Regularität, nicht nur für endliche Mengen.

Die Autoren positionieren den Trie-Automaten nicht als Approximation, sondern als exakte, isomorphe Alternative zur FSM-basierten Dekodierung für endliche Mengen, die 100 % Validität mit Größenordnungen besserer Performance in Szenarien mit hoher Kardinalität bietet.