Un paper pubblicato su arXiv il 9 aprile 2026 da François Pachet (Sorbonne Université) e Pierre Roy (Soundtrap) dimostra con prove formali che la generazione vincolata LLM — far produrre a un modello autoregressivo testo con rime esatte, metro fisso o segmenti mancanti in una sequenza — è NP-hard per la decodifica MAP e #P-hard per il campionamento esatto. In entrambi i casi, si tratta di problemi computazionalmente intrattabili nel caso generale.
Il risultato non riguarda le prestazioni dei modelli linguistici su compiti standard. Riguarda qualcosa di più strutturale: ogni sistema che oggi produce testi con vincoli globali — rima, sillabazione, inpainting musicale o testuale — non sta campionando dalla distribuzione condizionata corretta del modello sottostante. Sta usando un’approssimazione. E in molti casi non si sa quali soluzioni ammissibili vengono escluse, né con quale probabilità vengono prodotte quelle restituite.
Cosa dimostra il paper sulla generazione vincolata LLM
Il problema centrale è il mismatch tra come i modelli autoregressivi generano token — localmente, da sinistra a destra — e come funzionano i vincoli globali, che dipendono dall’intera sequenza completata. Un modello autoregressivo calcola efficientemente le probabilità condizionate del token successivo. Ma trovare la sequenza più probabile che soddisfi un vincolo sull’intera frase — il MAP decoding vincolato — richiede di ottimizzare su uno spazio esponenzialmente grande di completamenti possibili.
Pachet e Roy formalizzano questa intuizione con due teoremi centrali. Il primo (Teorema 1) riduce il problema SAT a un’istanza di MAP decoding per modelli autoregressivi succintamente rappresentati: trovare la sequenza più probabile sotto un vincolo globale è NP-hard. Il secondo (Teorema 2) riduce #SAT al calcolo della costante di normalizzazione necessaria per il campionamento esatto da sequenze di lunghezza fissa: quella costante è #P-hard da calcolare — una classe di complessità computazionale ancora più difficile di NP.
“Unlike finite-state Markov models, general autoregressive models do not admit a bounded-state dynamic program for these tasks.”
La distinzione con i modelli di Markov a stati finiti è centrale. Per quei modelli, la programmazione dinamica risolve esattamente i problemi di ottimizzazione e campionamento vincolato perché la dipendenza dal passato è riassumibile in uno stato limitato. Per i modelli autoregressivi generali — dove la distribuzione del token successivo dipende dall’intero prefisso attraverso una rappresentazione contestuale illimitata — non esiste un algoritmo analogo di complessità polinomiale.
Inpainting e vincoli metrici: i casi concreti
Il paper estende i risultati a due scenari particolarmente rilevanti per chi lavora con modelli generativi. Il primo è l’inpainting: riempire un segmento mancante in una sequenza parzialmente specificata — un uso comune sia nel testo che nella musica simbolica. L’inpainting esatto richiede di condizionare sia su un prefisso sia su un suffisso fisso, il che introduce necessariamente il calcolo di continuation masses (le masse di probabilità sui possibili completamenti futuri) sull’intero spazio dei completamenti compatibili. Il Corollario 6 del paper formalizza questo: qualsiasi procedura di inpainting esatto per modelli autoregressivi succinti che campioni dalla distribuzione condizionata corretta deve calcolare termini #P-hard.
Il secondo caso sono i vincoli metrici — sequenze con un numero fisso di sillabe o un peso totale prefissato. Anche qui, la NP-hardness persiste. Il caso degenere con peso unitario per ogni token corrisponde esattamente al vincolo di lunghezza fissa, il che mostra che la difficoltà non dipende da strutture metriche complesse: è intrinseca alla generazione vincolata su sequenze globali.
I sistemi esistenti — Anticipation-RNN, Piano Inpainting Application, DeepBach, i modelli di infilling testuale — evitano il problema addestrando modelli separati per ogni tipo di vincolo, oppure usando campionamento di Gibbs approssimato. Non risolvono il condizionamento esatto: lo sostituiscono con un’architettura diversa o con un’inferenza approssimata.
Cosa cambia per chi costruisce con i modelli generativi
Le implicazioni pratiche sono dirette. Primo: i fallimenti osservabili dei modelli linguistici su compiti con vincoli formali — una riga di dodici sillabe che ne conta tredici, una rima approssimata, un pattern posizionale che regge su un requisito e cede su un altro — non sono artefatti di dati di addestramento insufficienti o di architetture migliorabili con più parametri. Sono conseguenze di un ostacolo computazionale strutturale.
Secondo: chi sviluppa applicazioni basate su LLM che richiedono output con vincoli globali precisi — generatori di testo poetico, sistemi di completamento musicale, strumenti di inpainting per contenuti strutturati — non può attendersi che il problema si risolva scalando il modello. Deve progettare esplicitamente con vincoli esterni: constrained decoding, controller a stati finiti, moduli simbolici di reranking, architetture encoder-decoder dedicate al tipo di vincolo richiesto.
Terzo, e forse il punto più utile per chi legge questo articolo: il paper introduce la distinzione tra bias inferenziale nascosto e bias da distribuzione di addestramento. Il secondo — il termine con cui “bias” viene normalmente usato nel dibattito sui modelli linguistici — descrive distorsioni nei contenuti generati ereditate dai dati. Il primo descrive distorsioni nella procedura di generazione stessa: anche a parità di modello e di dati, l’approssimazione del condizionamento introduce campioni distorti rispetto alla distribuzione condizionata corretta.
Per chi valuta o audita sistemi generativi, questa distinzione ha conseguenze dirette su come misurare la copertura dello spazio delle soluzioni ammissibili e la correttezza delle probabilità sui campioni prodotti.
Il caso trattabile esiste: i modelli di Markov del primo ordine ammettono condizionamento esatto con belief propagation anche per vincoli regolari e Markoviani. Ma al di fuori di quella classe ristretta, la frontiera non è tra generazione vincolata e non vincolata. È tra vincoli che ammettono una ricorsione esatta a stato limitato insieme al modello, e vincoli che richiedono di ottimizzare o sommare su completamenti futuri. Per la seconda classe, i sistemi attuali producono invariabilmente campioni distorti rispetto alla legge condizionata target del modello sottostante.
Consulta il nostro Glossario AI.
Fonte primaria: Pachet, F. & Roy, P. (2026). Hidden Biases in Conditioning Autoregressive Models.