📊 statistics

Pass@K Policy Optimization: Solving Harder Reinforcement Learning Problems

Dieses Paper stellt die Pass-at-k Policy Optimization (PKPO) vor, ein neuartiges Reinforcement-Learning-Framework, das unverzerrte Schätzer ableitet, um direkt den kollektiven Erfolg von Stichprobenmengen (pass@k) anstatt isolierter Versuche zu optimieren, wodurch durch k-Annealing die Exploration verbessert und schwierigere Probleme gelöst werden, während die pass@1-Leistung beibehalten oder gesteigert wird.

Ursprüngliche Autoren: Christian Walder, Deep Karkhanis

Veröffentlicht 2026-06-11

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Christian Walder, Deep Karkhanis

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 Lehrer, der versucht, einem Schüler zu helfen, schwierige mathematische Probleme zu lösen.

Der alte Weg: Die „Erster Versuch“-Falle
Traditionell, wenn man KI-Modelle trainiert (wie die, die Code schreiben oder Mathe lösen), versucht der Computer, ein Problem zu lösen, erhält eine Punktzahl und passt sein Gehirn baselt auf diesem einen Versuch an. Wenn der erste Versuch fehlschlägt, lernt der Computer nichts aus den anderen Versuchen, die er im Hintergrund vielleicht unternommen hätte. Es ist wie ein Schüler, der eine Prüfung ablegt, eine Frage falsch beantwortet und sofort aufgibt, obwohl er sie beim zweiten oder dritten Versuch vielleicht richtig gelöst hätte, wenn er nur weitergemacht hätte.

Diese Methode optimiert auf Pass@1: „Hat die allererste Antwort funktioniert?“ Dies zwingt die KI dazu, sicher und konservativ zu sein, und führt oft dazu, dass sie die riskanten, kreativen Vermutungen vermeidet, die nötig sind, um wirklich schwierige Probleme zu lösen.

Die neue Idee: Der „Best of the Batch“-Ansatz
Die Autoren dieses Papers schlagen eine neue Strategie namens Pass@K Policy Optimization (PKPO) vor.

Anstatt sich nur um die erste Antwort zu kümmern, besagt diese Methode: „Lass uns für jedes Problem K verschiedene Versuche generieren (sagen wir 8 oder 16). Es ist uns egal, ob die ersten 7 falsch sind; uns ist nur wichtig, ob mindestens einer von ihnen richtig ist.“

Denken Sie an ein Fischernetz.

Alte Methode: Sie werfen eine Angel aus. Wenn Sie den Fisch verpassen, ziehen Sie die Angel ein und lernen nichts.
PKPO-Methode: Sie werfen ein Netz mit 16 Leinen aus. Wenn auch nur eine einzige Leine einen Fisch fängt, ist das gesamte Netz ein Erfolg. Die KI wird für den besten Fang im Netz belohnt, nicht für den Durchschnitt aller Leinen.

Der magische Trick: Die Ergebniskarte
Das Schwierige ist herauszufinden, wie man die KI so lehrt, dies zu tun. Wenn Sie der KI nur sagen: „Du hast einen Fisch auf Leine #4 gefangen“, wird sie Leine #1, #2 und #3 vielleicht ignorieren. Aber wenn Sie ihr sagen: „Du hast einen Fisch gefangen, also hast du eine gute Arbeit geleistet“, erkennt sie vielleicht nicht, welche Leine der Held war.

Die Autoren haben eine spezielle mathematische „Ergebniskarte“ (einen Schätzer) erfunden, die wie ein kluger Schiedsrichter fungiert.

Sie betrachtet alle 16 Versuche.
Sie berechnet eine Punktzahl, die die KI dafür belohnt, dass sie irgendeine richtige Antwort in der Gruppe hat.
Entscheidend ist, dass sie auch den „falschen“ Antworten ein wenig Anerkennung zuteilt, da sie Teil der Gruppe waren, die schließlich den Gewinner hervorgebracht hat. Dies ermutigt die KI, weiterhin zu explorieren und gewagte, riskante Ideen auszuprobieren, im Wissen, dass selbst eine „schlechte“ Vermutung zum Erfolg des Teams beiträgt, wenn später eine „gute“ Vermutung auftaucht.

Warum das wichtig ist
Das Paper zeigt, dass diese Methode wie eine Superkraft für schwierige Aufgaben wirkt:

Sie schaltet schwierige Probleme frei: Bei sehr anspruchsvollen Mathe- und Coding-Herausforderungen, bei denen die alte „Erster Versuch“-Methode stecken bleibt, ermöglicht diese neue Methode das Lernen und das Lösen von Problemen.
Sie ist flexibel: Man kann der KI sagen: „Nutze die erste Hälfte des Trainings, um ein Risikoträger zu sein und auf das Beste aus 8 Versuchen abzielend zu arbeiten. Konzentriere dich in der zweiten Hälfte darauf, den ersten Versuch richtig zu machen.“ Dieses „Annealing“ (das langsame Ändern der Regeln) hilft der KI, zuerst zu explorieren und dann ihre Fähigkeiten zu verfeinern.
Sie funktioniert mit echten Modellen: Sie haben dies an populären Open-Source-Modellen (GEMMA2 und LLAMA3.1) getestet und festgestellt, dass es die Fähigkeit dieser Modelle, mathematische Probleme zu lösen und Code zu schreiben, im Vergleich zu bisherigen Methoden signifikant verbessert.

