Research map / Large language models / Agents, code and math
ALE-Bench: A Benchmark for Long-Horizon Objective-Driven Algorithm Engineering
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces ALE-Bench, a benchmark built from 40 AtCoder Heuristic Contest problems for evaluating LLMs and agents on long-horizon, score-based algorithm engineering, plus an ALE-Agent scaffold.
Problem
Existing AI coding benchmarks test short, pass/fail exact-solution problems, so they do not measure long-horizon iterative improvement on hard optimization problems with score-based objectives.
Approach
Turns real AtCoder Heuristic Contest tasks into a timed, sandboxed benchmark with test-run feedback, visualizers, and human-comparable performance and rating metrics, and proposes ALE-Agent with domain-knowledge prompting and beam-search-like diversity-oriented best-first search.
Key results
- In the one-shot setting, o3-high was the only model with average performance above 1000 (1044 overall), and no model exceeded 2000 performance on any problem.
- In the iterative-refinement setting over four hours, o4-mini-high reached average performance 1520 and rating 2104 (top 11.8% of humans), with 32.5% of problems at 1600+ performance.
- ALE-Agent with Gemini 2.5 Pro (Method 1 and Method 2) reached average performance 1879 on the lite subset, versus 1167 for the base agent.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Iteratively refine solutions using public test-run feedback | LLMs on ALE-Bench · ALE-Bench full | average performance: over 400 points | Helped |
| Add domain knowledge prompting (ablation) | ALE-Agent with Gemini 2.5 Pro · ALE-Bench lite | average performance: 1167 -> 1264 | Helped |
| Add diversity-oriented solution search to domain knowledge prompting (ablation) | ALE-Agent with Gemini 2.5 Pro · ALE-Bench lite | average performance: 1264 -> 1879 | Helped |
| Use OpenHands CodeActAgent scaffolding instead of sequential refinement | GPT-4.1 mini on ALE-Bench lite · ALE-Bench lite | average performance: 1016 -> 618 | Hurt |
| Use OpenHands CodeActAgent scaffolding instead of sequential refinement | o4-mini-high on ALE-Bench lite · ALE-Bench lite | average performance: 1411 -> 859 | Hurt |
| Use OpenHands CodeActAgent scaffolding instead of sequential refinement | Gemini 2.5 Pro on ALE-Bench lite · ALE-Bench lite | average performance: 1198 -> 903 | Hurt |
| Use C++20 instead of Python3 | LLMs in the one-shot setting · ALE-Bench full | average performance: 624 -> 668 | Helped |
| Use C++20 instead of Rust | LLMs in the one-shot setting · ALE-Bench full | average performance: 611 -> 668 | Helped |
| Use Rust instead of C++20 | LLMs in the one-shot setting · ALE-Bench full | percentage of problems with performance >=1600: 1.0 -> 1.1 | Helped |
| Use 150 independent One-Shot trials instead of iterative refinement | o4-mini-high · ahc006 | maximum performance: 2472 -> 2174 | Hurt |
| Use 150 independent One-Shot trials instead of iterative refinement | o4-mini-high · ahc005, ahc006, ahc012, ahc020, ahc041, ahc044 | maximum performance: approximately 300 points or more | Hurt |
| Use reasoning models rather than non-reasoning models in one-shot evaluation | LLMs on ALE-Bench · ALE-Bench full, one-shot | average performance | Helped |
Surprising findings
- Ratings overstate AI skill: o4-mini-high's rating places it in the top 11.8% of humans, yet its 32.5% rate of 1600+ performance is well below the human average of 56.2% in the same rating band.
- 150 independent one-shot trials per problem remained about 300 or more points below iterative refinement peaks, so brute-force parallel sampling does not match long-horizon refinement.
Limitations
- Only 40 problems from 49 contests, a relatively small benchmark size.
- Performance is approximated from rank only, not AtCoder's official calculation, and the sandbox may differ slightly from AtCoder's environment.
- Single run per model with no error bars due to API cost.
Experimental setup
Datasets: AtCoder Heuristic Contest problems (40 problems, AHC001-AHC046)
Benchmarks: ALE-Bench
Metrics: performance average performance rating performance distribution rank percentile
Baselines: GPT-4o GPT-4.1 GPT-4.1 mini Claude 3.7 Sonnet DeepSeek-R1 DeepSeek-V3 Gemini 2.5 Pro OpenHands
Builds on: Self-Refine FunSearch OpenHands CodeActAgent
Closest papers by meaning
- CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization (AAAI 2026 · similarity 0.87)
- Terminal-Bench: Benchmarking Agents on Hard, Realistic Tasks in Command Line Interfaces (ICLR 2026 · similarity 0.86)
- SWE-Marathon: Can AI Agents Autonomously Complete Ultra-Long-Horizon Software Work? (NeurIPS 2026 · similarity 0.86)
- MLE-bench: Evaluating Machine Learning Agents on Machine Learning Engineering (ICLR 2025 · similarity 0.86)
- Establishing Best Practices in Building Rigorous Agentic Benchmarks (NeurIPS 2025 · similarity 0.85)
- FML-bench: A Controlled Study of AI Research Agent Strategies from the Perspective of Search Dynamics (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.