🤖 machine learning

Sketch-and-Verify: Structured Inference-Time Scaling via Program Sketching

L'article présente Sketch-and-Verify, une stratégie de mise à l'échelle au moment de l'inférence rentable pour les petits modèles de code qui surpasse l'échantillonnage plat en énumérant des esquisses algorithmiques diverses et en les remplissant avec plusieurs candidats, bien qu'elle ne puisse pas entièrement remplacer les performances des niveaux de modèles plus puissants.

Auteurs originaux : Shan Jiang, Zijian Yi, Chenguang Zhu

Publié 2026-05-12

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Shan Jiang, Zijian Yi, Chenguang Zhu

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 de résoudre un casse-tête difficile, mais que vous n'avez à votre disposition qu'un petit robot peu coûteux pour vous aider. Ce robot est rapide et bon marché, mais il a une mauvaise habitude : lorsqu'il tente de résoudre un problème, il choisit presque toujours la même mauvaise façon de penser. Si vous lui demandez d'essayer 100 fois, il ne vous donnera que 100 versions légèrement différentes de cette même mauvaise réponse.

C'est le problème que l'article "Sketch-and-Verify" (Esquisser et Vérifier) tente de résoudre. Il propose une nouvelle façon d'utiliser ce petit robot peu coûteux afin qu'il puisse résoudre plus de problèmes sans avoir besoin de passer à un robot géant et extrêmement cher.

Voici comment fonctionne la méthode, décomposée en étapes simples :

1. Le Problème : « Toujours la même chanson »

Habituellement, lorsque nous demandons à une IA d'écrire du code, nous disons simplement : « Essayez 100 fois et donnez-moi la meilleure version. »

Le défaut : Si l'idée « par défaut » de l'IA est erronée, lui demander d'essayer 100 fois revient à demander à une personne d'écrire 100 versions différentes d'une mauvaise chanson. Vous pourriez changer les paroles ou le tempo, mais la mélodie reste fausse. L'IA reste coincée dans une boucle de changements « cosmétiques » (changer les noms de variables ou la mise en forme) sans jamais essayer une approche fondamentalement différente.

2. La Solution : « L'Architecte et le Constructeur »

Les auteurs proposent un processus en deux étapes appelé Sketch-and-Verify. Au lieu de demander à l'IA d'écrire tout le code immédiatement, ils divisent le travail en deux rôles :

Étape 1 : L'Architecte (L'Esquisse)
D'abord, ils demandent à l'IA d'agir comme un architecte. Ils disent : « N'écrivez pas encore le code. Listez simplement 5 façons complètement différentes de résoudre ce problème. »
- Exemple : « Stratégie A : Utiliser une carte. Stratégie B : Trier la liste d'abord. Stratégie C : Utiliser une boucle. »
- Une fois que l'IA a choisi une stratégie, elle dessine une « ébauche » grossière (un sketch) avec des trous. L'ébauche contient la structure principale (les murs et le toit) mais laisse les détails spécifiques (la couleur de la peinture, la poignée de porte) comme des espaces vides marqués ??.
- Pourquoi cela aide : Cela force l'IA à s'arrêter et à réfléchir à des chemins différents avant de commencer à construire. Cela garantit que l'IA explore différents « quartiers » de solutions au lieu de simplement tourner en rond dans le même.
Étape 2 : Le Constructeur (Le Remplissage)
Maintenant, pour chaque ébauche, l'IA agit comme un constructeur. Elle remplit les trous ?? pour créer un programme complet.
- Si l'IA a créé 5 ébauches (stratégies) et rempli chacune d'elles 10 fois, elle dispose désormais de 50 programmes complètement différents à tester.
- Parce que les ébauches étaient différentes, ces 50 programmes sont structurellement diversifiés. Ils ne sont pas de simples réécritures de la même idée ; ce sont des approches véritablement différentes.
Étape 3 : L'Inspecteur (Vérification)
Enfin, ils exécutent tous ces programmes à travers un test. Ils conservent ceux qui fonctionnent et choisissent le meilleur.

