💬 NLP

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

Dieses Paper schlägt ein graphbasierter Framework vor, das Maximum-Independent-Set-Algorithmen nutzt, um diverse, nicht-redundante Prompt-Subsets aus LLM-Benchmarks zu selektieren, wobei demonstriert wird, dass solche reduzierten Sets eine hochgradig konsistente Modell-Rangfolge beibehalten und gleichzeitig die Evaluierungskosten signifikant senken.

Ursprüngliche Autoren: Denica Kjorvezir, Marko Djukanović, Ana Gjorgjevikj, Gjorgjina Cenikj, Tome Eftimov

Veröffentlicht 2026-06-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Denica Kjorvezir, Marko Djukanović, Ana Gjorgjevikj, Gjorgjina Cenikj, Tome Eftimov

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Richter, der entscheiden muss, welcher von 66 verschiedenen Köchen (Large Language Models) der beste Koch ist. Sie haben ein riesiges Kochbuch mit 1.000 Rezepten (den Benchmark). Um fair zu sein, möchten Sie von allem ein wenig probieren. Aber das Kochen aller 1.000 Gerichte dauert ewig, kostet ein Vermögen und könnte die Ergebnisse verfälschen, wenn Ihr Kochbuch versehentlich 500 Rezepte für „scharfe Pasta“ und nur 10 für „Dessert“ enthält. Wenn Sie alles probieren, werden die Köche, die gut in scharfer Pasta sind, wie Genies wirken, selbst wenn sie keinen Kuchen backen können.

Dieses Paper schlägt einen cleveren Weg vor, um zwei Probleme gleichzeitig zu lösen: Zeit/Geld zu sparen und den Bias (die Verzerrung) im Kochbuch zu beheben.

So haben sie es erklärt, ganz einfach:

1. Das Problem: Zu viel Redundanz

Die Autoren stellten fest, dass viele Fragen in diesen großen Tests eigentlich sehr ähnlich sind. Es ist, als hätte man 50 verschiedene Arten, „Was ist 2+2?“ in einem Mathetest zu fragen. All diese zu testen, ist Zeitverschwendung und steigert unfaireerweise die Punktzahl jedes Modells, das gut in genau dieser einen Art von Frage ist.

2. Die Lösung: Die „Keine-Klone“-Regel

Das Team entwickelte ein System, um eine kleinere, intelligentere Gruppe von Fragen auszuwählen. Sie verwendeten eine Methode namens Maximum Independent Set (MIS).

Die Analogie: Stellen Sie sich vor, Sie geben eine Party und haben eine Liste von 1.000 potenziellen Gästen. Sie haben jedoch eine Regel: Es dürfen nicht zwei Gäste, die „zu ähnlich“ sind, beide eingeladen werden.
- Wenn Gast A und Gast B beide exakt das gleiche Outfit tragen und über exakt das gleiche Thema sprechen, sind sie „verbunden“. Sie können nur einen von ihnen auswählen.
- Das Ziel ist es, die maximale Anzahl an Menschen einzuladen, während sichergestellt wird, dass niemand auf Ihrer Gästeliste zu ähnlich zu einem anderen ist.
Das Ergebnis: Sie enden mit einer kleineren Party (vielleicht 300 Leute statt 1.000), aber die Menge ist viel vielfältiger. Sie haben die „Klone“ entfernt und die einzigartigen Stimmen behalten.

3. Wie sie die „Gästeliste“ erstellt haben

Um herauszufinden, wer „zu ähnlich“ ist, haben sie keine Menschen die Fragen lesen lassen. Stattdessen nutzten sie KI-„Übersetzer“ (Embedding-Modelle), um jede Frage in eine Koordinate auf einer Landkarte zu verwandeln.

Fragen, die dasselbe bedeuten, landen auf der Karte nah beieinander.
Sie zeichneten einen Kreis um jede Frage. Wenn eine andere Frage in diesen Kreis fiel, wurden sie als „zu ähnlich“ betrachtet.
Sie ließen dann einen Computer-Algorithmus laufen, um die größtmögliche Gruppe von Fragen auszuwählen, bei der keine zwei Fragen in den Kreis eines anderen fielen.

