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 ).