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

Summary

This work attempts to solve a filtered list of Sudoku puzzles by training a transformer model with data derived from solutions produced by a mechanistic 'simple solver' (rather than a sophisticated recursive planner). They show that the training regime transformer model can be engineered to enable the model to learn to do the task effectively. In addition, the authors perform linear probes to show the extent of the model's internal representation of the ongoing problem solution.

Strengths

This work tackles a problem that is readily understood by the public, using transformers which might be expected to struggle (compared to GOFAI solvers, which work on even harder Sudoku puzzles than tested here). The number of experiments, looking at different aspects of the learnability of the task, and the probing of the resulting model internal states is very nicely done.

Weaknesses

Selecting only those solvable by a simple solver is quite a simplification : Puzzles that require a full-backtracking approach are excluded. This means that the results show that Transformers are capable of planning when the situation is simple, which is far from being fully capable of planning/reasoning. Should link to dataset (https://www.kaggle.com/datasets/radcliffe/3-million-sudoku-puzzles-with-ratings). According to the dataset description on Kaggle, 43% of the puzzles in the dataset have a difficulty of zero, meaning that it can be solved using a simple scanning technique. The filtered dataset is 1.9M of the original 3.0MM (63%), so only 31% of the dataset being used is not amenable to the 'simple scanning technique'. Perhaps this should be highlighted. Should mention the 42M param GPT-2 architecture earlier in the paper than Appendix B. Minor quibbles: * L32: "In this work, we aim to understand how complex a reasoning task can Transformers trained with next-token prediction solve by focusing on a synthetic task: Sudoku puzzles." + -> "In this work, we aim to understand how complex a reasoning task Transformers trained with next-token prediction can solve by focusing on a synthetic task: Sudoku puzzles." * L70: "This ensures that all our puzzles are solvable in polynomial time." Should be 'reasonable time' - the polynomial time claim is beyond what's proven.

Questions

Could an analysis of model performance vs the 'rating' of the puzzle hardness (which I believe exists in the dataset) be done? i.e. Does the model get more puzzles wrong, the objectively harder they get?

Rating

8

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

The filtering of the initial dataset should have been emphasised more : It may be that the model learns only puzzles that would be in an 'Easy Sudoku' collection.

Summary

This paper applies causal language models (Transformers) to solve Sudoku puzzles, reporting a 94.21% accuracy rate in solving the puzzles completely. The authors claim to demonstrate that these models can develop human-like reasoning capabilities by employing insights from CoT prompting through carefully structured training data and probing analyses. The contribution of the paper is: 1. Demonstration that causal language models can learn complex reasoning tasks like Sudoku solving through carefully structured training data. 2. Development of a novel training methodology that leverages solver-decomposed reasoning order to enhance model performance.

Strengths

Novel Methodology and Application: Applying Transformers to Sudoku Solving is an interesting extension of Transformers techniques, and the use of sequences mimicking human reasoning steps is a creative training method.

Weaknesses

1: Limited novelty: While applying Transformers to Sudoku is new, the underlying techniques are not innovative. The paper lacks significant theoretical or methodological advancements. 2: Narrow scope: Focusing solely on Sudoku limits the paper's impact and generalizability. It's unclear how well this approach would generalize to other reasoning tasks or more complex Sudoku variants. Testing models across various types of reasoning tasks, especially those requiring different logical structures or knowledge types (rule-based vs. rule-less puzzles), could significantly enhance the understanding of the model's generalization capabilities. [1] 3: Inadequate comparisons: A major oversight is the lack of comparisons to traditional Sudoku-solving algorithms or other AI approaches. It's necessary to compare neural approaches with traditional algorithms to assess advancements meaningfully [1] 4: Overstated claims: The paper may overstate the model's "reasoning" capabilities. It's not yet convincing that what's described could be pattern matching rather than actual reasoning. Distinguishing between genuine reasoning and sophisticated pattern matching can be challenging. Further evidence could be demonstrated by testing the model's ability to solve puzzles it was not directly trained on, or by altering puzzle formats to see if the model can adapt its solving strategy without retraining. 5: Computational efficiency: There's insufficient discussion of the computational costs involved comparing the different order/decomposing as well as beam search appraoches. 6: Lack of error analysis: A detailed examination of where and why the model fails would provide more insight than focusing on its successes. [1] Giadikiaroglou, P., Lymperaiou, M., Filandrianos, G., & Stamou, G. (2024). Puzzle Solving using Reasoning of Large Language Models: A Survey.

Questions

1. How does this approach compare speed and efficiency to traditional Sudoku-solving algorithms? 2. What evidence supports the claim that the model is genuinely "reasoning" rather than pattern matching? 3. How well does this method generalize to other types of puzzles or reasoning tasks? 4. What are the computational efficiency for different tested methods presented? 5. Can you provide a more detailed error analysis? what are standard failure modes? 6. Have you investigated whether the model can explain its reasoning process, similar to how humans might describe their Sudoku-solving steps？

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

Yes

Summary

* This work presents a study of solving sudoku puzzles via causal language modeling. * Given the sequence of filled places and their values in sudoku, the model must output the series of empty cell positions and the values that correspond to them. * They study how the model performs with various input representations of a sudoku puzzle. (considering sudoku puzzle as a matrix) * Fixed cell order (from top-left to bottom-right) * Random cell order * Chain-of-thought prompting (using a solver to provide the method to solve the sudoku) * Through experiments, the authors have demonstrated that appropriate training data that breaks down the problem into smaller components is essential for the model to solve the puzzle correctly. * The model's performance improved with CoT prompting. It's even enhanced with the use of position hints and beam search.

Strengths

* The problem definition, model description, and experimental setup are presented clearly, making the paper accessible and informative. * Introduced a sudoku puzzle dataset with steps to solve the puzzles (1.9M puzzles). * Probing analysis for tracking the candidate set of cell,

Weaknesses

1. No SoTA models are evaluated on the sudoku puzzle data. 2. A full ablation analysis is not included. This is to understand better how different settings (CoT, beam search, puzzle complexities) affected the model performance and where the model is struggling. Only improvements in accuracies are mentioned in the paper.

Questions

1. How do models like GPT-4, Gemini-1.5, and Llama-3 perform on these sudoku puzzles? (with and without CoT) 2. Are the plots in Figure 3 in the CoT+Beam search setting?

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

NA

Summary

This paper assesses causal language models', particularly transformer decoders', abilities to solve Sudoku puzzles. The authors encode Sudoku puzzles into sequences, representing each cell as a (row, column, value) triple, and train a model from scratch on 1.8M puzzles. They then evaluate the trained model on a 0.1M holdout test set. Results indicate that when unfilled cells in the training data are arranged in an easy-to-hard order (based on a solver's results), the model can solve Sudoku puzzles with a 94.21% full-puzzle solving rate. The authors also use linear probing to show that the model's activations contain information about possible values for any given cell. The paper concludes that causal language models may exhibit complex reasoning capabilities when trained on data that informs appropriate reasoning steps, without requiring techniques like Chain-of-Thought or external reasoning engines.

Strengths

- The selected task and settings are suitable for studying the reasoning and planning capabilities of language models; - The paper presents strong results that causal LMs can solve the Sudoku puzzle by training with appropriate data, without the need of techniques such as using CoT, search or external solvers. - The results indicate that causal LMs may be able to perform search and planning internally, which seems novel and insightful for further research. - The writing is easy to follow.

Weaknesses

- The probing study's methodology is somewhat questionable. It merely compares the top-k predictions for each cell against the ground truth candidate set. This approach may not accurately be termed "probing" as it doesn't examine intermediate representations. Furthermore, this study might not conclusively demonstrate that the language model internally tracks candidate sets, given that the model is explicitly prompted to predict the cell. A more effective approach could involve probing potential values of one cell while prompting the model to predict another. Positive results from such a method could more convincingly show that the model can internally reason about other cells relevant to solving the current one. - I’m not sure about what the takeaway of Sec. 3.5 is. - It seems like the paper used the wrong template.

Questions

- Showing some example data in the appendix can be helpful. - When trained with random order data, do you include tokens for cell locations for the loss calculations? Additionally, how do you ensure that the model predicts every cell during testing? - I assume the input context always includes previously predicted cells and values, is this correct?

Rating

7

Confidence

3

Soundness

2

Presentation

2

Contribution

3

Limitations

The authors have properly adequately limitations of their work in the paper.

response to the rebuttal

Thanks for the detailed response especially on the error analysis and the additional study on the zebra puzzle; I still hope to see more experimental results on comparison with other solvers and models to justify its effetiveness, but I am willing to increase my rating for the current draft.