Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error
Authors: Panagiotis Giannoulis
Yorgos Pantis
Christos Tzamos
Venue: NeurIPS 2025 poster ()
Keywords: LLMs
Transformers
Combinatorial
Sudoku
SAT
Primary area: deep_learning
TL;DR: This work introduces a method for NP-class combinatorial problems using a vanilla Transformer. By combining Sudoku rules and guesses, the approach achieves SOTA results (99.8%). Solution length is analyzed via the Min-Sum Set Cover problem.

Abstract: Despite their proficiency in various language tasks, Large Language Models (LLMs) struggle with combinatorial problems like Satisfiability, Traveling Salesman Problem, or even basic arithmetic. We address this gap through a novel trial \& error approach for solving problems in the class NP, where candidate solutions are iteratively generated and efficiently validated using verifiers. We focus on the paradigmatic task of Sudoku and achieve state-of-the-art accuracy (99\%) compared to prior neuro-symbolic approaches. Unlike prior work that used custom architectures,  our method employs a vanilla decoder-only Transformer (GPT-2) without external tools or function calling. Our method integrates imitation learning of simple Sudoku rules with an explicit Depth-First Search (DFS) exploration strategy involving informed guessing and backtracking. Moving beyond imitation learning, we seek to minimize the number of guesses until reaching a solution. This is achieved using depth-1 guessing, showing empirically that almost all Sudoku can be solved using the puzzle's rules with at most one guess. We provide a rigorous analysis of this setup formalizing its connection to a contextual variant of $\textit{Min-Sum Set Cover}$, a well-studied problem in algorithms and stochastic optimization.

Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error
Panagiotis Giannoulis'
Yorgos Pantis 2.3 Christos Tzamos
National Technical University of Athens, Greece National and Kapodistrian University of Athens, Greece Archimedes, Athena Research Center, Greece
Abstract
Despite their proficiency in various language tasks, Large Language Models (LLMs) struggle with combinatorial problems like Satisfiability, Traveling Sales- man Problem, or even basic arithmetic. We address this gap through a novel trial & error approach for solving problems in the class NP, where candidate solutions are iteratively generated and efficiently validated using verifiers. We focus on the paradigmatic task of Sudoku and achieve state-of-the-art accuracy (99%) com- pared to prior neuro-symbolic approaches. Unlike prior work that used custom architectures, our method employs vanilla decoder-only Transformer (GPT-2) without external tools or function calling. Our method integrates imitation learning simple Sudoku rules with an explicit Depth- -iist Search (DFS) exploration strategy involving informed guessing and backtracking. Moving beyond imitation learning, we seek to minimize the number of guesses until reaching a solution. This is achieved using depth-1 guessing, showing empirically that almost all Sudoku can be solved using the puzzle's rules with at most one guess. We provide rigorous analysis of this setup formalizing its connection to contextual variant of Min-Sum Set Cover, a well-studied problem in algorithms and stochastic optimization.
1 Introduction
Large Language Models (LLMs) based the Transformer architecture have shown remarkable per- formance in a wide range of Machine Learning tasks, achieving statc-of-the-arr results on language un- derstanding and generation benchmarks (VSP+ 17 BMR + 20 RWC 19]. Trained predict the next token in large text corpora, these models acquire strong reasoming abilities, but whether they perform genuine logical reasoning or rely on pattern-matchinn matching remains under debate [VMO 2-3 DLS + Prompting strategies such as Chain-of- Thought and its many variants [NAGA * 21, WWS 22 YY WWS+
BBK 24 CCWC23 KTF+22) ZZH *23 MTG 23 have enabled LLMs to exhibit multi-step reasoning capabilities and solve even complex mathematical problems [HBK 21). Yet, I.LMs still struggle in more structured domains like arithmetic and combinatorial optimization. Controlled evaluations on synthetic tasks, including algorithmic puzzles, formal grammars, logic-based games, and arithmetic problems, have revealed consistent failure modes of current models and methods [LAG 22 LHB+ 23) NLW23 AZL23 YXLAZ24a YXLAZ24b LSL+24] At the same time, the literature highlights that Transformer-bases models have the potential to leverage
Authors listed alphabetically; equal contribution.
Code available /ttttps://gtthub... com/ gpt- http://g.....aaiiiii//aaaaaaaaaa
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Performance of five state-of-the-ar LLMs on solving Sudoku puzzles in 9x9 format. The models.
first two are LLMs, while the remaining three are
Model
Board Accuracy
Cell Accuracy
Time (sec./puzzle)
GPT-4o
0.00%
44.62%
1.60
Gemini-1.5 Pro
0.00%
31.70%
3.20
GPT-o3 mini
0.00%
30.99%
265.70
Gemini-2.5 Flash
0.00%
20.00%
250.80
DeepSeek-Ro R1
0.00%
41.48%
510.40
internal mechanisms like attention to capture combinatorial structure without specialized heuristics external tools. However, appropriately training them to display this behavior remains a major challenge and an active topic of research in robustness and generalization.
In this work, we focus on improving reasoning in Lty-style Transformers for combinatorial problems. We develop a framework for teaching Transformers to identify a path towards a solution to a combinatorial problem through effectively exploring different alternatives with trial-and-error. Our framework relies on training the model to distinguish valid and invalid solutions and incrementally builds solution with clever guesses. This approach applics in very general settings and can be used to solve any combinatorial problem that belong to the NP-class, like Satisfiability, Clique detection or the Traveling Salesman Problem, where verifying a valid solution can be done efficiently.
Our primary testbed in this work Sudoku, chosen for its well-defined rules, extensively studied difficulty levels, and widespread use reasoning benchmark. A standard Sudoku puzzle consists of a grid, subdivided into nine 3 boxes. The grid is partially filled with digits from to 9, and the goal is to complete it subject to the following rules: (i) each cell contains exactly one digit, (ii) each row contains every digit exactly once, (iii) each column contains every digit exactly once, and (iv) each box contains every digit exactly once. We focus on the standard Sudoku puzzles, while our approach can be directly applied to its generalized form with n X n grids which is NP-complete [YS03) and thus equivalent any problem in the class NP.
Solving Sudoku puzzles without external tools extremely challenging even for state-of-the-an industrial-scale LLMs. We evaluated several models, including OpenAl GPT |AAA+23] Google Gemini TAB*23) and DeepSeek 25YZ+25), on randomly generated Sudoku puzzles. As shown in T none of these models were able to produce correct solutions. We tested both LLMS and reasoning- focusedd variants, since Sudoku demands logical reasoning. General-purpose models ran significantly longer as
models generated answers quickly, whereas reasoning-orientee they attempted step-by-step strategies mirroring human solving patterns. However, once they made an incorrect inference, these models could not backtrack and revise their solutions, often ending with contradictory board states. Additional details are provided in Appendix B
Beyond these general- purpose models, several methods have been proposed in the literature to solve Sudoku puzzles via Deep Learning although often relying on specialized architectures. [MKPZI]] investigates Neural Network (NN)-based approach based on Hopfield Networks as an integer optimization tool, addressing its convergence limitations through a coprocessor NN designed to solve linear programming problems. (PPW18) introduces the Recurrent Relational Network (RRN), a generalization of the Relational Network [7] to evaluate multi-step relational reasoning. Their method involves multiple rounds of message passing between Sudoku puzzle cells to arrive at solution. [YIL23) explores solving Sudoku puzzles using a Recurrent Transformer model, integrating Sudoku's 'ss constraints directly into both the model architecture and the training process.
While effective in solving even difficult puzzles, these prior models diverge from the LLM paradigm, and their architectural customizations limit the transferability of their insights to combinatorial reasoning with LLMs. Moreover, these methods follow direct solution approach: given the initial state of the puzzle, the network attempts to predict the entire solution in single forward pass. This design introduces critical limitations. First, there is no mechanism for error recovery, so if the model generates an incorrect solution, it cannot easily revise or correct its output. Second, the reasoning process remains opaque. Unlike humans, who solve puzzles step-by-sted these models not expose their intermediate decision-making making, resulting in behavior that is difficult to interpret trust.

---

Closer to our work, [SDWP24] study how causal language model (GPT-based) can reliably solve Sudoku puzzles. By reframing Sudoku as a next-token prediction task over transcripts of human- like reasoning based on known Sudoku strategies, their Causal Transformer learns to imitate and apply these heuristics incrementally, typically executing simpler strategies before tackling more complex ones. This approach showcases the promising capability of Autoregressive Transformers to successfully internalize and deploy multi-step reasoning procedures in a more interpretable way. However, their proposed method trains the Transformer on structured sequence of logical steps, which do not allow the model to make mistakes. This inherently limits its woblem-solvving capability to strategies present in the training data whereas large fraction of puzzles not solvable by simple logic steps. As such, its performance is significantly worse than previous task-specific models and for puzzles solvable by logic, the model is still not perfect potentially due to the complexity of applying the given chain of heuristics.
Another line of works investigates the reasoning capabilities of Masked Diffusion Models (MDMs) in language generation through the Sudoku task. YYGG=25) show the potential of MDMs to outperform autoregressive models in reasoning and planning with fewer parameters, highlighting their potential impact on downstream applications. [KSK +25 investigate the same models, exploring sampling strategies and token ordering effects, and propose adaptive inference method that further improves performance. While [SDWP24] is more closely related to our work, our results are also comparable to those of 1 who outperformed |YGG 25). This demonstrates that our methodology surpasses all existing state-of-the-as approaches for solving combinatorial tasks such as Sudoku.
2 Methodology
In this work, we introduce a novel framework for reasoning with Transformers. Our method combines imitation learning with trial-and-erron search, enabling models to go beyond learned heuristics. For combinatorial problems such as Sudoku, a verifier exists that can check whether a partial or complete assignment satisfies the problem's 's rules; therefore use this verifier to validate the correctness of each attempted instance. Specifically, when no further logical steps can be applied, the model is trained to make informed guesses, just humans do. Crucially, it can backtrack when guess eventually leads to a dead end, and attempt alternative continuations in Depth-First Search (DFS) manner. By coupling simple learned rules with the flexibility to explore, while continuously relying on the verifier for correctness checks, our method navigates the solution space efficiently. The resulting Causal Transformer solves puzzles robustly and interpretably, showcasing emerging behaviors of progressive reasoning and self-correction.
Our experiments showcase the capability of Transformers to learn this algorithmic behavior. Specif- ically, we observe that the models effectively learn to fill the values based on the Sudoku rules.
98.9
99.8
100
92
93
Board Accuracy %
80
75
80
82
67
Causal Transformer [SDWP)]]]
MDM
RRN
Recurrent Trausformer Learning [V[L2]]
Imitation
Beyond
Imitation
[6SKRCS)]
[Ours]
Figure 1: Comparison of board accuracy with previous state-of-the-ee models on 100K randomly generated Sudoku. As some models are trained on different dataset, we retrain them using our random Sudoku generator and report their increased accuracy with shaded bars.
3

---