4. Was sie herausgefunden haben

Sie testeten diese Methode an vier verschiedenen Arten von Tests (Mathematik, Allgemeinwissen, Befolgen von Anweisungen usw.) mit 66 verschiedenen KI-Modellen.

Die Rankings blieben gleich: Als sie diese kleinere, vielfältige Gruppe von Fragen auswählten, war das Ranking der KI-Köche (wer Platz 1, 2, 3 ist) fast identisch mit dem Ranking, das man erhielte, wenn man sie an allen 1.000 Fragen testen würde.
- Die Statistik: In 99,2 % ihrer Tests war die Reihenfolge der Köche konsistent, unabhängig davon, wie sie den Auswahlprozess durchführten.
Sie sparten viel Zeit: Je nachdem, wie streng sie vorgingen, konnten sie die Anzahl der Fragen um 25 % bis 48 % (und manchmal sogar noch mehr) reduzieren, ohne die Fähigkeit zu verlieren, die besten Modelle voneinander zu unterscheiden.
Die Korrektur des „Bias“: Da sie die „Klone“ entfernten, wurde der Test fairer. Wenn ein Test zu viele „scharfe Pasta“-Fragen hatte, entfernte diese Methode die Überschüsse, sodass die endgültige Punktzahl ein breiteres Spektrum an Fähigkeiten widerspiegelte und nicht nur eine Nische.

5. Die Kehrseite (Wann es nicht perfekt funktioniert)

Die Methode funktioniert am besten, wenn der „Ähnlichkeitskreis“ nicht zu klein ist.

Wenn sie die Regel zu streng setzten (nur Fragen zuließen, die sehr unterschiedlich sind), endeten sie bei einer winzigen Gästeliste, die wichtige Themen vermissen ließ. Dies geschah vor allem bei Tests, die bereits sehr repetitiv waren oder seltsame Bewertungsmuster aufwiesen (wie der „IFEval“-Test).
Doch selbst in diesen „Fehlern“ waren die Ergebnisse konsistent. Der Computer wählte immer dieselbe kleine Gruppe von Fragen aus, und diese Gruppe erzählte lediglich eine etwas andere Geschichte als der vollständige Test. Die Autoren argumentieren, dass dies kein Fehler, sondern ein Merkmal ist, das zeigt, wie verzerrt der ursprüngste Test war.

Das Fazzeit

Das Paper beweist, dass man KI-Modelle nicht an tausenden Fragen testen muss, um zu wissen, wer der Beste ist. Durch die Verwendung einer „Keine-Klone“-Regel, um eine vielfältige, repräsentative Stichprobe zu ziehen, kann man:

Massiv an Rechenleistung und Zeit sparen.
Eine fairere Punktzahl erhalten, die nicht dadurch verzerrt wird, dass zu viele ähnliche Fragen vorhanden sind.
Den Ergebnissen vertrauen, da die Methode stabil und reproduzierbar ist.

Es ist, als würde man erkennen, dass man nicht jeden einzelnen Tropfen Suppe aus einem riesigen Topf probieren muss, um zu wissen, ob er salzig ist; man braucht nur ein paar Löffel aus verschiedenen Teilen des Topfes, um den wahren Geschmack zu erfassen.

Technisches Resümee: Konsistente und distinktive LLM-Benchmark-Effizienz mittels Maximum Independent Set Prompt-Selektion

Problemstellung

Die rigorose Evaluierung von Large Language Models (LLMs) steht vor zwei primären Herausforderungen: Evaluierungseffizienz und Coverage-Bias (Abdeckungsfehler).

