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.
Figures & tables
Figure 1 : Valid solutions are sparse . (a) A toy puzzle with eight typed cells. (b) Its core structure, with one node per statement. On input codoku(10,20) , execution must follow entry -> b1 -> exit (blue), so b2 never runs (grey). With three choices per ID , two per CONST , and 25 for OP , there are 34×23×25=16,200 candidate fillings. Global constraints couple distant cells: the return value must be 1050 , which ties the return to c = - CONST and to the update in b1 (orange), and the three CONST cells share one constant table (green). (c) The six valid fillings: the branch condition admits two choices and the ID in the unexecuted b2 admits three; all other cells are forced.
Figure 2 : Building a codoku puzzle and checking a solution (for Figure 1 ). (a) Semantic reification populates a required CFG with symbolic inputs, intermediates, and output 1 , encodes the conditions imposed by the path π , and solves them in one SMT query 2 , returning a witness solution P⋆ . (b) Masking replaces shaded tokens with typed cells 3 . The witness supplies the constraints: its graph gives g , its constants the constant table C , and its run on i the path π and output o 4 . (c) A candidate is checked in the same places 5 : first statically (cells, structure, constants), then dynamically by running it on i 6 . Checking against Φ , not P⋆ , accepts valid fillings that differ from the witness.
Table 1 : Codokus challenge every evaluated agent, and larger profiles are more complex and generally harder . The left table displays average puzzle properties per profile. The right table shows mutually exclusive run outcomes ( Section 3.3 ): a run is exhausted when it reaches its time, cost, or request budget, and failed when it otherwise ends without a valid solution.
Figure 3 : Resource use rises with profile scale among solved runs . Each plot reports the per-run median and interquartile range.
Figure 4 : Agents combine several strategies to solve codokus . Each cell reports the percentage of solved runs that carry the corresponding strategy label. A run may carry several labels.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Small
Medium
Large
Metric
Mean
Std.
Med.
Q1
Q3
Mean
Std.
Med.
Q1
Q3
Mean
Std.
Med.
Q1
Q3
search space
Typed cells
58.5
17.4
58.5
46.0
71.3
134.7
62.4
114.5
89.8
168.0
366.5
162.1
313.0
263.0
444.8
ID
11.9
4.4
11.5
9.0
15.0
32.6
18.3
26.0
20.0
41.3
95.1
43.0
81.5
65.0
115.0
FUNC
0.0
0.0
0.0
0.0
0.0
0.8
1.1
0.0
0.0
1.0
2.9
2.8
2.0
1.0
4.0
CONST
14.7
5.7
14.0
10.0
19.0
32.1
12.7
29.0
23.8
39.0
78.6
33.5
69.5
54.8
95.3
Appendix
Table 2 : Puzzle metrics per profile. Values are rounded to one decimal place. Each profile reports mean with its standard deviation and median with the first and third quartile.
Figure 5 : Agents actively use tools, particularly for candidate search, but codoku puzzles make it difficult to translate tool calls into valid solutions . File : file inspection and editing. Search : candidate search. Execute : candidate execution. Debug : debugging and instrumentation. Validate : syntax checking and solution verification. Others : all other tool calls.
Tokens (K)
Model
Profile
Requests
Input
Cache read
Cache write
Output
Think
Cost ($)
Think (m)
Claude Opus 5
⋅ small
22.8
0.0
1,494.5
105.7
67.5
56.9
3.49
6.6
⋅ medium
29.7
0.1
2,312.4
283.9
97.2
84.6
5.85
9.4
⋅ large
33.6
0.1
2,934.5
368.8
123.2
111.1
7.20
12.3
GPT 5.6 Sol
⋅ small
39.7
0.1
1,126.1
39.9
19.9
10.2
1.20
2.2
⋅ medium
60.0
0.6
2,349.9
56.8
24.8
14.6
1.75
3.3
Appendix
Table 3 : Average requests, token usage, cost, and thinking time , reported over all 1,500 agent runs.
Exhausted
Failed
Model
Profile
Solved
Time
Cost
Requests
Stopped
Refusal
Length
Infra.
Claude Opus 5
Small
77
18
2
0
0
3
0
0
Medium
62
25
8
0
0
4
0
1
Large
50
21
24
0
0
1
4
0
GPT 5.6 Sol
Small
67
32
0
1
0
0
0
0
Medium
53
38
0
5
4
0
0
0
Appendix
Table 4 : Termination reason of all agent runs . The last row sums over all 1,500 runs. Exhausted and Failed group the reasons as in Table 1(b) .
Model
Profile
No sol.
Basics
Parse
Compile
Re- mask.
CFG
Exec. limit
EP
Output
Const.
Pass
Claude Opus 5
⋅ small
22
0
0
0
0
0
1
0
0
0
77
⋅ medium
37
1
0
0
0
0
0
0
0
0
62
⋅ large
47
0
0
0
0
0
0
3
0
0
50
GPT 5.6 Sol
⋅ small
32
0
0
0
0
0
0
1
0
0
67
⋅ medium
42
0
0
0
2
0
0
0
3
0
53
⋅ large
43
0
0
0
1
0
0
2
0
0
54
Appendix
Table 5 : Fine-grained checker verdict on the final candidate of each run . No sol. : no provided solution. The remaining columns give the first check that the candidate fails. Basics checks if all cells are filled, Re-mask. is the cell and structure preservation check, and Exec. limit is the checker’s execution time limit (5s) for the candidate ( Section 2.3 ).
Recent advances in large language models (LLMs) have shown that test-time scaling can substantially improve model performance on complex tasks, particularly in the coding domain. Under this paradigm, models use a larger token budget during inference to generate intermediate reasoning traces before producing a final answer. However, current evaluations primarily rely on competitive programming benchmarks, which may not capture the full range of reasoning abilities. In this work, we perform a systematic study of frontier reasoning models to understand their performance on real-world coding benchmarks. To gain more insights into the performance of such models, we devise a programmatic way to {\em automatically generate} coding tasks of arbitrary difficulty and structure from existing benchmarks. Using this framework, our analysis reveals that the structure of a reasoning trace, not just its contents, is a strong predictor of correctness. Motivated by this, we propose structured thought-trees as means to represent reasoning traces. To illustrate their use, we train a lightweight classifier on features extracted from thought-trees to predict trace correctness, and demonstrate that flagging and retrying structurally anomalous traces based on the extracted features yields consistent gains at lower complexity levels.
Turning ideas into full software projects from scratch has become a popular use case for language models. Agents are being deployed to seed, maintain, and grow codebases over extended periods with minimal human oversight. Such settings require models to make high-level software architecture decisions. However, existing benchmarks measure focused, limited tasks such as fixing a single bug or developing a single, specified feature. We therefore introduce ProgramBench to measure the ability of software engineering agents to develop software holisitically. In ProgramBench, given only a program and its documentation, agents must architect and implement a codebase that matches the reference executable's behavior. End-to-end behavioral tests are generated via agent-driven fuzzing, enabling evaluation without prescribing implementation structure. Our 200 tasks range from compact CLI tools to widely used software such as FFmpeg, SQLite, and the PHP interpreter. We evaluate 9 LMs and find that none fully resolve any task, with the best model passing 95% of tests on only 3% of tasks. Models favor monolithic, single-file implementations that diverge sharply from human-written code.
Many real-world coding challenges are open-ended and admit no known optimal solution. Yet, recent progress in LLM coding has focused on well-defined tasks such as feature implementation, bug fixing, and competitive programming. Open-ended coding remains a weak spot for LLMs, largely because open-ended training problems are scarce and expensive to construct. Our goal is to synthesize open-ended coding problems at scale to train stronger LLM coders. We introduce FrontierSmith, an automated system for iteratively evolving open-ended problems from existing closed-ended coding tasks. Starting from competitive programming problems, FrontierSmith generates candidate open-ended variants by changing the problems'goals, restricting outputs, and generalizing inputs. It then uses a quantitative idea divergence metric to select problems that elicit genuinely diverse approaches from different solvers. Agents then generate test cases and verifiers for the surviving candidates. On two open-ended coding benchmarks, training on our synthesized data yields substantial gains over the base models: Qwen3.5-9B improves by +8.82 score on FrontierCS and +306.36 (Elo-rating-based performance) on ALE-bench; Qwen3.5-27B improves by +12.12 and +309.12, respectively. The synthesized problems also make agents take more turns and use more tokens, similar to human-curated ones, suggesting that closed-ended seeds can be a practical starting point for long-horizon coding data.
Runyuan He, Qiuyang Mang, Shang Zhou +14
UC Berkeley · UC San Diego · University of Washington +4