When direct rule application is exhausted, the model guesses a candidate value and recovers cor- rectly from incorrect guesses by backtracking when dead end is identified, as in the DPLL al- gorithm [D66 62 As a result of these learned abilities, our method achieved near- hear-perfect accuracy on Sudoku puzzles (99%), demonstrating state-of-the-art performance for a NN-based Sudoku solver (see Figure
Our framework applies to any NP problem, whose solutions are hard to find but easy verify. To demonstrate its generality, we also apply it to the canonical NP-complete problem of Satisfiabil- ity [Coo7]], specifically the 1-in-3 SAT variant, where each clause contains three literals and exactly one must be true. Even in this task, our trained Transformer is able to correctly find solutions 99% of the time. Note that 1-in-3 SAT is a canonical No-copllete problem, and by the Cook-Levin theorem [Coo7[]. any problem in NP can be written as 1-in-3 SAT. However, some problems may benefit from problem-specife optimizations and therefore, we provide library in Appendix [F22 that lets one generate transcripts for any problem in NP by providing the appropriate components.
key ingredient for our framework generating appropriate training transcripts via a DFS routine that guesses partial assignments, checks them for correctness, and either recurses or backtracks as needed. We represent the problem-solving process as a sequence of discrete actions and use an action-level tokenization. This allows us to use a multiple-target approach during training, where the output of each token treated as a distribution of probabílities over the next possible actions (soft-labels), enabling richer learning signals compared to single-target approaches. We provide an efficient Python library (written in C) for generating the transcripts and the corresponding targets (see Appendix F.2). The library can be easily extended to provide reasoning transcripts for any combinatorial problem.
Beyond imitation learning. Whereas earlier studies struggled with accurately solving Sudoku, our approach can teach Transformers solve combinatorial problems with near-perfect accuracy. Our thesis is that once LLMs can learn to solve different problems correctly, the next milestone is to also minimize the reasoning time. In fact, it is well-known that any combinatorial problem can be solved given sufficient time. As long as Transformers can reliably detect valid solutions to a problem, they can also solve by randomly generating tokens and checking whether the produced transcript contains a solution. According to the "infinite-onnke theorem [Mon]. an infinitely large sequence of random tokens will almost-surely contain a valid solution to the problem instance.
For the second part of our work, we aim to use the predictive abilities of Machine Learning to efficiently navigate the space of solutions with the goal of minimizing the expected number of reasoning steps. While in the first part, our goal was to imitate how humans solve problems systematically, in this stage we aim do even better. Humans themselves are limited in their ability to solve combinatorial problems and the DFS method outlined above only works for small instances; quickly becomes intractable as problem size increases. In fact, we do not know of efficient methods for solving most problems in the class NP which is reflected by the major open problem of P vs NP. An important promise of using Machine Learning for combinatorial problems is to develop data-driven methods for solving problems more efficiently than hand-crafted methods can.
Minimizing the time solution is known as the min- objective in combinatorial optimization. To perform a theoretically grounded analysis of this setting, we make two important assumptions: (i) one-level guessing, where we only allow the method to make a single guess and any second guess counts as failure, and (ii) non-adaptive guessing, where for every new guess point we proceed without retaining any memory of previous attempts. Under these restrictions, any instance solvable with one guess will eventually be solved in finite expected time. Remarkably, on randomly generated Sudoku boards, single guess suffices to correctly solve 99..8% of them: after applying the standard set of simple rules, nearly every board admits a backdoor i.c. a guess that, when followed by those same rules, completes the puzzle. In this setup, optimizing the probability of correctly guessing the backdoors directly corresponds to minimizing the solution length. We formulate this problem as contextual variant of the MIN- SET COVER, problem commonly studied in algorithms and stochastic optimization (see Appendix EE. Through this connection, we identify a novel loss function that directly captures the length of the solution and outperforms the standard Cross-Entropy loss, both theoretically and empirically. Our experiments show that for the Sudoku task the solution lengths of the trained model compare favorably to those of an oracle that knows the correct values of all remaining cells without knowing which are backdoors.

---

Despite its simplicity, this setup remains surprisingly effective, even outperforming the previous multi- level guessing method. This advantage arises because, in our beyond imitation learning approach. training uses only successful trajectories, i.e., those that contain the correct guess. While imitation learning provides richer supervision by including both correct and incorrect guess tokens, it also encourages the model through next-token prediction to continue generating incorrect tokens, rather than identifying the correct path. By excluding incorrect tokens from the training data, our approach goes beyond imitation learning and concentrates learning on high-value decisions that directly lead to a solution.
Experimental setup and puzzle generation. All our experiments follow a Causal Transformer (GPT-2 variant [WCC 191) that is identical to that of [SDWP24] to allow for a direct comparison. The model comprises 8 layers, each with 8 self-attention heads, an embedding dimension of 576, and a feed-forward network with hidden dimension 3456 (6 x the embedding size). The model also employs causal masking within its attention layers prevent access to future tokens. In total, this model contains 42M parameters.
We train and evaluate our model using randomly generated Sudoku. We deviate from previous works that used pre-existing datasets, such as the one provided by [Rad20], striving for clean and interpretable distribution of Sudoku puzzles. In particular, our generator works exactly as follows:
Out of the 5,670.903,752.022 0.1.....9966666666 distinct Sudoku boards that exist, it picks one uniformly at random and removes entries based on a uniformly random
permutation of the 81 cells, skipping entry if its removal yields > 1 solution.
This process results in a nearly identical distribution of puzzles to the Kaggle dataset used in previous work but arises in a very principled way. Relying solely on static datasets can introduce bias into the evaluation, these datasets may represent only selective portion of the true distribution. Moreover, having a generator instead of a dataset is more appropriate for combinatorial problems allowing stream-like training and avoiding overfitting issues every puzzle is only seen once. We release an efficient generator as a Python library (written in C), named SudokuPy but the same distribution can also be reproduced using the description above. Full functionality details appear in Appendix FFalnng with a description of the random generator for random instances of 1-in-3 SAT that we use.
Summary of our contributions. Our key contributions can be summarized as follows:
novel trial-and-error reasoning framework. We introduce a principled trial-and-error reasoning framework for solving combinatorial puzzles using LLM-style Causal Transformers. This framework leverages two key ingredients:
(i) Action-Level Tokenized Transcript Generation: A method for representing the problem-solving process as a sequence of discrete actions. Importantly, during training, we utilize a multiple-target approach, where the output of each token is treated as a distribution of probabilities over the next possible actions (soft-labels), enabling richer learning signals compared to single-target approaches. (ii) Exploration Beyond Heuristics: The ability to explore the solution space through informed guessing and backtracking, going beyond reliance on handcrafted heuristics.
State-of-the-art performance on challenging combinatorial tasks. Our LLM-style architecture achieves near-perfect accuracy of 99% on Sudoku puzzles, surpassing previous NN methods. Furthermore, we attain 99% accuracy on the 1-in-3 SAT task showcasing the framework's versatility (see Appendix G
Principled optimization of the guessing process. We theoretically analyze and optimize the crucial guessing component of our framework by reframing it as contextual MIN-SUM SET COVER problem. Through this connection, we identify a novel loss function that directly captures the length of the solution and outperforms the standard Cross-Entropy loss, both theoretically and empirically.
standardized benchmark with an efficient puzzle generation library. To facilitate future research, introduce a fast and lightweight Python library for generating uniformly random Sudoku puzzles from the entire solution space. This enables streaming- like training and provides a standardized benchmark for evaluating and comparing different reasoning models.
'Code available /tttps://gite htgp:/ttww.aa/pppopooooooo/a//aa
5

---

start
rules end
guess level
d
dead end
end
172
316
181
181
316
912
213
636
636
912
912
215
639
119
975
172
316
912
1
213
515
814
639
183
636
766
181
given
rules
Figure 2: Example of training transcript. Values in blue brackets indicate the multiple valid labels for the output of each token during the rule-application step. Yellow brackets show the set of valid candidates when the model reaches guess token at a given level. The selected guess is shown as gray circle with yellow outline. If leads to a dead end, a follow-up guess is made at the same cell.
Imitation learning DFS algorithm
3.1 Method overview
Baseline approach and rule logic. In SDWP224) the authors train GPT-2 variant solve Sudoku puzzles using supervised imitation learning. Their training data consists step-by-step solution transcripts that progressively apply seven human human-crafted crafted strategies (namely the Lone Single, Hidden Single, Naked Pair, Naked Triplet, Locked Candidate, XY Wing, and Unique Rectangle), ordered from simpler to v), where r and e denote the cell's row and column indices, and v the digit placed at that position.
complex. For token encoding, each cell is represented using three tokens: (r,
In our approach, rather than incorporating complex human-designes strategies into the training tran- scripts, we rely solely on applying the four fundamental Sudoku rules. These essentially correspond to the heuristics Lone Single and Hidden Single. Specifically, during rule-based inference, we fill cell values according to the following constraints: (i) an unfilled cell (r, e) can only be filled with value, fill it, (ii) if in a row the digit can only be filled in single position, fill it, (iii) if in column the digit u can only be filled in a single position, fill it, (iv) a x 3 box the digit v can only be filled in single position, fill it.
Encoding choice. We adopt novel tokenization strategy, encoding each move single 3-digit number ranging from 111 to 999, with the first digit representing the row r the second the column c and the third the value This differs from (SDWP24), that use 3 separate tokens for the row, column and value. Our action-level representation reduces the input sequence length by a factor of 3, leading to faster training iterations and more efficient solution generation during evaluation.
Multiple targets. In standard language modeling tasks, each training example consists of fixed sentence, and the model is trained to predict single next token at each step. In contrast, combinatorial puzzle transcripts often permit multiple valid next moves at any given point. To leverage this property, we modify the loss function to support multiple next-token predictions, rather than assuming single deterministic target. Specifically, instead of using the standard Cross-Entropp loss - log Pi, use the sum of Cross-Entropies across all valid targets: - Eies logp;, where Š denotes the set of all valid next tokens at that step. This enables the model treat one input having multiple plausible continuations, enriching its exposure to diverse sequence paths during training. Our experiments demonstrate that this adjustment facilitates faster learning of the task (see Figure 3)
Algorithm. Our algorithm is trained using transcription sequences (see Figure that proceed through the following steps. The input begins with the sequence of moves (tokens) corresponding to the initially filled cells, followed by a "start" token 8. Given this input, to fill all resolvable cells by iteratively applying the basic Sudoku rules. If the board is completed during this phase, the model outputs the "end" token e. Otherwise, outputs "rules end" token r, indicating that no further cells can be filled using rules alone and that guessing is required.
model first attempts

---

100
100
Rubeslogic Actrray
Board Accuracy %
80-
50
T,O
60
Random
25
DCV
Kaggle
2CV
multiple Largets
RRN
0-
40
0B
1.1B
2.2B
3.3B
4.4B
5.5B
0B
1.9B
3.8B
5.8B
7.7B
9.6B
Number Tokens
Soen
Number Tokens Seen
Figure 3: Rule-logic accuracy during training for Figure 4: Board accuracy during training on sam- three model variants differing in token encoding ples from our generator, evaluated on Random, and loss function.
Kaggle unfiltered, and RRN datasets.
At this point, the model outputs the current "guess level" token (an integer from 1 to 99 representing the number of active guesses) and proceeds to select an informed guess from the remaining valid candidates. This guessed move becomes the next token. The model then re-enters the rule-application phase and fills in as many cells as possible based on the updated board.
unresolved cells remain, the model increases the guess level and repeats the guess-and-fill process. In the event of a conflict (c.g.. no valid values exist for cell in the current state of the board), the model outputs a "dead end" token d to signal failure at the current search path. It then backtracks to the last guess level and selects a new guess different from the one that led the conflict. This guess is made on the same cell by selecting a different potential value.
This combination of rule application, informed guessing, and backtracking continues recursively with a DFS approach until a valid solution found or a maximum maximum-allowed allowed sequence length is reached. At inference, we get the solution choosing for any cell its last assigned value in the generated sequence.
3.2 Benchmarks
We evaluate our model across four distinct datasets to benchmark its performance and ensure generalization: (i) Random: our own puzzle generator, used to produce both training data and a held-out 100K test set, (ii) Kaggle unfiltered: the Kaggle dataset (Rad20). uniformly sampled collection of 3M puzzles, from which we randomly sample 100K for evaluation, (iii) Kaggle filtered: 1.9M puzzle subset of the unfiltered Kaggle dataset, curated by (SDWP24) to include only puzzles solvable using seven Sudoku strategies, and (iv) RRN: the dataset introduced by (PPWI8) consisting of 180K training and an 18K test set, stratified by clue count (ranging from to 34 initial givens).
3.3 Results
We begin by evaluating how effectively the Transformer learns to apply basic Sudoku rules, and examine how our design choices, specifically the action-level token encoding and multi-targ loss, affect the speed and efficiency learning. In this setting, rule-logic accuracy is defined as the model's ability to correctly fill all cells resolvable by rule-based inference. If even single such cell is left unfilled or incorrectly filled, the entire board considered incorrect. Figure shows the evolution of rule-logic accuracy during training on our Random dataset, plotted against the number of tokens seen (in billions), which also correlates closely with training time. We compare three configurations: (i) the baseline setup from (SDWP24) using their triplet tokenization and single-target loss, (ii) our compact encoding with tingle-target loss, and (iii) our full approach with both compact encoding and multi-target loss. While all configurations eventually achieve high accuracy, method substantially accelerates learning, with the multi target variant reaching neaf-perfect performance much earlier.
We then track the evolution of board accuracy throughout training on the full Sudoku-solving task, across three test sets: Random, Kaggle unfiltered, and RRN. As shown Figure 4 our generated puzzles yield board accuracy curves that closely mirror those from the Kaggle set, rising in parallel throughout training. This suggests that our generator samples uniformly from the puzzle space, similar to the Kaggle dataset, while also offering the advantages of stream- like training and full
7

---

Table 2: Board accuracy comparison of neural Sudoku solvers across training and test sets.
Test Data
Method
Train Data
Random
Kaggle unfiltered
Kaggle filtered
RRN
RRN
79.30%
79.60%
90.70%
98.90%
RRN PPWT8
Random
92.40%
92.40%
98.30%
97.90%
RRN 82.20%
82.10%
93.90%
99.50 %
Recurrent Transformer YIL23
Random
92.60%
92.50%
99.30%
99.00%
Causal Transformer [SDWP24]
Kaggle filt.
67.16%
67.16%
87.18%
94.80%
MDM KSK*25
Kaggle filt.
74.97%
74.97%
89.49%
_²
Causal Transformer Trial & Error (ours)
Random
98.90 %
98.90% %
99.50%
99.40%
TAccuracy approximated from Kaggle unfiltered performance due dataset similarity. 'Accuracy is unreported because the model code has not been released.
distribution coverage. contrast, the RRN dataset appears easier to solve in practice, with board accuracy rising more quickly, which indicates that its puzzles may be biased toward simpler instances.
Regarding training, our model trained using puzzles generated by our random generator. For the baselines, the Causal Transformer from [SDWP24] was trained on the Kaggle filtered dataset; the same holds for MDM KKSK + 25). The RRN [PWWI I8 and Recurrent Transformer [IL233] models were originally trained on the RRN dataset. For fair comparison, we also trained these models on our random generator using their released training code.
The following key takeaways emerge from the comparative analysis in Table first, our trial-and-error Transformer achieves significant improvements over the Causal Transformer baseline [SDWP24), with absolute accuracy gains of 31.7% (Kaggle unfiltered), 12.3% (Kaggle filtered), and 4.6% (RRN). Notably, while their model is restricted to puzzles solvable by seven numan-crafted strategies (covering only 1.9M of Kaggle's s 3M puzzles), our method generalizes across the full distribution, achieving 98. accuracy on all 3M puzzles. Also, while domain- seeuunn--peeficc models like RRN and the Recurrent Transformer achieve strong performance on the RRN benchmark, our method outperforms them by 6-7% on the more diverse Random and Kaggle datasets, even when these competitors are enhanced by training our random generator. For example, our model achieves 98.9% vs. their 92.4-92.6% on Random dataset. Finally we see that training on our random generator improves performance on diverse datasets (e.g., RRN's +13+ +13.1 % gain on Random test) while preserving RRN benchmark accuracy (97.9% vs. 98.9% when RRN-trained), demonstrating broad coverage without compromising specialization.
4 Beyond imitation learning oppimizzig guesses
In our previous approach, we used imitation learning to teach Transformers to solve combinatorial problems, achieving near-perfect accuracy. Having reached this milestone, now shift focus from correctness to efficiency. Our goal is to leverage the predictive power of Transformers to minimize the expected reasoning time, measured by the number of steps needed to reach valid solution. To this end, we focus on optimizing the guessing steps, as they constitute the primary source of variability in solution length.
To study this systematically and connect with thcoretical foundations, we study a simplified variant of our setup. We impose two constraints: (i) depth-1 guessing, where only single guess is allowed before restarting; and (ii) non-adaptive policies, where each failed attempt triggers a full restart with no memory of past guesses. This reduced problem closely resembles the MIN-SUM SET COVER problem, where the objective to choose elements (guesses) that cover (solve) the problem as early as possible in expectation. We analyze theoretically the connection in Appendix [D] where quantify the performance degradation non non-adaptive methods compared to adaptive ones.
Despite its simplicity, the setup remains surprisingly effective: on randomly generated Sudoku boards, our policy achieves 99.8% 8% accuracy on instances from our random generator; even beating the previous multi-level guessing method. This means that 99.8% of random Sudoku can be solved by
8

---

start
rules end
g
guess node
dead end
end
Backdoors
Restart
135
318
427
318
731
917
731
731
975
343
356
363
g
10%
116
989
135
318
731
898
178
279
776
30%
given
rules
975
471
898
536 725
training
decoding
Figure 5: One-level guessing with restarts. The figure illustrates both training and decoding. During decoding, guess is sampled from the output of the guess node. the guess is not backdoor, even if correct, subsequent application of rules fails to produce a solution and a restart is triggered.
first applying fixed set of simple rules until only single backdoor guess is required; once that guess made, the same simple rules are sufficient to complete the solution. This property, firstly uncovered in our work, and is of independent interest. Note that backdoor move refers to such a single guess such that once it is made, the same simple rules can complete the entire solution. Identifying the correct backdoor non-trivial. Since model does not know in advance which cell is the backdoor, it often requires multiple guesses before finding the right one (see Figure
Our method is illustrated in Figure Unlike our earlier deterministic (argmax) generation policy, here we sample guesses from the model's token distribution at the guess node. If the sampled guess leads to a full solution via rule application, the process terminates; otherwise, it restarts. Crucially, only successful trajectories, those containing the correct guess, are used for training. This design makes the approach more efficient than our previous imitation learning setup: while imitation learning includes incorrect guess tokens and thus provides richer supervision, it also encourages the model to learn to predict subsequent wrong tokens via next-token prediction, rather than immediately identifying the correct path. By excluding incorrect guesses from the training data, this approach goes beyond imitation learning focuses learning high-value decisions. The guess node, viewed as a single decision step, may represent either a single action/token or a thinking sequence (see Appendix D). This process continues until a valid trajectory terminates at "end" token, indicating completion. This framework offers a tractable yet powerful setting to study how well LLMs can prioritize high-value guesses under uncertainty.
Central to our optimization is the training objective applied at the output the guess node, which must encourage the model to concentrate probability mass on all valid backdoor moves. Specifically, S is the set of valid backdoor moves at a given guess node, and pt denotes the probability assigned to each such move, we consider different losses for optimization. The loss corresponding to the expected number of trials is L = (Eies P:) whereas the standard Cross-Entropy loss with multiple targets is L2 implemented using the log-sum-exp trick. One can interpret the Li loss in terms of geometric distribution: we treat each good guess as a Bernoulli trial where "success" means finding valid backdoor. Not every correct guess actually works as 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.
Eies log Ps. For numerical stability during training, we minimize log Li,
In Appendix we theoretically compare the losses C1 and L2 showing that Cn theoretically optimal whereas L2 may result in excessively long sequences. Figure [ggure/ocom compares empirically the performance of the loss functions, L1 and L2, against two reference baselines using a cumulative histogram. The x-axis indicates the number of guesses required to reach valid solution, while the y-axis shows the percentage of instances solved within that number of guesses. To interpret the results, we compare our method against two theoretical oracles: a) upper-bound oracle and b) lower-bound oracle. 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 random unfilled

---

100
Cumulative Peroentage
60
lower hound
upper bound
20
Li
Li
0
10
20
50
100
Guesses until Sucress
Figure 6: Cumulative histogram of guesses needed solve Sudoku instances for two losses and two baselines. The lower bound corresponds to random guessing among the remaining candidates for all unfilled cells, while the upper bound corresponds random guessing the correct value among all unfilled cells without knowing which are backdoors. Remarkably more than 80% of the puzzles are solved with fewer guesses than the oracle upper bound.
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 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 backdoor. Note that a backdoor must necessarily be correct as the solution to a Sudoku is always unique. Both oracles serve only as reference curves, one optimistic (upper bound) and one pessimistic (lower bound), to help contextualize the results. They are purely theoretical and not tied to transformers or any specific model architecture.
We observe that both of our loss functions significantly outperform the lower bound. Notably, the theoretically optimal loss L1 achieves the best performance, especially in the low-guess regime, with a steeper curve and a median of just 1.5 guesses. The sum of coos--Enroopies loss L2 also performs well, closely matching the upper bound and achieving median of 2.2 guesses compared to 2.3 for the bound baseline. These results confirm that both losses guide the model effectively, while Ci offers a meaningful advantage in reducing the expected number of trials.
5 Summary, limitations and future work
In this work, we demonstrate that Transformers can be trained to solve combinatorial problems by effectively exploring solution paths through trial and eиror. Starting with imitation learning, we teach the model to make guesses and backtrack when simple rules are not sufficient which leads to nearly perfect accuracy 99% on the Sudoku and the 1-in-3 SAT tasks. Beyond imitation learning, we introduce principled optimization strategy based on the MIN-SUM SET COVER problem. This approach addresses the inefficiencies of naive guessing, resulting in optimized inference time. For the Sudoku task it even results in higher board accuracy of 99.8%. Our approach is directly compatible with any LLM training pipeline as it is based on standard causal Transformers and only requires using our appropriate transcript sequences and corresponding multi-target losses. We hope that these ideas will enable increased performance of LLMs in tackling combinatorial tasks.
While very effective for the Sudoku task, our method for optimizing the number of guesses is limited depth-1 and non-adaptive policies. Extending the optimization beyond these constraints an interesting direction for further research. Even with non-adaptivity, we can still consider randomized multi-level policies as performing a random walk in the search tree of guesses until a valid solution is reached. Optimizing over such policies would automatically identify how deep the search should go, which guess to make next and when backtrack even no dead-end has been identified. While the architecture could directly follow that of Figure 5 restarting to previous guess nodes if the model chooses so, training the weights appropriately requires carefully thinking about the corresponding loss functions. This is an interesting challenge to explore both theoretically and empirically.
10

---

Acknowledgments and disclosure of funding
This work has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NexIGenerationEU Program. AWS resources were provided by the National Infrastructures for Research and Technology GRNET and funded by the EU Recovery and Resiliency Facility.
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, al. Gpt-4 technical report. arXiv preprint arXiv:2303.08771 2023.
[ACG+24] Alexia Atsidakou, Constantine Caramanis, Evangelia Gergatsouli, Orestis Pa- padigenopoulos, and Christos Tzamos. Contextual pandora's box. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 10944-10952, 2024.
[AG11] Yossi Azar and Iftah Gamzu. Ranking with submodular valuations. In Proceedings of the twenty-second amnual ACM-SIAM symposium on Discrete Algorithms, pages 1070-1079. SIAM, 2011.
[AGY09] Yossi Azar, Iftah Gamzu, and Xiaoxin Yin. Multiple intents re-ranking. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 669-678. 2009.
[APD*22] Eriq Augustine, Connor Pryor, Charles Dickens, Jay Pujara, William Wang, and Lise Getoor. Visual sudoku puzzle classification: A suite of collective neuro-symbolic tasks. International Workshop on Neural-Symbole Learning and Reasoning, 2022.
[AZL23] Zeyuan Allen-Zhu and Yuanzhi Li. Physics of language models: Part 1, learning hicrarchical language structures. arXiv preprint vrXiv:2305.13677 2023.
[BBFT23] Nikhil Bansal, Jatin Batra, Majid Farhadi, and Prasad Tetali. On min sum vertex cover and generalized min sum set cover. SIAM Journal on Computing, 52(2):327-357, 2023.
24] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski. Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 17682-17690, 2024.
[BBT23] Mateusz Basiak, Marcin Bienkowski, and Agnieszka Tatarczuk. An improved de- terministic algorithm for the online min-sum set cover problem. In International Workshop on Approximation and Online Algorithms, pages 45-58. Springer, 2023.
[BC23] Hedyeh Beyhaghi and Linda Cai. Pandora's 's problem with nonobligatory inspection: Optimal structure and ptas. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 803-816, 2023.
[DP22] Curtis Bechtel, Shaddin Dughmi, and Neel Patel. Delegated pandora's box. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 666-693, 2022.
[BEFF23] Ben Berger, Tomer Ezra, Michal Feldman, and Federico Fusco. Pandora's problem with combinatorial cost. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 273-292, 2023.
[BFLL22]] Shant Boodaghians, Federico Fusco, Philip Lazos, and Stefano Leonardi. Pandora's ss box problem with order constraints. In Proceedings of the 2 ACM Conference on Economics and Computation, pages 439, 2020.
11

---

[BGKIO] Nikhil Bansal, Anupam Gupta, and Ravishankar Krishnaswamy. A constant factor approximation algorithm for generalized min-sum set cover. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1539-1545.
SIAM, 2010.
[BGKM20] Aditya Bhaskara, Sreenivas Gollapudi, Kostas Kollias, and Kamesh Munagala. Adap- tive probing policies for shortest path routing. Advances in Neural Information Processing Systems, 33:8682-8692, 2020.
[BK19] Hedyeh Beyhaghi and Robert Kleinberg. Pandora's problem with nonobligatory inspection. In Proceedings of the 2019 ACM Conference on Economics and Compula- sion, pages 131-132, 2019.
[BM23] Marcin Bienkowski and Marcin Mucha. An improved algorithm for online min-sum set cover. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 6815-6822, 2023.
[BMR + 20] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33:1877-1901, 2020.
[CBCMP21] Nicolò Cesa-Bianchi, Tommaso Cesari, Yishay Mansour, and Vianney Perchet. A new theoretical framework for fast and accurate online decision-making. In NeurIPS, 2021.
[CFLS20] Oscar Chang, Lampros Flokas, Hod Lipson, and Michael Spranger. Assessing satnet's ability to solve the symbol grounding problem. Advances in Neural Information Processing Systems, 33:1428- 2020.
[CGMT23] Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, and Christos Tzamos. Approximating pandora's 's box with correlations. In International Conference on Approximation Algorithms for Combinatorial Optimization Problems, 2023.
[CGT+20) Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang. Pandora's 's box with correlations: Learning and approximation. In 2020 IEEE sl Annual Symposium on Foundations of Computer Science, pages IEEE, 2020.
[CMWC23] Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. Trunsactions on Machine Learning Research, 2023.
[Coo71] Stephen A. Cook. The complexity of theorem- theorem-proving proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing (STOC), 1971.
[DF Bolin Ding, Yiding Feng, Chien-Ju Ho, Wei Tang, and Haifeng Xu. Competitive information design for pandora's box. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 353-381. SIAM, 2023.
[DLL62] Martin Davis, George Logemann, and Donald Loveland. A machine program for theorem-proving. Communications of the ACM, (7)):394-377, 1962.
[DLS+23] Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, et al. Faith and fate: Limits of transformers on compositionality. Advances in Neural Information Processing Systems, 36.70293-70332, 2023.
[Dov18] Laura Doval. Whether or not to open pandora's box. Journal of Economic Theory, 175:127-158, 2018.
[DP60] Martin Davis and Hilary Putnam, A computing procedure for quantification theory. Journal of the ACM, 703):201-215, 1960.
12

---

[EHLM19] Hossein Esfandiari, MohammadTaghh HajiAghayi, Brendan Lucier, and Michael Mitzenmacher, Online pandora's boxes and bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1885-1892, 2019.
[FJ06] Bertram Felgenhauer and Frazer Jarvis. Mathematics of sudoku Mathematical Spectrum, 39(1):15-22, 2006.
[FKK + 20] Dimitris Fotakis, Loukas Kavouras, Grigorios Koumoutsos, Stratis Skoulakis, and Manolis Vardas. The online min-sum set cover problem. In International Colloquium on Automata, Languages, and Programming, volume 168, page 51, 2020.
2I] Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, and Stratis Skoulakis. On the approximability of multistage min-sum set cover. In International Colloquium on Automata, Languages, and Programming, pages 65-1, 2021.
[FLL23] Hu Fu, Jiawei Li, and Daogao Liu. Pandora box problem with nonobligatory inspec- tion: Hardness and approximation scheme. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 789-802, 2023.
[FLT02] Uriel Feige, László Lovász, and Prasad Tetali. Approximating min-sum set cover. In Approximation Algorithms for Combinatorial Optimization: International Workshop, APPROX, pages 94-107. Springer, 2002.
[FLX18] Hao Fu, Jian Li, and Pan Xu. A ptas for class of stochastic dynamic programs. In International Colloquium on Automata, Languages, and Programming, page 56, 2018
[GHTZ21] Chenghao Guo, Zhiyi Huang. Zhihao Gavin Tang, and Xinzhi Zhang. Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora's 's problem. In Conference on Learning Theory, pages 2248-2288. PMLR, 2021.
[GJSS19] Anupam Gupta, Haotian Jiang, Ziv Scully, and Sahil Singla. The markovian price of information. In Integer Programming and Combinatorial Optimization: 20th International Conference, pages 233-246. Springer, 2019.
[GKSW24] Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, and Yifan Wang. Bandit algorithms for prophet inequality and pandora's ' box. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms,, pages 462-500. SIAM, 2024.
[GT22] Evangelia Gergatsouli and Christos Tzamos. Online learning for min sum set cover and pandora's 's box. In International Conference on Machine Learning, pages 7382-7403.
PMLR, 2022.
[GT23] Evangelia Gergatsouli and Christos Tzamos. Weitzman's 's rule for pandora's box with correlations. Advances in Neural Information Processing Systems, 36:12644-12664, 2023.
[GYZ+25] Daya Guo, Dejian Yang. Haowei Zhang. Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang. Xiao Bi, et al. Deepseek-rl: Incentivizing rea- soning capability in Ilms via reinforcement learning. arXiv preprint MrXiv:2501.1294 2025.
[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. Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2021.
[NNZ16] Sungjin Im, Viswanath Nagarajan, and Ruben Van Der Zwaan. Minimum latency submodular cover. ACM Transactions on Algorithms, 13(1):1-28, 2016.
13

---

[ISDDZ14] Sungjin Im, Maxim Sviridenko, and Ruben Van Der Zwaan. Preemptive and non- preemptive generalized min sum set cover. Mathematical Programming. 145(1):377- 401, 2014.
[KB15] Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations, 2015.
[KSK*25] Jaeyeon Kim, Kulin Shah, Vasilis Kontonis, Sham M Kakade, and Sitan Chen. Train for the worst, plan for the best: Understanding token ordering in masked diffusions. In Forty-second International Conference on Machine Learning, 2025.
[KTF+22] Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. Decomposed prompting: A modular approach for solving complex tasks. International Conference on Learning Representations, 2022.
[LAG+22] Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. International Conference Learning Representations, 2022.
[LHB+23] Kenneth Li, Aspen K Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, and Martin Wattenberg. Emergent world representations: Exploring sequence model trained on a synthetic task. International Conference on Learning Representations, 2023.
[LSL*24] Nayoung Lee, Kartik Sreenivasan, Jason Lee, Kangwook Lee, and DImitris Papail- iopoulos. Teaching arithmetic to small transformers. In International Conference Leurning Representations, 2024.
MAB+23) Lia Morra, Alberto Azzari, Letizia Bergamasco, Marco Braga, Luigi Capogrosso, Federico Delrio, Giuseppe Di Giacomo, Simone Eiraudo, Giorgia Ghione, Rocco Giudice, et al. Designing logic tensor networks for visual sudoku puzzle classification. In NeSy, pages 223-233 2023.
[MBMW05] Kamesh Munagala, Shivnath Babu, Rajeev Motwani, and Jennifer Widom. The pipelined set cover problem. In International Conference on Database Theory, pages 83 98. Springer, 2005.
[MKPZ11] Valeri Mladenov, P Karampelas, C Pavlatos, and E Zirintsis. Solving sudoku puzzles by using hopfield neural networks. Proc. of ICACM, 11:174-179, 2011.
[MMMG24] Maxime Mulamba, Jayanta Mandi, Ali irfan Mahmutogulları, and Tias Guns. Perception-based constraint solving for sudoku images. Constraints, 29(1):112-15,, 2024.
[Mon] Infinite monkey theorem.
https://en.iiiiipdaaaogg....
monkey_theoree
[MT23] Mingchen Ma and Christos Tzamos. Buying information for stochastic optimization. In International Conference Machine Learning, pages 33388-23411 PMLR, 2023.
[MCC14] Gary McGuire, Bastian Tugemann, and Gilles Civario. There is no 16-clue sudoku: Solving the sudoku minimum number of clues problem via hitting set enumeration. Experimental Mathematics, 23(2):190-2) 2014.
[MG Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao. Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self- refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36:46534-46591 2023.
[NAGA+21] Maxwell I. Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowyzz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show your work: Scratchpads for intermediate computation with language models. CoRR, abs/2 12.00114, 2021.
14

---

[NLW23] Neel Nanda, Andrew Lee, and Martin Wattenberg. Emergent linear representations in world models of self-supervised sequence models. In BlackboxNLP Workshop: Analyzing and Interpreting Neural Networks for NLP, pages 16-30, 2023.
(PD+22) Connor Pryor, Charles Dickens, Eriq Augustine, Alon Albalak, William Yang Wang. and Lise Getoor. Neupsl: neural probabilistic soft logic. In Proceedings of the Thirty- Second International Joint Conference on Artificial Intelligence, pages 4145-4155 2023.
[PGM+ 19] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-perfie perfformrfr deep learning library. Advances in Neural Information Processing Systems, 2019.
[PWW18] Rasmus Palm, Ulrich Paquet, and Ole Winther. Recurrent relational networks. Ad- vances in Neural Information Processing Systems, 31, 2018.
[PWSL25] Bart Pogodzinski, Christopher Wewer, Bernt Schiele, and Jan Eric Lenssen. Spatial reasoners for continuous variables in any domain. In Championing Open-source DEvelopment in ML Workshop @ @ICML25, 2025.
[Rad20] David G. Radcliffe. 3 million sudoku puzzles with ratings, 2020. https: /tops://we www
kaggle. www/dsv/mmaaa/
[RJ06] Ed Russell and Frazer Jarvis. Mathematics of sudoku ii Mathematical Spectrum, 39(2):54-58, 2006.
[RWC+19] 19] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 18))99 2019.
[SDWP24] Kulin Shah, Nishanth Dikkala, Xin Wang, and Rina Panigrahy. Causal language modeling can elicit search and reasoning capabilities on logic puzzles. In Advances in Neural Information Processing Systems, 2024.
[Sin18] Sahil Singla. The price of information in combinatorial optimization. In Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, pages 2523-2532. SIAM, 2018.
[SRB+17 + 17] Adam Santoro, David Raposo, David G.T. Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. A simple neural network module for relational reasoning. Advances in Neural Information Processing Systems, 30, 2017.
[SS21] Danny Segev and Sahil Singla. Efficient approximation schemes for stochastic probing and prophet problems. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 793-794, 2021.
[SW11] Martin Skutella and David P Williamson. A note on the generalized min-sum set cover problem. Operations Research Letters, 39(6):433-436, 2011.
[TAB+23] Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean-Baptin Alayrac Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, Katie Millican, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312. 11055 2023.
[TRS21] Sever Topan, David Rolnick, and Xujie Si. Techniques for symbol grounding with satnet. Advances in Neural Information Processing Systems, 34:20733-20744, 2021.
[vKTT+23] Emile van Krieken, Thiviyan Thanapalasingam, Jakub Tomezak, Frank Van Harmelen, and Annette Ten Teije. A-nesi: A scalable approximate method for probabilis- tie neurosymbolic inference. Advances Neural Information Processing Systems, 36:24586-24600 2023.
15

