Technisch Overzicht: Consistente en Kenmerkende LLM-Benchmark Efficiëntie via Maximum Independent Set Prompt Selectie

Probleemstelling

De rigoureuze evaluatie van Large Language Models (LLMs) staat voor twee primaire uitdagingen: evaluatie-efficiëntie en coverage bias (dekking-bias).

1. Efficiëntie: Uitgebreide benchmarks (bijv. MMLU-Pro, GPQA) bevatten vaak honderden tot duizenden vragen, wat aanzienlijke inferentiekosten met zich meebrengt voor frontier-modellen en grootschalige leaderboards.
2. Coverage Bias: Benchmark-prompts zijn frequent ongelijk verdeeld in de embedding-ruimte. Als een benchmark specifieke semantische regio's oververtegenwoordigt (bijv. talrijke vergelijkbare chemievragen), weegt dit impliciet de prestaties van een model op die specifieke facetten zwaarder mee, wat de rangschikking vertekent, ongeacht de algemene capaciteit. Deze structurele bias is onzichtbaar in geaggregeerde metrieken, maar ontstaat door semantische redundantie tussen prompts.

Bestaande methoden voor subset-selectie, zoals die gebaseerd op Item Response Theory (IRT), vereisen vaak iteratieve modelinteractie of specifieke modellering van item-moeilijkheid. Er is behoefte aan een model-agnostische aanpak die prompts selecteert op basis van louter pairwise gelijkenis om tegelijkertijd kosten te verlagen en coverage bias te corrigeren.

Methodologie

De auteurs stellen een graaftheoretisch framework voor dat elke benchmark modelleert als een prompt-gelijkenisgraaf $G = (V, E)$.

1. Embedding Constructie: Prompts worden naar vectoren met een vaste dimensie gemapt met behulp van diverse embedding-modellen (zowel encoder-gebaseerd als decoder-gebaseerd).

2. Graaf Constructie: Knopen representeren prompts. Een ongerichte rand verbindt twee knopen als hun afstand in de embedding-ruimte een configureerbare drempelwaarde $\theta$ overschrijdt (gedefinieerd als een percentiel van de empirische afstandverdeling).

   • Opmerking: De paper definieert randen op basis van afstand boven een drempelwaarde, wat betekent dat verbonden knopen als "dissimilaar" worden beschouwd in de context van de graafconstructielogica beschreven voor MIS, of andersom: de independent set zorgt ervoor dat geselecteerde nodes niet verbonden zijn, wat betekent dat ze binnen de drempelwaarde van gelijkenis liggen?
   • Correctie op basis van tekst: De tekst stelt: "een rand verbindt twee prompts... als de embedding-ruimte afstand boven een configureerbare drempelwaarde valt ($d(e_u, e_v) \ge \theta$)."
   • MIS Logica: Een Maximum Independent Set (MIS) is een verzameling nodes waarbij geen twee nodes een rand delen. Daarom is in de geselecteerde subset geen twee prompts verbonden, wat betekent dat alle prompts een afstand $< \theta$ hebben tot elkaar?
   • Nauwkeurige herlezing van de tekst: De tekst zegt: "een rand verbindt... als de afstand boven een drempelwaarde valt... Onder deze constructie komt een independent set overeen met een subset van prompts waarvan de pairwise afstanden onder de drempelwaarde $\theta$ blijven."
   • Logische tegenstrijdigheid Check: Als een rand bestaat wanneer afstand $\ge \theta$ (dissimilaar), dan betekent een Independent Set (geen randen) dat alle paren een afstand $< \theta$ hebben (gelijksoortig). Dit zou een cluster van gelijkaardige prompts selecteren, wat de doelstelling van "maximale diversiteit" tegenspreekt.
   • Alternatieve Interpretatie van Tekst: De tekst zegt: "nodes zijn prompts verbonden als hun embedding-ruimte afstand boven een configureerbare drempelwaarde valt... MIS... selecteert een maximaal diverse, niet-redundante subset."
   • Standaard MIS in Redundantie: Meestal verbinden randen gelijkaardige items (afstand $< \theta$), en de MIS selecteert items die niet gelijkaardig zijn (geen randen).
   • Conclusie over Methodologie: Er is een mogelijke formuleringfout in de beschrijving van de edge-conditie versus de MIS-uitkomst in de paper, OF de "afstand" metriek is geïnverteerd (bijv. een gelijkenis-score waarbij hoog = dichtbij).
   • Besluit: Ik zal de intentie en het resultaat beschrijven (het selecteren van een maximaal diverse, niet-redundante subset via MIS) en vermelden dat de graafconstructie een afstandsdrempel betreft, zonder vast te lopen op de potentiële tekstuele tegenstrijdigheid van de edge-definitie, met de focus op het beschreven resultaat: "geen twee geselecteerde prompts zijn semantisch dicht bij elkaar."

3. Maximum Independent Set (MIS) Selectie: Het probleem wordt geformuleerd als het vinden van de grootste subset $S$ van nodes zodanig dat geen twee nodes een rand delen.

   • Geëvalueerde Algoritmen: Vier solvers werden getest:
     • CPLEX: Exacte solver (Integer Linear Programming).
     • GREEDY: Deterministische heuristiek (laagste-graad vertex).
     • Online-MIS: Gerandomiseerde streaming heuristiek.
     • ReduMIS: Graaf-kernelisatie + stochastische lokale zoektocht.
   • Stochasticiteit: Stochastische solvers (Online-MIS, ReduMIS) werden uitgevoerd met 5 willekeurige seeds om consistentie te testen.

