💬 NLP

Constrained Adaptive Rejection Sampling

Das Paper stellt Constrained Adaptive Rejection Sampling (CARS) vor, eine Methode, welche die Sample-Effizienz der Generierung von Sprachmodellen unter strengen Nebenbedingungen verbessert, indem sie ungültige Fortsetzungen adaptiv über einen Trie beschneidet, wodurch die ursprüngliche Verteilung bewahrt und gleichzeitig die Akzeptanzraten sowie die Diversität im Vergleich zu bestehenden gierigen oder standardmäßigen Rejection-Sampling-Ansätzen verbessert werden.

Ursprüngliche Autoren: Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni

Veröffentlicht 2026-06-04

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni

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 bringen einem sehr talentierten, aber etwas chaotischen Koch (dem Sprachmodell) bei, ein spezifisches, komplexes Gericht (einen gültigen Output) basierend auf einem strengen Rezeptbuch (den Constraints) zu kochen. Der Koch ist großartig darin, zu improvisieren, aber er ignoriert oft die Regeln und fügt Zutaten hinzu, die das Gericht ungenießbar oder strukturell unmöglich machen.

Das Papier stellt eine neue Methode namens CARS (Constrained Adaptive Rejection Sampling) vor, um dieses Problem zu lösen. Um zu verstehen, warum CARS besonders ist, schauen wir uns die zwei alten Wege an, wie dieses Problem gelöst wurde, und warum beide scheitern.

Die alten Wege: Zwei fehlerhafte Strategien

1. Die „Wegwerf-Methode“ (Rejection Sampling)
Stellen Sie sich vor, der Koch bereitet eine vollständige Mahlzeit zu, Sie prüfen das Rezept, und wenn es falsch ist, werfen Sie den ganzen Topf in den Müll und bitten ihn, von vorne zu beginnen.

Das Problem: Wenn das Rezept sehr streng ist (wie eine komplexe Programmiersprache), kocht der Koch vielleicht 999 schlechte Mahlzeiten, bevor er eine richtige bekommt. Sie verschwenden eine enorme Menge an Zeit und Energie, indem Sie Essen wegwerfen.
Das Gute: Die eine Mahlzeit, die tatsächlich serviert wird, ist perfekt und schmeckt genau so, wie der Koch sie beabsichtigt hat.

2. Die „Hovering Hand“-Methode (Greedy Decoding)
Stellen Sie sich vor, Sie stehen dem Koch über die Schulter. Jedes Mal, wenn er nach einer Zutat greift, die gegen die Regeln verstößt, schlagen Sie ihm die Hand weg und zwingen ihn, eine andere zu wählen.

Das Problem: Der Koch hört auf, natürlich zu kochen. Er wird roboterhaft und wählt nur noch „sichere“ Zutaten. Die resultierende Mahlzeit mag zwar essbar sein, aber sie schmeckt nicht mehr nach dem einzigartigen Stil des Kochs; sie ist verzerrt.
Das Gute: Sie erhalten sehr schnell eine gültige Mahlzeit, mit fast keiner Verschwendung.

Die neue Lösung: CARS (Der „kluge Notiznehmer“)

Die Autoren schlagen CARS vor, das das Beste aus beiden Welten kombiniert: Es bewahrt den natürlichen Stil des Kochs (Fidelity), verhindert aber gleichzeitig, dass Zeit mit unmöglichen Gerichten verschwendet wird (Effizienz).

So funktioniert CARS, unter Verwendung der Analogie einer Bibliothek verbotener Pfade:

Anfangen zu kochen: Der Koch beginnt ganz natürlich zu kochen, genau wie bei der „Wegwerf-Methode“.
Der Fehler: Angenommen, der Koch versucht, einen Satz zu bilden, der mit 0++ beginnt (was mathematisch ungültig ist). Das System erkennt dies.
Die kluge Notiz: Anstatt nur diesen einen spezifischen Satz wegzuwerfen, öffnet das System einen Trie (eine spezielle Art von baumartigem Notizbuch). Es schreibt auf: „Jedes Gericht, das mit 0++ beginnt, ist unmöglich.“
Der Welleneffekt: Entscheidend ist, dass das System auch erkennt, dass jedes Gericht, das mit 0+ gefolgt von einem weiteren + beginnt, ebenfalls zum Scheitern verurteilt ist. Es markiert diese gesamten Zweige des Baumes als „Verboten“.
Zukünftiges Kochen: Wenn der Koch das nächste Mal zu kochen beginnt, konsultiert er dieses Notizbuch. Wenn er versucht, eine Zutat zu wählen, die zu einem „verbotenen“ Zweig führt, steuert das System ihn sanft davon ab, bevor er Zeit damit verschwendet, die ganze schlechte Mahlzeit zuzubereiten.
Das Ergebnis: Der Koch kocht nie wieder eine schlechte Mahlzeit. Er kocht schneller, weil er keine Zeit mit Sackgassen verschwendet, aber wenn er kocht, ist es immer noch 100 % sein eigener natürlicher Stil und keine erzwungene Nachahmung.

