💬 NLP

Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

Cet article propose une approche générique pour atténuer le biais dans le décodage localement contraint en construisant des propositions globalement contraintes et tractables via des automates finis tensorisés et la multiplication de circuits, permettant un échantillonnage de Monte Carlo séquentiel efficace qui converge plus rapidement vers la distribution cible avec moins de particules à travers des tâches telles que l'appel de fonctions et la génération de SQL.

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

Publié 2026-06-02

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

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

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'enseigner à un conteur très créatif mais légèrement chaotique (un grand modèle de langage ou LLM) à écrire une histoire qui suit un carnet de règles très strict, comme un format de code JSON ou une requête de base de données SQL spécifique.

Le problème est que le conteur adore s'égarer. Si vous lui dites simplement : « Ne brise pas les règles », il peut commencer une phrase qui semble correcte au premier abord, mais qui devient impossible à terminer correctement à la fin.

Voici comment l'article résout ce problème, en utilisant des analogies simples :

1. L'ancienne méthode : Le guide « myope » (LCD)

Imaginez que le conteur traverse un labyrinthe. L'ancienne méthode (appelée Locally Constrained Decoding ou LCD) agit comme un guide qui ne regarde que le pas suivant.

Comment ça marche : Si le prochain pas semble risquer de heurter un mur, le guide le bloque.
La faille : Le guide est « myope » (il manque de vision à long terme). Il peut laisser le conteur prendre un chemin qui semble sûr pour le prochain pas, mais qui mène à une impasse trois pas plus tard. Le conteur continue d'avancer, pensant qu'il va bien, pour réaliser à la toute fin qu'il ne peut pas terminer son histoire dans la limite de mots impartie. Il doit alors recommencer ou produire une histoire brisée.

2. La nouvelle méthode : La « Carte Globale » (GCD)

Les auteurs proposent une nouvelle méthode appelée Globally Constrained Decoding (GCD).

L'analogie : Au lieu de regarder seulement le pas suivant, ce guide possède une carte complète de l'ensemble du labyrinthe et sait exactement combien de pas restent à faire pour atteindre la sortie.
Comment ça marche : Avant que le conteur ne fasse un pas, le guide vérifie : « Si tu vas par là, peux-tu réellement atteindre la sortie avec les pas restants ? »
Le résultat : Si la réponse est « Non », le guide bloque ce chemin immédiatement. Cela garantit que, peu importe le choix du conteur, il atteindra toujours une fin valide. C'est comme avoir un GPS qui n'affiche que les itinéraires garantis pour vous mener à destination à temps.

3. La carte « intelligente » : Ajouter la probabilité (P-GCD)

La « Carte Globale » (GCD) est excellente pour éviter les impasses, mais elle traite tous les chemins valides de la même manière. Elle ne sait pas quel chemin le conteur préfère ou lequel est le plus susceptible d'être une bonne histoire.

L'analogie : Imaginez que le conteur ait une façon préférée de marcher. La carte de base dit simplement : « Ce chemin est valide ». La nouvelle Probabilistic GCD (P-GCD) dit : « Ce chemin est valide, et c'est aussi le chemin que le conteur est le plus susceptible d'apprécier ».
Comment ça marche : Les auteurs combinent la « Carte Globale » (les règles) avec un « Modèle de Mémoire » (une version simplifiée du cerveau du conteur). Ils multiplient ces deux éléments ensemble.
Le résultat : Le guide ne se contente plus de bloquer les mauvais chemins ; il oriente doucement le conteur vers les chemins qui sont à la fois valides et de haute qualité. Cela rend le processus de narration beaucoup plus efficace.

4. La course de « particules » (SMC)

Pour tester ces méthodes, les chercheurs utilisent une technique appelée Sequential Monte Carlo (SMC).

