- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces Codoku - a novel benchmark for assessing the performance of coding agent+harness combinations. The puzzle synthesis is performed using semantic reification algorithm for random program synthesis. Part of the program is then masked with symbols corresponding to their type and the agents are supposed to fill these masks in a way the checks out with several tests. The authors evaluate several agents to show that this benchmark is challenging.
Critical strengths
- The proposed benchmark allows synthesizing arbitrary many problems and is not saturated out of the box.
- The authors evaluate several state of the art open and closed source llms.
Critical weaknesses
- The codoku puzzles are inherently CSPs rather than programming problems, which are inherently much more open ended. The authors position these problems as benchmarks for coding agents, which may be misaligned.
- I think those would be very difficult to solve even for humans - from the few examples presented in the appendix. Would the conclusions from performance on these problems generalize?
- While the authors have provided analysis of the failure modes and techniques employed by various agents, the analysis could be broader, including more cherry picked failure analysis, and even more importantly - cumulative curves of the agent resource use (time / tokens / money ) per solutions attained - maybe all the problems will get solved if you give some of the agents enough time (overwhelming majority of failures are exhaustion).
- While the paper provides an artifact - the codoku benchmark, the overall novelty of the techniques used is difficult for me to assess, as I am not closely familiar with program synthesis literature.
Questions for authors
- Do differnt agents manage to solve an overlapping core of problems? Or could it be that different model/harness combination manage to solve different puzzles?
- The way the problem is formulated with the typed cells being enums / integers for the most part, could these problems be solved with a SAT solver or a SAT-aware neurosymbolic approach?
2 comments
Answer to Q1
Q1: Do differnt agents manage to solve an overlapping core of problems? Or could it be that different model/harness combination manage to solve different puzzles?
Yes, agents share a small solvable core, particularly among small puzzles: 23 are solved by all five models, compared with 11 for medium puzzles and only 3 for large puzzles. We will add a Venn diagram to illustrate these overlaps in the revision.
For harnesses, we selected Pi because it is lightweight, without vendor-specific prompting, orchestration, or tools that could obscure the underlying model’s reasoning or steer it along potentially biased paths. Different model-harness combinations may solve different sets of puzzles; investigating this further would be an interesting future work. We will clarify this rationale in the revision.
Answer to W3
W3: While the authors have provided analysis of the failure modes and techniques employed by various agents, the analysis could be broader, including more cherry picked failure analysis, and even more importantly - cumulative curves of the agent resource use (time / tokens / money ) per solutions attained - maybe all the problems will get solved if you give some of the agents enough time (overwhelming majority of failures are exhaustion).
The failure categories and analysis in Table 1(b) and Appendix A.4 already cover all 1,500 runs, including their termination reasons and fine-grained checker results.
Figure 3 and Appendix A.3 report average resource usage; Lines 442–443 and Appendix A.5 present the budget-extension experiment. We doubled all three limits (two hours, $30, and 256 requests) for the best-performing agent, GPT 5.6 Sol, on the large puzzles. Gains were modest and turned to converge: only 8 of 56 previously unsolved puzzles were solved, while the remaining reached the two-hour limit. Inspection suggests that ineffective subproblem decomposition and strategy selection, account for most failures and limit the benefits of larger budgets.
In the revision, we will move some content into the main text and add a cumulative curve of agent resource uses. We will also release all data.
Answer to W1
Codoku is indeed a CSP, but the domain is programs and it evaluates constraint-guided program reasoning.
Codoku concerns the static and dynamic semantics of a program: a valid solution must compile, match the control-flow graph, follow the execution path, and produce the expected return value on concrete inputs under a constant budget.
Formulating and solving these constraints combines:
Codoku is therefore a benchmark for a specific capability of coding agents, i.e., constraint-guided program reasoning: an agent must reason locally about each cell and globally about their inter-dependencies, infer candidate structures, and revise it when its behavior violates our constraints. We will clarify this scope in the paper.
Answer to W2/Q2
Codoku is challenging but tractable through constraint-guided program reasoning: the best-performing agent solves 50% of large puzzles, while three direct-search and -solve baselines solve none under the evaluated budget.
Finite cell domains permit SAT/SMT encodings. However, the challenge is not just assigning enum or integer values: the encoding must also capture the program's structure, control flow, data flow, and execution constraints. Following reviewers’ suggestions, we built three additional baselines (our agent experiment in Section 3 already demonstrates an SMT-aware neurosymbolic approach):
Each baseline attempted all 300 puzzles with checker access, unlimited candidate checks, and the paper's one-hour time budget per puzzle.
Across 900 solver-puzzle runs, none succeeded, and 98% timed out, consistent with Codoku’s design to make undirected search (without program reasoning) ineffective.
But Codoku puzzles remain tractable through reasoning about local program states and decomposing puzzles into smaller subproblems. Successful agents combine this local reasoning with algebra, search, constraint solving, repair, and other strategies, as presented in Section 4.1. The best-performing agent solves 50% of large puzzles, indicating a level of difficulty comparable to TerminalBench and FrontierCode.
Our goal is to elicit, thus evaluate, the program reasoning capabilities of agents. We agree with the reviewer that whether performance transfers to broader coding tasks is an interesting question, which we leave for future work.