# k-server-bench: Automating Potential Discovery for the k-Server Conjecture

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 41 references that are in the map.
- First posted on arXiv 8 Apr 2026.

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

- [The AI Scientist: Towards Fully Automated Open-Ended Scientific Discovery](https://mlsanity.com/paper/2408.06292/) (2024)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [FrontierMath: A Benchmark for Evaluating Advanced Mathematical Reasoning in AI](https://mlsanity.com/paper/2411.04872/) (2024)
- [ShinkaEvolve: Towards Open-Ended And Sample-Efficient Program Evolution](https://mlsanity.com/paper/2509.19349/) (2025)
- [Mathematical exploration and discovery at scale](https://mlsanity.com/paper/2511.02864/) (2025)
- [ThetaEvolve: Test-time Learning on Open Problems](https://mlsanity.com/paper/2511.23473/) (2025)
- [Constructions in combinatorics via neural networks](https://mlsanity.com/paper/2104.14516/) (2021)
- [Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning](https://mlsanity.com/paper/2504.05108/) (2025)
- [Early science acceleration experiments with GPT-5](https://mlsanity.com/paper/2511.16072/) (2025)
- [Towards Autonomous Mathematics Research](https://mlsanity.com/paper/2602.10177/) (2026)
- [Semi-Autonomous Mathematics Discovery with Gemini: A Case Study on the ErdHos Problems](https://mlsanity.com/paper/2601.22401/) (2026)
- [First Proof](https://mlsanity.com/paper/2602.05192/) (2026)
- [DeltaEvolve: Accelerating Scientific Discovery through Momentum-Driven Evolution](https://mlsanity.com/paper/2602.02919/) (2026)
- [LoongFlow: Directed Evolutionary Search via a Cognitive Plan-Execute-Summarize Paradigm](https://mlsanity.com/paper/2512.24077/) (2025)
- [Learning selection strategies in Buchberger's algorithm](https://mlsanity.com/paper/2005.01917/) (2020)
- [Reinforced Generation of Combinatorial Structures: Hardness of Approximation](https://mlsanity.com/paper/2509.18057/) (2025)
- [Reinforced Generation of Combinatorial Structures: Ramsey Numbers](https://mlsanity.com/paper/2603.09172/) (2026)
- [Solving an Open Problem in Theoretical Physics using AI-Assisted Discovery](https://mlsanity.com/paper/2603.04735/) (2026)
- [Solving a Research Problem in Mathematical Statistics with AI Assistance](https://mlsanity.com/paper/2511.18828/) (2025)
- [Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle](https://mlsanity.com/paper/2102.10474/) (2021)
- [Deterministic 3-Server on a Circle and the Limitation of Canonical Potentials](https://mlsanity.com/paper/2205.08103/) (2022)
- [Applying language models to algebraic topology: generating simplicial cycles using multi-labeling in Wu's formula](https://mlsanity.com/paper/2306.16951/) (2023)

## Abstract (arXiv)

We introduce a code-based challenge for automated, open-ended mathematical discovery based on the k-server conjecture, a central open problem in competitive analysis. The task is to discover a potential function satisfying a large graph-structured system of simple linear inequalities. The resulting evaluation procedure is sound but incomplete: any violated inequality definitively refutes a candidate, whereas satisfying all inequalities does not by itself constitute a proof of the corresponding conjecture's special case. Nevertheless, a candidate that passes all constraints would be strong evidence toward a valid proof and, to the best of our knowledge, no currently known potential achieves this under our formulation in the open k=4 circle case. As such, a successful candidate would already be an interesting contribution to the k-server conjecture, and could become a substantial theoretical result when paired with a full proof. Experiments on the resolved k=3 regime show that current agentic methods can solve nontrivial instances, and in the open k=4 regime they reduce the number of violations relative to existing potentials without fully resolving the task. Taken together, these results suggest that the task is challenging but plausibly within reach of current methods. Beyond its relevance to the k-server community, where the developed tooling enables researchers to test new hypotheses and potentially improve on the current record, the task also serves as a useful benchmark for developing code-based discovery agents. In particular, our k=3 results show that it mitigates important limitations of existing open-ended code-based benchmarks, including early saturation and the weak separation between naive random baselines and more sophisticated methods.