TL;DR
Directly fine-tuning Large Language Models (LLMs) to optimize for Pass@$k$ (getting at least one correct answer out of $k$ attempts) often severely degrades their Pass@1 performance (single-shot accuracy). This paper mathematically proves that Pass@$k$ optimization implicitly shifts the training focus entirely toward hard prompts; if these hard prompts "negatively interfere" with the rest of the dataset, the resulting gradient conflict actively drives down single-shot accuracy.
What Problem Does This Paper Address?
When deploying LLMs for verifiable tasks like code generation or mathematical reasoning, systems often sample multiple candidate answers ($k$ times) and use an automated verifier (like unit tests) to catch the correct one. This is evaluated using the Pass@$k$ metric.
To maximize performance, researchers naturally started fine-tuning models using Pass@$k$ objectives directly. However, a recurring, frustrating trade-off emerged: as Pass@$k$ performance went up, Pass@1 performance dropped. This is a massive operational bottleneck because Pass@1 remains a hard constraint due to latency budgets, API costs, and the need for a reliable single-shot fallback.
This paper uncovers the root cause of this trade-off, providing a theoretical and empirical characterization of how Pass@$k$ optimization induces gradient conflict via prompt interference.
Methods
The authors tackle this problem by building a rigorous mathematical framework around policy gradients:
- Prompt Similarity Kernel: They introduce a kernel, $\kappa_\theta(x, x') = \langle \nabla p_\theta(x), \nabla p_\theta(x') \rangle$, which measures whether a parameter update that improves the success probability of prompt $x$ will help (positive interference) or hurt (negative interference) prompt $x'$.
- Gradient Conflict Characterization: They derive an exact expression for the inner product between the population gradients of Pass@$k$ and Pass@1. This allows them to mathematically define when the two objectives form an obtuse angle (i.e., conflict).
- Toy Example & Proofs: They validate the math using a minimal contextual-bandit abstraction to simulate easy vs. hard prompt distributions, proving a phase transition where increasing $k$ mathematically guarantees Pass@1 degradation.
- LLM Gradient Analysis: They empirically compute the actual gradients of final hidden layers in open-source reasoning models to see if these theoretical conditions occur in real-world training.
Datasets
The empirical validation was conducted using the MATH dataset (Hendrycks et al., 2021), which consists of competition-style high school math problems across seven subjects. The authors randomly sampled 2,000 problems for their evaluation.
Key Insights and Ideas
- The Implicit Reweighting Trap: Pass@$k$ optimization doesn't treat prompts equally. It implicitly multiplies each prompt's gradient by a weight proportional to $(1 - p_\theta(x))^{k-1}$. As $k$ grows, prompts with a high success probability (easy prompts) are aggressively downweighted to near-zero, while low-success prompts (hard prompts) are massively amplified.
- Reweighting Meets Interference: If the hard prompts happen to be negatively interfering—meaning the parameter changes required to solve them actively damage the model's ability to solve easy prompts—the Pass@$k$ gradient direction rotates completely away from the Pass@1 direction.
- Collinear Per-Prompt, Conflicting in Population: Crucially, at an individual prompt level, the Pass@$k$ gradient is always perfectly aligned (positively collinear) with the Pass@1 gradient. The conflict is an emergent property that only appears when averaging across a diverse population of prompts.
Key Results
The authors tested their theory on two high-performing reasoning models: DeepSeek-R1-Distill-Llama-8B and DeepSeek-R1-Distill-Qwen-7B.
- Extreme Weight Disparity: In practice, the Pass@$k$ objective creates mind-boggling weight ratios exceeding $10^{28}:1$. Hard prompts receive significant gradient updates, while easy prompts receive negligible weights around $10^{-28}$.
- Flipped Gradients: On Llama-8B, this extreme reweighting caused a critical downward shift in the gradient agreement score, flipping the inner product between Pass@$k$ and Pass@1 to a negative value (-0.613).
- The Minority Rules: On Qwen-7B, despite the dataset containing a 21.6:1 ratio heavily favoring easy prompts (627 easy vs. only 29 hard prompts), the weight disparity allowed those 29 hard prompts to completely dominate the gradient, resulting in a massive negative inner product of -181.
Limitations and Future Work
- Diagnostic Focus: The paper focuses heavily on diagnosing and mathematically characterizing why the degradation happens, rather than introducing a brand-new optimization algorithm to fix it.
- Layer-Banded Gradients: For computational efficiency, the empirical gradients were only computed with respect to the parameters in the language model's final hidden layer, rather than across the entire network.
- Future Directions: The authors point toward "gradient surgery" (selectively altering conflicting prompt gradients using their similarity kernel) and exploring alternative concave objective functions that can harvest multi-attempt gains without sacrificing single-shot reliability.
Summary updated