💬 NLP

Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

Dit artikel stelt een generieke aanpak voor om bias in lokaal beperkte decodering te mitigeren door door middel van getensoriseerde eindige automaten en circuitvermenigvuldiging hanteerbare, globaal beperkte voorstellen te construeren, wat efficiënte Sequential Monte Carlo-sampling mogelijk maakt die sneller convergeert naar de doelverdeling met minder deeltjes over taken zoals function calling en SQL-generatie.

Oorspronkelijke auteurs: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

Gepubliceerd 2026-06-02

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

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 voor dat je een zeer creatieve maar enigszins chaotische verhalenverteller (een Large Language Model) probeert te leren om een verhaal te schrijven dat een zeer strikt regelboek volgt, zoals een JSON-codeformaat of een specifieke SQL-databasequery.

Het probleem is dat de verhalenverteller ervan houdt om te dwalen. Als je alleen zegt: "Breek de regels niet," kan de verhalenverteller een zin beginnen die er in het begin goed uitziet, maar aan het einde onmogelijk correct af te maken is.

Hier is hoe het papier dit probleem oplost, met behulp van eenvoudige analogieën:

1. De Oude Manier: De "Miope" Gids (LCD)

Stel je voor dat de verhalenverteller door een doolhof loopt. De oude methode (genoemd Locally Constrained Decoding of LCD) werkt als een gids die alleen naar de volgende stap kijkt.

Hoe het werkt: Als de volgende stap eruitziet alsof deze misschien tegen een muur aanloopt, blokkeert de gids deze.
De Fout: De gids is "mioop" (kortzichtig). Ze kunnen de verhalenverteller een pad laten nemen dat voor de volgende stap veilig lijkt, maar dat drie stappen later in een doodlopende weg eindigt. De verhalenverteller blijft doorlopen, denkend dat het goed gaat, om er pas aan het einde achter te komen dat hij het verhaal niet binnen de woordlimiet kan afmaken. Hij moet dan opnieuw beginnen of een kapot verhaal produceren.

2. De Nieuwe Manier: De "Globale Kaart" (GCD)

De auteurs stellen een nieuwe methode voor genaamd Globally Constrained Decoding (GCD).

De Analogie: In plaats van alleen naar de volgende stap te kijken, heeft deze gids een volledige kaart van het hele doolhof en weet precies hoeveel stappen er nog over zijn om de uitgang te bereiken.
Hoe het werkt: Voordat de verhalenverteller een stap zet, controleert de gids: "Als je deze kant op gaat, kun je dan daadwerkelijk de uitgang bereiken binnen de resterende stappen?"
Het Resultaat: Als het antwoord "Nee" is, blokkeert de gids dat pad onmiddellijk. Dit garandeert dat de verhalenverteller, ongeacht wat hij kiest, altijd een geldig einde zal bereiken. Het is als het hebben van een GPS die alleen routes laat zien die gegarandeerd leiden naar je bestemming op tijd.

3. De "Slimme" Kaart: Waarschijnlijkheid Toevoegen (P-GCD)

De "Globale Kaart" (GCD) is geweldig in het vermijden van doodlopende wegen, maar behandelt alle geldige paden als gelijk. Het weet niet welk pad de verhalenverteller verkiest of welk pad waarschijnlijker een goed verhaal is.

De Analogie: Stel je voor dat de verhalenverteller een favoriete manier van lopen heeft. De basiskaart zegt alleen: "Dit pad is geldig." De nieuwe Probabilistic GCD (P-GCD) zegt: "Dit pad is geldig, en het is ook het pad dat de verhalenverteller het meest waarschijnlijk leuk zal vinden."
Hoe het werkt: De auteurs combineren de "Globale Kaart" (de regels) met een "Geheugenmodel" (een vereenvoudigde versie van het brein van de verhalenverteller). Ze vermenigvuldigen deze twee met elkaar.
Het Resultaat: De gids blokkeert nu niet alleen slechte paden; hij stuurt de verhalenverteller ook subtiel richting de paden die zowel geldig als van hoge kwaliteit zijn. Dit maakt het vertelproces veel efficiënter.

4. De "Deeltjes"-race (SMC)

