Technische Samenvatting: Versnelling van Beperkte Decoding met Tokenruimtecompressie (CFGZIP)

Probleemstelling

Grote Taalmodellen (LLMs) moeten vaak tekst genereren die voldoet aan specifieke structuren, zoals JSON, XML of domeinspecifieke programmeertalen. Hoewel LLMs goed presteren op veelvoorkomende formaten die in hun trainingsdata voorkomen, worstelen ze met nieuwe of complexe formaten. Om syntactische correctheid te garanderen, worden Beperkte Decoding-engines ingezet. Deze engines gebruiken Context-Vrije Grammatica's (CFG's) om ongeldige tokens bij elke generatiestap te maskeren.

Echter, huidige state-of-the-art (SoTA) grammatica-engines (bijvoorbeeld XGrammar2) ondervinden een aanzienlijke prestatieknelpunt. Hoewel ze geoptimaliseerd zijn, moeten ze bij elke decodingstap tokens valideren tegen de volledige tokenvocabulaire. Voor complexe CFG's (bijvoorbeeld C++ of aangepaste talen) resulteert dit in onaanvaardbare overhead, waardoor de inferentielatentie 2x tot 10x toeneemt in vergelijking met onbeperkte generatie. Deze latentie maakt beperkte decoding onuitvoerbaar voor grootschalige toepassingen die complexe grammatica's vereisen.

Methodologie: CFGZIP

De auteurs introduceren CFGZIP, een offline techniek die is ontworpen om de tokenzoekruimte te comprimeren, waardoor de runtime per stap van de grammatica-engine wordt verminderd zonder correctheid in te leveren.

Kernconcept: Equivalentieklassen

Het fundamentele inzicht van CFGZIP is dat veel tokens in een vocabulaire uitwisselbaar zijn met betrekking tot een specifieke CFG. Als twee tokens $t$ en $u$ "syntactisch congruent" zijn, kunnen ze in elke geldige string van de taal $L(G)$ worden verwisseld zonder de geldigheid te beïnvloeden. Bijgevolg hoeft de grammatica-engine slechts de geldigheid van één representatief token per equivalentieklasse te verifiëren, in plaats van elk individueel token.

De Pipeline

1. Offline Voorberekening:

   • Benadering: Aangezien exacte syntactische congruentie onbeslisbaar is voor willekeurige CFG's, berekent CFGZIP een hanteerbare benadering genaamd Displacement Equivalence ($\sim_{L(G)}$).
   • Mechanisme: De CFG wordt omgezet naar Greibach Normal Form (GNF) om een Pushdown Automaton (PDA) te benutten. Voor elk token berekent het systeem zijn "displacement" $\Delta_G(t)$, gedefinieerd als de set input/output-stacktransities die het token induceert op de PDA. Tokens met identieke displacement-sets worden gegroepeerd in dezelfde equivalentieklasse.
   • Optimalisatie: Om dit computatief haalbaar te maken, beperken de auteurs de stack-backtrackoperatie met behulp van een vooraf berekende stack-adjacentierelatie, waardoor geheugenexplosie bij grote grammatica's wordt voorkomen.
   • Caching: Het systeem koppelt token-ID's aan klassen-ID's en selecteert een byte-voor-byte kortst mogelijke token als "representatief" voor elke klasse. Deze koppelingen worden op schijf gecached.

2. Operatie tijdens Inferentie:

   • Vocabulairevermindering: De grammatica-engine wordt geïnitieerd met het vocabulaire van representatieven van equivalentieklassen in plaats van de volledige tokenvocabulaire.
   • Tokenkoppeling: Wanneer het LLM een token samplet, koppelt CFGZIP dit aan zijn klasserepresentatief en geeft deze representatief door aan de grammatica-engine om de parserstatus bij te werken.
   • Maskering: De grammatica-engine produceert een geldigheidsmasker over de kleinere set representatieven. Dit masker wordt vervolgens "verzameld" en toegepast op de oorspronkelijke LLM-logits. Deze operatie is paralleliseerbaar op GPU's en veroorzaakt minimale overhead.