L'analogie : Imaginez que vous essayiez de trouver le meilleur itinéraire à travers une forêt brumeuse. Au lieu d'envoyer une seule personne, vous envoyez un essaim de 100 « particules » (explorateurs).
L'ancienne méthode : Avec le guide myope, vous devez envoyer des milliers d'explorateurs car beaucoup d'entre eux se perdront ou heurteront des impasses avant d'avoir terminé.
La nouvelle méthode : Avec la « Carte Globale » et la « Carte Intelligente », les explorateurs restent sur la bonne voie. Vous avez besoin de beaucoup moins d'explorateurs pour trouver le chemin parfait car le guide est bien plus efficace pour filtrer les mauvaises options dès le début.

5. L'astuce du « changement de forme » (Tensorisation)

L'une des percées techniques de l'article est la manière dont ils gèrent la « Carte ».

Le problème : Des règles complexes (comme les schémas JSON) peuvent créer des cartes avec des millions de chemins. Habituellement, les ordinateurs sont submergés en essayant de dessiner ces cartes sur un processeur standard.
La solution : Les auteurs ont transformé ces cartes complexes en blocs mathématiques (tenseurs) qui s'adaptent parfaitement aux cartes graphiques (GPU) modernes.
L'analogie : C'est comme prendre une pile géante et désordonnée de cartes papier et la plier en une puce numérique compacte et ultra-rapide que un supercalculateur peut lire instantanément. Cela permet de calculer la « Carte Globale » en un clin d'œil, même pour des règles très complexes.

Résumé des résultats

L'article a testé cela sur trois tâches réelles :

Appel de fonction (Function Calling) : S'assurer que l'IA appelle des fonctions informatiques avec le bon format (comme le JSON).
Génération de mots-clés : S'assurer qu'une histoire inclut des mots spécifiques.
Génération SQL : Écrire des requêtes de base de données syntaxiquement correctes.

Le verdict :

Fiabilité : La nouvelle méthode garantit que l'histoire se termine correctement dans la limite de mots, alors que l'ancienne méthode échouait souvent à la ligne d'arrivée.
Efficacité : Pour obtenir la même qualité de résultats, la nouvelle méthode a eu besoin de beaucoup moins d'« explorateurs » (particules) que l'ancienne méthode.
Vitesse : Bien que la « Carte Intelligente » (P-GCD) demande un peu plus de puissance de calcul, elle reste suffisamment rapide pour être pratique, et la « Carte Globale » (GCD) est presque aussi rapide que l'ancienne méthode.

En résumé, l'article donne à l'IA une « Carte Globale » et un « Guidage Intelligent » pour qu'elle puisse suivre des règles strictes sans se perdre, sans perdre de temps et sans produire de code défectueux.

Résumé Technique : Atténuation du Biais dans le Décodage Localement Contraint via des Propositions Tractables

Énoncé du Problème

Les grands modèles de langage (LLM) échouent souvent à générer des sorties qui respectent strictement les contraintes logiques ou structurelles, telles que les schémas JSON, les requêtes SQL valides ou des formats spécifiques d'appel de fonctions. Bien que l'ajustement par instructions (instruction tuning) et l'optimisation des préférences aient amélioré l'alignement général, ils restent peu fiables pour imposer des contraintes « fortes ».

Les approches existantes font face à deux limitations principales :

Échantillonnage par Rejet (Rejection Sampling) : Bien qu'in biaisé, il est informatiquement impraticable pour des contraintes complexes en raison de taux d'acceptation extrêmement faibles.
Décodage Localement Contraint (LCD - Locally Constrained Decoding) : Cette approche standard masque les jetons qui violent immédiatement une contrainte à chaque étape. Cependant, elle souffre de deux défauts critiques :
- Biais : Elle déforme la distribution sous-jacente du modèle en masquant de manière myope les jetons sans considérer la validité future, ce qui entraîne un biais d'échantillonnage.
- Absence de Garantie de Terminaison : Le LCD garantit uniquement la validité locale. Une séquence peut rester localement valide indéfiniment (par exemple, une accolade non fermée dans un JSON) mais échouer à satisfaire la contrainte dans un budget de jetons $n$ fixé.