Om deze methoden te testen, gebruiken de onderzoekers een techniek genaamd Sequential Monte Carlo (SMC).

De Analogie: Stel je voor dat je de beste route door een mistig bos probeert te vinden. In plaats van één persoon te sturen, stuur je een zwerm van 100 "deeltjes" (explorers) uit.
De Oude Manier: Met de kortzichtige gids moet je duizenden verkenners sturen omdat velen van hen verdwaald raken of tegen doodlopende wegen aanlopen voordat ze klaar zijn.
De Nieuwe Manier: Met de "Globale Kaart" en de "Slimme Kaart" blijven de verkenners op het juiste spoor. Je hebt veel minder verkenners nodig om het perfecte pad te vinden, omdat de gids veel beter is in het vroegtijdig filteren van slechte opties.

5. De "Vormveranderende" Truc (Tensorization)

Een van de technische doorbraken van het papier is hoe ze de "Kaart" afhandelen.

Het Probleen: Complexe regels (zoals JSON-schema's) kunnen kaarten creëren met miljoenen paden. Normaal gesproken raken computers overbelast bij het tekenen van deze kaarten op een standaard processor.
De Oplossing: De auteurs hebben deze complexe kaarten omgezet in wiskundige blokken (tensors) die perfect passen op moderne grafische kaarten (GPU's).
De Analogie: Het is alsof je een enorme, rommelige stapel papieren kaarten neemt en ze opvouwt tot een compacte, hogesnelheids digitale chip die een supercomputer direct kan lezen. Dit zorgt ervoor dat de "Globale Kaart" in een oogwenk kan worden berekend, zelfs voor zeer complexe regels.

Samenvatting van de Resultaten

Het papier heeft dit getest op drie real-world taken:

Function Calling: Ervoor zorgen dat AI computerfuncties aanroept met het juiste formaat (zoals JSON).
Keyword Generation: Ervoor zorgen dat een verhaal specifieke woorden bevat.
SQL Generation: Het schrijven van databasequeries die syntactisch correct zijn.

Het Oordeel:

Betrouwbaarheid: De nieuwe methode garandeert dat het verhaal correct eindigt binnen de woordlimiet, terwijl de oude methode vaak bij de finishlijn faalde.
Efficiëntie: Om hetzelfde kwaliteitsniveau van resultaten te krijgen, had de nieuwe methode aanzienlijk minder "deeltjes" (particles) nodig dan de oude methode.
Snelheid: Hoewel de "Slimme Kaart" (P-GCD) iets meer rekenkracht vraagt, is het nog steeds snel genoeg om praktisch bruikbaar te zijn, en de "Globale Kaart" (GCD) is bijna net zo snel als de oude methode.

Kortom, het papier geeft AI een "Globale Kaart" en een "Slimme Duw" zodat het strikte regels kan volgen zonder de weg kwijt te raken, tijd te verspillen of kapotte code te produceren.

Technische Samenvatting: Het mitigeren van bias in lokaal beperkt decoderen via tractabele voorstellen

Probleemstelling

Large Language Models (LLM's) falen vaak in het genereren van outputs die strikt voldoen aan logische of structurele beperkingen, zoals JSON-schema's, geldige SQL-queries of specifieke function-calling formaten. Hoewel instructie-tuning en preference optimalisatie de algemene afstemming hebben verbeterd, blijven ze onbetrouwbaar voor het afdwingen van "harde" beperkingen.

Bestaande benaderingen kampen met twee primaire beperkingen:

Rejection Sampling: Hoewel onbevooroordeeld, is het computationeel onpraktisch voor complexe beperkingen vanwege de extreem lage acceptatiepercentages.
Locally Constrained Decoding (LCD): Deze standaardbenadering maskeert tokens die op elk punt direct een beperking schenden. Dit lijdt echter aan twee kritieke gebreken:
- Bias: Het vervormt de onderliggende distributie van het model door myope maskering van tokens zonder rekening te houden met toekomstige geldigheid, wat leidt tot sampling bias.
- Geen terminatiegarantie: LCD waarborgt alleen lokale geldigheid. Een sequentie kan indefinite tijd lokaal geldig blijven (bijv. een niet-gesloten accolade in JSON) maar er niet in slagen aan de beperking te voldoen binnen een vaste token-budget $n$ .

Om deze problemen aan te pakken, is het Sequential Monte Carlo (SMC) framework voorgesteld, waarbij LCD wordt gebruikt als een proposal-distributie en het herwegen van deeltjes (particles) plaatsvindt om te convergeren naar de doelverdeling. Echter, de convergentiesnelheid van SMC wordt beperkt door de kwaliteit van het voorstel; LCD is een zwak voorstel omdat het geen probabilistische informatie bevat over toekomstige geldige voltooiingen en geen garantie biedt op het voldoen aan de beperking binnen een eindig budget.

Methodologie

De auteurs stellen een generieke benadering voor om tractabele voorstellen en potentiaalfuncties te construeren voor SMC-sampling uit de beperkte distributie $p_{lm}(\cdot \mid C)$ . De kerninnovatie bestaat uit het representeren van beperkingen als eindige automaten en het benutten van tensoroperaties voor efficiënte GPU-executie.

1. Globally Constrained Decoding (GCD)

GCD verbetert LCD door te garanderen dat elke gegenereerde token kan leiden tot een geldige voltooiing binnen het resterende token-budget $n$ .

Tensorized Finite Automata: Beperkingen gecodeerd als Finite Automata (FA), specifiek Non-deterministic Finite Automata (NFA's) en Deterministic Finite Automata (DFA's), worden gecompileerd naar tensorized representaties (transitiematrices $T_{out}, T_{in}$ en emissiematrix $B_f$ ). Dit maakt efficiënte executie op GPU's mogelijk.
Forward-Backward Inference:
- Forward Process: Berekent de set FA-toestanden die bereikbaar zijn na het observeren van de prefix $x_{1:t-1}$ .
- Backward Process: Berekent of een toestand in exact $n-t$ stappen een accepterende toestand kan bereiken.
Global Masking: Een token wordt alleen toegestaan als het leidt naar een toestand die een geldige voortzetting toestaat binnen het resterende budget. Dit garandeert dat elke sequentie van lengte $n$ die onder GCD wordt gegenereerd, aan de beperking $C$ voldoet.

2. Probabilistic Globally Constrained Decoding (P-GCD)

Hoewel GCD voldoen aan de beperking garandeert, is de maskering binair (geldig/ongeldig) en negeert het de waarschijnlijkheid van geldige voltooiingen onder de LLM. P-GCD pakt dit aan door probabilistische informatie te integreren.

HMM Distillatie: De distributie van de LLM wordt benaderd door een Hidden Markov Model (HMM), volgens eerder werk (Zhang et al., 2023).
Circuit Multiplication: De tensorized FA (gezien als een ongenormaliseerde HMM over edges) wordt vermenigvuldigd met de gedestilleerde HMM met behulp van circuit multiplication algoritmen. Dit maakt gebruik van de gedeelde algebraïsche structuur van FA's en HMM's.
Productdistributie: De resulterende productdistributie $p_{prod}$ vangt zowel de harde logische beperkingen van de FA als de probabilistische voorkeuren van de LLM op.
Proposal en Potentiaal:
- Proposal ( $q_{pgcd}$ ): Herweegt de LM-distributie bij elke stap met behulp van de beperkte volgende-token waarschijnlijkheid afgeleid van $p_{prod}$ .
- Potentiaal ( $\phi_{pgcd}$ ): Weegt de deeltjes in SMC door de product van de prefix-waarschijnlijkheid van de LM en de look-ahead schatting van de HMM voor het voldoen aan de beperking.

3. Efficiënte Implementatie

De auteurs maken gebruik van tensor-netwerkoperaties (specifiek de Kronecker-vec identiteit) om te voorkomen dat grote Kronecker-productmatrices expliciet worden gematerialiseerd. Dit vermindert de computationele kosten van transitiestappen van $O((HE)^2)$ naar $O(H^2E + HE^2)$ , waarbij $H$ de HMM-verborgen grootte is en $E$ het aantal FA-edges, wat efficiënte autoregressieve generatie mogelijk maakt.

Belangrijkste Bijdragen

GCD en P-GCD Frameworks: De introductie van Globally Constrained Decoding en Probabilistic GCD, die tractabele voorstellen en potentialen bieden voor SMC die voldoen aan de beperking binnen een token-budget.
Tensorized Automata op GPU's: Het eerste voorstel om finite automata (inclusief NFA's) te tensorizen voor efficiënte GPU-native inferentie, waarmee de CPU-gebonden beperkingen van bestaande frameworks zoals Outlines en XGrammar worden overwonnen.
NFA Support: Het aantonen dat NFA's exponentieel compacter kunnen zijn dan DFA's voor complexe beperkingen (bijv. function calling met variabele parameters), wat de aanpak schaalbaar maakt voor real-world agentic toepassingen waar DFA-constructie kan leiden tot geheugenoverloop.
Integratie met SMC: Het aantonen dat (P-)GCD de convergentie van SMC aanzienlijk versnelt vergeleken met LCD-gebaseerde voorstellen, waarbij veel minder deeltjes nodig zijn om de doelverdeling te bereiken.

Experimentele Resultaten

De auteurs hebben (P-)GCD geëvalueerd op drie benchmarks: xLAM (function calling), CommonGen (keyword-based generation) en Spider (text-to-SQL).

Function Calling (xLAM):
- (P-)GCD behaalde een substantieel hogere nauwkeurigheid dan LCD bij hetzelfde aantal deeltjes.
- P-GCD convergeerde sneller naar de grondwaarheid-distributie (rejection sampling) dan GCD, wat het voordeel van probabilistische informatie benadrukt.
- Constraint Satisfaction: GCD en P-GCD behaalden een 100% voldoen aan de beperking over alle deeltjes-budgets, terwijl LCD zelfs bij gematigde budgetten faalde (bijv. ~95% voor JSON).
- Efficiëntie: LCD en GCD veroorzaakten een bescheiden overhead (1.08× en 1.10× vertraging). P-GCD was trager (3.11× tot 10.2×) door HMM-computaties, maar bleef haalbaar.
Keyword Generatie (CommonGen): Het gebruik van P-GCD als zowel proposal als potentiaal verbeterde de BLEU-scores en de convergentiesnelheid aanzienlijk ten opzichte van LCD.
Text-to-SQL (Spider): GCD en P-GCD verbeterden de executie-nauwkeurigheid ten opzichte van LCD over diverse deeltjes-budgets, met name bij gematigde waarden.
NFA vs. DFA: Experimenten bevestigden dat voor complexe schema's (bijv. variabelen-lengte function parameters) NFA's lineair groeien in omvang, terwijl DFA's exponentieel groeien. Voor de Spider SQL grammatica leidde DFA-constructie tot Out-of-Memory (OOM) fouten op token-niveau, terwijl de NFA tractabel bleef (~32k toestanden).

Betekenis en Claims

Het artikel claimt dat lokaal beperkt decoderen een substantiële sampling bias introduceert en er niet in slaagt om binnen eindige token-budgetten aan de beperking te voldoen. Door (P-)GCD voor te stellen, biedt de auteur een oplossing die:

Geldigheid Garandeert: Zorgt ervoor dat elke gegenereerde sequentie van lengte $n$ aan de beperking voldoet, waardoor de faalgevallen van LCD worden geëlimineerd.
Bias Vermindert: Door probabilistische informatie te integreren (via P-GCD) en globale lookahead, benaderen de voorstellen de doelvoorwaardelijke distributie beter.
Efficiëntie Verbetert: In het SMC-framework convergeert (P-)GCD naar de doelverdeling met aanzienlijk minder deeltjes dan LCD-gebaseerde benaderingen, wat de computationele kosten van hoogwaardige beperkte generatie verlaagt.

Dit werk positioneert zich als een fundamentele stap naar betrouwbare, beperkings-voldoende generatie voor LLM's in toepassingen die strikte structurele naleving vereisen, zoals function calling en code generatie, door logische beperkingen (via automata) en probabilistische modellering (via HMM's) te verenigen op een GPU-efficiënte wijze.