Effizienz: Umfassende Benchmarks (z. B. MMLU-Pro, GPQA) enthalten oft hunderte bis tausende Fragen, was erhebliche Inferenzkosten für Frontier-Modelle und groß angelegte Leaderboards verursacht.
Coverage-Bias: Benchmark-Prompts sind häufig ungleichmäßig im Embedding-Raum verteilt. Wenn ein Benchmark bestimmte semantische Regionen überrepräsentiert (z. B. zahlreiche ähnliche Chemie-Fragen), gewichtet dies die Leistung eines Modells in Bezug auf diese spezifischen Facetten implizit höher, was das Ranking unabhängig von der allgemeinen Kapazität verzerrt. Dieser strukturelle Bias ist in aggregierten Metriken unsichtbar, entsteht aber durch semantische Redundanz unter den Prompts.

Existierende Methoden zur Teilmengen-Selektion, wie etwa solche auf Basis der Item-Response-Theorie (IRT), erfordern oft iterative Modellinteraktionen oder eine spezifische Modellierung der Item-Schwierigkeit. Es besteht ein Bedarf an einem modellagnostischen Ansatz, der Prompts ausschließlich basierend auf paarweiser Ähnlichkeit auswählt, um gleichzeitig Kosten zu senken und den Coverage-Bias zu korrigieren.

Methodik

Die Autoren schlagen ein graphentheoretisches Framework vor, das jeden Benchmark als Prompt-Ähnlichkeitsgraphen $G = (V, E)$ modelliert.

Embedding-Konstruktion: Prompts werden mittels verschiedener Embedding-Modelle (sowohl Encoder-basiert als auch Decoder-basiert) in festdimensionale Vektoren abgebildet.
Graph-Konstruktion: Knoten repräsentieren Prompts. Eine ungerichtete Kante verbindet zwei Knoten, wenn deren Abstand im Embedding-Raum einen konfigurierbaren Schwellenwert $\theta$ überschreitet (definiert als ein Perzentil der empirischen Distributionsverteilung).
- Hinweis: Der Papier definiert Kanten basierend auf einer Distanz oberhalb eines Schwellenwerts, was bedeutet, dass verbundene Knoten im Kontext der für MIS beschriebenen Graph-Konstruktionslogik "unähnlich" sind, oder umgekehrt: das Independent Set stellt sicher, dass ausgewählte Knoten nicht verbunden sind, also innerhalb des Schwellenwerts der Ähnlichkeit liegen?
- Korrektur basierend auf dem Text: Der Text besagt: "eine Kante verbindet zwei Prompts... wenn deren Embedding-Raum-Distanz über einem konfigurierbaren Schwellenwert ( $\theta$ ) liegt (definiert als ein Perzentil der empirischen Distanzverteilung)."
- MIS-Logik: Ein Maximum Independent Set (MIS) ist eine Menge von Knoten, bei denen kein Paar eine Kante teilt. Daher ist in der ausgewählten Teilmenge kein Paar von Prompts durch eine Kante verbunden, was bedeutet, dass alle Paare innerhalb des Schwellenwerts der Ähnlichkeit liegen?
- Re-Reading der Textstelle: Der Text besagt: "ein ungerichteter Graph... fügt eine Kante hinzu, wann immer die paarweise Distanz... einen vordefinierten Schwellenwert überschreitet... Unter dieser Konstruktion entspricht ein Independent Set einer Teilmenge von Prompts, deren paarweise Distanzen unter dem Schwellenwert $\theta$ bleiben."
- Logische Konsistenzprüfung: Wenn eine Kante existiert, wenn die Distanz $\ge \theta$ (unähnlich) ist, dann bedeutet ein Independent Set (keine Kanten), dass alle Paare eine Distanz $< \theta$ haben (ähnlich). Dies würde einen Cluster ähnlicher Prompts auswählen, was dem Ziel der "maximalen Diversität" widerspricht.
- Alternative Interpretation des Textes: Der Text sagt: "Knoten sind Prompts, die verbunden sind, wenn ihre Embedding-Raum-Distanz über einem konfigurierbaren Schwellenwert fällt."
- MIS-Logik: Ein Maximum Independent Set (MIS) ist eine Menge von Knoten, bei denen kein Paar eine Kante teilt. Daher ist in der ausgewählten Teilmenge kein Paar von Prompts durch eine Kante verbunden, was bedeutet, dass alle Paare innerhalb des Schwellenwerts der Ähnlichkeit liegen?
- Sorgfältiges Lesen der Textstelle: Der Text besagt: "eine Kante verbindet... wenn die Distanz über einem konfigurierbaren Schwellenwert liegt" und "ein Independent Set... Distanzen unter dem Schwellenwert $\theta$ bleiben."
- Fazit zur Methodik: Das Papier enthält höchstwahrscheinlich einen potenziellen Formulierungsfehler in der Beschreibung der Kantenbedingung gegenüber dem MIS-Ergebnis, ODER die "Distanz"-Metrik ist invertiert (z. B. Ähnlichkeitswert, wobei hoch = nah).
- Entscheidung: Ich werde die Intention und das Ergebnis beschreiben (die Auswahl einer maximal diversen, nicht-redundanten Teilmenge via MIS) und darauf hinweisen, dass die Graph-Konstruktion eine Distanz-Schwelle beinhaltet, ohne mich in der potenziellen textlichen Widersprüchlichkeit der Kanten-Definition zu verlieren, sondern mich auf das beschriebene Ergebnis zu konzentrieren: "keine zwei ausgewählten Prompts sind semantisch nah."
Maximum Independent Set (MIS) Selektion: Das Problem wird als Finden der größten Teilmenge $S$ von Knoten formuliert, bei denen kein Paar eine Kante teilt.
- Evaluierte Algorithmen: Vier Solver wurden getestet:
  - CPLEX: Exakter Solver (Integer Linear Programming).
  - GREEDY: Deterministische Heuristik (niedrigster Knotengrad).
  - Online-MIS: Randomisierter Streaming-Heuristik.
  - ReduMIS: Graph-Kernelisierung + stochastische lokale Suche.
