📊 statistics

More Bang for the Buck: Improving the Inference of Large Language Models at a Fixed Budget using Reset and Discard (ReD)

Cet article introduit Reset-and-Discard (ReD), une stratégie de requête qui optimise la couverture des questions uniques résolues par les grands modèles de langage au sein d'un budget fixe en atténuant les rendements décroissants de l'échantillonnage pass@k grâce à une allocation basée sur la loi de puissance.

Auteurs originaux : Sagi Meir, Tommer D. Keidar, Noam Levi, Shlomi Reuveni, Barak Hirshberg

Publié 2026-06-09

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Sagi Meir, Tommer D. Keidar, Noam Levi, Shlomi Reuveni, Barak Hirshberg

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

La vue d'ensemble : Le problème du « Jeu de devinettes »

Imaginez que vous avez un grand sac d'énigmes (questions) et un montant d'argent limité pour acheter des tentatives auprès d'un ami intelligent mais parfois têtu (un Grand Modèle de Langage ou LLM). Votre objectif n'est pas seulement de résoudre une seule énigme vraiment difficile ; votre objectif est de résoudre autant d'énigmes différentes que possible avant de manquer d'argent.

Le papier traite d'une erreur courante que les gens commettent en jouant à ce jeu.

L'ancienne méthode : « Le joueur têtu » (Résolution jusqu'à complétion)

