We thank the Reviewer's for their time and thoughtful feedback, which has provided valuable guidance for refining our paper. We have carefully considered each comment and have revised the manuscript accordingly. Our detailed responses to each point are provided below.

1. Thank you for your thoughtful comments regarding the time, memory, and FLOPs considerations.

   Regarding the input/output tokens and compute: in our work, we use the same vanilla decoder-only Transformer architecture as in [SDWP24] (see line 143 and Appendix D). This choice ensures that the underlying model capacity, token processing cost, and FLOPs per step remain comparable.

   The purpose of Table 1 is mainly to highlight that even very large, high-capacity industrial language models (and even with their reasoning mode enabled) spend significant resources attempting to solve Sudoku, yet ultimately fail to solve the puzzles correctly. This observation arises the need for effective, alternative reasoning strategies in combinatorial problems.

   As stated in the introduction (and now made more explicit in the revised draft), our primary goal was to demonstrate that vanilla Transformers can acquire a generalizable and interpretable reasoning strategy for combinatorial problems such as Sudoku, rather than to optimize absolute compute efficiency or minimize FLOPs.

   It might be possible to create transcripts, for example by using external Sudoku solvers as in [SDWP24], that can produce a shorter solution path. However, this requires sophisticated, predefined solving algorithms/strategies to generate training data, which is not feasible for all Sudoku puzzles. One of the key advantages of our approach is that it is based only on the fundamental Sudoku rules and simple clever guessing, without relying on handcrafted strategies.

2. We added additional relevant references and discussion about SAT solvers.

   Please note that although classical SAT solvers can indeed solve Sudoku puzzles very quickly, they are not learned systems. Our goal is not to outperform SAT solvers, but rather to show that vanilla Transformers can acquire a generalizable and interpretable reasoning strategy. This is why a direct comparison with SAT solvers is not appropriate, and instead we chose state-of-the-art works like [SDWP24] as our main baseline (see Table 2).

   In particular, we achieved state-of-the-art results already with our first approach (imitation learning), and then improved further with our second approach (beyond imitation learning), again reaching state-of-the-art performance.

3. We ran DeepSeek-R1 also via its API, for which we paid usage fees. Further details regarding the prompts used are provided in the Appendix to ensure clarity.

4. Our intuition is that the r, c, v + multiple targets line would lie above the blue curve but below the orange and green curves in Figure 3.

We hope these explanations make our framework and decisions clearer. Please let us know if there is anything else you would like us to elaborate on.

Thank you for your follow-up question Reviewer adCH!

In terms of output tokens for the Sudoku task, our method (causal transformer + backtracking) generates on average ~82 tokens until reaching a solution.

For comparison, the optimal (or minimum) number of output tokens for our method would be 81−ngiven+2 tokens. The '+2' accounts for the <start> and <end> tokens, and ngiven is the number of initially filled cells, which is typically in the range of 18 to 34. This optimal case occurs when the model correctly fills all the remaining cells, one token at a time. In contrast, the optimal length for the baseline causal transformer [SDWP24], which doesn't use backtracking, is 3*(81−ngiven). The factor of 3 is because they use three tokens for each move.

This shows that, on average during evaluation, our method outputs fewer tokens than even the optimal output length for the baseline method [SDWP24]. A further advantage is that because their initial input is larger, each token generation is slower and more computationally heavy for their approach.

You are correct that when backtracking is involved, the output length could become quite large. However, our key idea is to iteratively combine logic rules with backtracking, which significantly reduces the search space and therefore the computational overhead of backtracking. The degree to which the search space is reduced depends on the number and effectiveness of the logic rules used. In the Sudoku case, the very simple rules that define the task were enough to accelerate our method, making it both viable and efficient despite the use of backtracking. Similar efficiency was observed in the 1-in-3 SAT task with the rules employed there.

We sincerely thank the Reviewer for their constructive feedback and valuable suggestions. Their comments have helped us identify areas where additional clarification and improvements were needed. Below, we address each of their points in detail:

1. Our framework applies to any problem in NP and while we only illustrate this for Sudoku and 1-in-3 SAT, it is really easy to integrate any other NP problem. Note that since 1-in-3 SAT is NP-complete, by the Cook-Levin theorem, any problem in NP can be written as 1-in-3 SAT.

   However, some problems may benefit from problem-specific optimizations and therefore, we provide a library in Appendix F2 that lets one generate transcripts for any problem in NP by providing the appropriate components.

   Our framework has essentially 3 components that are learnable by a transformer. Solution generation, Solution verification and Guess generation (Hints).

   For any problem in NP, these components are simple to obtain. Problems in NP have short certificates meaning that few guesses are needed to arrive at a solution. Moreover, problems in NP have efficient solution verification meaning that it is easy to verify correct solutions. The challenging part for NP (or NP-complete) problems is to arrive at a good solution and it is an open problem whether this can be done efficiently. As we discussed in our previous response, our goal is to optimize efficiency by automatically learning correct and useful guesses.

   While our exploration was limited to problems in NP, our framework can also apply in other domains, as Reviewer stHu mentioned, with efficient verification like verification of mathematical proofs or program correctness. In fact a similar pipeline was used in the recent work https://arxiv.org/abs/2507.15855 for solving math problems for IMO 2025 where hints like "mathematical induction" and "analytic geometry" where given to a solver that produced proofs that were subsequently verified using an LLM-based proof verifier.