Zusammenfassend
Das Paper lehrt die KI, sich nicht darauf zu konzentrieren, beim allerersten Versuch perfekt zu sein. Stattdessen lehrt es die KI, eine vielfältige Menge an Ideen zu generieren, die Gruppe für das Vorhandensein irgendeines Gewinners zu belohnen und diesen kollektiven Erfolg zu nutzen, um die schwierigsten Rätsel zu lösen. Es geht darum, den Teamgeist mehrerer Vermutungen gegenüber der individuellen Leistung einer einzelnen Vermutung aufzuwerten.

Technisches Resümee: Pass@K Policy Optimization (PKPO)

Problemstellung

Reinforcement Learning (RL)-Algorithmen, die auf Large Language Models (LLMs) angewendet werden, sampeln oft mehrere Lösungsversuche ( $n > 1$ ) für ein einzelnes Problem, optimieren jedoch basierend auf der Performance einzelner Samples (pass@1). Dieser Ansatz priorisiert den Nutzen eines einzelnen hochbelohnten Samples gegenüber dem kollektiven Nutzen der Menge und unterverwendet somit effektiv die Sampling-Kapazität. Infolgedessen können Standard-Policy-Gradient-Methoden möglicherweise den Lösungsraum nicht ausreichend explorieren, insbesondere bei schwierigeren Aufgaben, bei denen die Wahrscheinlichkeit eines einzelnen korrekten Samples gering ist. Während Methoden der Inferenz-Zeit-Suche existieren, deutet die Kopplung zwischen Inferenz und Modell-Updates darauf hin, dass eine naive Optimierung des erwarteten Single-Sample-Rewards suboptimal für Aufgaben ist, bei denen Korrektheit verifizierbar ist, Lösungen jedoch nicht a priori bekannt sind.

Methodik

Die Autoren schlagen die Pass-at-k Policy Optimization (PKPO) vor, ein Framework, das direkt das pass@k-Metrik (oder dessen kontinuierliches Analogon, maxg@k) optimiert, definiert als der erwartete maximale Reward über $k$ unabhängige Samples, die aus der Policy gezogen wurden.

Zentrale theoretische Beiträge

Der primäre Beitrag ist die Ableitung neuer, varianzarmer, unverzerrter Schätzer sowohl für das pass@k-Ziel als auch für dessen Gradienten. Diese Schätzer funktionieren durch Mittelung einfacher Schätzer über alle $\binom{n}{k}$ Teilmengen der Größe $k$ aus einem Batch von $n$ Samples.

Binäre Rewards (Abschnitt 2):
- Für binäre Korrektheitslabels ( $f \in \{0, 1\}$ ) leiten die Autoren einen unverzerrten Schätzer $\rho(n, c, k)$ für pass@k ab, wobei $c$ die Anzahl der korrekten Samples ist.
- Sie beweisen, dass ein unverzerrter Schätzer nur existiert, wenn $n \ge k$ .
- Ein entsprechender unverzerrter Gradientenschätzer wird abgeleitet, der Samples basierend auf ihrer Korrektheit und der kombinatorischen Wahrscheinlichkeit ihrer Inklusion in einer erfolgreichen Teilmenge gewichtet.
Kontinuierliche Rewards (Abschnitt 3):
- Das Framework generalisiert zu kontinuierlichen Rewards $g(x)$ via des maxg@k-Ziels: $E[\max_{i=1}^k g(x_i)]$ .
- Durch die Annahme sortierter Rewards ( $g_1 \le g_2 \le \dots \le g_n$ ) leiten die Autoren einen unverzerrten Schätzer $\rho^{(g)}(n, c, k)$ ab, der sortierte Rewards mittels Binomialkoeffizienten gewichtet.
- Ein unverzerrter Gradientenschätzer wird konstruiert, wobei das Gewicht $s_i$ für ein Sample eine Linearkombination von Rewards ist, die effizient in $O(k + n \log n)$ Zeit berechnet wird.
Varianzreduktion (Abschnitt 4):
- Um die Varianz der Gradientenschätzungen zu reduzieren, ohne Bias einzuführen, schlagen die Autoren Leave-One-Out (LOO)-Baselines vor.
- Sie führen eine spezifische Baseline $s^{(loo-1)}_i$ ein, die den erwarteten maxg@k von Teilmengen der Größe $k-1$ (unter Ausschluss des aktuellen Samples) vom maxg@k der Teilmengen der Größe $k$ subtrahiert. Dies generalisiert vorangegangene Arbeiten (speziell [TZSM25]), welche auf den Fall $n=k$ beschränkt waren.
- Diese Formulierung ermöglicht eine robuste Optimierung selbst wenn $n > k$ , ein häufiges Szenario beim LLM-Training, bei dem große Batches gesampelt werden.

