Résumé technique : Estimation instance-optimale avec plusieurs juges LLM sous contrainte budgétaire

1. Formulation du problème

L'article aborde le défi de l'évaluation des modèles de langage (LLM) dans le cadre du « LLM-as-a-judge » sous des contraintes budgétaires strictes. Dans ce contexte, il existe $K$ paires prompt-réponse (requêtes) à évaluer par $J$ juges LLM disponibles. Chaque juge $j$ a un coût de requête connu $c_j$, mais la fiabilité de leurs évaluations varie. Plus précisément, la variance $\sigma^2_{k,j}$ du score fourni par le juge $j$ sur la requête $k$ est inconnue et hétéroscédastique (dépendante à la fois du juge et de la difficulté intrinsèque de la requête).

L'objectif est d'allouer de manière adaptative un budget total fixe $B$ parmi les $K \times J$ paires requête-juge afin d'estimer le vecteur de scores vrai $s \in \mathbb{R}^K$ avec la plus grande précision possible. La précision est mesurée en minimisant l'erreur $\ell_p$ ($\|\hat{s} - s\|_p$) pour un $p \in [1, \infty]$ fixe. Le problème est formalisé comme une estimation multi-juges hétéroscédastique sous contrainte budgétaire, une généralisation consciente des coûts de l'allocation de Neyman où les variances sont inconnues et les scores sont bornés dans un intervalle connu $[0, R]$.

2. Méthodologie

Allocation Oracle (variances connues)

Les auteurs analysent d'abord l'estimateur pondéré par l'inverse de la variance (IVWE) en supposant que les variances $\sigma^2_{k,j}$ sont connues. Ils dérivent l'allocation oracle qui minimise le taux d'erreur de l'IVWE.

• Idée clé : L'allocation optimale est sparse. Pour chaque requête $k$, l'intégralité du budget alloué à cette requête doit être attribuée à un seul juge « optimal » $j^*(k)$ qui minimise le produit du coût et de la variance : $j^*(k) = \arg\min_j c_j \sigma^2_{k,j}$.
• Règle d'allocation : Le budget est réparti entre les requêtes de sorte que le poids d'allocation $\omega^*_{k, j^*(k)}$ soit proportionnel à $(c_{j^*(k)} \sigma^2_{k, j^*(k)})^{\frac{p}{p+2}}$. Cela généralise des travaux antérieurs (par exemple, Saha et al., 2026) qui étaient limités à $p=\infty$ et à un seul juge.

Algorithme adaptatif : EST-IVWE (variances inconnues)

Puisque les variances sont inconnues en pratique, l'article propose EST-IVWE, un algorithme adaptatif en deux étapes :

1. Phase I (Exploration forcée) : L'algorithme interroge chaque paire $(k, j)$ un nombre fixe de fois ($N_0$) pour calculer des estimations de variance empiriques $\hat{\sigma}^2_{k,j}$.
2. Phase II (Allocation) : Le budget restant est alloué en fonction de l'allocation optimale empirique dérivée de ces estimations.
   • Innovation technique : Pour gérer l'instabilité des estimations de variance près de zéro (ce qui causerait des problèmes numériques dans la formule d'allocation), l'algorithme utilise un estimateur de variance biaisé de manière optimiste $\bar{\sigma}_{k,j} = \hat{\sigma}_{k,j} + \tau$. Ce biais stabilise l'allocation pour les paires « faciles à évaluer » (faible variance) sans affecter significativement le taux d'erreur asymptotique.
   • Séparation des échantillons : Les échantillons utilisés pour l'estimation de la variance dans la Phase I ne sont pas réutilisés pour l'estimation finale de la moyenne dans la Phase II. Cela découple l'aléatoire des estimations de variance de celui des estimations de moyenne, garantissant que l'estimateur final reste sans biais conditionnellement aux estimations de variance.

Bornes inférieures théoriques

L'article établit des bornes inférieures minimax locales pour prouver l'optimalité instance de EST-IVWE.

