Skip to content

Codoku: Renewable Program-Reasoning Challenges for Frontier Coding Agents

Sep 2026 · arXiv.org · Vol abs/2609.34661 · 0 citations · 25 references
Computer Science

TL;DR

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, is introduced.

Abstract

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.

View source

Similar papers

Preprint Aug 2026

Improving Constraint Models with LLM Agents

This work introduces an agentic framework that reformulates a constraint model from an open-ended space and establishes correctness empirically rather than by construction, and demonstrates that autonomous agentic methods can support the improvement of constraint models.

Florentina Voboril, Stefan Szeider · 0 citations
#artificial intelligence Preprint Sep 2026

Synthesizing Reactive Character Behaviors for Continuous Games via Programmatic Policy Search

We present a method for synthesizing reactive character behaviors for continuous games as compact, human-readable programs. Game AI practice still relies heavily on manually authored behavior trees, state machines, and scripts, while academic reinforcement learning typically produces opaque neural controllers that are...

Maxim Gumin, Hsueh-Ti Derek Liu, Victor B. Zordan et al. · 0 citations
#artificial intelligence Preprint Aug 2026

CEDAR: Automata as Verifiable Interfaces for Language-Guided Embodied Action

CEDAR is presented, a counterexample-guided framework that grounds instructions as regular languages over environment event traces and represents both skills and specifications as deterministic finite automata, suggesting that regular languages offer a practical verification layer between natural-language instructions...

Le Chen, Alvaro Velasquez, Ashutosh Trivedi · 0 citations

State of Thought Enables Endogenous Reasoning

State of Thought is proposed, a new reasoning paradigm that enables endogenous reasoning in LLMs, with the model's internal reasoning state governing how reasoning unfolds, and provides a generalizable and efficient alternative to existing test-time reasoning paradigms.

Z. Gong, Yi-Kun Hou, Zi-Hao Zeng et al. · 0 citations
#artificial intelligence Review Sep 2026

Right Answers, Costly Models: The Efficiency Gap in LLM-based Optimization Modeling

This work systematically investigates whether LLMs can identify problem structure from natural-language descriptions and apply suitable optimization modeling techniques to generate mathematical models and solver code that solve the problems correctly and efficiently.

Zhong Li, Xin Huang, Jin-Hui Wan et al. · 1 citation
Preprint Aug 2026

One Recipe, Many Harnesses: What Self-Evolution Encodes Across Languages and Models

Together, these results recast the evolved harness as a legible compensation layer, shaped jointly by the language's engineering demands and the model's behavioral gaps, rather than an opaque benchmark-tuned scaffold.

Siqi Yang, Qianlan Yang, Yu-Xiong Wang et al. · 2 citations

Related blog posts

Hugging Face Blog Nov 10, 2026

Decision Models in Hugging Face

We’re on a journey to advance and democratize artificial intelligence through open source and open science.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.