Causal language modeling can elicit search and reasoning capabilities on logic puzzles
Authors: Kulin Shah
Nishanth Dikkala
Xin Wang
Rina Panigrahy
Venue: NeurIPS 2024 poster (2024)
Keywords: reasoning
search
planning
sudoku
world model
transformers
Primary area: generative_models

Abstract: 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.

Causal language modeling can elicit search and reasoning capabilities on logic puzzles
Kulin Shah UT Austin kul kulinshahoutexas.o
Nishanth Dikkala
Google Research
iishanthd@goggle.comm com
Xin Wang Google Research wanxin8google. com com
Rina Panigrahy
Google Research rinapggoogle. com
Abstract
Causal language modeling using the Transformer architecture has yielded remark- able capabilities in Large Language Models (LLMMs) over the last few years. How- ever, 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 Sudoku, the model is first required 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 strategy only results thinning down the possible values in cell rather than concluding the exact value of the cell. such cases, multiple strategies are applied one after the other to a single cell. We observe that Transformer models trained on this synthetic task can indeed learn to solve Sudokus (our model solves 94.21% the puzzles fully correctly) when trained 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% the puzzles fully correctly. In addition, Transformer and find that through linear probing, we can decode information about the of possible values in any given cell from them, pointing the presence of strong reasoning engine implicit the Transformer weights
study the internal representations of the trained
Introduction
Language models using the Transformer architecture [VSP+17 17] have displayed remarkable abilities on variety of Machine Learning tasks over the last few years [BMR+22 20, RWC+ 19]. Trained with simply the task of predicting the next token on huge amounts of text, these models display highly performant and deep language understanding skills. In order make progress achieving human-like artificial intelligence, one of the most important ability is the ability to perform human- like reasoning and planning. Although LLMs have displayed seemingly remarkable ability to excel at reasoning and planning tasks as well, it is a ongoing debate as to whether this ability comes from true understanding and reasoning the underlying problem or some other process which simulates reasoning but can be highly brittle. For instance, although LLMSs show remarkable
Work done during internship Google Research. 2The code is available at https://githhn com kul www.llinnhhhiineee www.ahhhwneee...-.ooooooiininnni logic- pozie-uzzees
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Model
Percent of puzzles solved fully Percent of cells answered correctly
GPT-40
0%
9.5%
Gemini- Pro
0%
10.2%
Table I: Results of 4-shot with CoT prompting Sudoku solving by two of the frontier LLM models.
They solved 0 % of the puzzles completely right and their accuracy on a per cell basis was around 9-10% (close random guessing).
performance on benchmarks requiring non-trivial reasoning and planning skills such MATH [HBK+21], HumanEval [CT]+21] and others, there is research showing that these abilities can be extremely brittle or worse, the model is simply performing "approximate retrieval' [VOSK22, 24..
In this work, we aim to understand how complex a reasoning task can Transformers trained with next-token prediction solve by focusing on a set of synthetic tasks: logic puzzles. In this work we focus our analysis on two types of logic puzzles: Sudoku puzzles and Zebra puzzles.
Sudoku. In the classic variant of Sudoku, we are given a x 9 grid where each cell is to be occupied by number in the range along each row and column should be unique. In addition, the numbers within each 3 x mini-grid should also be unique. Given set of initially filled positions, the goal is to figure out the values that can occur in the unfilled cells. In standard Sudoku puzzles, there will always only exist unique solution to the puzzle.
9). The constraints are that the numbers
Zebra Puzzles. There are more verbal style of puzzle (Figure 3) where we need fill in values in a grid again but this time the type of possible constraints is much richer. These are also known as Einstein riddles.
Focusing on synthetic tasks like this gives a precise handle on what data the model has seen, and allows us to also control the difficulty of reasoning required for the task, see e.g. [LHB+23 AZL23, LSL+23, LAG 12]. Prior works have studied how causal language modeling with Transformers performs on synthetic tasks such as learning how to make valid moves in Othello, learning context-free free grammars, learning deterministic finite automata and learning specific algorithmic tasks [LAG 22, LHB NLW23, AZL23, YXLAZ24a, YXLAZ24b] (See Appendix B for a detailed discussion on related work). Compared to these, Sudoku puzzles present more challenging task. The Sudoku environment is highly challenging Constraint Satisfaction Problem (CSP) and determining the value in even a single cell can require highly complex reasoning involving multiple steps. In general the extension of the puzzle to n ni grids is known to be NP-complete [YS03]. Same is the case for Zebra puzzles. However, we will consider a class of logic puzzles which can be solved in polynomial time. This class still remains non-trivial to learn. For an idea of how challenging these can be, we performed a small experiment on how well some frontier LLM's of today can solve Sudoku puzzles. We prompted them in a 4-shot manner with Sudoku puzzles (we serialize a puzzle by converting it into a sequence of (row, column, value) triplets) and their corresponding solutions given before asking for the solution for a 5th test Sudoku puzzle. We evaluated 3000 examples on Gemini-1 1.5 Pro and GPT-40. We observed that neither models are able to solve any of the puzzles fully correctly. The results are summarized in Table 1.
1.1 Our setup
We treat each Sudoku/Zebra puzzle as a sequence to sequence problem. In Sudoku, given the sequence of filled cell positions and their values, the model needs to output the sequence of unfilled cell positions and their corresponding values. Similarly in Zebra puzzle, we are given all the clues and the possible values for the characteristics in sequential manner and we need to predict the values in the grid. To focus attention on a model's 's reasoning abilities, we abstract out symbolic versions of the Zebra puzzles. This means we refer to each person as an entity indexed by number and their favorite color or car becomes an attribute number. For both types of puzzles, clearly, the order in which the model outputs the sequence of filled cells doesn't 't matter as long as the values are correct. However, we will see that the order which the solutions are presented to the model during training makes significant difference in the final performance of the model.

---

We consider a dataset of Sudoku puzzles of varying difficulty levels from [Rad20]. In addition, we use Sudoku solver which employs a set of 7 strategies that humans commonly use for solving Sudokus, Given these set of 7 strategies the solver iteratively scans through all unfilled cells and checks if progress can be made using one or more of the strategies. it finds a cell where progress can be made if fills in its value and repeats the process of searching for the next cell to fill. Although some of the 7 strategies are simple and direct, some of them are highly non-trit non-trivial and non-local. From the dataset, we filter out those puzzles which cannot be solved by our solver and end up with 1.9M examples. This ensures that all our puzzles are solvable in polynomial time"
We can characterize the size of a Zebra puzzle by tuple of two numbers: the number of entities and the number of attributes. Each clue in a puzzle one of 7 different types. We generate around 320,000 Zebra puzzles of sizes varying between (3,3) to (6,6) in the following manner. We first design human-like solver for these puzzles which tries to solve the puzzles in an iterative manner without backtracking. This solver runs in time cubic in the number of clues of the puzzle. When generating a puzzle of a certain size, we iteratively keep adding clues to a clue set until our solver is able to solve the puzzle. This way, we can ensure that, similar to our Sudoku puzzles, all our sampled Zebra puzzles are also solvable efficiently. Note that, even in the symbolic format, there are an exponential number of puzzles possible implying that our train set and test set won't 't overlap with a very high probability.
1.2 Our results
In this section, we provide an overview of our results. We mainly focus on the Sudoku puzzles to explain our results and include brief discussion the Zebra puzzles.
Our first experiment studies whether a Transformer is capable of solving the Sudoku puzzle in a fixed cell order (from top-left to bottom-right). This would amount to the model knowing what values single forward pass. We observe that although the model learns to
to fill in each unfilled cell predict the values for some cells in puzzle (average cell accuracy 58.64% % across all unfilled cells), in general, this leads to poor accuracy of solving the complete puzzle (7.2%).
Observe that solving Sudoku puzzle can be thought of as finding casy-to-decode cells and then finding correct value at such cells. We combine this observation with insights from Chain-of- Chain-of-Thhoulee Thought prompting and use our solver to provide the order to fill cells for given puzzle. In this setting, we use the cell positions provided by the solver during the decoding (i.e., position hints of easy to decode cells) and calculate how many cell values the model gets right. In other words, given prefix of partially solved puzzle, we query the solver to find out the "easiest" cell position to solve next and then, conditioning on this position, query the model for its value. The average cell accuracy only goes up marginally by about 3%.
To exploit the full value of the order given by our solver, we train the model from scratch using the solver order. This allows the model to learn what is a good strategic order in which to fill the cells. Importantly this order is adaptive based on the puzzle. To train it in this manner, we first feed each puzzle to our solver and collect the sequence of cells it fills in order. We use these sequences as our training data which acts as our Chain-of- Thought data for the model. This leads to much stronger model which is able to solve full Sudoku puzzles to an accuracy of 87.18% % (see Section 3.4).
Given this new model, we again try giving position hints during decoding as above and we see the average cell accuracy shoot up to 99.02% % This indicates the following. The iterative process of solving Sudokus can be broken down into two steps: (I) searching and finding cell position where we can apply subset of the strategies, (2) given cell position, computing the value that needs be filled in that position. Step (I) is the harder task for a model to learn. We provide examples of Sudoku puzzles where the model makes mistake in step (1) where step (2) is quite trivial (see Section 4.1 for more details). To make the model more proficient at solving the puzzle without the position hints, we perform beam search of width 3 or and notice that this suffices to get stronger full puzzle solving accuracies of 91.36 % and 94.21 % respectively (see Section 3.5).
In environment where the model needs search over a of candidates to take the next step, recent work by [BN24] demonstrated that next-token prediction might be a flawed objective. Another recent work [LSM+ 24] posit including the entire search trace as part of the training Chain-of-Thought
'Each of the 7 strategies the solver uses can be generalized to general n X n grid and they can be applied in (nly(n) time
3

---

