🤖 machine learning

Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification

Dieser Beitrag stellt ADAP vor, einen adaptiven Algorithmus zur Laufzeit, der durch dynamisches Sampling und Ranking von Kandidaten eine effiziente Balance zwischen kostengünstigem Reward-Scoring und aufwändiger Verifikation herstellt und unter Monotonieannahmen in Aufgaben wie mathematischem Schlussfolgern und Codegenerierung nahezu optimale Kosten-Leistungs-Verhältnisse erzielt.

Ursprüngliche Autoren: Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan Kalayci

Veröffentlicht 2026-05-19

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan Kalayci

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 Detektiv, der versucht, ein Rätsel zu lösen, aber zwei sehr unterschiedliche Werkzeuge zur Verfügung stehen, deren Nutzung beide Geld kostet.

Die Werkzeuge:

Das „Bauchgefühl" (Das Belohnungsmodell): Dies ist ein billiger, schneller, aber manchmal unzuverlässiger Verdacht. Es kann einen Verdächtigen ansehen und sagen: „Diese Person sieht schuldig aus!" oder „Diese Person sieht unschuldig aus!" Es kostet fast nichts, danach zu fragen, aber es macht Fehler.
Der „Lügendetektor" (Der Verifizierer): Dies ist der teure, langsame, aber zu 100 % genaue Test. Er sagt Ihnen mit Sicherheit, ob ein Verdächtiger schuldig ist. Aber jedes Mal, wenn Sie ihn verwenden, kostet es ein Vermögen (wie eine riesige Rechnung für einen Labortest).

Das Problem:
Sie haben eine Liste von Verdächtigen (von einer KI generierte Kandidatenantworten). Sie müssen die eine schuldige Person finden (die richtige Antwort).

Wenn Sie den Lügendetektor bei allen einsetzen, gehen Sie bankrott.
Wenn Sie nur Ihrem Bauchgefühl vertrauen, verhaften Sie möglicherweise die falsche Person.
Die alte Methode bestand darin, eine feste Regel zu wählen: „Ich werde das Bauchgefühl bei 100 Personen befragen, dann den Lügendetektor bei den Top 5 einsetzen."
- Der Fehler: Einige Rätsel sind einfach (die schuldige Person ist offensichtlich), also haben Sie Geld verschwendet, indem Sie 100 Personen überprüft haben. Andere Rätsel sind schwer (die schuldige Person ist versteckt), sodass die Überprüfung von nur 5 nicht ausreichte und Sie gescheitert sind. Sie können keine feste Regel für jeden Fall verwenden.

Die Lösung: „ADAP" (Der adaptive Detektiv)
Die Autoren dieses Papiers haben eine intelligente Strategie namens ADAP entwickelt. Anstatt an einer festen Regel festzuhalten, ist ADAP wie ein Detektiv, der unterwegs lernt.

So funktioniert ADAP, mit einer einfachen Analogie:

Die „Schalen"-Strategie

Stellen Sie sich vor, Sie suchen eine Nadel im Heuhaufen, wissen aber nicht, wie groß der Heuhaufen ist.

Klein beginnen: ADAP beginnt damit, das billige „Bauchgefühl" bei nur wenigen Verdächtigen zu befragen.
Rangfolge festlegen: Es reiht sie von „Am wahrscheinlichsten schuldig" bis „Am wenigsten wahrscheinlich" auf.
Die erste Überprüfung: Es setzt den teuren „Lügendetektor" bei dem ganz oben stehenden Verdächtigen ein.
- Hat es funktioniert? Großartig! Stoppen und feiern.
- Hat es versagt? Okay, der Top-Verdächtige war unschuldig.
Die „Schalen"-Erweiterung: Da die erste Überprüfung gescheitert ist, erkennt ADAP: „Dieses Rätsel ist schwieriger als gedacht." Es gibt nicht auf. Stattdessen verdoppelt es seine Anstrengungen.
- Es fragt das Bauchgefühl bei mehr neuen Verdächtigen.
- Es ordnet den gesamten Haufen (alte und neue) neu.
- Es setzt den Lügendetektor bei den neuen Top-Verdächtigen ein.
Wiederholen: Wenn es immer noch scheitert, verdoppelt es die Anstrengungen erneut. Es erweitert seine Suche in „Schalen" (Schichten), die immer größer werden, bis es die Antwort findet.

Warum ist das genial?