---

[VM0*23] Karthik Valmeckam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Sub- barao Kambhampati. Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change. Advances in Neural Information Processing Systems, 36:38975-38987 2023.
[VSP+ 17] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
[WDWK19] Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In Interna- tional Conference on Machine Learning, pages 6545-6554, PMLR, 2019.
[Wei79] Martin L Weitzman, Optimal search for the best alternative. Econometrica: Journal of the Econometric Society, pages 641-6554 1979.
[WPSL.25] Christopher Wewer, Bartlomiej Pogodzinski, Bernt Schiele, and Jan Eric Lenssen. Spatial reasoning with denoising models. In International Conference Machine Leurning (ICML), 2025.
22W Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, et al. Chain-of-thoughh prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems,
2022.
[WWS+23] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. cenfsconnisyyncy improves chain of thought reasoning in language models. International Conference on Learning Representations, 2023.
[YGG+25] Jiacheng Ye, Jiahui Gao, Shansan Gong, Lin Zheng, Xin Jiang, Zhenguo Li, and Lingpeng Kong. Beyond autoregression: Discrete diffusion for complex reasoning and planning. The Thirteenth International Conference on Learning Representations, 2025.
[YIL23] Zhun Yang, Adam Ishay, and Joohyung Lee. Learning to solve constraint satisfac- tion problems with recurrent transformer. In 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):1052-1060, 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. In International Conference on Leurning Representations, 2024.
[YXLAZ24b] Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of language models: Part 2.2, how to learn from mistakes grade-school math problems. International Conference on Learning Representations, 2024.
[YYZ+23] 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: 1809-1 1822, 2023.
[S] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoe Le, al. Least-to-most prompt- ing enables complex reasoning in large language models. International Conference on Learning Representations, 2023.
16

