💬 NLP

Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

Questo articolo propone un approccio generico per mitigare il bias nella decodifica localmente vincolata costruendo proposte globalmente vincolate e trattabili tramite automi tensoriali e moltiplicazione di circuiti, consentendo un campionamento Sequential Monte Carlo efficiente che converge più velocemente alla distribuzione target con meno particelle in compiti quali la chiamata di funzioni e la generazione di SQL.

Autori originali: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

Pubblicato 2026-06-02

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di cercare di insegnare a un narratore molto creativo ma leggermente caotico (un Large Language Model) come scrivere una storia che segua un libro di regole molto rigido, come un formato di codice JSON o una specifica query di un database SQL.

Il problema è che il narratore ama vagare. Se dici solo "Non infrangere le regole", potrebbe iniziare una frase che sembra corretta all'inizio, ma che diventa impossibile da terminare correttamente verso la fine.

Ecco come il documento risolve questo problema, usando analogie semplici:

1. Il vecchio modo: La guida "miope" (LCD)

Immagina che il narratore stia camminando attraverso un labirinto. Il vecchio metodo (chiamato Locally Constrained Decoding o LCD) agisce come una guida che guarda solo il passo successivo.

Come funziona: Se il passo successivo sembra che potrebbe colpire un muro, la guida lo blocca.
Il difetto: La guida è "miope" (miope). Potrebbe lasciare che il narratore faccia un passo che sembra sicuro per il passaggio successivo, ma che conduce a un vicolo cieco tre passi dopo. Il narratore continua a camminare, pensando di stare bene, solo per rendersi conto alla fine che non può finire la storia entro il limite di parole. Deve ricominciare da capo o produrre una storia interrotta.

2. Il nuovo modo: La "Mappa Globale" (GCD)

Gli autori propongono un nuovo metodo chiamato Globally Constrained Decoding (GCD).

L'analogia: Invece di guardare solo il passo successivo, questa guida ha una mappa completa dell'intero labirinto e sa esattamente quanti passi mancano per raggiungere l'uscita.
Come funziona: Prima che il narratore faccia un passo, la guida controlla: "Se vai da questa parte, riuscirai effettivamente a raggiungere l'uscita entro i passi rimanenti?"
Il risultato: Se la risposta è "No", la guida blocca quel percorso immediatamente. Questo garantisce che, indipendentemente dalla scelta del narratore, egli raggiungerà sempre una conclusione valida. È come avere un GPS che mostra solo percorsi che garantiscono di raggiungere la destinazione in tempo.

3. La mappa "intelligente": Aggiungere la probabilità (P-GCD)

La "Mappa Globale" (GCD) è ottima per evitare vicoli ciechi, ma tratta tutti i percorsi validi allo stesso modo. Non sa quale percorso il narratore preferisce o quale sia più probabile che sia una buona storia.

L'analogia: Immagina che il narratore abbia un modo preferito di camminare. La mappa di base dice solo: "Questo percorso è valido". Il nuovo Probabilistic GCD (P-GCD) dice: "Questo percorso è valido, ed è anche il percorso che il narratore probabilmente preferirà".
Come funziona: Gli autori combinano la "Mappa Globale" (le regole) con un "Modello di Memoria" (una versione semplificata del cervello del narratore). Moltiplicano queste due cose insieme.
Il risultato: La guida ora non si limita a bloccare i percorsi sbagliati; spinge gentilmente il narratore verso i percorsi che sono sia validi che di alta qualità. Questo rende il processo di narrazione molto più efficiente.

4. La corsa delle "Particelle" (SMC)

Per testare questi metodi, i ricercatori utilizzano una tecnica chiamata Sequential Monte Carlo (SMC).

