💬 NLP

Probabilistic Programs of Thought

Ce papier propose un cadre novateur appelé « programmes de pensée probabilistes » qui exploite les distributions de probabilité des tokens générés par un LLM pour construire un programme compact représentant exponentiellement d'autres programmes, permettant ainsi d'échantillonner de nouvelles solutions sans coût de calcul GPU supplémentaire et d'améliorer les performances en génération de code et en raisonnement mathématique.

Auteurs originaux : Poorva Garg, Renato Lui Geh, Daniel Israel, Todd Millstein, Kyle Richardson, Guy Van den Broeck

Publié 2026-04-21

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Poorva Garg, Renato Lui Geh, Daniel Israel, Todd Millstein, Kyle Richardson, Guy Van den Broeck

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

Imagine que vous demandez à un grand chef cuisinier (l'Intelligence Artificielle) de vous préparer un plat complexe, comme un gâteau mathématique ou un code informatique.

Le problème actuel :
Habituellement, si le chef vous donne un gâteau qui n'est pas parfait (par exemple, il manque un œuf ou il y a trop de sucre), vous devez lui demander de recommencer depuis le début. Pour avoir une chance d'avoir un gâteau parfait, vous devez lui en faire faire 10, 20, voire 50. C'est très long, très cher en énergie (comme utiliser un four géant 50 fois), et ça prend beaucoup de temps.

La solution proposée par les auteurs (PPoT) :
Ces chercheurs de l'UCLA et de l'Allen Institute for AI ont trouvé une astuce géniale. Au lieu de faire refaire le gâteau 50 fois, ils disent : "Attends, ce gâteau que tu viens de faire est presque parfait. Regarde, tu hésitais entre mettre 2 œufs ou 3 œufs. Au lieu de tout recommencer, transformons ce gâteau en un 'gâteau magique' qui contient toutes les possibilités en même temps."

Voici comment cela fonctionne, étape par étape, avec des analogies simples :

1. Le Gâteau "Probabiliste" (Le Programme Probabiliste)

Quand le chef (l'IA) écrit une ligne de code ou un chiffre, il ne choisit pas au hasard absolu. Il a une petite voix intérieure qui dit : "Il y a 90 % de chances que ce soit un '2', mais 10 % de chances que ce soit un '3'."

D'habitude, l'IA choisit le "2" et on oublie le "3".
PPoT, c'est comme si on prenait ce gâteau et qu'on le transformait en un sac de possibilités.

Au lieu d'avoir un seul chiffre "2", on met un petit bouton magique qui dit : "Ce chiffre est soit un 2, soit un 3, selon les probabilités que le chef avait en tête."
On fait ça pour tous les endroits où le chef hésitait (les chiffres, les signes + ou -, les virgules).

2. La Cuisine "Sans Four" (Économie d'énergie)

Maintenant, vous avez ce "sac de possibilités".

L'ancienne méthode : Pour tester si le gâteau est bon avec 3 œufs, vous deviez allumer le four (le GPU) et cuire un nouveau gâteau.
La nouvelle méthode (PPoT) : Vous n'avez plus besoin du four ! Vous prenez votre "sac de possibilités" et vous le secouez. Mathématiquement, vous pouvez "simuler" 100 versions différentes de ce gâteau instantanément sur un simple ordinateur de bureau, sans utiliser le super-ordinateur coûteux.

C'est comme si vous aviez un gâteau qui, une fois coupé, pouvait se transformer en 100 variantes différentes sans avoir besoin de cuisiner à nouveau.

3. Le Résultat : Plus de chances de succès

En secouant ce "sac de possibilités", on obtient rapidement des centaines de variations du code ou de la réponse.

L'une des variations aura peut-être le bon chiffre (le "3" au lieu du "2").
Une autre aura le bon signe de multiplication.
On teste toutes ces variantes rapidement. Si l'une d'elles fonctionne, on l'envoie.

En résumé :
Au lieu de demander à l'IA de répéter son travail 50 fois (ce qui coûte cher et prend du temps), on prend une seule fois son travail, on y injecte un peu de "magie mathématique" pour explorer toutes les petites erreurs possibles, et on trouve la solution correcte presque gratuitement.

L'analogie finale :
C'est comme si vous aviez une boussole un peu floue.

Méthode classique : Vous marchez dans la forêt, vous vous trompez, vous revenez en arrière et vous recommencez 50 fois pour trouver le chemin.
Méthode PPoT : Vous regardez la boussole, vous réalisez qu'elle hésite entre le Nord et le Nord-Est. Vous dessinez instantanément 100 chemins possibles sur une carte (sans marcher), vous vérifiez lequel mène à la sortie, et vous y allez directement.

C'est une façon intelligente de faire plus avec moins, en utilisant la logique des probabilités pour économiser de l'énergie et du temps.

1. Problématique

Les grands modèles de langage (LLM) sont de plus en plus utilisés pour la génération de code et le raisonnement mathématique (par exemple, via la méthode "Programs of Thought"). Le flux de travail standard consiste à interroger le modèle, générer un programme, l'exécuter et vérifier le résultat. Si le programme est incorrect, le processus est répété.

Pour améliorer la précision, les approches actuelles utilisent des stratégies de décodage comme Best-of-n ou la recherche par faisceau (beam search), qui nécessitent de générer $n$ programmes distincts. Cependant, chaque génération demande un appel coûteux au LLM (inférence GPU). Pour les grands modèles, générer un grand nombre d'échantillons ( $n$ ) devient prohibitif en termes de ressources de calcul (GPU) et de temps, limitant ainsi l'efficacité de l'exploration de l'espace des solutions.

2. Méthodologie : Probabilistic Programs of Thought (PPoT)

Les auteurs proposent une nouvelle technique de décodage appelée Probabilistic Programs of Thought (PPoT). L'idée centrale est d'exploiter la distribution de probabilité sous-jacente du LLM au sein même du programme généré, plutôt que de rejeter cette information après l'échantillonnage.

Principes Fondamentaux

Modélisation comme Programme Probabiliste : Au lieu de traiter le code généré par le LLM comme un programme déterministe fixe, PPoT le transforme en un programme probabiliste.
Conversion des Tokens en Variables Aléatoires :
- Le LLM génère d'abord un programme déterministe (ex: return 0 + 2).
- Au lieu de figer les tokens (comme les chiffres 0 ou 2), l'algorithme identifie certains tokens clés (chiffres, opérateurs arithmétiques, opérateurs de comparaison) et les remplace par des variables aléatoires ( $X_i$ ).
- La distribution de ces variables est paramétrée par les logits (probabilités des prochains tokens) fournis par le LLM lors de la génération initiale.
Inférence Efficace :
- Le programme résultant est un programme probabiliste compact qui représente de manière exponentielle un grand nombre de programmes déterministes potentiels.
- Au lieu de faire de nouveaux appels GPU coûteux, on effectue un échantillonnage (sampling) à partir de ce programme probabiliste sur CPU. Cela permet de générer des milliers de variantes du code initial (en changeant par exemple 0 en 2 ou + en -) sans aucune inférence supplémentaire du LLM.
Hypothèse d'Indépendance : Pour garantir la validité théorique, l'article suppose que les tokens rééchantillonnés sont indépendants des tokens suivants dans la séquence originale (hypothèse de rééchantillonnage indépendant). Sous cette hypothèse, la distribution empirique des échantillons converge vers la distribution réelle du LLM.

Algorithme

L'algorithme (Algorithm 2 dans le papier) fonctionne en deux étapes :

Génération LLM : On génère $k$ programmes initiaux et on conserve les distributions de probabilité des tokens pour une sélection de positions $L$ .
Compilation et Rééchantillonnage : On compile ces programmes en structures probabilistes. Pour chaque programme initial, on génère $m$ nouveaux échantillons en rééchantillonnant uniquement les tokens de l'ensemble $L$ selon leurs distributions d'origine, tout en gardant le reste du code fixe.

3. Contributions Clés

Nouvelle Technique de Décodage : Introduction de PPoT, une méthode qui permet d'obtenir beaucoup plus d'échantillons de haute qualité à partir d'un seul appel au LLM, en transformant le code généré en programme probabiliste.
Validité Distributionnelle : Démonstration théorique que, sous certaines hypothèses d'indépendance, la distribution des échantillons générés par PPoT converge vers la distribution du modèle de langage original ( $P_{code}$ ).
Efficacité Computationnelle : Preuve que cette approche réduit drastiquement le coût de calcul (GPU) tout en augmentant la couverture de l'espace de recherche.
Validation Empirique : Évaluation sur trois benchmarks majeurs couvrant le raisonnement mathématique, la génération de code et la compréhension de code.

4. Résultats Expérimentaux

Les expériences ont été menées sur les modèles Qwen2.5 Coder (0.5B, 3B, 7B) et Qwen2.5 VL sur trois jeux de données :

GSM8k (Raisonnement mathématique)
Plot2Code (Génération de code pour tracer des graphiques)
CRUXEval (Compréhension et inversion de code)

Résultats Principaux :

Amélioration de la Précision (Pass@k) : PPoT améliore systématiquement les performances. Par exemple, sur GSM8k avec le modèle 7B, l'utilisation de seulement 5 échantillons PPoT par génération LLM augmente la précision de 2 à 7 % sans aucun coût GPU supplémentaire.
Réduction du Coût GPU : Pour atteindre la même précision qu'une méthode "Best-of-n" classique (nécessitant 20 générations LLM), PPoT n'a besoin que de 8 générations LLM combinées à des échantillons probabilistes.
Gain de Temps : Le temps d'exécution est dominé par l'inférence LLM initiale. La compilation et l'échantillonnage des programmes probabilistes se font sur CPU et sont négligeables en temps comparé aux appels GPU.
Correction d'Erreurs : Les exemples qualitatifs montrent que PPoT corrige efficacement des erreurs courantes (ex: dimensions de tableaux incorrectes dans matplotlib, erreurs de calcul arithmétique, opérateurs mal choisis) en explorant les alternatives probables que le LLM avait envisagées mais n'avait pas sélectionnées.

5. Signification et Impact

Ce travail ouvre une nouvelle direction de recherche en traitant les générations de code des LLM non pas comme des sorties statiques, mais comme des abstractions probabilistes.

Efficacité : PPoT permet de "débloquer" le potentiel de calcul des LLM en utilisant le CPU pour explorer l'incertitude du modèle, rendant le raisonnement complexe beaucoup moins coûteux.
Généralité : La méthode s'applique à tout type de sortie structurée vérifiable (code, objets Python, formules mathématiques).
Futur : Les auteurs envisagent d'étendre cette approche à des structures de contrôle plus complexes (boucles, conditions) et à des sous-expressions entières, permettant des requêtes probabilistes plus riches (calcul d'espérance, conditionnement) avec un nombre minimal d'appels au modèle.

En résumé, Probabilistic Programs of Thought propose un changement de paradigme : au lieu de demander au LLM de "deviner" plusieurs fois la bonne réponse (coûteux), on lui demande une fois de fournir une carte des probabilités, puis on utilise des algorithmes probabilistes légers pour naviguer sur cette carte et trouver la solution optimale.