pass@k Scorecard for an Agent Eval Suite

1. Background Knowledge

The pass@k metric is a standard evaluation method in AI agent and code generation research, particularly for benchmarks like HumanEval or SWE-bench. Because Large Language Models (LLMs) are stochastic, a single execution does not reliably reflect an agent's capability. Instead, we sample $k$ independent attempts for a given task. The metric estimates the probability that at least one of these $k$ attempts produces a correct solution.

The formula provided, $\text{pass@}k = 1 - \frac{\binom{n - c}{k}}{\binom{n}{k}}$, is an unbiased estimator derived from combinatorics. Here, $n$ is the total number of runs for a task, and $c$ is the count of successful runs. The term $\binom{n}{k}$ represents the total ways to choose $k$ runs from $n$. The term $\binom{n - c}{k}$ represents the ways to choose $k$ runs such that all of them are failures (since there are $n-c$ failures total). Subtracting this ratio from 1 gives the probability that the chosen set of $k$ runs contains at least one success.

Crucially, this problem involves aggregation and grouping. You are not just calculating a single metric; you are processing a stream of heterogeneous data points (runs) into structured statistics. This requires grouping data by task_id to compute per-task metrics, and then aggregating those metrics globally and by tag. The concept of a flaky task ($0 < c < n$) highlights the importance of analyzing variance in agent performance, not just the mean.

2. Algorithm Approach

The core algorithmic pattern here is Map-Reduce or Group-By-Aggregate.

1. Grouping (Map): Iterate through the input runs list once. Group the runs by task_id. During this pass, you must also capture the tag associated with each task (specifically from the first occurrence of that task in the list) and count the number of passes ($c$) and total runs ($n$) for each task.
2. Per-Task Calculation (Reduce): For each unique task, apply the pass@k formula. Handle the edge case where $n < k$ by using $k' = n$.
3. Aggregation: Compute the global mean of these per-task scores. Simultaneously, group these scores by tag to compute tag-specific means.
4. Filtering: Identify tasks where $0 < c < n$ to populate the flaky list.

This approach ensures that you process the data in $O(N)$ time, where $N$ is the number of runs, avoiding repeated scans of the input list.

3. Step-by-Step Strategy

1. Initialize Data Structures: Create a dictionary to store task statistics. Keys will be task_id, and values will be objects or dictionaries containing n (total runs), c (passed count), and tag.
2. Process Runs:

• Iterate through each run in the runs list.
• If the task_id is not in your dictionary, initialize it with n=0, c=0, and store the tag from this run.
• Increment n for this task.
• If passed is True, increment c.

3. Compute Per-Task Metrics:

• Create a list to hold per-task pass@k scores.
• Create a dictionary to hold tag-specific scores.
• Create a list for flaky tasks.
• Iterate through the collected task statistics.
• For each task, determine the effective $k$ value: $k_{eff} = \min(k, n)$.
• Calculate $\text{pass@}k_{eff} = 1 - \frac{\binom{n - c}{k_{eff}}}{\binom{n}{k_{eff}}}$. Note: If $n - c < k_{eff}$, the numerator is 0, resulting in a score of 1.0.
• Append this score to the global list and to the list corresponding to its tag.
• If $0 < c < n$, add the task_id to the flaky list.

4. Final Aggregation:

• Calculate pass_at_k as the mean of the global score list, rounded to 4 decimal places. Handle the empty case.
• Calculate by_tag by iterating through sorted unique tags. For each tag, compute the mean of its associated scores, rounded to 4 decimal places.
• Sort the flaky list alphabetically.

5. Return Result: Construct and return the dictionary with keys tasks, pass_at_k, by_tag, and flaky.

4. Common Pitfalls

• Tag Assignment: The problem states the tag is taken from the first run of a task. If you simply update the tag on every run, you might overwrite the correct tag if later runs have different tags (though the problem implies consistency, strict adherence to "first run" is safer).
• Combinatorial Edge Cases: When $n < k$, you must use $k' = n$. If you blindly pass $k$ to math.comb(n, k) where $k > n$, it may raise a ValueError or return 0 depending on the implementation, leading to incorrect division or errors.
• Division by Zero: Ensure you handle the case where there are no tasks (tasks == 0) to avoid division by zero when calculating the mean.
• Rounding Precision: Python's round() function uses "banker's rounding" (round half to even). While usually acceptable, ensure you round the final mean, not intermediate per-task scores, to minimize cumulative floating-point error.
• Sorted Output: The by_tag dictionary keys must be in sorted order. In Python 3.7+, dictionaries maintain insertion order, so you must iterate through sorted tags when building the dictionary. The flaky list must also be sorted.
• Flaky Definition: A task is flaky if it has some passes and some failures. A task with $c=0$ (all fail) or $c=n$ (all pass) is not flaky.

5. Time & Space Complexity

• Time Complexity: $O(N + T \log T)$, where $N$ is the number of runs and $T$ is the number of unique tasks.
• Iterating through runs takes $O(N)$.
• Calculating combinations is $O(1)$ for small integers or $O(k)$ depending on implementation, but generally negligible compared to $N$.
• Sorting the flaky list and the tags for by_tag takes $O(T \log T)$.
• Space Complexity: $O(T)$, where $T$ is the number of unique tasks.
• We store statistics for each unique task in a dictionary.
• The output structures (by_tag, flaky) also scale with the number of tasks.
• This is efficient as we do not store the entire input list in memory beyond the initial pass.