2. Imitation learning refers to training a Transformer to predict the next step in rule-based reasoning transcripts generated by a symbolic solver, or handcrafted solvers such as the [SDWP24] approach.

   In our setup, imitation learning means that the model is trained to follow the sequence of logic steps depicted in the transcripts, i.e. iteratively apply the simple rules and perform guesses in a DFS way. The results of this approach were state-of-the-art compared to the [SDWP24] method, and our framework is simpler since it does not rely on external solvers, unlike [SDWP24].

3. Thank you for your comments regarding the distinction between our work and the previous Causal Transformer [SDWP24].

   There seems to be a misunderstanding in your comment (1). The [SDWP24] approach creates data transcripts based on 7 handcrafted Sudoku-solving strategies (not just rules). This means that good solving algorithms must first be predefined to generate training data. In contrast, our approach relies solely on the fundamental rules of Sudoku combined with simple guessing, without requiring handcrafted strategies.

   In our imitation learning setup, we do not allow the model to make wrong guesses and backtrack. In the beyond imitation learning setup, however, wrong guesses and subsequent corrections are permitted, enabling a more flexible reasoning process. This extension achieved further state-of-the-art results, outperforming our earlier imitation learning approach.

   We also kept our model architecture identical to [SDWP24] (see line 143 and Appendix D) to ensure a fair comparison. Your points (2) and (3) are correct and represent additional differences between the two works.

   Another important difference is that, we formulate the guessing process in the context of the Min-Sum Set Cover problem. We introduce a novel loss, which is described and theoretically justified in Appendix B.

4. In our work we indeed focused on training Transformers for combinatorial problems with problem-specific tokens rather than free-form text. This type of a more succinct/structured representation allowed for efficiency in training and evaluation.

   However, our pipeline is based only on decoder-only Transformers (like LLMs) and can be directly combined with natural language expressing the transcripts in plain English. e.g. instead of using token 134 we could instead write "I place number 4 in row 1 and column 3". Also we could be more descriptive in some tokens, e.g. when a deadend token appears, we could describe in natural language 'conflict occurred; no valid value can be placed in row X and column Y." However in this case training and evaluation would be far less efficient as the input sequence length increases. We might also need a larger Transformer model to capture the increased complexity of this expanded vocabulary.

   So in principle, our method is not limited to input sequences of symbolic encodings. It could be applied to any combinatorial puzzle, as long as we can apply some logic rules to the problem and we can express them in natural language in a consistent way.

5. The training data transcripts for the Transformer consist of Sudoku puzzles represented in RCV format (row–column–value). This defines the sequence structure and includes multiple target predictions and guesses. The training input is exactly as illustrated in Figures 2 and 5.

6. Sorry for the confusion regarding the oracle terminology and we will clarify further in the paper to make it clear.

   We provide two theoretical oracles as a reference to help parse the results, one upper-bound and one lower-bound, and are unrelated to transformers or specific architectures.

   The upper-bound oracle corresponds to knowing the full Sudoku solution but not which cells are backdoors. This corresponds to guessing the correct value for a random unfilled cell (after the basic rules are applied) but this guess may not be a backdoor resulting in a restart.

   The lower-bound is similar but does not assume we know the solution. After the basic rules are applied, it chooses a uniformly random (cell, value) combination that does not conflict with the existing values, i.e. appears valid but may not be correct and restarts if the combination is not a backdoor. Note that a backdoor must necessarily be correct as the solution to a Sudoku is always unique.

   Regarding the choice of L1 and L2 losses, please note that the L2 loss corresponds to the standard Cross-Entropy loss, while the L1 loss is our novel contribution, derived from the Min-Sum Set Cover problem as discussed in Section 3 and Appendix B. You can interpret this L1 loss in terms of a geometric distribution: we treat each good guess as a Bernoulli trial where a “success” means finding a valid backdoor. Not every correct guess actually works as a backdoor, so each attempt can succeed or fail. The goal is to minimize the expected number of trials needed to find a working backdoor; analogous to minimizing the expectation in the geometric distribution.