data to help a Transformer learn tasks involving search and planning dynamics. In contrast to these works, we observe that Transformers trained with the next-token prediction objective and without access to the entire search trace can learn complex reasoning tasks.
Finally, we further ask if we can similarity between the model's way of solving the puzzles to humans/solvers way of solving the puzzle. We study this via probing which has been a technique to understand the latent conceptual content, see e.g. [LHB 23, AZL23, PCV23, NLW23, JRR 224. In particular, works such as [PCV23, NLW23, JRR 24] argue that often simple functions of the model's activations or weights can extract useful latent information (See Appendix B for more details). We study the following via probing, Generally, humans and algorithmic solvers for Sudoku keep track of a possible set of values for each cell at a given state of the board make progress on solving the Sudoku puzzle. We see that the model also implicitly keeps track of a candidate set and this candidate set matches with the solver's candidate set (see Section 4.2 for more details).
We perform a similar set of experiments as above on Zebra puzzles and observe qualitatively similar trends giving evidence that our conclusions are not limited the domain of Sudoku (See Appendix I for more details). In summary, our contributions are
1. We show that causal language modeling with the Transformer architecture is capable of learning to perform search and reasoning in highly non-trivial domains like Sudoku and Zebra puzzles.
2. We present evidence that the right form of training data which decomposes the problem into smaller constituents is crucial. However this data is not required to be too descriptive. In particular, it need not contain search traces similar to those provided in [LSM* L.J.
3. We perform probing analysis to show that human-like abstract reasoning concepts such as candidate set of values emerge implicitly within the model's activations.
2 Preliminaries and setup
In this section, we provide a brief overview of the logic puzzles we consider and the input/output data format that is fed to the model. More details about Zebra puzzle, dataset, architectures and hyperparameterrs can be found in Appendix D.
Sudoku puzzle and solver. The goal of the sudoku puzzle is to fill out the whole board with numbers 1 to 9 without having duplicates in each row, column, and box (See appendix H for more details). Unless specified otherwise, we will use (r, c) to denote the position of a cell on the board and v(r, c) to denote the value position (r,c) where
{1, 21....... 99} denotes the row number of the cell and e E {1, ,,2,....9) 9} denotes the column number of the cell. Additionally, we use b(r; e) to denote the block number (among one of the nine 3 3 blocks) of the cell at position (r; To solve a Sudoku
puzzle, a sudoku-solver (and humans up to an extent) keeps track of the candidate set for each of the empty cells. See more details about Candidate set in Appendix H.
As mentioned carlier, the generalized version of Sudoku with board size n X n is NP-complete [YS03]. This implies that for some Sudoku puzzles, progress likely can not be made using any strategy that executes in polynomial time. We avoid such puzzles by restricting our focus to those Sudoku puzzles that can be solved using set of 7 well-known and commonly used strategies which are executable efficiently*.. Further details about each of the strategies is provided in Appendix C. An important point to note is that not all the strategies fill value in a cell. In fact, only 2 out of strategies that we use, fill a value in a cell and the other strategies are used to eliminate possible values of a cell and narrow down the candidate set at particular cell. Additionally, some strategies (e.g., XY wing, Unique rectangle) involve reasoning on multiple cells in different rows/columms/blocks and these strategies don't 't fill value at any cell and therefore, these strategies need to be applied in combination with other strategies to deduce a value at cell. Additionally, we only provide the solution list of cell values to the puzzle during training, therefore the model not getting any direct signal about the strategies that eliminate possible values of a cell and is only getting a signal in combinations of the strategies that deduce a value.
Dataset, model architecture and training. Our training dataset for the Sudoku experiment contains 1.8M puzzles and the test dataset contains MM puzzles. Each puzzle also comes with a difficulty
'The list of the strategies we consider is Lone Single, Hidden Single, Naked Pair, Naked Triplet, Locked Candidate, XY Wing, Unique Rectangle,

---

rating calculated as follows. To rate puzzle, a backtracking based solver (different from the one we use to generate our solver-order data) is employed. This solver tries to iteratively make progress on puzzle using some elimination techniques. When it gets stuck, it makes guesses and tries to solve the puzzle. The difficulty rating the maximum depth of the guess stack the solver had to use to solve the puzzle. Therefore, even puzzle rated 0.5 can require complex strategies beyond simple scanning to solve them without guessing. We train a seguence-to-sqqueee in as input representation of a Sudoku puzzle sequence and needs to output the solution of the puzzle as a sequence. During the training, we provide information about a single cell using three tokens (r, c, v(r, c)): the first two tokens (r,c) contain information about the position of the cell (row and column number) and the third token contains the number in that cell. Each training sequence is divided into two parts. The first part contains the information about cells whose values are given in the puzzle question and the second part contains information about unfilled cells in the solution. Note that there can multiple valid orders for the solution. Also, note that the length of the first part depends on the number of cells filled in the puzzle. We train the model using the next-token prediction loss but we don't 't apply the loss corresponding the prediction of the filled cells given in the question.
model that takes
We use a Transformer-basee layer has 8 attention heads with model dimension of 576 and an MLP of hidden dimension 3456 (6x model dimension) follows in each layer. The total number of parameters of our model is 42M. We use causal masking in the attention layers to avoid looking into the future.
GPT-2 [RWC+ 19] architecture with 8 layers for both puzzles. Each
Evaluation metries. To evaluate the performance of our model, we use the following two metrics primarily: 1) Cell accuracy: denotes the percentage of the unfilled cells whose values are correctly predicted by the model. 2) Complete puzzle accuracy: denotes the percentages of the correctly solved puzzles in the evaluation dataset. A puzzle with even a single mistake is counted as incorrect.
3 Experiments on Sudoku puzzles
We study the performance of a Transformer model when the model is trained with the next-token prediction objective. We set up the model architecture and training of the model as discussed in Section 2 however, the question remains how order cells in the input sequences of the Sudoku puzzle during the training of the model. Note that given the state of a Sudoku puzzle, some cells might be easier to solve than others so the order of the cells of input sequences provided during training could be important. We first try using predefined fixed order or a random order of the cells during the training and inference in Section 3.1. However, this leads poor performance. Thereafter, we turn our focus on using a solver to create a better order which we call solver-decomposed reasoning order (Section 3.2). Inspired by uses volver-decomposed reasoning order only during the inference on the above trained models to provide position hints. Yet, conditioning on these position hints during decoding only provides a relatively small improvement in the performance showing that even if we tell the model to find the value in a particular cell, it has not learnt fully how to do so.
literature [WWS+22b), Section 3.3
Therefore, in Section 3.4, we explore training the model using cells provided in soloer-de reasoning order. This provides huge boost to the performance allowing the model to solve over 85% of the puzzles in the test set accurately. However, it still does not achieve near-perfect cell accuracy. Therefore, Section 3.5 uses beam search decoding to improve the performance.
3.1 Training using fixed or random order of the cells
A natural choice for the cell order in the input sequence would be to use a fixed order of the cells or a random order of the cells in the puzzle for the input sequence. Note that the order of the puzzle is only provided during the training and we do not penalize the model for wrong order during evaluation as long as it solves the given sudoku puzzle correctly.
Fixed order of the cells. this ordering of the cells, we arrange the cells in a predefined fixed order of top- to noith of the board of the puzzle. To be more precise. for any two cells (r, e) and (r',e') e') where r and r' denote the row numbers and e and c' denote the column number, we will order the first cell (r, before (r',c') if r < r' or r' and c < d. We order both parts of the puzzle (input sequence)- - given cells in the puzzle and the remaining solution of the puzzle using the alove-mentioned ordering.
5

---

Cell accuracy comparison
Complete puzcle accuraty comparison
100
Camplete acturaty
accuracy
70-
00
Decomposed reasering order
50-
Decomposed reasoning ander
Fixd order
Fixed order
70-
Random order
Random order
10
JM
Steps
Stegs
Figure I: Comparison of cell accuracy and full puzzle accuracy for fixed order training, random order training and solver-decomposed reasoning order training.
Random order of the cells. Another way to arrange the cells that we consider is to randomly order cells in given cells of the puzzle and solution of the inputs. For any given prefix (state of the puzzle), we randomly pick a cell from the set of empty cells and append that cell and corresponding value to the prefix.
We provide the experimental results for the fixed order in Figure 1. We see that the model trained with fixed order achieves 58.64% cell accuracy and only 7.2% full puzzle accuracy whereas the model trained with random order only achieves around 52% cell accuracy and only 1% complete puzzle accuracy.
Results.
In the above ordering of the cells, given state of the puzzle, the model decides on a random cell or fixed cell to output value but at that state, only a few cells might be easier to solve than others and the model trained using random or fixed order of cells do not necessarily decode the easier cells at that state. Therefore, inspired by Chain-of-though literature [WWS+ 22b], we ask the following question: if we provide the model information during inference which cells are easier to fill then does the performance improve? Before we answer the above question, we define the solver-decomposed reasoning order which will be useful in finding cells that are casier to fill.
3.2 Solver-decomposed reasoning order
A natural way humans solve Sudoku is by iteratively trying find cells that look easier to fill. The search process involves trying to see if any of a given set of strategies can be applied to fill in the value otherwise make progress a cell. Inspired by this analogy, we construct order of filling cells using a solver. The solver uses 7 strategies as mentioned in Section 2. At any given state of the puzzle, it tries to apply an easier strategy first and if it can make progress with easier strategy then it goes to harder strategy. To apply a strategy, the solver goes through all the cells and tries to apply the strategy for each cell make progress toward solving the puzzle. Progress doesn't 't necessarily mean filling a value in a cell but simply eliminating possible values from the candidate set (set of possible values) of cell also counts as progress. We call the order given by the solver as polver-decomper
reasoning order or decomposed reasoning order for brevity when it is clear from the context. Note that the decomposed reasoning order arranges the cells based on how easy they are to fill in, as the solver initially employs simpler strategies to make progress.
3.3 Hinted cell accuracy
In recent years, chain-of of-tn-of-thought (CoT) prompting [WWS* 22b] has emerged as one of the effective techniques to extract complex reasoning abilities from model. The main idea of CoT is to lead the model to the correct output by providing intermediate steps to help the model. Inspired by the CoT prompting, we ask if providing the model additional information about masier-to-decode cells during inference improves the performance?
Specifically, we use decomposed reasoning order to provide position hints during inference. Recall that to infer value at position (r,c) c) at state of the puzzle 8, we provide (s, r, e) as input to the transformer model and the random-order baseline model is trained to predict value as next token given positions in previous two-tokens (r, c), and because positions are chosen randomly during the training, the model is forced to use the positions in previous two-tokens (r, c) while predicting the

---

