Technical Summary: ALGOBENCH

Problem Statement

Current large language model (LLM) benchmarks for code generation, such as HumanEval and LiveCodeBench, often yield high pass rates that do not necessarily reflect genuine algorithmic reasoning capabilities. A primary limitation is data contamination: established problem statements, editorials, and reference solutions are widely available in public training corpora. Consequently, models may achieve high scores by recalling memorized solution patterns rather than deriving algorithms from constraints. While recent benchmarks attempt to mitigate this by using newer or harder problems (e.g., LiveCodeBench, ProBench, HLCE), these remain static. Once released, their problem statements and model-generated solutions inevitably enter training data, allowing future models to improve via exposure rather than enhanced reasoning. There is a need for a benchmark that dynamically generates problems where memorizing the source solution is insufficient, forcing models to adapt their algorithmic strategies.

Methodology

Core Framework: ALGOBENCH

The authors propose ALGOBENCH, a framework for automatically constructing novel algorithmic problems from known competitive programming sources. The core philosophy is constraint-shifting transformation: modifying a source problem such that the original reference algorithm fails, necessitating a new algorithmic approach or a different asymptotic complexity.

1. Transformation Operators
The framework employs ten rule-based transformation operators to generate variants ($q'$) from source problems ($q$). These include:

• Constraint Scaling (CS): Increasing input bounds (e.g., $N \le 2000 \to N \le 2 \times 10^5$).
• Static-to-Dynamic (SD): Converting static problems to dynamic ones (e.g., adding update operations).
• Objective Perturbation (OP): Changing the optimization goal.
• Greedy-Trap Injection (GT): Introducing constraints that invalidate greedy heuristics, requiring dynamic programming.
• Other operators include Constraint Coupling, Edge-Case Expansion, Output Requirement Change, and broader transformations like Real-World Wrapping and Graph-Structure Change.

2. Quality Gates
To ensure validity and prevent triviality, generated problems must pass four automated gates:

• Gate 1 (Old-Solution Rejection): The original reference solution ($a^*$) must fail on the new problem (producing WA, TLE, or MLE).
• Gate 2 (New Solution Verification): A new reference solution ($\hat{a}^*$) must be verified against a brute-force oracle on small inputs.
• Gate 3 (Non-Paraphrase): The generated statement must be sufficiently distinct from the source (TextSim $< \tau_{text}$).
• Gate 4 (Complexity Certification): The new solution must satisfy the target time and space complexity.

3. Deterministic Complexity Verifier
A three-layer verifier assesses submitted solutions to distinguish between functional correctness and algorithmic optimality:

• Layer 1 (Static AST Analysis): Parses code to estimate time/space complexity based on loop nesting, recursion, and data structures.
• Layer 2 (Algorithm-Tag Verification): Checks for structural evidence of expected algorithms (e.g., lazy propagation for segment trees) and absence of forbidden ones.
• Layer 3 (Calibrated Runtime Scaling): Runs solutions on increasing input sizes to fit a runtime model $T(n) = cn^\alpha (\log n)^\gamma$. Solutions are penalized if the fitted exponent exceeds the target by more than 0.15.

Evaluation Metrics

Beyond standard pass@k, ALGOBENCH introduces complexity-aware metrics:

• OPTT/OPTS: Rates of submissions that are correct and meet target time/space complexity.
• TRAPRATE: The fraction of incorrect submissions that structurally reuse the source algorithm (indicating "old-solution trap").
• GAPT (Efficiency Gap): Measures the gap between the fitted runtime exponent and the target exponent.
• CONSENS: Measures performance drop as constraint magnitude increases.
• $\Delta_{gen}$: The performance drop from source problems to generated variants.

Key Contributions

1. Framework: Introduction of ALGOBENCH, an automatic pipeline for generating traceable but algorithmically distinct problems.
2. Transformation & Validation: Design of ten transformation operators and a four-gate quality control system ensuring generated problems reject old solutions and require new complexity.
3. Benchmark Dataset: Construction of a benchmark with 598 accepted variants (420 used in main experiments) derived from 300 source problems (Codeforces, AtCoder, Kattis, LeetCode Hard), complete with metadata, reference solutions, and brute-force oracles.
4. Metrics: Proposal of metrics (OPTT, OPTS, TRAPRATE, GAPT, CONSENS) that evaluate asymptotic suitability, not just functional correctness.
5. Empirical Findings: Evaluation of seven LLMs across six prompting strategies, demonstrating that performance degrades significantly on generated variants and that many "correct" solutions fail complexity requirements.

Experimental Results

Performance Drop and Adaptation

• Generalization Gap: Models show a sharp decline in performance when moving from source problems to ALGOBENCH variants. Older models dropped from an average 85.1% pass@1 on sources to 53.6% on variants. Even the latest frontier models (GPT-5.4, Claude Opus 4.5) dropped by 33.3%.
• Complexity Mismatch: A significant gap exists between pass@k and OPTT. For instance, GPT-4o achieved 72.7% pass@5 but only 63.6% OPTT, indicating that many passing solutions used suboptimal algorithms.
• Retrieval Risks: Retrieval-Augmented Generation (RAG) using source problems as context often increased TRAPRATE. For Gemini 2.5 Flash, RAG increased the trap rate from 3.6% to 30.0%, suggesting retrieval anchors models to the original (now invalid) solution.

Error Analysis

Analysis of 400 failed submissions revealed that failures are predominantly algorithmic rather than implementation-level:

• Old-Solution Trap (42.3%): Models implemented the source algorithm, passing public examples but failing hidden trap tests.
• Too Slow (21.8%): Models identified the correct approach but missed necessary optimizations (e.g., failing to switch from $O(N^2)$ to $O(N \log N)$).
• Implementation Bugs: Accounted for only 9.0% of failures.

Sensitivity and Contamination

• Constraint Sensitivity: Performance degraded sharply as input bounds increased (e.g., $N=10K \to 50K$), precisely where quadratic solutions time out.
• Contamination Effect: Models performed significantly better on older source problems (2020) compared to newer ones (2024), suggesting memorization. However, this gap narrowed for ALGOBENCH variants, which remained consistently difficult regardless of the source problem's publication year.

Significance and Claims

The paper claims that ALGOBENCH evaluates a distinct capability from standard code benchmarks: the ability to adapt algorithmic reasoning to novel constraints rather than relying on memorized templates.

• Beyond Functional Correctness: The benchmark demonstrates that high pass rates on static datasets do not guarantee asymptotic suitability. Many models produce solutions that are functionally correct but algorithmically inefficient.
• Robustness to Memorization: By automatically generating problems where the source solution fails, ALGOBENCH mitigates the risk of training-data contamination, providing a more reliable measure of true algorithmic reasoning.
• Diagnostic Value: The framework identifies specific failure modes (e.g., inability to transition from Greedy to DP, or failure to handle dynamic updates) that are obscured in traditional benchmarks.

The authors conclude that current LLMs struggle when familiar templates are insufficient, and that future progress in algorithmic reasoning requires benchmarks that demand genuine adaptation rather than pattern matching.