Pour remédier à ces problèmes, un cadre de Monte Carlo Séquentiel (SMC) a été proposé, utilisant le LCD comme distribution de proposition et en repondérant les particules pour converger vers la distribution cible. Cependant, le taux de convergence du SMC est limité par la qualité de la proposition ; le LCD est une proposition faible car il manque d'informations probabilistes sur les complétions valides futures et ne garantit pas la satisfaction de la contrainte dans un budget fini.

Méthodologie

Les auteurs proposent une approche générique pour construire des propositions et des fonctions de potentiel tractables pour l'échantillonnage SMC à partir de la distribution contrainte $p_{lm}(\cdot \mid C)$ . L'innovation centrale consiste à représenter les contraintes sous forme d'automates finis et à exploiter les opérations tensorielles pour une exécution efficace sur GPU.

1. Décodage Globalement Contraint (GCD - Globally Constrained Decoding)

Le GCD améliore le LCD en garantissant que chaque jeton généré peut mener à une complétion valide dans le budget de jetons restant $n$ .

Automates Tensorisés : Les contraintes encodées sous forme d'automates finis (FA), spécifiquement des automates finis non déterministes (NFA) et déterministes (DFA), sont compilées en représentations tensorielles (matrices de transition $T_{out}, T_{in}$ et matrice d'émission $B_f$ ). Cela permet une exécution efficace sur les GPU.
Inférence Forward-Backward :
- Processus Forward (Avant) : Calcule l'ensemble des états de l'automate (FA) atteignables après avoir observé le préfixe $x_{1:t-1}$ .
- Processus Backward (Arrière) : Calcule si un état peut atteindre un état acceptant en exactement $n-t$ étapes.
Masquage Global : Un jeton est autorisé uniquement s'il mène à un état qui admet une continuation valide dans le budget restant. Cela garantit que toute séquence de longueur $n$ générée sous GCD satisfait la contrainte $C$ .

2. Décodage Globalement Contraint Probabiliste (P-GCD)

Bien que le GCD garantisse la satisfaction de la contrainte, son masque est binaire (valide/invalide) et ignore la vraisemblance des complétions valides sous le LLM. Le P-GCD traite cela en intégrant des informations probabilistes.

Distillation HMM : La distribution du LLM est approximée par un Modèle de Markov Caché (HMM), suivant les travaux antérieurs (Zhang et al., 2023).
Multiplication de Circuits : L'automate tensorisé (vu comme un HMM non normalisé sur les arêtes) est multiplié par le HMM distillé en utilisant des algorithmes de multiplication de circuits. Cela tire parti de la structure algébrique partagée des FA et des HMM.
Distribution Produit : La distribution produit résultante $p_{prod}$ capture à la fois les contraintes logiques dures de l'automate (FA) et les préférences probabilistes du LLM.
Proposition et Potentiel :
- Proposition ( $q_{pgcd}$ ) : Repondère la distribution du LM à chaque étape en utilisant la probabilité du jeton suivant contrainte dérivée de $p_{prod}$ .
- Potentiel ( $\phi_{pgcd}$ ) : Pondère les particules dans le SMC par le produit de la probabilité du préfixe du LM et de l'estimation de satisfaction de la contrainte par anticipation (look-ahead) du HMM.

3. Implémentation Efficace