7. What Table 1 mainly aims to show is that even these large, high-capacity industrial models spend a significant amount of time attempting to solve Sudoku, yet in the end, they fail to actually solve anything.

   In our case, the inference time is in the order of milliseconds (while achieving ~99% accuracy).

   Regarding training, we trained our model for 3 million steps with a batch size of 32 using the AdamW optimizer, on a single NVIDIA A10G GPU. We omitted detailed training and inference times because they depend heavily on the specific computational resources used. In our case (single A10G GPU), the training time took approximately 168 GPU hours.

8. Thanks for mentioning the SAT solvers related work and DPLL algorithm. We have added relevant references and discussion.

9. Regarding Table 2, the [SDWP24] model is trained and tested only on Sudoku puzzles that can be solved using the 7 handcrafted strategies they define. Randomly generated Sudoku puzzles cannot always be solved with these strategies, so it is not even possible to create full training transcripts for all such data.

   For this reason, we provide an approximate accuracy for [SDWP24] on random puzzles (thus marked with * in Table 2). The results for [SDWP24] on the Kaggle filtered and RNN datasets are taken directly from their paper.

   The difference in performance arises from our general framework, as described earlier, and not from the choice of dataset. Note that we compare our model against several state-of-the-art approaches, and both of our methods outperform them (see Table 2).

We hope these explanations make our approach and choices clearer. Please do not hesitate to ask if you have additional questions; we would be glad to provide further details.

I appreciate the authors for their clarifications via rebuttal. While the rebuttal adds some useful context, I believe the paper still needs improvements in clarity and exposition before it can be considered for acceptance.

We appreciate the Reviewer's time and effort in reviewing our work. The feedback has highlighted important aspects for clarification, and we hope that further discussion will help address any remaining concerns. Below, we provide their responses to each point:

1. In our work we focused on training Transformers for combinatorial problems with problem-specific tokens rather than free-form text. However, our pipeline is based only on decoder-only Transformers and can be directly combined with natural language expressing the transcripts in plain English - instead of using token 134 we could instead write "I place number 4 in row 1 and column 3". We opted for a more succinct representation for efficiency in training and evaluation.

   As we discuss in our answer to Reviewer 8BxY, there are additional opportunities for applying our framework to other problems, including mathematics as you already suggested.

2. Due to page limitations, we decided to add the detailed results and descriptions of the SAT experiments in Appendix. If the paper is accepted, we plan to extend the main manuscript to include further details on the SAT problem.

3. We have corrected the typos mentioned.

4. Sorry for the confusion regarding the oracle terminology and we will clarify further in the paper to make it clear.

   We provide two theoretical oracles as a reference to help parse the results, one upper-bound and one lower-bound, and are unrelated to transformers or specific architectures.

   The upper-bound oracle corresponds to knowing the full Sudoku solution but not which cells are backdoors. This corresponds to guessing the correct value for a random unfilled cell (after the basic rules are applied) but this guess may not be a backdoor resulting in a restart.

   The lower-bound is similar but does not assume we know the solution. After the basic rules are applied, it chooses a uniformly random (cell, value) combination that does not conflict with the existing values, i.e. appears valid but may not be correct and restarts if the combination is not a backdoor. Note that a backdoor must necessarily be correct as the solution to a Sudoku is always unique.

5. Indeed, the number of puzzles seen in the r,c,v representation (shown in Figure 3) is 3 times lower. In our work we do not consider the number of data-points as we can produce novel puzzles using our Random Puzzle Generator. It seems that the important parameter for improving accuracy is the number of tokens consumed by the transformer as its convergence is slow in the initial phase. For a fair comparison, we compared the number of tokens consumed which also accurately reflects the wall-clock training time as the models are identical. We can thus observe that our rcv representation can achieve higher accuracy compared to r,c,v for the same training time. Also r,c,v needs much more training time to achieve same accuracy as the rcv approach.

6. The "backdoor property" we refer to is primarily an empirical observation, 99,8% of the Sudoku Puzzles from our Random Generator can be solved using at most 1 Guess (backdoor cell). This holds for our chosen and well-defined distribution of random Sudoku Puzzles. Since it is difficult to find which is the right backdoor, our model requires more guesses to identify this.

   As shown in Figure 6 and discussed in lines 318–323, for more than 50% puzzles typically 1-2 tries are sufficient to identify the backdoor. We reworded this part of the manuscript to make it clear that this is an empirical finding rather than a theoretically established property of all Sudoku instances.

7. We have not explored this hybrid approach, as our primary goal was to demonstrate that vanilla Transformers can acquire a generalizable and interpretable reasoning strategy. Note that our model can still be directly used for inference in a manner to the hybrid approach you describe.

