🤖 machine learning

LLM Priors for ERM over Programs

Cet article introduit \textsc{LLM-PV}, un cadre de proposition et de vérification qui exploite les a priori des LLM pré-entraînés pour effectuer efficacement la minimisation du risque empirique sur des classes de programmes discrets sans énumération exhaustive ni mises à jour de gradient, permettant ainsi une généralisation robuste sur des tâches algorithmiques là où les méthodes traditionnelles échouent.

Auteurs originaux : Shivam Singhal, Priyadarsi Mishra, Eran Malach, Tomer Galanti

Publié 2026-07-03

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Shivam Singhal, Priyadarsi Mishra, Eran Malach, Tomer Galanti

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

Le gros problème : Trouver une aiguille dans une botte de foin

Imaginez que vous essayiez d'apprendre à un ordinateur une règle secrète. La règle est simple, du genre : « Si le nombre est divisible par 3, dis "Oui" ; sinon, dis "Non" ». Mais l'ordinateur ne connaît pas la règle ; il voit seulement quelques exemples de nombres et les réponses.

Dans le monde de l'informatique, il existe deux manières principales de tenter de trouver cette règle :

Le Détective de la « Force Brute » : Cette méthode tente d'écrire chaque règle possible de l'univers, une par une, et vérifie si elle correspond aux exemples.
- Le Problème : Si la règle est même légèrement complexe, le nombre de règles possibles est si immense (comme le nombre de grains de sable sur toutes les plages de la Terre) que cette méthode prendrait plus de temps que l'âge de l'univers pour se terminer. C'est trop lent.
L'Étudiant de la « Descente de Gradient » : C'est ainsi que l'IA moderne (comme les chatbots que vous utilisez) apprend habituellement. Elle commence par une supposition et ajuste lentement ses boutons internes pour s'améliorer, comme un étudiant qui étudie pour un examen en faisant de petites erreurs et en les corrigeant.
- Le Problème : Pour certains types de règles logiques (comme vérifier si un nombre est premier ou compter des motifs spécifiques), cette méthode de « réglage » se retrouve bloquée. L'étudiant peut mémoriser parfaitement l'examen blanc, mais échouer complètement face à une nouvelle question légèrement différente. C'est comme un étudiant qui a mémorisé les réponses sans avoir appris les mathématiques.

La Nouvelle Solution : LLM-PV (Le Bibliothécaire Intelligent)

Les auteurs proposent une troisième voie appelée LLM-PV. Considérez cela comme l'embauche d'un Bibliothécaire Intelligent pour vous aider à trouver la règle.

Voici comment le processus fonctionne, étape par étape :

