Riepilogo Tecnico: ALGOBENCH

Problematica

Gli attuali benchmark per la generazione di codice tramite modelli linguistici di grandi dimensioni (LLM), come HumanEval e LiveCodeBench, producono spesso tassi di successo elevati che non riflettono necessariamente vere capacità di ragionamento algoritmico. Un limite primario è la contaminazione dei dati: le dichiarazioni dei problemi, gli editoriali e le soluzioni di riferimento stabiliti sono ampiamente disponibili nei corpora di addestramento pubblici. Di conseguenza, i modelli possono ottenere punteggi elevati richiamando schemi di soluzione memorizzati piuttosto che derivare algoritmi dalle costrizioni. Sebbene i benchmark recenti tentino di mitigare questo aspetto utilizzando problemi più nuovi o più difficili (ad esempio, LiveCodeBench, ProBench, HLCE), questi rimangono statici. Una volta rilasciati, le dichiarazioni dei problemi e le soluzioni generate dai modelli entrano inevitabilmente nei dati di addestramento, permettendo ai modelli futuri di migliorare tramite l'esposizione piuttosto che tramite un potenziamento del ragionamento. È necessario un benchmark che generi dinamicamente problemi in cui la memorizzazione della soluzione sorgente sia insufficiente, costringendo i modelli ad adattare le proprie strategie algoritmiche.

Metodologia

Framework Core: ALGOBENCH

Gli autori propongono ALGOBENCH, un framework per la costruzione automatica di nuovi problemi algoritmici partendo da note fonti di programmazione competitiva. La filosofia centrale è la trasformazione per spostamento dei vincoli (constraint-shifting transformation): modificare un problema sorgente in modo che l'algoritmo di riferimento originale fallisca, rendendo necessaria una nuova strategia algoritmica o una diversa complessità asintotica.