• Limitation de l'inégalité de Fano : Les auteurs démontrent que les bornes inférieures standard à haute probabilité basées sur des arguments de packing de type Fano sont trop grossières pour ce problème. Elles échouent à capturer la structure de variance locale requise pour une allocation optimale, produisant des taux sous-optimaux pour $p < \infty$.
• Argument de type Assouad : À la place, les auteurs emploient un argument de type Assouad en espérance basé sur des perturbations locales. Cette technique préserve la structure de variance locale et produit une borne inférieure précise qui correspond à la borne supérieure de EST-IVWE à des termes d'ordre inférieur près. Cela prouve que l'algorithme est instance-optimal.

3. Contributions clés

1. Formalisation du problème : Définition du problème d'estimation multi-juges hétéroscédastique sous contrainte budgétaire, étendant l'allocation de Neyman à des contextes avec des variances inconnues, hétéroscédastiques et des scores bornés.
2. Analyse Oracle : Dérivation de l'allocation sparse optimale pour l'IVWE sous variances connues, montrant que le budget doit être concentré sur le seul meilleur juge par requête.
3. Algorithme adaptatif : Proposition de EST-IVWE, un algorithme adaptatif qui atteint le taux d'erreur oracle sans connaissance préalable des variances, utilisant un biais optimiste et une séparation des échantillons pour gérer des scores bornés et non gaussiens.
4. Bornes inférieures précises : Démonstration d'une borne inférieure minimax locale correspondante en utilisant un cadre de type Assouad en espérance, établissant l'optimalité instance de la méthode proposée. L'article souligne que les arguments de type Fano sont insuffisants pour capturer la géométrie d'allocation précise dans ce contexte.
5. Validation empirique : Validation de l'approche sur des données synthétiques et le jeu de données réel HelpSteer2, démontrant des améliorations significatives par rapport à une allocation uniforme naïve.

4. Résultats

• Performance théorique : Le taux d'erreur de EST-IVWE correspond au terme dominant du taux IVWE Oracle (qui suppose des variances connues) à des termes d'ordre inférieur près dans le budget $B$. Plus précisément, pour $p \ge 2$, l'erreur évolue en $O(\sqrt{A^*_p/B})$, où $A^*_p$ est l'objectif d'allocation optimal.
• Performance empirique : Les expériences sur des données synthétiques ($K=1000, J=10$) et le jeu de données HelpSteer2 ($K \approx 178, J=3$) montrent que EST-IVWE surpasse systématiquement l'allocation uniforme et converge rapidement vers la performance de la stratégie Oracle à mesure que le budget augmente.
• Robustesse : L'algorithme reste robuste face à différentes structures de coûts (par exemple, lorsque les juges à variance élevée sont moins chers) et différentes normes d'erreur ($\ell_1, \ell_2, \ell_\infty$).

5. Importance et affirmations

L'article prétend fournir une solution théorique et algorithmique complète au problème de l'évaluation sous contrainte budgétaire avec plusieurs juges hétérogènes. Son importance principale réside dans :

• Optimalité instance : La preuve que la stratégie adaptative proposée est théoriquement optimale pour toute instance de problème spécifique (définie par le profil de variance), et pas seulement dans un sens de pire cas.
• Insight méthodologique : La démonstration que les techniques standard de bornes inférieures à haute probabilité (Fano) sont inadéquates pour les problèmes où l'allocation optimale dépend de structures de variance locales fines, et que des arguments en espérance (Assouad) sont nécessaires pour dériver des bornes précises.
• Utilité pratique : Offre d'un algorithme pratique en deux étapes ne nécessitant aucune connaissance préalable de la fiabilité des juges, le rendant immédiatement applicable aux pipelines d'évaluation LLM réels où les coûts et les variances varient.

Les auteurs notent que, bien que leur cadre soit motivé par le LLM-as-a-judge, il aborde une classe plus large de problèmes d'allocation de ressources adaptative. Ils reconnaissent que l'extension du cadre à des coûts stochastiques (par exemple, dépendant de la longueur des tokens) et l'intégration de modèles de biais des juges sont des pistes de travail futur, et que la dérivation d'une borne inférieure à haute probabilité correspondante reste un défi théorique ouvert.