Warum ist das eine große Sache?

Das Papier hat CARS in drei realen Szenarien getestet, in denen man viele verschiedene gültige Dinge generieren muss:

Program Fuzzing (Fehlersuche): Stellen Sie sich vor, man versucht, eine Software zu manipulieren, indem man Millionen verschiedener Eingaben einspeist. Man benötigt Eingaben, die gültiger Code sind, aber dennoch seltsam genug, um das System zum Absturz zu bringen. CARS fand mehr Bugs (deckte mehr Codezeilen ab) als die alten Methoden, weil es gültige, diverse Eingaben viel schneller generieren konnte, ohne in Sackgassen stecken zu bleiben.
Molekulare Entdeckung (Wirkstoffdesign): Chemiker müssen gültige chemische Strukturen generieren. CARS generierte gültige, diverse Moleküle viel schneller als bisherige Methoden, was enorme Mengen an Rechenleistung einsparte.
Text-to-SQL (Umwandlung von Fragen in Datenbankabfragen): Wenn man eine Frage an eine Datenbank stellt, muss die Antwort eine perfekte SQL-Abfrage sein. CARS lieferte die genauesten Abfragen mit den wenigsten Versuchen.

Das Fazit

Betrachten Sie CARS als einen lernenden Filter.

Alte Methoden verschwendeten entweder Zeit durch das Wegwerfen schlechter Versuche (Rejection Sampling) oder ruinierten die Qualität, indem sie die KI zu starr machten (Greedy Decoding).
CARS lernt aus jedem Fehler. Es erstellt eine Karte der „Sackgassen“, damit die KI niemals wieder in diese läuft. Das bedeutet, Sie erhalten perfekt gültige Ergebnisse, die immer noch wie die natürliche Stimme der KI klingen, aber Sie erhalten sie viel schneller, weil Sie keine Energie mehr für unmögliche Pfade verschwenden.

Das Papier behauptet, dass dies die erste Methode ist, die sowohl exakt (perfekt genau) als auch effizient (schnell) für diese Arten von strengen Aufgaben ist.

Technisches Resümee: Constrained Adaptive Rejection Sampling (CARS)

1. Problemstellung

Sprachmodelle (LMs) werden zunehmend in Anwendungen eingesetzt, die Ausgaben erfordern, welche strikte semantische oder syntaktische Bedingungen erfüllen, wie etwa die Generierung von syntaktisch korrektem Code, die Einhaltung von Datenschemata oder die Erzeugung chemischer Strukturen. Die zentrale Herausforderung bei der beschränkten Generierung besteht darin, zwei konkurrierende Anforderungen in Einklang zu bringen:

Fidelität (Treue): Die Stichproben müssen der exakten bedingten Verteilung des LMs unter Berücksichtigung der Beschränkung ( $P_L$ ) folgen, anstatt einer Approximation.
Effizienz: Die Methode muss die Anzahl der erforderlichen Forward-Passes des LMs minimieren, um gültige Stichproben zu generieren.

Bestehende Ansätze lassen sich in drei Kategorien unterteilen, von denen jede beide Kriterien nicht gleichzeitig erfüllt:

Exakt, aber ineffizient: Standard-Rejection Sampling (RS) erzeugt unverzerrte Stichproben aus der wahren beschränkten Verteilung, verwirft jedoch die überwiegende Mehrheit der Kandidaten in strukturierten Domänen (z. B. Akzeptanzraten von <1 %), was zu prohibitiven Rechenkosten führt.
Effizient, aber verzerrt: Greedy Constrained Decoding (GCD) erzwingt die Gültigkeit durch Maskierung ungültiger Token während der Generierung. Obwohl effizient, verzerrt es nachweislich die bedingte Verteilung des LMs, was häufig die nachgelagerte Leistung verschlechtert und potenziell das Terminieren verhindert.
Asymptotisch exakt, aber instabil: Methoden wie MCMC oder Sequential Monte Carlo (SMC) konvergieren im Grenzwert gegen die korrekte Verteilung, bieten jedoch keine fundierte Abbruchregel. Frühe Stichproben können beliebig verzerrt sein, und die Effizienz hängt stark von der Hyperparameter-Optimierung und der Anzahl der für die Stabilisierung erforderlichen Iterationen ab.

