IT
I modelli risolvono meno problemi quando un cambiamento strutturale li rende NP-completi
Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting · arXiv:2610.30103
In parole semplici
Il paper presenta una serie di problemi di programmazione abbinati per verificare se i modelli linguistici riconoscono quando una piccola modifica strutturale rende un problema molto più difficile. Ogni coppia condivide lo stesso contesto, ma una caratteristica fa sì che un problema sia risolvibile in tempo polinomiale e l'altro sia NP-completo.
In media, tutti i 12 modelli valutati hanno ottenuto risultati inferiori sui problemi NP-completi. Concedere più tempo ha aiutato poco: questo suggerisce che molti insuccessi dipendessero da soluzioni errate o inutilizzabili, invece che da soluzioni corrette eseguite troppo lentamente.
La ricerca
Quando un dettaglio strutturale cambia un problema da risolvibile in tempo polinomiale a NP-completo, i modelli linguistici riescono ad adattare le proprie soluzioni alla nuova struttura computazionale?
I test esistenti non abbinavano queste classi mantenendo il contesto dei problemi il più possibile simile, rendendo difficile isolare la questione.
Gli autori presentano P2NPCBench, una serie di problemi di programmazione abbinati per verificare se i modelli seguono un cambiamento strutturale da risolvibile in tempo polinomiale a NP-completo.
Gli autori confrontano problemi abbinati in 12 famiglie. Ogni coppia condivide lo stesso contesto, mentre una caratteristica strutturale cambia la possibilità di risolvere il problema in tempo polinomiale o la sua appartenenza alla classe NP-completa.
Una traccia conta come risolta solo quando una soluzione Python generata supera tutti i casi di test.
Sui 12 modelli, la quota media di tracce risolte è stata del 63.8% per i problemi risolvibili in tempo polinomiale e del 35.4% per quelli NP-completi; ogni modello ha ottenuto in media un risultato inferiore per questi ultimi.
Il confronto tra problemi abbinati sostiene l'esistenza di un divario di prestazioni associato al cambiamento strutturale.
I risultati riguardano 12 famiglie di problemi in inglese, problemi in P e NP-completi e soluzioni in Python 3. Le tracce sono state rese più difficili rispetto a un gruppo fisso di quattro modelli; le versioni correlate compaiono all'interno delle stesse linee evolutive e ogni modello valutato ha prodotto un solo campione greedy. Questi risultati non stabiliscono le prestazioni al di fuori di questo ambito.
Cosa mostrano le prove
- Verificare il cambiamento strutturale
P2NPCBench è un benchmark che verifica se i modelli linguistici tengono conto della struttura computazionale di un problema. Abbina problemi risolvibili in tempo polinomiale e problemi NP-completi formulati nello stesso contesto, distinguendoli tramite una caratteristica strutturale.
La domanda è se i modelli risolvano i problemi in base a quella struttura, invece di affidarsi soprattutto a formulazioni o schemi familiari.
- Creare varianti valide
Per creare tracce più difficili, gli autori hanno usato AgentGAN, un adattamento di un framework esistente di riscrittura multi-agente. Un generatore scrive le varianti delle tracce, un gruppo fisso di modelli per il codice prova a risolverle e un controllo di validità verifica che le riscritture accettate mantengano la risposta e la classe di complessità e restino ben formulate e risolvibili.
Il benchmark comprende 2,114 tracce in 12 famiglie, con versioni correlate raggruppate in linee evolutive.
- Confrontare i risultati abbinati
Gli autori hanno misurato se una soluzione Python generata superasse tutti i casi di test di una traccia. Sui 12 modelli, i punteggi medi sono stati del 63.8% per le tracce risolvibili in tempo polinomiale e del 35.4% per quelle NP-complete; ogni modello ha ottenuto in media un risultato inferiore sul versante NP-completo.
Il confronto usa problemi abbinati e la stessa regola di valutazione, quindi i risultati mostrano un divario coerente associato al cambiamento strutturale.
- Esaminare tempo e formulazione
Limiti di tempo più lunghi hanno cambiato poco i risultati sulle tracce NP-complete: moltiplicare per dieci il limite dichiarato per ogni test, passando da 1 a 10 secondi, ha portato il punteggio medio dal 28.5% al 31.9%.
In un confronto separato, l'accuratezza è calata dalle tracce iniziali alle ultime varianti rese più difficili in entrambe le classi; il calo è stato maggiore per quelle risolvibili in tempo polinomiale. Nel complesso, i risultati suggeriscono che sia il tempo disponibile sia la familiarità della formulazione contino, ma nessuno dei due elimina il divario tra le classi.
- Interpretare gli errori e la trasferibilità
Gli autori hanno anche esaminato cosa accadeva nei casi di test falliti. Per i problemi NP-completi, gli errori di esecuzione erano la categoria più numerosa, seguiti dalle risposte errate e dai timeout.
Questo sostiene la loro interpretazione secondo cui molti insuccessi erano soluzioni errate o non eseguibili, e non soluzioni corrette ma lente. La stessa direzione del divario è emersa per un singolo modello escluso dal processo di hardening, ma il risultato è limitato a quel modello e a questo benchmark.
Dettagli
- Autori del paper originale
- Nurul Labib Sayeedi, Md. Faiyaz Abdullah Sayeedi, Zabir Al Nazi, Mahbub E Sobhani, Shubhashis Roy Dipta
- Inviato ad arXiv
- Licenza
- CC BY 4.0