Technische Samenvatting: Decode-Time Grammatica's

1. Probleemstelling

Large Language Models (LLMs) worden steeds vaker gebruikt voor het genereren van code voor agenten en serveer-systemen waarbij de gegenereerde output wordt gecompileerd of uitgevoerd zonder menselijke controle. Hoewel dit werkt voor mainstream talen, blijft het fragiel voor low-resource programmeeroppervlakken zoals domeinspecifieke talen (DSL's), custom library API's en command-line tools.

Een terugkerende foutmodus in deze omgevingen is de ghost reference: een syntactisch geldige token (bijv. een variabelenaam, kolom, API-functie of CLI-optie) die niet bestaat in de huidige runtime-omgeving $\Gamma$.

• Voorbeelden: Het refereren aan een buffer die nooit is gedeclareerd in een TileLang kernel, het selecteren van een kolom die afwezig is uit een SQL-schema, of het aanroepen van een intrinsic die niet beschikbaar is in een specifieke versie van een library.
• Oorzaak: Deze fouten komen vaak voort uit negative transfer, waarbij het model kennis toepast van een naburige dialect, een oudere API-versie of een andere tool-interface op de doelomgeving.
• Beperkingen van bestaande oplossingen:
  • Fixed Grammars: Standaard grammatica-beperkte decodering (bijv. CFG's) waarborgt syntactische geldigheid maar behandelt referentieposities als open klassen (bijv. identifier), waardoor zowel geldige als ongeldige namen worden toegelaten.
  • Model-Side Remedies: Prompting, fine-tuning of retry-mechanismen kunnen de waarschijnlijkheid van fouten verminderen, maar kunnen ongeldige continuaties niet verwijderen uit de support set van het model. Ze vertrouwen erop dat het model de "juiste" weg verkiest, wat onvoldoende is wanneer de "foute" weg vloeiend en hoog-waarschijnlijk is.

2. Methodologie: Decode-Time Grammatica's

De paper introduceert decode-time grammars, een framework waarbij grammatica-fragmenten dynamisch worden geïnstantieerd tijdens de generatie op basis van een runtime-omgeving $\Gamma$.

Kernmechanisme

1. Runtime Omgeving ($\Gamma$): Een snapshot van de huidige staat, bevattende in-scope namen, sorts, shapes, schema-entries, API-members of tool-state. $\Gamma$ evolueert naarmate declaraties worden gegenereerd.
2. Grammatica-fragmenten & Verfijningsvolgorde: In plaats van één enkele vaste grammatica, gebruikt het systeem een bibliotheek van grammatica-fragmenten die geordend zijn door verfijning ($\sqsubseteq$).
   • Fragmenten variëren van coars (bijv. het accepteren van elke identifier) tot tight (bijv. het accepteren van alleen namen gedeclareerd in $\Gamma$).
   • Een per-regio beleid $\pi(s, \Gamma)$ selecteert het passende fragment voor een specifieke "gat" (een getypeerde positie in de generatie) op basis van de verwachte sort $s$ en de huidige omgeving.
3. De $\tau_\Gamma$ Operator (Tightening): Dit is het cruciale mechanisme. Het transformeert een open referentiepositie in een fragment naar een $\Gamma$-getypeerde slot.
   • De kandidaat-set van de slot is exact de namen die beschikbaar zijn in $\Gamma$ (bijv. Gamma.names(sort=Buffer)).
   • Deze kandidaten worden gecompileerd naar een escaped alternatie (bijv. "A" | "B" | "C") en geïnjecteerd in de token-level recognizer vóór het decoderen van deze regio.
4. Self-Extending Generation: Terwijl het model declaraties genereert, worden deze geëxtraheerd en toegevoegd aan $\Gamma$ voordat daaropvolgende referentie-holes worden gedecodeerd. Dit zorgt ervoor dat referenties beperkt worden door de reeds gegenereerde prefix.

Systeemarchitectuur

De implementatie, gproj, bestaat uit twee componenten:

• TemplateInductor (Offline): Gebruikt anti-unificatie op kleine corpora om grammatica-fragmenten en policies te induceren. Het valideert fragmenten tegen een "hard gate" met behulp van corpus-posities en automatisch gegenereerde negatieven (inclusief gemined ghost references) om uitvoerbaarheid en correctheid te garanderen.
• gproj Executor (Online): Een online masked executor die $\Gamma$ bijhoudt, de policy $\pi$ bevraagt, fragmenten instancieert via $\tau_\Gamma$, en de resulterende grammatica compileert naar een token mask voor de LLM decoder (bijv. XGrammar).

3. Belangrijkste Bijdragen & Formele Resultaten

Theoretische Bijdragen

• No-Ghost Soundness: De paper bewijst dat voor elk fragment waar referentieposities worden gerealiseerd als $\Gamma$-getypeerde slots, de gegenereerde strings scope-veilig zijn door constructie. Elke uitgegeven referentie is gegarandeerd aanwezig in $\text{dom}(\Gamma)$.
• Refinement Preservation: Er wordt bewezen dat als een lossere fragment sound is, elke striktere verfijning (via $\tau_\Gamma$) deze soundness behoudt. Dit maakt het systeem in staat om tussen fragment-sterktes te schakelen zonder own-errors te introduceren.
• Noodzakelijkheid van Dynamische Support (Proposition 3): De paper bewijst dat geen enkele eindige familie van precompiled grammars met vaste referentie-supports zowel sound (geen ghost references) als non-blocking (toelaat alle geldige continuaties) kan zijn voor onbegrensde identifier-ruimtes.
  • Implicatie: Exacte referentie-support moet tijdens het decoderen worden gesynthetiseerd op basis van de prefix. Statische pre-compilatie is theoretisch onvoldoende voor declaratie-consistente talen.

Praktische Bijdragen

• Verdeling van Arbeid: De aanpak scheidt omgeving-gebonden correctheid (behandeld door de mask) van open-ended program decisions (behandeld door het model). De mask garandeert dat referenties geldig zijn; het model kiest het algoritme, de strategie of de intentie.
• Inductie-pipeline: Een methode om automatisch de vereiste grammatica-fragmenten en policies te genereren van kleine corpora, wat de aanpak toepasbaar maakt voor nieuwe DSL's zonder handmatige grammatica-engineering.

4. Evaluatieresultaten

Het systeem werd geëvalueerd over TileLang (tensor-kernel DSL), SQL (Spider dataset), P4 (data-plane taal) en CLI tools (git, FFmpeg), met modellen variërend van 0.6B tot 236B parameters.

• Eliminatie van Ghost References:
  • Over alle oppervlakken bereikte de $\Gamma$-getypeerde arm (met gebruik van $\tau_\Gamma$) 0% ghost references door constructie.
  • In contrast hiermee faalden open identifier arms (vrije decodering) door ghost references in 100% van de gevallen voor TileLang, SQL en P4, ongeacht de modelgrootte (0.6B tot 236B).
  • Voorbeeld: Op SQL resulteerden open identifiers in 0% execution match; $\Gamma$-constrained decoding bereikte 100%.
• Modelonafhankelijkheid: De garantie is overdraagbaar op modelgrootte. Zelfs het 236B frontier model (DeepSeek-V4-Flash) faalde om geldige referenties te genereren zonder de mask, terwijl het 0.6B model slaagde met de mask.
• Vergelijking met Alternatieven:
  • Prompting/Retry: Op SQL bereikte prompting met schema en maximaal 4 retries een 90% execution match, maar produceerde nog steeds 5 ghost columns. De mask bereikte 100% match met 0 ghosts in één enkele pass.
  • Kosten: De aanpak brengt een gematigde overhead met zich mee. Relatief aan unconstrained decoding bedraagt de end-to-end throughput reductie gemiddeld 17.3%. Relatief aan standaard constrained decoding (XGrammar), reduceert gproj de throughput met 10.6–17.8%.
• Offline Inductie: De TemplateInductor slaagde er succesvol in om geldige fragmenten te induceren voor complexe oppervlakken (bijv. AscendC operators, FFmpeg filters) die niet handmatig geschreven waren, wat de "inductie + hard gate" workflow valideert.

5. Betekenis en Claims

De paper claimt dat decode-time grammars een precieze, stabiele laag van correctheid bieden die orthogonal is aan modelcapaciteit.

• Mechanische Garantie: Het transformeert referentie-veiligheid van een probabilistische uitkomst (afhankelijk van modelkwaliteit) naar een garantie op constructieniveau.
• Schaalbaarheid: Door de "semantische schets" (taak van het model) te scheiden van "omgeving-gebonden referenties" (taak van de mask), stelt het systeem zwakkere modellen in staat om geldige code te genereren in low-resource omgevingen waar ze anders zouden hallucineren.
• Theoretische Noodzakelijkheid: Het bewijs dat statische grammatica's niet tegelijkertijd sound en non-blocking kunnen zijn voor declaratie-consistente talen, vestigt de noodzaak van de voorgestelde runtime-instantiatie aanpak.

De auteurs positioneren dit werk niet als een oplossing voor volledige programmatische semantische correctheid (bijv. algoritmische logica of terminatie), maar als een robuust mechanisme om de specifieke klasse van mechanisch enumereerbare fouten (ongedefinieerde symbolen) te elimineren die codegeneratie in beperkte omgevingen teisteren.