---

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: The main claims of the paper are stated the abstract and further highlighted and explained in the introduction. The main body provides all supporting details and evidence.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in Section
Guidelines:
The answer NA means that the paper has 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 a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn 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 few datasets or with 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-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't '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
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
17

---

Answer: [Yes]
Justification: The theoretical component of this research is clearly presented, with complete and accurate proof' provided in Section E
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 or 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 a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
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 whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All important details of the experimental setup are presented in the main body, while specific information about the model's training hyperparameters is provided in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer 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 is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
18

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Both the code associated with this paper and the Python libraries, described in detail in Sections 2 and F are both publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidefines (https://nips.co cc/
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
//nips /nips.cc/puu http:/ulllggggugeeee
for more details.
The authors should provide instructions on data access and preparation, including how to 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, 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
Question: 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?
Answer: [Yes]
Justification: All important details of the experimental setup are presented in the main body, while specific information about the model's training hyperparameters is provided in Section[[]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Yes, appropriate information about the statistical significance of the experi- ments is provided throughout the paper. Our experiments are based on synthetic tasks of Sudoku and SAT. We conducted the experiments on very large samples from fixed distribu- tions of valid instances for both problems and report the number of samples taken typically in the order of 100,000. As such the reported percentages are highly accurate in the reported precision.
Guidelines:
19

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-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 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 етror 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 the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All computational resources mentioned in Section Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as 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 failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: httprrpp....ppplloccccccccccadd.
Answer: [Yes]
Justification: The research presented in this paper fully complies with all aspects of the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make 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 socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
20

---

Justification:
This research primarily aims to advance our understanding of LLMs in combinatorial problems. As such, does not have any direct societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 out that a generic algorithm for optimizing neural networks could enable people 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.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: LLMs trained on toy and controlled tasks such as Sudoku puzzles or SAT problems do not pose any risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example 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]
All previously existing models and datasets are properly cited in the main paper. Additionally, for the pre-existing code used to implement our Sudoku generator, we provide the license and terms of use in Section
Justification:
Guidelines:
The answer NA means that the paper does not existing assets.
21

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license ge.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, papprssitthheeeocc thoode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pase 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 are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Both the code associated with this paper and the Python libraries, described in detail in Sections
2 and are both publicly available.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create 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 participants and screenshots. if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourced data or research involving human participants.
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 NeurIPS Code of Ethics, workers involved 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
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?
Question:
Answer: [NA]
22

