Technische Samenvatting: Schalen van de Agentic Verifier voor Competitief Programmeren

Probleemstelling

Hoewel Large Language Models (LLM's) sterke capaciteiten hebben getoond in programmasynthese, worstelen ze vaak met het correct oplossen van competitieve programmeerproblemen in een enkele poging. Een veelgebruikte strategie om de nauwkeurigheid te verbeteren is test-time scaling, waarbij meerdere kandidaat-oplossingen worden gesampled en een verifier de beste selecteert.

Bestaande verificatiemethoden kampen met aanzienlijke beperkingen in de context van competitief programmeren:

1. Volledige Generatie van Testgevallen: Het genereren van volledige testgevallen (inputs + grondwaarheid-outputs) is vaak even moeilijk als het oplossen van het oorspronkelijke probleem, wat computationeel duur en onbetrouwbaar is.
2. Alleen-Input Executie: Recente benaderingen genereren alleen geldige test-inputs en selecteren oplossingen op basis van output-overeenkomst (voting). Deze methoden vertrouwen echter doorgaans op random input sampling.
3. Inefficiëntie van Random Sampling: De ruimte van geldige inputs in competitief programmeren is enorm, maar slechts een klein deel is "discriminatief" (d.w.z. in staat om gedragsverschillen tussen correcte en incorrecte oplossingen bloot te leggen). De voorlopige experimenten van het paper laten zien dat het schalen van het aantal willekeurige inputs een afnemende meeropbrengst heeft en er niet in slaagt de prestatiekloof met grondwaarheid-testgevallen te dichten.

Methodologie: Agentic Verifier

De auteurs stellen de Agentic Verifier voor, een LLM-gebaseerde agent die actief redeneert over programmacapaciteiten en zoekt naar hoogst discriminatieve test-inputs die discrepanties tussen kandidaat-oplossingen blootleggen.

Kernmechanisme

In plaats van blind random sampling, gaat de verifier een multi-turn interactie aan met een code-executieomgeving:

1. Taakformulering: Gegeven een probleem $Q$ en een paar kandidaat-oplossingen $(C_a, C_b)$, is het doel van de agent om een input-generator programma $G$ te genereren dat een geldige input $x$ produceert waarvoor geldt dat $Exec(C_a, x) \neq Exec(C_b, x)$.
2. Interactieloop: De agent stelt iteratief inputs voor, voert kandidaat-oplossingen uit, inspecteert feedback (runtime errors, outputs) en verfijnt zijn hypothesen om tegenvoorbeelden te ontdekken.
3. Selectiestrategie: Tijdens inferentie genereert de getrainde verifier gerichte test-inputs voor paren van kandidaat-oplossingen. Deze inputs worden gebruikt in een execution-based voting strategie om de uiteindelijke oplossing te selecteren.

Trainingspipeline

De verifier wordt getraind via een schaalbare driefasige pipeline:

1. Grootschalige Datasynthese: De auteurs construeren een dataset van competitieve programmeerproblemen met gelabelde oplossingen. Voor problemen zonder grondwaarheid-testgevallen synthetiseren zij hoogwaardige testsuites met behulp van een consensus-gebaseerd meerderheidsstemmechanisme over meerdere referentie-oplossingen om de betrouwbaarheid te waarborgen.
2. Rejection Fine-Tuning: Met behruik van een sterk teacher-model (Qwen3-235B) verzamelen zij succesvolle multi-turn interactietrajecten waarbij de agent succesvol onderscheidende inputs genereert. Het basismodel wordt gefinetuned op deze hoogwaardige trajecten, waarbij initiële prompts en feedback worden gemaskeerd om effectieve interactiepatronen te leren.
3. Agentic Reinforcement Learning (RL): De verifier wordt verder geoptimaliseerd met behulp van GRPO (Group Relative Policy Optimization). De beloningsfunctie is spaars en op resultaat gebaseerd:
   • $+1$: Geldige input die de twee oplossingen onderscheidt.
   • $0$: Geldige input die niet onderscheidt (oplossingen komen overeen).
   • $-1$: Ongeldige input of lege generator.
     Het trainingscurriculum geeft prioriteit aan "hard negative" paren waarbij onderscheidende inputs zeldzaam zijn, wat de agent aanmoedigt om gerichte generatiegedragingen te leren.

Belangrijkste Bijdragen

1. Empirische Analyse: Het paper demonstreert empirisch dat random inputgeneratie zeer inefficiënt is voor input-only execution-based verificatie, wat een aanzienlijke prestatiekloof onthult vergeleken met discriminatieve test-inputs.
2. Agentic Verifier: Introductie van een agent die actief hoogst discriminatieve test-inputs genereert via multi-turn interactie, waarmee men verder gaat dan statische of random sampling.
3. Schaalbare Trainingspipeline: Een nieuwe pipeline die datasynthese, rejection fine-tuning en agentic reinforcement learning combineert om de verifier te trainen.
4. Test-Time Scaling: Demonstratie dat de voorgestelde methode continu profiteert van toegenomen test-time computation, en effectief schaalt met zowel het aantal kandidaat-oplossingen als het aantal gegenereerde inputs.

Experimentele Resultaten

De aanpak werd geëvalueerd op vijf competitieve programmeerbenchmarks (USACO, LiveCodeBench, OJBench, ICPC-Eval, en een nieuwe CodeForces benchmark) met behulp van twee policy-modellen (Qwen3-30B en Qwen3-235B).

• Prestatiewinst: De Agentic Verifier presteerde consequent beter dan sterke baselines, inclus_ief random inputgeneratie, model-gegenereerde testgevallen (CodeT, CodeRM) en reward-model-gebaseerde selectie.
  • Behaalde absolute winsten van +10–15% in Best@k nauwkeurigheid ten opzichte van sterke execution-based baselines.
  • Op de OJBench "Hard" subset verbeterde de getrainde 30B verifier de prestaties met +34,1% ten opzichte van de baseline, waarmee het een zero-shot 235B model aanzienlijk versloeg.
• Schaalgedrag: In tegen tegenstelling tot baselines die vroege verzadiging vertoonden, vertoonde de Agentic Verifier duidelijk test-time scaling gedrag, waarbij de prestaties gestaag verbeterden naarmate het aantal test-inputs toenam.
• Zero-Shot vs. Getraind: Zero-shot LLM's boden enige verbetering, maar de taakspecifiek getrainde verifier presteerde aanzienlijk beter dan hen, zelfs wanneer het getrainde model 7x kleiner was dan de zero-shot tegenhanger.

Betekenis en Claims

Het paper claimt dat de effectiviteit van execution-based voting primair wordt bepaald door de discriminatieve kwaliteit van de test-inputs in plaats van door hun loutere hoeveelheid.

Naast het verbeteren van de Best-of-N selectie, benadrukken de auteurs een bredere implicatie: Benchmark testsuites zijn imperfecte verifiers. Vaste testsuites dekken slechts een beperkt deel van de geldige inputruimte, wat leidt tot false positives waarbij incorrecte oplossingen alle benchmark-tests halen. De Agentic Verifier kan deze fouten actief blootleggen door gerichte tegenvoorbeelden te ontdekken. De auteurs positioneren de verifier daarom niet enkel als een reranking tool, maar als een complementair mechanisme voor correctheidscontrole dat de input-dekking kan vergroten en benchmark-geïnduceerde ruis in grootschalige code-evaluatie kan mitigeren.