Vol. XXI · Evaluation Plate 4 of 10pass@k, unbiased estimator, sampling, code evaluation, HumanEval, bias, combinatoricsEL

Pass@k.

Draw n samples, count c correct, and compute 1 − C(n − c, k)/C(n, k) — not 1 − (1 − c/n)^k.

For code, a solution can be checked by running tests, so it is natural to ask whether a model solves a problem in k attempts: pass@k. Chen and colleagues (2021), introducing HumanEval, noted that estimating it from exactly k samples is noisy, and that the obvious alternative — sample n, estimate the success rate p̂ = c/n, report 1 − (1 − p̂)^k — is biased: 1 − (1 − p)^k is a concave function of p, so by Jensen’s inequality plugging in the noisy estimate p̂ gives, on average, less than the true pass@k. The unbiased estimator is the probability that k samples drawn without replacement from the n include at least one correct: 1 − C(n − c, k)/C(n, k).

The workshop applies both to real samples: the fine-tuned model of plate XVII.1 answers each of the 30 held-out sums 16 times at temperature 1; c is the count correct for each. It compares the estimators for each k and shows how far they differ.

Below: left, pass@k on the held-out sums by the unbiased estimator and by the plug-in formula, against k. Right, the number of correct samples out of 16 for each question.

What you will learn
Workshop
The fine-tuned model, 16 samples per held-out sum at temperature 1, c correct per sum. Unbiased: the combinatorial estimator averaged over the 30 sums. Plug-in: 1 − (1 − c/n)^k per sum, averaged. Only k ≤ n is defined for the unbiased estimator.

Unbiased, from every sample

From 16 samples per question, pass@1 is 49.6% by either estimator — at k = 1 they coincide. At k = 8 the unbiased estimate is 69.3% and the plug-in 68.1%; at k = 16, 73.3% against 70.7%. The plug-in formula under-states pass@k here because for a question solved in, say, 1 of 16 samples it assigns a chance of finding a solution in 16 tries of only 1 − (15/16)¹⁶ ≈ 64%, while the samples drawn show one was found. 8 questions were never solved in 16 tries and 4 always were.

The practical rules from Chen and colleagues still apply: draw n well above k (they used n = 200 for k up to 100), compute the unbiased estimator in a numerically stable form, and report which k. pass@1 measures the typical answer, large k measures reach — the distinction that matters for RL-trained models (plate XIX.9) and for any system that can try several times and check (plate XIX.10).

The combinatorial ratio C(n − c, k)/C(n, k) is computed as a running product of (1 − k/i) for i from n − c + 1 to n, which avoids the huge binomial coefficients that overflow at realistic n.

Terms

pass@k
The probability that at least one of k samples is correct.
Unbiased estimator
An estimator whose expectation equals the true value.
Plug-in estimate
Substituting an estimated parameter into a formula.
n
The number of samples drawn per problem, at least k.
Estimate pass@k with 1 − C(n − c, k)/C(n, k) from n ≥ k samples, not by plugging c/n into 1 − (1 − p)^k.

Sources

  1. Chen et al., “Evaluating Large Language Models Trained on Code”, arXiv:2107.03374, 2021, section 2.1 and appendix A.
  2. Kulal et al., “SPoC: Search-based Pseudocode to Code”, NeurIPS 2019 (pass@k).