🤖 machine learning

The Alignment Problem in Constrained Code Generation

Diese Arbeit zeigt auf, dass eine Diskrepanz zwischen Sprachmodellen und unvollständigen beschränkten Decodern die Leistung der Codegenerierung durch die Verzerrung von Wahrscheinlichkeitsverteilungen und das Verursachen von Timeouts erheblich verschlechtern kann, was unbeschränktes Decoding oft effektiver für die funktionale Korrektheit macht.

Ursprüngliche Autoren: Matteo Biagiola, Jahrim Gabriele Cesario, Luca Di Grazia, George Zakhour, Guido Salvaneschi

Veröffentlicht 2026-06-23

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Matteo Biagiola, Jahrim Gabriele Cesario, Luca Di Grazia, George Zakhour, Guido Salvaneschi

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

Die Kernidee: Das Problem des „überfürsorglichen Elternteils“

Stellen Sie sich vor, Sie bringen einem sehr talentierten, aber etwas chaotischen Kind (dem KI-Modell) bei, eine Geschichte (den Code) zu schreiben.

Normalerweise lassen Sie das Kind schreiben, was es möchte. Manchmal macht es Rechtschreibfehler oder verwendet die falsche Grammatik, aber oft bekommt es die Geschichte richtig hin. Dies ist Unconstrained Decoding (ungebremste Dekodierung).

Um die Fehler zu beheben, beschließen Sie, als strenger Editor (der Constrainer) zu fungieren. Sie sagen dem Kind: „Du darfst nur Wörter verwenden, die in diese spezifische Grammatikregel passen. Wenn du versuchst, ein Wort zu schreiben, das die Regel bricht, werde ich dich sofort stoppen und dich zwingen, ein anderes Wort zu wählen.“

Die Arbeit argumentiert, dass dies zwar eine großartige Idee klingt, um Fehler zu vermeiden, aber oft nach hinten losgeht. Wenn Ihre Editierregeln unvollständig sind (das heißt, Sie kennen nicht alle Regeln der Sprache oder Sie blockieren gültige Arten des Schreibens), zwingen Sie das Kind letztlich dazu, auf eine seltsame, unnatürliche Weise zu schreiben, nur um Ihre begrenzten Regeln zu erfüllen. Das Ergebnis? Die Geschichte wird unsinnig, das Kind wird frustriert und hört vorzeitig auf zu schreiben, und die fertige Geschichte ist schlechter, als wenn Sie es einfach frei hätte schreiben lassen.

Die drei Hauptakteure

Die Arbeit identifiziert drei Dinge, die „gut miteinander auskommen“ müssen, damit dies funktioniert:

Das Modell (Das Kind): Die KI, die den Code generiert. Sie hat aus ihren Trainingsdaten gelernt, wie Code normalerweise aussieht.
Das Ziel (Das Ziel): Der perfekte, korrekte Code, den wir tatsächlich wollen (z. B. valides TypeScript).
Der Constrainer (Der Editor): Das Werkzeug, das versucht, die KI dazu zu bringen, Regeln zu befolgen (wie Typen oder Syntax zu prüfen), während sie schreibt.

Das Problem: Der „Editor“ ist oft unvollständig. Er kennt nicht jede gültige Art, Code zu schreiben. Er könnte einen gültigen Satz blockieren, weil er ein bestimmtes Feature noch nicht gelernt hat (wie „Forward References“, bei denen man ein Wort verwendet, bevor man es definiert).

Die „Fehlalignment“-Analogie

Stellen Sie sich das Gehirn der KI wie eine Karte einer Stadt vor, die sie sehr gut kennt.

Das Ziel ist der Bestimmungsort, den Sie erreichen wollen.
Der Constrainer ist eine Reihe von Straßensperren, die Sie aufstellen, um sicherzustellen, dass der Fahrer auf den „korrekten“ Straßen bleibt.

