💬 NLP

Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

Dieses Paper schlägt einen generischen Ansatz vor, um Bias in lokal beschränktem Decoding zu mildern, indem es durch tensorisierte endliche Automaten und Schaltkreismultiplikation handhabbare, global beschränkte Vorschläge konstruiert, was ein effizientes Sequential Monte Carlo Sampling ermöglicht, das schneller gegen die Zielverteilung konvergiert und dabei weniger Partikel über Aufgaben wie Function Calling und SQL-Generierung hinweg benötigt.

Ursprüngliche Autoren: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

Veröffentlicht 2026-06-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, einem sehr kreativen, aber etwas chaotischen Geschichtenerzähler (einem Large Language Model) beizubringen, eine Geschichte zu schreiben, die einem sehr strengen Regelwerk folgt, wie etwa einem JSON-Codeformat oder einer spezifischen SQL-Datenbankabfrage.

Das Problem ist, dass der Geschichtenerzähler dazu neigt, zu abschweifen. Wenn Sie einfach nur sagen: „Brich die Regeln nicht“, fängt er vielleicht einen Satz an, der anfangs völlig in Ordnung aussieht, sich aber am Ende als unmöglich zu vollenden erweist.

So löst dieses Paper das Problem, unter Verwendung einfacher Analogien:

1. Die alte Art: Der „kurzsichtige“ Führer (LCD)

Stellen Sie sich vor, der Geschichtenerzähler geht durch ein Labyrinth. Die alte Methode (genannt Locally Constrained Decoding oder LCD) fungiert wie ein Führer, der nur auf den nächsten Schritt schaut.

Wie es funktioniert: Wenn der nächste Schritt so aussieht, als könnte er eine Wand berühren, blockiert der Führer ihn.
Der Fehler: Der Führer ist „myopisch“ (kurzsichtig). Er lässt den Geschichtenerzähler vielleicht einen Pfad einschlagen, der für den nächsten Schritt sicher aussieht, aber drei Schritte später in einer Sackgasse endet. Der Geschichtenerzähler läuft weiter und denkt, alles sei in Ordnung, nur um am Ende festzustellen, dass er die Geschichte innerhalb des Wortlimits nicht korrekt abschließen kann. Er muss von vorne beginnen oder produziert eine fehlerhafte Geschichte.

2. Die neue Art: Die „Globale Karte“ (GCD)

Die Autoren schlagen eine neue Methode namens Globally Constrained Decoding (GCD) vor.

Die Analogie: Anstatt nur auf den nächsten Schritt zu schauen, besitzt dieser Führer eine vollständige Karte des gesamten Labyrinths und weiß genau, wie viele Schritte noch bis zum Ausgang verbleiben.
Wie es funktioniert: Bevor der Geschichtenerzähler einen Schritt macht, prüft der Führer: „Wenn du diesen Weg nimmst, kannst du den Ausgang tatsächlich innerhalb der verbleibenden Schritte erreichen?“
Das Ergebnis: Wenn die Antwort „Nein“ lautet, blockiert der Führer diesen Pfad sofort. Dies garantiert, dass der Geschützerzähler, egal welchen Weg er wählt, immer ein gültiges Ende erreicht. Es ist wie ein GPS, das nur Routen anzeigt, die garantiert rechtzeitig am Ziel ankommen.

3. Die „schlaue“ Karte: Wahrscheinlichkeit hinzufügen (P-GCD)

Die „Globale Karte“ (GCD) ist großartig darin, Sackgassen zu vermeiden, behandelt aber alle gültigen Pfade als gleichwertig. Sie weiß nicht, welchen Pfad der Geschichtenerzähler bevorzugt oder welcher eher ein guter Teil der Geschichte wäre.

Die Analogie: Stellen Sie sich vor, der Geschichtenerzähler hat eine bevorzugte Art zu gehen. Die einfache Karte sagt nur: „Dieser Pfad ist gültig.“ Die neue Probabilistic GCD (P-GCD) sagt: „Dieser Pfad ist gültig, und es ist auch der Pfad, den der Geschichtenerzähler am wahrscheinlichsten genießen wird.“
Wie es funktioniert: Die Autoren kombinieren die „Globale Karte“ (die Regeln) mit einem „Gedächtnismodell“ (einer vereinfachten Version des Gehirns des Geschichtenerzählers). Sie multiplizieren diese beiden Werte miteinander.
Das Ergebnis: Der Führer blockiert nun nicht mehr nur schlechte Pfade; er lenkt den Geschichtenerzähler sanft zu den Pfaden, die sowohl gültig als auch qualitativ hochwertig sind. Dies macht den Prozess des Geschichtenerzährens viel effizienter.