Actuellement, la plupart des gens utilisent une stratégie que les auteurs appellent « Solve-to-Completion » (Résoudre jusqu'à complétion).

Comment ça marche : Vous choisissez l'Énigme n°1. Vous demandez une réponse à votre ami. S'il se trompe, vous demandez encore. Et encore. Et encore. Vous continuez à demander l'Énigme n°1 jusqu'à ce qu'il la réussisse enfin. Ce n'est qu'alors que vous passez à l'Énigme n°2.
Le problème : Certaines énigmes sont vraiment, vraiment difficiles. Votre ami pourrait rester bloqué sur l'Énigme n°1 pendant 50 tentatives. Au moment où il finit par la résoudre, vous avez déjà dépensé 50 tentatives. Il ne vous reste plus aucune tentative pour les énigmes n°2 à n°100. Vous avez résolu une chose difficile, mais vous avez manqué 99 choses faciles.
Le résultat : À mesure que vous dépensez plus d'argent, le nombre de nouvelles énigmes résolues augmente de plus en plus lentement. C'est comme essayer de remplir un seau avec un tuyau qui fuit ; plus vous poussez fort, moins l'eau entre réellement.

La nouvelle méthode : « L'explorateur en largeur » (Reset-and-Discard / ReD)

Les auteurs proposent une nouvelle stratégie appelée Reset-and-Discard (ReD) (Réinitialiser et Écarter).

Comment ça marche :
1. Vous choisissez l'Énigme n°1 et vous posez la question à votre ami une seule fois.
2. S'il réussit, vous célébrez, vous jetez l'énigme (Discard) et vous passez à l'Énigme n°2.
3. S'il échoue, vous ne continuez pas. Vous arrêtez immédiatement, vous mettez cette énigme de côté pour l'instant, et vous passez à l'Énigme n°2.
4. Vous parcourez toute la liste d'énigmes, en posant chaque question exactement une fois (ou quelques fois).
5. Une fois que vous avez parcouru toute la liste, vous revenez au début pour essayer celles qui n'ont pas encore été résolues.
L'analogie : Imaginez que vous êtes un pompier essayant d'éteindre de nombreux petits incendies. Au lieu de rester devant un feu tenace et de projeter de l'eau dessus jusqu'à ce qu'il soit éteint (en ignorant les autres incendies qui se propagent à proximité), vous projetez un peu d'eau sur chaque feu. Si un feu s'éteint, vous le laissez tranquille. S'il brûle encore, vous y revenez plus tard.
Le résultat : Vous résolvez un énorme nombre d'énigmes très rapidement. Même si vous ne résolvez pas les plus difficiles immédiatement, vous résolvez tous les problèmes faciles et moyens en premier. Cela vous donne un bien meilleur « rendement pour votre argent ».

La science derrière la magie

Le papier utilise les mathématiques pour prouver pourquoi cela fonctionne si bien.

La loi de puissance : Les auteurs ont remarqué que pour ces modèles d'IA, la probabilité de résoudre un problème chute selon un motif mathématique spécifique (une « loi de puissance »). En gros, plus le problème est difficile, plus il devient exponentiellement difficile à résoudre.
Le piège des « rendements décroissants » : Sous l'ancienne méthode du « Joueur têtu », cette mathématique signifie qu'à mesure que vous dépensez plus d'argent, vous obtenez de moins en moins de nouveaux problèmes résolus.
La solution : La méthode « Reset-and-Discard » brise ce piège. Les mathématiques montrent qu'en réinitialisant après chaque tentative (ou quelques tentatives), vous transformez cette croissance lente et décroissante en une croissance linéaire et constante. Vous obtenez un flux constant de problèmes résolus, quel que soit le nombre de tentatives effectuées.

Principales conclusions des expériences

Les auteurs ont testé cela sur de vrais modèles d'IA (comme Llama et GPT) en utilisant trois types de défis :

Codage : Écrire des programmes informatiques.
Mathématiques : Résoudre des problèmes mathématiques textuels.
Raisonnement : Répondre à des questions complexes à choix multiples.

Ce qu'ils ont découvert :

Plus de solutions : Avec le même budget, ReD a résolu significativement plus de problèmes uniques que l'ancienne méthode.
Moins cher : Pour atteindre un objectif spécifique (comme résoudre 80 % des problèmes), ReD a nécessité moins de tentatives, moins de jetons informatiques (tokens) et moins d'argent réel.
Fonctionne avec des vérificateurs imparfaits : Même si le système qui vérifie les réponses fait des erreurs (disant parfois « faux » quand c'est « vrai », ou inversement), ReD gagne toujours.
Prédire l'avenir : Les auteurs ont également montré qu'en utilisant ReD, vous pouvez en fait déterminer à quel point l'IA est intelligente (son « exposant de loi de puissance ») sans avoir à effectuer des milliers de tests coûteux. C'est comme être capable de deviner la vitesse d'une voiture simplement en la regardant rouler pendant quelques secondes, plutôt que de chronométrer une course entière.

L'essentiel à retenir

Si vous avez un budget fixe pour amener une IA à résoudre une liste de problèmes, ne vous acharnez pas sur les problèmes difficiles. À la place, essayez chaque problème une fois, écartez ceux que vous avez résolus, et revenez vers ceux que vous avez manqués. Cette stratégie de « Réinitialisation et Écart » (Reset-and-Discard) vous permet de résoudre bien plus de problèmes pour le même prix, transformant un processus lent et frustrant en une machine efficace et à haute vitesse.

Résumé technique : Reset and Discard (ReD) pour l'inférence de LLM

Énoncé du problème

Les grands modèles de langage (LLM) sont de plus en plus évalués sur des tâches vérifiables (ex. : codage, mathématiques, preuves formelles) en utilisant la métrique pass@k, qui mesure la probabilité de résoudre correctement une instance unique en $k$ tentatives. Les observations empiriques indiquent que pour de nombreuses tâches, le taux d'échec ( $1 - \text{pass@k}$ ) décroît selon une loi de puissance par rapport à $k$ (c'est-à-dire $1 - \text{pass@k} \propto k^{-\alpha}$ ).

Cependant, dans les scénarios d'inférence pratique avec un budget global fixe (mesuré en tentatives, en tokens ou en USD), l'objectif pertinent n'est pas le taux de succès sur un seul problème, mais la couverture@coût (coverage@cost) : le nombre attendu de problèmes uniques résolus compte tenu d'une contrainte de ressources totale. La politique d'allocation standard, résolution jusqu'à complétion (solve-to-completion) — qui consiste à échantillonner de manière répétée un même problème jusqu'à sa résolution avant de passer au suivant — est inefficace sous des distributions de difficulté de type loi de puissance. Parce que les problèmes difficiles consomment un nombre disproportionné de tentatives, cette politique conduit à une croissance sous-linéaire de la couverture@coût lorsque l'exposant de la loi de puissance $\alpha < 1$ (un constat empirique courant). Cela entraîne des rendements décroissants, où un budget supplémentaire produit de moins en moins de problèmes résolus.

Méthodologie : Reset-and-Discard (ReD)

Les auteurs proposent Reset-and-Discard (ReD), une politique d'allocation qui optimise le débit global en traitant le processus d'inférence comme une recherche en largeur (breadth-first search) à travers un ensemble de problèmes.

Le protocole ReD

Reset (Réinitialisation) : Au lieu de persister sur un seul problème jusqu'à sa résolution, le système tente chaque problème pour un nombre fixe d'essais $\tau$ (dans le cas optimal, $\tau=1$ , c'est-à-dire à chaque tentative).
Discard (Élimination) : Si un problème est résolu en $\tau$ tentatives, il est immédiatement retiré de la file d'attente.
Rotation : Si un problème n'est pas résolu après $\tau$ tentatives, il est renvoyé à la fin de la file d'attente, et le système passe immédiatement au problème suivant disponible.

Cadre théorique

L'article établit une correspondance mathématique entre pass@k et couverture@coût en utilisant la théorie du renouvellement.

Politique standard : Pour une distribution de difficulté où $P(p) \sim p^{\alpha-1}$ (menant à un pass@k suivant une loi de puissance), le nombre attendu de tentatives pour résoudre un problème, $E[T]$ , diverge si $\alpha < 1$ . Par conséquent, la croissance de la couverture@coût est sous-linéaire ( $\propto t^\alpha$ ).
Politique ReD : En réinitialisant toutes les $\tau$ $τ$ tentatives, le nombre effectif de tentatives pour résoudre un problème, $E[T_\tau]$ $E [T_{τ}]$ , devient fini quelle que soit la distribution de difficulté sous-jacente.
- Si $0 < \alpha < 1$ , ReD transforme la croissance de la couverture@coût de sous-linéaire à linéaire ( $\propto t$ ).
- Si $\alpha > 1$ , ReD maintient une croissance linéaire mais avec une pente plus raide (une efficacité supérieure) que la politique standard.
Optimalité : Les auteurs prouvent que réinitialiser à chaque tentative ( $\tau=1$ ) est la stratégie optimale pour minimiser le nombre attendu de tentatives par problème résolu pour toute distribution de difficulté. Cela reste vrai même avec des vérificateurs imparfaits, à condition que la somme des taux de faux négatifs et de faux positifs soit inférieure à 1.

Inférence des lois d'échelle

L'article démontre également que les trajectoires ReD peuvent être utilisées pour inférer l'exposant de la loi de puissance $\alpha$ sans nécessiter d'évaluations coûteuses à grand $k$ . À mesure que ReD progresse à travers les cycles, la distribution des problèmes non résolus converge vers une distribution Beta. En analysant le ratio de problèmes restants entre les cycles, $\langle R_n \rangle / \langle R_{n+1} - R_n \rangle$ , on peut estimer linéairement $\alpha$ .

Contributions clés

Connexion des métriques : A établi une correspondance exacte entre pass@k et couverture@coût, caractérisant comment le comportement de pass@k suivant une loi de puissance ( $0 < \alpha < 1$ ) induit une croissance sous-linéaire dans les schémas d'allocation standard.
Algorithme ReD : Propose et prouve l'optimalité de la stratégie Reset-and-Discard. Elle garantit une croissance linéaire de la couverture@coût pour $\alpha < 1$ et améliore l'efficacité pour $\alpha > 1$ .
Garanties théoriques : Prouve que ReD maximise strictement la récompense attendue par tentative pour toute distribution de difficulté et reste robuste face au bruit du vérificateur.
Inférence de l'exposant : Développe une méthode pour estimer les exposants de mise à l'échelle de l'inférence directement à partir des exécutions ReD, évitant ainsi le besoin d'échantillonnages coûteux à grand $k$ .
Validation empirique : Démontre des améliorations substantielles sur trois LLM (Llama-3.1-8b, Llama-3.3-70b, GPT-oss-20b) et trois benchmarks (HumanEval, GSM8K, MMLU-Pro).

Résultats expérimentaux

Les expériences ont été menées sur le jeu de données HumanEval (codage), GSM8K (mathématiques) et MMLU-Pro (raisonnement).

Efficacité : ReD a considérablement réduit le nombre de tentatives, de tokens et le coût en USD requis pour atteindre une couverture cible par rapport à la méthode de résolution jusqu'à complétion.
Comparaison de modèles : Sur le benchmark HumanEval, l'application de ReD à un modèle plus petit (Llama-3.1-8b) a surpassé l'allocation standard d'un modèle beaucoup plus grand (Llama-3.3-70b) en termes de tentatives et de tokens jusqu'à environ 90 % de couverture. En termes de coût USD, la stratégie ReD sur le modèle 8b était la plus rentable sur tous les niveaux de couverture.
Inférence de la loi d'échelle : En utilisant ReD sur le modèle 8b, les auteurs ont réussi à inférer un exposant de loi de puissance $\alpha \approx 0,34$ , ce qui correspond à l'exposant dérivé des mesures de pass@k à grand $k$ .
Robustesse : L'avantage de ReD a été maintenu même en simulant des vérificateurs bruités.

Signification et revendications

L'article soutient que ReD offre un changement fondamental dans la manière dont le calcul d'inférence est alloué pour les tâches vérifiables.

De "Paiement par Token" à "Résultat en tant que Service" : ReD permet aux systèmes de concentrer les ressources de calcul sur le "frontière de l'apprenabilité" (les problèmes qui sont solubles en quelques tentatives) plutôt que de gaspiller des ressources sur des instances difficiles qui présentent des rendements décroissants.
Routage hiérarchique : La méthodologie supporte des stratégies hybrides efficaces où de petits modèles gèrent l'essentiel des problèmes via ReD, et seuls les problèmes non résolus sont routés vers des modèles plus grands et plus coûteux.
Applicabilité générale : L'approche est applicable à tout pipeline supportant l'échantillonnage répété et la vérification, offrant une amélioration prouvable du débit sans nécessiter de modifications de l'architecture ou de l'entraînement du modèle.

Les auteurs font preuve de modestie quant à la portée de leurs travaux, notant que ReD est conçu spécifiquement pour les tâches vérifiables où la correction des solutions peut être automatiquement évaluée. Ils ne prétendent pas à une applicabilité aux tâches de génération non vérifiables et ne proposent pas d'intégration de prédicteurs de difficulté appris dans le cadre de ce travail.