Source-linked AI summary
Causal Language Modeling Can Elicit Search and Reasoning Capabilities on Logic Puzzles
Kulin Shah, Nishanth Dikkala, Xin Wang, Rina Panigrahy
TL;DR
The paper asks whether causal language modeling can produce genuine search and reasoning capabilities rather than brittle approximations. It trains Transformers on solver-decomposed Sudoku and Zebra solutions, finding strong puzzle-solving performance and internally decodable candidate-set information.
Problem
The paper investigates whether Transformers trained with next-token prediction can learn complex search and reasoning, amid debate over whether language-model reasoning is genuine or brittle.
Method
The authors train Transformers on synthetic Sudoku and Zebra puzzles using solver-generated, logically ordered solution sequences and analyze their internal representations.
Results
The model solves 94.21% of Sudoku puzzles fully correctly with beam search, while probing decodes candidate sets from its activations.
Takeaways & Limitations
Causal language modeling can learn non-trivial search and reasoning when training data provides an appropriate decomposition of the reasoning steps.
Takeaways & Limitations
The study uses synthetic toy tasks, Sudoku lacks some long-term planning demands, and the puzzles do not require inventing new strategies.
Abstract
from arXiv · showhide
Causal language modeling using the Transformer architecture has yielded remarkable capabilities in Large Language Models (LLMs) over the last few years. However, the extent to which fundamental search and reasoning capabilities emerged within LLMs remains a topic of ongoing debate. In this work, we study if causal language modeling can learn a complex task such as solving Sudoku puzzles. To solve a Sudoku, the model is first required to search over all empty cells of the puzzle to decide on a cell to fill and then apply an appropriate strategy to fill the decided cell. Sometimes, the application of a strategy only results in thinning down the possible values in a cell rather than concluding the exact value of the cell. In such cases, multiple strategies are applied one after the other to fill a single cell. We observe that Transformer models trained on this synthetic task can indeed learn to solve Sudokus (our model solves $94.21\%$ of the puzzles fully correctly) when trained on a logical sequence of steps taken by a solver. We find that training Transformers with the logical sequence of steps is necessary and without such training, they fail to learn Sudoku. We also extend our analysis to Zebra puzzles (known as Einstein puzzles) and show that the model solves $92.04 \%$ of the puzzles fully correctly. In addition, we study the internal representations of the trained Transformer and find that through linear probing, we can decode information about the set of possible values in any given cell from them, pointing to the presence of a strong reasoning engine implicit in the Transformer weights.
1 Introduction
The paper tests whether Transformers trained by causal language modeling can perform search and reasoning on synthetic Sudoku and Zebra puzzles. It finds that solver-decomposed training data is crucial, enabling strong puzzle-solving performance and representations that encode candidate values.
- 1 Introduction: The task addresses whether apparent language-model reasoning reflects genuine reasoning or brittle processes such as approximate retrieval.Sudoku is a challenging constraint-satisfaction problem, while Zebra puzzles provide a verbal logic-puzzle setting with richer constraints.
- 1.2 Our Results: Solver-decomposed reasoning order substantially strengthens Sudoku learning by presenting adaptive sequences of cells generated from iterative solver steps.Training from scratch on solver order produced 87.18% full-puzzle accuracy before the stronger decoding variants.
- 1.2 Our Results: 94.21% of Sudoku puzzles were solved fully correctly with solver-decomposed training and beam search, while position hints reached 99.02% cell accuracy.The authors identify cell-position search as harder than computing a value once the position is supplied.
- 1.2 Our Results: A probing analysis finds that the model’s activations implicitly encode candidate sets of possible values, matching the solver’s candidate set.This supports the presence of abstract reasoning information in the trained model’s internal representations.
- 1.2 Our Results: Causal language modeling can learn search and reasoning on non-trivial Sudoku and Zebra logic puzzles when training data decomposes problems into smaller constituents.The authors argue that complete search traces are unnecessary when the training data provides an appropriate high-level breakdown.
2 Preliminaries and setup
The paper formulates Sudoku and Zebra puzzles as sequence-to-sequence tasks and constructs solver-generated datasets for Transformer training and evaluation. Sudoku solving is restricted to puzzles handled by seven efficient strategies, including strategies that eliminate candidates rather than immediately filling cells.
- Solver and scope: Sudoku instances are restricted to puzzles solvable by seven well-known efficient strategies, including multi-cell methods such as XY-Wing and Unique Rectangle.Only two of the seven strategies directly fill a cell; the others narrow candidate sets.
- Data and representation: The Sudoku dataset contains 1.8M training puzzles and 0.1M test puzzles, with each cell represented by row, column, and value tokens.Puzzle difficulty is separately rated using a backtracking solver's maximum guess-stack depth.
- Data and representation: The Zebra dataset contains 0.3M training puzzles and 15k test puzzles generated by adding clues until an iterative solver can solve each puzzle.The generated puzzles vary in size and use seven clue types.
- Model and evaluation: The experiments use an 8-layer causal GPT-2-style Transformer with 42M parameters and evaluate cell accuracy alongside complete puzzle accuracy.A puzzle with one incorrect cell counts as incorrect under complete puzzle accuracy.
3 Experiments on Sudoku puzzles
Sudoku performance depends strongly on exposing the model to solver-decomposed cell orders during training rather than fixed or random orders. The results indicate that selecting an easy cell is harder than applying the value-filling strategy once that position is supplied, while beam search further improves decoding.
- 3.1 Training using fixed or random order: Fixed-order training reaches 58.64% cell accuracy and 7.2% complete puzzle accuracy, while random-order training reaches about 52% and 1%, respectively.These orders do not reliably select cells that are easiest at the current puzzle state.
- 3.2 Solver-decomposed reasoning order: Solver-decomposed reasoning order applies easier strategies first, scans cells for progress, and records adaptive cell sequences for training.Progress includes eliminating candidates, not only filling a final value.
- 3.3 Hinted cell accuracy: Position hints alone provide limited gains for a random-order model, reaching 54.57% hinted cell accuracy, because the model still must learn the relevant strategies.The authors attribute the limitation to factors including scarce easy-strategy examples and finite model capacity.
- 3.4 Using solver for CoT training: 87.18% complete puzzle accuracy and 94.23% cell accuracy are achieved with solver-decomposed reasoning-order training, versus about 8% and 1% complete accuracy for fixed and random orders.The decomposed order improves cell accuracy by around 36% over fixed order and 43% over random order.
- 3.4 Using solver for CoT training: 99.02% hinted cell accuracy shows that supplying solver-selected positions largely closes the gap from 94.23% cell accuracy, implicating cell search as the harder component.The task separates choosing an easy-to-decode cell from computing its value once the position is known.
- 3.5 Beam-search decoding: Beam search improves cell accuracy by around 2% and complete puzzle accuracy by around 4% at width k=3, with similar gains from increasing width to k=5.At k=5, cell accuracy largely bridges the gap to hinted accuracy without requiring position hints.
4 Analysis
The analysis finds that solver-decomposed training yields strong Sudoku performance, with errors driven mainly by selecting which cell to decode rather than valuing the selected cell. The model also encodes solver-like candidate sets in its logits.
- 4.2 Performance analysis of the model using the difficulty of the puzzles: Complete-puzzle accuracy is nearly perfect for low-difficulty Sudokus but falls as difficulty increases, while beam search helps more on harder puzzles.Even at difficulty ratings of 3 to 3.5, the model solves around 50% of puzzles completely; the rating is based on average solver guesses.
- 4.3 Failure in search for easy-to-decode cells: 94.23% cell accuracy is achieved by the solver-decomposed model, while hinted-cell accuracy reaches 99.02%, indicating that search for easy-to-decode cells is the main gap.The model finds the correct value more reliably when easy-to-decode cells are identified during inference.
- 4.3 Failure in search for easy-to-decode cells: The model’s search failures occur when it fills a harder-to-decode cell despite another cell being easier to fill.The failure examples support the hinted-cell analysis by showing incorrect cell selection as a concrete error mode.
- 4.3 Failure in search for easy-to-decode cells: Block-based easy-to-decode cells are missed more often, possibly because the input explicitly represents rows and columns but not block numbers.Providing a block number is proposed as a future extension.
- 4.4 Emergence of candidate set information in the model: Candidate-set overlap between the solver and model exceeds 93% across positions, rising to about 96.5% with 60 filled cells and about 98.5% with 70.This is obtained directly from model logits for all empty cells, without training a probe or directly supervising candidate sets.
5 Experiments on Zebra puzzle
Zebra-puzzle experiments compare fixed, random, and solver-decomposed solution orders. Solver-decomposed training performs best, and beam search provides an additional improvement.
- Order of the solution: Training uses unchanged clues while varying whether the solution is presented in fixed, random, or solver-decomposed reasoning order.The solver-decomposed order follows values that are easier to determine from the clues before less readily determined values.
- Order of the solution: Solver-decomposed training reaches 95.63% cell accuracy and 91.17% complete-puzzle accuracy, versus nearly zero complete-puzzle accuracy for random order and 79.36% for fixed order.The evaluation uses 1,000 puzzles; the authors attribute fixed-order performance partly to many smaller, easier puzzles in the evaluation set.
- Order of the solution: Beam search with width 3 improves Zebra-puzzle performance by 0.7%.
6 Conclusion
The paper concludes that causal next-token prediction can learn Sudoku and Zebra solving when training data provides a high-level decomposition of reasoning steps. It also emphasizes that the evidence comes from synthetic, constrained tasks and does not establish performance on more abstract reasoning.
- 6 Conclusion: Next-token prediction with high-level reasoning-step decomposition learns to solve complex Sudoku and Zebra logic puzzles.The authors suggest this may indicate reasoning capacity in pretrained models when training data contains sufficiently detailed decompositions.
- 6 Conclusion: The study is limited to synthetic toy tasks, and Sudoku requires less long-term planning than problems requiring backtracking.
- 6 Conclusion: The experiments do not test creative strategy invention or non-logic-puzzle reasoning tasks such as probabilistic or rule-less puzzles.
A Details about our list of strategies
The study uses seven strategies for both Sudoku and Zebra puzzles.
- A Details about our list of strategies: Both Sudoku and Zebra experiments use seven solver strategies.
A.1 Strategies for Sudoku puzzles
The Sudoku solver uses seven strategies, ranging from single-candidate placements to multi-cell deduction and candidate-elimination techniques.
- Seven strategies are listed for solving Sudoku puzzles, covering direct placements, candidate elimination, and multi-step deductions.The strategies are lone single, hidden single, naked pair, naked triplet, locked candidate, XY wing, and unique rectangle.
- Lone single fills a cell with only one possible candidate, while hidden single places a number in its only possible cell within a row, column, or box.
- Naked pairs and triplets eliminate candidate values when two or three cells share exactly the same admissible numbers.
- Locked candidates eliminate possibilities when all positions for a number within a box lie on the same row or column.
- XY wing and unique rectangle apply multi-cell deductions to eliminate admissible values from other cells.XY wing uses a pivot and two wing cells, while unique rectangle uses four cells arranged in a rectangle.
A.2 Relationtypes for Zebra puzzles
The Zebra-puzzle representation uses seven relation types to encode equality, exclusions, adjacency, ordering, and positional constraints among entities and attributes.
- Seven relation types describe Zebra-puzzle constraints: equality, inequality, immediate left, neighboring, endpoint, left-of, and in-between.
- Equality and inequality clues assign an attribute value or exclude a particular value.Examples specify that the Norwegian lives in the first house or that the Englishman does not live there.
- Immediate-left and neighbor relations encode adjacency, with neighbor generalizing immediate left to either adjacent side.
- Ends-in, left-of, and in-between relations encode endpoint placement and relative ordering among entities or attribute values.Left-of does not require immediate adjacency, whereas in-between relates three entities.
B Details about hyperparameters of training
The experiments train on 1.8M Sudoku puzzles after filtering a 1.9M-puzzle dataset, using AdamW for 4M steps with a fixed optimization schedule.
- 1.8M puzzles form the training set, while 0.1M puzzles are held out for validation from 1.9M puzzles solvable by the seven listed strategies.The dataset originates from, and filtering adapts a solver from.
- Models use AdamW with a 1×10^-4 learning rate, batch size 64, and 4M training steps.
- A cosine learning-rate schedule uses 4000 warmup tokens and an end learning-rate factor of 0.2.
C Mistake position frequency experiment.
Mistakes tend to begin early in Sudoku-solving sequences but accumulate later, consistent with invalid prefixes propagating subsequent errors.
- First mistakes are more frequent early, when puzzles contain more empty cells, whereas the overall mistake distribution shifts toward later cells.
- Once a model makes a mistake, it is likely to continue making mistakes because the sequence prefix has become invalid.
- The examples show failures in selecting an easy-to-decode cell even when the selected cell’s value is comparatively straightforward to determine.
E An example of candidate set for the puzzle
Generalized Sudoku uses an n × n board divided into n √n × √n boxes, with the objective of filling every row, column, and box with numbers 1 through n without duplicates.
- A generalized Sudoku board has size n × n and is divided into n boxes of size √n × √n.
- The completed board must contain the full set of numbers from 1 to n in every row, column, and √n × √n box.
- The experiments use a 9 × 9 Sudoku board divided into nine 3 × 3 boxes.
E.2 Candidate set example
Candidate sets record the possible values for each Sudoku cell and support deduction or narrowing of possibilities, illustrated by an example puzzle.
- A candidate set for position (r, c) contains all values that the cell can take.
- Candidate sets support either deducing a value for a cell or narrowing the possibilities at an empty cell.
- Figure 9 presents an example of the candidate set for a puzzle.