# Causal Language Modeling Can Elicit Search and Reasoning Capabilities on Logic Puzzles

arXiv: https://arxiv.org/abs/2409.10502 · HTML: https://mlsanity.com/paper/2409.10502/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 31 of its 56 references that are in the map.
- First posted on arXiv 16 Sep 2024.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 30 of 31)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Inner Monologue: Embodied Reasoning through Planning with Language Models](https://mlsanity.com/paper/2207.05608/) (2022)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Gemini: A Family of Highly Capable Multimodal Models](https://mlsanity.com/paper/2312.11805/) (2023)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [The Linear Representation Hypothesis and the Geometry of Large Language Models](https://mlsanity.com/paper/2311.03658/) (2023)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [Emergent Linear Representations in World Models of Self-Supervised Sequence Models](https://mlsanity.com/paper/2309.00941/) (2023)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Large Language Model Guided Tree-of-Thought](https://mlsanity.com/paper/2305.08291/) (2023)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023)
- [Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process](https://mlsanity.com/paper/2407.20311/) (2024)
- [Beyond A*: Better Planning with Transformers via Search Dynamics Bootstrapping](https://mlsanity.com/paper/2402.14083/) (2024)
- [Physics of Language Models: Part 1, Learning Hierarchical Language Structures](https://mlsanity.com/paper/2305.13673/) (2023)
- [On the Origins of Linear Representations in Large Language Models](https://mlsanity.com/paper/2403.03867/) (2024)
- [Amortized Planning with Large-Scale Transformers: A Case Study on Chess](https://mlsanity.com/paper/2402.04494/) (2024)
- [Puzzle Solving using Reasoning of Large Language Models: A Survey](https://mlsanity.com/paper/2402.11291/) (2024)
- [Improving Length-Generalization in Transformers via Task Hinting](https://mlsanity.com/paper/2310.00726/) (2023)

## Built on by (most cited first, 30 of 38)

- [Gemma 3 Technical Report](https://mlsanity.com/paper/2503.19786/) (2025)
- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [BIG-Bench Extra Hard](https://mlsanity.com/paper/2502.19187/) (2025)
- [Inverse Scaling in Test-Time Compute](https://mlsanity.com/paper/2507.14417/) (2025)
- [To Backtrack or Not to Backtrack: When Sequential Search Limits Model Reasoning](https://mlsanity.com/paper/2504.07052/) (2025)
- [Sudoku-Bench: Evaluating creative reasoning with Sudoku variants](https://mlsanity.com/paper/2505.16135/) (2025)
- [Improving Discrete Diffusion Unmasking Policies Beyond Explicit Reference Policies](https://mlsanity.com/paper/2510.05725/) (2025)
- [Transformers Struggle to Learn to Search](https://mlsanity.com/paper/2412.04703/) (2024)
- [Chasing Progress, Not Perfection: Revisiting Strategies for End-to-End LLM Plan Generation](https://mlsanity.com/paper/2412.10675/) (2024)
- [Insertion Language Models: Sequence Generation with Arbitrary-Position Insertions](https://mlsanity.com/paper/2505.05755/) (2025)
- [Stop Training for the Worst: Progressive Unmasking Accelerates Masked Diffusion Training](https://mlsanity.com/paper/2602.10314/) (2026)
- [Reasoning with Latent Tokens in Diffusion Language Models](https://mlsanity.com/paper/2602.03769/) (2026)
- [Scalable Autoregressive 3D Molecule Generation](https://mlsanity.com/paper/2505.13791/) (2025)
- [Flow Reasoning Models: Turning Flows Into Efficient Recurrent Reasoners](https://mlsanity.com/paper/2606.29150/) (2026)
- [Variational Masked Diffusion Models](https://mlsanity.com/paper/2510.23606/) (2025)
- [Are Language Models Efficient Reasoners? A Perspective from Logic Programming](https://mlsanity.com/paper/2510.25626/) (2025)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error](https://mlsanity.com/paper/2509.22023/) (2025)
- [When Does Intrinsic Self-Correction Help? A Task-Sensitive Analysis](https://mlsanity.com/paper/2606.23196/) (2026)
- [LogiPlan: A Structured Benchmark for Logical Planning and Relational Reasoning in LLMs](https://mlsanity.com/paper/2506.10527/) (2025)
- [Recursive Scaling in Masked Diffusion Models](https://mlsanity.com/paper/2606.18022/) (2026)
- [Sticky Jump Diffusions: A Unifying View of Masked, Continuous, and Hybrid Diffusion](https://mlsanity.com/paper/2607.10951/) (2026)
- [Leveraging Pretrained Language Models as Energy Functions for Glauber Dynamics Text Diffusion](https://mlsanity.com/paper/2605.04291/) (2026)
- [The Confidence Shortcut: A Reasoning Failure Mode of Masked Diffusion Models](https://mlsanity.com/paper/2605.29123/) (2026)
- [Understanding Parallel Samplers in Masked Diffusion via Random Walks on Graphs](https://mlsanity.com/paper/2606.22976/) (2026)
- [Scheduling Thoughts: Learning the Order of Thought in Diffusion Language Models](https://mlsanity.com/paper/2606.23567/) (2026)
- [Formalizing Latent Thoughts: Four Axioms of Thought Representation in LLMs](https://mlsanity.com/paper/2606.27378/) (2026)
- [Token Time Continuous Diffusion for Language Modeling](https://mlsanity.com/paper/2607.14106/) (2026)
- [From Interface to Inference: Eliciting Any-Order Inference from Any-Order Models](https://mlsanity.com/paper/2607.26504/) (2026)
- [Learning Model Successors](https://mlsanity.com/paper/2502.00197/) (2025)

## Abstract (arXiv)

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.