# FormulaOne: Measuring the Depth of Algorithmic Reasoning Beyond Competitive Programming

arXiv: https://arxiv.org/abs/2507.13337 · HTML: https://mlsanity.com/paper/2507.13337/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 34 references that are in the map.
- First posted on arXiv 17 Jul 2025.

## Builds on (most cited first, 14 of 14)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Humanity's Last Exam](https://mlsanity.com/paper/2501.14249/) (2025)
- [FrontierMath: A Benchmark for Evaluating Advanced Mathematical Reasoning in AI](https://mlsanity.com/paper/2411.04872/) (2024)
- [ARC-AGI-2: A New Challenge for Frontier AI Reasoning Systems](https://mlsanity.com/paper/2505.11831/) (2025)
- [Competitive Programming with Large Reasoning Models](https://mlsanity.com/paper/2502.06807/) (2025)
- [CodeElo: Benchmarking Competition-level Code Generation of LLMs with Human-comparable Elo Ratings](https://mlsanity.com/paper/2501.01257/) (2025)
- [ARC Prize 2024: Technical Report](https://mlsanity.com/paper/2412.04604/) (2024)
- [ALE-Bench: A Benchmark for Long-Horizon Objective-Driven Algorithm Engineering](https://mlsanity.com/paper/2506.09050/) (2025)
- [DynASP2.5: Dynamic Programming on Tree Decompositions in Action](https://mlsanity.com/paper/1706.09370/) (2017)
- [Enumeration of Minimal Hitting Sets Parameterized by Treewidth](https://mlsanity.com/paper/2408.15776/) (2024)

## Built on by (most cited first, 3 of 3)

- [The Illusion of Diminishing Returns: Measuring Long Horizon Execution in LLMs](https://mlsanity.com/paper/2509.09677/) (2025)
- [Large Language Model Reasoning Failures](https://mlsanity.com/paper/2602.06176/) (2026)
- [AutoCode: LLMs as Problem Setters for Competitive Programming](https://mlsanity.com/paper/2510.12803/) (2025)

## Abstract (arXiv)

Frontier AI models demonstrate formidable breadth of knowledge. But how close are they to true human -- or superhuman -- expertise? Genuine experts can tackle the hardest problems and push the boundaries of scientific understanding. To illuminate the limits of frontier model capabilities, we turn away from contrived competitive programming puzzles, and instead focus on real-life research problems. We construct FormulaOne, a benchmark that lies at the intersection of graph theory, logic, and algorithms, all well within the training distribution of frontier models. Our problems are incredibly demanding, requiring an array of reasoning steps. The dataset has three key properties. First, it is of commercial interest and relates to practical large-scale optimisation problems, such as those arising in routing, scheduling, and network design. Second, it is generated from the highly expressive framework of Monadic Second-Order (MSO) logic on graphs, paving the way toward automatic problem generation at scale; ideal for building RL environments. Third, many of our problems are intimately related to the frontier of theoretical computer science, and to central conjectures therein, such as the Strong Exponential Time Hypothesis (SETH). As such, any significant algorithmic progress on our dataset, beyond known results, could carry profound theoretical implications. Remarkably, state-of-the-art models like OpenAI's o3 fail entirely on FormulaOne, solving less than 1% of the questions, even when given 10 attempts and explanatory fewshot examples -- highlighting how far they remain from expert-level understanding in some domains. To support further research, we additionally curate FormulaOne-Warmup, offering a set of simpler tasks, from the same distribution. We release the full corpus along with a comprehensive evaluation framework.