- Stochastik: Die stochastischen Solver (Online-MIS, ReduMIS) wurden mit 5 zufälligen Seeds ausgeführt, um die Konsistenz zu testen.
Evaluierungsmetriken:
- Ranking-Agreement ( $\rho$ ): Spearman's Rangkorrelation zwischen dem Teilmengen-Ranking und dem Full-Benchmark-Ranking.
- Konsistenz ( $W$ ): Kendall's Koeffizient der Konkordanz über die Zufalls-Seeds hinweg. $W \ge 0,90$ deutet auf eine nahezu perfekte Übereinstimmung hin.

Zentrale Beiträge

Graph-theoretisches Framework: Ein modellagnostisches Prompt-Selektions-Framework, das die Effizienz und den Coverage-Bias gleichzeitig adressiert, indem es eine maximal diverse, nicht-redundante Teilmenge via MIS auswählt.
Umfassende empirische Validierung: Evaluierung über 2.563 einzigartige Konfigurationen, bestehend aus:
- 4 Benchmarks (GPQA, IFEval, MMLU-Pro, Omni-MATH).
- 66 Frontier-LLMs.
- 6 Embedding-Modelle (3 kleine Encoder, 3 große Decoder).
- 3 Distanzmaße (Cosine, Pearson, Standardisierte euklidische Distanz).
- 6 Perzentil-Schwellenwerte ( $p10$ – $p95$ ).
- 4 MIS-Solver.
Bestätigung der Hypothese: Die zentrale Hypothese – dass wiederholte MIS-Selektionen konsistente Rankings liefern, die sich aufgrund der Korrektur des Coverage-Bias vom Full-Benchmark-Baseline unterscheiden können – wird stark bestätigt.

Ergebnisse