value. (Note that this is not the case for the model trained with fixed order and therefore, we don't t consider them in this experiment).
Now, to provide additional information to the model about the easier cells to predict, we use the decomposed reasoning order. Specifically, for any given state s, provide the state s to the solver to obtain the position of the easiest cell. Suppose the solver picks (r', c'), then we provide (s, r', e') to the trained model predict a value (r',')). We reiterate this process for every non-empty cell of the puzzle. We measure the cell accuracy in this setting and we call this accuracy as hinted cell accuracy to denote the provided hints about easy-to- to-doedde positions from the solver.
Results. We see that the model trained using random order achieves 54.57% hinted cell accuracy. This means that providing hints about easy-to- to-deodde positions improves the accuracy by around 3% over without any hints. At first glance, it seems like the model is struggling significantly to implement the correct strategy even when we provide information about the positions of easy-to-fill cells as hints during the inference. However, this might not be the correct conclusion because of the following reasons: during the training, the model is trained predict the value from random cells, and the model needs to learn and apply very hard strategies as well to improve its training loss. In the process of learning hard strategies, the model might fail to learn easier strategies as well because of various reasons (e.g., limited data corresponding to easier strategies, limited model size, etc.).
When use decomposed reasoning order during the inference, it helps to improve the performance for the model trained using random-order of the cells but because the model needs to perform a hard search and reasoning task while decoding value at single cell, it not only seems to hurt the model in searching easy-to-decode cells but also affects its reasoning capabilities to decode a value at given cells even after we explicitly provide positions of easy to fill cells. This motivates to use decomposed reasoning order during the training.
3.4 Using solver for CoT training
Solving the sudoku puzzle can be decomposed into two sub-tasks: 1) Search across the board to find the cells that are easy to fill and 2) After finding the easy-to-fill cell, apply the correct strategy on the cell to obtain a correct value in it. As mentioned earlier, the model trained for fixed-order and random- order does not have explicit incentives to perform search for easy-to-fill cells. Therefore, the motivation for providing the colver-decomposed reasoning order during the training is to provide an order of cells such that training model using the order helps the model to decompose the complex task of solving sudoku into smaller sub-tasks.
To provide decomposed reasoning order of cells during the training, we arrange the cells according to how easy to fill they are. Note that we can obtain this using Then, we use these sequences during the training with the tet-tokee--reedcctin loss corresponding to position tokens incentivizes the model to learn to find casy-to-decode cells, and the loss corresponding to value tokens incentivizes the model to learn the strategy.
loss for all the tokens. Therefore, given a board state the
Result. We provide the result for the decomposed reasoning order training in Figure 1. We see that using the decomposed reasoning order achieves the cell accuracy 94.23 % and complete puzzle accuracy 87.18% accuracy. Training the model on the decomposed reasoning order improves cell accuracy by around 36% over the fixed-order training and by around 43% over the mandom-order training. The most noticeable improvement comes in complete puzzle accuracy where decomposed reasoning order training achieves $7.18 % accuracy whereas the fixed-order training achieves around 8 % accuracy and the random-order training achieves around %.
Hinted accuracy for training using solver-decomposed reasoning order. Even though solver- decomposed reasoning order training significantly improves performance over fixed-order training and uundom-ordes training, it does not achieve near-perfect accuracy. Therefore, to understand whether the model is struggling to perform search for easy-to-decee to-decode training or to employ a strategy given a position, we perform the experiment of providing hints about -asy-to- positions (presented in Section 3.3). Recall that to measure the hinted cell accuracy for a model, we provide information about easy-to to-d-odde decode cells to the model during inference and measure cell accuracy in that setting. We see that the model with solver-decomposed reasoning order training achieves 99.02 % hinted cell accuracy. This means that the model can employ the correct strategy assuming it has access to information about easy-to- -ee-dd- cells and that the performance gap in cell accuracy (94.23 % to near-perfect accuracy) is mainly due to searching for easy-to -ecode cells.
7

---

Cell accuracy
Complete puzzle accuracy
Beam width & =
94.23 %
87.18 %
Beam width & 3 96.07 %
91.36 %
Beam width A =
98.03 %
94.21 %
Table 2: Performance (cell accuracy and complete puzzle accuracy) change as we increase beam- width in beam-search.
Next, we try to bridge the gap between 94.23% cell accuracy and 99.02% hinted cell accuracy achieved by the model trained using decomposed reasoning order. To improve the accuracy, we first understand the number of cells that are filled for puzzle when the model is making the first mistake for the puzzle. Note that when the model makes mistake by filling in an incorrect value on the puzzle, then the probability of the model making mistake on the remaining empty cells increases. We also see this happen in our experiments (See Appendix E).
A hypothesis about lower cell accuracy than hinted cell accuracy is that given a certain state of the puzzle, the model might be confused between several cells about which cells are easier to decode. However, if the model is allowed to explore multiple potential cells of the puzzle, it might figure out the true solution as the model will make a prediction confidently for the true solution of the puzzle compared to other wrong solutions. Because of this reason, we try beam-search decoding for the model trained using solver- decooposee reasoning order.
3.5 Beam-search decoding
Beam-search decoding (used in many popular NLP systems, e.g. [WSC+ 16]) in language modeling allows the model explore multiple partial decoding of the sequences during the inference of language model and output the most probable explored sequence. The beam width k of the beam search decoding denotes how many partial sequences (hypotheses) are kept each step. At each step of the decoding, it expands all partial solutions of the puzzle by decoding one more token. Then, among this expanded partial solution set, the model selects the top k most probable partial solutions. This process is repeated for the decoding of every token. Note that beam search only maintains k possible output sequences throughout the decoding process. Compared to standard decoding, beam search incurs computational overhead of a factor of k22 In the Sudoku puzzle, It is important to note that the beam search can not try out all possible outputs for the Sudoku puzzle. After all, the total number of outputs can be arbitrarily large because many of the empty cells will have on average 2 to 5 possible values and the total number of empty cells the puzzle at least 50.
Results. We present our results for beam- decoding in Table 2. The beam search with k = 1 is equivalent to greedy decoding as it only keeps one partial sequence. We see that beam search with k = 3 improves the cell accuracy by around 2% and complete puzzle accuracy by around 4%. We see similar improvement when we increase beam width from k = 3 to k = Note that the cell accuracy with beam width l- = 5 is able to bridge the gap from the hinted cell accuracy up to large extent but does not need hints about easy-to-decode positions.
4 Analysis
In the above section, we showed that solver-decomposed reasoning order during the training can greatly help improve the model's performance. In this section, we analyze the trained model on several fronts. Section 4.1 contains discussion about failure cases of the model in searching easy- to-decode cells. In Section 4.2, we show that the candidate set information emerges in the model to explain how the learned model is solving the puzzles. We compare the model's performance to neural network-based method designed to solve the Sudoku puzzle [PPW18] in appendix F. Appendix F.2 contains the breakdown of the complete puzzle accuracy across various difficulties.
4.1 Failure in search for easy-to-decode cells
As discussed in section 3.4, the model trained using solver-decomposed reasoning order solves 94.23 % cells of the sudoku puzzles correctly. To understand the failure modes of the model, we measure the hinted cell accuracy by providing information about easy-to-decode cells to the model during inference. We see that the model achieves 99.02% accuracy. This shows that the model can find
8

---

2 9
6
Figure 2: A failure case of the model in searching for casy-to-decode cells. The left figure shows the sudoku puzzle state when the model makes the first mistake and the right figure shows the puzzle's solution. Numbers given in the blue provided in the puzzle. The puzzle makes mistake by choosing to fill the red-colored cell whereas the green background cell can be easily filled.
the correct value at the cell when it is provided the information about casy-to-decode cells and the performance gap in cell accuracy is mainly due to the inability to search for casy-to-ecodde cells.
We also provide some examples of the puzzle situations in Figure 2 and Figure (in Appendix) when the model makes mistake by trying fill cell but there another cell for which is easier fill. This supports our finding by hinted cell accuracy that the performance gap of our trained model to perfect accuracy is due to the inability to search for easy-to-decode cells.
Additionally, a cell can be easy-to casy-to-deett to-decode because of either row, column or block constraint of the Sudoku puzzle. We found that our trained model misses more cells which are easy-to-decode because of the block constraint. This might be due to the input format being not explicit for block and explicit for row and column of cell (recall that cell in the format of (r, c, v(r, c)) as input the model). A natural extension in this case could be to provide block number also an input to the model. We leave it for future work.
4.2 Emergence of candidate set information the model
We saw in the previous section that a model trained with puzzles given in solver-decomposed reasoning order performs very well. Therefore, focus on how the model is learning such task that requires planning and reasoning. As mentioned earlier, the sudoku solver (and to an extent humans) keeps track of possible values that cell can take for the given puzzle. Therefore, ask the following question: does the model also keep track of possible values of cell? Can we extract them from the model?
We answer both of these questions (perhaps surprisingly) positively by showing that for given puzzle, the candidate set of the solver can be extracted from the logits of the model. The candidate set of an empty cell keeps track of possible values that the cell can take given a state the puzzle. Note that given some state of the puzzle, the candidate set at an empty cell (r, c) can be different from {1, ., 9} (set of filled values row r. column c and box b(r, c)} as some of the strategy removes value which does not occur in the same row, column or box.
Calculating candidate set equivalence. For all puzzles in the validation dataset, we obtain the candidate set of all empty cells from the solver when the number of filled cells is in the set S (35, 40, 45, 50, 55, 60, 65, 70, 75). For state
puzzle, we denote the candidate set of the solver at an empty cell (r, c) as (*(8,r, c). We use (s* r,, <) to denote the number of possible values in the candidate set (* r, e). To extract the candidate set from the model at the state s of the puzzle and at an empty cell (r, e), we feed (s, e) as the prefix to the model and values corresponding

---

Number of filled cells Accuracy (%)
35
40
45
50
55
60
65
70
75 99.37
93.19
93.23
94.14
94.81
94.70
96.60
97.71
98.54
Table 3: Candidate set equivalence accuracy when the number of filled cells is different in the given puzzle. The candidate-set equivalence accuracy measures the average overlap between the solver's and the model's candidate set for the correctly solved puzzles.
to top-k output logits where k If. r, c)] becomes the candidate set of the model. We denote the model's ss candidate set as m(s, r, c). Importantly, note that we DO NOT only evaluate the top-k candidates on the cell the model chooses to predict. Although during its natural course of decoding the model might wish to decode cell location A, we force it (by conditioning) to decode at every other location and evaluate the top-k candidates. This ensures that we are looking at what the model thinks is the set of possible candidates of cell location (r1,C1 (1) even when it has decided to decode cell (72, 02) * (r1,c1 next. We note that this style of probing differs from the more common way to perform probing analysis which involves learning finear/non-linee probe which takes in the embedding and outputs a label indicating a concept. However, we use probing in more general sense to refer to understand some of the inner workings of the model.
The accuracy for the candidate set equivalence between the solver and the model state s of a puzzle and at an empty (r, c) is measured by (s, r, c) O m(s, r, (s, c)). The reported accuracy at position n E S in Table 3 is the average over all empty cells when the number of filled cells is for the puzzles which are correctly solved by the model. Intuitively, the candidate-sed equivalence accuracy measures the average overlap between solver's and model's candidate set for the correctly solved puzzles.
Results. The results of candidate set equivalence accuracy are given in Table 3. We see that for all positions the average overlap between the solver's and the model's candidate set is above 93 %. This overlap improves to around 96.5 when the prefix has information about 60 cells and to around 98.5 % when the prefix contains information about 70 cells. Note that to extract the candidate set of the model, we are just reading the logits and not even training linear function. Additionally, the candidate set equivalence result is not only for cells that are easy to decode but for all empty cells. Moreover, during the training of the model, no direct information about the candidate set is provided and the model is only trained to predict the correct value for cell and therefore is not directly incentivized to predict the correct candidate set for all the empty cells with such a high accuracy.
5 Conclusion
We have shown that even on complex logical reasoning tasks such as Sudoku and Zebra puzzles, simple next-token prediction provided with a high-level decomposition of the reasoning steps during training is able to learn to solve the task. This suggests that, given the right level of detail and breakdown of reasoning steps in the training data, a pre-trained model might already present as a prompt
strong reasoning engine (without the need for post-training techniques such as etc). These techniques might help significantly boost
engineering, cofsisenss,,,,, rree-ff-thuughe the baseline performance of a model or potentially make up for deficiencies in the pre-training data however. To move towards more general reasoning systems, an interesting challenge overcome would be to simulate the decomposed reasoning data in an efficient manner. These tasks capture many different types of constraint satisfaction problems and we believe the framework and results should generalize to other settings as well.
Finally, we conclude with some limitations of our study. Firstly, we note that we studied synthetic setting on a toy task and real-world reasoning and planning tasks can be much more abstract and challenging. More specifically, Sudoku is a task which doesn't 't require the same degree of long-term planning as some harder benchmarks. That is, any cell we can make progress on is progress unlike constraint problems where one might need to backtrack. Moreover, we focused on reasoning setting where creative thinking was not required. That is, the model did not need to invent new strategies to solve any test time puzzle.
an interesting future direction to study to what extent causal language modeling can yield novel reasoning strategies. Moreover, there can be many different types of reasoning tasks which are not logic puzzles (for instance probabilistic puzzles or rule-less puzzles, see c.g. [GLFS24]) and our experiments do not explore those.
10

