Draft-Conditioned Constrained Decoding for Structured Generation in LLMs

Dit paper introduceert Draft-Conditioned Constrained Decoding (DCCD), een trainingsvrije methode die de semantische planning en structurele validatie ontkoppelt om de nauwkeurigheid van gestructureerde generatie in taalmodellen aanzienlijk te verbeteren zonder de modelgrootte te vergroten.

De kern

Het Probleem: De Strikte Architect en de Creatieve Bouwer

Stel je voor dat je een creatieve bouwer (een Large Language Model of LLM) hebt die fantastische verhalen kan vertellen en moeilijke wiskundepuzzels kan oplossen. Maar je hebt een strikte architect nodig die zorgt dat het eindresultaat precies voldoet aan een bouwplan, bijvoorbeeld een strak JSON-bestand (een soort digitale lijst met haakjes en komma's) of een exacte code.

In het verleden hadden we twee manieren om dit te doen:

1. De "Zeg het maar" methode: Je zegt tegen de bouwer: "Zorg dat je antwoord in een JSON-bestand staat."
   • Resultaat: De bouwer probeert het, maar maakt vaak fouten. Misschien mist hij een haakje, of de zin loopt niet goed. Het resultaat is onbruikbaar voor de computer.
2. De "Strenge Architect" methode (Constrained Decoding): Je laat een strenge architect meekijken. Zodra de bouwer een woord wil zeggen dat niet in het bouwplan past, stopt de architect hem en zegt: "Nee, dat mag niet! Probeer een ander woord."
   • Resultaat: Het eindresultaat is altijd perfect in de juiste vorm (geen fouten in de haakjes). Maar er zit een groot nadeel aan: omdat de architect de bouwer zo vaak onderbreekt, raakt de bouwer in paniek. Hij vergeet zijn eigen logica. Hij zegt misschien iets als "Het antwoord is 27" in plaats van "14", alleen maar omdat "27" makkelijker in te passen viel in het bouwplan op dat specifieke moment. De vorm is perfect, maar de inhoud is fout.

De Oplossing: Eerst Schetsen, Dan Bouwen (DCCD)

De auteurs van dit paper, Avinash Reddy en zijn team, hebben een slimme nieuwe methode bedacht die ze Draft-Conditioned Constrained Decoding (DCCD) noemen. Laten we het vergelijken met het tekenen van een huis.

De oude methode (Strenge Architect):
Je probeert direct het definitieve huis te bouwen met bakstenen, terwijl je tegelijkertijd een streng bouwvoorschrift volgt. Als je een baksteen op de verkeerde plek zet, moet je hem eruit halen en een andere proberen. Hierdoor raak je de visie van het hele huis uit het oog en bouw je een raar, maar wel "voorschrift-compliant" huis.

De nieuwe methode (DCCD):
Deze methode splitst het werk op in twee stappen:

1. Stap 1: De Schets (De Draft).
   Laat de creatieve bouwer eerst vrijuit werken. Hij mag alles zeggen wat hij wil, zonder enige beperking. Hij tekent een ruwe schets van het huis, lost de wiskundepuzzel op, en bedenkt het perfecte antwoord. Omdat hij niet wordt gestoord door de strenge architect, is zijn idee helder en correct.

   • Vergelijking: Een schetsmaker tekent eerst het hele huis op papier, inclusief de details, zonder zich zorgen te maken over de exacte afmetingen van de ramen.

2. Stap 2: De Vertaling (Constrained Decoding).
   Nu pas komt de strenge architect. Maar deze keer kijkt hij niet naar een leeg vel papier, maar naar de schets van stap 1. Hij vertaalt de schets naar het strikte bouwplan. Omdat de schets al het juiste antwoord bevat, is het voor de architect veel makkelijker om de juiste haakjes en komma's te plaatsen. Hij hoeft de bouwer niet meer te forceren om iets te zeggen wat hij niet bedoelde.

   • Vergelijking: De architect neemt de schets en maakt er een technisch, perfect meetbaar bouwplan van. Omdat de schets al klopt, is het plan ook correct.

Waarom werkt dit zo goed?

Het paper legt uit dat het oude probleem ontstond omdat de computer (het model) soms een heel klein kansje had om het juiste woord te kiezen terwijl hij al in de strenge vorm zat. Dit noemen ze "lage waarschijnlijkheid". Het was alsof je probeert een auto te sturen terwijl iemand je het stuur telkens een beetje naar links duwt; je raakt de weg kwijt.

Met de nieuwe methode (DCCD):

• De "schets" zorgt ervoor dat de computer al weet wat het antwoord is.
• Hierdoor is de kans dat het juiste woord past in het bouwplan veel groter.
• De strenge architect hoeft niet meer zo hard te duwen, waardoor de boodschap niet meer wordt vervormd.

De Resultaten in het Kort

• Beter voor kleine modellen: Zelfs kleine, snelle computermodellen (die normaal gesproken minder slim zijn) kunnen met deze methode net zo goed presteren als veel grotere, duurdere modellen. Het is alsof je een slimme assistent krijgt die je helpt je werk te structureren.
• Minder fouten: Op tests zoals wiskundepuzzels (GSM8K) en logica (FOLIO) zagen ze enorme verbeteringen. Soms verdubbelde het aantal juiste antwoorden.
• Efficiënter: Je hoeft geen nieuwe modellen te trainen. Het is een slimme manier om bestaande modellen slimmer te laten werken zonder extra kosten.

Kortom: In plaats van een kunstenaar te dwingen om direct een perfect geformatteerd document te schrijven (wat zijn creativiteit doodt), laat je hem eerst een ruwe schets maken en laat je een editor die schets pas in het juiste formaat gieten. Het resultaat is een tekst die zowel creatief en correct is als perfect in de juiste vorm.

Technische samenvatting

1. Probleemstelling

Grote Taalmodellen (LLMs) worden steeds vaker ingezet voor het genereren van uitvoerbare outputs, zoals JSON-objecten, API-calls en SQL-query's. In deze scenario's is syntactische validiteit niet onderhandelbaar; zelfs één syntaxfout kan de uitvoering laten mislukken.

De huidige standaardoplossing is Constraint Decoding (CD). Hierbij worden ongeldige tokens tijdens het generatieproces gemaskeerd en wordt de kansverdeling genormaliseerd. Hoewel dit garandeert dat de output syntactisch correct is, introduceert het een significant probleem:

• Semantische vervorming: CD is geen passief filter; het verandert de kansverdeling van het model bij elk token. Als het model een lage waarschijnlijkheid toekent aan geldige vervolgtokens (bijvoorbeeld omdat het model liever in vrije tekst redeneert dan in een strak JSON-formaat), leidt de herhaalde normalisatie tot een cumulatieve "projectiebelasting" (projection tax).
• Trajectbias: Het decoderingstraject wordt systematisch geduwd naar voorvoegsels die makkelijker geldig zijn te houden, zelfs als dit leidt tot semantisch onjuiste oplossingen. Dit resulteert in outputs die perfect gestructureerd zijn, maar inhoudelijk fout.

2. Methodologie: Draft-Conditioned Constrained Decoding (DCCD)

De auteurs introduceren DCCD, een trainingsvrije, tweestaps inferentieprocedure die semantische planning loskoppelt van structurele afdwinging. Het idee is gebaseerd op de observatie dat de "haalbare massa" (feasible mass, $\alpha$) van het model context-afhankelijk is.

Het algoritme bestaat uit twee fasen:

1. Stap 1: Onbeperkte Draft-generatie (Semantische Planning)

   • Een model (de draft model) genereert een onbeperkte draft $y$ op basis van de prompt $x$.
   • Deze draft bevat de semantische planning, redenering of het conceptuele antwoord, zonder rekening te houden met de harde structuurbeperkingen (zoals JSON-schemas).
   • Doel: Het model kan vrij redeneren en de juiste inhoud genereren.

2. Stap 2: Draft-geconditioneerde Constraint Decoding (Structurele Afdwinging)

   • De definitieve gestructureerde output $z$ wordt gegenereerd met behulp van constraint decoding, maar nu geconditioneerd op de draft $(x, y)$.
   • De context voor het model bevat nu zowel de prompt als de gegenereerde draft.
   • Kernmechanisme: Door de draft toe te voegen, verschuift de kansverdeling van het model. Tokens die nodig zijn voor de structuur (zoals accolades, komma's, veldnamen) krijgen een veel hogere waarschijnlijkheid omdat ze nu consistent zijn met de reeds gegenereerde inhoud.
   • Dit verhoogt de haalbare massa ($\tilde{\alpha}$) aanzienlijk, waardoor de normalisatiestap minder verstorend is en de "projectiebelasting" wordt verminderd.
   • De output wordt gegarandeerd geldig door de standaard masking en renormalisatie, maar nu op een verdeling die semantisch al voorbereid is.

Optimalisatie (Best-of-K):
Het algoritme kan meerdere drafts genereren ($K > 1$). De beste draft wordt geselecteerd op basis van de cumulatieve log-haalbare massa die tijdens de tweede stap wordt behaald, wat een maatstaf is voor de hoeveelheid door constraints veroorzaakte vervorming.

3. Belangrijkste Bijdragen

• Theoretisch Inzicht (KL-projectie): De auteurs analyseren CD vanuit een KL-projectie-perspectief. Ze tonen aan dat de vervorming wordt bepaald door de feasible mass. Als deze laag is, is de KL-divergentie tussen het originele model en de gedwongen verdeling groot, wat leidt tot een cumulatieve bias.
• DCCD Algoritme: Een nieuwe, trainingsvrije methode die de "draft-then-constrain" strategie implementeert. Dit verhoogt de haalbare massa voordat de harde constraints worden toegepast, zonder de validiteitsgaranties op te geven.
• Parameter-efficiëntie: DCCD maakt het mogelijk om een combinatie van kleinere modellen te gebruiken (bijv. een klein model voor de draft en een ander voor de structuur) die presteren als een veel groter enkel model, wat kostenbesparend is.

4. Resultaten

De methode is getest op diverse benchmarks (GSM8K, MATH500, GSM-Symbolic, FOLIO) met modellen variërend van 1B tot 14B parameters.

• Verbeterde Nauwkeurigheid: DCCD verbetert de "strict structured accuracy" (correcte inhoud én geldige structuur) aanzienlijk.
  • Op GSM8K met een 1B-model steeg de nauwkeurigheid van 15,2% naar 39,0% (+24 procentpunten) ten opzichte van standaard constraint decoding.
  • Op GSM8K met een 1,5B-model steeg de nauwkeurigheid van 49,36% naar 73,92%.
• Parameter-efficiëntie: Een combinatie van een 1,5B en een 3B model (via DCCD) presteerde op MATH500 efficiënter (nauwkeurigheid per parameter) dan een enkel 8B model met standaard constraint decoding.
• Test-time Scaling: DCCD profiteert meer van extra rekenkracht tijdens de inferentie (door het genereren van meerdere drafts) dan standaard CD. De prestatieverbetering blijft groter naarmate het aantal samples ($n$) toeneemt.
• Zelfvertrouwen: DCCD genereert antwoorden met een significant hoger zelfvertrouwen (gemiddelde confidence score van 0,527 vs 0,393 bij CD), wat correleert met de hogere nauwkeurigheid.

5. Betekenis en Conclusie

Dit paper biedt een fundamentele oplossing voor het klassieke compromis tussen kwaliteit (semantische juistheid) en validiteit (syntactische correctheid) bij LLMs.

• Decoupling: De kernboodschap is dat het scheiden van "redeneren" (draft) en "formatteren" (constraint) de beste route is voor betrouwbare gestructureerde generatie.
• Toepasbaarheid: Omdat het trainingsvrij is, kan DCCD direct worden toegepast op bestaande LLMs zonder fine-tuning.
• Impact: Het maakt LLMs betrouwbaarder voor kritieke toepassingen zoals tool-calling, API-integratie en data-extractie, waarbij fouten in de structuur onacceptabel zijn. Het stelt ook kleinere, goedkopere modellen in staat om concurrerende prestaties te leveren ten opzichte van veel grotere modellen.

Samenvattend: DCCD lost het probleem van de "projection tax" op door de context van het model te manipuleren via een vooraf gegenereerde draft, waardoor de modelverdeling minder verstoord wordt tijdens het afdwingen van strakke formaten.