# Codoku: Renewable Program-Reasoning Challenges for Frontier Coding Agents

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 16 of its 25 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)
- LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/)

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [CRUXEval: A Benchmark for Code Reasoning, Understanding and Execution](https://mlsanity.com/paper/2401.03065/) (2024)
- [CyberGym: Evaluating AI Agents' Real-World Cybersecurity Capabilities at Scale](https://mlsanity.com/paper/2506.02548/) (2025)
- [CodeI/O: Condensing Reasoning Patterns via Code Input-Output Prediction](https://mlsanity.com/paper/2502.07316/) (2025)
- [Pynguin: Automated Unit Test Generation for Python](https://mlsanity.com/paper/2202.05218/) (2022)
- [Reasoning Runtime Behavior of a Program with LLM: How Far Are We?](https://mlsanity.com/paper/2403.16437/) (2024)
- [CRUXEval-X: A Benchmark for Multilingual Code Reasoning, Understanding and Execution](https://mlsanity.com/paper/2408.13001/) (2024)
- [ExploitGym: Can AI Agents Turn Security Vulnerabilities into Real Attacks?](https://mlsanity.com/paper/2605.11086/) (2026)
- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [CoRe: Benchmarking LLMs Code Reasoning Capabilities through Static Analysis Tasks](https://mlsanity.com/paper/2507.05269/) (2025)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [CodeARC: Benchmarking Reasoning Capabilities of LLM Agents for Inductive Program Synthesis](https://mlsanity.com/paper/2503.23145/) (2025)
- [Mokav: Execution-driven Differential Testing with LLMs](https://mlsanity.com/paper/2406.10375/) (2024)
- [How Robustly do LLMs Understand Execution Semantics?](https://mlsanity.com/paper/2604.16320/) (2026)

## Abstract (arXiv)

Existing program-reasoning benchmarks ask large language models to predict a program's behavior on a given input. Coding agents break two assumptions on which these benchmarks rest: an agent can recover the answer by executing the program instead of reasoning about it, and fixed task sets drawn from existing programs are increasingly exposed to contamination, yet costly to renew. We introduce Codoku (code sudoku), a renewable benchmark in which a solver fills typed cells in a partial program to satisfy global static and dynamic constraints, such as a prescribed control-flow graph and execution path. Because a partial program cannot be executed and valid fillings are sparse in an exponentially large space of interdependent choices, neither tool use nor enumeration can substitute for program reasoning. Puzzles are synthesized from scratch via semantic reification, so fresh puzzles of controllable complexity can be generated on demand, each with a witness that guarantees solvability. We evaluate five frontier models on 300 puzzles through a coding agent free to use any tool within a fixed budget. Small puzzles already challenge open-weight models, whereas even proprietary models solve only about half of the large ones. Codoku thus offers a renewable testbed for program reasoning that can keep pace with rapidly improving coding agents. GitHub: https://github.com/connglli/Codoku.