Das Paper argumentiert, dass eine Lücke für einen Algorithmus besteht, der exakt (die wahre Verteilung bewahrend) und amortisiert-effizient (die Effizienz über die Zeit verbessernd, ohne die Fidelität zu opfern) ist, insbesondere in Domänen, die eine diverse Menge gültiger Stichproben erfordern, wie etwa beim Program-Fuzzing oder der molekularen Entdeckung.

2. Methodik: Constrained Adaptive Rejection Sampling (CARS)

CARS ist ein exakter Sampling-Algorithmus, der die Fidelität von Rejection Sampling mit der Effizienz von adaptivem Pruning kombiniert. Es baut auf Adaptive Rejection Sampling (ARS) auf, erweitert dieses jedoch durch die Nutzung der Struktur der Beschränkungen, um nicht nur abgelehnte Stichproben, sondern ganze Familien ungültiger Fortsetzungen zu prunen.

Kernmechanismus

Der Algorithmus pflegt eine Menge von ungültigen Präfixen ( $W$ ), die während des Sampling-Prozesses entdeckt wurden. Er verwendet eine Trie-Datenstruktur, um diese Präfixe zu speichern und die Sampling-Verteilung ( $R_W$ ) dynamisch umzugestalten, um sie zu vermeiden.

Initialisierung: Der Algorithmus beginnt mit einer leeren Menge ungültiger Präfixe ( $W = \emptyset$ ).
Sampling: In jeder Iteration zieht der Algorithmus eine Sequenz aus einer umgewichteten Verteilung $R_W$ $R_{W}$ . Diese Verteilung wird aus der ursprünglichen LM-Verteilung $P$ $P$ abgeleitet, indem sie über Sequenzen normalisiert wird, die kein Präfix in $W$ $W$ erweitern.
- Formal: Für ein Präfix $u$ wird die Wahrscheinlichkeit, es zu einer gültigen Sequenz zu erweitern, als $p_u$ verfolgt. Wenn $u$ ein bekanntes ungültiges Präfix erweitert, ist $p_u = 0$ .
- Die Sampling-Wahrscheinlichkeit für ein Token $a$ gegeben das Präfix $u$ wird angepasst: $R_W(ua | u) = P(ua | u) \cdot \frac{p_{ua}}{p_u}$ .
Adaptives Pruning (Die zentrale Innovation): Wenn eine Stichprobe generiert wird, protokolliert CARS nicht bloß die abgelehnte Zeichenkette (wie bei Standard-ARS). Stattdessen identifiziert es alle Präfixe der generierten Sequenz, die die Beschränkung verletzen, sowie alle deren ungültigen Fortsetzungen.
- Speziell: Wenn eine Sequenz $w$ generiert wird, fügt CARS zur Menge $W$ das kürzeste Präfix $u$ von $w$ hinzu, das nicht in der gültigen Sprache $L$ liegt.
- Entscheidend ist, dass es auch alle Erweiterungen $ua$ (wobei $a$ ein Token ist) hinzufügt, für die gilt: $ua \notin \text{prefix}(L)$ .
- Dieser Prozess bewirkt effektiv, dass die Wahrscheinlichkeitsmasse ganzer Teilbäume ungültiger Fortsetzungen von zukünftigen Zügen "subtrahiert" wird.
Update: Der Trie wird aktualisiert, um die neuen ungültigen Präfixe widerzuspiegeln, und die Wahrscheinlichkeitswerte ( $p_u$ ) werden aufwärts propagiert. Dies stellt sicher, dass zukünftige Stichproben diese ungültigen Pfade niemals erneut besuchen, wodurch die Akzeptanzrate monoton steigt.

Theoretische Eigenschaften

Exaktheit: CARS liefert Stichproben exakt aus der Zielverteilung $P_L$ . Die Umgewichtung stellt sicher, dass die Wahrscheinlichkeitsmasse korrekt unter den gültigen Sequenzen umverteilt wird.
Monotonie: Die Akzeptanzrate verbessert sich monoton, während die Menge $W$ wächst.
Abnehmender Grenznutzen: Die erwartete entfernte Wahrscheinlichkeitsmasse pro Stichprobe ist nicht steigend. Dies legt eine praktische Heuristik nahe: Sob_once der Trie aufhört, signifikante Wahrscheinlichkeitsmasse zu entfernen, kann die Verteilung für das nachfolgende Sampling "eingefroren" werden, ohne signifikanten Effizienzverlust.

3. Zentrale Beiträge

