Abstract
Causal language modeling using the Transformer architecture has yieldedremarkable capabilities in Large Language Models (LLMs) over the last fewyears. However, the extent to which fundamental search and reasoningcapabilities emerged within LLMs remains a topic of ongoing debate. In thiswork, we study if causal language modeling can learn a complex task such assolving Sudoku puzzles. To solve a Sudoku, the model is first required tosearch over all empty cells of the puzzle to decide on a cell to fill and thenapply an appropriate strategy to fill the decided cell. Sometimes, theapplication of a strategy only results in thinning down the possible values ina 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. Weobserve that Transformer models trained on this synthetic task can indeed learnto 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 thattraining Transformers with the logical sequence of steps is necessary andwithout such training, they fail to learn Sudoku. We also extend our analysisto Zebra puzzles (known as Einstein puzzles) and show that the model solves$92.04 \%$ of the puzzles fully correctly. In addition, we study the internalrepresentations of the trained Transformer and find that through linearprobing, we can decode information about the set of possible values in anygiven cell from them, pointing to the presence of a strong reasoning engineimplicit in the Transformer weights.