4. Das „Partikel“-Rennen (SMC)

Um diese Methoden zu testen, verwenden die Forscher eine Technik namens Sequential Monte Carlo (SMC).

Die Analogie: Stellen Sie sich vor, Sie versuchen, den besten Weg durch einen nebligen Wald zu finden. Anstatt eine Person zu schicken, senden Sie einen Schwarm von 100 „Partikeln“ (Entdeckern) aus.
Die alte Art: Mit dem kurzsichtigen Führer müssen Sie Tausende von Entdeckern ausschicken, da viele von ihnen sich verlaufen oder vor dem Ziel in Sackgassen geraten.
Die neue Art: Mit der „Globalen Karte“ und der „Smarten Karte“ bleiben die Entdecker auf dem richtigen Kurs. Sie benötigen weit weniger Entdeker, um den perfekten Pfad zu finden, weil der Führer so viel besser darin ist, schlechte Optionen frühzeitig herauszufiltern.

5. Der „Formwandler“-Trick (Tensorisierung)

Einer der technischen Durchbrüche des Papers ist die Handhabung der „Karte“.

Das Problem: Komplexe Regeln (wie JSON-Schemas) können Karten mit Millionen von Pfaden erzeugen. Normalerweise werden Computer überfordert, wenn sie versuchen, diese Karten auf einem Standardprozessor darzustellen.
Die Lösung: Die Autoren haben diese komplexen Karten in mathematische Blöcke (Tensoren) verwandelt, die perfekt auf moderne Grafikkarten (GPUs) passen.
Die Analogie: Es ist, als würde man einen riesigen, unordentlichen Stapel Papierkarten nehmen und sie zu einem kompakten, Hochgeschwindigkeits-Digitalchip falten, den ein Supercomputer sofort lesen kann. Dies ermöglicht es, die „Globale Karte“ im Bruchteil einer Sekunde zu berechnen, selbst bei sehr komplexen Regeln.

Zusammenfassung der Ergebnisse

Das Paper hat dies an drei realen Aufgaben getestet:

Function Calling: Sicherstellen, dass eine KI Computerfunktionen im richtigen Format aufruft (wie JSON).
Keyword Generation: Sicherstellen, dass eine Geschichte bestimmte Wörter enthält.
SQL Generation: Das Schreiben von Datenbankabfragen, die syntaktisch korrekt sind.

Das Urteil:

Zuverlässigkeit: Die neue Methode garantiert, dass die Geschichte innerhalb des Wortlimits korrekt endet, während die alte Methode oft am Zielstrich scheiterte.
Effizienz: Um die gleiche Qualität der Ergebnisse zu erzielen, benötigte die neue Methode signifikant weniger „Entdecker“ (Partikel) als die alte Methode.
Geschwindigkeit: Obwohl die „Smarte Karte“ (P-GCD) etwas mehr Rechenleistung benötigt, ist sie dennoch praktikabel schnell, und die „Globale Karte“ (GCD) ist fast so schnell wie die alte Methode.

Kurz gesagt: Das Paper gibt der KI eine „Globale Karte“ und einen „Smarten Stoß“, damit sie strengen Regeln folgen kann, ohne sich zu verlaufen, Zeit zu verschwenden oder fehlerhaften Code zu produzieren.

Technisches Resümee: Minderung von Bias durch traktierbare Vorschläge bei lokal eingeschränktem Dekodieren

Problemstellung

Große Sprachmodelle (LLMs) scheitern oft daran, Ausgaben zu generieren, die strikt logischen oder strukturellen Beschränkungen folgen, wie etwa JSON-Schemata, gültige SQL-Abfragen oder spezifische Function-Calling-Formate. Obwohl Instruction Tuning und Preference Optimization die allgemeine Ausrichtung verbessert haben, bleiben sie unzuverlässig bei der Durchsetzung von „harten“ Constraints.

Bestehende Ansätze stehen vor zwei primären Einschränkungen:

Rejection Sampling: Obwohl erwartungsneutral, ist es aufgrund extrem niedriger Akzeptanzraten für komplexe Constraints rechnerisch unpraktikabel.
Locally Constrained Decoding (LCD): Dieser Standardansatz maskiert Token, die die Beschränkung im jeweiligen Schritt unmittelbar verletzen. Er leidet jedoch unter zwei kritischen Mängeln:
- Bias: Er verzerrt die zugrunde liegende Verteilung des Modells, indem er Token myopisch maskiert, ohne zukünftige Gültigkeit zu berücksichtigen, was zu einem Sampling-Bias führt.
- Keine Terminierungsgarantie: LCD gewährleistet nur lokale Gültigkeit. Eine Sequenz kann lokal unendlich lange gültig bleiben (z. B. eine nicht geschlossene Klammer in JSON), aber die Beschränkung innerhalb eines festen Token-Budgets $n$ nicht erfüllen.