---

Justification:
This paper does not involve crowdsourced data or research involving human participants.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending 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 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [Yes]
This research primarily aims to advance our understanding of LLMs in the context of combinatorial problems. To this end, we have developed a pipeline using the GPT- 2 architecture, which is clearly explained and presented in the main paper. Our work also includes comparative experiments with previous research approaches, as well as evaluations against industrial models such as OpenAI, Gemini, and DeepSeek.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve L.LMs as any important, original, or non-standard components.
Please refer to our LLM policy h cct.o//eeeeeeeeee/220555555 for what should or should be described.
A Related work
n² x n² grid divided into blocks. The standard version has a rank of 3, resulting in a 9 x 9 grid. Solving a Sudoku puzzle is an NP-complete problem [YS03), meaning that while verifying solution is computationally efficient, finding one is generally hard. Although there are more than 6.67 x 1021 possible Sudoku grids, only approximately 5.47B are essentially distinct after accounting for symmetries. A valid Sudoku puzzle must have a unique solution. It has been proven through exhaustive computational analysis [MTC14] that at least 17 clues are required ensure a unique solution. Further insights into Sudoku, its mathematical properties, and solving techniques can be found in related works [F]06 RJ06].
Sudoku. Sudoku puzzles played
Beyond the traditional text-based representation of Sudoku, described in the main body, several studies have approached the problem from a visual perspective. These models, often referred to as neural-symbolic (NeSy) systems, perform constraint satisfaction by reasoning over their outputs produce structured predictions. Typically, this involves some form of joint reasoning that integrates prior knowledge and constraints directly into the prediction process. SATNet (WDWKI9) is differentiable MAXSAT solver that employs semi-definite program relaxations to solve MAXSAT problems. can be integrated as a layer within Deep NNs tackle composite learning tasks that written visual Sudoku puzzles.
combine visual perception with logical reasoning, such as solving SATNet notable for its ability to learn to solve visual Sudoku without relying on hand-crafted rules or symbolic supervision. However, subsequent work by (CFLS20) identified a critical flaw in the experimental setup: label leakage issue that inadvertently exposed the model to information about the correct outputs during training. This issue was later addressed by [RS21], who introduced self-supervised clustering and distillation process for training visual classifier within the SATNet architecture. Their approach uses self-supervised pre-training to solve visual Sudoku, effectively
23

---

addressing the Symbol Grounding Problem observed in the original SATNet method. Recent research continues to explore visual representations of Sudoku and develop new NeSy models. Examples include the work of [APD+22 PDA+23 MAB+23 23 23 MMMG24). Recently, another line of work has explored the visual representations of Sudoku using Spatial Reasoning Models, a variation of diffusion/flow models, demonstrating their ability to solve Sudoku [WPSL25, PWSL25..
MIN-SUM SET COVER problem. The MIN-SUM SET COVER problem is a fundamental combi- natorial optimization problem that models sequential decision decision-making. In this setting, there are n boxes, each containing hidden value drawn from a known distribution. Opening box incurs a known cost, and the value revealed is either 0 or oc. A scenario is said to be covered if at least one opened box reveals the value [FLT02] The goal is to determine which boxes to open and which value to select, in order to minimize the total cost. This total cost includes both the costs of opening boxes and the value selected. The MIN-SUM SET COVER problem can be seen as a simplified version of the PANDORA'S Box problem [Wei7]]. There is a substantial body of literature focused on the MIN-SUM SET COVER problem, aiming to improve approximation guarantees and to investigate various generalizations. These generalizations encompass a wide range of settings, including but not limited to, selecting boxes without prior inspection, correlations among boxes, requirements to inspect boxes in specific order, and situations involving
complex combinato- rial constraints [MBWW05] AGY09 BGK AGGI SWI II ISVDZ14) INZ16 FKN 21 BBFT23] Similarly, the PANDORA'S s Box problem itself is also well studied in the literature, with many works exploring its generalized settings to account for more complex information structures and decision-making frameworks [Dov18 FLX18 Sin18 GISST9 [K19, BFLL2 CGT+20 SS21 BDP22] [GMT233 BC23, FLL23 GT23 BEFF23 MT23, 23). In addition, both
MIN-SUM SET COVER and PANDORA'S Box problems have been studied from a machine learning perspective, as it naturally combines algorithmic and learning aspects. Work in this direction has considered frameworks involving sample complexity and online learning models EHLMI)) GT2
BGKM20 2K CBCMP21 GHTZ21 BM23
BET23 ACG 24 GKSW24
B Solving Sudoku with frontier models
We evaluated the performance of several industrial-scale models from the OpenAl GPT [AAA 23).
Google Gemini [TAB*23] 23), and DeepSeek [GYZ+25) families, considering both general-purpon purpose and reasoning- oriented versions. None of these models were able to produce correct solutions. The ceasoning-oriented
general-purpose models generate responses quickly but inaccurately, which made it feasible to test them 1,000 Sudoku puzzles. In contrast, reasoning models require significantly more time for inference; therefore, we limited their evaluation to 10 representative samples. Additionally, we tested the models GPTT-o1, GPT-o3, GPT-o4 mini, and Gemini-2.5 Pro. In every attempt, these models spent the entire inference process producing intermediate steps, without ever generating final solution. For this reason, we have not included them in the result tables.
To further explore the impact of input representation on model performance, we tested three distinct formats for encoding Sudoku puzzles. Examples of each format are provided below.
Single-line format: A single string of 81 digits (with indicaating empty cells), such as: 0001 00000000000000000000000005555110
380500800000
Grid format (9x9): A standard 9-line grid with 9 digits per line, such as:
000100000
000030960
007000402
300006000
000040000
806000120
603050009
290000380
500800000
Triplet format (row, column, value): sequence of 3-digit numbers where the first digit the row index, the second is the column index, and the third is the cell value, such as:
24

---

110
120
130
141
150
160
170
180
190
210
220
230
240
253
260
279 286
310
320
337 340
360
374 380 392
413
420
430
440
450
466 470
480
490
510
520
530
540
554
560 570 580 590
618
620 636 640
650 660
682 690 716 720 733
740 755 760 770 780 799 812 829 830
840 850
860 873 888 890 915 920 930 948 950 960
970 980 990
As shown in Tables 38 the evaluated models consistently fail to solve Sudoku puzzles across three different encoding formats. This failure occurs even when prompts explicitly suggest Sudoku solving strategies the models could follow. When prompts do not guide them to apply logical rules, the models tend to rely external code backtracking algorithm. Backtracking relies brute-force search rather than reasoning, making it less generalizable and frequently inefficient in challenging cases. Moreover, or resource constraints. As shown in the tables below, although Sudoku is a complex reasoning task, general-purpose models typically achieve, in most of the cases, slightly higher cell accuracy than reasoning-specifee models, and they do so with significantly faster inference.
produce suboptimal
incorrect solutions, especially under time
Reasoning models, tend to follow Sudoku-solving strategies models. However, they exhibit two key weaknesses. Firstly, their inference times are significantly higher. As shown in Table 4 the best-time performing general purpose model completed puzzle in 1.6 seconds on average, whereas the best reasoning model required 214.9 seconds in the single- line encoding format, increase of 134.3%. Secondly, while reasoning models apply strategies in more step-by-step fashion, they lack the flexibility to revise incorrect inferences. Once they make mistake, they often continue along invalid solution path, preventing them from arriving correct final answer. In some cases, they spend the entire inference process generating intermediate reasoning steps without completing the puzzle.
systematically than general-purposs.
B.1 Single-Line format
The prompt used in this case was as follows:
Prompt
Solve the following Sudoku puzzle using logical reasoning only. Do not use or simulate any external code, algorithms, automated Instead, apply human-style solving
solvers (e.g., backtracking). techniques such as lone singles, hidden singles, naked pairs, naked triples, locked candidates, pointing pairs, X-Wing, Swordfish, XY-Wing, unique rectangles, and other logical strategies typically used by experienced Sudoku solvers. The puzzle is represented as single line of 81 digits (0 means empty cell): ppuzzle_strigg Return only the final solution as a single line of exactly 81 digits, with no extra explanation or formatting.
Table 3: Performance of two state-of-the-ee art LLMs on solving 1,000 Sudoku puzzles (in single-line format), evaluated by board-level accuracy and average inference time per puzzle. Model
Board Accuracy Cell Accuracy Time (sec.ppuzzle)
GPT-4o
0.00%
46.39%
1.60
Gemini-1.5 Pro
0.00%
34.9%
3.20
Table 4: Performance of three reasoning ofute-of-thh-art LLMs solving 10 Sudoku puzzles (in
single-line format), evaluated by board-level accuracy and average inference time per puzzle.
Model
Board Accuracy Cell Accuracy Time (sec/puzzle)
GPT-o3 mini
0.00%
29.38%
214.90
Gemini-2.5 Flash
0.00%
22.22%
253.80
DeepSeek-RY
0.00%
39.26%
588.20
25

---

