💬 NLP

Consistent and Distinctive: LLM Benchmark Efficiency via Maximum Independent Set Prompt Selection on Similarity Graphs

Cet article propose un cadre basé sur les graphes utilisant des algorithmes d'ensemble indépendant maximal pour sélectionner des sous-ensembles de prompts diversifiés et non redondants à partir de benchmarks de LLM, démontrant que de tels ensembles réduits maintiennent des classements de modèles hautement cohérents tout en réduisant considérablement les coûts d'évaluation.

Auteurs originaux : Denica Kjorvezir, Marko Djukanović, Ana Gjorgjevikj, Gjorgjina Cenikj, Tome Eftimov

Publié 2026-06-02

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Denica Kjorvezir, Marko Djukanović, Ana Gjorgjevikj, Gjorgjina Cenikj, Tome Eftimov

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 soyez un juge essayant de décider quel chef parmi 66 différents (des modèles de langage étendu ou LLM) est le meilleur cuisinier. Vous avez un livre de recettes massif contenant 1 000 recettes (le benchmark). Pour être équitable, vous voulez goûter un peu de tout. Mais cuisiner les 1 000 plats prend un temps infini, coûte une fortune et pourrait fausser les résultats si votre livre de recettes contient accidentellement 500 recettes de « pâtes épicées » et seulement 10 de « desserts ». Si vous goûtez tout, les chefs qui sont excellents en pâtes épicées passeront pour des génies, même s'ils sont incapables de faire un gâteau.

Cet article propose une méthode ingénieuse pour résoudre deux problèmes à la fois : gagner du temps et de l'argent et corriger le biais du livre de recettes.

Voici comment ils ont procédé, expliqué simplement :

1. Le problème : Trop de redondance

Les auteurs ont remarqué que beaucoup de questions dans ces tests volumineux sont en réalité très similaires les unes aux autres. C'est comme avoir 50 façons différentes de demander « Quel est 2+2 ? » dans un test de mathématiques. Tester toutes ces variantes est une perte de temps, et cela favorise injustement le score de tout modèle qui est bon pour ce type spécifique de question.

2. La solution : La règle du « Pas de clones »

L'équipe a créé un système pour choisir un groupe de questions plus petit et plus intelligent. Ils ont utilisé une méthode appelée Ensemble Indépendant Maximal (MIS - Maximum Independent Set).

L'analogie : Imaginez que vous organisiez une fête et que vous ayez une liste de 1 000 invités potentiels. Cependant, vous avez une règle : aucun de deux invités qui sont « trop similaires » ne peut être invité.
- Si l'Invité A et l'Invité B portent exactement la même tenue et parlent du même sujet, ils sont « connectés ». Vous ne pouvez en choisir qu'un seul.
- L'objectif est d'inviter le nombre maximum de personnes possible tout en garantissant qu'aucun duo sur votre liste d'invités ne soit trop similaire.
Le résultat : Vous vous retrouvez avec une petite fête (peut-être 300 personnes au lieu de 1 000), mais la foule est beaucoup plus diversifiée. Vous avez éliminé les « clones » pour ne garder que les voix uniques.

3. Comment ils ont construit la « Liste d'invités »

Pour déterminer qui est « trop similaire », ils n'ont pas demandé à des humains de lire les questions. À la place, ils ont utilisé des « traducteurs » IA (des modèles d'embedding) pour transformer chaque question en une coordonnée sur une carte.

Les questions qui signifient la même chose se retrouvent proches les unes des autres sur la carte.
Ils ont dessiné un cercle autour de chaque question. Si une autre question tombait à l'intérieur de ce cercle, elle était considérée comme « trop similaire ».
Ils ont ensuite exécuté un algorithme informatique pour choisir le plus grand groupe possible de questions où aucune paire de questions ne tombait à l'intérieur du cercle de l'autre.

4. Ce qu'ils ont découvert

Ils ont testé cette méthode sur quatre types de tests différents (mathématiques, culture générale, respect des instructions, etc.) en utilisant 66 modèles d'IA différents.

