Technische Samenvatting: ALGOBENCH

Probleemstelling

Huidige benchmarks voor grote taalmodellen (LLM's) voor codegeneratie, zoals HumanEval en LiveCodeBench, leveren vaak hoge slaagpercentages op die niet noodzakelijkerwijs een werkelijk algoritmisch redeneervermogen weerspiegelen. Een primaire beperking is data-contaminatie: gevestigde probleemstellingen, editorials en referentie-oplossingen zijn wijdverspreid aanwezig in publieke trainingscorpora. Bijgevolg kunnen modellen hoge scores behalen door het herinneren van gememoriseerde oplossingspatronen in plaats van het afleiden van algoritmen uit restricties. Hoewel recente benchmarks proberen dit te verzachten door nieuwere of moeilijkere problemen te gebruiken (bijv. LiveCodeBench, ProBench, HLCE), blijven deze statisch. Zodra ze zijn uitgebracht, komen hun probleemstellingen en door modellen gegenereerde oplossingen onvermijdelijk in de trainingsdata terecht, waardoor toekomstige modellen kunnen verbeteren via blootstelling in plaats van verbeterd redeneren. Er is behoefte aan een benchmark die dynamisch problemen genereert waarbij het memoriseren van de bronoplossing onvoldoende is, wat modellen dwingt hun algoritmische strategieën aan te passen.

Methodologie

Kernframework: ALGOBENCH

De auteurs stellen ALGOBENCH voor, een framework voor het automatisch construeren van nieuwe algoritmische problemen vanuit bekende competitieve programmeerbronnen. De kernfilosofie is constraint-shifting transformatie: het modificeren van een bronprobleem zodanig dat het originele referentiealgoritme faalt, wat een nieuwe algoritmische aanpak of een andere asymptotische complexiteit noodzakelijk maakt.

1. Transformatie-operators
Het framework maakt gebruik van tien regelgebaseerde transformatie-operators om varianten ($q'$) te genereren van bronproblemen ($q$). Deze omvatten:

• Constraint Scaling (CS): Het vergroten van de inputgrenzen (bijv. $N \le 2000 \to N \le 2 \times 10^5$).
• Static-to-Dynamic (SD): Het omzetten van statische problemen naar dynamische problemen (bijv. het toevoegen van update-operaties).
• Objective Perturbation (OP): Het veranderen van het optimalisatiedoel.
• Greedy-Trap Injection (GT): Het introduceren van restricties die greedy heuristieken ongeldig maken, wat dynamisch programmeren vereist.
• Andere operators omvatten Constraint Coupling, Edge-Case Expansion, Output Requirement Change en bredere transformaties zoals Real-World Wrapping en Graph-Structure Change.

2. Kwaliteitscontroles (Quality Gates)
Om validiteit te garanderen en trivialiteit te voorkomen, moeten gegenereerde problemen vier automatische controles passeren:

• Gate 1 (Old-Solution Rejection): De originele referentieoplossing ($a^*$) moet falen op het nieuwe probleem (produceren van WA, TLE of MLE).
• Gate 2 (New Solution Verification): Een nieuwe referentieoplossing ($\hat{a}^*$) moet worden geverifieerd tegen een brute-force oracle op kleine inputs.
• Gate 3 (Non-Paraphrase): De gegenereerde stelling moet voldoende verschillend zijn van de bron (TextSim $< \tau_{text}$).
• Gate 4 (Complexity Certification): De nieuwe oplossing moet voldoen aan de doelstelling voor tijd- en ruimtecomplexiteit.

3. Deterministische Complexiteitsverificator
Een verifier met drie lagen beoordeelt ingediende oplossingen om onderscheid te maken tussen functionele correctheid en algoritmische optimaliteit:

• Laag 1 (Statische AST-analyse): Parseert code om de tijd-/ruimtecomplexiteit te schatten op basis van loop-nesting, recursie en datastructuren.
• Laag 2 (Algoritme-Tag Verificatie): Controleert op structureel bewijs van verwachte algoritmen (bijv. lazy propagation voor segment trees) en de afwezigheid van verboden algoritmen.
• Laag 3 (Gekalibreerde Runtime Scaling): Draait oplossingen op toenemende inputgroottes om een runtime-model $T(n) = cn^\alpha (\log n)^\gamma$ aan te passen. Oplossingen worden gestraft als de aangepaste exponent de doelstelling met meer dan 0,15 overschrijdt.

Evaluatiemetrieken

Naast de standaard pass@k introduceert ALGOBENCH complexiteitsbewuste metrieken:

• OPTT/OPTS: Ratio's van inzendingen die correct zijn en voldoen aan de doelstelling voor tijd/ruimtecomplexiteit.
• TRAPRATE: Het deel van de incorrecte inzendingen die structureel het bronalgoritme hergebruiken (duidend op de "old-solution trap").
• GAPT (Efficiency Gap): Meet de kloof tussen de aangepaste runtime-exponent en de doel-exponent.
• CONSENS: Meet de prestatiedaling naarmate de omvang van de restricties toeneemt.
• $\Delta_{gen}$: De prestatiedaling van bronproblemen naar gegenereerde varianten.

Belangrijkste Bijdragen

1. Framework: Introductie van ALGOBENCH, een automatische pipeline voor het genereren van traceerbare maar algoritmisch onderscheidende problemen.
2. Transformatie & Validatie: Ontwerp van tien transformatie-operators en een vier-gate kwaliteitscontrolesysteem dat garandeert dat gegenereerde problemen oude oplossingen verwerpen en een nieuwe complexiteit vereisen.
3. Benchmark Dataset: Constructie van een benchmark met 598 geaccepteerde varianten (420 gebruikt in de hoofdexperimenten) afgeleid van 300 bronproblemen (Codeforces, AtCoder, Kattis, LeetCode Hard), compleet met metadata, referentie-oplossingen en brute-force oracles.
4. Metrieken: Voorstel van metrieken (OPTT, OPTS, TRAPRATE, GAPT, CONSENS) die asymptotische geschiktheid evalueren, niet alleen functionele correctheid.
5. Empirische Bevindingen: Evaluatie van zeven LLM's over zes prompting-strategieën, waarbij wordt aangetoond dat de prestaties aanzienlijk afnemen op gegenereerde varianten en dat veel "correcte" oplossingen niet aan de complexiteitseisen voldoen.

Experimentele Resultaten

Prestatiedaling en Adaptatie

• Generalisatiekloof: Modellen vertonen een scherpe daling in prestaties bij de overgang van bronproblemen naar ALGOBENCH-varianten. Oudere modellen daalden van een gemiddelde 85,1% pass@1 op bronnen naar 53,6% op varianten. Zelfs de nieuwste frontier-modellen (GPT-5.4, Claude Opus 4.5) daalden met 33,3%.
• Complexiteitsmismatch: Er bestaat een aanzienlijke kloof tussen pass@k en OPTT. Bijvoorbeeld, GPT-4o behaalde 72,7% pass@5 maar slechts 63,6% OPTT, wat aangeeft dat veel passerende oplossingen suboptimale algoritmen gebruikten.
• Retrieval Risico's: Retrieval-Augmented Generation (RAG) met bronproblemen als context verhoogde vaak de TRAPRATE. Voor Gemini 2.5 Flash verhoogde RAG de trap rate van 3,6% naar 30,0%, wat suggereert dat retrieval modellen verankert aan de originele (nu ongeldige) oplossing.

Foutanalyse

Analyse van 400 mislukte inzendingen onthulde dat fouten voornamelijk algoritmisch zijn in plaats van op implementatieniveau:

• Old-Solution Trap (42,3%): Modellen implementeerden het bronalgoritme, wat de publieke voorbeelden passeerde maar faalde op verborgen trap-tests.
• Te Langzaam (21,8%): Modellen identificeerden de juiste aanpak maar misten noodzakelijke optimalisaties (bijv. falen om over te schakelen van $O(N^2)$ naar $O(N \log N)$).
• Implementatiefouten: Verantwoordelijk voor slechts 9,0% van de fouten.

Gevoeligheid en Contaminatie

• Restrictiegevoeligheid: Prestaties verslechterden scherp naarmate de inputgrenzen toenamen (bijv. $N=10K \to 50K$), precies waar kwadratische oplossingen tijd uit de tijd (time out) gaan.
• Contaminatie-effect: Modellen presteerden aanzienlijk beter op oudere bronproblemen (2020) vergeleken met nieuwere (2024), wat duidt op memorisatie. Echter, deze kloof werd kleiner voor ALGOBENCH-varianten, die consistent moeilijk bleven ongeacht het publicatiejaar van het bronprobleem.

Betekenis en Claims

Het artikel beweert dat ALGOBENCH een onderscheidende capaciteit evalueert van standaard code-benchmarks: het vermogen om algoritmisch redeneren aan te passen aan nieuwe restricties in plaats van te vertrou(ing op gememoriseerde templates.

• Voorbij Functionele Correctheid: De benchmark demonstreert dat hoge slaagpercentages op statische datasets geen asymptotische geschiktheid garanderen. Veel modellen produceren oplossingen die functioneel correct zijn maar algoritmisch inefficiënt.
• Robuustheid tegen Memorisatie: Door automatisch problemen te genereren waarbij de bronoplossing faalt, mitigeert ALGOBENCH het risico op training-data-contaminatie, wat een betrouwbaardere maatstaf biedt voor echt algoritmisch redeneren.
• Diagnostische Waarde: Het framework identificeert specifieke faalmodi (bijv. het onvermogen om over te stappen van Greedy naar DP, of het falen om dynamische updates te verwerken) die verborgen blijven in traditionele benchmarks.

De auteurs concluderen dat huidige LLM's worstelen wanneer vertrouwde templates onvoldoende zijn, en dat toekomstige vooruitgang in algoritmisch redeneren benchmarks vereist die echte adaptatie eisen in plaats van patroonherkenning.