Les auteurs utilisent des opérations de réseaux tensoriels (spécifiquement l'identité Kronecker-vec) pour éviter de matérialiser explicitement de grandes matrices de produit de Kronecker. Cela réduit le coût computationnel des étapes de transition de $O((HE)^2)$ à $O(H^2E + HE^2)$ , où $H$ est la taille de l'état caché du HMM et $E$ est le nombre d'arêtes de l'automate (FA), permettant une génération autorégressive efficace.

Principales Contributions

Cadres GCD et P-GCD : L'introduction du Décodage Globalement Contraint et du GCD Probabiliste, qui fournissent des propositions et des potentiels tractables pour le SMC garantissant la satisfaction des contraintes dans un budget de jetons.
Automates Tensorisés sur GPU : La première proposition de tensorisation des automates finis (incluant les NFA) pour une inférence efficace et native sur GPU, surmontant les limitations liées au CPU des frameworks existants comme Outlines et XGrammar.
Support NFA : Démontrer que les NFA peuvent être exponentiellement plus concis que les DFA pour des contraintes complexes (ex: appel de fonction avec paramètres variables), rendant l'approche scalable aux applications agentiques réelles où la construction de DFA peut causer un dépassement de mémoire (OOM).
Intégration avec SMC : Montrer que le (P-)GCD accélère significativement la convergence du SMC par rapport aux propositions basées sur le LCD, nécessitant beaucoup moins de particules pour atteindre la distribution cible.

Résultats Expérimentaux

Les auteurs ont évalué le (P-)GCD sur trois benchmarks : xLAM (appel de fonction), CommonGen (génération basée sur des mots-clés) et Spider (text-to-SQL).

Appel de Fonction (xLAM) :
- Le (P-)GCD a atteint une précision nettement supérieure au LCD pour un même nombre de particules.
- Le P-GCD a convergé vers la distribution réelle (échantillonnage par rejet) plus rapidement que le GCD, soulignant l'avantage des informations probabilistes.
- Satisfaction de la Contrainte : Le GCD et le P-GCD ont atteint des taux de satisfaction de contrainte de 100 % sur tous les budgets de particules, tandis que le LCD a échoué à satisfaire les contraintes même à des budgets modérés (ex: ~95 % pour JSON).
- Efficacité : Le LCD et le GCD ont subi un ralentissement modeste (1,08× et 1,10×). Le P-GCD était plus lent (3,11× à 10,2×) en raison des calculs HMM, mais restait faisable.
Génération de Mots-Clés (CommonGen) : L'utilisation du P-GCD comme proposition et potentiel a amélioré les scores BLEU et la vitesse de convergence de manière significative par rapport au LCD.
Text-to-SQL (Spider) : Le GCD et le P-GCD ont amélioré la précision d'exécution par rapport au LCD sur divers budgets de particules, particulièrement pour des valeurs modérées.
NFA vs. DFA : Les expériences ont confirmé que pour des schémas complexes (ex: paramètres de fonction à longueur variable), les NFA croissent linéairement en taille tandis que les DFA croissent exponentiellement. Pour la grammaire SQL de Spider, la construction du DFA a entraîné des erreurs de dépassement de mémoire (OOM) au niveau du jeton, alors que le NFA est resté traitable (~32k états).

Signification et Revendications

L'article affirme que le décodage localement contraint introduit un biais d'échantillonnage substantiel et ne garantit pas la satisfaction des contraintes dans des budgets de jetons finis. En proposant le (P-)GCD, les auteurs offrent une solution qui :

Garantit la Validité : Assure que toute séquence générée de longueur $n$ satisfait la contrainte, éliminant les cas d'échec du LCD.
Réduit le Biais : En incorporant des informations probabilistes (via le P-GCD) et une anticipation globale, les propositions approximent mieux la distribution conditionnelle cible.
Améliore l'Efficacité : Dans le cadre du SMC, le (P-)GCD converge vers la distribution cible avec beaucoup moins de particules que les approches basées sur le LCD, réduisant ainsi le coût computationnel d'une génération contrainte de haute qualité.

Ce travail se positionne comme une étape fondamentale vers une génération fiable satisfaisant les contraintes pour les LLM dans des applications exigeant une adhérence structurelle stricte, telle que l'appel de fonctions et la génération de code, en unifiant les contraintes logiques (via les automates) et la modélisation probabiliste (via les HMM) de manière efficace sur GPU.