pass@k Unbiased Estimator

Background

For verifiable tasks (code synthesis, math), the standard LLM eval metric is pass@k: the probability that at least one of $k$ independent samples from the model is correct. Naively estimating it as "I sampled $k$, did any pass?" is high-variance and wasteful. The HumanEval paper (Chen et al., 2021) introduced the unbiased estimator: sample $n \ge k$ candidates, count the number correct $c$, and apply a single combinatorial formula.

Problem statement

Implement pass_at_k(n, c, k) returning the unbiased estimate:

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

This is the probability that at least one correct candidate is in a random size-$k$ subsample drawn without replacement from the $n$ candidates - the standard interview-grade derivation.

Input

• n - int >= 1, total candidates sampled.
• c - int, with $0 \le c \le n$, number of correct candidates among the $n$.
• k - int, with $1 \le k \le n$, the target $k$ for $\mathrm{pass@}k$.

Output

• float in $[0, 1]$ - the unbiased estimate.

Examples

Example 1 - hand-computed

Input:  n=10, c=5, k=1
Output: 0.5

Explanation: $1 - \binom{5}{1}/\binom{10}{1} = 1 - 5/10 = 0.5$.

Example 2 - all candidates wrong -> 0

Input:  n=10, c=0, k=5
Output: 0.0

Example 3 - all candidates correct -> 1

Input:  n=10, c=10, k=5
Output: 1.0

Example 4 - mostly wrong, large k makes it nearly certain to hit a correct one

Input:  n=10, c=2, k=8
Output: 1 - C(8, 8) / C(10, 8) = 1 - 1/45 ~= 0.9778

Constraints

• $1 \le k \le n$; raise ValueError otherwise.
• $0 \le c \le n$; raise ValueError otherwise.
• When $n - c < k$ (you've subsampled more than the wrong-count), every size-$k$ subset must contain at least one correct - return exactly $1.0$.
• Return a plain Python float.

Notes

• Why the unbiased form. The naive $\mathrm{1}(c \ge 1)$ on a single trial is unbiased only for $k = n$. Drawing $n$ samples and computing the closed-form $\mathrm{pass@}k$ for many $k$ is far more sample-efficient than running fresh trials per $k$.
• Numerical stability. For large $n$ ($\gtrsim 10^3$), the ratio of binomials underflows in naive arithmetic - compute it iteratively as $\prod_{i=0}^{k-1} \tfrac{n - c - i}{n - i}$ to stay in $[0, 1]$.