💻 computer science

Trie Automata for Constrained Decoding over Large Finite Sets

Dit artikel introduceert de trie-automaat, een gespecialiseerd mechanisme dat Aho-Corasick multi-pattern matching gebruikt om tokenmaskers vooraf te berekenen voor decoding met beperkingen van eindige verzamelingen, waarmee een tot 29x hogere doorvoer en aanzienlijk snellere compilatie wordt bereikt vergeleken met bestaande systemen zoals XGrammar, terwijl een 100% geldigheid van de output wordt gegarandeerd.

Oorspronkelijke auteurs: Xingzi Xu, Karim Bouyarmane

Gepubliceerd 2026-08-14

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Xingzi Xu, Karim Bouyarmane

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een wereld voor waarin computers lijken op ongelooflijk talentvolle maar licht chaotische chefs. Ze kunnen verhalen schrijven, wiskundige problemen oplossen en zelfs software coderen, maar ze hebben de slechte gewoonte om dingen te verzinnen. Als je hen vraagt om de hoofdsteden van de wereld op te sommen, kunnen ze vol vertrouwen een stad genaamd "Narnia" verzinnen of de spelling van "Parijs" verkeerd schrijven. Om dit te stoppen, gebruiken wetenschappers een techniek genaamd constrained decoding (beperkte decodering). Denk aan het geven van een strikt receptboek aan de chef. In plaats van de chef elke ingrediënt uit het hele universum te laten kiezen, zegt het receptboek: "Je mag alleen bloem, suiker of eieren gebruiken." De computer controleert elk woord dat hij wil schrijven tegen deze lijst om er zeker van te zijn dat hij niet per ongeluk een nieuw ingrediënt verzint.

Dit werkt geweldig wanneer de lijst kort is, zoals een recept met drie ingrediënten. Maar wat als de lijst enorm groot is? Stel je een recept voor dat zegt: "Je kunt elke van de 10.000 verschillende kruiden in de wereld gebruiken," of "Je kunt elke van de 50.000 gereedschappen in een enorme werkplaats kiezen." Het controleren van een lijst met drie items is eenvoudig. Het controleren van een lijst met 50.000 items bij elke nieuwe stap die de computer zet, is alsof je probeert een specifieke naald in een hooiberg te vinden die steeds groter wordt. De computer raakt zo erg afgeleid door het controleren van de lijst dat hij helemaal stopt met koken, of het duurt zo lang dat het eten koud wordt. Dit is het probleem dat onderzoekers proberen op te lossen: hoe houd je de computer snel en nauwkeurig, zelfs wanneer de "verboden lijst" enorm groot is.

De Grote Bibliotheek van Verboden Woorden

In dit artikel introduceren de onderzoekers een slim nieuw hulpmiddel genaamd de Trie Automaton. Om te begrijpen waarom dit een gamechanger is, laten we kijken naar hoe de oude methode werkte. Stel je voor dat de computer een beveiligingsbeambte is bij de deur van een enorme bibliotheek. Elke keer dat de computer een woord wil zeggen, moet de bewaker een lange gang afrennen, een gigantisch, stoffig grootboek (de lijst van 10.000 geldige woorden) controleren en kijken of het woord is toegestaan. Als de lijst enorm groot is, brengt de bewaker al zijn tijd door met heen en weer rennen, en loopt de rij mensen die naar binnen willen (de gedachten van de computer) vast. Dit is wat het artikel de "cardinality wall" (de cardinaliteitsmuur) noemt — een punt waarop de lijst zo groot wordt dat het systeem crasht of tot een kruipende snelheid vertraagt.

De onderzoekers realiseerden zich dat de oude methode elke lijst behandelde als een willekeurige verzameling woorden. Maar in de echte wereld zijn lijsten niet willekeurig. Denk aan een lijst met gereedschapsnamen: "aws.create_user," "aws.delete_user," "aws.list_user." Ze beginnen allemaal met "aws." Daarna hebben ze allemaal "create," "delete," of "list." Ze delen veel van dezelfde beginstukken, zoals takken aan een boom. De oude beveiligingsbeambte merkte dit niet op; hij controleerde elke keer elk woord vanaf nul.

De nieuwe Trie Automaton is als een superintelligente bibliothecaris die een speciale kaart van de bibliotheek maakt. In plaats van een lange gang, bouwt de bibliothecaris een pad in de vorm van een boom.