Algorithmus-Design: Einführung von CARS, einem neuen Algorithmus für die beschränkte LM-Generierung, der durch die Nutzung der Beschränkungsstruktur zum Pruning ungültiger Präfix-Fortsetzungen Exaktheit mit praktischer Effizienz erreicht.
Theoretische Garantien: Beweis, dass CARS aus der wahren beschränkten Verteilung sampelt und dass seine adaptiven Updates die Wahrscheinlichkeit, eine gültige Stichprobe zu erhalten, monoton erhöhen.
Empirische Validierung: Demonstration, dass CARS bestehende Methoden in Bezug auf Sampling-Effizienz (weniger LM Forward-Passes pro gültiger Stichprobe) und Stichproben-Diversität über mehrere Domänen hinweg übertrifft.

4. Experimentelle Ergebnisse

Die Autoren evaluierten CARS auf vier Modellen (Llama-3.1-8B/70B, Qwen2.5-7B/14B) in drei unterschiedlichen Domänen:

A. Grammatikbasiertes Fuzzing

Aufgabe: Generierung diverser, gültiger Programmsamen (JSON, SQL, XML), um die Code-Abdeckung (Code Coverage) in Fuzzern zu maximieren.
Ergebnisse: CARS erreichte das Ziel von 100 gültigen Stichproben mit signifikant weniger Generationen als RS, ARS und RSFT. Beispielsweise benötigte CARS bei der XML-Generierung ohne Grammar-Prompts etwa 440 Generationen, verglichen mit >2.000 für RS/ARS (welche das Ziel nicht erreichten).
Auswirkung: Die von CARS generierten Samen führten zu einer höheren Zeilenabdeckung (~~7.985 Zeilen) im Vergleich zu GCD (~~7.115) und MCMC (~7.965), was zeigt, dass die distributionalistische Fidelität zu einer besseren nachgelagerten Leistung führt.

B. Molekulare Synthese

Aufgabe: Generierung gültiger SMILES-Strings für spezifische chemische Klassen (Acrylate, Kettenverlängerer, Isocyanate).
Ergebnisse: CARS benötigte 4,3-mal weniger Stichproben als RS und 1,3-mal weniger als ARS, um 100 gültige Moleküle zu generieren. Es erzielte die höchste Validitäts- und Diversitätsrate unter den exakten Methoden.
Fidelität: Die KL-Divergenz von CARS war 1,5-mal niedriger als die von MCMC und 1,8-mal niedriger als die von AWRS, was auf eine überlegene Adhärenz an die wahre Verteilung hindeutet.

C. Text-to-SQL Generierung

Aufgabe: Generierung von SQL-Abfragen aus natürlichen Sprachfragen (Spider-Datensatz).
Ergebnisse: CARS erreichte die höchste Ausführungsgenauigkeit (0,578) unter allen Methoden. Es benötigte 1,85-mal weniger Stichproben als RS und 1,28-mal weniger als ARS.
Vergleich: Während approximative Methoden wie GCD schneller waren (1,00 Stichproben/Abfrage), litten sie unter geringerer Genauigkeit (0,525). CARS bot das beste Gleichgewicht und übertraf GCD in der Genauigkeit bei nur 1,1-mal so vielen benötigten Stichproben.

5. Bedeutung und Behauptungen

Das Paper behauptet, dass CARS einen neuen Stand der Technik (State-of-the-Art) für das Sampling aus der exakten beschränkten Verteilung eines LMs setzt. Seine Bedeutung liegt in der Lösung des fundamentalen Tradeoffs zwischen Exaktheit und Effizienz:

Im Gegensatz zu RS ist CARS in der Praxis amortisiert-effizient, was es für Aufgaben, die viele diverse Stichproben erfordern, praktikabel macht.
Im Gegensatz zu GCD und anderen approximativen Methoden bewahrt CARS die wahre LM-Verteilung, wodurch sichergestellt wird, dass die nachgelagerte Leistung (z. B. Fuzzing-Abdeckung, chemische Diversität, SQL-Ausführungsgenauigkeit) nicht durch eine Verzerrung der Verteilung beeinträchtigt wird.

Die Autoren merken an, dass CARS am effektivsten ist, wenn Beschränkungen präfix-prüfbar sind und ein hohes Informationspotenzial für das Pruning bieten (z. B. kontextfreie Grammatiken). In Szenarien, in denen der Raum der ungültigen Eingaben aus vielen unabhängigen, niedrig-wahrscheinlichen Teilräumen ohne gemeinsame Präfixe besteht, könnten die Vorteile gegenüber ARS moderater ausfallen, und approximative Methoden könnten eine praktische Alternative bleiben. Für die Mehrheit der strukturierten Generierungsaufgaben bietet CARS jedoch eine fundierte, exakte und effiziente Lösung.