3. Les Résultats : Bon marché vs Cher

Les chercheurs ont testé cette méthode sur un test de codage standard appelé HumanEval+ en utilisant trois versions de l'IA Gemini de Google :

Lite : Le petit modèle, peu coûteux et rapide.
Flash : Le modèle moyen.
Pro : Le grand modèle, cher et intelligent.

Les grandes découvertes :

Pour le robot bon marché (Lite) : La méthode « Sketch-and-Verify » a été un véritable jeu de bascule.
- S'ils demandaient simplement au robot Lite d'essayer 100 fois normalement (Échantillonnage plat), il résolvait environ 53 % des problèmes difficiles.
- S'ils utilisaient la méthode Sketch-and-Verify (créant 10 ébauches et les remplissant 10 fois), il résolvait 79 % des problèmes difficiles.
- L'analogie : C'est comme dire à un étudiant : « Ne rédigez pas simplement 100 essais sur le même sujet. Écrivez 10 plans pour 10 sujets différents, puis remplissez-les. » L'étudiant apprend davantage et obtient une meilleure note pour le même effort.
Pour le robot cher (Pro) : La méthode n'a pas beaucoup aidé.
- Le robot Pro est déjà si intelligent que son idée « par défaut » est généralement bonne. Le forcer à esquisser différentes stratégies l'a en fait rendu légèrement moins performant car cela l'a distrait de son meilleur instinct.
- La règle : Si vous avez un robot super-intelligent, laissez-le simplement réfléchir intensément (Greedy). Si vous n'avez qu'un robot bon marché, utilisez Sketch-and-Verify pour le forcer à penser de manière créative.

4. La Conclusion

L'article soutient que Sketch-and-Verify est une façon intelligente de dépenser des ressources informatiques supplémentaires lorsque vous êtes contraint d'utiliser un modèle d'IA plus petit et moins cher.

Ce n'est pas magique : Cela ne rend pas un modèle faible plus fort qu'un modèle fort. Si vous pouvez vous permettre le modèle cher « Pro », utilisez simplement celui-ci.
C'est une stratégie : Si vous devez utiliser le modèle bon marché (en raison du budget ou de la vitesse), cette méthode est le meilleur moyen d'extraire des performances supplémentaires de celui-ci. Elle empêche l'IA de rester coincée dans une routine et la force à explorer différentes solutions, un peu comme une séance de brainstorming humaine.

En bref : Ne demandez pas simplement à l'IA d'essayer plus fort ; demandez-lui d'essayer différemment.

Résumé Technique : Sketch-and-Verify : Mise à l'échelle structurée du temps d'inférence par esquissage de programmes

1. Énoncé du Problème

L'article aborde une contrainte opérationnelle spécifique rencontrée par les praticiens : étant donné un modèle de code fixe, petit et rentable (par exemple, Gemini 3.1 Flash Lite) choisi pour des raisons de latence ou de budget, comment doit-on allouer une quantité limitée de calcul supplémentaire au moment du test pour améliorer la précision ?

Les approches standard impliquent un échantillonnage plat (génération de $N$ programmes candidats indépendants et sélection du meilleur via exécution). Les auteurs soutiennent que l'échantillonnage plat est inefficace car il traite l'espace des programmes comme homogène. Les grands modèles de langage (LLM) attribuent souvent une masse de probabilité élevée à une seule stratégie algorithmique « modale ». Par conséquent, même avec une température élevée ou un grand $N$ , le pool de candidats résultant manque de diversité structurelle ; il se compose principalement de variantes cosmétiques superficielles (différents noms de variables, mise en forme) des mêmes 2 à 3 stratégies. Si la stratégie par défaut du modèle est incorrecte pour un problème spécifique, l'échantillonnage plat échouera probablement à découvrir la solution correcte, indépendamment du nombre d'échantillons.

