Research map / Large language models / Agents, code and math
Causal language modeling can elicit search and reasoning capabilities on logic puzzles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Trains a 42M GPT-2-style causal Transformer on Sudoku and Zebra puzzles using solver-generated decomposed reasoning orders, reaching 94.21% full-puzzle Sudoku accuracy with beam search and showing candidate sets are linearly/logit-decodable.
Problem
Whether causal language modeling Transformers trained from scratch can learn search and reasoning on logic puzzles such as Sudoku and Zebra puzzles, which frontier LLMs fail at.
Approach
Train next-token-prediction Transformers on cell-fill sequences ordered by a human-like strategy solver (decomposed reasoning order) instead of fixed or random orders, so the model learns both where to search and which value to fill; beam search and candidate-set probing then reveal the learned reasoning.
Key results
- Solver-decomposed order training with beam width 5 reaches 94.21% complete Sudoku puzzle accuracy, versus ~7.2% for fixed order and ~1% for random order.
- Hinted cell accuracy reaches 99.02%, suggesting the remaining gap is mainly in searching for easy-to-decode cells.
- Zebra puzzles reach 92.04% complete puzzle accuracy with beam width 5, while GPT-4o and Gemini-1.5 Pro solve 0% of Sudoku puzzles in a 4-shot CoT setup.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train using solver-decomposed reasoning order instead of fixed cell order (ablation) | GPT-2 Sudoku solver · Sudoku test set | complete puzzle accuracy: around 8% to 87.18% | Helped |
| Train using solver-decomposed reasoning order instead of random cell order (ablation) | GPT-2 Sudoku solver · Sudoku test set | complete puzzle accuracy: around 1% to 87.18% | Helped |
| Use beam search with width 3 instead of greedy decoding (ablation) | Solver-order GPT-2 Sudoku solver · Sudoku test set | complete puzzle accuracy: 87.18 % -> 91.36 % | Helped |
| Increase beam width from 3 to 5 (ablation) | Solver-order GPT-2 Sudoku solver · Sudoku test set | complete puzzle accuracy: 91.36 % -> 94.21 % | Helped |
| Provide solver-selected position hints during inference (ablation) | Random-order GPT-2 Sudoku solver · Sudoku test set | cell accuracy: around 3 % | Helped |
| Provide solver-selected position hints during inference (ablation) | Solver-order GPT-2 Sudoku solver · Sudoku test set | cell accuracy: 94.23 % -> 99.02 % | Helped |
| Use fixed cell order rather than solver-decomposed reasoning order (ablation) | GPT-2 Sudoku solver · Sudoku test set | cell accuracy: 94.23 % -> 58.64% | Hurt |
| Use random cell order rather than solver-decomposed reasoning order (ablation) | GPT-2 Sudoku solver · Sudoku test set | complete puzzle accuracy: 87.18% -> 1% | Hurt |
| Use beam search with width 3 instead of greedy decoding (ablation) | Solver-order GPT-2 Zebra solver · Zebra puzzle evaluation set | eval complete puzzle accuracy: 91.17 % -> 91.83 % | Helped |
| Increase beam width from 3 to 5 (ablation) | Solver-order GPT-2 Zebra solver · Zebra puzzle evaluation set | eval complete puzzle accuracy: 91.83 % -> 92.04 % | Helped |
| Train using solver-decomposed reasoning order instead of fixed solution order (ablation) | GPT-2 Zebra solver · Zebra puzzle evaluation set | eval complete puzzle accuracy: 79.36 % -> 91.17 % | Helped |
| Increase beam width from 1 to 5 (ablation) | Solver-order GPT-2 Sudoku solver · Sudoku RRN evaluation set | eval complete puzzle accuracy: 94.76 % -> 95.43 % | Helped |
Surprising findings
- Frontier LLMs (GPT-4o, Gemini-1.5 Pro) solved 0% of Sudoku puzzles in 4-shot CoT prompting, near-random per-cell accuracy.
- Candidate sets of the solver can be read directly from model logits with 93-99% overlap, without training a probe.
Limitations
- Synthetic toy setting; real-world reasoning tasks are more abstract and challenging.
- Sudoku does not require backtracking or long-term planning, and no novel strategies must be invented at test time.
- Model misses easy-to-decode cells determined by block constraints, since block number is not an explicit input.
Experimental setup
Datasets: Sudoku dataset (Kaggle, difficulty-rated) Zebra puzzles generated by authors RRN Sudoku test set (18k puzzles)
Benchmarks: Sudoku validation set (0.1M) RRN Sudoku evaluation set (18k) Zebra puzzle eval set (15k)
Metrics: cell accuracy complete puzzle accuracy hinted cell accuracy candidate set equivalence accuracy
Baselines: GPT-4o Gemini-1.5 Pro Recurrent Relational Network fixed-order training random-order training
Builds on: GPT-2 Chain-of-Thought prompting Recurrent Relational Network
Closest papers by meaning
- Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error (NeurIPS 2025 · similarity 0.91)
- Enigmata: Scaling Logical Reasoning in Large Language Models with Synthetic Verifiable Puzzles (NeurIPS 2025 · similarity 0.88)
- HardcoreLogic: Challenging Large Reasoning Models with Long-tail Logic Puzzle Games (ICLR 2026 · similarity 0.88)
- Arithmetic Without Algorithms: Language Models Solve Math with a Bag of Heuristics (ICLR 2025 · similarity 0.87)
- Selection, Reflection and Self-Refinement: Revisit Reasoning Tasks via a Causal Lens (ICLR 2026 · similarity 0.87)
- Constraints-Guided Diffusion Reasoner for Neuro-Symbolic Learning (AAAI 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.