Für einfache Fälle: Wenn die Antwort offensichtlich ist, findet ADAP sie schnell mit sehr wenigen Überprüfungen. Es spart eine Menge Geld.
Für schwierige Fälle: Wenn die Antwort versteckt ist, bleibt ADAP dran, bis es sie findet. Es gibt nicht vorzeitig auf, wie es eine feste Regel tun könnte.
Das Ergebnis: Im Durchschnitt gibt ADAP viel weniger Geld aus als die alten „festen Regel"-Methoden und findet dennoch zu 100 % die richtige Antwort.

Die „Monotonie"-Regel (Das Geheimnis)

Damit ADAP funktioniert, gibt es eine wichtige Annahme: Das Bauchgefühl muss einigermaßen richtig liegen.
Das Papier geht davon aus, dass, wenn das Bauchgefühl sagt, ein Verdächtiger sei „sehr wahrscheinlich schuldig", dieser tatsächlich wahrscheinlicher schuldig ist als jemand, bei dem es „leicht wahrscheinlich" sagt. Es muss nicht perfekt sein, nur allgemein in der richtigen Reihenfolge. Wenn das Bauchgefühl völlig zufällig wäre, würde ADAP nicht funktionieren. Aber in der realen Welt (Matheprobleme und Programmierung) leistet das Bauchgefühl in der Regel eine anständige Arbeit beim Rangieren.

Was das Papier bewiesen hat

Die Autoren haben nicht nur geraten, dass dies funktionieren würde; sie haben die Mathematik betrieben, um es zu beweisen.

Das ideale Szenario: Sie stellten sich zunächst einen Detektiv vor, der weiß, wie wahrscheinlich jeder Verdächtige genau schuldig ist. Sie berechneten die absoluten Mindestkosten, um das Rätsel zu lösen.
Die reale Welt: Sie zeigten, dass ADAP, ohne die Zukunft zu kennen, innerhalb eines konstanten Faktors dieser „perfekten" Kosten liegen kann. Auf Deutsch gesagt: ADAP ist fast so gut wie ein Detektiv mit einer Kristallkugel, braucht aber keine.
Die Notwendigkeit von Struktur: Sie bewiesen auch, dass, wenn das Bauchgefühl völlig chaotisch wäre (kein Muster überhaupt), keine Strategie effizient sein könnte. Sie brauchen dieses Muster „höherer Score = wahrscheinlicher korrekt", um Geld zu sparen.

Der Realwelt-Test

Das Team testete dies bei zwei schwierigen Aufgaben:

Matheprobleme: Das Lösen kniffliger Mathefragen.
Programmierung: Das Schreiben von Computerprogrammen, die versteckte Tests bestehen.

Die Ergebnisse:

ADAP fand zu 100 % die richtige Antwort.
Alte feste Methoden (Überprüfung einer festgelegten Anzahl von Personen) fanden entweder die Antwort nicht oder gaben 3- bis 5-mal mehr Geld aus, um das gleiche Ergebnis zu erzielen.
Selbst im Vergleich zu einer „intelligenten" Methode, die versuchte, die Schwierigkeit des Problems im Voraus zu erraten, schnitt ADAP genauso gut oder besser ab, ohne dass Vorwissen nötig war.

Zusammenfassung

Das Papier stellt eine intelligente, adaptive Art vor, KI einzusetzen. Anstatt blind eine festgelegte Anzahl von Antworten zu generieren und eine festgelegte Anzahl davon zu überprüfen, passt es seine Anstrengungen dynamisch an, je nachdem, wie schwierig das spezifische Problem aussieht. Es spart enorme Mengen an Rechenleistung (und Geld), indem es flexibel ist und sicherstellt, dass Sie bei einfachen Aufgaben nicht zu viel und bei schwierigen Aufgaben nicht zu wenig ausgeben.

Technische Zusammenfassung: Adaptive Generate-Rank-Verify

Problemformulierung

Der Beitrag adressiert das Problem der kostenempfindlichen Zuweisung von Rechenressourcen zur Inferenzzeit bei Large Language Models (LLMs). Moderne Reasoning-Pipelines nutzen häufig ein „Generate–Rank–Verify"-Paradigma: Ein LLM generiert mehrere Kandidatenlösungen, ein günstiges, aber verrauschtes Reward-Modell sortiert sie, und ein teurer Verifizierer (z. B. Ausführung versteckter Tests im Code oder exaktes Abgleichen von Antworten in Mathematik) validiert die besten Kandidaten.

