- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper studies whether a one-layer, one-head Transformer can solve Sudoku when paired with an external harness that handles candidate tracking, constraint propagation, and backtracking. Trained by imitating a minimum-remaining-values (MRV) solver on easy puzzles, the 0.87M-parameter model reportedly solves all evaluated easy, medium, and hard puzzles.
Critical strengths
The small architecture enables a detailed mechanistic analysis, supported by interventions on inputs and activations. The problem of Sudoku is a very well explored problem.
Critical weaknesses
The presentation would benefit from clearer explanations of key experimental choices in the main text. Difficulty is defined through preprocessing-solver backtrack counts, but the thresholds and training details are largely deferred to the appendix. Blue emphasis within the prose is visually distracting, although primarily a stylistic issue. Experiments cover only Sudoku, limiting evidence for broader applicability, and parameter-count comparisons require care because the harness performs substantial computation. The related work also omits "Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error (NeurIPS 2025)", which studies Transformer-based Sudoku solving with guessing and backtracking.
Questions for authors
-
Could you clarify the motivation for the solver-based difficulty thresholds in Appendix B.1 (easy: 1–9 backtracks; medium: 10–99; hard: 100–999)? How sensitive are the results to the preprocessing solver and these thresholds?
-
Appendix B.5 reports 1,000 training epochs on a fixed set of teacher traces with online symmetry augmentation. What evidence rules out memorization of this training pool, and are symmetry-equivalent puzzles excluded across training and evaluation? Have the authors considered comparing this setup with streaming training on freshly generated puzzles to assess generalization further?
-
How well does your approach generalize beyond Sudoku-Extreme? Could you evaluate the trained model on independently generated puzzles from SudokuPy and on David G. Radcliffe’s 3 Million Sudoku Puzzles with Ratings (2020)? Such experiments would help assess robustness across data sources and difficulty distributions.
-
Could you clarify the relationship between your approach, Shah et al., Causal Language Modeling Can Elicit Search and Reasoning Capabilities on Logic Puzzles (NeurIPS 2024), and the work of Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error (NeurIPS 2025)? A direct experimental comparison would help establish the advantages of your model and harness.
3 comments
Q2. Training-evaluation overlap
Appendix B.5 reports 1,000 training epochs on a fixed set of teacher traces with online symmetry augmentation. What evidence rules out memorization of this training pool, and are symmetry-equivalent puzzles excluded across training and evaluation? Have the authors considered comparing this setup with streaming training on freshly generated puzzles to assess generalization further?
Response.
Our overlap audit supports generalization beyond the fixed teacher traces. Across the paper’s 2,000 evaluation puzzles and 4,500 additional extreme puzzles, we found zero matches with the 5,000 training puzzles, including under all rotations, reflections, and digit relabelings used in training augmentation.
We also checked 10,566,302 intermediate states along teacher trajectories, up to 8,192 actions per puzzle. Comparing both the grid and candidate state against the entire 158,215-state teacher pool, including validation states, yielded zero exact or symmetry-equivalent matches. On these unmatched states, the model achieves 99.9992% agreement with the teacher’s action, requiring both cell and digit to match for forward actions and REVERT at dead ends. These decisions therefore occur on states that are neither training examples nor their augmented copies.
These findings complement the held-out solve rates, causal mechanism analyses, and memorization-to-generalization transition in Figure 3(b,c): fitting small training sets alone does not produce successful solving, whereas larger datasets yield reliable held-out performance.
We train on offline teacher traces from only 5,000 easy puzzles, with online symmetry augmentation, to test whether a small, fixed training pool suffices for generalization. Streaming fresh puzzles could provide broader coverage and less repetition, potentially making generalization easier. We therefore focus on demonstrating generalization from this limited, fixed pool and do not include streaming training in this study.
Q3. Generalization beyond Sudoku-Extreme
How well does your approach generalize beyond Sudoku-Extreme? Could you evaluate the trained model on independently generated puzzles from SudokuPy and on David G. Radcliffe’s 3 Million Sudoku Puzzles with Ratings (2020)? Such experiments would help assess robustness across data sources and difficulty distributions.
Response.
Our model learns a general, MRV-guided search procedure for Sudoku through interaction with the harness. The model selects cell–digit assignments or REVERT, while the harness updates the state and maintains the backtracking stack. This allows the same learned procedure to be applied across puzzle sources through a common state representation and evaluation protocol. We therefore evaluate the unchanged model and harness on independently sourced puzzles to test whether this procedure generalizes beyond the training distribution, without fine-tuning.
We evaluated the paper’s 1,000-epoch checkpoint on 100,000 independently generated SudokuPy puzzles, 100,000 puzzles uniformly sampled from Radcliffe’s collection, the 100,000-puzzle Kaggle-filtered test split, and the 18,000-puzzle RRN test set, using the same environment and unmasked greedy decoding.
Complete-puzzle solve rates (%) are:
| Method | Parameters | Random / SudokuPy | Kaggle-unfiltered | Kaggle-filtered | RRN |
|---|---|---|---|---|---|
| Shah et al. (2024), greedy | 42M | 67.16† | 67.16 | 87.18 | 94.76 |
| Giannoulis et al. (2025), DFS | 42M | 98.90 | 98.90 | 99.50 | 99.40 |
| Ours, greedy, 49,152 actions | 0.87M | 99.998 | 100.00 | 99.999 | 99.16 |
| Ours, greedy, 8,192 actions | 0.87M | 99.996 | 99.997 | 99.999 | 97.06 |
† Giannoulis et al. (2025) estimate Shah’s Random accuracy from its Kaggle-unfiltered performance. Prior-work values are published results; ours use the stated action budgets. We use the released Kaggle-filtered and RRN test sets, while SudokuPy and Kaggle-unfiltered are fresh samples. Parameter counts describe the learned models; our policy operates alongside the environment.
Across all 318,000 external puzzles, we found zero training-puzzle matches, including under the rotations, reflections, and digit relabelings used in training augmentation. Excluding puzzles solved by initial singleton fills, solve rates at 49,152 actions remain 99.998% on SudokuPy and 100% on the unfiltered Radcliffe sample.
Q4. Relationship to Shah et al. (2024) and Giannoulis et al. (2025)
Could you clarify the relationship between your approach, Shah et al., Causal Language Modeling Can Elicit Search and Reasoning Capabilities on Logic Puzzles (NeurIPS 2024), and the work of Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error (NeurIPS 2025)? A direct experimental comparison would help establish the advantages of your model and harness.
Response.
We agree that the relationship should be stated explicitly. The omission of Giannoulis et al. (2025) was an oversight, and we will add it to the related work. The key distinction across these studies is how search is represented and how computation is divided between the model and its environment.
Shah et al. (2024) train an autoregressive Transformer on solver-ordered, mistake-free solution sequences and probe its candidate representations. Giannoulis et al. (2025) extend transcript-based solving to guessing and backtracking, and further study efficient depth-1 guessing. Both use approximately 42M-parameter Transformers.
Our harness has two roles: executing state transitions and maintaining the information needed for backtracking. The one-layer, one-head, 0.87M-parameter policy selects each cell–digit assignment or REVERT. The harness performs candidate updates, singleton fills, and state restoration using its backtracking stack.
This separation mirrors how models and harnesses work together in practice. For example, in coding agents, the model chooses edits and tool calls, while the file system stores current files and Git maintains version history. Our setting makes this interaction explicit, allowing us to investigate how a small learned policy works with a stateful harness to carry out reliable search.
The benefit becomes important over long searches. A full transcript of explored branches can grow beyond a fixed context window. Our harness maintains the active backtracking stack, while the policy receives only the current grid and candidate state. This allows the same small model to make thousands of decisions without processing the entire trajectory and makes its decision mechanisms directly analyzable.
We train on only 5,000 easy puzzles, with trajectories capped at 200 forward actions and online symmetry augmentation. The resulting policy generalizes to much longer searches and, without fine-tuning, to the 318,000 external puzzles reported in Q3. These evaluations include the released Kaggle-filtered and RRN test sets, plus independently generated SudokuPy puzzles and a fresh Radcliffe sample.
The comparison in Q3 provides evidence about solving accuracy across these sources. Training data, inference procedures, and the allocation of computation differ across methods, so the parameter counts describe the learned components rather than a matched comparison of total computational cost. Our contribution is reliable generalization from short, easy traces together with an explicit, causally tested explanation of the learned search decisions.
We hope the additional results and manuscript revisions address your concerns, and we would appreciate your reconsideration of the rating in light of this new evidence.
We thank the reviewer for recognizing that our small model allows a detailed mechanistic analysis and for suggesting that we evaluate it on independently generated Sudoku puzzles. Please check the revised PDF.
W1. Critical weaknesses
Response.
Presentation and experimental choices. We now state the difficulty thresholds and key training settings explicitly in the main text and reduce the blue emphasis. Q1 explains the order-of-magnitude grouping and shows increasing search effort under both our teacher and tdoku.
Broader applicability. Sudoku allows us to study reliable composition over long searches while keeping the rules fixed. The additional 318,000-puzzle external evaluation establishes transfer across Sudoku sources (Q3). Extensions to other constraint satisfaction problems remain future work; our response to reviewer zfww’s Q1 describes the formulation and required adaptations.
Environment computation. We have measured the environment’s work and total solving time, including initialization and failed branches, as reported in our response to reviewer j3mn’s Q2. We will present these measurements alongside the parameter count, which describes the learned policy.
Related work. The omission of Giannoulis et al. (2025) was an oversight, and we have added it. Q4 explains the differences in search representation, model–environment interaction, and mechanistic analysis. The comparison in Q3 additionally places our external evaluation alongside the published results of Shah et al. and Giannoulis et al.
We have incorporated these clarifications and additional results into the revised manuscript, including the difficulty analysis, overlap checks, external evaluations, and comparison with Shah et al. and Giannoulis et al. We also clarify the respective roles of the model and harness.
Q1. Difficulty criterion
Response.
We define difficulty through preprocessing search effort: each failed candidate assignment counts as one backtrack. The thresholds—1–9, 10–99, 100–999, and at least 1,000—separate orders of magnitude of search cost. Reasoning length captures an important aspect of difficulty in sequential tasks, including multi-step mathematical reasoning and long-horizon agent tasks: longer solutions require reliable decisions over more steps. Our Sudoku setting studies this aspect while keeping the rules fixed. Appendix B.3 reports median teacher forward-decision counts of 7, 26, 231, and 791 across these bands.
The learning experiments provide complementary evidence. Under a fixed training budget, Figure 3(b,c) shows that the transition from memorization to generalization occurs at larger training-set sizes for hard and extreme puzzles.
To assess whether our difficulty grouping is meaningful under another solver, we compared the same evaluation puzzles using tdoku, a C++ Sudoku solver with stronger constraint propagation. Its backtrack-based ratings are provided with the source dataset. Median tdoku backtrack counts increase from 1 to 4, 28, and 34 across our easy, medium, hard, and extreme groups. This supports the overall increase in search difficulty under an independent grader.