We hope our responses help address the concerns you raised. If there are any remaining points that need clarification, please feel free to let us know, we would be happy to discuss them further.

1. Yes - I understand the formatting could have been more “natural language-like”, but that’s exactly my point - it can also not be. Transformers existed before their application to LLMs, and I don’t see an advantage, or in fact any direct relation between your system to anything language-related.
   If you insist on creating this connection, then you need to compare performance of different models, with and without fine-tuning etc.

2. Using wall-clock measurement as the metric is completely legitimate, but it still looks like an advantage of the representations, not the system.

3. Yes I understood that it’s an empirical property - the question is whether your network learns to identify it faster (less attempts) with time. Also, I’m still not sure I understand why, during inference, you backtrack at the second failed attempt. During training - to train the network to guess the backdoor move - that I understand, but during inference it’s unclear to me.

We sincerely appreciate the Reviewer's insightful review of our work which have enabled us to address the issues, and we hope that through further discussion, we can clarify any remaining concern. Below, we provide our responses to each point:

1. We agree that a naive DFS approach can be intractable for large-scale combinatorial problems. However, the idea of combining DFS with simple rules, like DPLL, is quite powerful and is known to solve even large scale combinatorial problems like SAT. Our first finding is that even small Transformers can learn to implement such rules with DFS.

   Once we realize that Transformers, are capable of reliably solving hard combinatorial problems, we also realize that doing it efficiently is paramount.

   The key advantage of our framework is the integration of clever guessing (see Figures 2 and 5).

   Even plain DFS can be made faster by rewarding correct guesses instead of just following the DFS rules. Our work in the second part of the paper illustrates a more clever pipeline that rewards guesses that are simultaneously correct and useful and explicitly limits the depth of search. This pipeline is significantly more efficient and exploits the powerful predictive capabilities of Transformers.

   We formulated the guess selection problem as a Min-Sum Set Cover problem, which reduces the number of possible paths to explore and speeds up the solving process (see also Section 3 the losses comparison).

2. Our framework applies to any problem in NP and while we only illustrate this for Sudoku and 1-in-3 SAT, it is really easy to integrate any other NP problem. Note that since 1-in-3 SAT is NP-complete, by the Cook-Levin theorem, any problem in NP can be written as 1-in-3 SAT.

   However, some problems may benefit from problem-specific optimizations and therefore, we provide a library in Appendix F2 that lets one generate transcripts for any problem in NP by providing the appropriate components.

   Our framework has essentially 3 components that are learnable by a transformer. Solution generation, Solution verification and Guess generation (Hints).

   For any problem in NP, these components are simple to obtain. Problems in NP have short certificates meaning that few guesses are needed to arrive at a solution. Moreover, problems in NP have efficient solution verification meaning that it is easy to verify correct solutions. The challenging part for NP (or NP-complete) problems is to arrive at a good solution and it is an open problem whether this can be done efficiently. As we discussed in our previous response, our goal is to optimize efficiency by automatically learning correct and useful guesses.

   While our exploration was limited to problems in NP, our framework can also apply in other domains, as reviewer stHu mentioned, with efficient verification like verification of mathematical proofs or program correctness. In fact a similar pipeline was used in the recent work https://arxiv.org/abs/2507.15855 for solving math problems for IMO 2025 where hints like "mathematical induction" and "analytic geometry" where given to a solver that produced proofs that were subsequently verified using an LLM-based proof verifier.

3. We are familiar with the work of Bello et al. (2016) and follow-up works and will add a short discussion in the paper.

4. While we have not looked at Sudoku-Bench which seems to be a newer dataset and has been released after our submission, there are a number of Sudoku benchmarks that exist of varying difficulty. Our goal was to provide a comprehensive benchmark and Sudoku generator which is transparent in its puzzle selection which is essentially uniformly random Sudoku boards and thus not biased towards a particular solution.

5. Thank you for your question regarding the depth of guesses.

   We note that our first part based on imitation learning does not have any constraints in depth and is very effective getting 99% accuracy. One can allow arbitrary depths or use DFS with iterative deepening until a solution is found.

   What we have not explored yet and it is an interesting direction for follow-up work is how to optimize multi-level guesses to minimize time-to-solution. We describe this in more detail in the section - Summary and Future Directions. While the single level DFS that we present in this work was already sufficient for the challenging task of Sudoku, optimizing multiple level guesses is important for other problems. While the 1-level guess corresponds to Min-Sum Set Cover which is well studied, optimizing multi-level guesses corresponds to the Min-Sum Group-Steiner Tree problem and requires additional insights (theoretical and applied) to integrate in the training pipeline that we plan to explore in future work.

We hope these answers clarify the points you raised. Please let us know if there is anything else we should elaborate on, we would be glad to discuss further.