Le classement est resté le même : Lorsqu'ils ont choisi ce groupe de questions plus petit et plus diversifié, le classement des chefs IA (qui était le n°1, le n°2, le n°3) était presque identique à celui que vous obtiendriez en les testant sur les 1 000 questions.
- La statistique : Dans 99,2 % de leurs tests, l'ordre des chefs était cohérent, peu importe la manière dont le processus de sélection était mené.
Ils ont gagné énormément de temps : Selon la rigueur appliquée, ils ont pu réduire le nombre de questions de 25 % à 48 % (et parfois même plus) sans perdre la capacité de distinguer les meilleurs modèles.
La correction du « Biais » : Parce qu'ils ont supprimé les « clones », le test est devenu plus équitable. Si un test contenait trop de questions sur les « pâtes épicées », cette méthode a supprimé les doublons, garantissant que le score final reflète un éventail plus large de compétences, et non un seul domaine de niche.

5. Le bémol (Quand cela ne fonctionne pas parfaitement)

La méthode fonctionne mieux lorsque le « cercle de similitude » n'est pas trop petit.

S'ils ont appliqué la règle de manière trop stricte (en n'autorisant que des questions qui sont très différentes), ils se sont retrouvés avec une liste d'invités minuscule qui passait à côté de sujets importants. Cela s'est produit principalement avec des tests qui étaient déjà très répétitifs ou qui présentaient des schémas de notation étranges (comme le test « IFEval »).
Cependant, même dans ces « échecs », les résultats étaient cohérents. L'ordinateur choisissait toujours le même petit groupe de questions, et ce groupe racontait simplement une histoire légèrement différente du test complet. Les auteurs soutiennent que ce n'est pas un bug, mais une fonctionnalité qui révèle le biais du test original.

L'essentiel

L'article prouve que vous n'avez pas besoin de tester les modèles d'IA sur des milliers de questions pour savoir qui est le meilleur. En utilisant une règle de « pas de clones » pour choisir un échantillon diversifié et représentatif, vous pouvez :

Économiser des quantités massives de puissance de calcul et de temps.
Obtenir un score plus juste qui n'est pas biaisé par un trop grand nombre de questions similaires.
Avoir confiance dans les résultats, car la méthode est stable et reproductible.

C'est comme réaliser que vous n'avez pas besoin de goûter chaque goutte de soupe dans une marmite géante pour savoir si elle est salée ; il vous suffit de quelques cuillerées provenant de différentes parties de la marmite pour obtenir la saveur réelle.

Résumé Technique : Efficacité des Benchmarks LLM Consistants et Distinctifs via la Sélection de Prompts par Ensemble Indépendant Maximal

Énoncé du Problème

L'évaluation rigoureuse des grands modèles de langage (LLM) fait face à deux défis primordiaux : l'efficacité de l'évaluation et le biais de couverture.

Efficacité : Les benchmarks complets (ex. MMLU-Pro, GPQA) contiennent souvent des centaines à des milliers de questions, ce qui engendre des coûts d'inférence substantiels pour les modèles de pointe et les classements à grande échelle.
Biais de Couverture : Les prompts des benchmarks sont fréquemment répartis de manière inégale dans l'espace d'embedding. Si un benchmark surreprésente des régions sémantiques spécifiques (ex. de nombreuses questions similaires en chimie), il augmente implicitement le poids de la performance du modèle sur ces facettes spécifiques, faussant ainsi les classements indépendamment de la capacité générale. Ce biais structurel est invisible dans les métriques agrégées mais provient de la redondance sémantique entre les prompts.

Les méthodes existantes de sélection de sous-ensembles, telles que celles basées sur la théorie de la réponse aux items (IRT), nécessitent souvent une interaction itérative avec le modèle ou une modélisation spécifique de la difficulté des items. Il existe un besoin pour une approche indépendante du modèle qui sélectionne les prompts uniquement sur la base de la similitude par paires afin de réduire simultanément les coûts et de corriger le biais de couverture.

Méthodologie

Les auteurs proposent un cadre de théorie des graphes qui modélise chaque benchmark comme un graphe de similitude de prompts $G = (V, E)$ .