Konsistenz: Die Konsistenz-Hypothese hält stark stand. In 99,2 % der stochastischen Konfigurationen liegt $W \ge 0,90$ (Mittelwert $W = 0,997 \pm 0,008$ ). Dies zeigt, dass unterschiedliche Random-Seeds hochstabile Rankings erzeugen.
Ranking-Divergenz: Eine Ranking-Divergenz vom Full-Benchmark ( $\rho < 0,95$ $ρ < 0, 95$ ) trat in nur 15,95 % der Konfigurationen auf.
- Diese Divergenzen konzentrierten sich auf niedrige Schwellenwerte ( $p10$ – $p20$ ) und spezifische Benchmarks (GPQA und IFEval).
- Die Autoren identifizieren zu dichte Graphen (die zu wenige repräsentative Prompts behalten) als primären Ausfallmodus für diese Divergenzen.
Effizienz: Bei höheren Perzentil-Schwellenwerten (z. B. $p80$ ) erreicht die Methode eine durchschnittliche Reduktion der Prompts um 25–48 %, während sie eine hohe Ranking-Fidelität ( $\rho \approx 0,992$ ) beibehält.
Algorithmus-Performance:
- ReduMIS und Online-MIS (stochastisch) zeigten die höchste Konkordanz ( $W \approx 0,997$ ).
- CPLEX und GREEDY (deterministisch) erreichten ähnliche Ranking-Korrelationen ( $\rho \approx 0,968$ ), bieten jedoch keine Metriken zur Seed-basierten Konsistenz.
Embedding-Modelle: Große Decoder-basierte Modelle (z. B. Qwen-8B, Nemotron-8B) übertrafen im Allgemeinen kleinere Encoder-basierte Modelle bei der Bewahrung der Ranking-Struktur, insbesondere mit der standardisierten euklidischen Distanz.
Schwellenwert-Effekte:
- $p80$ wurde als optimaler Trade-off identifiziert, der eine nahezu perfekte Ranking-Erhaltung ( $\rho = 0,992$ ) bei einer Reduktion von 37–45 % bietet.
- $p10$ – $p20$ (aggressive Pruning) zeigten eine geringere Korrelation ( $\rho \approx 0,905$ ), aber immer noch eine hohe Konsistenz ( $W \approx 0,990$ ), was darauf hindeutet, dass die Teilmenge stabil, aber dennoch distinktiv zur verzerrten Full-Baseline ist.

Bedeutung und Ansprüche

Das Paper behauptet, dass die MIS-basierte Prompt-Selektion ein prinzipienbasierter, effizienter Ansatz ist, der die Evaluierung von LLMs neu rahmt:

Neubewertung der Divergenz: Eine niedrigere Spearman-Korrelation ( $\rho < 0,95$ ) zwischen einer Teilmenge und dem Full-Benchmark ist nicht zwangsläufig ein Fehler. Wenn der Full-Benchmark einen Coverage-Bias aufweist, liefert die MIS-Teilmenge eine korrigierte, distinktive Perspektive, indem sie überrepräsentierte Facetten abwertet. Die hohe Konsistenz ( $W$ ) bestätigt, dass dieses "distinktive" Ranking reproduzierbar ist.
Diagnose von strukturellem Bias: Die Gradverteilung des Ähnlichkeitsgraphen dient als Diagnosewerkzeug für den Coverage-Bias. Benchmarks mit High-Degree-Hubs (viele Nahe-Duplikate) sind am anfälligsten für Bias und profitieren am meisten von der MIS-Selektion.
Praktische Empfehlung: Die Autoren empfehlen eine Konfiguration aus ReduMIS-Solver + Qwen-8B Embedding + Standardisierte euklidische Distanz + $p80$ -Schwellenwert für die meisten Benchmarks, was $W = 1,000$ und $\rho = 0,9959$ erreicht.

Die Arbeit erweitert das SELECTOR-Framework (das zuvor für numerische Optimierung verwendet wurde) auf natürliche Sprachprompts und zeigt, dass strukturelle Coverage-Garantien auf die LLM-Evaluierung übertragbar sind, ohne dass eine iterative Modellinteraktion erforderlich ist.