La Proposition (La supposition du Bibliothécaire) : Au lieu de vérifier chaque livre de la bibliothèque (Force Brute) ou d'essayer de réécrire toute la bibliothèque à partir de zéro (Descente de Gradient), vous demandez au Bibliothécaire Intelligent (un Grand Modèle de Langage pré-entraîné) de vous faire quelques suggestions.
- La Magie : Le Bibliothécaire a lu des millions de livres et d'extraits de code. Lorsque vous lui montrez vos exemples, il ne devine pas au hasard. Il utilise son « intuition » (connaissance préalable) pour suggérer quelques règles plausibles qui pourraient fonctionner. Il réduit la recherche de « toutes les règles possibles » à « quelques candidats probables ».
La Vérification (L'essai routier) : Le Bibliothécaire écrit ces règles sous forme de véritable code informatique. Vous prenez ensuite ces extraits de code et vous les exécutez sur vos exemples pour voir lequel fonctionne réellement.
- Point Crucial : Le Bibliothécaire n'est pas autorisé à changer d'avis en fonction des résultats du test. Il se contente de faire des suggestions. La sélection du vainqueur est effectuée strictement en vérifiant le code par rapport aux données.
La Sélection (Le Vainqueur) : Vous choisissez l'extrait de code qui obtient le plus de bonnes réponses.

Pourquoi c'est une avancée majeure

Le papier démonte que cette approche du « Bibliothécaire Intelligent » est incroyablement efficace.

C'est Rapide : Il n'a pas besoin de vérifier des milliards de règles. Il ne vérifie qu'une poignée de suppositions intelligentes.
C'est Précis : Contrairement aux méthodes d'IA de « réglage » qui échouent souvent sur les puzzles logiques, cette méthode trouve la règle mathématique exacte (comme le test de primalité de Miller-Rabin pour vérifier les nombres premiers).
Cela Généralise : C'est la partie la plus impressionnante. Si vous enseignez le système avec des nombres courts (par exemple, 10 chiffres), il apprend la règle, pas seulement les nombres. Ainsi, quand vous lui demandez de vérifier un nombre de 100 chiffres, il fonctionne toujours parfaitement. L'IA de « réglage » échoue généralement ici, car elle est déroutée par les nombres plus longs.

Une analogie de la vie réelle : Apprendre à cuisiner

Imaginez que vous vouliez apprendre la recette secrète d'un gâteau.

Force Brute : Vous essayez de cuisiner un gâteau avec toutes les combinaisons possibles d'ingrédients (sel, sucre, sable, cailloux, etc.) jusqu'à ce que l'un d'eux ait le bon goût. Cela prend un temps infini.
Descente de Gradient (IA Standard) : Vous cuisinez un gâteau, vous le goûtez et vous dites : « Manque de sucre ». Vous cuisinez à nouveau : « Moins de farine ». Vous continuez ainsi. Finalement, vous pourriez faire un gâteau qui a le goût de celui que vous essayiez de copier, mais si vous changez la température du four ou la marque de la farine, votre gâteau s'effondre car vous avez seulement appris à imiter ce lot spécifique, et non le principe de la pâtisserie.
LLM-PV : Vous demandez à un Maître Chef (le LLM) qui a vu des millions de recettes. Vous lui montrez quelques indices sur le gâteau. Le Chef dit : « Je parie que c'est un gâteau au chocolat avec un mélange d'épices spécifique ». Ils écrivent trois recettes précises. Vous cuisinez ces trois recettes. L'une d'elles est parfaite. Vous n'avez pas eu besoin de cuisiner un million de gâteaux, et vous n'avez pas eu besoin de modifier la recette indéfiniment. Vous avez obtenu la vraie recette qui fonctionne pour n'importe quel four.

L'essentiel

Le papier soutient que nous ne devrions pas seulement utiliser l'IA pour prédire des réponses directement. Au lieu de cela, nous devrions utiliser l'IA comme un outil de recherche pour générer des solutions potentielles (des programmes), puis utiliser des tests stricts pour choisir la meilleure. Cela combine le « bon sens » d'un grand modèle de langage avec la fiabilité d'un programme informatique, permettant d'apprendre des règles complexes à partir de très peu d'exemples.

Résumé Technique : Les Priors des LLM pour l'ERM sur les Programmes

Énoncé du Problème

Le papier traite de la tension fondamentale entre l'efficacité d'échantillonnage et l'efficacité computationnelle lors de l'apprentissage de descriptions de programmes courts et discrets (par exemple, du "code Python") à partir de données étiquetées.

La théorie classique de l'apprentissage (PAC learning) suggère que si une fonction cible admet une description de programme courte de longueur $L$ sur un alphabet $\Sigma$ , elle peut être apprise à partir de $\tilde{O}(L \log |\Sigma|)$ exemples via l'Empirical Risk Minimization (ERM) (Minimisation du Risque Empirique) sur la classe des programmes. Cependant, implémenter l'ERM nécessite une énumération exhaustive des programmes candidats, ce qui est de l'ordre de $\Theta(|\Sigma|^L)$ , rendant la tâche computationnellement infaisable même pour un $L$ modéré.

À l'inverse, les approches modernes de deep learning utilisant la Descente de Gradient Stochastique (SGD) sur des réseaux de neurones à haute capacité évitent l'énumération explicite et sont efficaces sur le plan computationnel. Pourtant, des résultats théoriques dans le cadre des Requêtes Statistiques (SQ) indiquent que les méthodes basées sur le gradient peinent avec les familles structurées et "SQ-difficiles" (telles que les fonctions de parité et les primitives cryptographiques). Ces méthodes nécessitent souvent un nombre exponentiel d'exemples pour réussir, car l'interface de gradient est mal adaptée à la structure discrète de la règle cible, ce qui conduit à un échec de la généralisation au-delà des longueurs de séquences d'entraînement.

La question centrale est la suivante : Pouvons-nous récupérer l'efficacité d'échantillonnage de l'ERM sur des programmes courts sans payer le coût complet de l'énumération exhaustive ?

Méthodologie : LLM-PV

Les auteurs proposent LLM-PV (LLM Propose-and-Verify), un algorithme d'apprentissage qui traite un Grand Modèle de Langage (LLM) pré-entraîné non pas comme un prédicteur, mais comme un prior de recherche pour l'ERM.

L'Algorithme

LLM-PV sépare les rôles de proposition et de sélection :

Proposition (Le Prior) : Un LLM pré-entraîné est sollicité par un ensemble d'entraînement $S_{tr}$ pour induire une distribution dépendante des données sur des programmes candidats. Le LLM génère un petit nombre de programmes candidats (ou d'éditions) qui sont supposés expliquer les données.
Vérification (L'étape ERM) : Chaque programme candidat est compilé et exécuté sur un ensemble de validation tenu à l'écart $S_{val}$ . Les programmes qui échouent à la compilation, ne s'arrêtent pas ou produisent des sorties invalides sont rejetés.
Sélection : L'algorithme sélectionne le programme présentant l'erreur de validation la plus faible. Crucialement, aucune mise à jour de gradient n'est effectuée sur le LLM, et aucun retour de validation n'est utilisé pour adapter la distribution d'échantillonnage du LLM pendant la recherche. Le LLM agit uniquement comme un mécanisme de biais inductif.

Cadre Théorique

Les auteurs formalisent la performance de LLM-PV en utilisant une garantie de type "propose-and-verify". Si la distribution de proposition du LLM place une masse non négligeable $p_\epsilon(S_{tr})$ sur des programmes ayant une erreur de population $\le \epsilon$ , alors le nombre d'essais $k$ requis pour trouver une bonne hypothèse évolue comme $O(\log(1/\delta) / p_\epsilon(S_{tr}))$ . Cela remplace l'espace de recherche exponentiel $|\Sigma|^L$ par une taille de recherche effective de $1/p_\epsilon(S_{tr})$ .

Les auteurs fournissent également des bornes inférieures théoriques démontrant que pour les problèmes de $k$ -parité plantés, la SGD de coordonnées par mini-lots à précision finie nécessite $\Omega(\sqrt{N}/2^b)$ nouveaux exemples (où $N$ est le nombre de cibles possibles), tandis que l'énumération nécessite $\Theta(|\Sigma|^L)$ de temps. Cela établit un régime où tant l'énumération naïve que l'entraînement standard par gradient échouent, motivant l'approche LLM-PV.

Contributions Clés

Formalisation de la tension Calcul-Échantillon : Le papier isole un régime spécifique de petits échantillons (parité $k$ plantée) où l'ERM à classe finie est efficace en termes d'échantillonnage mais intraitable sur le plan computationnel, tandis que l'entraînement par gradient est pratique sur le plan computationnel mais inefficace en termes d'échantillonnage en raison de la difficulté SQ.
Algorithme LLM-PV : L'introduction d'un pipeline "propose-and-verify" clair qui utilise les LLM pré-entraînés strictement comme mécanisme de proposition. Cela préserve l'auditabilité et les garanties théoriques de l'ERM (sélection basée sur l'erreur de validation) tout en exploitant la capacité du LLM à concentrer la recherche sur des hypothèses plausibles.
Preuve Empirique de la Récupération de Règles : Des expériences approfondies à travers diverses tâches algorithmiques (variantes de parité, automates cellulaires, palindromes, Dyck-2, test de primalité, automates cellulaires et parité SHA-256) montrent que LLM-PV récupère souvent la règle sous-jacente exacte à partir de seulement 200 exemples étiquetés.
Généralisation de Longueur : Contrairement aux modèles transformeurs entraînés par SGD, aux modèles affinés (fine-tuned), ou aux bases d'apprentissage en contexte (ICL), qui mémorisent souvent les distributions d'entraînement et échouent à généraliser à des séquences d'entrée plus longues, LLM-PV synthétise fréquemment des programmes invariants de dimension qui se généralisent parfaitement à des longueurs d'entrée dépassant largement l'ensemble d'entraînement.
Auditabilité : La méthode produit du code exécutable et lisible par l'humain ainsi qu'une trace de raisonnement complète (la séquence de programmes proposés et leurs erreurs de validation), permettant un débogage direct et une validation mécaniste.

Résultats

Les auteurs ont évalué LLM-PV par rapport à un large éventail de bases, incluant le ML classique (XGBoost, SVM, Algorithmes Génétiques), le SGD-training (à partir de zéro et affiné) et l'In-Context Learning (ICL) avec de grands modèles optimisés pour les instructions.

Tâches Algorithmiques : Sur des tâches comme la 10-Parity, la Parité d'Automate Cellulaire et le test de primalité, les bases standards (y compris les modèles ICL de plus de 30B de paramètres) ont performé proche du hasard (5% de précision) aux longueurs de test ( $n=100$ ), même avec 200 exemples d'entraînement. En revanche, LLM-PV a atteint 100% de précision de test sur ces tâches avec les mêmes 200 exemples.
Généralisation : Lorsqu'ils sont entraînés sur des séquences courtes ( $n=10$ ) et testés sur des séquences longues ( $n=100$ ), les bases SGD et le fine-tuning s'effondrent vers une précision aléatoire. LLM-PV maintient une précision élevée, synthétisant avec succès des règles qui sont invariantes à la longueur d'entrée.
Échelle des Données : Augmenter la taille de l'ensemble d'entraînement pour les modèles basés sur le SGD (jusqu'à 100k exemples) n'a pas résolu l'échec de généralisation sur les tâches de parité et d'automates cellulaires, confirmant la nature SQ-difficile de ces problèmes pour les apprenants par gradient.
Utilisation d'Outils : Le papier note que bien que l'ICL augmenté par des outils (où le modèle peut exécuter du code) améliore les performances par rapport au simple prompting, il échoue toujours à récupérer de manière fiable les règles algorithmiques. Le succès de LLM-PV est attribué à l'objectif de recherche spécifique (proposer des programmes et sélectionner par erreur de validation) plutôt qu'à l'accès aux outils seul.
Données Tabulaires : Sur les benchmarks tabulaires standards, LLM-PV performe de manière comparable aux apprentisseurs tabulaires puissants, suggérant que l'approche n'est pas limitée aux tâches de séquences synthétiques.

Signification et Revendications

Le papier affirme que les priors des LLM pré-entraînés peuvent servir de biais de recherche efficaces pour l'ERM, comblant avec succès l'écart entre l'efficacité statistique et l'efficacité computationnelle dans l'apprentissage de programmes.

La signification centrale réside dans la séparation des rôles : le LLM est utilisé uniquement pour proposer des hypothèses, tandis que l'objectif d'apprentissage reste ancré dans la vérification exécutable et l'erreur de validation. Cette approche :

Évite la nature "boîte noire" des prédicteurs basés sur le gradient en produisant du code explicite et vérifiable.
Surmonte l'inefficacité d'échantillonnage des méthodes basées sur le gradient sur des tâches discrètes et structurées où la cible admet une description courte.
Fournit un mécanisme de généralisation de longueur que les méthodes classiques de deep learning ne parviennent pas à atteindre sur les tâches algorithmiques.

Les auteurs font preuve de modestie quant à la portée de l'étude, reconnaissant que la méthode repose sur la capacité du LLM à placer une masse suffisante sur les bons programmes et que l'approche est actuellement adaptée aux régimes de faibles données structurées plutôt qu'à servir de remplacement général à l'apprentissage supervisé sur des données non structurées. Le succès dépend de la capacité du "proposeur" et de la robustesse de l'étape de "vérification".