pass@k Estimator

mediumPROProduction: Cost, Caching & EvalsAI AgentsAI Agents 1

Problem Statement

Estimate pass@k, the probability that at least one of k sampled generations passes, given n total samples of which c passed. This is the standard unbiased HumanEval estimator.

Background

The unbiased estimator is

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

If n - c < k (fewer failures than k), pass@k is exactly 1.0 (every draw of k must include a pass). Compute it stably.

Your Task

def pass_at_k(n, c, k):

Return the pass@k estimate as a float rounded to 6 decimals.

Input Format

n (int total samples), c (int correct), k (int), with 0 <= c <= n, 1 <= k <= n.

Output Format

A float rounded to 6 decimals.

Sample

print(pass_at_k(5, 1, 1))

Output:

0.2

Example

Input

print(pass_at_k(5, 1, 1))

Output

0.2

Reasoning

Check for guaranteed pass: Compare the number of failures ( $n - c$ ) against $k$ . With $n=5$ and $c=1$ , there are $5 - 1 = 4$ failures. Since $4 \ge 1$ ( $k$ ), it is not guaranteed that a pass is included in the sample, so we proceed to the probabilistic calculation.
Calculate the failure probability: The term $\frac{\binom{n-c}{k}}{\binom{n}{k}}$ represents the probability that all $k$ samples are failures. For $k=1$ , this simplifies to the ratio of failures to total samples: $\frac{5-1}{5} = \frac{4}{5} = 0.8$ .
Compute the pass probability: Subtract the failure probability from 1 to find the probability of at least one pass: $1 - 0.8 = 0.2$ .
Format the result: Round the result to 6 decimal places, yielding $0.200000$ , which is represented as 0.2.
The final output is 0.2

Constraints

If n - c < k, return 1.0.
Otherwise 1 - C(n-c,k)/C(n,k); compute with a stable product.
Round to 6 decimals.

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium Savings from a Semantic Cachemedium Cache Hit Rateeasy

Concept primerPREVIEW

1. Background Knowledge

pass@k is a standard metric in code generation evaluation (introduced in the HumanEval paper) that estimates the probability that at least one of $k$ independently sampled solutions is correct. Given $n$ total samples where $c$ are correct, the unbiased estimator is:

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

The term $\frac{\binom{n-c}{k}}{\binom{n}{k}}$ represents the probability that all $k$ draws are failures (i.e., none pass). Subtracting from 1 gives the probability that at least one passes. This is a hypergeometric probability: drawing $k$ items without replacement from a population of $n$ containing $n-c$ failures.

A critical edge case exists: if $n - c < k$ , it is impossible to draw $k$ failures because there aren't enough of them. In this scenario, every subset of size $k$ must contain at least one correct sample, so pass@k is exactly $1.0$ .

2. Algorithm Approach

The core challenge is numerical stability. Directly computing binomial coefficients $\binom{n}{k}$ via factorials will overflow for moderately large $n$ (e.g., $n > 170$ in double-precision floating point). Instead, compute the ratio $\frac{\binom{n-c}{k}}{\binom{n}{k}}$ using a product of ratios, which avoids large intermediate values.

The ratio can be expanded as:

$\frac{\binom{n-c}{k}}{\binom{n}{k}} = \prod_{i=0}^{k-1} \frac{n-c-i}{n-i}$

This product form is numerically stable because each factor is a ratio of two numbers of similar magnitude, keeping intermediate results bounded between 0 and 1.

3. Step-by-Step Strategy

Handle the edge case: If $n - c < k$ , return 1.0 immediately.
Initialize a variable fail_prob = 1.0 to accumulate the product.
Loop $i$ from $0$ to $k-1$ :

Multiply fail_prob by $\frac{n - c - i}{n - i}$ .

Compute the result as $1 - \text{fail\_prob}$ .
Round to 6 decimal places and return.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results