4. Evaluatiemetrieken:

   • Ranking Agreement ($\rho$): Spearman's rangcorrelatie tussen de subset-rangschikking en de volledige benchmark-rangschikking.
   • Consistentie ($W$): Kendall's coefficient of concordance over willekeurige seeds. $W \ge 0.90$ duidt op bijna perfecte overeenstemming.

Belangrijkste Bijdragen

1. Graaftheoretisch Framework: Een model-agnostische prompt-selectie methode die zowel efficiëntie als coverage bias tegelijkertijd aanpakt door een maximaal diverse, niet-redundante subset te selecteren via MIS.
2. Uitgebreide Empirische Validatie: Evaluatie over 2.563 unieke configuraties bestaande uit:
   • 4 Benchmarks (GPQA, IFEval, MMLU-Pro, Omni-MATH).
   • 66 Frontier LLMs.
   • 6 Embedding-modellen (3 kleine encoders, 3 grote decoders).
   • 3 Afstandsmaten (Cosine, Pearson, Standardized Euclidean).
   • 6 Percentiel Drempels ($p10$–$p95$).
   • 4 MIS Solvers.
3. Hypothese Bevestiging: De centrale hypothese — dat herhaalde MIS-selectie consistente rangschikkingen oplevert die kunnen verschillen van de full-benchmark baseline vanwege de correctie van coverage bias — wordt sterk bevestigd.

Resultaten

• Consistentie: De consistentie-hypothese houdt sterk stand. In 99,2% van de stochastische configuraties is Kendall's $W \ge 0.90$ (gemiddelde $W = 0.997 \pm 0.008$). Dit geeft aan dat verschillende willekeurige seeds zeer stabiele rangschikkingen produceren.
• Ranking Divergentie: Rangschikking-divergentie van de volledige benchmark ($\rho < 0.95$) kwam slechts voor in 15,95% van de configuraties.
  • Deze divergenties waren geconcentreerd bij lage drempels ($p10$–$p20$) en specifieke benchmarks (GPQA en IFEval).
  • De auteurs identificeren overmatig dichte grafen (waarbij te weinig representatieve prompts worden behouden) als de primaire faalmodus voor deze divergenties.
• Efficiëntie: Bij hogere percentiel drempels (bijv. $p80$) bereikt de methode een reductie van 25–48% in prompts terwijl de hoge ranking-getrouwheid behouden blijft ($\rho \approx 0.992$).
• Algoritme Prestaties:
  • ReduMIS en Online-MIS (stochastisch) vertoonden de hoogste concordantie ($W \approx 0.997$).
  • CPLEX en GREEDY (deterministisch) bereikten vergelijkbare rangcorrelaties ($\rho \approx 0.968$) maar bieden geen seed-gebaseerde consistentie-metrieken.
• Embedding Modellen: Grote decoder-gebaseerde modellen (bijv. Qwen-8B, Nemotron-8B) presteerden over het algemeen beter dan kleinere encoder-gebaseerde modellen in het behouden van de rangschikkingsstructuur, met name met Standardized Euclidean afstand.
• Drempel Effecten:
  • $p80$ wordt geïdentificeerd als de optimale afweging, waarbij een bijna perfecte ranking-behoud ($\rho=0.992$) wordt geboden met een reductie van 37–45%.
  • $p10$–$p20$ (agressieve pruning) vertoonden lagere correlatie ($\rho \approx 0.905$) maar nog steeds hoge consistentie ($W \approx 0.990$), wat suggereert dat de subset stabiel is maar distinct is van de bevooroordeelde volledige baseline.

Betekenis en Claims

De paper claimt dat MIS-gebaseerde prompt-selectie een geprincieerde, efficiënte benadering is die de evaluatie van LLM's herkadert:

1. Herformulering van Divergentie: Een lagere Spearman correlatie ($\rho < 0.95$) tussen een subset en de volledige benchmark is niet noodzakelijkerwijs een fout. Als de volledige benchmark coverage-biased is, biedt de MIS-subset een gecorrigeerd, onderscheidend perspectief door oververtegenwoordigde facetten te downweighten. De hoge consistentie ($W$) bevestigt dat deze "onderscheidende" rangschikking reproduceerbaar is.
2. Structurele Bias Detectie: De graadverdeling van de gelijkenisgraaf dient als een diagnostisch instrument voor coverage bias. Benchmarks met high-degree hubs (veel nabij-duplicaten) zijn het meest vatbaar voor bias en profiteren het meest van MIS-selectie.
3. Praktische Aanbeveling: De auteurs bevelen een configuratie van ReduMIS solver + Qwen-8B embedding + Standardized Euclidean distance + $p80$ threshold aan voor de meeste benchmarks, wat $W=1.000$ en $\rho=0.9959$ oplevert.

Het werk breidt het SELECTOR framework (voorheen gebruikt voor numerieke optimalisatie) uit naar natuurlijke taal prompts, en demonstreert dat structurele dekking-garanties overdraagbaar zijn naar LLM-evaluatie zonder dat daar iteratieve modelinteractie voor nodig is.