2. Méthodologie : SKETCHVERIFY

Les auteurs proposent SKETCHVERIFY, une méthode qui restructure le calcul du temps d'inférence en factorisant l'espace de recherche en stratégie algorithmique et détails d'implémentation. Inspirée par l'esquissage de programmes (Solar-Lezama, 2008, 2013) et des travaux antérieurs sur les tests de compilateurs pilotés par LLM (OBsmith, Jiang et al., 2026b), la méthode opère en quatre étapes :

Étape 1 : Génération d'esquisses (Prompting de catégorie en premier)
- Énumération de catégories : Le LLM est invité à lister $K$ stratégies algorithmiques fondamentalement différentes (par exemple, « table de hachage », « deux pointeurs », « programmation dynamique ») en langage naturel. Cela force le modèle à raisonner sur l'espace des stratégies avant de coder.
- Esquissage : Pour chaque stratégie, le LLM génère un programme partiel (une « esquisse ») où l'algorithme, les structures de données et le flux de contrôle sont entièrement spécifiés, mais où les détails d'implémentation (expressions, conditions, bornes de boucle) sont remplacés par des espaces réservés ??. L'objectif est de 4 à 8 trous par esquisse.
- Innovation clé : Ce processus en deux étapes empêche le modèle autorégressif de se fixer sur une seule stratégie par défaut, assurant une diversité structurelle à travers les $K$ esquisses.
Étape 2 : Remplissage
- Chaque esquisse valide est remplie $M$ fois pour produire $K \times M$ programmes candidats complets.
- Pour encourager la variation au sein d'une seule esquisse, chaque troisième remplissage est conditionné par le remplissage précédent et invité à fournir une implémentation différente.
Étape 3 : Vérification
- Les candidats sont filtrés pour la compilation et l'exécution sans plantage.
- Les candidats survivants sont exécutés sur $D$ entrées de test diverses (générées via une approche similaire basée sur l'esquissage).
- Une empreinte d'exécution est générée pour chaque candidat : un vecteur de paires (statut, sortie). Des empreintes identiques indiquent une équivalence comportementale.
Étape 4 : Sélection
- Les candidats sont regroupés par leurs empreintes d'exécution.
- Le plus grand cluster (représentant le consensus comportemental le plus robuste) est sélectionné.
- À partir du plus grand cluster, le programme le plus court est renvoyé (rasoir d'Occam). Cette règle de sélection est identique à la ligne de travail concurrente « Semantic Voting », isolant ainsi le bénéfice de la génération structurée du mécanisme de sélection.

3. Contributions Clés

Cadre SKETCHVERIFY : Introduit une politique coût-performance au sein d'un niveau qui applique l'esquissage de programmes à la mise à l'échelle du temps d'inférence. Il factorise l'espace de recherche en $K$ (stratégies) et $M$ (implémentations), atteignant une courbe de mise à l'échelle pass@1 plus raide que l'échantillonnage plat sur des modèles faibles.
Analyse Pareto Coût-Qualité : Fournit une analyse rigoureuse sur le benchmark HumanEval+, réanalysant spécifiquement un « sous-ensemble difficile » de 19 problèmes où le modèle de base Lite (glouton) échoue.
- Au sein d'un niveau : L'esquissage domine l'échantillonnage plat pour des nombres de candidats équivalents. Sur le sous-ensemble difficile, Lite Sketch ( $K=2, M=5$ ) récupère 58 % des problèmes contre 26 % pour l'échantillonnage plat ( $N=10$ ). Même avec une augmentation de budget de 3x, l'échantillonnage plat ( $N=50$ ) n'atteint que 47 %, perdant toujours face à la configuration d'esquissage moins chère.
- Entre niveaux : L'esquissage ne remplace pas la mise à niveau du modèle. Des niveaux plus forts (par exemple, Gemini Pro glouton) dominent les configurations Lite+Sketch tant sur le coût que sur la précision. L'esquissage est un complément, et non un substitut, à la mise à niveau du niveau de modèle.
Décomposition Catégorie-En-Premier : Propose une stratégie de prompting spécifique (énumération des noms de stratégies avant le codage) qui est cruciale pour générer une diversité structurelle plutôt que des variantes cosmétiques.
Caractérisation du compromis K-vs-M : Grâce à des balayages de mise à l'échelle, les auteurs montrent que la relation entre $K$ et $M$ est non monotone. Les allocations mixtes (par exemple, $K=2, M=5$ ) surpassent souvent les extrêmes purement plats ( $K=1$ ) ou purement esquissés ( $M=1$ ), et augmenter simplement $K$ ne produit pas toujours des gains linéaires (par exemple, $K=5, M=10$ a sous-performé $K=2, M=5$ sur certaines métriques).
Composabilité : Démontre que la génération structurée s'associe proprement à une sélection basée sur l'exécution (Semantic Voting). La méthode agit comme un générateur d'un pool de candidats diversifié, tandis que le sélecteur reste agnostique à la méthode de génération.

4. Résultats Expérimentaux

Benchmarks : Évalué sur HumanEval+ (164 problèmes Python avec des suites de tests augmentées). Une validation inter-benchmarks sur MBPP+ et LiveCodeBench est notée comme travail futur.
Modèles : Trois niveaux de modèles Google Gemini (Pro, Flash, Flash Lite) à des niveaux de réflexion faibles.
Performance sur le Sous-ensemble Difficile (19 problèmes où Lite glouton échoue) :
- Lite Sketch ( $K=10, M=10$ ) : 79 % pass@1.
- Lite Flat ( $N=100$ ) : 53 % pass@1.
- Lite Sketch ( $K=2, M=5$ ) : 58 % pass@1 (à un coût inférieur à Flat $N=50$ ).
- Flash/Pro Glouton : Surpasse toutes les configurations Lite, confirmant que la capacité du modèle est le principal moteur de la précision.
Courbes de Mise à l'Échelle : Sur l'ensemble complet HumanEval+, l'échantillonnage plat Lite sature à ~89 % pass@1. SKETCHVERIFY brise ce plafond, atteignant 93 % à $K=10, M=10$ . Cependant, sur Flash et Pro, où les modèles sont proches de la saturation, les gains de l'esquissage sont marginaux ou inexistants par rapport au décodage glouton.

5. Signification et Revendications

L'article positionne SKETCHVERIFY comme une politique coût-performance au sein d'un niveau, et non comme une amélioration universelle de la précision.

Règle pour le Praticien : Si un niveau de modèle plus fort est disponible, utilisez le décodage glouton sur ce niveau. Si vous êtes contraint à un modèle plus faible (en raison de la latence, du déploiement ou du budget), SKETCHVERIFY est le moyen le plus rentable de dépenser un calcul supplémentaire au moment du test.
Mécanisme : La méthode réussit en forçant explicitement l'exploration de différentes stratégies algorithmiques (diversité structurelle) plutôt que de compter sur la stochasticité de l'échantillonnage plat pour trouver accidentellement une nouvelle approche.
Limites : Les auteurs reconnaissent des limitations, notamment la dépendance à une seule famille de modèles (Gemini), un seul niveau de réflexion, et le fait que la qualité de l'esquisse est bornée par la propre distribution de stratégies du modèle (si le modèle ne peut pas concevoir la stratégie correcte, l'esquissage ne peut pas la générer). Ils notent également une surcharge de tokens d'environ 7 % pour la phase de génération d'esquisses.

L'article conclut que, bien que l'esquissage soit hautement efficace pour les modèles faibles luttant contre la diversité stratégique, il n'est pas une panacée pour les modèles qui ont déjà atteint leur plafond de capacité ou pour des problèmes où la stratégie correcte est entièrement en dehors des connaissances latentes du modèle.