De Kaart: Ze tekenen een pad voor "aws." Zodra je op het "aws"-pad bent, hoef je "aws" niet meer te controleren. Je kijkt gewoon naar de volgende splitsing in de weg: "create," "delete," of "list."
De Pre-Check: Hier zit de magische truc. Voordat de computer zelfs maar begint te praten, berekent de bibliothecaris vooraf precies welke woorden toegestaan zijn bij elke splitsing in de boom. Ze schrijven deze antwoorden op kleine plakbriefjes en plakken ze direct op de takken van de boom.
De Snelheid: Nu, wanneer de computer wil spreken, rent de bibliothecaris niet naar het grootboek. Hij kijkt gewoon naar het briefje op de huidige tak. "Oh, je bent bij de 'aws'-tak? Het briefje zegt dat je als volgende alleen 'create', 'delete' of 'list' mag zeggen." Dat kost een fractie van een seconde.

De Resultaten: Van een Snail naar een Raket

De onderzoekers testten dit nieuwe systeem tegen de huidige beste methoden (zoals XGrammar) met lijsten van geldige woorden variërend van 10 tot 10.000 items. De resultaten waren spectaculair.

Compilatiesnelheid: Bij het bouwen van de kaart voor een lijst van 1.000 items duurde het oude systeem ongeveer 75 milliseconden (een klein beetje wachten). De nieuwe Trie Automaton deed het in ongeveer 33 milliseconden. Maar toen de lijst groeide naar 10.000 items, duurde het oude systeem bijna 240 milliseconden, terwijl de nieuwe methode bijna vlak bleef op 40 milliseconden. Het was alsof het oude systeem door de modder rende, terwijl de nieuwe methode op een loopband liep die niet zwaarder werd, ongeacht hoe snel je ging.
De "Cardinality Wall": De oude systemen begonnen te falen of drastisch te vertragen wanneer de lijst de paar honderd items passeerde. Het nieuwe systeem handelde lijsten van 10.000 items zonder moeite, en de onderzoekers toonden aan dat het theoretisch tot 100.000 items aan kan.
Batch Serving (De echte winst): De grootste verrassing kwam toen ze het systeem testten met veel verzoeken tegelijkertijd (zoals een druk restaurant met 256 bestellingen). Het oude systeem kon slechts ongeveer 7,5 bestellingen per seconde aan. De nieuwe Trie Automaton handelde 219 bestellingen per seconde. Dat is een verbetering van 29 keer.

Waarom was het zo veel sneller? Het was niet alleen de kaart; het was hoe de kaart werd gebruikt. Omdat de antwoorden vooraf waren opgeschreven op briefjes, hoefde de computer geen complexe berekeningen of controles uit te voeren terwijl hij aan het praten was. Hij kon gewoon het briefje pakken en verder gaan. Dit stelde de computer in staat om een hele reeks trage, ingewikkelde stappen over te slaan die het oude systeem elke keer opnieuw moest doen.

Wat dit betekent

Het artikel bewijst dat voor specifieke soorten lijsten — zoals het kiezen van een tool uit een register, het selecteren van een medische code, of het kiezen van een productcategorie — de oude "controleer alles"-methode te traag is. Door gebruik te maken van de structuur van de woorden (de gedeelde beginstukken) en de antwoorden vooraf te berekenen, maakt de nieuwe methode constrained decoding weer snel en betrouwbaar.

De onderzoekers merkten zeer zorgvuldig op dat deze nieuwe methode de computer niet slimmer maakt of verandert wat hij zegt; het zorgt er alleen voor dat hij alleen zegt wat hij moet zeggen, en dat doet hij ongelooflijk snel. Ze maten dit op echte computerchips en vonden dat de nieuwe methode 100% accuraat is in het volgen van de regels, net als de oude methode, maar doet het 7 keer sneller voor elk gegenereerd woord. Wanneer je die snelheid vermenigvuldigt met honderden gelijktijdige verzoeken, is het verschil enorm.

Kortom, het artikel vond een manier om een chaotische, trage zoektocht door een enorme hooiberg te veranderen in een snelle, georganiseerde wandeling over een vooraf verlicht pad. Het lost het probleem van de "cardinality wall" op, waardoor AI enorme lijsten met opties kan verwerken zonder vast te lopen, wat cruciaal is voor de toekomst van AI-agenten die duizenden tools of diensten direct moeten kunnen kiezen.