---

Acknowledgments and Disclosure of Funding
Authors would like to thank Erik Vee for guiding them to use the hinted cell accuracy to understand the failure modes of the trained model.
References
[AAA*23] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Flo- rencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
[ABB+22] Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan, Karol Hausman, et al. Do as can, not as say: Grounding language in robotic affordances. arXiv preprint arXiv:2204.01691, 2022.
[AG23] Pranjal Awasthi and Anupam Gupta, Improving tongth-generalization in transformers via task hinting, arXiv preprint arXiv:2310000726, 2023.
[AZL23] Zeyuan Allen-Zhu and Yuanzhi Li. Physics of language models: Part 1, context-free grammar. arXiv preprint arXiv:2305. 1.200./3677 13673, 2023.
[BMR+20) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Pra- fulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models few-shot learners. In NeurlPS, 2020.
[BN24] Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction. arXiv preprint arXiv:2403. 06963, 2024.
[BPL 16] Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint 1119991611.09940. 2016.
[CFK*23] Constantine Caramanis, Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos. Optimizing -auutinn-samperss for combinatorial problems: The landscape of policy-gradient method, In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 44035-1409. Curran Associates, Inc., 2023.
[CMWC22] Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. arXiv preprint arXiv:221 12588, 2022.
[CT]+21] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brock- man, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021.
[DLS+24] Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, al. Faith and fate: Limits of transformers on compositionality. Advances in Neural Information Processing Systemx, 36, 2024.
[GLFS24] Panagiotis Giadikiaroglou, Maria Lymperaiou, Giorgos Filandrianos, and Giorgos Stamou. Puzzle solving using reasoning large language models: A survey, arXiv preprint 2rXiv:2402.11291 2024.

---

[GTLV22] Shivam Garg, Dimitris Tsipras, Percy S Liang, and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes. Advances in 2022.
Neural Information Processing Systems, 35:30583-30553
[HBK*21] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang. Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv: (tt:::2203008888 2021.
[HXX*22] Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, et al. Inner mono- logue: Embodied reasoning through planning with language models. arXiv preprint NkIV:2207.056066 2022.
[JRR+24] Yibo Jiang, Goutham Rajendran, Pradeep Ravikumar, Bryon Aragam, and Victor Veitch. On the origins of linear representations in large language models. arXiv preprint 20Xiv:2403.03867, 2024.
[KGR 22] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199-22221 2022.
[LAD+22] Aitor Lewkowye7, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, et al. Solving quantitative reasoning problems with language models. Advances in Neural Information Processing Systems, 35:3843-3857, 2022.
[LAG*22] Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. arXiv preprint arXiv:2210.107493 2022.
[LH16] Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint 1608::1608.03300 2016.
[LHB+23] Kenneth Li, Aspen K. Hopkins, David Bau, Fernanda B. Viégas, Hanspeter Pfister, and Martin Wattenberg. Emergent world representations: Exploring sequence model trained on synthetic task. In ICLR, 2023.
[Lon23] Jieyi Long. Large language model guided tree-of-thought. arXiv preprint arXiv:2305.08291, 2023.
23] Nayoung Lee, Kartik Sreenivasan, Jason Lee, Kangwook Lee, and Dimitris Papail- iopoulos. Teaching arithmetic to small transformers. arXiv preprint arXiv:2307.03381, 2023.
[LSM+24] Lucas Lehnert, Sainbayar Sukhbaatar, Paul Mevay, Michael Rabbat, and Yuandong Tian. Beyond a Better planning with transformers via search dynamics bootstrapping. arXiv preprint 24t.:2402.11088.3 2024.
[3] Ida Momennejad, Hosein Hasanbeig, Felipe Vieira Frujeri, Hiteshi Sharma, Nebojsa Jojic, Hamid Palangi. Robert Ness, and Jonathan Larson. Evaluating cognitive maps and planning in large language models with cogeval. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[MKPZ11] Valeri Mladenov, Karampelas, C Pavlatos, and E Zirintsis. Solving sudoku puzzles by using hopfield neural networks. Proc. of ICACM, 11:174-179, 2011.
[MP23] Aleksei Maslakov and Basil Papadimas. Sudoku solver with step-by-step guidance. 2023.
https://github... com wwtp://w.wooooo/eoooeeeeeeaaeaee
[MSIB21] Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforce- ment learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400, 2021.
[NB21] David Noever and Ryerson Burdick. Puzzle solving without search or human knowl- edge: An unnatural language approach. arXiv preprint Sii::2009002997 2021.
12

---

INCL*23] Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability. arXiv preprint arXiv:2301.05217, 2023.
[NLW23] Neel Nanda, Andrew Lee, and Martin Wattenberg. Emergent linear representations in world models of self-supervised sequence models. arXiv preprini 1rXiv:2309.00941, 2023.
[PCV23] Kiho Park, Yo Joong Choe, and Victor Veitch. The linear representation hypothesis and the geometry of large language models. arXiv preprint 1rXiv2231..03656 2023.
[PPW18] Rasmus Palm, UIrich Paquet, and Ole Winther. Recurrent relational networks. Ad- vances in neural information processing systems, 31, 2018.
[Rad20] David G. Radcliffe. 3 million sudoku puzzles with ratings, 2020.
[RDM*24] Anian Ruoss, Grégoire Delétang, Sourabh Medapati, Jordi Grau-Moya, Li Kevin Wenliang, Elliot Catt, John Reid, and Tim Genewein. Grandmaster-leww chess without search. arXiv preprint arXiv:2402.cm 04494, 2024.
[RWC* 19] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
23] Ishika Singh. Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. Progprompt: Generating situated robot task plans using large language models. 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 11523-11553 IEEE, 2023.
[33 Chan Hee Song, Jiaman Wu, Clayton Washington, Brian M Sadler. Wei-Lun Chao, and Yu Su. LIm-planner: Few-shot grounded planning for embodied agents with large language models. Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2998-3000 2023.
[T]B+23] Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Lean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. Gemini: family of highly capable multimodal models. arXiv preprint 18805 2023.
[VOSK22] Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambham- pati. Large language models still can't it plan (a benchmark for Ilms on planning and reasoning about change). arXiv preprint arXiv:2206. 10498. 2022.
[VSP+17] 17] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is you need. NIPS, 2017.
[WSC+16] Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolf- gang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google's neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv: (609.081444 2016.
22w Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprini arXiv: 171, 2022.
[WWS+22) 226] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe Le, Denny Zhou, et al. Shain-of-thouglee prompting elicits reasoning in large language models. Advances neural information processing systems, 01024844-248877 2022.
[XKZ+24] Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, James Xu Zhao, Min-Yen Yen Kan, Junxian He, and Michael Xie. Self-evaluation guided beam search for reasoning. Advances in Neural Information Processing Systems, 36, 2024.
13

---

[4ZC*24] Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. Travelplanner. A benchmark for real-world planning with language agents. arXiv preprint urXiv:2402.01662, 2024.
[YIL23] Zhun Yang, Adam Ishay, and Joohyung Lee. Learning to solve constraint satisfaction problems with recurrent transformer. In The Eleventh International Conference on Learning Representations, 2023.
[YS03] Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE transactions on fundamentals of electronics, communications and computer sciences, 86(5)10522-1660 2003.
[YXLAZ24a] Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of language models: Part 2.1, grade-school math and the hidden reasoning process. arXiv preprint MXXi:2407.20314 2024.
[YXLA724b] Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of language models: Part 2.2, how to learn from mistakes on grade-school math problems, 2024.
[YYZ*24] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024.
[YZY+22] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022.
[3] Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua Tenenbaum, and Chuang Gan. Planning with large language models for code generation. arXiv preprint 10555:2303.055/0, 2023.
[Zhu] Richard Zhu. Solving sudoku puzzles with recurrent neural networks.
[ZLH24] Zirui Zhao, Wee Sun Lee, and David Hsu. Large language models as commonsense knowledge for large-scale task planning. Advances in Neural Information Processing Systems, 36, 2024.
[ZSH 22] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoe Le, et al. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205. 10625, 2022.
14

---

