Bigobench Eval

bigobench-eval

BigO(Bench) -- Can LLMs Generate Code with Controlled Time and Space Complexity? — Chambon et al. (2025) (arXiv:2503.15242, 2025)

What this evaluates

Evaluates whether LLMs can accurately predict the time and space complexity of given code snippets and generate new code that satisfies explicit complexity constraints. It probes algorithmic reasoning and scalability awareness beyond mere syntactic or functional correctness.

Datasets

• BigO(Bench) — total ?; splits: test (-1); repo https://github.com/facebookresearch/bigobench

Metrics

• Pass@k (primary) — range: percent
  • Fraction of problems where at least one of the k generated samples passes correctness tests (generation) or matches the ground-truth complexity class (prediction). Evaluated using an unbiased estimator over 20 samples. Macro-averaged first by complexity class, then across problems.
• Best@k — range: percent
  • Accuracy measured only across the most optimized complexity class of each problem, ignoring suboptimal but correct classes.
• All@k — range: percent
  • Requires the model to correctly output the complexity across all complexity classes for a given problem simultaneously.
• Complexity Coefficient Ranking — range: percent
  • Percentile-based ranking of the best measured coefficient of the complexity curve (from 20 attempts) among human solutions of the same problem and complexity class. Lower coefficient indicates flatter curve and better optimization.

Input / output format

Input: For prediction: problem description paired with a human-written code snippet. For generation: problem description paired with an explicit time or space complexity requirement (e.g., O(n log n)).

Output: For prediction: a Big-O complexity class string. For generation: a Python code snippet implementing the solution.

Scoring recipe

def compute_metrics(predictions, gold, k=1):
    pass_count = best_count = all_count = 0
    for prob_preds, prob_gold in zip(predictions, gold.values()):
        classes = prob_gold['complexity_classes']
        best_class = prob_gold['most_optimized']
        if any(p in classes for p in prob_preds[:k]):
            pass_count += 1
        if any(p == best_class for p in prob_preds[:k]):
            best_count += 1
        if all(c in prob_preds for c in classes):
            all_count += 1
    return {
        'Pass@k': pass_count / len(gold),
        'Best@k': best_count / len(gold),
        'All@k': all_count / len(gold)
    }

Common pitfalls

• Confusing Pass@k, Best@k, and All@k, which evaluate different granularity levels of complexity correctness (any class vs. most optimized vs. all classes simultaneously).
• Assuming complexity is verified via static analysis; the benchmark uses a dynamic profiling framework with synthetic input fuzzing and regression to measure actual runtime/memory behavior.
• Failing to account for discarded empty outputs from reasoning models (e.g., o1-mini), which were excluded from metric computation and treated as an optimistic upper bound.

Evidence (verbatim from paper)

Pass@k measures the accuracy of finding the correct complexity; Best@k measures accuracy only across the most optimized complexity class of each problem; All@k requires correct complexity output across all complexity classes at once per problem.

Citation

@misc{chambon2025bigobench,
  title={BigO(Bench) -- Can LLMs Generate Code with Controlled Time and Space Complexity?},
  author={Chambon et al. (2025)},
  year={2025},
  note={arXiv:2503.15242}
}

• arXiv: 2503.15242