L'analogia: Immagina di dover trovare il percorso migliore attraverso una foresta nebbiosa. Invece di inviare una sola persona, invii uno sciame di 100 "particelle" (esploratori).
Il vecchio modo: Con la guida miope, devi inviare migliaia di esploratori perché molti di loro si perderanno o colpiranno vicoli ciechi prima di finire.
Il nuovo modo: Con la "Mappa Globale" e la "Mappa Intelligente", gli esploratori rimangono sulla strada giusta. Hai bisogno di molti meno esploratori per trovare il percorso perfetto perché la guida è molto più brava a filtrare le opzioni errate all'inizio.

5. Il trucco del "cambio di forma" (Tensorization)

Uno dei progressi tecnici del documento è il modo in cui gestiscono la "Mappa".

Il problema: Regole complesse (come gli schemi JSON) possono creare mappe con milioni di percorsi. Di solito, i computer vengono sopraffatti nel tentativo di disegnare queste mappe su un processore standard.
La soluzione: Gli autori hanno trasformato queste mappe complesse in blocchi matematici (tensori) che si adattano perfettamente alle moderne schede grafiche (GPU).
L'analogia: È come prendere un enorme e disordinato mucchio di mappe cartacee e ripiegarle in un chip digitale compatto e ad alta velocità che un supercomputer può leggere istantaneamente. Questo permette alla "Mappa Globale" di essere calcolata in un battito di ciglia, anche per regole molto complesse.

Sintesi dei Risultati

Il documento ha testato questo su tre compiti del mondo reale:

Function Calling: Assicurarsi che l'IA chiami le funzioni del computer con il formato corretto (come JSON).
Keyword Generation: Assicurarsi che una storia includa parole specifiche.
SQL Generation: Scrivere query di database che siano sintatticamente corrette.

Il Verdetto:

Affidabilità: Il nuovo metodo garantisce che la storia termini correttamente entro il limite di parole, mentre il vecchio metodo spesso falliva al traguardo.
Efficienza: Per ottenere la stessa qualità di risultati, il nuovo metodo ha richiesto significativamente meno "esploratori" (particelle) rispetto al vecchio metodo.
Velocità: Sebbene la "Mappa Intelligente" (P-GCD) richieda un po' più di potenza di calcolo, è comunque abbastanza veloce da essere pratica, e la "Mappa Globale" (GCD) è quasi veloce quanto il vecchio metodo.

In breve, il documento fornisce all'IA una "Mappa Globale" e una "Spinta Intelligente" affinché possa seguire regole rigide senza perdersi, sprecare tempo o produrre codice interrotto.

Sintesi Tecnica: Mitigare il Bias nella Decodifica Localmente Vincolata tramite Proposte Trattabili

Problema

I Large Language Models (LLM) spesso falliscono nel generare output che aderiscano rigorosamente a vincoli logici o strutturali, come schemi JSON, query SQL valide o formati specifici per la chiamata di funzioni (function-calling). Sebbene l'instruction tuning e l'ottimizzazione delle preferenze abbiano migliorato l'allineamento generale, essi rimangono inaffidabili per l'imposizione di vincoli "hard".

Gli approcci esistenti affrontano due limitazioni primarie:

Rejection Sampling: Sebbene non distorto (unbiased), è computazionalmente impraticabile per vincoli complessi a causa di tassi di accettazione estremamente bassi.
Locally Constrained Decoding (LCD): Questo approccio standard maschera i token che violano immediatamente un vincolo ad ogni step. Tuttavia, soffre di due criticità fondamentali:
- Bias: Distorce la distribuzione sottostante del modello mascherando miopeamente i token senza considerare la validità futura, portando a un bias di campionamento.
- Assenza di Garanzia di Terminazione: L'LCD garantisce solo la validità locale. Una sequenza può rimanere localmente valida indefinitamente (ad esempio, una parentesi graffa non chiusa in un JSON) ma fallire nel soddisfare il vincolo entro un budget fisso di $n$ token.

