2026-02-25

Foundations of Pass@k Optimization

In many verifiable tasks, such as code generation and short-answer math, a system can afford multiple response attempts for the same prompt and check the correctness of each response attempt with an automatic verifier... The corresponding metric, pass@k, measures the probability that at least one of k i.i.d. samples solves the prompt.

The pass@k objective is defined as the probability that at least one response is correct among k responses, i.e., Jk(θ) := E_x~D [1 – (1 – p_θ(x))^k]. This can be written using the nonlinear transformation f_k(p) := 1 − (1 − p)^k. Pass@k optimization can be performed using pass@k policy gradients, where ∇J_k(θ) = E_x~D[W_k(p_θ(x))∇p_θ(x)], and w_k(p) := k(1 − p)^k-1.

The per-prompt success probability for any x ∈ X and any policy parameter θ ∈ R^d is P_θ(x) := E_y~πθ(·|x) [r(x, y)], with its gradient ∇p_θ(x) = E_y~πθ(·|x) [r(x, y)s_θ(x, y)], where s_θ(x, y) := ∇ log π_θ(y|x) is the score function. The weights W_k(p_θ(x)) emphasize low-probability of success prompts.

Introducing Prompt Interference

We introduce the concept of prompt interference. We say that two given prompts are positively (resp. negatively) interfering if a policy parameter update which increases the probability of providing a correct response for that prompt tends to increase (resp. decrease) the probability of success of the other prompt. To capture the similarity between prompts in terms of pass@1 gradient representation, we introduce a similarity kernel κ_θ(x, x') := (∇p_θ(x), ∇p_θ(x')). This kernel informs on whether improving pass@1 on one prompt tends to also improve pass@1 on another prompt.

Illustration of negative prompt interference: It follows that the per-prompt success probability defined in (1) is given by p_θ(x) = π_θ(y*(x)|x) for any prompt x ∈ X... two prompts that have a similar representation will have opposite per-prompt pass@1 gradients and will hence be negatively interfering.

Figure 2 interpretation: The cosine kernel heatmap visually demonstrates prompt interference. Blue regions correspond to negative prompt interference, where improving one prompt's success actively harms another due to shared policy parameters. This phenomenon is central to understanding the pass@k/pass@1 trade-off.

The Core of Gradient Conflict

We show that pass@k and pass@1 gradients can be conflicting in the sense that they can form an obtuse angle. This implies that a policy update following pass@k's policy gradient tends to increase pass@k while decreasing pass@1. We provide a characterization of this gradient conflict by establishing an interpretable expression for the inner product between pass@k and pass@1.

Our key insight: Compared to pass@1, optimizing the pass@k objective induces an implicit prompt reweighting toward prompts with lower success probability (i.e., prompts the current policy rarely solves). When these prompts contribute gradients that conflict with the population pass@1 gradient, upweighting them increases their influence on the pass@k policy gradient update. Consequently, the pass@k gradient can conflict with the pass@1 gradient direction.

Sufficient conditions and influence of k: Using our gradient conflict characterization, we provide sufficient conditions under which gradient conflict occurs. We further study the influence of the parameter k and show that increasing k encourages gradient conflict under some conditions in the relative probability of success in negatively versus positively interfering prompts.

Pass@1 degradation under pass@k updates: We prove that pass@1 decreases while pass@k increases (simultaneously) under one-step pass@k policy updates satisfying an explicit stepsize condition.

Figure 3 interpretation: This contour plot illustrates the pass@1 and pass@k objectives in parameter space. The gradients are conflicting in the gray area, meaning updates for pass@k can move the policy in a direction that lowers pass@1.

Experimental Evidence & Real-world Models

We empirically test whether the pass@k objective can induce gradient conflict with pass@1 on math reasoning, as predicted by Proposition 4.1. We use the MATH dataset (Hendrycks et al., 2021) and run experiments with two reasoning models: DeepSeek-R1-Distill-Llama-8B and DeepSeek-R1-Distill-Qwen-7B.

Our experiments validate the theoretical predictions in several ways. First, the agreement scores show clear separation between hard prompts (negative agreement scores clustered below zero) and easy prompts (positive agreement scores above zero), confirming that prompt interference exists in practice.

Second, the pass@k weights reveal extreme disparity in how pass@k values different prompts. Hard prompts (low pass@1 values) receive weights orders of magnitude higher than easy prompts, demonstrating the extreme reweighting mechanism our theory identifies.

Third, the weighted agreement scores demonstrate the consequence of this reweighting. For Llama-8B, the gradient alignment flips from positive to negative, resulting in an inner product of −0.613. For Qwen-7B, despite only 29 hard prompts versus 627 easy, the extreme weight disparity causes an even more dramatic shift (∆ = −3.04 × 10⁻¹), yielding a strongly negative inner product of -181.

Figure 6 interpretation: These panels vividly show how pass@k reweighting causes gradient conflict. Column A shows prompt interference. Column B highlights the extreme reweighting of hard prompts by pass@k. Column C demonstrates the resulting downward shift in weighted agreement, leading to a negative inner product between pass@k and pass@1 gradients, confirming the conflict.