1. Operatori di Trasformazione
Il framework impiega dieci operatori di trasformazione basati su regole per generare varianti ($q'$) da problemi sorgente ($q$). Questi includono:

• Scaling dei Vincoli (CS - Constraint Scaling): Aumento dei limiti di input (ad es., $N \le 2000 \to N \le 2 \times 10^5$).
• Da Statico a Dinamico (SD - Static-to-Dynamic): Conversione di problemi statici in problemi dinamici (ad es., aggiunta di operazioni di aggiornamento).
• Perturbazione dell'Obiettivo (OP - Objective Perturbation): Modifica dell'obiettivo di ottimizzazione.
• Iniezione di Trappole Greedy (GT - Greedy-Trap Injection): Introduzione di vincoli che invalidano le euristiche greedy, richiedendo la programmazione dinamica.
• Altri operatori includono il Accoppiamento dei Vincoli (Constraint Coupling), l'Espansione dei Casi Limite (Edge-Case Expansion), il Cambio dei Requisiti di Output e trasformazioni più ampie come l'Avvolgimento nel Mondo Reale (Real-World Wrapping) e il Cambio della Struttura a Grafo (Graph-Structure Change).

2. Gate di Qualità
Per garantire la validità e prevenire la trivialità, i problemi generati devono superare quattro gate automatizzati:

• Gate 1 (Rifiuto della Vecchia Soluzione): La soluzione di riferimento originale ($a^*$) deve fallire sul nuovo problema (producendo WA, TLE o MLE).
• Gate 2 (Verifica della Nuova Soluzione): Una nuova soluzione di riferimento ($\hat{a}^*$) deve essere verificata rispetto a un oracle brute-force su piccoli input.
• Gate 3 (Non-Parafrasi): La dichiarazione generata deve essere sufficientemente distinta dalla sorgente (TextSim $< \tau_{text}$).
• Gate 4 (Certificazione della Complessità): La nuova soluzione deve soddisfare il target di complessità temporale e spaziale.

3. Verificatore Deterministico della Complessità
Un verificatore a tre livelli valuta le soluzioni inviate per distinguere tra correttezza funzionale e ottimalità algoritmica:

• Livello 1 (Analisi Statica AST): Analizza il codice per stimare la complessità temporale/spaziale basandosi su annidamento di cicli, ricorsione e strutture dati.
• Livello 2 (Verifica del Tag Algoritmico): Verifica la presenza di prove strutturali degli algoritmi attesi (ad es., propagazione pigra per segment tree) e l'assenza di quelli proibiti.
• Livello 3 (Scaling del Tempo di Esecuzione Calibrato): Esegue le soluzioni su dimensioni di input crescenti per adattarle a un modello di runtime $T(n) = cn^\alpha (\log n)^\gamma$. Le soluzioni sono penalizzate se l'esponente calcolato supera il target di oltre 0.15.

Metriche di Valutazione

Oltre al classico pass@k, ALGOBENCH introduce metriche consapevoli della complessità:

• OPTT/OPTS: Tassi di sottomissioni che sono corrette e rispettano il target di tempo/spazio.
• TRAPRATE: La frazione di sottomissioni errate che riutilizzano strutturalmente l'algoritmo sorgente (indicando la "trappola della vecchia soluzione").
• GAPT (Gap di Efficienza): Misura il divario tra l'esponente del runtime calcolato e l'esponente target.
• CONSENS: Misura il calo delle prestazioni all'aumentare della magnitudo dei vincoli.
• $\Delta_{gen}$: Il calo delle prestazioni dai problemi sorgente alle varianti generate.

Contributi Chiave

1. Framework: Introduzione di ALGOBENCH, una pipeline automatica per generare problemi tracciabili ma algoritmicamente distinti.
2. Trasformazione e Validazione: Progettazione di dieci operatori di trasformazione e un sistema di controllo qualità a quattro gate che assicura che i problemi generati rifiutino le vecchie soluzioni e richiedano una nuova complessità.
3. Dataset Benchmark: Costruzione di un benchmark con 598 varianti accettate (420 utilizzate negli esperimenti principali) derivate da 300 problemi sorgente (Codeforces, AtCoder, Kattis, LeetCode Hard), completi di metadati, soluzioni di riferimento e oracle brute-force.
4. Metriche: Proposta di metriche (OPTT, OPTS, TRAPRATE, GAPT, CONSENS) che valutano l'idoneità asintotica, non solo la correttezza funzionale.
5. Risultati Empirici: Valutazione di sette LLM attraverso sei strategie di prompting, dimostrando che le prestazioni degradano significativamente sulle varianti generate e che molte soluzioni "corrette" falliscono i requisiti di complessità.

Risultati Sperimentali

Calo delle Prestazioni e Adattamento

• Gap di Generalizzazione: I modelli mostrano un forte declino delle prestazioni passando dai problemi sorgente alle varianti ALGOBENCH. I modelli più vecchi sono scesi da una media dell'85.1% di pass@1 sulle sorgenti al 53.6% sulle varianti. Anche i più recenti modelli di frontiera (GPT-5.4, Claude Opus 4.5) sono scesi del 33.3%.
• Mismatch di Complessità: Esiste un divario significativo tra pass@k e OPTT. Ad esempio, GPT-4o ha ottenuto il 72.7% di pass@5 ma solo il 63.6% di OPTT, indicando che molte soluzioni passate utilizzavano algoritmi subottimali.
• Rischi di Retrieval: L'uso della Generazione Aumentata da Recupero (RAG) con i problemi sorgente come contesto ha spesso aumentato il TRAPRATE. Per Gemini 2.5 Flash, il RAG ha aumentato il tasso di trappola dal 3.6% al 30.0%, suggerendo che il recupero ancora i modelli alla soluzione originale (ora invalida).

Analisi degli Errori

L'analisi di 400 sottomissioni fallite rivela che i fallimenti sono prevalentemente algoritmici piuttosto che a livello di implementazione:

• Trappola della Vecchia Soluzione (42.3%): Il modello implementa l'algoritmo sorgente, superando gli esempi pubblici ma fallendo i test nascosti.
• Troppo Lento (21.8%): Il modello identifica l'approccio corretto ma manca le ottimizzazioni necessarie (ad es., fallendo nel passare da $O(N^2)$ a $O(N \log N)$).
• Bug di Implementazione: Hanno rappresentato solo il 9.0% dei fallimenti.

Sensibilità e Contaminazione

• Sensibilità ai Vincoli: Le prestazioni sono degradate bruscamente all'aumentare dei limiti di input (ad es., $N=10K \to 50K$), proprio dove le soluzioni quadratiche vanno in timeout.
• Effetto Contaminazione: I modelli hanno performato significativamente meglio sui problemi sorgente più vecchi (2020) rispetto a quelli più recenti (2024), suggerendo la memorizzazione. Tuttavia, questo divario si è ridotto per le varianti ALGOBENCH, che sono rimaste costantemente difficili indipendentemente dall'anno di pubblicazione del problema sorgente.

Significato e Rivendicazioni

Il paper sostiene che ALGOBENCH valuta una capacità distinta rispetto ai classici benchmark di codice: la capacità di adattare il ragionamento algoritmico a nuovi vincoli invece di fare affidamento su template memorizzati.

• Oltre la Correttezza Funzionale: Il benchmark dimostra che alti tassi di pass non garantiscono l'idoneità asintotica. Molti modelli producono soluzioni che sono funzionalmente corrette ma algoritmicamente inefficienti.
• Robustezza alla Memorizzazione: Generando automaticamente problemi in cui la soluzione sorgente fallisce, ALGOBENCH mitiga il rischio di contaminazione dei dati di addestramento, fornendo una misura più affidabile del vero ragionamento algoritmico.
• Valore Diagnostico: Il framework identifica specifici modi di fallimento (ad es., l'incapacità di passare da Greedy a DP, o il fallimento nel gestire aggiornamenti dinamici) che sono oscurati nei benchmark tradizionali.

Gli autori concludono che gli attuali LLM faticano quando i template familiari sono insufficienti, e che il progresso futuro nel ragionamento algoritmico richiede benchmark che esigano una vera adattabilità piuttosto che il semplice riconoscimento di pattern.