Technische Zusammenfassung: Beschleunigung der eingeschränkten Dekodierung durch Token-Raum-Kompression (CFGZIP)

Problemstellung

Large Language Models (LLMs) müssen häufig Text generieren, der spezifischen Strukturen wie JSON, XML oder domänenspezifischen Programmiersprachen entspricht. Während LLMs bei gängigen Formaten, die in ihren Trainingsdaten vorkommen, gut abschneiden, haben sie Schwierigkeiten mit neuen oder komplexen Formaten. Um die syntaktische Korrektheit zu garantieren, werden eingeschränkte Dekodierungs-Engines eingesetzt. Diese Engines verwenden kontextfreie Grammatiken (CFGs), um bei jedem Generierungsschritt ungültige Token zu maskieren.

Aktuelle State-of-the-Art (SoTA)-Grammatik-Engines (z. B. XGrammar2) stoßen jedoch an ein signifikantes Leistungsengpass. Obwohl sie optimiert sind, müssen sie bei jedem Dekodierungsschritt Token gegen das gesamte Token-Vokabular validieren. Für komplexe CFGs (z. B. C++ oder benutzerdefinierte Sprachen) führt dies zu prohibitivem Overhead, wodurch die Inferenz-Latenz im Vergleich zur uneingeschränkten Generierung um den Faktor 2 bis 10 ansteigt. Diese Latenz macht die eingeschränkte Dekodierung für großskalige Anwendungen mit komplexen Grammatiken unpraktikabel.

Methodik: CFGZIP

Die Autoren stellen CFGZIP vor, eine Offline-Technik, die darauf ausgelegt ist, den Token-Suchraum zu komprimieren und damit die Laufzeit pro Schritt der Grammatik-Engine zu reduzieren, ohne die Korrektheit zu beeinträchtigen.

Kernkonzept: Äquivalenzklassen

Die grundlegende Erkenntnis von CFGZIP ist, dass viele Token in einem Vokabular bezüglich einer bestimmten CFG austauschbar sind. Wenn zwei Token $t$ und $u$ „syntaktisch kongruent" sind, können sie in jedem gültigen String der Sprache $L(G)$ ausgetauscht werden, ohne die Gültigkeit zu beeinflussen. Folglich muss die Grammatik-Engine nur die Gültigkeit eines repräsentativen Tokens pro Äquivalenzklasse überprüfen, anstatt jedes einzelne Token.

Die Pipeline

1. Offline-Vorverarbeitung:

   • Approximation: Da exakte syntaktische Kongruenz für beliebige CFGs unentscheidbar ist, berechnet CFGZIP eine handhabbare Approximation namens Displacement-Äquivalenz ($\sim_{L(G)}$).
   • Mechanismus: Die CFG wird in Greibach-Normalform (GNF) umgewandelt, um einen Kellerautomaten (PDA) zu nutzen. Für jedes Token berechnet das System seine „Displacement" $\Delta_G(t)$, definiert als die Menge der Eingabe-/Ausgabe-Stack-Übergänge, die das Token auf dem PDA auslöst. Token mit identischen Displacement-Mengen werden in dieselbe Äquivalenzklasse gruppiert.
   • Optimierung: Um dies rechnerisch machbar zu machen, beschränken die Autoren den Stack-Rückwärtsoperation mit einer vorab berechneten Stack-Nachbar-Relation, was eine Speicherüberlastung bei großen Grammatiken verhindert.
   • Caching: Das System ordnet Token-IDs Klassen-IDs zu und wählt ein Byte-für-Byte-kürzestes Token als „Repräsentant" für jede Klasse. Diese Zuordnungen werden auf Festplatte zwischengespeichert.

2. Operation zur Inferenzzeit:

   • Vokabular-Reduktion: Die Grammatik-Engine wird mit dem Vokabular der Äquivalenzklassen-Repräsentanten initialisiert, nicht mit dem gesamten Token-Vokabular.
   • Token-Mapping: Wenn das LLM ein Token sampelt, ordnet CFGZIP es seinem Klassen-Repräsentanten zu und übergibt diesen Repräsentanten an die Grammatik-Engine, um den Parserzustand zu aktualisieren.
   • Maskierung: Die Grammatik-Engine erzeugt eine Gültigkeitsmaske über dem kleineren Satz von Repräsentanten. Diese Maske wird dann „gesammelt" und auf die ursprünglichen LLM-Logits angewendet. Dieser Vorgang ist auf GPUs parallelisierbar und verursacht einen minimalen Overhead.