Implementierung

Die Methode ist als „Drop-in-Replacement“ für Standard-Reward-Transformationen in jedem Policy-Gradient-Algorithmus (z. B. PPO) konzipiert. Gegeben sei ein Batch von $n$ Samples und deren Roh-Rewards; die Rewards werden unter Verwendung der abgeleiteten Schätzer (speziell der sloo_minus_one-Funktion im bereitgestellten Code) transformiert, bevor sie in den Policy-Update-Schritt eingespeist werden.

Zentrale Ergebnisse

Die Autoren validieren PKPO durch Toy-Experimente und Real-World-Benchmarks unter Verwendung von GEMMA2 (2B und 9B Parameter) und LLAMA3.1 (8B Parameter).

Toy-Experimente:
- In einem 1D-Gaußschen Policy-Experiment verschiebt PKPO den optimalen Policy-Mittelwert erfolgreich hin zu einer höheren „Risikotoleranz“ für höheres $k$ , was es dem Modell ermöglicht, Regionen mit geringerer Wahrscheinlichkeit, aber höherem Potenzial zu explorieren.
- Die Varianzanalyse bestätigt, dass der vorgeschlagene sloo_minus_one-Schätzer die Gradientenvarianz im Vergleich zu naiver Partitionierung oder Schätzern ohne Baselines signifikant reduziert.
Real-World-Benchmarks (MATH, Coding, ARC-AGI-1):
- Selektive Optimierung: Das Setzen des Optimierungsziels $k_{opt}$ gleich dem Evaluierungsmetrik $k_{eval}$ liefert die beste Performance. Beispielsweise verbessert die Optimierung für pass@8 die pass@8-Evaluierungswerte signifikant im Vergleich zur Optimierung für pass@1.
- Lösen schwierigerer Probleme: Auf dem anspruchsvollen ARC-AGI-1 Benchmark stagniert die konventionelle pass@1-Optimierung und versagt dabei, die kumulative Lösungsrate zu verbessern. Im Gegensatz dazu „entsperrt“ PKPO mit $k_{opt} > 1$ das Lernen und erreicht höhere Lösungsraten sowie höhere pass@k-Scores für alle $k$ .
- Annealing-Strategie: Die Autoren zeigen, dass das Annealing von $k$ während des Trainings (beginnend mit einem hohen $k_{opt}$ , um die Exploration zu fördern, dann Reduktion auf $k_{opt}=1$ , um zu konsolidieren) eine starke pass@1-Performance neben signifikanten pass@k-Gewinnen erreicht und so den typischen Trade-off vermeidet, bei dem die Verbesserung von pass@k die pass@1-Leistung verschlechtert.
- Vergleich: PKPO übertrifft den Spezialfall von $n=k$ (wie in [TZSM25]) und Entropy-Regularisierungs-Baselines, insbesondere bei schwierigen Aufgaben, bei denen Exploration kritisch ist.

Bedeutung und Ansprüche

Das Paper behauptet, dass PKPO eine robuste, effiziente und theoretisch fundierte Methode bietet, um den kollektiven Nutzen einer Menge von Samples anstatt nur den Durchschnitt oder das beste einzelne Sample zu optimieren.

Exploration entsperren: Die Autoren argumentieren, dass durch die Priorisierung des gemeinsamen Nutzens (die Wahrscheinlichkeit, dass mindestens eines von $k$ Samples erfolgreich ist) gegenüber dem individuellen Sample-Nutzen die Methode die Exploration verbessert. Dies ist entscheidend für das Lösen schwierigerer Probleme, bei denen das „Signal“ (eine korrekte Lösung) im Suchraum spärlich ist.
Flexibilität: Im Gegensatz zu früheren Methoden, die auf $k=n$ (Optimierung für das Beste des gesamten Batches) oder $k=1$ beschränkt waren, ermöglicht PKPO eine robuste Optimierung für jedes beliebige $k \le n$ .
Praktische Auswirkungen: Die Methode erlaubt es Praktikern, den Exploration-Exploitation-Trade-off über den Parameter $k_{opt}$ zu steuern, was Modellen ermöglicht, komplexere Reasoning- und Coding-Aufgaben zu lösen, die mit Standard-pass@1-Optimierung sonst unzugänglich wären.

Die Arbeit positioniert sich als Generalisierung und Varianzreduktion bestehender Order-Statistic-Policy-Gradient-Methoden und bietet einen praktischen Weg, das RL-Training für LLMs auf Aufgaben zu skalieren, die tiefe Exploration erfordern.