Die zentrale Herausforderung besteht darin, dass die optimale Zuweisung von Rechenressourcen (Anzahl der Generierungen versus Anzahl der Verifizierungen) promptabhängig ist. Feste Strategien (z. B. Generieren von $N_{rew}$ Proben und Verifizieren der besten $N_{ver}$ ) sind ineffizient: Sie verschwenden Ressourcen bei einfachen Prompts und investieren zu wenig bei schwierigen. Die Autoren formalisieren dies als Active Search, ein sequenzielles Entscheidungsproblem, bei dem eine Strategie adaptiv:

Kandidaten generieren und deren Reward-Scores beobachten muss (Kosten $c_{rew}$ ).
Ausgewählte Kandidaten verifizieren muss, um Ground-Truth-Labels zu erhalten (Kosten $c_{ver}$ ).
Stoppt, sobald eine verifizierte, korrekte Antwort gefunden wurde.

Das Ziel ist es, die erwarteten Gesamtkosten $J = c_{rew}N_{rew} + c_{ver}N_{ver}$ zu minimieren und dabei eine Erfolgsquote von 100 % sicherzustellen (Finden einer korrekten Antwort, falls eine in der Generierungsverteilung existiert).

Methodik

1. Verteilungsbewertender Benchmark

Die Autoren leiten zunächst eine theoretische untere Schranke her, indem sie annehmen, die Strategie verfüge über perfektes Wissen der Umgebung:

$D_x$ : Die Verteilung der Reward-Scores für einen Prompt $x$ .
$h^*_x(r)$ : Die konditionale Erfolgsfunktion, die die Wahrscheinlichkeit darstellt, dass ein Kandidat mit Score $r$ die Verifizierung besteht.

Theorem 3.2 charakterisiert die optimale Strategie in diesem idealisierten Setting. Es beweist, dass die optimale Strategie eine Schwellenwertregel ist: Ein Kandidat wird sofort verifiziert, wenn seine konditionale Erfolgswahrscheinlichkeit $h^*_x(r)$ einen spezifischen Break-even-Schwellenwert $\tau^*$ überschreitet, andernfalls wird er verworfen. Der Schwellenwert $\tau^*$ ist die eindeutige Lösung von $c_{ver} \mathbb{E}[\max\{h^*(R) - \tau^*, 0\}] = \tau^* c_{rew}$ .

2. Der ADAP-Algorithmus

In der Praxis sind $D_x$ und $h^*_x$ unbekannt. Die Autoren schlagen ADAP (Adaptive Generate-Rank-Verify) vor, einen shellweisen Online-Algorithmus, der ohne Vorwissen über die Score-Verteilung oder die Erfolgsfunktion auskommt und sich ausschließlich auf die Monotonieannahme stützt (höhere Reward-Scores sind nicht weniger wahrscheinlich, die Verifizierung zu bestehen).

ADAP-Mechanismus:

Shellweise Suche: Der Algorithmus sucht über „Shells" dyadischer Skalen für die Anzahl der Proben ( $m$ ) und Verifizierungen ( $k$ ). Jede Shell $s$ entspricht einem Kostenbereich $[2^s c_{min}, 2^{s+1} c_{min})$ .
Progressive Erweiterung: Ausgehend von kleinen Shells generiert ADAP einen Batch neuer Kandidaten, fügt sie einem Pool hinzu und sortiert den gesamten Pool nach Reward-Score.
Verifizierung: Es werden die besten $k$ Kandidaten im Pool verifiziert. Wird ein positives Label gefunden, wird gestoppt. Andernfalls wird zur nächsten Shell mit größerem $m$ und $k$ übergegangen.
Pul-basierte Effizienz: Im Gegensatz zu Streaming-Strategien, die unverifizierte Kandidaten verwerfen, führt ADAP einen Pool. Kandidaten mit hohem Reward, die in frühen Shells generiert wurden, bleiben für Verifizierungen in späteren Shells verfügbar, falls sie noch nicht abgefragt wurden.

3. Theoretische Garantien

Obere Schranke: Unter der Monotonieannahme beweist Theorem 4.2, dass ADAP erwartete Kosten innerhalb eines konstanten Faktors (speziell $\le 400$ ) des verteilungsbewertenden Optimums $J^*$ erreicht. Diese Garantie gilt gleichmäßig für alle machbaren Prompts und unbekannten Verteilungen.
Untere Schranken & Notwendigkeit von Struktur: Die Autoren zeigen, dass strukturelle Annahmen notwendig sind. Unter Verwendung der zentrierten Sternzahl ( $s_0$ ), eines lerntheoretischen Komplexitätsmaßes, zeigt Theorem 6.2, dass ohne Annahmen über die Beziehung zwischen Scores und Labels (d. h. wenn $s_0 = \infty$ ) keine korrekte Online-Strategie ein konstantes Wettbewerbsverhältnis gegenüber dem verteilungsbewertenden Orakel erreichen kann. Die Worst-Case-Lücke kann als $\Omega(\min\{s_0, c_{ver}/c_{rew}\})$ skalieren.