Technische Samenvatting: Trie Automata voor Constrained Decoding over Grote Eindige Verzamelingen

1. Probleemstelling: De Cardinaliteitsmuur

Large Language Models (LLMs) vereisen steeds vaker gestructureerde outputs die voldoen aan vooraf gedefinieerde schema's, met name bij het selecteren van een string uit een bekende eindige verzameling (bijv. toolnamen, medische codes, producttaxonomieën). Huidige systemen voor constrained decoding, zoals XGrammar en Outlines, verwerken deze beperkingen door schema's te compileren naar algemene automata (Finite State Machines, Pushdown Automata of Earley-parsers).

Hoewel dit effectief is voor complexe grammatica's, creëert deze algemene aanpak een "cardinaliteitsmuur" voor eenvoudige eindige-verzamelingbeperkingen. Naarmate het aantal geldige strings ( $K$ ) groeit naar duizenden, worden de compilatietijd en de per-stap decoding-latentie prohibitief traag. Bestaande providers leggen strikte limieten op (bijv. OpenAI bij 1.000 enums, Google Gemini bij ~120) omdat de standaard compilatiepijplijn slecht schaalt met $K$ . Het kernprobleem is een fundamentele mismatch: complexe, algemene engines worden toegepast op eenvoudige beperkingen (eindige unies van strings) die een exploiteerbare structuur bezitten (gedeelde prefixes, begrensde diepte, bekende cardinaliteit).

2. Methodologie: De Trie Automaton

De auteurs introduceren de trie automaton, een gespecialiseerde backend voor eindige-verzamelingbeperkingen die de algemene FSM-laag vervangt. De methode maakt gebruik van de structuur van de beperkingsverzameling om sub-lineaire compilatie en constante tijd per stap te bereiken.

Kernmechanismen

Character-Level Trie Constructie: In plaats van token-level tries (die falen in het delen van prefixes over token-grenzen heen) of algemene DFAs, bouwt het systeem een character-level trie direct vanuit de verzameling geldige strings. Dit voegt gedeelde prefixes samen, waardoor het aantal nodes wordt verminderd van $O(K \cdot L_{max})$ naar $O(N_{chars})$ , waarbij $N_{chars}$ het totale aantal tekens is.
BPE-Trie Alignment via Aho-Corasick: Een centrale uitdaging is het afstemmen van de character-level trie met de Byte-Pair Encoding (BPE) vocabulaire van het model. Een enkele BPE-token kan meerdere trie-edges beslaan. De auteurs lossen dit op door het probleem te reduceren tot multi-pattern string matching. Ze bouwen een Aho-Corasick (AC) automaton vanuit de vocabulaire-tokens en doorlopen de trie om de set geldige BPE-tokens (valid[n]) voor elke trie-node $n$ vooraf te berekenen.
Precomputed Masks: Tijdens de compilatie berekent het systeem valid[n] voor alle nodes. Tijdens de decoding reduceert masking tot een directe $O(1)$ lookup: $A(s_t) = valid[s_t]$ . Dit omzeilt de noodzaak om de volledige vocabulaire te scannen of transities te simuleren voor elke token bij elke stap.

Complexiteitsvoordelen

Compilatie: De kosten worden gedomineerd door de AC-automaton constructie over de vocabulaire, wat $O((N_{chars} + V) \cdot \ell)$ is, waarbij $V$ de vocabulairegrootte is en $\ell$ de maximale tokenlengte. Cruciaal is dat dit grotendeels onafhankelijk is van $K$ zodra de AC-automaton is gebouwd, wat leidt tot bijna vlakke compilatietijden (30–67ms), zelfs voor $K=10.000$ .
Per-Step Decoding: De kosten dalen van $O(V \cdot \ell)$ (het scannen van alle tokens) naar $O(|valid[s_t]|)$ . Omdat de geldige set exponentieel krimpt met de diepte van de trie (typisch 10–100 tokens na 3–4 tekens), is de effectieve kost constant en extreem laag (0.65µs).
Stateless Serving: Omdat de masks vooraf zijn berekend, kan de trie opereren als een stateless LogitsProcessor, waardoor de state management en scheduling overhead van de guided decoding pipeline die vereist is voor FSM-gebaseerde benaderingen wordt omzeild.

3. Belangrijkste Bijdragen