Wenn Ihre Straßensperren perfekt sind, bleibt der Fahrer auf den besten Straßen und kommt sicher an.
Aber wenn Ihre Straßensperren unvollständig sind (Sie haben eine gültige Abkürzung blockiert, weil Sie nicht wussten, dass sie existiert), wird der Fahrer gezwungen, einen Umweg durch einen Sumpf zu nehmen (Bereiche mit geringer Wahrscheinlichkeit). Er könnte im Schlamm stecken bleiben (Timeout), der Benzin ausgehen (Tokens aufgebraucht) oder an einem Ort ankommen, der zwar wie das Ziel aussieht, aber nicht das richtige Haus ist (die Syntax ist korrekt, aber der Code funktioniert nicht).

Was die Forscher herausgefunden haben

Das Team führte Experimente mit mehreren KI-Modellen und zwei Arten von Code (TypeScript und TOML durch. Hier ist, was sie entdeckten:

1. Der „strenge Editor“ macht oft alles schlimmer (RQ0)
Als sie einen Standard-„unvollständigen“ Editor verwendeten (einen, der einigen validen Code blockiert), performte die KI schlechter, als wenn sie frei schreiben durfte.

Das Ergebnis: Die KI generierte Code, der technisch „sicher“ war (keine Syntaxfehler), aber nicht das tat, was verlangt wurde.
Die Analogie: Es ist, als würde man einen Koch zwingen, nur Zutaten aus einer winzigen, unvollständigen Speisekammer zu verwenden. Der Koch erstellt vielleicht ein Gericht, das perfekt aussieht, aber es schmeckt schrecklich, weil er gezwungen war, seltsame Ersatzstoffe zu verwenden.

2. Der „Bias“ (RQ1)
Die Forscher fanden heraus, dass der „unvollständige Editor“ die KI dazu zwingt, Wörter zu wählen, die sie normalerweise niemals wählen würde.

Das Ergebnis: Die KI beginnt, „unwahrscheinlichen“ Code zu generieren. Es ist, als würde man einen Jazzmusiker zwingen, nur Noten aus einer bestimmten Tonleiter zu spielen, die er hasst. Die Musik wird steif und unnatürlich.
Die Konsequenz: Die KI gibt oft ganz auf (Timeout), weil sie keinen Pfad findet, der die unvollständigen Regeln des Editors erfüllt.

3. Kann man das lösen? (RQ2)
Sie versuchten, die KI besser zu „lehren“, die begrenzten Regeln des Editors zu verstehen, indem sie sie feintunten.

Das Ergebnis: Das half ein wenig. Die KI blieb seltener stecken und der Code wurde etwas besser.
Der Haken: Es konnte das Problem nicht vollständig lösen. Die KI kämpfte immer noch gegen die unvollständigen Regeln des Editors an. Es ist, als würde man das Kind lehren, ein besserer Schreiber zu werden, aber es wird immer noch gezwungen, mit einem kaputten Stift zu schreiben.

4. Der „perfekte Editor“ (RQ3)
Schließlich testeten sie, was passiert, wenn der Editor vollständig ist (er kennt jede gültige Regel und blockiert nichts, was tatsächlich korrekt ist).

Das Ergebnis: Wenn der Editor perfekt war, performte die KI viel besser als beim freien Schreiben.
Die Analogie: Wenn Sie dem Kind ein perfektes Set an Regeln geben, das alles abdeckt, kann es ein Meisterwerk schreiben.
Die Überraschung: Die Forscher fanden heraus, dass selbst winzige, fehlende Details in den Regeln (wie das Vergessen eines Leerzeichens vor einem Gleichheitszeichen) die Leistung der KI um bis zu 97 % einbrechen lassen konnten. Die KI reagiert extrem empfindlich auf diese kleinen Lücken.

Das Fazit

Die Arbeit kommt zu dem Schluss, dass Constrained Decoding (das Erzwingen von Regeln während des Schreibens durch eine KI) nur dann eine gute Idee ist, wenn die Regeln perfekt mit dem abgestimmt (aligned) sind, was die KI bereits weiß und was der endgültige Code benötigt.

Wenn die Regeln unvollständig sind, wirken sie wie ein schlechter Filter, der die natürliche Fähigkeit der KI verzerrt und den Code verschlechtert.
Um dies zum Laufen zu bringen, müssen wir entweder die Regeln perfekt vollständig machen oder die KI so umtrainieren, dass sie perfekt zu den unvollständigen Regeln passt.

Kurz gesagt: Setzen Sie keinen halbfertigen Filter auf einen leistungsstarken Motor; er wird einfach das Auto kaputt machen.

Technisches Resümee: Das Alignment-Problem bei der beschränkten Codegenerierung

Problemstellung

Große Sprachmodelle (LLMs) haben beeindruckende Fähigkeiten in der Codegenerierung demonstriert, produzieren jedoch häufig Ausgaben mit Syntax- oder Typfehlern, was zu Kompilierungsfehlern führt. In statisch typisierten Sprachen wie TypeScript sind etwa 94 % der Kompilierfehler auf Verletzungen des Typsystems und nicht auf Syntaxfehler zurückzuführen. Um dies zu mildern, wurde die beschränkte Dekodierung (constrained decoding) als Technik vorgeschlagen, um formale Regeln (z. B. Syntaxgrammatiken, Typsysteme) während der Token-Generierung durchzusetzen, was theoretisch eine strukturelle Gültigkeit garantiert.

Die Autoren beobachten jedoch ein kontraintuitives Phänomen: In vorläufigen Studien übertrifft die unbeschränkte Dekodierung die beschränkte Dekodierung häufig in Bezug auf die funktionale Korrektheit. Das Papier postuliert, dass dieses Scheitern nicht inhärent am Konzept der Beschränkungen liegt, sondern aus einer kritischen Fehlausrichtung (Misalignment) zwischen drei Kernentitäten resultiert:

Die Modellsprache ( $L_M$ ): Die Menge der Programme, die das LLM basierend auf seiner Trainingsverteilung wahrscheinlich generiert.
Die Zielsprache ( $L_T$ ): Die Menge der gültigen Programme gemäß der Spezifikation (z. B. die Regeln des TypeScript-Compilers).
Die beschränkte Sprache ( $L_C$ ): Die Menge der Programme, die vom benutzerdefinierten Constrainer (z. B. einem inkrementellen Parser/Typ-Prüfer) während der Dekodierung zulässt.

Die zentrale These ist, dass die beschränkte Dekodierung dann nachteilig ist, wenn der Constrainer unvollständig ist (gültige Programme in $L_T$ ablehnt) oder unzulänglich (unsound) ist (ungültige Programme zulässt). Ein unvollständiger Constrainer zwingt das Modell in Regionen mit geringer Wahrscheinlichkeit, was zu „Inkomplettheits-Bias“, Textdegeneration und häufigen Timeouts führt, was letztlich die funktionale Korrektheit verringert.

Methodik

Die Autoren schlagen ein Alignment-Framework vor, um die Beziehung zwischen $L_M$ , $L_T$ und $L_C$ zu analysieren. Sie definieren Alignment als die Jaccard-Ähnlichkeit unter diesen drei Mengen. Die Studie ist um drei Forschungsfragen (RQs) strukturiert, um die Kosten der Fehlausrichtung und potenzielle Abhilfemaßnahmen zu untersuchen:

RQ0 (Effektivität): Eine groß angelegte empirische Studie, die die beschränkte mit der unbeschränkten Dekodierung über sechs LLMs (von 2B bis 80B Parametern), zwei Benchmarks (HumanEval und MBPP) und drei Temperatur-Einstellungen vergleicht.
RQ1 (Die Kosten der Fehlausrichtung): Quantifizierung des „Inkomplettheits-Bias“ durch Messung der normalisierten negativen Log-Likelihood (NLL) der generierten Programme. Die Studie analysiert, wie ein unvollständiger Constrainer (speziell ein TypeScript-Typ-Constrainer, dem die Unterstützung für Vorwärtsreferenzen und benutzerdefinierte Typen fehlt) die Verteilung des Modells verzerrt.
RQ2 (Wiederherstellung des Alignments): Evaluierung, ob ein Fine-Tuning des LLM zur Einhaltung der spezifischen Constraints des Constrainers den Bias mildern kann. Die Autoren verwenden Group Relative Policy Optimization (GRPO) mit einer Belohnungsfunktion, die auf dem Bestehen des inkrementellen Typ-Prüfers basiert.
RQ3 (Vollständiges Alignment): Systematische Untersuchung der Auswirkungen der Vollständigkeit unter Verwendung von TOML (einer Sprache mit einer strikten, kontextfreien Grammatik) als Sandbox. Sie vergleichen einen vollständigen syntaktischen Constrainer mit Varianten, denen spezifische Merkmale entfernt wurden (z. B. optionale Leerzeichen, Kommentare, punktierte Schlüssel), um die Sensitivität der Modelle gegenüber unterschiedlichen Graden der Unvollständigkeit zu isolieren.

Kernergebnisse

1. Unbeschränkte Dekodierung übertrifft oft die beschränkte Dekodierung (RQ0)

Über alle Konfigurationen hinweg (HumanEval- und MBPP-Benchmarks) erreichte die unbeschränkte Dekodierung konsistent eine höhere funktionale Korrektheit (FC) als die Typ-beschränkte Dekodierung.

Timeouts: Die beschränkte Dekodierung litt signifikant unter höheren Timeout-Raten (Überschreitung von Token- oder Zeitlimits), insbesondere bei kleineren Modellen und niedrigeren Temperaturen.
Typ-Syntax vs. Funktionalität: Während die beschränkte Dekodierung die Typ-Syntax-Korrektheit (TSC) verbesserte, übertrug sich dies nicht auf eine bessere funktionale Korrektheit. Tatsächlich zwangen die Beschränkungen das Modell oft dazu, syntaktisch korrekten, aber funktional inkorrekten Code zu generieren oder in Generierungsschleifen zu geraten.

2. Fehlausrichtung verursacht distributional Bias (RQ1)

Die Studie bestätigte, dass unvollständige Constrainer LLMs in Regionen mit geringer Wahrscheinlichkeit drängen.

NLL-Analyse: Beschränkte Lösungen wiesen eine signifikant höhere NLL auf (was bedeutet, dass sie unter der natürlichen Verteilung des Modells weniger wahrscheinlich sind) im Vergleich zu unbeschränkten Lösungen.
Mechanismus des Scheiterns: Wenn ein Modell versucht, ein vom Constrainer nicht unterstütztes Feature zu verwenden (z. B. eine Vorwärtsreferenz in TypeScript), lehnt der Constrainer das Token ab. Das Modell wird dann gezwungen, eine Alternative zu wählen, was oft zu einem „Pfad mit geringer Wahrscheinlichkeit“ führt, bei dem der generierte Code semantisch unsinnig wird oder in eine Repetitionsschleife gerät, bis ein Timeout auftritt.

3. Fine-Tuning mildert, aber eliminiert den Bias nicht (RQ2)

Das Fine-Tuning des LLM zur Abstimmung auf die Verteilung des Constrainers (unter Verwendung von GRPO) lieferte gemischte, aber positive Ergebnisse:

Reduzierte Timeouts: Das Fine-Tuning reduzierte die Timeout-Raten um 53–73 % (Token-Limits) und 74–94 % (Zeit-Limits).
Konvergenz: In einigen Fällen (z. B. Gemma-2-2B auf HumanEval) machte das Fine-Tuning die funktionale Korrektheit der beschränkten und unbeschränkten Dekodierung gleichwertig.
Limitierungen: Trotz verbesserter Ausrichtung blieb ein gewisser Inkomplettheits-Bias bestehen. Die beschränkte Dekodierung war in der funktionalen Korrektheit immer noch schlechter als oder nur ebenbürtig zur unbeschränkten Dekodierung, was darauf hindeutet, dass Fine-Tuning allein einen fundamental unvollständigen Constrainer nicht vollständig kompensieren kann.

4. Vollständigkeit ist entscheidend (RQ3)

Unter Verwendung von TOML zeigten die Autoren, dass vollständige Constrainer die unbeschränkte Dekodierung signifikant übertreffen, insbesondere bei kleineren Modellen.

Leistungssteigerungen: Mit einem vollständigen Constrainer verzeichnete das 2B-Modell (Gemma-2-2B) eine Steigerung der Exact-Match-Scores um 53 % im Vergleich zur unbeschränkten Dekodierung.
Sensitivität gegenüber Unvollständigkeit: Das Entfernen spezifischer Merkmale verursachte drastische Leistungseinbußen. Beispielsweise reduzierte das Verbot von optionalen Leerzeichen vor dem Gleichheitszeichen (c-space=) die funktionale Korrektheit des 80B-Modells um 97 %. Dies zeigt, dass Modelle signifikanten semantischen Wert selbst kleinen syntaktischen Konstrukten wie Leerzeichen beimessen.
Feature-Sensitivität: Nicht alle Merkmale sind gleichermaßen kritisch; das Entfernen von Kommentaren oder punktierten Schlüsseln hatte minimale Auswirkungen, während das Entfernen von Optionen für Leerzeichen katastrophal war.

Bedeutung und Beiträge

Das Paper leistet folgende Beiträge zur Fachwelt:

Empirischer Beleg des Scheiterns: Es liefert eine groß angelegte Studie, die zeigt, dass aktuelle Ansätze der beschränkten Dekodierung in der funktionalen Korrektheit konsistent von der unbeschränkten Dekodierung übertroffen werden, was die Annahme infrage stellt, dass Beschränkungen die Codegenerierung automatisch verbessern.
Das Alignment-Framework: Es führt das Konzept des Alignments zwischen Modellsprache, Zielsprache und beschränkter Sprache ein. Dieses Framework erklärt, warum die beschränkte Dekodierung scheitert (Inkomplettheits-Bias) und bietet eine theoretische Basis für die Diagnose dieser Probleme.
Quantitative Erkenntnisse zur Milderung: Es zeigt auf, dass Fine-Tuning zwar die negativen Auswirkungen von Fehlausrichtung reduzieren kann (indem es die Modellverteilung mit dem Constrainer harmonisiert), aber kein Allheilmittel ist. Die effektivste Lösung ist die Sicherstellung der Vollständigkeit des Constrainers.
Design-Richtlinien: Das Paper bietet quantitative Einblicke für das Design von Constrainern und hebt hervor, dass selbst geringfügige syntaktische Einschränkungen (wie Leerzeichen) massive negative Auswirkungen auf die Generierungsqualität haben können.

Fazit

Das Paper kommt zu dem Schluss, dass die beschränkte Dekodierung nur dann vorteilhaft ist, wenn ein striktes Alignment zwischen dem Modell, der Zielsetzung und den Beschränkungen besteht. Ein unvollständiger Constrainer wirkt als Quelle von Bias, die die Verteilung des LLM verzerrt und zu Generierungsfehlern führt. Um formale Garantien ohne Verlust der funktionalen Korrektheit zu erreichen, müssen Praktiker entweder vollständige Constrainer entwerfen oder die Verteilung des Modells durch Fine-Tuning an die Beschränkungen anpassen, wobei sie anerkennen müssen, dass Letzteres die durch Unvollständigkeit verursachte Performance-Lücke möglicherweise nicht vollständig schließen kann.