Schlüsseleigenschaften

• Verlustfrei: Die Kompression ist nachweisbar verlustfrei; die Ausgaben einer mit CFGZIP ausgestatteten Engine sind Byte-für-Byte identisch mit denen der ursprünglichen Engine.
• Engine-unabhängig: Theoretisch mit jeder Grammatik-Engine kompatibel, obwohl sich die Arbeit auf XGrammar2 konzentriert.
• Offline: Die schwere Berechnung erfolgt einmal pro Tokenizer/CFG-Paar und verursacht während der Inferenz praktisch keinen Overhead.

Experimentelle Ergebnisse

Die Autoren evaluierten CFGZIP in Kombination mit XGrammar2 auf Llama-3.2-3B, Qwen3-4B und gpt-oss-20B über vier Aufgaben hinweg: JSON-Schema, XML, C++ und Bython (eine benutzerdefinierte, geschweifte Klammern verwendende Python-Variante).

• Latenzreduktion: CFGZIP reduzierte den Overhead der Grammatik-Engine um eine bis zwei Größenordnungen.
  • Für C++ wurde die gesamte Inferenzzeit fast halbiert.
  • Für Bython (eine komplexe, ressourcenarme Sprache) wurde die gesamte Zeit für die eingeschränkte Generierung um den Faktor ~7,5x reduziert.
• Korrektheit: CFGZIP behielt 100 % syntaktische Korrektheit bei (Byte-für-Byte identisch mit der Baseline-Engine).
  • Funktionale Korrektheit: Die eingeschränkte Dekodierung verbesserte die funktionale Korrektheit erheblich, insbesondere für die Bython-Aufgabe, bei der uneingeschränkte Modelle Schwierigkeiten hatten (z. B. verbesserte sich GPT-20B von 10,8 % auf 46,9 % funktionale Korrektheit).
• Kompressionsraten: Die Technik erreichte Kompressionsraten von 40:1 (Llama-3B/C++) bis 800:1 (GPT-20B/JSON), wodurch die vom Engine zu verarbeitende Vokabulargröße drastisch reduziert wurde.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass CFGZIP eingeschränkte Dekodierung im großen Maßstab für komplexe CFGs praktikabel macht.

• Überbrückung der Lücke: Während SoTA-Engines für einfache Grammatiken (wie JSON) effizient sind, führen sie bei komplexen Grammatiken (wie C++) zu untragbarer Latenz. CFGZIP reduziert diesen Overhead auf nahezu vernachlässigbare Werte und erschließt damit die Leistungsvorteile der eingeschränkten Dekodierung für diese schwierigen Fälle.
• Kosteneffektivität: Die Ergebnisse deuten darauf hin, dass für kleinere, günstigere Modelle die eingeschränkte Dekodierung eine viable Alternative sein kann, um große Modelle für hohe funktionale Korrektheit einzusetzen.
• Praktikabilität: Durch die Entkopplung der schweren Arbeit in eine Offline-Vorverarbeitungsphase ermöglicht CFGZIP Echtzeit-Anwendungen, die eine strikte Einhaltung komplexer domänenspezifischer Sprachen erfordern, ohne Geschwindigkeit zu opfern.

Einschränkungen

Die Autoren weisen darauf hin, dass CFGZIP keine universelle Lösung für alle Szenarien ist:

• Dynamische Kontexte: Die Offline-Vorverarbeitungszeit (von Sekunden bis Minuten) macht sie weniger geeignet für dynamische, einmalige CFGs (z. B. ad-hoc JSON-Schemata oder Funktionsaufrufe), bei denen Engines wie llguidance bereits hochgradig optimiert sind.
• Engine-Kompatibilität: Obwohl theoretisch engine-unabhängig, ist die aktuelle Implementierung Python-basiert und in XGrammar2 integriert. Sie ist nicht kompatibel mit rein C++-basierten Engines wie llama.cpp (aufgrund fehlender Python-Bindings) oder Engines, die die verwendeten spezifischen CFGs nicht unterstützen (z. B. linksrekursive Grammatiken in transformers-cfg).
• Umfang: Die Methode eignet sich am besten für statische, große und komplexe CFGs, wie sie bei der Code-Generierung verwendet werden.