A Example of a Zebra puzzle
There are people next to each other in a row. Everyone has a different name: Ali, Rose, Randy. Every one lives in different colored house: gold, silver. indigo. Everyone likes different drink: orange juice, beer, coffee. Match the people to the correct value for each of their characteristics using the clues.
1. The person who likes orunge juice is immediately to the left of the person who likes coffee.
2. The person who likes beer is somewhere to the left of the person who lives in the indigo house.
3. The person at the 1st position is Rose.
4. Randy is not the person who likes orange juice.
5. Randy is the person who lives in the gold house.
Figure 3: An example Zebra puzzle with 3 entities, each having 3 attributes.
B
Related work
There many works which study the ability of language models to perform reasoning tasks which involve search and planning with mixed evidence as to whether they are actually learning to reason and plan. [BMR+ 20] was seminal work which showed that large language models (LLLM) few-shot learners and [KGR+ argued that they can be zero-shot reasoners. [LAD+22 22] shows that by fine-tuning the appropriate data LLMs can exhibit high performance the non-trivial MATH [HBK+21] dataset. In addition, the reports of frontier models like GPT-4 [AAA+ and Gemini [TAB+22 23] also contain support for the idea that LLMs can perform reasoning and planning. Building on these lines of work, [HXX-22 22, SBM 23, ABB 22, SWW+23) 23] employ LLMs in planning tasks in the robotics domain.
A number of follow-up works study how we can improve the reasoning and planning capabil- ities of LLMs using various techniques such as prompt engineering, tool use, using LLMs in combination with an external deduction engine. Some of the prominent works in this bracket are Chain-of-Thouuhh prompting [WWS 22b], least-to-most prompting [ZSH 22]. self-consistency [WWS+ 22a], tree-of-thought prompting [Lon23, YYZ+24, XKZ+24], program of thoughts [CMW C22], planning for code generation [ZCS*23]. Of these, [Lon23] evaluate the efficact of Thouuht- reasoning using LLMs like GPT-4 on solving Sudoku puzzles and only achieve results on 5x5 Sudoku puzzles, Moreover, the tree-of-thought prompting technique is known to quite expensive to run. [ZLH24] use LLMs to provide a commonsense world model and a policy which can be fed to Monte-Carlo tree search algorithm. The ReAct framework [YZY 22] uses LLMs to generate reasoning traces and task-specific actions in an interleaved manner.
In contrast to the above, [VOSK22] show that LLMs when acting alone or when combined with techniques such as Chain-of-Thought or Tree-of-thought cannot solve some standard planning and reasoning benchmarks when the questions are rephrased with a new terminology. This is even when we use techniques such as Chain-of-Thought, fine-tuning etc. [XZC+24] show that even the biggest LLMs perform very poorly at real-world travel planning tasks with a multitude of soft and hard constraints. [DLS* + 24] show that LLMs are limited and brittle in their ability to perform compositional tasks such multi-digit multiplication, logic grid puzzles and dynamic programming. [MHF+23) 23) argue that L.MSs have weak cognitive maps which are crucial for planning. [BN24] show that rather than the architecture, the training objective of next-token prediction might be crippling the planning and reasoning ability of a language model.
There are many works which use the help of synthetic tasks to gain insights into how Transformer language models work. We present a non-ext non-exhaustive list here. [LHB [LHB-23] use the synthetic task of learning to predict valid next moves in an Othello game to study whether an internal model of the Othello board emerges in the model or not. [AZL.23] use synthetic tasks such as learning context-free free grammars to understand the mechanics of how large-scale learning in LLMs works. [GTLV22] use
15

---

linear regression from in-context examples to study the in-context learning phenomenon. [NCL [33] use the task of modular addition to understand the specific algorithm shallow Transformer implements to solve the problem. [AG23] use the task of sorting list of numbers to study length generalization.
Comparison to traditional solvers and other ML approaches. Traditional constraint satisfaction libraries use very powerful combinatorial search algorithms solve logic puzzles and much more powerful than any deep model we learn here. In addition, many prior works study machine learning- based approaches for solving general combinatorial problems [BPI,+16, 16, MSIB21, CFK 223.. In addition, there are several approaches that tend to handcraft the architecture or loss to the puzzle using human understanding of the puzzle structure [MKPZ1] I, PPW18, 18, Zhu]. Even though our goal is to understand the capabilities and limitations of causal language modeling and not to compete with such solvers, we discuss some of these works more in detail.
[MKPZ1[] try to setup Hopfield network to solve Sudoku puzzles. [PPW18] handerafts the recurrent network to match the puzzle structure (and obey the constraints) and performs multiple rounds of message passing between cells of the sudoku puzzle to arrive at solution. We evaluate our trained model (trained using causal language modeling) on the test dataset proposed in this work and we observe a comparable performance without handcrafting the network or loss function. [Zhu] achieves a 65% accuracy of RNN based solvers on 3x3 Sudoku puzzles. [NB2I] study how well GPT-2 models trained on natural language perform on puzzle tasks such as Rubik's 's cube and Sudoku. [YIL23] study solving Sudokus using a recurrent form of Transformers by baking the knowledge of Sudoku's 's constraints into the model architecture and training pipeline. For chess, works like [RDM 24] use chess engine such as Stockfish to provide supervised labels for different board states and train a Transformer network to predict the value function of board state. This can then be used to play expert level chess.
C Details about our list of strategies
As mentioned earlier, we consider puzzles with 7 strategies for both Sudoku and Zebra puzzles.
C.1 Strategies for Sudoku puzzles
We first list all the strategies used Sudoku puzzles with an explanation.
1. Lone single: This strategy is applied to a cell where only one candidate number is possible based on the rules.
2. Hidden single: This strategy is applied the situation where a number can only be placed in one specfic cell within a row, column or box.
3. Naked pair: This strategy is applied when two cells in a row, column or box contain the exact same two admissible numbers. This strategy is used to eliminate the number of possible values.
4. Naked triplet": This strategy is applied when three cells in a row, column or box contain the exact same three admissible numbers. Similar to the "naked pair" strategy, this strategy is used to eliminate the number of possible values.
5. Locked candidate: This strategy is applied when all the possible positions for a specific number within box on the same row column.
6. XY wing:
This is a complicated strategy that involves three cells and multiple deduction steps. First, identify a vacant cell (called a pivot) that has two admissible numbers (denoted by X and Y); second, identify two other cells (called wing cells) such that each of them shares column, row or box with the pivot, and one cell has two admissible numbers X and Z, and the other cell has two admissible numbers Y and Z. third, for every other cell that share a column, row or box with both wing cells, Z can be eliminated from their admissible numbers.
7. Unique rectangle: This is another complicated strategy that involves four cells. First, identify four cells that forms rectangle such that three of these cells have only two
16

---

admissible numbers and the numbers are the same, and the fourth cell share at least of the numbers as an admissible number, second, both numbers can be eliminated from the admissible numbers for the fourth cell.
We provide some visual examples of complex strategies in Figure 4.
101
2.7
2.7
2.7
4.8
Figure 4: Examples of complex strategies that involves reasoning about multiple cells. Left: XY- Wing, where pivot cell (gray) has candidate values (X and Y), the wing cells (green) share column, row or box with the pivot and share one candidate value (X or Y) with pivot and another common candidate value (Z), then any cell that shares column, row box with both wing cells (yellow), we can eliminate Z from the candidate set; Right: Unique Rectangle, where four cells form rectangle, among which three cells (gray) share the exact same candidate values, and the fourth cell (green) share at least one of the 2 values, then both values can be eliminated from the candidate set for the fourth cell.
C.2 Relationtypes for Zebra puzzles
We now list all the relationship types for the Zebra puzzles. The examples of the following relation types are given for the original Zebra puzzles.
1. Is equal to: This relation type provides the value for attribute. An example of this type clue can the Norwegian lives in the first house.
2. Is not equal to: This relation type provides the information that attribute can not have particular value. An example of this type of clue can be the Englishman does not live the first house.
3. Immediate left: This relation type provides the relation order for the values either between attribute values entities in the solution. An example of this type of clue be the person with the dog is immediately left of the person who drinks the coffee.
4. Neighbour of: This relation type provides the information that entity with particular attribute value the neighbor of another entity. This relation type generalizes the "immediate left" relationship include the immediate neighbors of the left and right sides. An example this type of clue is the person with a dog is next to the person who drinks milk.
5. Ends in: This relation type provides the information that an entity with the particular attribute value is on either end of the order. For example, the person with the Zebra is on either end of the order.
6. Left of: This relation type provides the relative order of two entities with some particular values. Note that left-of relation does not mean the immediate left of an entity. For example, the person who drinks tea is left of the Japanese person.
7. In between: This relation type provides the relative order of three entities with some particular attribute values. For example, the Englishman lives in-between the person with the Horse and the person who drinks coffee.
D Extended preliminaries
In this section, we provide additional details about the setup of the Zebra puzzle, dataset, and hyperparameters.
17

---

Zebra puzzle and solver. The Zebra puzzle is characterized by the number of entities m and the number of attributes for each entity. e.g., in Figure 3 each person is an entity, and name, house color and drink are attributes associated with each entity. The relationships between entities and attribute values are given as clues in the puzzle and the task is to figure out values for all attributes and all the entities. See Figure 3. Observe that each clue puts some constraints on the value of attributes and entities. e.g.. "The "T person who likes beer is somewhere to the left of the person who lives in the indigo house." clue says that the house (entity) which has drink attribute = beer is somewhere left to the house whose color attribute indigo. As we allow more and more complex relationships in clues, the puzzles become more and more complex. In addition, increasing size makes the puzzles more complex as well as more and more interconnected clues are required to uniquely pin down a solution. Larger puzzles also have higher chance of deeper and trickier reasoning chains being utilized. Similar to Sudokus, a generalized version of m x n Zebra puzzles is also NP-hard. Unlike Sudoku puzzles, where the constraints are only the uniqueness constraints within each row, column and box, Zebra puzzles can have a much more diverse set of constraints which significantly increases the number of 'strategies' that can be used to make progress. Moreover, Zebra puzzles are step closer to natural language than Sudoku puzzles.
In the Zebra puzzles, we have 7 different types of clues. Details about each of the clue types is provided in Appendix C. We generate our own dataset of Zebra puzzles as follows. We first create a Zebra puzzle solver. The solver for the 7ebra puzzle takes in clue set and iteratively tries to make progress by using k-sized subsets of the clues at a time (for l ranging from I to 3). If it is able to make deduction, the solver marks that entry in the answer table and iterates over the clue subsets again. Given this solver, a new puzzle is generated by starting with an empty clue set and iteratively adding randomly generated clues until the solver is able successfully solve the puzzle. While adding new clues we ensure we do not add duplicates. Nonetheless, some clues might still be rendered redundant due to the presence of 2 or more other clues. To keep the clue set lean, once have a puzzle that the solver is able to solve, we filter out the clues unused by the solver. We generate puzzles of sizes m n for m, n ranging in [3, 6).
Our training dataset for the Zebra experiment contains 0.3M puzzles and the test dataset contains 15k puzzles. The input to the model during the training is divided into two parts. The first part (given in the puzzle) contains the clues and the second part (solution) contains values for all attributes and all entities. Each clue contains two parts: 1) the relationship type between attributes and entities and 2) the specific attributes and entity values that are in this relationship whereas the solution part of the puzzle consists of multiple triplets of entity, attribute, and the solution for that entity and attribute. Similar to the sudoku puzzle, there can be different orders in which the solution triplets for each entity and attribute can be provided during the training.
Dataset. We consider the Sudoku dataset from [Rad20] and then we adapt a Sudoku solver from [MP23] to filter out the puzzles that can not be solved by the 7 strategies listed above. After filtering, the dataset contains 1.9M puzzles. We randomly choose O. IM puzzles from these puzzles and use them as validation dataset for the evaluation of the model and the remaining 1.8M puzzles are part of our training dataset.
We use the AdamW optimizer for our experiments. For all the experiments, learning rate is set to 1 x 10-4 and models are trained for 4 million steps with a batch size of 64. We use the cosine learning rate schedule [LH16] with the first 4000 tokens as the warmup phase and an end learning rate factor of 0.2.
E Mistake position frequency experiment.
We present the results about the mistake frequency and first mistake frequency in Figure 5. In this section, we show that for puzzle, the model makes more first mistakes for that puzzle at the start of the puzzle when there are more empty cells because for a model, it is harder to predict the correct value for that cell but the distribution of all mistakes is more towards the later mistakes. This shows that when a model makes a mistake on sequence, it is likely that it will keep making a mistake because of the invalid prefix.
18

---

Number of cells filled vs frequency of all mistake!
Number of cells filled vs frequency of first mistake
Frequency of mistakes
2902-
Frequency firstt mistakes
250
250-
1542
1:0
50-
Number of cells filled
Number of cells filled
Figure 5: Left figure: Plots the number of mistakes made after how many number of cells were filled. Right figures: Plots the number of first mistakes that are made against number of cells that were filled when it made the first mistake.
Performance analysis of the model
F.1 Comparison with neural network-based Sudoku solver
The goal of our work is to understand the capabilities and limitations of causal language modeling (and not to propose new approach to solve the Sudoku puzzle). To understand if there exists performance gap between a model trained using causal language modelling and a model specifically designed to solve Sudoku puzzles, we compare the performance of our model with neural network based Sudoku solver proposed in [PPW18]. Palm et al. [PPW15 18] handcrafts the recurrent network to match the Sudoku puzzle structure (and obey the constraints) and perform multiple rounds of message passing between cells of the Sudoku puzzle to arrive at a solution. We evaluate our trained model on the test dataset proposed in [PPW 18] of 18000 Sudoku puzzles (See Table 4 for the result). We observe that our trained model (trained using solver-decomposet reasoning order and causal language modeling) combined with the beam search obtains a comparable performance without handcrafting the network or loss function.
Eval accuracy
Eval complete puzzle accuracy
Beam search 1
98.15 15.15 %
94.76 %
Beam search width=3
98.28
95.12 %
Beam search width=5
98.37 %
95.43 %
Recurrent Relational Network
NA
96.6
Table 4: Evaluating model on the evaluation dataset of Sudoku given in Recurrent Relational
Network (RRN) by Palm et al. [PPW18] 18]. Our trained model performs comparably to the RRN model but does require handcrafting the network and training procedure for training on the Sudoku puzzles.
F.2 Performance analysis of the model using the difficulty of the puzzles
We provide the breakdown of the complete puzzle accuracy across various difficulties in Figure 6 to better understand the performance of the trained model. We use the difficulty measure provided in the Kaggle dataset [Rad20]. To obtain the difficulty of puzzle, it considers solver (different from the one we use to generate our solver-order data) which tries to iteratively make progress on a puzzle using some simple strategies. When the solver gets stuck, it makes guesses and tries to solve the puzzle. The difficulty rating is the average number of guesses the solver had to make to solve the puzzle. We wish to point out that even puzzle rated 1.0 can require complex strategies beyond simple scanning to solve them without guessing and therefore, this is an imperfect measure of the difficulty.
In Figure 6, we observe that the model achieves almost perfect complete puzzle accuracy for lower difficulty accuracy and as the difficulty of the puzzle increases, the complete puzzle accuracy goes down. We want to note that even when the difficulty rating is between 3 to 3.5, the model can solve around 50 % of the puzzles completely. Additionally, the advantage of beam search increases for
19