B.2
9x9 format
The prompt used in this case was as follows:
Prompt
Solve following Sudoku puzzle using logical reasoning only.
not use or simulate any external code, algorithms, automated solvers (e.g., backtracking). Instead, apply human-style solving techniques such as lone singles, hidden singles, naked pairs, naked triples, locked candidates, pointing pairs, X-Wing, Swordfish, XY-Wing, unique rectangles, and other logical strategies typically used by experienced Sudoku solvers. The puzzle is represented as empty cell): fpuzzle_string
lines of digits each (0 means Return only the final solution as a single line of exactly 81 digits, with extra explanation or formatting.
Table 5: Performance of two state-of-ther the-art LLMs on solving 1,000 Sudoku puzzles (in 9x9 format),
evaluated by board-level accuracy and average inference time per puzzle.
Model
Board Accuracy
Cell Accuracy Time (sec//uuzze)
GPT-4o
0.00%
44.62%
1.60
Gemini-1.5 Pro
0.00%
31.70%
3.20
Table 6: Performance of three reasoning state-of-the art LLMs solving 10 Sudoku puzzles (in 9x9
format), evaluated by board-level accuracy and average inference time per puzzle.
Model
Board Accuracy Cell Accuracy Time (sec/puzzze)
GPT-o3 mini
0.00%
30.99%
265.70
Gemini-2.5 Flash
0.00%
20.00%
250.80
DeepSeek-R1
0.00%
41.48%
510.40
26

---

B.3
(Row, Column, Value) format
The prompt used in this case was as follows:
Prompt
Solve the following Sudoku puzzle using logical reasoning only.
not use or simulate any external code, algorithms, automated Instead, apply human-style solving techniques such as lone singles, hidden singles, naked pairs, naked triples, locked candidates, pointing pairs, X-Wing, Swordfish, XY-Wing, unique rectangles, and other logical strategies typically used by experienced Sudoku solvers. The puzzle is given as a list of 3-digit numbers separated by spaces. Each number represents cell: the first digit is the row (1-9), the second is the column (1-9), and the third is the value (0-9, with meaning empty): {puzzle, _trring Return only the final solution as a list of 3-digit numbers separated by spaces, each indicating row-colum--vllu (e.g., 123 for 1, column 2, value 3), with no extra explanation or formatting.
solvers (e.g., backtracking).
Table 7: Performance of two tate-offthhe-rt LLMs on solving 1,000 Sudoku puzzles (in (Row, Column, Value) format), evaluated by board-level accuracy and average inference time per puzzle. Model Board Accuracy Cell Accuracy Time (sec./puzzle)
GPT-4o
0.00%
27.54%
6.00
Gemini 1.5 Pro
0.00%
44.45%
3.80
Table 8: Performance of three reasoning state-of-the-art LLMs on solving 10 Sudoku puzzles (in (Row, Column, Value) format), evaluated by board-level accuracy and average inference time per puzzle.
Model
Board Accuracy
Cell Accuracy
Time (sec/puzzle)
GPT-o3 mini
0.00%
29.51%
289.80
Gemini-2.. Flash
0.00%
25.19%
245.40
DeepSeck-RR R1
0.00%
31.85%
672.30
C Additional experimental details (Table
Regarding the comparative results in Table 2 the RRN [PWWIS 18] and Recurrent Transformer YIL23 models were originally trained on the RRN dataset. We report their performance on the RRN test set based on the results published in their respective papers. To evaluate these models on additional test sets, we reproduced them using their publicly available code. We also retrained both models on our Random dataset by replacing the original training data with our own.
The Causal Transformer from (SDWP24) was trained on the filtered Kaggle dataset; we report its performance both the Kaggle filtered and RRN test as published their paper. The same holds for KSS++25) where we report their results as published in their work. For the unfiltered Kaggle test set, SDWP24] report the results of the Causal Transformer (SDWP24) in their paper, and we additionally computed the board accuracy on the full 3M dataset.
Regarding our approach, our Transformer-based model builds Andrej Karpathy's open-source minGPT implementation (MIT License, GitHuu Code). All experiments were conducted using PyTorch [PGM+ 19 single NVIDIA A10G GPU.
We trained our model 3M steps (about 168 GPU hours) with a batch size 32 using the AdamW optimizer [KB13]. A linear learning rate schedule was applied: the rate was linearly increased to x 10-1 during the first steps (warmup), then linearly decayed zero over the remaining training steps.
27

---

start
rules end
guess token
dead end
end
Backdoors
135
318
427
318
917
6
731
731
975
116
989
135
318
731
103
103
103
given
rules
scratchpad
(81 tokens)
Causal attention
Full attention
Figure 7: Expanded view the guess node from Figure The guess node implemented as a guess token followed by sequence of 81 thinking tokens (shown in orange), which form the scratchpad. Arrows represent full self-attention within the scratchpad and from the guess token to the thinking tokens. As in previous figures, all tokens attend causally to preceding tokens, but causal attention arrows are omitted for clarity.
Additional details on optimizing guesses
Figure filluserilssstteess our implementation the guess mechanism. We design the guess node of Figure as guess token followed by fixed sequence of 81 thinking lokens, which together form what we call the scratchpud. These thinking tokens correspond one-to-one with the 81 cells of Sudoku board and are assigned fixed positional embedding indices from to 81. Each thinking token is trained to predict the correct value of its corresponding cell (similarly to [YIL2])..
While the rest of the sequence follows standard causal attention, the scratchpad introduces local window of full self-attention: the guess token attends all 81 thinking tokens, and they attend one another. Each scratchpad token also attends causally to all preceding tokens in the sequence, This structure useful for the guessing step, as it allows the model to consider full board solution and base its next guess multiple coordinated cell predictions.
During evaluation, whenever the model outputs the guess token, augment the input sequence by appending the scratchpad tokens, enabling single forward pass with full attention between the guess token and the scratchpad. From this forward pass, we extract the model's output the guess token and use it as the next generated token.
After this step, the scratchpad is removed from the input, and the generation proceeds normally in an autoregressive manner by appending the newly generated token to the existing sequence.
This approach maintains next-tode next-token generation pipeline, while introducing a task taek-fpecific reasoning step the guess token leverage the Transformer's 's prediction power.
E Connection to the MIN-SUM SET COVER problem
We now describe the MIN-SUM SET COVER problem, in the terminology of our work. This models depth-1 search problem where the goal is find which guess would lead valid solution.
In this problem, there are n potential choices one can take but only subset of them are valid. While the exact subset S is unknown, it is known that the subset drawn from a given distribution D. In the simplest variant, it costs time unit to explore any choice and once a choice is made, one directly observes whether that choice goal in this problem is to find a policy æ that explores different options and minimizes the expected time until valid solution is obtained. More formally, defining for every policy and every subset S. T(x) (S) the expected time until a valid choice i E S made under policy æ, we seek to find the best policy that minimizes:
valid not but receives additional information. The
min ESwD [T(m]] [T]]
28

---

In the absence of additional feedback, the best policy takes the form of permutation of all choices 1 to n. For such a permutation x. T(*|S) arg min n s=1
S
Computing the optimal policy given distribution over sets 'D is significantly challenging even if the distribution D is explicitly given. In fact, as (FLT02) show it is NP-hard to approximate the optimal policy better than a factor of 4. Obtaining 4-approximate policy can be done in number of different ways, e.g. via greedy algorithm FLT02 or solving a linear programming relaxation and
performing randomized rounding [TT22].
Theorem E.1 (From (FLT)22). It is NP-hard to compute policy that approximates the optimal by factor better than 4. The greedy policy that always selects the most likely choice conditional on the set not being covered by the choices explored so far is 4-approximate.
We note however, that these policies require heavy optimization and estimating the conditional distribution after several number of choices have already been explored. In contrast, naive methods that directly order choices by the marginal probabilities that the guess is valid are highly suboptimal and may end-up up costing
more than the optimal policy.
Example E.1. Suppose that D simply the set {l...., n 1} with probability 2/3 and the set {n} with probability 1/3.
In such a case, a method based only on the marginals would explore all choices 1 through n 1 before exploring the choice n taking time at least n/3 in expectation. In contrast, the optimal policy expectation.
first explore option and then option n taking time 1 + =
Optimizing over MIN-SUM SET COVER policies is non-trivial and requires customized objectives. To simplify the optimization, we propose restricting focus to a simpler class of policies that are non-adaptive and do not depend the choices made so far. Such policies inherently randomized, and we treat π as a probability distribution over the choices. Every time the policy æ selects choice i with probability कं irrespective of what has been tried so far.
Definition E.1. A policy is called non-adaptive if the choice that it explores every round is independent of the current time t and choices explored up to time t.
Evaluating the expected time until a valid choice is identified takes a simple form. At any time step, the probability that valid choice is taken is ((S) Eies me. Therefore the expected time T(x|S)= Eies
We thus seck to minimize
ESnD
(1)
Eies Tr.
This gives a natural loss function capturing the time to make a valid choice which is convex optimization problem over the convex space of probability distributions over elements A(n) & {i E 1] Σ ग. = }} and can thus be solved efficienlly with stochastic gradient descent (SGD). To see this, note that the function 1/x is convex when x > O, and thus E is convex as a composition of a convex function with linear function and the overall loss is convex as an expectation convex functions.
Restricting over non-adaptive policies may come at a cost as some choices may be explored multiple times increasing the time until solution is found. However, the following theorem that we establish guarantees that the total time of the optimal non-adaptive policy is at most (logn) times that of the optimal permutation.
Theorem E.2. For any distribution over sets S C [n], holds that for any permutation
min ESnD TEA(R)
< H ESND arg min(mi $}
EiES T
where H, = =1=
O(log n) is the n-th harmonic number.
29

---

