Technische Samenvatting: RISCOSET voor Onzekerheidskwantificatie in LLM-gebaseerde Codegeneratie

Probleemstelling

Grote Taalmodellen (LLM's) worden steeds vaker ingezet voor codegeneratie, maar lijden onder hallucinaties en het genereren van giftige of bevooroordeelde output, wat hun inzetbaarheid in hoog-risico toepassingen beperkt. Hoewel Conformele Predictie (CP) een kader biedt voor onzekerheidskwantificatie met distributie-vrije garanties, is aanpassing aan gestructureerde generatietaken zoals code een uitdaging.

Bestaande benaderingen, zoals PAC (Probably Approximately Correct) predictie-sets voor code (Khakhar et al., 2023), staan voor twee kritieke beperkingen:

1. Monotoniteitsbeperkingen: Ze vertrouwen op een sterke monotoniteitsaanname met betrekking tot risico en de grootte van de predictie-set. Dit beperkt de ruimte van toelaatbare gedeeltelijke programma's, wat vaak leidt tot suboptimale oplossingen die te veel code-nodes verwijderen.
2. Aanname van Eén Label: Ze zijn ontworpen voor classificatie met één label. Codegeneratie is echter inherent een meer-label probleem, waarbij meerdere syntactisch verschillende programma's identieke, correcte semantics kunnen bezitten. Bestaande methoden slagen er niet in om deze veelvoudigheid te accommoderen, wat de ruimte van kandidaten ernstig beperkt.

Methodologie: RISCOSET

De auteurs stellen RISCOSET voor, een methode die risicogestuurde predictie-sets construeert voor LLM-gebaseerde codegeneratie door het probleem te herformuleren als een meer-label classificatietaken en gebruik te maken van het Learn Then Test (LTT) kader (Angelopoulos et al., 2025).

Kerncomponenten

1. Herformulering als Meer-label & Gestructureerd Risico:
   In plaats van monotoniteit af te dwingen, definieert RISCOSET een gestructureerde risicofunctie gebaseerd op semantische correctheid. Voor een gegeven input is het doel een predictie-set te produceren (weergegeven als een gedeeltelijk programma of AST-subboom) die ten minste één correct programma bevat uit een uitgebreide label-set $\tilde{Y}$. Het empirische risico wordt gedefinieerd als het fraction van kalibratie-instanties waarbij de predictie-set faalt om te snijden met de set van correcte programma's.

2. Optimalisatie voor Gedeeltelijke Programma's:
   Om de predictie-set te genereren, lost de methode een optimalisatieprobleem op om knopen te snoeien uit de Abstract Syntax Tree (AST) van het gegenereerde code.

   • Doel: Zoveel mogelijk knopen behouden terwijl ervoor wordt gezorgd dat de totale onzekerheid (negatieve log-probabiliteit) van het overblijvende gedeeltelijke programma een drempel $\lambda$ niet overschrijdt.
   • Beperkingen: De oplossing moet voldoen aan boom-connectiviteit (als een ouder wordt verwijderd, moeten kinderen worden verwijderd) en een limiet op het aantal toelaatbare subboom-verwijderingen ($t_{max}$). Cruciaal is dat deze optimalisatie de strikte monotoniteitsbeperking die in PAC-methoden voorkomt, verwijdert, waardoor een grotere haalbare label-ruimte mogelijk wordt.

3. Meerdere Hypothesetoetsing (LTT):
   RISCOSET maakt gebruik van het LTT-kader om de optimale parameter $\hat{\lambda}$ te selecteren die het risico controleert.

   • Het behandelt de selectie van $\lambda$ als een probleem van meerdere hypothesetoetsing.
   • Voor een set van kandidaat-$\lambda$-waarden worden $p$-waarden berekend op basis van het empirische gestructureerde risico.
   • Met behulp van een algoritme voor het controleren van de Family-Wise Error Rate (FWER) wordt een geldige set parameters $\Lambda_{valid}$ geïdentificeerd die garandeert dat het risico met een hoge zekerheid ($1-\delta$) onder een door de gebruiker gespecificeerde tolerantie $\alpha$ blijft.

4. Selectieve Executiestrategie:
   Omdat codegeneratie een meer-label probleem is, vereist het kalibratieproces het sampling van meerdere kandidaat-programma's en het verifiëren ervan via testgeval-executie, wat rekenkundig duur is. Om dit te mitigeren, introduceert RISCOSET een selectieve executiestrategie:

   • Het maakt gebruik van onzekerheidsscores (bijv. perplexiteit) om te beslissen welke gesamplede programma's test-executie vereisen.
   • Programma's met lage onzekerheid worden zonder executie geaccepteerd als correct, terwijl programma's met hoge onzekerheid worden geverifieerd.
   • Deze strategie maakt gebruik van importance sampling en de ongelijkheid van Hoeffding om een bovengrens voor de fout te schatten, waardoor wordt gegarandeerd dat het label-foutpercentage binnen een gecontroleerde grens $\epsilon$ blijft, terwijl de rekenkosten aanzienlijk worden verlaagd.

Belangrijkste Bijdragen

1. RISCOSET Kader: De eerste toepassing van het LTT-kader op gestructureerde codegeneratie, waarbij de constructie van predictie-sets wordt herformuleerd als een meer-label probleem met zwakkere beperkingen dan PAC-gebaseerde benaderingen.
2. Gestructureerde Risico-optimalisatie: Een nieuwe optimalisatieformulering voor het genereren van gedeeltelijke programma's (AST-subbomen) die de behouden informatie maximaliseert terwijl het voldoet aan risicobeperkende garanties, vrij van restrictieve monotoniteitsaanname.
3. Efficiënte Kalibratie: Een selectieve executiestrategie die de afweging tussen risicobeperking en de rekenkosten van labelverificatie in evenwicht brengt, ondersteund door niet-asymptotische foutgrenzen.
4. Empirische Validatie: Uitgebreide experimenten die de effectiviteit van de methode aantonen over drie LLM's (Deepseek-Coder, Qwen2.5-Coder, Llama3.1) en drie datasets (HumanEval, MBPP, APPS).

Experimentele Resultaten

De auteurs hebben RISCOSET geëvalueerd tegen state-of-the-art baselines, waaronder de PAC predictie-set benadering en een greedige variant.

• Vermindering van Knopenverwijdering: RISCOSET vermindert het aantal verwijderde AST-knopen aanzienlijk in vergelijking met baselines, terwijl hetzelfde niveau van risicobeperking wordt gehandhaafd. Bijvoorbeeld, op de MBPP-dataset met $\alpha=0.15$, verlaagde de methode de codeverwijdering met 24,5% ten opzichte van de beste concurrent.
• Dekkingsgaranties: De geconstrueerde predictie-sets bereikten consistent dekkingpercentages die de doelgrens ($1-\alpha$) overschreden, wat de theoretische risicogestuurde garanties valideert.
• Model Schaalbaarheid: De methode presteerde goed bij zowel op code gespecialiseerde modellen (Qwen2.5-Coder) als algemene modellen (Llama3.1), wat aantoont dat de prestaties verbeteren met krachtigere generatieve modellen.
• Efficiëntie van Selectieve Executie: De selectieve executiestrategie slaagde erin het percentage programma's dat testgeval-executie vereist, te verminderen (bijvoorbeeld het vermijden van executie voor ongeveer 30% van de programma's bij een label-foutpercentage van $\epsilon=0.1$) terwijl de dekking boven de doelgrens bleef.

Betekenis en Beweringen

Het artikel beweert het eerste werk te zijn dat het LTT-kader introduceert in gestructureerde codegeneratietaken. De primaire betekenis ligt in het aanpakken van de beperkingen van bestaande PAC-gebaseerde methoden door:

• De noodzaak van sterke monotoniteitsaanname te elimineren, waardoor de ruimte van kandidaat-programma's wordt uitgebreid en onnodige codeverwijdering wordt verminderd.
• Op een natuurlijke manier de meer-label aard van codegeneratie te accommoderen (meerdere geldige oplossingen voor één taak).
• Rigoureuze statistische garanties te bieden voor de correctheid van de gegenereerde code-sets zonder te vertrouwen op onafhankelijkheidsaanname die in gestructureerde domeinen zoals code falen.

De auteurs concluderen dat hoewel hun focus ligt op codegeneratie, de voorgestelde methode aanpasbaar is aan andere gestructureerde predictieproblemen waar onzekerheidskwantificatie cruciaal is. Ze erkennen de rekenkundige overhead van de kalibratiefase, maar benadrukken dat de selectieve executiestrategie deze kosten effectief mitigeert.