Hauptbeiträge

Formalisierung: Definition der Generate–Rank–Verify-Pipeline als kostenempfindliches Active-Search-Problem, das sich von Standard-Active-Learning durch die Notwendigkeit unterscheidet, Kandidaten online zu generieren statt einen festen Pool abzufragen.
Optimaler Benchmark: Charakterisierung der verteilungsbewertenden optimalen Strategie als einfache Schwellenwertregel basierend auf der Break-even-Erfolgswahrscheinlichkeit.
Adaptiver Algorithmus (ADAP): Vorschlag eines praktischen Online-Algorithmus, der Generierungs- und Verifizierungsaufwand adaptiv skaliert. Er liefert nachweisbare konstante Garantien gegenüber dem optimalen Orakel unter Monotonie.
Lerntheoretische Grenzen: Etablierung, dass strukturelle Annahmen (wie Monotonie) nicht nur technische Bequemlichkeiten, sondern fundamentale Voraussetzungen für effiziente Active Search sind, formalisiert durch die zentrierte Sternzahl.
Empirische Validierung: Validierung des Ansatzes bei mathematischem Reasoning (HMMT) und kompetitiver Programmierung (LiveCodeBench).

Experimentelle Ergebnisse

Die Autoren bewerteten ADAP gegenüber:

SampleAware: Eine Orakel-untere Schranke, die retrospektiv das günstigste $(N_{rew}, N_{ver})$ für jeden einzelnen Versuch auswählt.
DAPk: Eine Schwierigkeits-adaptive Baseline, die Prompts in $k$ Schwierigkeitsklassen basierend auf historischen Bestehensquoten unterteilt und jeder Klasse eine feste Strategie zuweist.
Uniform: Eine feste Strategie, die den durchschnittlichen Kosten von ADAP entspricht.

Ergebnisse:

Kosteneffizienz: Auf dem Subset machbarer Prompts erreichte ADAP eine 100%ige Erfolgsquote mit durchschnittlichen Kosten, die bei mathematischen Aufgaben 2,9 $\times$ niedriger und bei Programmieraufgaben 5,5 $\times$ niedriger waren als bei der besten festen Strategie.
Vergleich mit DAPk: ADAP entsprach DAPk oder übertraf es (selbst bei $k=10$ ), ohne historische Schwierigkeitslabels oder Offline-Tuning zu benötigen. Bei Programmieraufgaben schlug DAPk ADAP nie, während es bei mathematischen Aufgaben nur dann an die Leistung von ADAP herankam, wenn $k$ groß genug war, um ein pro-Problem-Orakel zu approximieren.
Robustheit: Der Vorteil von ADAP gegenüber festen Strategien nahm zu, wenn die Verifizierungskosten ( $c_{ver}$ ) im Verhältnis zu den Generierungskosten ( $c_{rew}$ ) stiegen.

Bedeutung und Behauptungen

Der Beitrag behauptet, dass online, promptabhängige Adaptation statischen oder historisch abgestimmten Strategien für die Suche zur Inferenzzeit überlegen ist. Indem das Problem als Active Search behandelt und die Monotonie von Reward-Signalen genutzt wird, kann ADAP Rechenressourcen dynamisch zuweisen, um der Schwierigkeit spezifischer Prompts zu entsprechen.

Die Autoren betonen, dass ihre Arbeit Folgendes liefert:

Nachweisbare Garantien: Eine konstante Approximation der optimalen Kosten ohne Kenntnis der zugrunde liegenden Verteilungen.
Praktische Effizienz: Signifikante Reduzierung der Rechenkosten (Latenz, GPU-Stunden, API-Ausgaben) für anspruchsvolle Reasoning-Aufgaben.
Theoretische Notwendigkeit: Der Nachweis, dass strukturelle Annahmen über die Beziehung zwischen Reward und Verifizierer unvermeidbar sind, um effiziente Suche zu erreichen, und damit die Lücke zwischen Active Search und Active-Learning-Theorie geschlossen wird.

Der Beitrag schließt, dass Erweiterungen auf variable Kosten und parallele Generierung zukünftige Richtungen sind, das aktuelle Framework jedoch die fundamentale Spannung zwischen der Generierung diverser Kandidaten und der Verifizierung der vielversprechendsten erfolgreich adressiert.