Construction des Embeddings : Les prompts sont projetés en vecteurs de dimension fixe en utilisant divers modèles d'embedding (basés sur des encodeurs et des décodeurs).
Construction du Graphe : Les nœuds représentent les prompts. Un arc non orienté relie deux nœuds si leur distance dans l'espace d'embedding dépasse un seuil configurable $\theta$ (défini comme un percentile de la distribution empirique des distances).
- Note : Le papier définit les arcs en fonction d'une distance au-dessus d'un seuil, ce qui signifie que les nœuds connectés sont considérés comme "dissimilaires" dans le contexte de la logique de construction du graphe décrite pour l'MIS, ou inversement, l'ensemble indépendant garantit que les nœuds sélectionnés ne sont pas connectés, signifiant qu'ils sont dans le seuil de similitude ?
- Correction basée sur le texte : Le texte stipule : "un arc connecte deux prompts... si leur distance dans l'espace d'embedding tombe au-dessus d'un seuil configurable ( $\text{d}(e_u, e_v) \ge \theta$ )."
- Logique de l'MIS : Un Ensemble Indépendant Maximal (MIS) est un ensemble de nœuds où aucun de ces nœuds ne partage un arc. Par conséquent, dans le sous-ensemble sélectionné, aucun des deux prompts n'a une distance $\ge \theta$ . Cela implique que tous les prompts sélectionnés sont à l'intérieur de la distance $\theta$ les uns des autres ?
- Rélecture attentive du texte : Le texte dit : "un arc connecte deux prompts... si leur distance... tombe au-dessus d'un seuil configurable... Sous cette construction, un ensemble indépendant correspond à un sous-ensemble de prompts dont les distances par paires restent en dessous du seuil $\theta$ ."
- Vérification de la contradiction logique : Si un arc existe quand la distance $\ge \theta$ (dissimilaire), un Ensemble Indépendant (pas d'arcs) signifie que toutes les paires ont une distance $< \theta$ (similaire). Cela impliquerait de sélectionner un groupe de prompts similaires, ce qui contredit l'objectif de "diversité maximale".
- Interprétation alternative du texte : Le texte dit : "les nœuds sont connectés si leur distance dans l'espace d'embedding tombe au-dessus d'un seuil configurable... l'ensemble indépendant... correspond à un sous-ensemble de prompts dont les distances par paires restent en dessous du seuil $\theta$ ."
- Vérification de la contradiction logique : Si l'arc existe pour une distance $\ge \theta$ (dissimilaire), l'Ensemble Indépendant (sans arcs) signifie que toutes les paires ont une distance $< \theta$ (similaire). Cela impliquerait de sélectionner un groupe de prompts similaires. Cela contredit l'affirmation de l'abstract : "maximale diversité, non-redondance".
- Vérification de la logique de l'MIS : Habituellement, pour éliminer la redondance, on veut choisir des éléments qui sont éloignés.
- Hypothèse : Il existe une potentielle erreur de formulation dans la description de la condition de l'arc par rapport au résultat de l'MIS dans le texte fourni, OU la métrique de "distance" est inversée (ex. score de similitude où un score élevé = proximité).
- Résolution : L'intention est claire : utiliser l'MIS pour sélectionner un sous-ensemble où aucun des deux prompts n'est sémantiquement proche (diversité).
Sélection par Ensemble Indépendant Maximal (MIS) : Le problème est formulé comme la recherche du plus grand sous-ensemble $S$ de nœuds tel qu'aucun des deux nœuds ne partage un arc.
- Algorithmes évalués : Quatre solveurs ont été testés :
  - CPLEX : Solveur exact (Programmation Linéaire en Nombres Entiers).
  - GREEDY : Heuristique déterministe (sommet de plus bas degré).
  - Online-MIS : Heuristique de flux aléatoire (streaming).
  - ReduMIS : Noyau de graphe (graph kernelization) + recherche locale stochastique.
- Stochasticité : Les solveurs stochastiques (Online-MIS, ReduMIS) ont été exécutés avec 5 graines aléatoires pour tester la cohérence.
Métriques d'Évaluation :
- Accord de Classement ( $\rho$ ) : Corrélation de rang de Spearman entre le classement du sous-ensemble et le classement du benchmark complet.
- Cohérence ( $W$ ) : Coefficient de concordance de Kendall à travers les graines aléatoires. Un $W \ge 0,90$ indique un accord quasi parfait.

Principales Contributions

Cadre de Théorie des Graphes : Un cadre de sélection de prompts indépendant du modèle qui traite simultanément l'efficacité et le biais de couverture en sélectionnant un sous-ensemble maximalement diversifié et non redondant via l'MIS.
Validation Empirique Étendue : Évaluation à travers 2 563 configurations uniques impliquant :
- 4 Benchmarks (GPQA, IFEval, MMLU-Pro, Omni-MATH).
- 66 LLM de pointe.
- 6 Modèles d'Embedding (3 petits encodeurs, 3 grands décodeurs).
- 3 Mesures de Distance (Cosinus, Pearson, Euclidienne standardisée).
- 6 Percentiles de Seuil ( $p10$ – $p95$ ).
- 4 Solveurs MIS.
Confirmation de l'Hypothèse : L'hypothèse centrale — que la sélection répétée par MIS produit des classements cohérents qui peuvent différer du benchmark complet de référence en raison de la correction du biais de couverture — est fortement confirmée.

Résultats

Cohérence : L'hypothèse de cohérence se vérifie fortement. Dans 99,2 % des configurations stochastiques, Kendall's $W \ge 0,90$ (moyenne $W = 0,997 \pm 0,008$ ). Cela indique que différentes graines aléatoires produisent des classements hautement stables.
Divergence de Classement : La divergence de classement par rapport au benchmark complet ( $\rho < 0,95$ $ρ < 0, 95$ ) s'est produite dans seulement 15,95 % des configurations.
- Ces divergences étaient concentrées dans les seuils bas ( $p10$ – $p20$ ) et certains benchmarks spécifiques (GPQA et IFEval).
- Les auteurs identifient les graphes excessivement denses (conservant trop peu de prompts représentatifs) comme le principal mode de défaillance de ces divergences.
Efficacité : À des seuils de percentile plus élevés (ex. $p80$ ), la méthode atteint une réduction de prompts de 25 à 48 % en moyenne tout en maintenant une haute fidélité de classement ( $\rho \approx 0,992$ ).
Performance des Algorithmes :
- ReduMIS et Online-MIS (stochastiques) ont montré la concordance la plus élevée ( $W \approx 0,997$ ).
- CPLEX et GREEDY (déterministes) ont obtenu des corrélations de classement similaires ( $\rho \approx 0,968$ ) mais n'offrent pas de métriques de cohérence basées sur les graines.
Modèles d'Embedding : Les grands modèles basés sur les décodeurs (ex. Qwen-8B, Nemotron-8B) ont généralement mieux performé que les petits modèles basés sur les encodeurs pour préserver la structure de classement, particulièrement avec la distance euclidienne standardisée.
Effets de Seuil :
- $p80$ est identifié comme le compromis optimal, offrant une préservation de classement quasi parfaite ( $\rho=0,992$ ) avec une réduction de 37–45 %.
- $p10$ – $p20$ (élagage agressif) a montré une corrélation plus faible ( $\rho \approx 0,905$ ) mais une cohérence toujours élevée ( $W \approx 0,990$ ), suggérant que le sous-ensemble est stable mais distinct du benchmark complet biaisé.

Signification et Revendications

Le papier affirme que la sélection de prompts par MIS est une approche principled et efficace qui recadre l'évaluation des LLM :

Recadrage de la Divergence : Une corrélation de Spearman plus faible ( $\rho < 0,95$ ) entre un sous-ensemble et le benchmark complet n'est pas nécessairement un défaut. Si le benchmark complet est biaisé par la couverture, le sous-ensemble MIS fournit une perspective corrigée et distincte en diminuant le poids des facettes surreprésentées. La haute cohérence ( $W$ ) confirme que ce classement "distinctif" est reproductible.
Détection du Biais Structurel : La distribution des degrés du graphe de similitude sert de diagnostic pour le biais de couverture. Les benchmarks avec des hubs à haut degré (nombreux doublons proches) sont les plus sujets au biais et bénéficient le plus de la sélection par MIS.
Recommandation Pratique : Les auteurs recommandent une configuration de solveur ReduMIS + embedding Qwen-8B + distance euclidienne standardisée + seuil $p80$ pour la plupart des benchmarks, atteignant $W=1,000$ et $\rho=0,9959$ .

Ce travail étend le cadre SELECTOR (précédemment utilisé pour l'optimisation numérique) aux prompts de langage naturel, démontant que les garanties de couverture structurelle se transfèrent à l'évaluation des LLM sans nécessiter d'interaction itérative avec le modèle.