---

Difficulty wise complete puzzle accuracy
100
80
Complete puzlie a1L.F103
0. 0.5
0.5
10:15
1.3 1.022. (mmaaty
2.0
25
3.5
Figure 6: Complete puzzle accuracy for different difficulty Sudoku puzzles. The difficulty rating is computed as the average number of guesses the rating-solver had to make to solve the puzzle therefore, the difficulty rating is an imperfect measure of the difficulty.
the higher difficulty puzzles as the model can explore multiple solutions when it has confusion and output a solution at the end.
G Additional examples of failure mode of the model
H
An example of candidate set for the puzzle
H.1 Sudoku puzzle
generalized version of Sudoku has board of size n n with n boxes of size /n x vn, and the goal of the game is to fill partially filled board so that each row, column and /n x vn boxes contains full set numbers from such that none of the rows, columns, and boxes contain duplicates. In our experiments, we consider Sudoku board size x 9 which is further divided into nine 3 boxes.
n. Implicitly, this means that the goal is to fill out the complete board
H.2 Candidate set example
The candidate set for position (r, e) keeps track of all possible values that the cell can take (See Section 4.2 for more details) and then uses the candidate sets to either deduce a value at particular cell or narrow down the candidate set (set of possible values) at empty cell.
I Experiments on Zebra puzzle
To extend our results beyond Sudoku, we also conduct our experiments on the Zebra puzzle (also known Einstein's ''s Puzzle). Like Sudoku puzzles, we consider providing the solution either fixed, random, solver-decomposed reasoning order during the training.
Order of the solution The input provided for a Zebra puzzle during training consists of two parts: the clues and the solution. The solution part contains values assigned to each entity and attribute. Based on the given clues, certain values for specific entities and attributes are easier to determine than others (e.g., in Figure 3, the third clue immediately reveals that the first house has a person with the name attribute = Rose). Thus, as seen in the Sudoku puzzle, the order in which the solution is provided is important.
Similar to Sudoku puzzles, we consider providing the solution in either a fixed, random, or solver- decomposed reasoning order during the training. In all cases, the clues part of the input remains unchanged. In fixed-order training, the solution is given in a predetermined sequence (we use the order starting from the first house's 's first attribute to the last house's 's first attribute, followed by the
20

---

5
6
5
5
2
3
6 8
2
5
Figure 7: Additional examples of the failure of the model in searching for easy-to-decode cells. Both left figures show the sudoku puzzle state when the model makes the first mistake and both right figure shows the corresponding puzzle's solution. Numbers given in the blue are provided in puzzle. The puzzle makes a mistake by choosing to the red-colored cell whereas the green background cell can be easily filled.
next attribute). In random-order training, the solution is shuffled. In solver-dccomposed reasoning order, the solution is arranged based on how the solver approaches the puzzle, progressively using smaller subsets clues make progress and therefore, dividing the reasoning to solve the puzzle into multiple stages.
Results We plot the cell accuracy and complete puzzle accuracy on an evaluation set of puzzles during the training in Figure 9. We see that the training using solver-decomposed reasoning order achieves 95.63 % cell accuracy and 91.17 1. complete puzzle accuracy whereas the random order training achieves almost zero complete puzzle accuracy and the fixed order training achieves 79.36 % complete puzzle accuracy. We believe this is due to larger number of small-sized Zebra puzzles in the evaluation set (e.g., puzzles with or attributes and entities) which are easier to solve than larger-sized Zebra puzzles.
also evaluate the model's performance by using beam search decoding and report the results in Table 5. We see that using beam search decoding with width=3 improves the performance by 0.7 % and increasing it to width=5 improves the performance by an additional 0.2 %.
21

---

1
3
1 2
2
1 4
1 2
2
7
7
7
7
8
7 8
8
7
8
2
2
1
9
5
2 3
614
4
8
6
5
4 5
4
7
9
8
1
2
6
2
3
5
5
9
7
7
7
9
7
4
2
2
8
3
2 3
1
9
7
7
9
2
3
5
5
4
5
5
7
7
7
6
2
8 3
4
5
5
4
2
2
4
1
9
5
8
1
123
3
13112
2
1
2
2 3
3
2
7
91
8
9
8
8
Figure 8: An example of the candidate set for puzzle
Evaluation accuracy
Eval complete puzzle accuracy
Beam search width=1
95.63 %
91.17 %
Beam search width=3
96.03 %
91.83 %
Beam search width=5
96.26 %
92.04 %
Table 5: Zebra puzzle results. The training dataset contains Zebra puzzles with the no. of entities and the no. of attributes in {3, 4, 5, 6} set. For each combination of the no. of entries and attributes. we generate 20k puzzles therefore, the complete dataset contains 320k puzzles of varying sizes. From the complete dataset, we randomly choose 15k puzzles for evaluation and the rest of the puzzles for training the model. Evaluation accuracy: the percentage of correctly predicted attributes on the evaluation set and eval complete puzzle accuracy: the percentage correctly and completely solved puzzles.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All the main claims we make in the paper are reflected in the introduction. Some of them are not highlighted in the abstract due to lack of space but they are all covered in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
22

---

Cell accuracy comparison
Complets puzzle accuracy comparison
100
Complete puzzle arsuuaacy
80%
80
Decomposed reasoning order
60%
Fixed
Random order
40%
Decomposed reasoning order
20%
Fixed order
Random order
20
0.2M
0:4M
0.6M
0.8M
0.2M
0M0M
0.M
Steps
Steps
Figure 9: Comparison of cell accuracy and full puzzle accuracy for fixed order training, random order training, and solver-decomposed order training
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
23

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification:
No theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: All important details of the experiment settings are discussed and presented.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
24

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The GitHub link of the code is provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
public/guie Stts///oooSSuiiiooniiiio
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Details provided in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Factors which can cause variability in our results include random seed used for optimization, train/test split. Due to limited computational and temporal resources we do report error bars from multiple runs with different random seeds. However, observed during our iterations to try and find the best syper-parameter settings for our experiments, all runs were stable and results were robust and consistent across runs with identical
Guidelines:
The answer NA means that the paper does not include experiments.
25

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details are provided the experiments section of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: httpppps...cppppictttttettiiiiie
Answer: [Yes]
Justification: We do not conduct research using human subjects. Our work is founda- tional and does not directly pose risk of negative societal impact. It helps develop our understanding of today's s Machine Learning models.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Paper is foundational research with no tie with any real-world application.
26

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Models trained on toy tasks. Doesn't post risk of misuse. Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We provide citation and describe the license and terms of use in Section 2 for the dataset we use.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
27

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcod com condaataeess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: As of now no new assets are being released although we plan to open-source code at later point.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
28

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "FWe3sTq5jJ", "reviewer": "Reviewer_W1Mz", "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.", "questions": "- Showing some example data in the appendix can be helpful.\n- 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?\n- I assume the input context always includes previously predicted cells and values, is this correct?", "limitations": "The authors have properly adequately limitations of their work in the paper.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The selected task and settings are suitable for studying the reasoning and planning capabilities of language models;\n- 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.\n- The results indicate that causal LMs may be able to perform search and planning internally, which seems novel and insightful for further research.\n- 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.\n- I’m not sure about what the takeaway of Sec. 3.5 is.\n- It seems like the paper used the wrong template.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and constructive feedback. We will make a pass over the paper and fix the typos pointed out and any other errors we find. We address your comments below.\n\n- *Clarifying our probing methodology*: We agree that the more common way to perform a probing analysis involves learning a linear/non-linear model which takes in the embedding and outputs a label indicating a concept. However, we use probing in more general sense to refer to understand some of the innerworkings of the model. In addition, we want to clarify some confusion about how we do our probing analysis. We DO NOT only evaluate the top-k candidates on the cell the model chooses to predict. Although during its natural course of decoding the model might wish to decode cell location A, we force it (by conditioning) to decode at every other location and evaluate the top-k candidates.\n\n- *Probing potential values of one cell while predicting another*: We had considered this approach but felt it was harder to get it working for the following reasons. It is unlikely that the same probe will work across different cells (since the embedding conditioned for predicting a particular cell might suppress information about other cells). This might require us to train separate probes for the values of each cell for which the amount of data available becomes sparse. We did try an alternative approach instead where we take the whole sequence of embeddings the model has produced as input to the probe. However, this concatenated embedding becomes a ~25000 dimensional vector which is very high dimensional and makes it hard to train the probe.\n\n- *Takeaway of Section 3.5*: This section shows the additional gains we get when we use beam search decoding instead of greedy decoding. Beam search decoding with beam width K, maintains K `plausible’ candidates to continue decoding at all times. Note that we prevent a combinatorial explosion with the decoding length by always truncating the list to what we believe are the K most plausible prefixes so far. Using this approach, we show that we are able to further boost the complete puzzle solving accuracy. The main takeaway from this section is that, even in situations where the model’s most likely next token is incorrect, the correct token is in the top-K most likely tokens.\n\n- *Wrong Template*: We are unsure of what the reviewer meant by the wrong template. We apologize if a formatting error slipped past us. Please let us know what specifically you are referring to and we will fix it.\n\nWe answer the reviewer’s technical questions below:\n\n- *Showing example data in the appendix*: We thank the reviewer for this feedback. Indeed, we agree that this would help explain the challenges in our work better and we will add examples to this end in the Appendix.\n\n- *When training with random data, do you include cell location tokens for loss calculations?*: We have tried both including it and excluding it. The results are similar in both settings.\n\n- *Additionally, how do you ensure that the model predicts every cell during testing?*: We deliberately don’t explicitly ensure this. The model is supposed to learn the basic rules of Sudoku as well purely from data. How well they are able to adhere to the rules during inference is a measure of their generalization ability.\n\n- *I assume that the input context always includes previously predicted cells and values*: Yes this is correct. Note that the input puzzle context length can vary as different puzzles have a different number of filled cells to begin with.\n\nIn addition to these comments, we have added additional ablations and a detailed error analysis into where the model struggles in the general response above. We have also shown additional experiments in a different puzzle solving setting - solving Zebra puzzles (also known as Einstein riddles) which shares some similarity with Sudoku puzzles but has many differences. We observe a similar outcome with Zebra puzzles as well where causal language modeling on solver order data is able to teach the model to perform well on these puzzles. Please see the general response for more details on these experiments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Lsg1B9Bhpb", "reviewer": "Reviewer_xEc8", "summary": "* This work presents a study of solving sudoku puzzles via causal language modeling. \n* 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.\n* They study how the model performs with various input representations of a sudoku puzzle. (considering sudoku puzzle as a matrix)\n    * Fixed cell order (from top-left to bottom-right)\n    * Random cell order\n    * Chain-of-thought prompting (using a solver to provide the method to solve the sudoku)\n* 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. \n    * The model's performance improved with CoT prompting. It's even enhanced with the use of position hints and beam search.", "questions": "1. How do models like GPT-4, Gemini-1.5, and Llama-3 perform on these sudoku puzzles? (with and without CoT)\n2. Are the plots in Figure 3 in the CoT+Beam search setting?", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The problem definition, model description, and experimental setup are presented clearly, making the paper accessible and informative.\n* Introduced a sudoku puzzle dataset with steps to solve the puzzles (1.9M puzzles).\n* Probing analysis for tracking the candidate set of cell,", "weaknesses": "1. No SoTA models are evaluated on the sudoku puzzle data.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and constructive feedback. We will make a pass over the paper and fix the typos pointed out and any other errors we find. We address your specific comments and questions below.\n- *No SoTA models are evaluated on the sudoku puzzle data*: We reiterate that our main focus is not to compete with SoTA approaches to Sudoku solving. We are studying the capabilities and limitations of causal language modeling (which is accepted as the dominant approach to train language models today) in a controlled setting and not looking to compare with other approaches. Nonetheless in our general response above, we present a comparison with some other approaches to solve Sudoku puzzles and will add this discussion to the paper. Note that in our approach we don’t handcraft any parts of the architecture for Sudoku puzzles.\n- *How do models like GPT-4, Gemini-1.5 and Llama-3 perform on these Sudoku puzzles (with and without CoT)?*: Frontier LLMs like GPT-4 and Gemini-1.5 are expected to perform very poorly on a challenging reasoning task such as Sudoku. The poor performance of these models on planning/reasoning tasks has been reported in [1], [2], [3] and others. For completeness, we performed a small-scale study on Gemini-1.5 and GPT-4o where we queried them with 3000 Sudoku puzzles each  (in a 4-shot with CoT manner) and we analyzed how well they can solve the puzzle. Overall, we found that they got 0% of the puzzles completely right and their accuracy on a per-cell basis was around 8-10% which is close to random guessing. We will include these results in the paper.\n- *A full ablation analysis is not included in the paper*: Thank you for this feedback. We will be extending the number of ablation studies we have in our paper. We wish to point out that we did include some ablations such as experiments with CoT data vs random order data vs fixed order data. In addition we have also included ablations for different beam search widths. In addition, we will have now performed ablations with respect to puzzle difficulties. The results are described in the general response.\n- *Are the plots in Figure 3 in the CoT+Beam search setting?*: We apologize for the confusion. These plots are just CoT training without beam search. We will clarify this in the figure’s caption.\n\n\nIn addition to these comments, we have added additional ablations and highlighted some error analysis into where the model struggles in the general response above. We have also shown additional experiments in a different puzzle solving setting - solving Zebra puzzles (also known as Einstein riddles) which shares some similarity with Sudoku puzzles but has many differences. We observe a similar outcome with Zebra puzzles as well where causal language modeling on solver order data is able to teach the model to perform well on these puzzles. Please see the general response for more details on these experiments.\n\n[1] Large language models still can’t plan (a benchmark for llms on planning and reasoning about change). Valmeekam et al. 2022.\n\n[2] Travelplanner: A benchmark for real-world planning with language agents. Xie et al. 2024\n\n[3]  Limits of transformers on compositionality. Dziri et al. 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9yNzTitmys", "reviewer": "Reviewer_Qf5M", "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.\nThe contribution of the paper is:\n1. Demonstration that causal language models can learn complex reasoning tasks like Sudoku solving through carefully structured training data.\n2. Development of a novel training methodology that leverages solver-decomposed reasoning order to enhance model performance.", "questions": "1. How does this approach compare speed and efficiency to traditional Sudoku-solving algorithms?\n2. What evidence supports the claim that the model is genuinely \"reasoning\" rather than pattern matching?\n3. How well does this method generalize to other types of puzzles or reasoning tasks?\n4. What are the computational efficiency for different tested methods presented?\n5. Can you provide a more detailed error analysis? what are standard failure modes?\n6. Have you investigated whether the model can explain its reasoning process, similar to how humans might describe their Sudoku-solving steps？", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "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.\n\n2: 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]\n\n3: 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] \n\n4: 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.\n\n5: Computational efficiency: There's insufficient discussion of the computational costs involved comparing the different order/decomposing as well as beam search appraoches.\n\n6: Lack of error analysis: A detailed examination of where and why the model fails would provide more insight than focusing on its successes.\n\n[1] Giadikiaroglou, P., Lymperaiou, M., Filandrianos, G., & Stamou, G. (2024). Puzzle Solving using Reasoning of Large Language Models: A Survey.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and constructive feedback. We address your comments below.\n\n- *Lacks theoretical or methodological advancements*: We reiterate that our main contribution is not proposing a new theory or a new method to train LLMs. Rather it is an advance in our understanding of the precise capabilities and limitations of causal language modeling. Our work is similar to works such as [1], [2], [3] which show that Transformers can learn useful world models. \nThat being said, we posit that our insight on showing the right style of data to train models on for reasoning puzzles might be helpful in developing better pre-training data collection strategies for general LLMs.\nOur contribution is novel because on general-purpose LLMs such as GPT-4, there is much evidence [5], [6], [7] that these models do not do well at challenging reasoning/planning tasks. Hence, apriori, it is not obvious that Sudoku puzzles can be solved by causal LM alone.\n\n- *Narrow scope - evaluations on other reasoning puzzles/variants*: \n  - Firstly, we note that Sudoku is a challenging task where prior work had not shown success of the causal LM approach (see point in general response about performance of frontier LLMs). While Sudoku is a specific puzzle setting, this enables us to perform a controlled study where we can quantify the exact amount of generalization we observe.Taking the reviewer’s feedback we added experiments with a second puzzle type: Zebra puzzles, where we observed similar results. Please refer to the general response and the attached PDF for more details. We will also add these to the paper.\n  - In addition, we believe that Sudokus involve many sub-reasoning tasks involving deductive logic, mapping to abstract concepts etc and are representative of many challenging deterministic puzzles. Hence, we believe, our main message is robust to changes to the puzzle such as the logical dependency structure while keeping the required components of logical inference, search, and planning the same.\n  - Rule-less puzzles require world knowledge to solve and complicate a principled and controlled study of the type we conducted. It is challenging to generate CoT style data for such puzzles on a large scale. We believe this is a very interesting direction for future research.\n  - We also like the idea of stochastic puzzles. It would be interesting to see how causal LM performs on them but we believe this is outside the scope of the current paper.\n\n- *Comparison to traditional Sudoku solvers and AI approaches*: Please see the corresponding point in the general response above.\n\n- *Overstated claims of reasoning vs pattern matching*: We disagree with this comment. Human reasoning also involves a great deal of pattern matching. However, this happens in an abstract concept space rather than the raw input space. For instance, when presented with a novel coding problem, one might perform an abstract pattern matching to understand whether dynamic programming or divide and conquer are applicable. A lot of frontier research also involves pattern matching. Hence, we argue that learning to pattern match in an abstract concept space consistently over a number of steps is reasoning. While we agree that our setting focuses on a single puzzle type, the model learns to solve unseen puzzles; it learns abstract “strategies” during training and applies them for a test puzzle. This is pattern matching in the abstract concept space. Moreover, some of these abstract strategies can involve O(n^3) computation to find the right square to apply the strategy to. The model is learning to do this search! In addition, it learns to do this consistently for over 50 steps. Hence, our claim of the model learning to reason.\n\n- *Computational Efficiency*: The computational cost of the different orders of the data in our paper is the same. In particular, giving only the value filled in each cell in a step by step manner is more efficient than giving an entire search trace as is done in [4].\nBeam search only adds a constant K^2 factor to the decoding process. While further improving the computational efficiency of LLMs is an important area of research, that is not our primary focus and we leave it for future work. We will add a detailed discussion on the computational efficiency aspects in the paper.\n\n- *Error analysis*: Thanks for the feedback. We have a preliminary error analysis in the paper. Please refer to the general response for details on this. We will be adding a more extended error analysis in the paper.\n\n- *Explaining model’s reasoning process*: Our toy model can’t generate English explanations. However, our probing study shows that the model implicitly keeps track of candidate sets (the set of possible values in a given cell). This is a commonly used technique by humans. In addition, we have done an edit distance analysis to study how much the choice of cell locations to decode varies between the model vs the solver. We find that there is a great deal of alignment between these two orders thus providing additional evidence of a human-like reasoning process.\n\n[1] Emergent world representations: Exploring a sequence model trained on a synthetic task. Li et al.\n\n[2] Physics of language models: Part 1, context-free grammar. Allen-Zhu et al.\n\n[3] Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process. Allen-Zhu et al.\n\n[4] Beyond a*: Better planning with transformers via search dynamics bootstrapping. Lehnert et al. \n\n[5] [1] Large language models still can’t plan (a benchmark for llms on planning and reasoning about change). Valmeekam et al.\n\n[6] Travelplanner: A benchmark for real-world planning with language agents. Xie et al.\n\n[7]  Limits of transformers on compositionality. Dziri et al.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k6YjkmpYbD", "reviewer": "Reviewer_Uxpn", "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.", "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?", "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.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "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).\n\nThe 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.\n\nShould link to dataset (https://www.kaggle.com/datasets/radcliffe/3-million-sudoku-puzzles-with-ratings).\nAccording 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.\n\nShould mention the 42M param GPT-2 architecture earlier in the paper than Appendix B.\n\nMinor quibbles:\n\n* 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.\" \n  + ->   \"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.\"\n\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and constructive feedback. We will make a pass over the paper and fix the typos pointed out and any other errors we find. We address your comments below.\n\n- *Selecting puzzles solvable by a solver*: We emphasize that we did this filtering on both our train and test sets to ensure that the puzzles can be solved in reasonable time. Additionally, although our solver only uses 7 strategies, many of the strategies are highly advanced (a hobby Sudoku solver might not be aware of some of them). We thus argue that our solver is a complex algorithm, albeit one which doesn’t use backtracking. We agree that this rules out puzzles which can be solved in reasonable time with backtracking and hence our results currently do not show that causal language modeling on transformers yields them with planning capabilities in complex scenarios requiring extensive backtracking.\n\n- *Difficulty rating of puzzles on Kaggle*: We wish to point out that the difficulty rating provided on Kaggle is an imperfect measure of the difficulty of the puzzle. This rating is computed as follows. To rate a puzzle, it consider a solver (different from the one we use to generate our solver-order data) which tries to iteratively make progress on a puzzle using some elimination techniques. When the solver gets stuck, it makes guesses and tries to solve the puzzle. The difficulty rating is the average number of guesses the solver had to make to solve the puzzle. Therefore, even a puzzle rated 0.5 can require complex strategies beyond simple scanning to solve them without guessing. Moreover, even for puzzles with rating 0, the elimination technique employed by the solver includes the hidden single strategy which is quite computationally intensive. That being said, we provide an analysis about how the complete puzzle accuracy changes as we increase the rating of puzzle in the attached PDF of the global response. \n\n- *“Polynomial time claim”*: To clarify the claim, by polynomial time we mean that polynomial in $n$ if the size of the puzzles is $n \\times n$.  We say that all our filtered puzzles are solvable in polynomial time because if we consider the general version of Sudoku of size $n \\times n$ and also consider a generalized version of the solver that employs the same set of strategies, then all the examples filtered by the solver will be solved by polynomial time in $n$ because each strategy in the solver runs in polynomial time in $n$ and none of the filtered Sudoku requires guessing a value in some empty cell. We will clarify this claim in the revised version of the paper. \n\nIn addition to these comments, we have added additional ablations and error analysis in the general response above. We have also shown additional experiments in a different puzzle solving setting - solving Zebra puzzles (also known as Einstein riddles) which shares some similarity with Sudoku puzzles but has many differences. We observe a similar outcome with Zebra puzzles as well where causal language modeling on solver order data is able to teach the model to perform well on these puzzles. Please see the general response for more details on these experiments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their careful reviews and constructive feedback. We first address comments raised by multiple reviewers.

- *Comparison to traditional solvers and AI approaches*: We reiterate that our main focus is not to propose a new approach to solve the sudoku puzzle. We study the capabilities and limitations of causal language modeling (which is the dominant approach to train LLMs today) in a controlled setting. Note that in our approach we *don’t handcraft any parts of the architecture or the loss function* for Sudoku puzzles. Nonetheless we present here a comparison with some other approaches and will include a discussion in the revised draft:
  - Combinatorial (Traditional) solvers: SoTA combinatorial solvers can solve a much larger fraction of Sudoku puzzles than our method. In fact, we filter to train and test only on those puzzles solvable by one such combinatorial solver. So our performance on a more general test set will be worse than such solvers. But this is an unfair comparison and not the point of the paper as these solvers are handcrafted with human intellect.
  - Frontier LLMs: Frontier LLMs like GPT-4 and Gemini-1.5 are expected to perform very poorly on a challenging search and reasoning task such as Sudoku. The poor performance of these models on planning/reasoning tasks has been reported in [1,2,3]. Also see point 2 below.
  - “Large Language Model Guided Tree-of-Thought” by Jieyi Long: This paper studies tree-of-thought prompting of LLMs and gets it to work for 5x5 Sudoku puzzles. This is an expensive prompting scheme already for 5x5 puzzles and these puzzles are much easier than 9x9 puzzles.
  - “Recurrent Relational Networks” by Palm et al.: This paper handcrafts the recurrent network to match the puzzle structure (and obey the constraints) and performs multiple rounds of message passing between cells of the sudoku puzzle to arrive at a solution. We evaluate our trained model (trained using causal language modeling) on the test dataset proposed in Palm et al. and we observe a comparable performance without handcrafting the network or loss function (see attached PDF for the result). 
  - “Solving Sudoku with neural networks” by Akin-David et al.: They study how well handcrafted CNNs or LSTMs work for solving Sudoku puzzles and observe worse results than us.

- *Experiments with Frontier LLMs*: We performed a small-scale study on Gemini-1.5 and GPT-4o where we queried them with 3000 Sudoku puzzles each  (in a 4-shot with CoT manner). Overall, we found that they got **0% of the puzzles completely** right and their accuracy on a per cell basis was around **8-11% (close to random guessing)**. We will add these results to the paper.

- *Error analysis*: We have some preliminary error analysis in the paper. Figure 3 (Appendix) shows where during decoding the model makes the first error. It tends to make it more often in the first 10-15 steps of decoding than later. We have added a breakdown of accuracy vs puzzle difficulty in the attached PDF. We also found some examples where there exists some easy-to-decode cells but the model fails to find such cells and therefore tries to decode a harder cell and ends up making a mistake. We have added one such example in the attached PDF. This adds to the evidence (as already mentioned in the paper) that when we provide hints about easy to decode positions to the model, it predicts the value of the cell correctly ~100% of the time. This indicates that the model is struggling to search for the positions that are easy to decode and the model selects positions which can’t be solved with the current information sometimes. 

- *Additional experiments with Zebra puzzles*: To extend our analysis beyond sudoku puzzles as requested by the reviewers, we conduct our experiments for the Zebra puzzle (also known as Einstein's Puzzle) [4]. 
  - *Background*: The Zebra puzzle is characterized by no. of entities and no. of attributes for each entity. e.g., each house in the original Einstein’s puzzle [4] is an entity and color, nationality, drink, smoke and pet are attributes associated with each house. In the puzzle, clues about relationships between entities and attribute values are given and the task is to figure out values for all attributes and for all the entities. Please see [4, 5] for some example puzzles. Observe that each clue can be abstracted out to a relationship between value of attributes and entities. e.g., “The Englishman lives in the red house” clue says that house (entity) which has color attribute = red also has nationality attribute = Englishman. 
  - *Experimental details*: To generate a zebra puzzle, we start with a random permutation of entities, attributes and values of each attribute and then we keep adding clues until the solver can solve the zebra puzzle without guessing/backtracking. To obtain a solution for a puzzle, the solver keeps track of possible values of each attribute for each entity and tries to narrow down them using the clues. The solver tries to make progress with clues with easier reasoning steps first and if it isn’t able to make progress then it tries clues with hard reasoning steps. Thus, the solver will fills the value of attributes which are easier to decide before going to the harder ones. Similar to the sudoku puzzle, we use the order in which attribute values are filled by the solver to train a transformer model of the same size using Causal LM (using the same hyperparameter as in Sudoku puzzle). We report our results in the attached pdf. The trained model solves **92% of the puzzles completely** and for **96% of the attributes**, the model predicts the correct value. 

[1] Large language models still can’t plan. Valmeekam et al. 2022.

[2] Travelplanner: A benchmark for real-world planning with language agents. Xie et al. 2024

[3]  Limits of transformers on compositionality. Dziri et al. 2024.

[4] Zebra Puzzle. Wikipedia page. 

[5] Zebra puzzle on Brainzilla webpage.

Meta-review: the paper probes the order in which reasoning puzzles (sudoku) get filled and its impact on performance. Paper has good insights and clear conclusions which are liked by reviewers. All of them lean positive -- so seems like a clear accept.

Authors should incorporate all discussion points in the revised version.
Decision: Accept (poster)