The Unbiased Pass@k Estimator for Code Generation

For tasks with a programmatic correctness check, evaluation can be exact: run the tests, observe pass or fail. That removes the need for references and judges entirely, and it makes code generation one of the few domains where the ground truth is mechanical. It also makes the sampling design visible, because the natural metric, whether the model produces a correct program for this problem, is a property of a distribution over programs, not of a single sample.

The naive approach generates one program per problem, checks it, and reports the fraction that pass. That estimates the probability that one sample is correct. Reporting it as pass@k, the probability that at least one of $k$ samples is correct, is wrong by a wide margin, and the error grows with $k$. The correct estimator uses $n$ samples per problem, counts how many passed, and applies a combinatorial formula that accounts for sampling without replacement.

Why the naive estimator overstates

Suppose $n$ samples are drawn and $c$ of them pass the tests. The naive pass@k estimate is $1 - (1 - c/n)^k$, which treats each sample as an independent draw from a fixed correctness probability estimated as $c/n$. The problem is that $c/n$ is itself an estimate, and the formula uses it as though it were exact. When $c$ is small, which is exactly the regime where pass@k matters, the estimate is dominated by a few observations and the formula systematically overstates the probability of at least one success.

The direction is intuitive. If $c = 1$ out of $n = 200$, the empirical pass rate is 0.005, and the naive formula gives $1 - 0.995^k$. But that estimate is driven by a single success, and the true rate could be considerably lower. The combinatorial estimator below produces exactly $k/n$ in this regime, which is the probability that a specific set of $k$ draws includes the one success, which is much lower than the naive figure for moderate $k$.

The estimator that the code-generation literature uses computes the probability that a random size-$k$ subset of the $n$ samples contains at least one correct program, given that exactly $c$ of the $n$ are correct. The probability that all $k$ draws miss is the number of ways to choose $k$ from the $n-c$ failures over the number of ways to choose $k$ from all $n$:

$$\text{pass@}k = 1 - \frac{\binom{n-c}{k}}{\binom{n}{k}}$$

This is an unbiased estimate of pass@k under the model that the $n$ samples are exchangeable draws from the model’s distribution. It requires $n \ge k$, and in practice $n$ is chosen well above $k$ so the estimate is stable.

from math import comb

def pass_at_k(n, c, k):
    """n samples per problem, c of them correct, estimate of pass@k."""
    if n - c < k:
        return 1.0
    return 1.0 - comb(n - c, k) / comb(n, k)

def mean_pass_at_k(results, k):
    """results: list of (n, c) tuples, one per problem."""
    return sum(pass_at_k(n, c, k) for n, c in results) / len(results)

The formula is computed in log space in practice, because $\binom{n-c}{k}$ and $\binom{n}{k}$ are both astronomically large for realistic $n$ and their ratio is not. Taking logs of the binomial coefficients and exponentiating the difference keeps the computation in range; the direct ratio overflows for $n$ in the thousands even though the result is a modest probability.

Choosing n, and why it is not the same as k

The sample size $n$ is an evaluation-cost parameter, and it is decoupled from the reported $k$. A larger $n$ gives a more precise estimate of the underlying correctness probability, and the estimator’s variance falls as $n$ grows. Reporting pass@1 from $n = 200$ samples per problem gives a much tighter estimate than reporting pass@1 from $n = 1$, because each problem contributes 200 observations rather than one.

The trade is compute. Evaluating pass@100 with $n = 200$ requires 200 generations per problem, each one a full decode of a program that may be hundreds of tokens. The cost scales linearly in $n$ and in the number of problems, and the largest cost is usually the test execution rather than the generation. Test harnesses that run untrusted generated code need sandboxing, timeouts, and a memory cap per execution, and a program that loops forever consumes its timeout whether or not it is correct.

There is a subtler choice: temperature. Sampling at a low temperature produces near-duplicate programs, so $n$ samples carry less information than $n$ independent draws would, and the estimator’s variance is understated because the exchangeability assumption is violated. Sampling at a high temperature produces more diversity and more failures, and pass@1 falls while pass@k rises. The temperature is part of the metric definition and has to be reported with it, since pass@1 at temperature 0.2 and pass@1 at temperature 1.0 are not the same quantity.

Where the estimator’s assumptions break

Exchangeability is the load-bearing assumption. The $n$ samples for a problem are drawn from the same model with the same prompt, so they are identically distributed, but they are not independent: a sampling procedure with a fixed random seed produces correlated outputs across nearby seeds, and a prompt that primes a particular solution strategy will produce a cluster of similar programs. Positive correlation means the effective number of independent draws is below $n$, and the estimate inherits more variance than the formula implies.

The second assumption is that correctness is a binary property of a program. It is not. A program can pass the provided tests and be wrong on inputs the tests do not cover, which is the classic weakness of test-based evaluation: the tests are a finite sample of the input space, and a model can overfit to them. A program can also be correct but non-terminating on some inputs, or correct under the reference interpreter and wrong under another. The pass/fail signal is a property of the program under a specific test suite, and the suite’s coverage bounds the metric’s meaning.

The third is that a problem’s difficulty is captured by a single number. Averaging pass@k over problems weights a problem with a trivial solution the same as one that requires a non-obvious algorithm. Reporting per-problem pass@k in addition to the mean shows the distribution, and the distribution is typically bimodal: many problems are solved at $k = 1$ and many are never solved at any $k$, with few in between. An aggregate mean over that distribution hides which regime a system improvement came from.

Reading the number

Pass@k is a property of a sampling procedure, not of a model in isolation. It says: draw $k$ samples at this temperature, run these tests, and this fraction of problems will have at least one pass. It is the natural metric when the deployment pattern is generate-and-filter: produce several candidates, run the tests, submit the one that passes, because in that pattern the user only needs one success out of $k$. It is the wrong metric when the deployment pattern is single-shot, where pass@1 is the relevant quantity and pass@100 says nothing about it.

The gap between pass@1 and pass@k is itself informative. A large gap means the model can produce correct programs but cannot identify which of its samples are correct, which is a selection problem rather than a generation problem. In the generate-and-filter pattern the selection is done by the tests, so the gap is exploitable; in a pattern where the tests are unavailable, the gap measures how much the model’s own confidence fails to discriminate. The distinction between producing and selecting is the same one that separates generation quality from ranking quality in pairwise preference evaluation, where a system that can rank better than it can generate shows up as a gap between the two measurements.

Finally, the estimator is unbiased for a fixed problem and a fixed sampling procedure, but the aggregate over problems is a ratio of sums and its uncertainty needs the same treatment as any other evaluation statistic. Problems are the sampling unit, and the confidence interval should be computed by resampling problems, not samples within a problem, since the samples within a problem are the measurement and the problems are the population.