Per affrontare questi problemi, è stato proposto il framework Sequential Monte Carlo (SMC), utilizzando l'LCD come distribuzione di proposta e ri-pesando le particelle per convergere alla distribuzione target. Tuttavia, il tasso di convergenza dell'SMC è limitato dalla qualità della proposta; l'LCD è una proposta debole perché manca di informazioni probabilistiche sulla validità delle completazioni future e non garantisce la soddisfazione del vincolo entro un budget finito.

Metodologia

Gli autori propongono un approccio generico per costruire proposte trattabili e funzioni di potenziale per il campionamento SMC dalla distribuzione vincolata $p_{lm}(\cdot \mid C)$ . L'innovazione principale consiste nel rappresentare i vincoli come automi finiti e sfruttare le operazioni tensoriali per un'esecuzione efficiente su GPU.

1. Globally Constrained Decoding (GCD)

Il GCD migliora l'LCD garantendo che ogni token generato possa portare a una completazione valida entro il budget di token rimanente $n$ .

Automi Finiti Tensorizzati: I vincoli codificati come Automi Finiti (FA), specificamente Automi Finiti Non-deterministici (NFA) e Automi Finiti Deterministici (DFA), vengono compilati in rappresentazioni tensorizzate (matrici di transizione $T_{out}, T_{in}$ e matrice di emissione $B_f$ ). Ciò consente un'esecuzione efficiente su GPU.
Inferenza Forward-Backward:
- Processo Forward: Calcola l'insieme degli stati dell'FA raggiungibili dopo aver osservato il prefisso $x_{1:t-1}$ .
- Processo Backward: Calcola se uno stato può raggiungere uno stato accettante in esattamente $n-t$ passi.
Mascheramento Globale: Un token è permesso solo se conduce a uno stato che ammette una continuazione valida entro il budget rimanente. Questo garantisce che qualsiasi sequenza di lunghezza $n$ generata sotto GCD soddisfi il vincolo $C$ .

2. Probabilistic Globally Constrained Decoding (P-GCD)

Sebre il GCD garantisca la soddisfazione del vincolo, la sua maschera è binaria (valido/invalido) e ignora la verosimiglianza delle completazioni valide sotto l'LLM. Il P-GCD affronta questo problema integrando informazioni probabilistiche.

Distillazione HMM: La distribuzione dell'LLM viene approssimata da un Modello di Markov Nascosto (HMM), seguendo il lavoro precedente (Zhang et al., 2023).
Moltiplicazione di Circuiti: L'FA tensorizzato (visto come un HMM non normalizzato sugli archi) viene moltiplicato con l'HMM distillato utilizzando algoritmi di moltiplicazione di circuiti. Ciò sfrutta la struttura algebrica condivisa tra FA e HMM.
Distribuzione Prodotto: La distribuzione prodotto risultante $p_{prod}$ cattura sia i vincoli logici rigidi dell'FA sia le preferenze probabilistiche dell'LLM.
Proposta e Potenziale:
- Proposta ( $q_{pgcd}$ ): Ri-pesa la distribuzione del LM ad ogni step utilizzando la probabilità del next-token vincolata derivata da $p_{prod}$ .
- Potenziale ( $\phi_{pgcd}$ ): Pesa le particelle nell'SMC tramite il prodotto della probabilità del prefisso del LM e la stima di soddisfazione del vincolo look-ahead dell'HMM.

3. Implementazione Efficiente