De Trie Automaton: Een gespecialiseerde constrained decoding backend die character-level tries, Aho-Corasick multi-pattern matching en precomputed token masks combineert. Het bereikt $O(|valid[s_t]|)$ per-stap masking, wat effectief een constante kost oplevert versus de $O(V \cdot \ell)$ kost van algemene FSM-benaderingen.
Het oplossen van het BPE-Trie Alignment Probleem: Het paper adresseert de voorheen onbehandelde uitdaging van het afstemmen van character-level trie-paden met BPE-tokens. Door dit te reduceren tot multi-pattern matching, maken ze sub-100ms compilatie mogelijk tot $K=10.000$ over diverse tokenizer-families.
Empirische Karakterisering van de Cardinaliteitsmuur: De auteurs demonstreren dat het afstemmen van handhavingsmechanismen op de structuur van de beperking de schaalbaarheidsproblemen overwint. Ze tonen aan dat precomputed masks een stateless serving pad mogelijk maken dat FSM-benaderingen niet kunnen gebruiken, wat de algoritmische versnellingen omzet in enorme throughput-winsten.

4. Experimentele Resultaten

Experimenten werden uitgevoerd op NVIDIA A100 GPU's met zeven tokenizer-families (32K–262K vocabulaire) en modellen waaronder Qwen3-8B, Mistral en Gemma3.

Compilatiesnelheid: De trie automaton bereikt een 2–6.5× snellere compilatie dan XGrammar bij $K \ge 300$ . Terwijl de XGrammar-compilatie lineair schaalt met $K$ (bereikt 2.7s bij $K=100.000$ ), blijft de trie vlak rond de ~30–67ms.
Per-Step Latency: De trie berekent valid-token masks in 0.65µs, vergeleken met 5.8µs voor XGrammar (een 7× versnelling) en 73–141µs voor LLGuidance (110–215× trager).
End-to-End Throughput: In batch serving (vLLM) cumuleert het voordeel. Bij een batch size van 256 bereikt de trie 219 req/s versus XGrammar's 7.5 req/s (29× verbetering). Deze winst komt voort uit de 7× algoritmische versnelling plus het elimineren van de overhead van de guided decoding pipeline.
Validiteit en Accuratesse: De trie garandeert 100% output validiteit. In classificatie-benchmarks (TREC, MASSIVE, Banking77, CLINC150) evenaart of overtreft constrained decoding met de trie de ongeconstraineerde accuratesse, terwijl hallucinaties worden geëlimineerd. Voor zwakkere modellen fungeert de trie als een cruciale facilitator, waarbij de accuratesse op Banking77 stijgt van 4.8% naar 24.8% door geldige outputs te waarborgen.
Schaalbaarheid: De methode behoudt sub-100ms compilatie en vlakke per-step kosten tot $K=10.000$ en verder, waardoor de praktische enum-limiet effectief wordt uitgebreid van ~1.000 naar ~100.000.

5. Betekenis en Claims

Het paper claimt dat de trie automaton een fundamentele inefficiëntie in constrained decoding oplost: het toepassen van algemene automata op eenvoudige, gestructureerde beperkingen. Door de specifieke structuur van eindige verzamelingen (gedeelde prefixes) te exploiteren, demonstreren de auteurs dat:

Algoritmische Efficiëntie: De trie is het efficiënte algoritme voor het vooraf berekenen van per-state masks over eindige verzamelingen, waarbij het de FSM-gebaseerde precomputatie met 196× versnelt.
Systemische Impact: Het vermogen om de masks vooraf te berekenen maakt een stateless serving pad mogelijk dat de guided decoding pipeline omzeilt, een voordeel dat alleen door precomputed masks mogelijk wordt gemaakt. Dit transformeert constrained decoding van een bottleneck naar een verwaarloosbare overhead in batch serving.
Generaliseerbaarheid: Het principe van het afstemmen van handhavingsmechanismen op de structuur van de beperking (bijv. het gebruik van character-position masks voor vaste formaten) levert grote versnellingen op voor elke beperking met exploiteerbare regelmaat, niet alleen voor eindige verzamelingen.

De auteurs positioneren de trie automaton niet als een benadering, maar als een exacte, isomorfe alternatief voor FSM-gebaseerde decoding voor eindige verzamelingen, wat 100% validiteit biedt met ordes van grootte aan prestatieverbeteringen in scenario's met hoge cardinaliteit.