Um diese Probleme anzugehen, wurde der Sequential Monte Carlo (SMC)-Framework vorgeschlagen, der LCD als Vorschlagsverteilung nutzt und Partikel umgewichtet, um zur Zielverteilung zu konvergieren. Die Konvergenzrate von SMC wird jedoch durch die Qualität des Vorschlags begrenzt; LCD ist ein schwacher Vorschlag, da es keine probabilistischen Informationen über zukünftige gültige Vervollständigungen besitzt und die Einhaltung der Beschränkung innerhalb eines endlichen Budgets nicht garantiert.

Methodik

Die Autoren schlagen einen generischen Ansatz vor, um traktierbare Vorschläge und Potenzialfunktionen für das SMC-Sampling aus der eingeschränkten Verteilung $p_{lm}(\cdot \mid C)$ zu konstruieren. Die Kerninnovation besteht darin, Constraints als endliche Automaten darzustellen und Tensoroperationen für eine effiziente GPU-Ausführung zu nutzen.

1. Globally Constrained Decoding (GCD)

GCD verbessert LCD, indem es sicherstellt, dass jedes generierte Token zu einer gültigen Vervollständigung innerhalb des verbleibenden Token-Budgets $n$ führen kann.

Tensorisierte endliche Automaten: Als endliche Automaten (FA) kodierte Constraints – speziell Nichtdeterministische Endliche Automaten (NFA) und Deterministische Endliche Automaten (DFA) – werden in tensorisierte Repräsentationen (Übergangsmatrizen $T_{out}, T_{in}$ und Emissionsmatrix $B_f$ ) kompiliert. Dies ermöglicht eine effiziente Ausführung auf GPUs.
Forward-Backward-Inferenz:
- Forward-Prozess: Berechnet die Menge der FA-Zustände, die nach Beobachtung des Präfixes $x_{1:t-1}$ erreichbar sind.
- Backward-Prozess: Berechnet, ob ein Zustand in genau $n-t$ Schritten einen akzeptierenden Zustand erreichen kann.
Globale Maskierung: Ein Token wird nur zugelassen, wenn es zu einem Zustand führt, der eine gültige Fortsetzung innerhalb des verbleibenden Budgets ermöglicht. Dies garantiert, dass jede unter GCD generierte Sequenz der Länge $n$ die Beschränkung $C$ erfüllt.

2. Probabilistic Globally Constrained Decoding (P-GCD)

Während GCD die Einhaltung der Beschränkung garantiert, ist seine Maske binär (gültig/ungültig) und ignoriert die Wahrscheinlichkeit gültiger Vervollständigungen unter dem LLM. P-GCD adressiert dies durch die Integration probabilistischer Informationen.

HMM-Destillation: Die Verteilung des LLM wird durch ein Hidden Markov Model (HMM) approximiert, basierend auf vorangegangener Arbeit (Zhang et al., 2023).
Schaltkreis-Multiplikation (Circuit Multiplication): Der tensorisierte FA (betrachtet als unnormalisiertes HMM über Kanten) wird unter Verwendung von Circuit-Multiplikationsalgorithmen mit dem destillierten HMM multipliziert. Dies nutzt die gemeinsame algebraische Struktur von FAs und HMMs aus.
Produktverteilung: Die resultierende Produktverteilung $p_{prod}$ erfasst sowohl die harten logischen Constraints des FA als auch die probabilistischen Präferenzen des LLMs.
Vorschlag und Potenzial:
- Vorschlag ( $q_{pgcd}$ ): Gewichtet die LM-Verteilung in jedem Schritt unter Verwendung der eingeschränkten Next-Token-Wahrscheinlichkeit abgeleitet aus $p_{prod}$ um.
- Potenzial ( $\phi_{pgcd}$ ): Gewichtet Partikel in SMC durch das Produkt der Präfix-Wahrscheinlichkeit des LM und der Look-ahead-Schätzung des HMM bezüglich der Constraint-Erfüllung.

3. Effiziente Implementierung

Die Autoren nutzen Tensor-Netzwerk-Operationen (speziell die Kronecker-vec-Identität), um die explizite Materialisierung großer Kronecker-Produktmatrizen zu vermeiden. Dies reduziert die Rechenkosten der Übergangsschritte von $O((HE)^2)$ auf $O(H^2E + HE^2)$ , wobei $H$ die HMM-verborgene Größe und $E$ die Anzahl der FA-Kanten ist, was eine effiziente autoregressive Generierung ermöglicht.