Gli autori utilizzano operazioni di reti tensoriali (specificamente l'identità Kronecker-vec) per evitare la materializzazione esplicita di grandi matrici prodotto di Kronecker. Ciò riduce il costo computazionale dei passaggi di transizione da $O((HE)^2)$ a $O(H^2E + HE^2)$ , dove $H$ è la dimensione nascosta dell'HMM ed $E$ è il conteggio degli archi dell'FA, consentendo una generazione autoregressiva efficiente.

Contributi Chiave

Framework GCD e P-GCD: L'introduzione di Globally Constrained Decoding e Probabilistic GCD, che forniscono proposte e potenziali trattabili per l'SMC che garantiscono la soddisfazione dei vincoli entro un budget di token.
Automi Tensorizzati su GPU: La prima proposta di tensorizzare gli automi finiti (inclusi gli NFA) per un'inferenza efficiente nativa su GPU, superando i limiti legati alla CPU di framework esistenti come Outlines e XGrammar.
Supporto NFA: Dimostrare che gli NFA possono essere esponenzialmente più succinti dei DFA per vincoli complessi (ad esempio, la chiamata di funzioni con parametri variabili), rendendo l'approccio scalabile ad applicazioni agentiche reali dove la costruzione di DFA può causare l'overflow della memoria.
Integrazione con SMC: Mostrare come (P-)GCD acceleri significativamente la convergenza dell'SMC rispetto alle proposte basate su LCD, richiedendo molte meno particelle per raggiungere la distribuzione target.

Risultati Sperimentali

Gli autori hanno valutato (P-)GCD su tre benchmark: xLAM (function calling), CommonGen (generazione basata su parole chiave) e Spider (text-to-SQL).

Function Calling (xLAM):
- (P-)GCD ha raggiunto un'accuratezza sostanzialmente superiore rispetto a LCD allo stesso numero di particelle.
- P-GCD è convergente alla distribuzione reale (rejection sampling) più velocemente di GCD, evidenziando il beneficio delle informazioni probabilistiche.
- Soddisfazione del Vincolo: GCD e P-GCD hanno raggiunto tassi di soddisfazione del vincolo del 100% in tutti i budget di particelle, mentre LCD ha fallito nel soddisfare i vincoli anche con budget moderati (ad esempio, ~95% per JSON).
- Efficienza: LCD e GCD hanno comportato un overhead modesto (slowdown di 1.08× e 1.10×). P-GCD è stato più lento (3.11× a 10.2×) a causa dei calcoli HMM, ma rimane fattibile.
Generazione di Parole Chiave (CommonGen): L'uso di P-GCD sia come proposta che come potenziale ha migliorato i punteggi BLEU e la velocità di convergenza significativamente rispetto a LCD.
Text-to-SQL (Spider): GCD e P-GCD hanno migliorato l'accuratezza di esecuzione rispetto a LCD attraverso vari budget di particelle, particolarmente per valori moderati.
NFA vs. DFA: Gli esperimenti hanno confermato che per schemi complessi (ad esempio, parametri di funzione a lunghezza variabile), gli NFA crescono linearmente in dimensione mentre i DFA crescono esponenzialmente. Per la grammatica SQL di Spider, la costruzione del DFA ha causato errori di Out-of-Memory (OOM) a livello di token, mentre l'NFA è rimasto trattabile (~32k stati).

Significato e Rivendicazioni

Il paper sostiene che la decodifica localmente vincolata introduce un sostanziale bias di campionamento e non garantisce la soddisfazione dei vincoli entro budget finiti di token. Proponendo (P-)GCD, gli autori offrono una soluzione che:

Garantisce la Validità: Assicura che qualsiasi sequenza generata di lunghezza $n$ soddisfi il vincolo, eliminando i casi di fallimento dell'LCD.
Riduce il Bias: Incorporando informazioni probabilistiche (tramite P-GCD) e un lookahead globale, le proposte approssimano meglio la distribuzione condizionale target.
Migliora l'Efficienza: Nel framework SMC, (P-)GCD converge alla distribuzione target con significativamente meno particelle rispetto agli approcci basati su LCD, riducendo il costo computazionale della generazione vincolata di alta qualità.

Il lavoro si posiziona come un passo fondamentale verso una generazione affidabile e conforme ai vincoli per gli LLM in applicazioni che richiedono una rigorosa aderenza strutturale, come il function calling e la generazione di codice, unificando i vincoli logici (tramite automi) e la modellazione probabilistica (tramite HMM) in modo efficiente su GPU.