Proof. Fix permutation and let be the probability that random S D is covered in exactly i steps. The cost of permutation i.c. EsnD [arg m S} given by Σi=1 9: 4.22
Without loss of generality assume that T2 = i. Now consider a non-adaptive policy æ that sets the probability क, v i.e. n,
Ei=1 v95
now have that
1
ESnD
EiEs TT.
Σ9
q: T
Σ
v
v
where the inequality follows from the fact that the q: Iz-fraction of sets S that are covered in steps according to 7 must contain the element
To complete the proof we need show that (E== V 1 iq.) which follows from the Cauchy-Schie Shuuhy-Schwartz inequality on the sequences = Viq; and b; Vi'
Remark E.1. Using the loss function of Equation Q results solutions with bounded approximation to the optimal policy. In contrast, if one treats the problem as multi-class classification task and attempts to use loss function such as weighted Cross Eots--yy Loss
1
EsnD
0s
log iES
Ti
the approximation would be much worse. This is because the Cross-Entropy loss can be rewritten entirely as function depending only on the marginals E; 3r log 1 for some given weights B, and as we established in Example E.1 this leads paying a linear multiplier in the total expected time.
n. for
E.1 From Sudoku to contextual MIN-SUM SET COVER problem
Mapping: the choices are the moves to be suggested as backdoors, and the goal is to efficiently figure out which backdoor given as hint would result in a correct solution.
While the above analysis considers a fixed distribution over sets, in our setting we wish exploit information about the instance to quickly pin-down the correct choice. While in our setting there is no stochasticity as all information about which choices would lead to solutions is directly encoded in the initial state, such mapping may be very incompressible and may not be representable even by large NNs. As such stochasticity arises due to this loss of information. We can thus view the problem as generalization of MIN-SUM SET COVER where the current state is given as a context F and the goal is to learn a mapping from context to a search policy (distribution over choices). this generalization,
given distribution D over contexts 5 IR and sets S C [ni] class II of contextual policies IRd An)) and we seek to minimize:
min E (( [T((()))S) #EN
the class contained all linear mappings i.e. π = Ax, the loss function presented Equation would remain convex function of the entries of and one can again optimize it via SGD. In general, we apply our method over mappings given by complex NNs and Transformers so optimality not-guaranteed but hopefully can converge to good local minima.
What is guaranteed however, is that as long as every choice gets assigned non-trivial probability of being selected will eventually arrive at a solution.
E.2 Multiple-levels of guessing
Our discussion so far focused on single level of guessing which corresponded to MIN-SUM SET COVER. One can define a generalization of the problem on arbitrary trees. We can still consider randomized non-adaptive policies as performing random walks the tree until a node that corresponds to a valid solution is reached. Optimizing over non-adaptive policies would boil down to estimating the transition probabilities of (absorbing) Markoy Chain so that the time to solution (time absorption) is minimized.
30

---

While this is a very interesting extension to explore both theoretically and experimentally, this comes with additional challenges that were of scope of the current work. We plan to do explore them however in future work.
F Libraries of data generators
F.1 SudokuPy: a fast Sudoku puzzle generator
In this section, we introduce SudokuPy; a fast Python library, primarily implemented in C, that generates uniformly random Sudoku puzzles in principled way from the full distribution of valid Sudoku grids. For combinatorial problems like Sudoku, it is essential to generate diverse, truly random instances rather than rely on static datasets, allowing stream-like training and avoiding overfitting issues every puzzle is only the-fly generation of puzzles along with their corresponding solutions, making particularly suitable for large-scale data generation and advanced AI training for standardized benchmarks in research. The library ensures principled and efficient puzzle generation by sampling from the full distribution of valid grids using precomputed permutation tables and optimized indexing. It includes high- performance C-based solver to validate and generate puzzles, significantly improving computational speed. SudokuPy be installed the Python package sudokupy. It is distributed under the MIT License, ensuring free accessibility, and the distribution can also be reproduced following the description below.
once. SudokuPy addresses this need by enabling on-
The core functionality of our generator is described and illustrated in Figure g In this figure, the input to our library function is shown in blue: the number P. which specifies how many Sudoku puzzles to generate. The output highlighted in green and labeled S; it represents the generated Sudoku puzzles.
The process starts by generating a uniformly random number between and 0,000,7722022,072,9666666,,
which corresponds to the total number of valid Sudoku puzzles. This number is then mapped to fully solved Sudoku board using precomputed permutation tables and the functions board_encood and board_decood which together form one-to-one mapping. the next stage, the generator gradually removes numbers from the completed board using the still has a unique solution by calling the puzzle
function. After each removal, the generator verifies that the puzzle sorzze__soveel solver function. While puzzle_genee -enerattor handles the random deletion of entries, puzzle e_solver ensures that the puzzle remains valid. The puzzle_sol ver is C-based function integrated with our package, ensuring high performance even on systems lacking a native C compiler. For user convenience, we provide the black-box function named as sudokupy boookupyggenae generator, which takes an integer as input and returns that many random Sudoku puzzles along with their corresponding solutions.
SudokuPy
Process of Generating Random Sudoku
board encode
puzzle generator
uniform
P
Permutation Table
Filled Sudoku Board
Unfilled Sudoku Board
board decode
puzzle solver
sudokupy generator
Figure 8: Main process and features of the uniform Sudoku puzzle generator, SudokuPy
31

---

F.2 Transcripts library
The Transcripts library is primarily implemented in C, and can be installed and used as Python package. It provides transcripts for wide range of problems, including Sudoku and 1-in-3 SAT problem which are used in this work. automatically supports any combinatorial problem as long as the user can implement the following functions.
// Generate (random) problem instance Problem generate_instant Caeeanceeeeeeeeee (GeneratorParametar *parama);
// Given problem instance encodes into tokens int problem_tokens (Problem *p, int *tokens);
// Provides the initial partial solution to the problem Potentially empty.
PartialSolution initial. (Proolln *p);
// The tokens corresponding to valid guess actions int guess_next__ookes (Partialslatt *s, Problem *p, int #tokens);
IfIf If a guess fails, provide the alternative tokens to try next. (int guess_token, PartialSolution *s, Problem *p, int *tokens);
int
// Find the action tokens according logic rules int nogic_next_tokent (PartialSolution *s, Problem *p, int *tokens);
// Given partial solution obtains new partial solution by applying the given action token PartialSolution (oply_toeenPaartaalaaa token);
*s, Problem *p,
// Checks if the solution is complete whether errors exist int is_comeeete (PartialSolution *8, Problem +p);
The transcripts library uses this interface to run DFS search on top of the partial solutions the prob- lem and provides complete transcripts along with multi-targets for the corresponding combinatorial problem.
G 1-in-3 SAT problem
Definition. Given N Boolean variables , and a Boolean formula á with M clauses in 3-Conjunctive Normal Form
C A CMr, where C. (fa v l22 V C2a),
and each literal kij E {Æx, - the 1-in-3 SAT problem asks for truth assignment to the N variables such that exactly one literal in each clause is true.
Instance generation. We use the following concrete process for generating 1-in-3 SAT instances that is popular in the literature. Starting from random assignment for the variables, we create random clause using 3 random literals on distinct variables and reject if the clause is not satisfied by exactly literal. We repeat this process until m clauses are selected. contrast the Sudoku task, this is not guaranteed to have unique solution but as the initial chosen assignment is solution is guaranteed to be solvable.
Transcript generation. To generate the transcript, we make guesses by assigning value to
random variable. We also apply the following logic rules to figure out additional assignments possible:
Positive inference. If clause has literal that was fixed be positive, the remaining two literals must be negative.
32

---

Negative inference. If a clause has a literal that was fixed to be negative, the other two literals must have different values. While this does not give us new value, allows replacing. instances of one literal with the negation of the other. Combined with the following rule this lets us infer additional assignments.
Same variable inference. If a clause contains variable twice, the value of the other literal is automatically determined. If the variable appears with opposite signs, the other literal must be negative while if appears with the same sign, the other literal must be positive and the literals corresponding to the variable r must be negative.
We generate the transcript by applying the above rules whenever possible and make guess if no additional assignment can be inferred.
Example of 1-in-3 SAT transeript with N 25 and M 15 is provided below.
(14, -13, 24), (18, -5, -12), (7, -10, -4), (15, 5, -11)
(-3, -21, -25), (25, -13, -11), (-17, -7, -8), (12, 1, -16),
(-22, 18, -24), (-8, 19, -17), (-6, 8, -24), (-3, 2, -1),
(21, -22, -15), (8, 14, -4), (23, -22, -20), 8, r,
L1, 4, r,
-1, 5, 22, 11, -15, -2, 16, -21, 24, 13, 25, -14, 6, 8, r, L3, -17, -19, 7, 10, r,
L2, 18, 12,
L4, -9, I,
L5, 20,
L6, 23, I, 6
Metric. We evaluate the performance in terms of board accuracy, as Sudoku. In this case, board is correct if all the clauses have exactly one satisfied literal.
Results. In the 1-in-3 SAT problem for N 25 and M 15 we achieve 99.10% board accuracy. During evaluation, for each variable we keep the last assigned value in the generated sequence.
33


Reviews:
[{"review_id": "lPNggQ1GQs", "reviewer": "Reviewer_8BxY", "summary": "This paper presents a framework to teach Transformers to solve combinatorial problems, using Sudoku as the primary testbed. The method combines imitation learning (of simple rule-based logic) with search, using Depth First Search informed guessing and backtracking. The authors introduce action-level tokenization and multi-target training strategy, achieving 99% accuracy on Sudoku and generalizing to 1-in-3 SAT which is an NP hard problem. The second contribution is a theoretical and empirical analysis of minimizing solution length by formulating the guessing optimization as a contextual Min-Sum Set Cover problem, resulting in a new loss function that outperforms baseline cross-entropy loss.", "questions": "How does the proposed framework perform on Sudoku-Bench?\n\nThe DFS-based backtracking search is hard to scale. How does the model perform on larger Sudoku grids or harder SAT variants? Are there known scalability bottlenecks? Is there any further optimization needed? \n\nHave the authors studied the impact of allowing deeper DFS (beyond depth-1)? What is the trade-off in performance and runtime?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "1) The proposed method is well designed, clearly described, and simple.\n2) This paper explores the use of LLMs for combinatorial reasoning, showing that trial-and-error with backtracking can be learned effectively.\n3) The reframing of guessing optimization as a contextual Min-Sum Set Cover problem (and the new loss function as a result) is interesting.\n\nWeakness:\n1) The DFS-based backtracking search may not scale to harder combinatorial problems or larger sizes without further optimization. Authors didn't discuss the possible solutions to address problem size.\n\n2) Evaluation is only limited to Sudoku and 1-in-3 SAT. The paper claims the effectiveness of using the method on general NP problems, but fails to provide more evaluations to support this claim. \n\n3) This paper has missed discussing and comparing important related work such as: \"Neural Combinatorial Optimization with Reinforcement Learning\" Bello et al., 2016 and the many follow up works that came out afterwards.\n\nOverall, The DFS-based backtracking search is an effective way to solve general NP problems, however, the scalability of the method on larger problems is challenging. This paper presented a way to integrate imitation learning of simple rule-based logic with Depth First Search (DFS) informed guessing and backtracking. The proposed optimization framework is limited to depth-1 in DFS and non-adaptive guessing. This will limit the application of this work on general NP problems. Moreover, the paper claimed to be effective to solve general NP problems, but failed to provide diverse evaluation to support this claim.", "was_revised": true, "final_justification": "Thanks for clarification. I will raise the score", "rebuttal": "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:\n1) 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.\n    \n    Once we realize that Transformers, are capable of reliably solving hard combinatorial problems, we also realize that doing it efficiently is paramount.\n    \n    The key advantage of our framework is the integration of clever guessing (see Figures 2 and 5). \n    \n    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.\n\n    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).\n\n2) 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.\n    \n    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. \n\n    Our framework has essentially 3 components that are learnable by a transformer. Solution generation, Solution verification and Guess generation (Hints).\n\n    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.\n\n    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\n    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.\n    \n   \n3) We are familiar with the work of Bello et al. (2016) and follow-up works and will add a short discussion in the paper.\n    \n4) 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.\n    \n\n5) Thank you for your question regarding the depth of guesses.\n    \n    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.\n\n    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.\n\n\nWe 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."}, {"review_id": "kGrb7AHUkv", "reviewer": "Reviewer_stHu", "summary": "A new strategy to tackle NP problems using transformers is proposed (exemplified by the classic Sudoku puzzle) - without external tools or code. The training and operation of the model is in 2 phases: learning basic Sudoku rules via imitation learning, and learning to guess cell values efficiently via a depth-first search - eventually getting to single-guess solution flows. A generator for Sudoku puzzles in a uniform distribution - for training and testing - is developed and published.\n\nThe new method is applied to several test datasets - achieving SOTA results.", "questions": "Line 141: The oracle is the same system that generated solutions for the imitation training stage? If so, I’m not sure I understand how we know that its solutions are optimal - or how close to optimal they are? It’s still a strong result if the transformer outperforms the training data substantially - just not clear how to attribute it specifically to the “backdoor guess” step.\n\nFigure 3 - if the r,c,v representation counts each step as 3 tokens, so the number of actual steps seen by the model is 3 times lower - yet achieves similar (even if slightly lower) results? I probably misunderstood something.\n\nLine 293: Is the “backdoor property” a known feature of Sudoku? Is it an empirical observation based on your generation of training data?\n\nHave you tried experimenting with a hybrid approach: apply the rules deterministically + train the model to guess only once the simple logic code gets stuck? Presumably it would lower the required training set, perhaps significantly, and leverage the strength of each part.\nThis can better separate the 2 functionalities that the model learns simultaneously.\n\nHave you tried rephrasing the training setting (and loss) in terms of standard RL metrics? The “moves” of the game are the guess steps, the reward (win/lose) is simply whether the board reaches an “e” or a “d”.\nThis is not mandatory of course - just seems to me like a more natural setting than learning transcripts of solutions.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nA solid work - in terms of engineering, experimental design, simplicity of approach, and efficiency.\n\nWell written and clearly explained (even if a few concepts in the intro become clear only later on), with high quality figures 2 and 5.\nSOTA on Sudoku benchmarks. \n\nPotentially applicable to a wide range of puzzles and mathematical challenges - even broader than the authors mention explicitly.\n\nWeaknesses:\n\nThe way I understood the system, there are 2 main parts: teaching the transformer the 4 basic Sudoku rules - imitating a deterministic algorithm - and teaching to make good guesses, specifically such that a single guess will bring to a full solution. While the second part can naturally leverage the flexible nature of networks, the first part seems more like a test of the tokenization and dataset generation choices - not a use case that would naturally benefit from DL.\n\nThe authors apply their method to other NP satisfiability problems to show generalization - specifically to 1-in-3 SAT, but it is only stated in the main paper - no details or description given. The information is in Appendix G (incorrectly called H in line 176).\n\nWhile LLMs are mentioned as motivation and potential impact of the paper (both in the intro and summary), this system resembles more an RL setting, or maybe action/time series data. I believe this approach is useful even without connection to LLMs (there are many transformer systems that have nothing to do with natural language) - but the claim should either be strengthened or removed.\n\n---\n\nLine 155: *in\n\nLine 310: “that the L1 is theoretically” - “the” should be removed.", "was_revised": true, "final_justification": "This is a technically robust and well written work, potentially applicable to a variety of \"hash-like\" problems.\n\nThe main strength in my view is the rigorous testing.\n\nI maintain my original recommendation to accept.", "rebuttal": "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:\n1) 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.\n\n    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.\n\n2) 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.\n    \n3) We have corrected the typos mentioned.\n    \n4) Sorry for the confusion regarding the oracle terminology and we will clarify further in the paper to make it clear.\n    \n    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. \n    \n    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. \n\n    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.\n\n5) 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. \n   \n6) 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.\n    \n    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.\n    \n7) 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.\n\nWe 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."}, {"review_id": "Fm884fFRST", "reviewer": "Reviewer_ekMH", "summary": "The paper presents a framework for solving combinatorial problems such as Sudoku using a standard decoder-only Transformer model. The key innovation lies in combining supervised imitation learning of basic Sudoku rules with a trial-and-error Depth-First Search (DFS) strategy. This enables the model to make informed guesses, backtrack when encountering conflicts, and eventually solve problems that cannot be addressed by heuristic rule application alone. Additionally, the paper introduces a novel loss function inspired by the Min-Sum Set Cover problem to optimize inference efficiency. The proposed method achieves near-perfect accuracy (99%) on Sudoku and 1-in-3 SAT tasks, outperforming prior neural and neuro-symbolic baselines.", "questions": "- What exactly is supervised imitation learning in your setup? A concise explanation would be helpful for readers unfamiliar with this technique.\n- What optimiser, GPU type, and training time (in GPU hours) were used? Reproducibility would benefit from detailed training settings.\n- The algorithm starting from the line 214 seems to be the main contribution. While the generation of training transcripts is explained, how exactly is this used during training and inference? What is the architecture of the network that takes these transcripts and learns from them?\n- How does the algorithm described around line 214 differ from that of the Causal Transformer? Based on your explanation, the main differences seem to be: (1) using 4 inference rules instead of 7, (2) using a more compact encoding by removing commas between row, column, and value triplets, and (3) adopting a multiple next-token prediction loss. Are there any other differences? Given that the Causal Transformer is a key baseline, the paper should explain this comparison more clearly.\n- In Table 2, why is there no test result for Causal Transformer on the Random dataset? Is it infeasible to evaluate?\n- In Table 2, is the Causal Transformer trained on the Kaggle filtered dataset only? It would be important to determine whether the performance gain of your model is due to the dataset change during training or the proposed methods in Section 2. An ablation study is needed to identify which factors contributed most to the performance improvement.\n- What do the terms “lower bound” and “upper bound” in Figure 6 represent? Is the lower bound equivalent to the “ours” model described in Section 2? The upper bound seems to assume access to the correct values of the remaining cells, functioning as an oracle. In that case, what does “guess” mean when the correct values are already known? Does it refer to steps where none of the four Sudoku rules can definitively determine the next number?\n- The paper’s approach to forward guessing and backtracking in Sudoku closely resembles the DPLL algorithm used in SAT solving. In DPLL, deterministic rules are applied until no further progress is possible, then a guess is made; if a contradiction arises, the process backtracks. A notable extension is CDCL (Conflict-Driven Clause Learning), which learns from conflicts to avoid similar mistakes. Adopting such strategies could help extend this method to more general NP-class problems.", "limitations": "This paper presents a framework that combines symbolic reasoning with Transformer-based learning in a novel way. Its success on Sudoku shows promise. However, the paper would benefit greatly from improved clarity in technical exposition, more extensive discussion of generalisability to broader NP tasks and general-purpose natural language processing, and inclusion of relevant related work in SAT-solving and symbolic learning in LLMs. If these areas are addressed, this work is likely to make a meaningful contribution to the field of combinatorial reasoning with language models.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n---\n- The model leverages a pure Transformer architecture (GPT-2 variant) without requiring architectural modifications or external solvers.\n- The model achieves 99% accuracy on standard Sudoku, demonstrating strong reasoning ability.\n- The authors provide a custom C-based puzzle generator and training transcript generator to support large-scale evaluation and reproducibility.\n- The authors demonstrate fair comparisons across multiple datasets and training regimes (Kaggle, RRN, Random) in their experiments.\n\nWeaknesses\n---\n- **Length and Structure of Introduction**: The introduction is overly long and merges motivation, background, and methodology. This impairs clarity about the specific contributions. Reorganising the content (e.g., by moving methodology details to a separate section) would improve readability.\n- **Lack of Training/Inference Time Reporting**: While the motivation includes time-per-puzzle as a crucial factor (Table 1), the paper does not report actual training or inference times, which weakens claims about efficiency.\n- **Insufficient Detail on Generalisation to NP Problems**: While the method is said to be applicable to general NP tasks, concrete explanations on how domain-specific design choices (e.g., tokenisation 111--999, rule application mechanics, backdoors) translate to other problems are not enough. The treatment of the 1-in-3 SAT task is not found in the main text.\n- **Neural Network Specification**: The paper does not clearly explain what inputs the Transformer receives and what outputs it produces. For example, while the transcription format and guess strategy are described, the Transformer input/output format and parameterisation are not fully formalised.\n- **Theoretical Contributions Need Clarification**: In Section 3, the comparison between two loss functions (L1 and L2) is said to be grounded in theory, but the intuitive significance of the findings is underexplained. More discussion of what the results mean practically would help.\n- **LLM Framing and Generalisation**: It remains unclear how this model fits into the LLM paradigm. Unlike general-purpose LLMs that process natural language prompts, this model uses highly structured tokens. The authors should clarify whether the model is applicable to natural language-stated logic puzzles or if its scope is limited to symbolic encodings.\n- **Missing Related Work on SAT Solvers**: The related work focuses heavily on Sudoku solvers. More references with neural SAT solvers (e.g., NeuroSAT, GNN-based approaches) would help understand the work within the broader literature.", "was_revised": true, "final_justification": "I still have some doubts about the applicability of this methodology to general combinatorial problems. While the authors demonstrate high accuracy on the 1-in-3 SAT problem in the appendix, I feel that the discussion in the main text is insufficient to fully support this claim. Specifically, the main text should have included what kind of 1-in-3 SAT instances were used in the experiments, whether they are representative or meaningful, how difficult they are, or whether they were derived from any practically challenging combinatorial problems. Additionally, the proposed contribution seems to be an incremental improvement based on Causal Transformer, so it would be helpful if the authors could better clarify what makes this work sufficiently novel to warrant acceptance.", "rebuttal": "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:\n\n1) 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.\n    \n    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. \n\n    Our framework has essentially 3 components that are learnable by a transformer. Solution generation, Solution verification and Guess generation (Hints).\n\n    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.\n\n    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\n    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.\n\n2) 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.\n\n    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].\n\n3) Thank you for your comments regarding the distinction between our work and the previous Causal Transformer [SDWP24].\n    \n    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.\n    \n    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.\n    \n    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.\n    \n    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.\n\n4) 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. \n    \n    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.\n\n    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.\n    \n5) 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.\n\n6) Sorry for the confusion regarding the oracle terminology and we will clarify further in the paper to make it clear.  \n    \n    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. \n    \n    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. \n\n    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.\n\n    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.\n    \n\n7) 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.\n\n    In our case, the inference time is in the order of milliseconds (while achieving ~99\\% accuracy).\n    \n    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.\n\n8) Thanks for mentioning the SAT solvers related work and DPLL algorithm. We have added relevant references and discussion. \n\n9) 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.\n\n    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.\n\n    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).\n\nWe 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."}, {"review_id": "BdjO5OjlXj", "reviewer": "Reviewer_adCH", "summary": "This paper studies transformer models for combinatorial problems, with a specific focus on NP problems. This has been studied a lot in recent years by the community, as covered in the related works section of the paper. The authors obtain gains of >10% for full solution accuracy using architectures from prior work with their new data generating library, which also allows for test set generation. \n\nThe authors then make three key addtions to obtain another gain of >6% to obtain an accuracy of 99%. Firstly, a method for representing the solving process as a series of discrete actions, secondly allowing the model to learn backtracking through curated training data and finally using a novel loss function which is not one hot to allow for probability of the model to be placed on all correct possible next moves. The change is loss function is backed by both theoretical and empirical results. One empirical validation of this new loss function is in Figure 6 where the new loss function allows more than 80% of puzzles to be solved in fewer guesses than an oracle.", "questions": "1. Is the Deepseek-R1 “Time” in number in table 1 large as it was run locally and all others are run on APIs? Either way, it would be very useful to have exact API references for all models in Table 1.\n\n2. Where would the r,c,v + multiple targets line be on Figure 3 left?\n\n3. Please see weakness 1, on \"additional time/memory taken to train and inference using the new method.\"\n\nDiscussion/progress on weakness 1 is most likely to impact my score.", "limitations": "I would like to see a little more on the limitations of this work compared to specialised/classical SAT solvers.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "# Strengths\n- Strong related works section which places the paper well in context.\n- The introduction and study of a novel loss function for combinatorial problems and new method to train models to learn to backtrack.\n- The promise to open source a new library to make it easier for the community to study NP problems in the future.\n\n# Weaknesses\n\n- There is a lack of discussion on the additional time/memory taken to train and inference using the new method. The authors compare to non-backtracking techniques which should use less tokens/compute to generate their solutions, although these come with the down sides the authors highlight throughout their paper there are other ways to compare to these methods on a FLOPs/output-tokens comparable axis.\n\t- For example, if the new backtracking technique takes twice the compute/tokens then we could run the non-backtracking approaches twice with a non-zero temperature to see if they generate the correct solution either time. One thing to note is that as the multiple attempts can be completed in the batch dimension the exact comparison here is intricate but inference FLOPs or total tokens output could be good options to make comparisons fair. \n\t- Additionally, in Table 1 the authors analyse at reasoning models for Sudoku. A reasonable baseline could be do GRPO directly on sudoku problems, as I believe “Aha movement” in GRPO (https://arxiv.org/pdf/2501.12948) does allow for backtracking.\n\n- It would be nice to contextualise in the conclusions outside of the language modelling community. For example, in the context of how fast traditional SAT solvers are, and highlight the future directions this work allows, highlighting the connection to all NP-Complete problems more directly for non topic specific readers.", "was_revised": true, "final_justification": "## Why not higher\n- I am not sure the paper will have \"groundbreaking impact\" as a 6 requires\n\n## Why not lower\n- I think this paper will have impact on the sub area of AI that sudies what algorithms transformers can learn\n- The evaluation scheme is rigorous and compares multiple models\n- The authors will open source code for reproducibility\n- No unaddressed ethical considerations", "rebuttal": "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.\n1) Thank you for your thoughtful comments regarding the time, memory, and FLOPs considerations.\n\n    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.\n    \n    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.\n    \n    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.\n\n    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.\n\n2) We added additional relevant references and discussion about SAT solvers.\n\n    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).\n\n    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.\n\n3) 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. \n    \n4) 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.\n    \nWe 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."}]

Author rebuttal:

Meta-review: In this paper the authors propose a new framework for solving combinatorial problems such as Sudoku using a standard decoder-only Transformer model. The key idea is to combine supervised imitation learning of basic Sudoku rules with a trial-and-error Depth-First Search (DFS) strategy to make informed guesses and backtrack when encountering conflicts. This leads to solving problems that cannot be addressed by heuristic rule application alone. In addition, the authors design a loss function inspired by the Min-Sum Set Cover problem to optimize inference efficiency. The proposed method achieves near-perfect accuracy (99%) on Sudoku and 1-in-3 SAT tasks, outperforming prior neural and neuro-symbolic baselines.

The key strength of the paper is the fact that they can teach their model to do backtracking. On the other hand, the claims of the paper seems to be a bit of oversell as their work has only been tested on a small set of problems. 

There has been some discrepancy between the authors regarding the novelty and significance of this paper. However, I strongly believe that the backtracking contribution is impressive and therefore it is worth presenting this paper at the conference.
Decision: Accept (poster)