Kernbeiträge

GCD- und P-GCD-Frameworks: Die Einführung von Globally Constrained Decoding und Probabilistic GCD, die traktierbare Vorschläge und Potenziale für SMC bereitstellen, welche die Einhaltung der Beschränkung innerhalb eines Token-Budgets garantieren.
Tensorisierte Automaten auf GPUs: Der erste Vorschlag, endliche Automaten (einschließlich NFAs) für eine effiziente GPU-native Inferenz zu tensorisieren, wodurch die CPU-gebundenen Limitationen bestehender Frameworks wie Outlines und XGrammar überwunden werden.
NFA-Unterstützung: Nachweis, dass NFAs für komplexe Constraints (z. B. Function Calling mit variablen Parametern) exponentiell kompakter als DFAs sein können, was den Ansatz skalierbar für reale agentische Anwendungen macht, bei denen die DFA-Konstruktion zu Speicherüberläufen (OOM) führen könnte.
Integration mit SMC: Aufzeigen, dass (P-)GCD die SMC-Konvergenz im Vergleich zu LCD-basierten Vorschlägen signifikant beschleunigt und weit weniger Partikel benötigt, um die Zielverteilung zu erreichen.

Experimentelle Ergebnisse

Die Autoren evaluierten (P-)GCD auf drei Benchmarks: xLAM (Function Calling), CommonGen (Keyword-basierte Generierung) und Spider (Text-to-SQL).

Function Calling (xLAM):
- (P-)GCD erreichte eine wesentlich höhere Genauigkeit als LCD bei gleicher Partikelanzahl.
- P-GCD konvergierte schneller zur Grundwahrheitsverteilung (Rejection Sampling) als GCD, was den Nutzen probabilistischer Informationen unterstreicht.
- Constraint-Erfüllung: GCD und P-GCD erreichten eine 100%ige Rate der Constraint-Erfüllung über alle Partikel-Budgets hinweg, während LCD selbst bei moderaten Budgets (z. B. ~95% für JSON) scheiterte.
- Effizienz: LCD und GCD verursachten einen moderaten Overhead (1,08× und 1,10× Verlangsamung). P-GCD war langsamer (3,11× bis 10,2×) aufgrund der HMM-Berechnungen, blieb jedoch praktikabel.
Keyword-Generierung (CommonGen): Die Verwendung von P-GCD sowohl als Vorschlag als auch als Potenzial verbesserte die BLEU-Scores und die Konvergenzgeschwindigkeit signifikant gegenüber LCD.
Text-to-SQL (Spider): GCD und P-GCD verbesserten die Ausführungsgenauigkeit gegenüber LCD über verschiedene Partikel-Budgets hinweg, insbesondere bei moderaten Werten.
NFA vs. DFA: Experimente bestätigten, dass NFAs für komplexe Schemata (z. B. variabel lange Funktionsparameter) linear in ihrer Größe wachsen, während DFAs exponentiell wachsen. Für die Spider-SQL-Grammatik führte die DFA-Konstruktion auf Token-Ebene zu Out-of-Memory (OOM) Fehlern, während der NFA handhabbar blieb (~32k Zustände).

Bedeutung und Behauptungen

Das Paper behauptet, dass lokal eingeschränktes Dekodieren einen erheblichen Sampling-Bias einführt und die Einhaltung von Constraints innerhalb endlicher Token-Budgets nicht garantiert. Durch den Vorschlag von (P-)GCD bieten die Autoren eine Lösung, die:

Validität garantiert: Sicherstellt, dass jede generierte Sequenz der Länge $n$ die Beschränkung erfüllt, wodurch die Ausnahmefälle von LCD eliminiert werden.
Bias reduziert: Durch die Einbeziehung probabilistischer Informationen (via P-GCD) und globalem Lookahead approximieren die Vorschläge die Ziel-bedingte Verteilung besser.
Effizienz verbessert: Im SMC-Framework konvergiert (P-)GCD mit signifikant weniger Partikeln als LCD-basierte Ansätze zur Zielverteilung, was die Rechenkosten für hochwertige eingeschränkte Generierung reduziert.

Die Arbeit positioniert sich als grundlegender Schritt hin zu einer zuverlässigen, constraint-erfüllenden Generierung für LLMs in Anwendungen, die eine strikte strukturelle Adhärenz erfordern, wie etwa Function Calling und Code-Generierung, indem sie logische Constraints (via Automaten) und probabilistische Modellierung (via HMMs) auf GPU-effiziente Weise vereint.