Belangrijkste Eigenschappen

• Verliesvrij: De compressie is bewezen verliesvrij; de output van een met CFGZIP uitgeruste engine is byte-identiek aan die van de originele engine.
• Engine-onafhankelijk: Theoretisch compatibel met elke grammatica-engine, hoewel de paper zich richt op XGrammar2.
• Offline: De zware berekening vindt één keer plaats per tokenizer/CFG-paar, wat tijdens inferentie vrijwel geen overhead veroorzaakt.

Experimentele Resultaten

De auteurs evalueerden CFGZIP gekoppeld aan XGrammar2 op Llama-3.2-3B, Qwen3-4B en gpt-oss-20B over vier taken: JSON Schema, XML, C++ en Bython (een aangepaste, op accolades gebaseerde Python-variant).

• Latentievermindering: CFGZIP verlaagde de overhead van de grammatica-engine met één tot twee ordes van grootte.
  • Voor C++ werd de totale inferentietijd bijna gehalveerd.
  • Voor Bython (een complexe, low-resource taal) werd de totale tijd voor beperkte generatie met een factor van ~7,5x verminderd.
• Correctheid: CFGZIP behield 100% syntactische correctheid (byte-identiek aan de baseline-engine).
  • Functionele Correctheid: Beperkte decoding verbeterde de functionele correctheid aanzienlijk, met name voor de Bython-taak, waarbij onbeperkte modellen worstelden (bijvoorbeeld verbeterde GPT-20B van 10,8% naar 46,9% functionele correctheid).
• Compressiefactoren: De techniek bereikte compressiefactoren variërend van 40:1 (Llama-3B/C++) tot 800:1 (GPT-20B/JSON), waardoor de vocabulairegrootte die de engine moet verwerken drastisch werd verminderd.

Betekenis en Claims

De paper claimt dat CFGZIP beperkte decoding op schaal haalbaar maakt voor complexe CFG's.

• Overbrugging van de Kloof: Waar SoTA-engines efficiënt zijn voor eenvoudige grammatica's (zoals JSON), introduceren ze onoplosbare latentie voor complexe grammatica's (zoals C++). CFGZIP verkleint deze overhead tot verwaarloosbare niveaus, waardoor de prestatievoordelen van beperkte decoding voor deze moeilijke gevallen worden vrijgegeven.
• Kosteneffectiviteit: De resultaten suggereren dat voor kleinere, goedkopere modellen, beperkte decoding een haalbaar alternatief kan zijn voor het gebruik van grotere modellen om hoge functionele correctheid te bereiken.
• Praktijktoepasbaarheid: Door de zware arbeid te ontkoppelen naar een offline voorberekeningsfase, stelt CFGZIP real-time toepassingen in staat die strikte naleving van complexe domeinspecifieke talen vereisen, zonder snelheid in te leveren.

Beperkingen

De auteurs merken op dat CFGZIP geen universele oplossing is voor alle scenario's:

• Dynamische Contexten: De offline voorberekeningstijd (variërend van seconden tot minuten) maakt het minder geschikt voor dynamische, eenmalige CFG's (bijvoorbeeld ad-hoc JSON-schema's of functiedeployments) waar engines zoals llguidance al sterk geoptimaliseerd zijn.
• Engine-compatibiliteit: Hoewel theoretisch engine-onafhankelijk, is de huidige implementatie Python-gebaseerd en geïntegreerd met XGrammar2. Het is niet compatibel met C++-only engines zoals llama.cpp (vanwege het ontbreken van Python-bindings) of engines die de specifieke gebruikte CFG's niet ondersteunen (bijvoorbeeld links-recursive grammatica's in transformers-cfg).
• Scope: De methode is het meest geschikt voor statische, grote en complexe CFG's, zoals die worden gebruikt in codegeneratie.