Can a One-Layer Transformer Solve Hard Sudoku? Test-Time Compute, Generalization, and Mechanistic Analysis

Modern AI agents pair a language model with a harness that executes actions, maintains state, and returns feedback. We study where the boundary between the two lies in its simplest form: a one-layer, one-head Transformer paired with a simple harness, on Sudoku. At each step, the Transformer observes the grid and the candidates of every cell and selects either a cell–digit placement or $\mathtt{REVERT}$; the harness applies the action, propagates constraints, and keeps the search history needed to backtrack. We train the Transformer by imitating a minimum-remaining-values (MRV) solver on easy puzzles only. We show that the Transformer generalizes from easy to hard puzzles: applied repeatedly, it solves all held-out easy, medium, and hard puzzles and $99.8\%$ of extreme puzzles, whose searches run to thousands of actions, and harder puzzles need only more test-time compute. Thanks to its simple structure, we can trace how the model computes each action: attention selects the cell with the fewest candidates, the MLP favors the teacher's digit at that cell, and a dead-end cell shifts the output to $\mathtt{REVERT}$. With only $0.87$M parameters, the Transformer solves hard Sudoku almost perfectly, while prior single-model solvers use $7$M to $27$M parameters.