Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
Authors: Yudong Xu
Wenhao Li
Scott Sanner
Elias Boutros Khalil
Venue: ICML 2025 poster (2025)
Keywords: Constraint Satisfaction Problem
Transformer
Self-supervised Learning
Local Search
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: A self-supervised Transformer-based framework for iteratively solving Constraint Satisfaction Problems.

Abstract: We present a Transformer-based framework for Constraint Satisfaction Problems (CSPs). 
CSPs find use in many applications and thus accelerating their solution with machine learning is of wide interest. Most existing approaches rely on supervised learning from feasible solutions or reinforcement learning, paradigms that require either feasible solutions to these NP-Complete CSPs or large training budgets and a complex expert-designed reward signal. To address these challenges, we propose ConsFormer, a self-supervised framework that leverages a Transformer as a solution refiner. ConsFormer constructs a solution to a CSP iteratively in a process that mimics local search. Instead of using feasible solutions as labeled data, we devise differentiable approximations to the discrete constraints of a CSP to guide model training. Our model is trained to improve random assignments for a single step but is deployed iteratively at test time, circumventing the bottlenecks of supervised and reinforcement learning. Experiments on Sudoku, Graph Coloring, Nurse Rostering, and MAXCUT demonstrate that our method can tackle out-of-distribution CSPs simply through additional iterations.

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
Yudong W. Xu
Wenhao Li
Scott Sanner
12 Elias B. Khalil 123
Abstract
straint propagation and backtracking search can be compu- tationally expensive, especially for large problem instances. This has motivated the exploration of learning-based ap- proaches as fast neural heuristics for CSP solving (Dai et al., 2017; Selsam et al., 2019; Bengio et al., 2021).
We present a Transformer-based framework for Constraint Satisfaction Problems (CSPs). CSPs find use in many applications and thus acceler- ating their solution with machine learning is of wide interest. Most existing approaches rely on su- pervised learning from feasible solutions or rein- forcement learning. paradigms that require either feasible solutions to these NP-Complete CSPs or large training budgets and a complex expert- designed reward signal. To address these chal- lenges, propose ConsFormer, self-supervised framework that leverages Transformer as so- lution refiner. ConsFormer constructs solution to a CSP iteratively in a process that mimics lo- cal search. Instead of using feasible solutions as labeled data, we devise differentiable approxima- tions to the discrete constraints of CSP guide model training. Our model is trained to improve random assignments for single step but is de- ployed iteratively at test time, circumventing the bottlenecks of supervised and reinforcement learn- ing. Experiments on Sudoku, Graph Coloring. Nurse Rostering, and MAXCUT demonstrate that our method can tackle -ittt---iittiitti CSPs simply through additional iterations.
Most existing learning -ased methods use either supervised or reinforcement learning (RL). Supervised approaches train models datasets of CSP instances with feasible solutions as labels, a paradigm that is laden with drawbacks. First, generating labels for CSP instances requires solving them, which makes it challenging to generate the large quanti- ties of data often needed to train a model that generalizes well. This is especially true for hard instances that tradi- tional solvers struggle to solve quickly. Second, CSPs often have multiple feasible solutions (Russell & Norvig, 2016), making it difficult to apply supervised learning unambigu- ously when there are many possible labels for the same input. RL-based methods, on the other hand, search for so- lution strategies through black-box optimization of reward function, often requiring extensive computing resources. Designing reward functions that capture solution feasibility across different constraints is difficult yet crucial to success in RL (Arulkumaran et al., 2017). These limitations hinder the generalization and scalability of learned heuristics.
To address these challenges, we introduce ConsFormer, a Transformerrbased self self-supervised framework for solving CSPs. Inspired by Constraint-based Local Search (Hen- tenryck & Michel, 2009), ConsFormer learns iteratively refine variable assignments through self-supervised train- ing paradigm that approximates discrete constraints with continuous differentiable penalty functions. Our model is trained to improve an initial random assignment a single refinement step, but is applied iteratively at test time, While single step may not yield feasible solution, a sufficiently large number of improving iterations (on average) does. Examples of ConsFormer solutions are shown in Figure 1.
1. Introduction
Constraint Satisfaction Problems (CSPs) are fundamental to many real-world applications such as scheduling, plan- ning, and resource management. However, solving CSPs efficiently in practice remains a significant challenge due to their comcleee nature. Traditional solvers based on con-
'Department of Mechanical & Industrial Engineering, Uni- versity of Toronto "Vector Institute for Artificial Intelligence "Saae AI Research Chair in Data-Driven Algorithms for Modern Supply Chains. Correspondence to: Yudong Xu wwx.xu@milluuooooooo
Transformers provide natural fit for this approach due to their strong generalization capabilities and their ability to process structured data efficiently (Lewkowyez et al., 2022; Achiam al., 2023). They are particularly effective at learning with tokenized inputs, making them well-suited for combinatorial problems formulated in the Constraint
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
Random Initial Solution
Iteration
lteration 50
Iteration 500
Iteration 1000
9
9
S
3
3
3
4
2
6
9
S
8
S
1
5
9
3
2
8
7
3
1
1
2
3
9
4
2
7
2
B
3
1
2
4
1
3
4
G
3
3
8
3
C
2
3
1
0
6 2
3
991
4
5
2
3
7
3
4
0
6
9
7
9
1
3
4
5
3
1
5
2
8
4
5
3
6
Single-Step Training
Iterative Test- Test-Time Deployment
Figure 1. Conseormer models construct solutions for Sudoku (Top) and Graph Coloring (Bottom). The models are trained with a single step from randomly initialized assignment. At test time, ConsFormer model is invoked iteratively until feasible solution is found or an itcration limit is met.
Programming paradigm (Rossi et al., 2006). Furthermore, recurrence has been shown enhance the generalization abilities of Transformers (McLeish et al., 2024; Fan et al., 2025), reinforcing their suitability for our setting.
instances and achieves state-of of-the- art results for generalizing to OOD tasks in Sudoku, outperforming all existing neural methods.
Our iterative solution improvement strategy enables Cons- Former generalize beyond its training distribution, ef- fectively solving -uito--distribution (OOD) CSP instances simply by performing more refinement steps. We evaluate ConsFormer on diverse set of CSP problems, including Sudoku, Graph Coloring, and Nurse Scheduling, demon- strating its ability to generalize across problem domains. Our implementation is available on GitHub'.
2. Background
2.1. Constraint Satisfaction and Programming
A Constraint Satisfaction Problem (CSP) is a mathematical model used to represent problems that involve finding val- ues for set of variables subject (possibly discrete and non-linear) constraints. Formally, a CSP is defined as tu- ple (X, D, C), where X = {x1, .., In is finite set of variables, D = {D1, D2..... Da), D; C Vi E [n] represents the discrete domains of these variables, and C= fc,, ,..,, is the set of constraints, where each constraint e; is defined over subset of variables X; C X, restricting the values that can be simultaneously assigned to them. The goal in solving CSP is to assign to each variable value from its domain such that all constraints in C' are satisfied.
The following high-level findings summarize our work:
Self-supervised learning can be applied to solve CSPs. We show that loss function that combines differentiable penalties for the violation of the discrete constraints of a CSP can guide model training without the need for labels.
Decision variable positional information key for Transformer learning. We show that by represent- ing variable positional information as absolute and relational positional encodings in the Transformer, we enable solution improvement in variable space.
Constraint Programming (CP) (Rossi et al., 2006) is the study of mathematical models and solution algo- rithms for CSPs. CP uses highly expressive global con- straints (Beldiceanu et al., 2005) that involve multiple vari- ables and are designed to capture common constraint struc- tures that appear in a wide range of real-world applications. One prominent example of global constraint is the AL.LD- IFFERENT constraint (Régin, 1994), which ensures that a subset of the variables take on distinct values.
ConsFormer can generalize when trained per- form solution improvement. While trained to perform single improvement step, ConsFormer generalizes to
'https://e / ttt.gttthhhh.ggggggggggg com kha ill rresearchh Consorrmer
2

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
2.2. Related Work
successfully applied in continuous domains (Donti al.; Park & Van Hentenryck, 2023), as well as for SAT (Ozolins et al., 2022).
Constraint solving with supervised learning. Super- vised learning has been extensively applied to constraint solving. For example, Pointer Networks (Vinyals et al., 2015) are used for the sequential generation of combinato- rial problems involving permutations such as the traveling salesperson problem. Palm et al. (2018) propose a graph- based recurrent network to model CSPs, effectively leverag- ing the graph structure to refine variable assignments iter- atively. SATNet (Wang et al., 2019) differentiates through semidefinite programming relaxations in supervised set- ting to handle logical constraints. Du et al. (2024) introduce method for iterative reasoning through energy diffusion, focusing on progressive refinement of solutions. More re- cently, Yang et al. (2023) proposed a recurrent Transformer architecture that reuses the same Transformer weights across multiple steps, iteratively refining inputs before projecting them to the final outputs. The common drawback for su- pervised approaches is the need for labels, which is not easy to generate for many large CSP problems. Addition- ally, for problems with more than one unique solution, label generation becomes non-trivial.
Continuous relaxation of discrete functions. Continu- ous relaxations have been used effectively to approximate discrete functions. For example, T-norm has been widely implemented as continuous approximation for discrete bi- nary logic operations (Petersen et al., 2022; Giannini et al., 2023; Gimelfarb et al., 2024). Petersen et al. (2021) intro- duced continuous relaxations for discrete algorithms, such as if-statements and while-loops. Combinatorial constraints have also been approximated using entropy-base -ased relax- ations (Chen et al., 2019), probabilistic methods (Karalias & Loukas, 2020; Bu et al., 2024), and set function exten- sions (Karalias et al., 2022).
Recurrency for generalization. The incorporation of re- currency has been shown to improve a model's general- ization. Bansal et al. (2022) implement recurrent ResNet blocks to solve simple logic puzzles and show that in- creasing recurrent steps at test-time allows generalization to harder unseen tasks. Recurrency was introduced to the Transformer architecture by sharing weights across Transformer layers (Dehghani et al., 2019; Takase & Kiy- ono, 2023), yielding improved generalization capabilities on arithmetic and logic-based string manipulation tasks (McLeish et al., 2024; Fan et al., 2025). Our method dif- fers from the existing work as recurrency is only introduced during test-time deployment.
Constraint solving without labels. A common recipe for Reinforcement Learning (RL) in constraint solving is to express the problem with a graph which is then processed using Graph Neural Networks (GNN). The GNN's weights are updated using RL based on reward function express- ing an objective function and/or constraint satisfaction (Dai et al., 2017; Chalumeau et al., 2021; Li et al., 2024; Boisvert et al., 2024). For example, Tönshoff et al. (2023) converts a CSP instance into tripartite prrfable-domaai-ccosttiinn graph which is then solved using a GNN trained by RL. Similarly, Yolcu & Póczos (2019) represent SAT problems using a clause-variable variable graph. Wu et al. (2022) use a Trans- former architecture to learn discrete transformation steps with RI. for routing problems. However, RI. approaches require significant computational resources for training, as well as an expertly designed reward signal for each problem.
3. ConsFormer: a Single-Step Self-Supervieed Transformer
We introduce ConsFormer, a single-step Transformer trained with self-supervision. Given an assignment of values to vari- ables (hereafter referred to as variable assignment), Cons- Former attempts to generate a refined variable assignment that is closer to satisfying the constraints of the input CSP. An overview of our model is shown in Figure 2.
Non-RI. based methods require addressing the non-
Section 3. presents Transformer representa- tion of variable assignments. Section 3.2 details the Trans- former design and how it generates an updated assignment. Section 3.3 focuses on the self supeesuper training process. Finally, Section 3.4 discusses how the model, trained for single-step solution refinement, can be deployed iteratively at test time to solve CSPs.
differentiability of discrete constraints. Yang et al. (2022) use the straight-through estimator (Bengio et al., 2013) for logical constraints and Tang et al. (2024) explore similar approach for mixed-integer non-linear programs. Toenshoff et al. (2021) devise a continuous relaxation for binary con- straints (i.e.. constraints involving two variables) which are used to guide a recurrent GNN to generate solutions; this approach is limited in applicability as many CSPs of interest have non-binar mon-binary constraints. Bai et al. (2021) design contin- uous relaxations for some constraint classes in conjunction with a reconstruction loss to tackle a visual Sudoku prob- lem: it is unclear how their architecture can be adapted to CSP solving in general. Sele-iupe learning has been
3.1. Input Representation
The input to the model includes the current variable assign- ment (which may be infeasible), variable indices, and a binary relational constraint graph indicating the participa- tion of a variable constraint. We adapt the Transformer
3

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
e(2) 1
Iterative Test-time Deployment
e(1) + [112
+ Cyy
e(1) [1
e(9) + c
e(9)
6
Multi-head Self Attention
Add & Norm
Feed Forward
Add & Norm
8
(
e
e(4)
e(2) 11
e3)
e(3)
L
x
Binary
Self Supervupee Loss
Constraint Graph
Figure 2. ConsFormer: a Single-Step Self-Supervised Transformer for CSP A CSP instance is transformed into a set of input embeddings composed of the variable assignment value encoding, index-based Absolute Position Encoding, and selected update set embedding indicating the variables to be updated. The input is processed by L Transformer layers, incorporating the binary constraint graph as Relative Positional Encodings for attention. The output values are used to update the variable assignments which are then used to compute a diffcrentiable self- seff-super loss on constraint violation. Although trained to perform one step of solution improvement, ConsFormer can deployed iteratively at test time, improving the odds of solving instances never seen during training.
architecture to process a CSP instance by encoding these elements as follows.
Constraint relations as Relative Positional Encoding. A Relative Positional Encoding (RPE) is typically used by Transformers to capture the positional relationship between tokens independently of their absolute positions in se- quence. For CSPs, lationships between variables. Specifically, we represent the CSP constraints as a binary constraint graph G = (V, E), where V = {1,22.... n.} corresponds to the variables and contains edges between pairs of variables that participate together in least one constraint of the CSP.
Variable assignments
tokens. Let X (21.:2)....5aa) be the set of variables in CSP, each of which has finite domain D;. A variable assignment 2; U. E D,, is treated as a token. A learnable embedding e(v) is assigned to each unique value E Uh_, D.. The input variable assignment, represented as = 1 = UI, 22 = 02,.... In = un J. forms the input token set to the Transformer. Thus, the input embedding set given by
RPE to encode the constraint re-
The RPE is incorporated into the attention mechanism by modifying the attention logits. Let Aij denote the attention logit between variables and j. The modified logits are computed as:
E = ((1)) e(c,)}-
(1)
In this paper, focus problems where all variables share the same domain D.
Ai = Aij + RPE(i,)),
Representing variable indices with Absolute Positional Encoding. Transformers use Absolute Positional Encoding (APE) to represent the position of tokens in a sequence. For CSPs, we use APE encode the indices of variables. the indices of variable x; are multi-dimensional, we concate- nate the positional encodings for each dimension. Specif- ically, let Pa..ii denote variable with k-dimensional indices (d1, puted as:
where
RPE(i.)) = c- c- & E),
(3)
and e S 0 is either constant hyperparameter learned parameter. Setting to effectively masks the attention between variables that do not have any constraints in com- mon. The inclusion of the constraint graph via the RPE helps the model identify variable pairs that have strong effect on each other's a
The APE for this variable is com-
APE(T ( Concat(PE(()), PE( ... PE(ix)), (2)
assignments.
where PE(ik) is the positional encoding for dimension k. For example, in Sudoku, a variable æ2 would have an APE formed by concatenating the encodings for row and col- umn 2. This approach is inspired by the APE design in Vision Transformers (Carion al., 2020; Li et al., 2025).
3.2. Single-Step Transformer Architecture
Our model takes the inputs described the previous section and outputs new variable assignment. Below, we outline the key components of the Transformer architecture.

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
Variable subset selection. Inspired by the local search principle, we posit that small modifications to variable assignment are preferable as is easier to assess their impact on constraint satisfaction. Our model essentially performs a stochastic local search by randomly selecting a subset C X of the variables to update. We do this by flipping a biased coin with probability of selection p for each variable, where p a hyperparameter. A special learned embedding C, is added to the variables in S. The Transformer's output for the variables in S' is used to update the assignment; variables not in S take on the same values as in the input variable assignment. The input to the first Transformer block for a variable z; is given by:
Feedforward network and layer stacking. The output of the self-attention mechanism 2; is passed through position- wise feedforward network (FFN):
h 111) = (F:( = W2(GeLLU(W12, bb)) + b2,
where W1. W2 b1, and b2 are learnable parameters. The Transformer consists of multiple such layers.
Output: one-hot variable assignments. At the final layer, the Transformer outputs a one-hot vector over the domain D; of each variable in the subset S, representing its new assignment. Specifically, for variable Ii the output is:
h h c(u:) + B. APE(x;) +y.0, c, I[2; S), (4)
y: = GumbelSoftmax WWon W ( + bou
where e(v;) is the token embedding of variable r current value o; described in Equation (I), and APB(x;) is its positional encoding as computed in Equation (2). ar, 3, are learnable scalars that allow the model to balance the contributions of each encoding, inspired by Li et al. (2025). The set of embeddings for all variables forms the input set ()) = [h, h h.. )
where 1 = D.). W and bout are learnable, and L is the number of Transformer layers. The Gumbel-Softmax (Jang et al., 2017) operator serves as differentiable proxy to selecting the highest-output domain value. The predicted assignment for I; then:
o = arg max
Vi E S.
We note that this allows for easy handling of problems where certain variables have fixed values, such as in Sudoku. We simply bypass the variable subset selection step for the fixed variables, ensuring they are never updated by ConsFormer.
3.3. Self-supervised Loss Function
How should the Transformer learn to refine input vari- able assignment into better one? In the CSP context, the loss function must reflect the level of constraint satisfaction achieved by the predicted assignment. As argued earlier, one could use a supervised approach in which feasible solution is first computed for each training CSP and a loss function measuring the tariable-wise mismatch between the prediction and the solution is used. However, this approach hinges on solving many NP-Complete CSPs, a substantial overhead for large and complex problems. Additionally, there may be multiple feasible solutions, making supervi- sion by a single solution somewhat arbitrary. Alternatively, our Transformer could be trained by RL, with the reward function reflecting the level of constraint satisfaction. We argue that this is unnecessarily complicated. An input CSP instance is fully observable is the amount of violation of a constraint for any given variable assignment. Treating this violation signal as part of a reward function given by a black-bor box "environment" thus overkill. Should we be able to derive differentiable approximations to the constraints, their violations could be used directly in a loss function, enabling end-to-end differentiable training.
ConsFormer employs multi-head self- attention mechanism to compute updated representations of variables based on other variables. For each variable token (0) E R 1 at layer 1, the self-attention mechanism for a single attention head proceeds as follows:
Self-attention.
h
Each input token is projected to query, key, and value vectors:
whn, where We E Rdxh, W E Rdxh, and w E Rd are learnable weight matrices.
q: = ! k; = hh
The relative positional encoding R) as described in Equation (3) is added to the attention logits Ay:
A, 9: k :)
The attention weights are computed using softmax:
exp(Ais)
Oij = Σ KES exp(A
With these design principles in mind, we train our Trans- former using self-supervision. As our loss function, we use a linear combination of approximations to the amount of constraint violations by the predicted variable assignment to guide the model towards a satisficing predicted assignment.
The output representation for token i is computed as:
2: = Σ VsyVy-
JES
5

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
Table Discrete constraints used in our studied problems and their continuous penalty counterparts. In the continuous penalties, the variables z; represented by probability distributions approximating their one-hot form such that x. E [0. 1] Vj [I...., m), where (1.....m) m) represents the domain D, Numerical examples for each constraint can be found in Appendix A.
Discrete Constraint (c)
Continuous Penalty (p)
CARDINALITY (T1,,..... Fn) =
k:
Σ
i=1
Explanation: The cardinality constraint ensures that there are exactly variables taking the value j. The continuous relaxation penalizes the deviation from the desired count
Σj=1 (1-E
ALLDIFFERNTTm=1(12 2pn)
Explanation: The all-different constraint ensures that each variable takes unique value. When the number variables equals the domain size m, the all-different constraint can be rewritten as cardinality constraints restricting the cardinality of every value in the domain to be 1.
Σ ReLUU (Ei= - -1) +-1++E -1)+ + 1 ( (II - = D]
ALLDIFFERENT m
Explanation: When there are more domain values than variables, each value should appear no more than once. This enforced by ensuring values above are penalized and values remain in the set {0,
(x
It Zk
Explanation: This constraint ensures that variables take different values by penalizing overlapping one-hot encodings. The continuous relaxation takes the dot product of the two variables, penalizing it if it is above O.
However, many constraints in CSP are discrete and not dif- ferentiable. To address this, we introduce simple continuous penalties that approximate discrete constraints, which are then used to compute the loss for guiding the model. Let p (pi, ......, pm be the set of continuous penalties approximating constraints C {C1, C2,......... .... Cm such that
3.4. Iterative Test-Time Deployment
Another issue with RL is its multi-step nature which requires exploring an extremely large space of iterative solution re- finement sequences. We show that learning a single-step solution refiner with self-supervision suffices as the model can be be deployed iteratively at test time. More specifi- cally, our method refines an initial solution by repeatedly feeding its output variable assignment back as input to the next iteration as visualized in Figure 2.
(x.) =0 + (X,)) = True,
implying that X is feasible solution for the CSP when
In this sense, ConsFormer can be viewed as performing single step of neural local search to improve the candi- date solution. Our experiments focus on basic iterative solution refinement in one continuous sequence, without additional augmentations. However, this capability can be combined with techniques such backtracking and random restarts (Rossi et al., 2006) to create a neuro-symbolic solver. Another possible extension is to incorporate ConsFormer as an evolutionary algorithm (Holland, 1992) utilizing the Transformer's parallel processing ability to update a pool of candidate solutions all at once. While we leave these explorations future work, demonstrate the potential of this direction by implementing simple multi-start strategy, which we show can significantly enhance performance in Appendix
px;);) = Vp E
The loss for ConsFormer for single CSP training instance is therefore
C Ex.(((((.)) Vp:
(5)
where hyperparameter A; is the weight assigned to pt, and is an optional operation to transform the penalty for bet- ter learning. In practice, we implemented the common quadratic penalty, f(x) 2 The discrete constraints and their relaxed continuous counterparts we implemented for our experiments are shown in Table 1. Further discussion about the design process can be found in Appendix and numerical examples valid and invalid assignments for each constraint can found in Appendix
6

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
4. Experimental Results
Table 2. Performance comparison for Sudoku. In-distribution test instances contain 1, 000 instances from the SATNet dataset, OOD refers to Out-of-Distribuun evaluation on the RRN test dataset which contains 18K instances. *Values reported in (Du et al., 2024).
4.1. Problems
Sudoku is a well-known CSP problem that involves filling a 9 x 9 grid with digits from 1 to such that each row, column, and 3 sub-grid contain each digit exactly once. A single Sudoku instance consists of partially filled board and a unique assignment to the unfilled cells that satisfies the constraints. A Sudoku instance's 's difficulty is determined by the initial board: fewer initially filled cells in the board involve a larger space of possible assignments to the unfilled cells, with the hardest Sudoku puzzles having only 17 of the 81 numbers provided (McGuire al., 2014). We use the constraint from Table to formulate the problem and its corresponding continuous penalty as the loss function to guide the model learning. The full formulation of Sudoku in CP is detailed in Appendix B.
Method
Test Instances
Harder OOD Instances
Wang et al. (2019)
98.3
3.2
Palm al. (2018)*
99.8
28.6
Yang al. (2023)
100
32.9
Yang et al. (2023) (2k Iters)
97.7
14.0
Du et al. (2024)* *
99.4
62.1
ALL.DIFEEREN, m= (21, (21,..... Fnn)
ConsFormer (2k Iters)
100
65,88
ConsFormer (10k Iters)
100
77.74
We use the dataset from SATNet (Wang et al., 2019), which contains instances with [31, 42) missing values, as the train- ing and in-distribution testing dataset. To test our model's ability to generalize to harder outtof-distribution instances, we use the dataset from RRN (Palm et al., 2018) which contains instances with [17, 34) missing values.
same setup Tönshoff et al. (2023), we generate random graphs with 100 vertices for training and evaluate general- ization on benchmark instances from the GSET dataset (Ye, 2003), which includes weighted graphs with sizes ranging from 800 to 10000 vertices.
Graph Coloring is the problem of finding an assignment of colors to vertices in a graph such that no two neighboring nodes share the same color. The problem is defined by the graph's structure and the number of available colors k. We generate two sets of graph instances for l = 5 and i 10 following similar procedure as Tönshoff et al. (2023) (See Appendix C for details). Training graphs have 50 vertices for k = 5 and 100 vertices for &- = 10 whereas OOD graphs have 100 for constraints of the form 2; F xy for an edge between nodes i and j and their penalty in Table to represent the coloring constraints.
4.2. Training
For each of the problems, we train the model with randomly initialized variable assignments guided by the loss function defined in Equation (5) and the corresponding y3 associated with the constraints used to define the CSP. The training set contains 9K instances for all problems. The training details and hyperparameters for the best performing model for each problem is detailed in Appendix D.
and 200 for & = 10. We use inequality
4.3. Results
Sudoku. Table 2 reports the performance of ConsFormer and various neural methods on the Sudoku task. Cons- Former solves 100% of the Sudoku tasks from the in- distribution test dataset. On the harder disttf-distiibuttin dataset, ConsFormer significantly outperforms all learned methods, demonstrating superior generalization capabilities. ConsFormer achieves instance solve rates of 65.88% and 77.74% with 2k and 10k iterations, respectively.
Nurse Scheduling is operations research problem of assigning nurses to shifts. A problem instance has speci- fied number of days n, number of shifts per day 8, number of nurses per shift nıs, and a total number of nurses. The variables Fs,,.ss are the shift slots indexed by the day, shift, and nurse and their domains are the indices of the nurses. A feasible solution ensures that nurse is assigned to more than one shift per day and avoids assigning the same nurse to both the last shift of one day and the first shift of the following day. We use both the inequality x; * Iy and the ALLDIFFERENTms (I.,..., .n) constraints for this problem; see Appendix for the full formulation.
This highlights the iterative reasoning nature of our ap- proach. Harder instances can be solved with additional reasoning steps. whereas other solvers with fixed reasoning steps struggle. Notably, Yang et al. (2023)'s approach also employs iterative reasoning with Transformers, but their performance degraded with more test-time iterations while ConsFormer's continued to improve. This could be due to Yang et al. (2023)'s 's approach being trained for 32 itera- tions, while ConsFormer was trained for a single iteration, allowing it to generalize better when applied iteratively.
MAXCUT aims to partition the vertices of graph into two disjoint sets such that the number of edges crossing the partition is maximized. The problem can be viewed as 2-coloring problem where the objective is to satisfy as many inequality constraints 2; * xj as possible. Following the
7

---

Self-Supervieed Transformers as Iterative Solution Improvers for Constraint Satisfaction
Table Performance comparison for Graph-Coloring tasks. OOD refers to Of Df-tstribbttin evaluation for ANYCSP and Cons- Former where the number of verticies n in the graph is larger than that of the training instances. All datasets has 1200 instances.
Table 4. Performance comparison for MAXCUT tasks on GSET. Numbers reported are the average percentage gap to the best known cut size, the lower the better.
Method
-V-800
|V==K
V|=2k
V|23K
Method
Test
Harder OOD
Greedy
5.26
6.64
6,81
6,30
Instances
Instances
SDP
3.14
4.24
Graph-Coloring-5 (n 50
100)
RUNCSP
2.38
2.90
3,30
3.26
ECO-DQN
0.83
1.01
1.45
3.49
OR-Tools (10s)
83.08
57.16
ECORD
0.11
0.16
0.36
1.53
ANYCSP (10s)
79.17
34.83
ANYCSP
0.02
0.05
0.12
0.42
ConsFormer (10s)
81.00
47.33
ConsFormer OR-Tools 1.84
0.31
0.34
0.43
1.27
Graph-Coloring- 10 (n 100
+ n = 200)
2.09
3.38
3.08
OR-Tools (10s)
52.41
10.25
ANYCSP (10s)
0.00
0.00
ConsFormer (10s)
52.60
11.92
problem neurally is non-trivial, the model must learn to balance multiple constraints within a single step of solution refinement. ANYCSP was not evaluated on this dataset due to their difficulty dealing with the ALLDIFFERENT con- straint. This highlights ConsFormer's 's potential to generalize to complex problems with diverse constraint structures.
Graph Coloring. Table summarizes the performance of OR-Tools, ANYCSP (Tönshoff et al., 2023), and Cons- Former on Graph Coloring instances. OR-Tools is a state- of-the-art traditional solver for constraint programming ap- plications and serves as a strong baseline (Perron & Di- dier), achieving 100% on Sudoku instances. We ran test instances sequentially through all models with a 10-second timeout, though ConsFormer can process instances signifi- cantly faster if processed in batches due the Transformer architecture. We note that the harder dataset is not out of dis- tribution for OR-Tools, since it solves each task individually and is not learning-based solver.
MAXCUT. Table 4 compares various methods on GSET instances, reported as the relative gap (in percentage) to the best known cut values (Matsuda, 2019). ConsFormer and OR-Tools performances are obtained using the same set- up as ANYCSP, while the rest are computed directly from values reported by Tönshoff et al. (2023). While ANYCSP remains the best-performing method on GSET, ConsFormer achieves an average relative gap of 0.31 % to 1.27% without extensive model tuning, demonstrating its ability to scale to larger problems with thousands of constraints.
ConsFormer demonstrates competitive performance on in- distribution Graph Coloring with i = 5, solving 81% of the test instances approaching the 83.08% achieved by OR- Tools. While it lags behind the state-of-the-ar solver with 47.33% on the harder OOD test set, ConsFormer outper- forms ANYCSP on both distributions, which again shows our method's high generalization ability.
4.4. Ablations
Effect of subset improvement. Figure 3 examines the im- pact of varying probability of selection p on the performance of the model. The horizontal axis refers to the number of iterations at test time while the vertical axis represents the percentage of in-distribution test instances solved. We inves- tigate the behavior of the model under different probabilities p E {1.0, 0.9, 0.7, 0.5, 0.3, 0.1), where p determines the probability of selecting each variable for updates during single iteration as detailed in Section 3.2. A larger results in more variables being selected to be updated.
On the more challenging Graph Coloring with k = 10, ConsFormer surpasses OR-Tools in performance, showeas- ing the advantage of learned heuristic approaches: it may not surpass state-of-the-att solvers smaller instances, but it excels in complex cases under short time limits limits-crucial for real-world applications. Surprisingly, ANYCSP failed to solve any instances within 10 seconds for both datasets, underscoring the scalability limitations of its graph-based representation and the difficulty of training with RL. Some additional basclines can be found in Appendix G.
When = 1.0 (blue line), all variables are selected for updates during every iteration. This approach leads to rapid improvement in the early stages, as the model converges quickly to local optima. This is clearly observed in Graph Coloring, where the p 1.0 model rapidly solved 65% of instances. Performance plateaus after the initial surge whereas the stochastic models surpass it in accuracy after 50 iterations. The difference in model performance is even more drastic for Sudoku, with the p = 1.0 model reaching 20% instances solved early and converging, while the p =
Nurse Scheduling. For the Nurse Scheduling problem, ConsFormer matches OR-Tools in solving 100% of tasks across both in-distribution and out-of-distribution instances within the 10-second timeout. This high accuracy is ex- pected, given the large number of feasible solutions for each instance, as detailed Appendix C. However, solving this
8

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
Table 5. Positional Encoding Ablation Sudoku.
0.8
Model Variant
No APE
ID APE
2D APE
RPE
0.00%
0.00%
99.90%
Learned RPE
98.70%
97.10%
98.20%
0.4
Masked RPE
99.80%
99.50%
99.80%
% Instances Solved
0.2
0.0
Table 6. Positional Encoding Ablation on Graph Coloring.
10
20
30
10
50
0.8
Model Variant
No APE
ID APE
0.7
COL50
COL100
COL50
COL100
No RPE
1.58%
0.00%
1.25%
0.00%
0.5
Learned RPE
78.00%
12.50%
77.33%
0.25%
0.4
Masked RPE
75.67%
52.25%
77.00%
51.92%
0.2
2D APE outperforms the standard 1D APE typically used in Transformers, These results suggests the importance of supporting both forms of positional encodings, as different properties of different problems requires distinct spatial or relational information.
0.0
Number of Ittrations
Figure 3. Variable selection probability ablation for Sudoku (Top) and Graph Coloring with k (Bottom). The horizontal axis shows the number of iterations at test time and the vertical axis represents the % salved of in-distribution test instances.
We also note that when RPE is implemented as masked RPE, attention scores for each variable are restricted to its connected variables, closely resembling the behavior of graph neural network with attention.
0.9.p 0.7, and p 0.5 models surpass and reach near 100% within 50 iterations.
5. Limitations and Future Work
These findings highlight the importance of incorporating stochasticity into the update process for combinatorial opti- mization tasks. While deterministic updates provide faster initial convergence, they are prone to premature stagna- tion. Stochastic updates, by selectively updating subset of variables, improve generalization and allow the model to achieve higher final performance.
In its current form, ConsFormer assumes fixed constraint structure, the effects of which solution feasibility implicitly learned during training via the loss function. ConsFormer does not receive explicit constraint represen- tations as input. Constraints which are "parametric", e.g., SAT clause in which some variables may be negated and some not, cannot be handled with the architecture described herein. It is possible to address this limitation through ex- plicit constraint representations in the input; this is an im- portant direction for future work.
Effect of variable information as positional encodings, Table 5 and show the performance of ConsFormer with different positional encodings. The value displayed indi- cates the percentage in-distribution test instances solved by the model rumning 1, 000 iterations
Other future work includes exploring neural-se courol-symbolic ap- proaches incorporating ConsFormer such as those discussed in Section 3.4, other performance boosting techniques such as self taff-improvement 2025), as well as extending ConsFormer to more problems and more constraints, with the goal of devising general continuous approximation for constraints.
Across both Graph Coloring and Sudoku, observe that the inclusion of relative variable relations with RPE provides significant performance boost. This is especially true in the Graph Coloring problem, which heavily relies on the constraint graph, since the vertices have no inherent ordering to them, and therefore the indices have little meaning for the model learn from.
augment the training data (Lee et al.,
6. Conclusion
that the Transformer is able to achieve strong performance using only 2D APE, with- out leveraging explicit constraint graph information. This indicates that highly structured problems like Sudoku, the positional indices of variables alone contain sufficient information for solving the instances. We also observe that
In Sudoku however,
We introduced ConsFormer, self-supervised Transformer for iteratively solving Constraint Satisfaction Problems. We showed that our method, trained to perform single step of solution improvement, is able to generalize harder out-of- distribution instances at test time, outperforming supervised and reinforcement learning approaches.

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
Acknowledgments
Boisvert, L., Verhaeghe, H., and Cappart, Q- Towards generic representation of combinatorial problems for learning-based approaches. In International Conference on the Integration of Constraint Programming. Artifi- cial Intelligence, and Operations Research, pp. 99-108. Springer, 2024.
We thank the anonymous reviewers for their insightful feed- back, which helped us identify key limitations and promis- ing directions for future work. This work was supported by the Institute of Information & Communications Technology Planning & Evaluation (ITTP) grant funded by the Korean Govermment (MSIT) (No. 2SS22024000557882, National AI Research Lab Project). Elias B. Khalil acknowledges support from the SCALE Al Research Chair program.
Bu, F., Jo, H., Lee, S. Y., Ahn, S., and Shin, K. Tack- ling prevalent conditions in unsupervised combinato- rial optimization: Cardinality, minimum, covering, and more. In Forty-first International Conference on Machine Learning, 2024. URL httph:ttt///o forum? 9
Impact Statement
htt.ttttss//ppeeeeeeeeeee http://vpeeeeiieeeeeeee net./
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Carion, N., Massa, F., Synnaeve, G., Usunier, N., Kirillov, A., and Zagoruyko, S. End-to-end object detection with transformers. In European conference on computer vision, pp. 213-229, Springer, 2020.
References
Chalumeau, F., Coulon, I., Cappart, Q., and Rousseau, L.- M. Seapearl: A constraint programming solver guided by reinforcement learning. In Integration of Constraint Programming, Artificial Intelligence, and Operations Re- search: 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5-8, 2021, Proceedings 18, pp. 392- 409. Springer, 2021.
Achiam, J., Adler, S., Agarwal, S., Ahmad, L.., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. Gpt-4 technical report. arXiv preprint wrX1v22303.08774, 2023.
Arllkumaran, K., Deisenroth, M. P., Brundage, M., and Bharath, A. A. Deep reinforcement learning: brief survey. IEEE Signal Processing Magazine, 34(6))26-38, 2017.
Chen, D., Bai, Y., Zhao, W., Ament, S., Gregoire, J. M., and Gomes, C. P. Deep reasoning networks: Thinking fast and slow. arXiv preprint arXiv: (ao:::9000..555 2019.
Bai, Y., Chen, D., and Gomes, C. P. Clr-dmets: Curricu- lum learning with restarts to solve visual combinatorial games. 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). I). Schloss- Aaaloss-Dasttuh--Leibbiii Zentrum für Informatik, 2021.
Dai, H., Khalil, E., Zhang, Y., Dilkina, B., and Song, Learning combinatorial optimization algorithms over graphs. Advances neural information processing sys- lems, 30, 2017.
Bansal, A., Schwarzschild, A., Borgnia, E., Emam, Z., Huang. F., Goldblum, M., and Goldstein, T. End-to- end algorithm synthesis with recurrent networks: Ex- trapolation without overthinking. Advances in Neural Information Processing Systems, 35:20232-20242, 2022.
Dehghani, M., Gouws, S., Vinyals, O., Uszkoreit, J., and Kaiser, L. Universal transformers. In In- ternational Conference on Learning Representations, 2019. URL https: btttps://operreeee http:////ppeeeeeeeeeeeeeeeeeeeea net forum? id=HyzdRiR9Y7.
Beldiceanu, N., Carlsson, M., and Rampon, J.-X. Global Constraint Catalog, 2005, URL https::/hal. Research Report SICS
Donti, P. L.,, Rolnick, D.. and Kolter, J. Z. Dc3: A learn- ing method for optimization with hard constraints. In International Conference on Learning Representations.
welenneehaal000455 T2005-08.
Bengio, Y., Léonard, N., and Courville, A. Estimating propagating gradients through stochastic neurons for con- ditional computation. arXiv preprint urXiv:1308.344 2013.
Du, Y., Mao, J., and Tenenbaum, J. B. Learning iterative reasoning through energy diffusion. In International Con- ference on Machine Learning (ICML), 2024.
Fan, Y., Du, Y., Ramchandran, K., and Lee, K. Looped transformers for length generalization. In The Thirteenth International Conference on Learning Representations, 2025. URL https: http:///ppppreeeeeeee net forum? id=2edi (d=2edigk8yol gyoy
Bengio, Y., Lodi. A., and Prouvost, A. Machine learning for combinatorial optimization: a methodological tour d'horizon. European Journal of Operational Research, 290(2):405 2021.
10

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
Giannini, F., Diligenti, M., Maggini, M., Gori, M., and Marra, G. T-norms driven loss functions for machine learning. Applied Intelligence, 53(15))18775-11889) 2023.
Li, Z., Guo, J., and Si, X. G4SATBench: Bench- marking and advancing SAT solving with graph neu- ral networks. Transactions
Machine Learning Re- search, 2024. ISSN 2835-8856. URL https:// epenreview. net. forum? (atpmmmid==vaaoeoo d=7vR5do721r.
Gimelfarb, M., Taitler, A., and Sanner, S. Jaxplan and guro-
biplan: Optimization baselines for replanning in discrete and mixed discrete-contimuuus probabilistic domains. In Proceedings of the International Conference on Auto- mated Planning and Scheduling, volume 34, pp. 230-238, 2024.
Matsuda, Y. Benchmarking the max-cut problem on the sim- ulated bifurcation machine. Benchmarking the MAX-CUT problem on the Simulated Bifurcation Machine, 2019.
McGuire, G., Tugemann, B., and Civario, G. There is no 16-clue sudoku: Solving the sudoku minimum number of clues problem via hitting set enumeration. Experimental Mathematics, 23(2):190-217, 2014.
Hagberg, A., Swart, P. J., and Schult, D. A. Exploring network structure, dynamics, and function using net- workx. Technical report, Los Alamos National Labo- ratory (LANL), Los Alamos, NM (United States), 2008.
McLeish, S., Bansal, A., Stein, A., Jain, N., Kirchenbauer, J., Bartoldson, B., Kailkhura, B., Bhatele, A., Geiping, J., Schwarzschild, A., et al. Transformers can do arithmetic with the right embeddings. Advances in Neural Informa- tion Processing Systems, 37:108012-108041 2024.
Hentenryck, V. and Michel, L. Constraint-ber local search. The MIT press, 2009.
Holland, J. H. Genetic algorithms. Scientific american, 267 (1):66-73, 1992.
Ozolins, E., Freivalds, K., Draguns, A., Gaile, E., Zakovskis, R., and Kozlovics, S. Goal-aware neural sat solver. In 2022 International joint conference on neural networks (IJCNN), 1-8, IEEE, 2022.
Jang, E., Gu, S., and Poole, B. Categorical reparameteriza- tion with gumbel-softmax. In International Conference on Learning Representations, 2017.
Palm, R., Paquet, U., and Winther, O. Recurrent relational networks. Advances in neural information processing systems, 31, 2018.
Karalias, N. and Loukas, A. Erdos goes neural: an unsuper- vised learning framework for combinatorial optimization graphs. Advances in Neural Information Processing Systems, 33:6659-6672, 2020.
Park, S. and Van Hentenryck, P. Self-supervised primal- dual learning for constrained optimization. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 4052-4060, 2023.
Karalias, N., Robinson, J., Loukas, A., and Jegelka, S. Neu- ral set function extensions: Learning with discrete func- Advances in Neural Information Processing Systems, 35:15338-1553 2022.
tions in high dimensions. Advances
Perron, L. and Didier, F. CP-SAT. URL https: / //dveeloper..oooee cocpsperrs.ooll....oooooooo.. com/ optimization ep/cp_solven
Lee, N.. Cai, Z., Schwarzschild, A., Lee, K., and Papail- iopoulos, D. Self-improving transformers overcome easy-to-hard and length generalization challenges. arXiv preprint arXiv:2502.01612 2025.
Petersen, F., Borgelt, C., Kuehne, H., and Deussen, O. Learning with algorithmic supervision via continuous relaxations. Advances Neural Information Processing Systems, 34:16520-1653) 2021.
Lewkowycz, A., Andreassen, A., Dohan, D., Dyer, E., Michalewski, H., Ramasesh, V., Slone, A., Anil, C., Schlag, I., Gutman-Sole -Sol,, T., et al. Solving quantitative reasoning problems with language models. Advances in Neural Information Processing Systems, 35:3843-3857, 2022.
Petersen, F., Borgelt, C., Kuehne, H., and Deussen, O. Deep differentiable logic gate networks. Advances in Neural Information Processing Systems, 35:2006-200 2022.
Régin, J.-C. A filtering algorithm for constraints of differ- ence in esps. In AAAI, volume 94, pp. 362-367, 1994.
Li, W., Xu, Y., Sanner, S., and Khalil, E. B. Tackling the abstraction and reasoning corpus with vision transform- ers: the importance of 2d representation, positions, and objects. Transactions on Machine Learning Research, 2025.
Rossi, F., Van Beek, P., and Walsh, T. Handbook of con- straint programming. Elsevier, 2006.
Russell, S. and Norvig, P. Artificcil intelligence: modern approach. Pearson, 2016.

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
Selsam, D., Lamm, M., Bünz, B., Liang, P., de Moura, L., and Dill, D. L.. Learning SAT solver from single-bit supervision. In International Conference Learning Representations, 2019. URL https: http///pppnre...eee/eee/e./...er net/forum? i HJ A5tm.
Takase, S. and Kiyono. S. Lessons on parameter sharing across layers in transformers. In Proceedings of The Fourth Workshop on Simple and Efficient Natural Lan- guage Processing (SustaiNLP), pp. 78 90, 2023.
Tang, B., Khalil, E. B., and Drgoña, J. Learning to opti- mize for mixed-integer non non-linear programming. arXiv preprint arXiv:2410.1 1061, 2024.
Toenshoff, J., Ritzert, M., Wolf, H., and Grohe, M. Graph neural networks for maximum constraint satisfaction. Frontiers in artificial intelligence, $3580607,2022
Tönshoff, J., Kisin, B., Lindner, J., and Grohe, M. One model, any esp: graph neural networks fast global search heuristics for constraint satisfaction. In Pro- ceedings of the Thirly-Second International Joint Con- ference on Artificial Intelligence, IJCAI '23, 2023. ISBN 978-1-956792-03-4. doi: 10.24963/ijcai 476. URL https: /oi. otw.lorgg/1.200 ott//orr22.2463//jcaa 2023/476.
Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks.
Advances in neural information processing systems, 28,
2015.
Wang, P.-W., Donti, P., Wilder, B., and Kolter, Z. Satnet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In International Con- ference on Machine Learning, pp. 6545-6554. PMLR, 2019.
Wu, Y., Song, W., Cao, Z., Zhang, J., and Lim, A. Learn- ing improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 33(9)50057-506,, 2022. doi: 10.1 109/TNS.S. 2021.3068828.
Yang, Z., Lee, and Park, C. Injecting logical con- straints into neural networks via straight- estima- tors. In International Conference on Machine Learning, pp. 25096-25122. PMLR, 2022.
Yang, Z., Ishay, A., and Lee, J. Learning to solve con- straint satisfaction problems with recurrent transformer. In The Eleventh International Conference on Learning Representations, 2023.
Ye, Y. The gset dataset, 2003.
Yolcu, E. and Póezos, B. Learning local search heuristics for boolean satisfiability, Advances in Neural Information Processing Systems, 32, 2019.
12

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
A. Example Continuous Penalty Evaluations
Table Example assignments illustrating the evaluation of continuous penalties for discrete constraints. The variables æ; are represented by probability distributions approximating their one-hot form. Two assignments shown: valid assignment representing of variable values that exactly satisfy the constraint, and an invalid assignment representing set of variable values that violate the constraint. The penalty evaluates 0 for valid assignments and increases with the degree of constraint violation.
Constraint and Relaxation
Example Assignments
Valid Assignment: I1 = (1, x2 = (1,0), 23 = =0,1)
Σ c [1] =1+1++
CARDINALITY,(
(EI,.., (I,))...,An) = k
p= 2-2-
p = h Σ 10
Invalid Assignment: = (0.7, 0.3), (0.2, 0.8), = 20, 1)
Σ x (1) = 0.7 0.2 + 0 0.9
j= L, =2
p= 2-9
Valid Assignment: x1 (1, 0), 82 (0,1,0), 23 = (0,0,1)
(1) =1, (2) =1 Σ, (3) =1
ALLDIFFERENT mm (I15...,
p= -= - =.
-p= 1- 1i
Invalid Assignment: 21 (0.9, (0.9,0.1,0). 22 == (0.9.0.1,0), x3 = (0,0,1) (1) p=
(3) =1 - 1.8, Σ, 2; (2) = 0.2, Σ,,,
+ -|| 0
Valid Assignment: 3j = (1,0,0),
(1,,0,,,) 32 (0,1,0)
Σ = 1, Σ, x; =1, E, -
ALLDIPFERENT m>n m.n (I1....,
ReLU(1 1) = 0, 1-1-11
ReLU(1 - 0) 0, 0-11-
= Σ ReLU Σ
24 (
11
0 0+++0+++0=
Invalid Assignment: -1 = (0.6, 0.4, 0),
82 (0.7, 0.3, 0)
+ Σ (1) 1 Σ 2 |
Σ -
= 1.3,
=07, -,
ReLU(1.3 - 1) 0.3, -.3
ReI.U(0.77 - 0, -7 0.21 11
p= 0.3 0-3 0000+0000+0+000-000 0.9.
Valid Assignment: I; = (1,0,), t = 10,
Di + I
p = (1 0) + 1)0 (0-
p= = Σ ! Ik
(i))
Invalid Assignment: z; z; 00.7,0.3.0). 24 = (0.7,0.2,0.1) p (0.7 0.7) (0.3 0.2) (0- 0.10 = 0.49 0.06 00 0.55.
3
13

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
B. Constraint Programming formulations
B.1. Sudoku
We define the Sudoku problem as a constraint satisfaction problem (CSP) with the following components:
Variables:
Let X1, denote the variable representing the value assigned to cell (i.j), where i.j E 21. .9.
Domains:
Each variable X1, takes values from the discrete domain:
Xi. E (1,2.....
Constraints:
The solution must satisfy the following AllDifferent constraints:
Each must contain unique values:
ALL.IIFFEENT
X1,9), Vi (1)....9)))
Each column must contain unique values:
ALI.DIFFEREN (X X2j..... Xo.)); Vj (1,..,9,,
Each 3 subgrid must contain unique values. Let (r, c) index the subgrid with r, E {0, 1,2), then:
X3r+ 1,3011 X3r+ 1,302,, X3r+ 1,3033: X X3r+2,304 X3r+2,3022 X 23,+2,30433
ALFDIFFERENT
Vr,ce E 1,,1.
X3r43,3041 X X3r43,3042 N3r+3,3043
B.2. Graph Coloring
Given graph G (V, E). we define the graph coloring problem as constraint satisfaction problem (CSP) with the following components:
Variables:
Let X, be a variable representing the color assigned to vertex v E V.
Domains:
Each variable X, takes values from a set of available colors:
X, (1, k); E V.
The solution must satisfy that any two adjacent vertices must be assigned different colors: Constraints:
X, + X., V(u,v) E E.
B.3. Nurse Rostering
define the nurse rostering problem as constraint satisfaction problem (CSP) with the following components:
Variables:
Let Td,,nns be variable representing the nurse assigned to the ns-th slot of shift on day d, where:
fd.ans NJ, Vd nI, Vs E (L. Vns E (1....,N7 NS).
Constraints:
A feasible schedule must satisfy the following constraints:
No nurse can be assigned more than one shift per day:
ALLDIFFERENT m (Fa,1,1 14,1,
T4,1,N T4,,1 ........................ 242.2 J.2,NN.. ,.22....... Fd,8.1 T4.82, Kd,S,N8)
Vd E (I.
A nurse cannot be assigned both the last shift of a given day and the first shift of the following day:
Ss # Te Idtss,
Vd E (l....,
...,.. n 1}, Vns, ns' E (I....,NS))
14

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
C. Dataset Details
C.1. Graph Coloring
Following (Tönshoff et al., 2023), we generate Graph Coloring instances with the following 3 distributions:
Erdós-Rényi graphs with edge probability 100.1, 0.3)
Barabási-Albert graphs with parameter m U12, 10]
Random geometric graphs with vertices distributed uniformly at random in a 2-dimensional x threshold radius drawn uniformly from r ~ 000. 0.3].
square and edge
The 5-coloring instances were drawn uniformly for all 3 distributions, with vertices count 50 for training and in-distribution testing data, vertices count 100 for out of distribution testing. The 10-coloring instances were drawn uniforming from Erdös-Rényi graphs and Random geometric graphs, with vertices count 100 for training and in-distribution testing data, and 200 for out of distribution testing.
For each graph generated linear time greedy coloring heuristic as implemented by NetworkX (Hagberg et al., 2008) to color the graph without conflict. the greedy heuristic required k' colors for G, then we pose the problem of coloring G with & colors the training CSP instance, where is chosen
k max m10, 1}}
We generate instances until a fixed number of instances for specific is reached. 9000 for training sets, 1200 for sets.
C.2. Nurse Scheduling
We generate Nurse Rostering instances with varying difficulties. Each problem instance is defined by the number of days n, number of shifts per day s, number of nurses required per shift ns, and the total number of available nurses N.
in-distribution instances were generated with 10 days, 3 shifts per day, 3 nurses per shift, and total of N 10 nurses.
Out-of-distribution instances were generated with n 10, 3, nss 3, and N 10.
The in-distribution instances consisted of 9000 training instances and 1000 test instances. Out-of-distribution instances also had 1000 samples.
To initialize different instances, we assign one random shift to every nurse as an initial assignment. This ensures that each instance starts with a minimally constrained but valid configuration.
We note that these instances relatively easy solve due the large number of feasible solutions available. The constraints in the problem formulation do not drastically limit the space ofValid Assignments. The purpose of this dataset is to examine ConsFormer's ability to solve instances with combination of different constraints.
15

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
D. Model Details
Our models were trained on various single-core GPU nodes, including PI00, V100, and T4. A grid search was conducted to determine the best-performing hyperparameters, evaluating few hundred configurations per problem. The final reported models were trained with batch size of 512 for 5000 epochs. The typical training time for model ranges from 6 to 10 hours (wall clock). The hyperparameters for the best performing model for each of the problems is shown in Table 8. For all models, we used A as the optimizer and applied dropout of 0.1, with learning rate set to 0.0001.
Table 8, Hyperparamelers for the best performing models.
Sudoku
Graph-coloring-5
Graph-coloring-10 10
Nurse Scheduling
MAXCUT
Layer Count Head Count
7
4
7
4
3
Embedding Size
128
128
128
126
128
Selection Probability p
0.5
0.3
0.3
0.3
1.0
E. Effects of Gumbel Softmax
We use Gumbel-Softmax in ConsFormer to enable differentiable sampling of discrete variables, aligning with the discrete nature of CSPs.
To better understand why Gumbel-Softmax improves performance, we investigate whether the benefit stems from the stochasticity introduced by Gumbel noise or simply from producing sharper output distributions. To isolate these factors, we compare against a softmax variant with temperature control:
exp (Zi/T) Softmax, Σ, exp (z₃/T)
This variant allows us to control the sharpness of the output distribution without introducing stochasticity. Table 9 presents results for Sudoku and Graph Coloring (percentage of instances solved), and MAXCUT (absolute gap to best known values).
Results indicate that softmax with temperature performs competitively or even better on smaller-scale problems such as Sudoku and Graph Coloring instances. However, for larger problems like MAXCUT with thousands of variables, Gumbel-Softmax clearly outperforms temperature-controllee softmax.
This suggests that while sharper distributions (e.g.. from low temperature) beneficial, the stochasticity allows the model to generalize better across larger problem instances. The randomness can promote diversity in intermediate solutions which may help the model escape local optima over multiple inference steps.
Table 9. Comparison ConsFormer with without Gumbel-Softmax
Method
Gumbel-Softman
Softmax
0.1
0.1
Sudoku Sudoku OOD
100
100
100
100
77.74
83.71
85.67
73.72
Graph-Coloring-5 V=50
78.16
76.91
77.33
74.91
Graph-Coloring-5 V=100
42.50
41.08
42.66
35.33
Graph-Coloring-10 V=100
52.60
53.25
53.66
53.0
Graph-Coloring-I1 10 V=200
11.92
12.75
12.92
12.75
MAXCUT V 800
24.44
102.89
123.11
126.56
MAXCUT V 1K
18.22
44.0
58.33
56,89
MAXCUT V -2K
47.0
119.33
123.67
135.11
MAXCUT V 233
155.88
187.0
287.38
305.25
16

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
F. ConsFormer with Multi-Start
simple extension to enhance our model is the implementation of multi-start. Instead of a single initial solution continuously refined, we maintain a pool of candidate solutions that are updated concurrently. A solution is accepted as soon any candidate satisfies all constraints. This approach naturally complements ConsFormer, as the Transformer architecture efficiently handles batched processing.
Table 10 reports results for various candidate pool sizes. A candidate count of corresponds to the standard version of ConsFormer used in the main paper.
We observe that as the number candidates increases, the number of update iterations per candidate slightly decreases due the fixed time budget. However, the drop modest compared to the increase in candidates, highlighting the scalability of the Transformer-based model. We observe that the multi-start strategy is able noticably improve model performance. boosting accuracy from 47.33% 55.67% for graph coloring with it = 5 and 11.92% to 15.00% for k 10.
These findings highlight the potential of integrating with symbolic strategies, such restarts and backtracking, as discussed in Section 3.4. We leave further exploration of these hybrid techniques to future work.
Table 10. Performance comparison for Graph-Cor Coloring tasks on Out-of- Distribution evaluation for ConsFormer. Candidates Count refers the number of solutions used for multi-start. # Iterations Average shows the number of iterations each candidate went through under the time limit.
Method
Harder OOD
Pool Size
# Iterations
Instances
Avg
Graph-Coloring-5 (n 100)
OR-Tools (10s)
57.16
ConsFormer (10s)
47.33
2310
ConsFormer (10s)
43.42
2213
ConsFormer (10s)
50.92
10
1634
ConsFormer (10s)
55.17
50
1613
ConsFormer (10s)
55.67
100
892
Graph-Coloring-IW (n
200)
OR-Tools (10s)
10.25
ConsFormer (10s)
11.92
1490
ConsFormer (10s)
13.67
1445
ConsFormer (10s)
13.92
1064
ConsFormer (10s)
14.42
1150
ConsFormer (10s)
15.00
50
806
ConsFormer (10s)
13.25
100
229
17

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
G. Additional Baselines for Graph Coloring
We provide additional baselines for comparison on the Graph Coloring task. first run OR-Tools additional time (30 and 60 seconds) with 10 colors (where ConsFormer had previously outperformed it under 10s). We see that CP-SAT can outperform our method on small instances (nodes=100) with extended time, but it still underperforms on larger instances (nodes=200), even with 6x more time. Furthermore, in the new MAXCUT problem, 20 parallel runs each with 180s limit-were used to compute the results. ConsFormer also outperforms OR-Tools by significant margin.
We then include additional heuristic baselines; Greedy Coloring, Feasibility Jump, Random Search. The first is the greedy coloring algorithm implemented by networkx and the other two are local search approaches implemented by OR-Tools. Results are shown in Table We observe that while the local-search based heuristics were able perform well on the smaller instances, their performance significantly worsens on the larger instances with 10 colors.
Table 11. Performance comparison for Graph-Coloring tasks. OOD refers to Out-of Disttribtitttni evaluation for ANYCSP and ConsFormer where the number of verticies n in the graph is larger than that of the training instances. All datasets has 1200 instances.
Method
Test
Harder OOD
Instances
Instances
Graph-Coloring-5 (n 50 + n
100)
Greedy
32.42
0.0
OR-Tools-F] (10s)
82.83
54.5
OR-Tools-RS (10s)
83.08
56.91
OR-Tools (10s)
83.08
57.16
ANYCSP (10s)
79.17
34.83
ConsFormer (10s)
81.00
47.33
Graph-Coloring- 10 (n 100 n
200)
Greedy
0.75
0.0
OR-Tools-FJ (10s)
35.66
6.0
OR-Tools-RS (10s)
49.75
9.08
OR-Tools (10s)
52.41
10.25
OR-Tools (30s)
53.58
11.16
OR-Tools (60s)
53.67
11.66
ANYCSP (10s)
0.00
0.00
ConsFormer (10s)
52.60
11.92
18

---

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
H. Penalty Functions Design
As detailed in Section 3.3, our continuous penalties are designed such that
p(X) = 0 c(X) = True,
where penalty p approximates constraint e. defined over variables X. Intuitively, the penalty only evaluates to 0 when the constraint è is satisfied.
This approach follows constraint-bur based local search (Hentenryck & Michel, 2009). Here, constraint is associated with "violation degree" function Ue where
(X() =0 c()) satisfied
Specific functions evaluate violation degrees are designed for different global constraints. For example, a violation function for AllDi ffreenfffertt........ can be defined
vo(II,...... Inn Σ max (0, Kæy= l.. 1)
iES
where S is the set of all values in the domains of Fi,..., Fn. Intuitively, this violation degree counts how many values are assigned to more than one variable among F1,-.., This idea is extended to design the continuous penalty function for ALLDIFFERETTweee (F.
The design of the penalty functions a flexible and modular component our framework, and can benefit from further improvements which we leave for future work.
Direct Gradient Descent on Variables
A natural baseline to consider is optimizing variable assignments directly using stochastic gradient descent (SGD), without learned architecture. Specifically, if we ignore the Transformer component of ConsFormer and instead treat the variable assignments as continuous parameters, we can optimize them using our self-supervise loss. In theory, this procedure should lead to relaxed satisfying solution.
However, we found that in practice, this method frequently converges poor local optima. Additionally, because the optimization is performed independently for each instance, the updates cannot generalize other instances.
To illustrate the limitation of this approach, we performed a simple experiment on Sudoku. Starting from random initialization of missing cells, we applied SGD for 10000 steps using the self-supervised loss. The table below reports the average number of satisfied A. D ferent constraints (out of 27 total) across 10 runs:
Table 12, Direct SGD optimization Sudoku variable assignments
Missing Cells
19
33
41
47
# Satisfied AllDifferes
26.8
25.8
24.5
21.8
As expected, performance degrades as the number missing cells increases. The optimization becomes harder, and the model fails to satisfy all constraints. This highlights the importance of learning iterative improvement model, rather than relying solely on instance- instance-specific gradient descent.
19


Reviews:
[{"review_id": "vVtTz0zMPH", "reviewer": "Reviewer_tcHx", "summary": "The paper proposes training a transformer architecture in a self-supervised manner to solve constraint satisfaction problems. The input to the model is an assignment of values to the variables and the output is a refined assignment. The assignment is encoded as tokens and the constraints of the problem are encoded as relative positional encodings. The loss used to train the model is a continuous proxy for constraint satisfaction. Each type of constraint has its own proxy and then a weighted combination is taken to compute the final loss.\n\nThe approach shows competitive results in sudoku solving and CSPs like graph coloring and the nurse scheduling problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your thorough feedback and have conducted new experiments which we believe have substantially improved the paper. \n\n> Additional benchmark.\n\nWe have adapted ConsFormer for MAXCUT based on your suggestion. \n- MAXCUT is the problem of partitioning nodes of a graph into two sets in a way that maximizes the size of the cut. \n- Following ANYCSP, we train on graphs with 100 vertices and test on GSET instances with 800 to up to 10000 vertices. \n\nWe report the absolute and relative gap (in percentage) to best known values:\n|Method|V=800|V=1K|V=2K|V≥3K|\n|-|-|-|-|-|\n|Greedy|411.44(5.26)|359.11(6.64)|737.00(6.81)|774.25(6.30)|\n|SDP|245.44(3.14)|229.22(4.24)|-|-|\n|RUNCSP|185.89(2.38)|156.56(2.90)|357.33(3.30)|401.00(3.26)|\n|ECO-DQN|65.11(0.83)|54.67(1.01)|157.00(1.45)|428.25(3.49)|\n|ECORD|8.67(0.11)|8.78(0.16)|39.22(0.36)|187.75(1.53)|\n|ANYCSP|1.22(0.02)|2.44(0.05)|13.11(0.12)|51.63(0.42)|\n|ConsFormer|24.44(0.31)|18.22(0.34)|47.00(0.43)|155.88(1.27)|\n|OR-Tools|143.89(1.84)|112.78(2.09)|365.89(3.38)|378.62(3.08)|\n\nWe observe that while ANYCSP remains the best performing approach on GSET, ConsFormer achieves a relative gap of 0.31% to 1.27% on average without extensive model tuning, showcasing its ability to scale up to larger problems with thousands of constraints. \n\n> ablation study on the Gumbel-Softmax.\n\nWe chose Gumbel-Softmax for its differentiable sampling of discrete variables, aligning with the discrete nature of CSPs. Experiments during development showed it outperformed standard softmax, which we confirmed through a more systematic ablation below.\n\nHowever, your question prompted us to further investigate why Gumbel-Softmax helps: is it the stochasticity introduced by the Gumbel noise, or simply the sharper outputs it produces? To investigate this, we ran additional experiments using softmax with added temperature control – a variant we had not systematically explored in earlier versions ($Softmax_\\tau(z_i) = \\frac{\\exp\\left(z_i / \\tau\\right)}{\\sum_{j} \\exp\\left(z_j / \\tau\\right)}$\n), and present the results below (for Sudoku/Graph Coloring, we show the % instances solved, MAXCUT reports the absolute gap to best known values):\n\n||Gumbel-Softmax|Softmax|Softmax w/T|\n|-|-|-|-|\n|Sudoku|100|100|100|\n|Sudoku-hard|77.74|73.72|**85.67**|\n|Graph-Coloring-5 V=50|**78.16**|74.91|77.33|\n|Graph-Coloring-5 V=100|42.50|35.33|**42.66**|\n|Graph-Coloring-10 V=100|52.60|53.00|**53.66**|\n|Graph-Coloring-10 V=200|11.92|12.75|**12.92**|\n|MAXCUT V=800|**24.44**|126.56|123.11|\n|MAXCUT V=1K|**18.22**|56.89|58.33|\n|MAXCUT V=2K|**47.00**|135.11|123.67|\n|MAXCUT V≥3K|**155.88**|305.25|287.38|\n\nInterestingly, softmax with temperature yielded similar or better results than Gumbel-Softmax on problems with smaller sizes, while performing worse on larger problems from MAXCUT. This suggests that while the sharper distributions indeed boost model performance, the stochasticity allows the model to generalize better across larger problem instances. The randomness can promote diversity in intermediate solutions which may help the model escape local optima over multiple inference steps. We will include this ablation in the updated paper.\n\n> additional references\n\nWe appreciate the extensive list of references and will include them accordingly. We note that this list of references echoes our own finding which is that most existing approaches focus on graph-based representations or SAT formulations. To the best of our knowledge, Transformers have not been effectively implemented for general form CSPs.  \n\n> constraint violation functions seems ad-hoc and merits more discussion in the paper.\n\nOur approach is grounded in principles from the constraint-based local search literature in CP [1]. Here, constraints are associated with “violation degrees” where violation degree = 0 ⇔ satisfied. Specific functions to evaluate violation degrees are designed for different global constraints. \n\nSelecting the design for the continuous penalty is indeed important. During development we experimented with various continuous approximations including some inspired by recent work using T-norm [2] and Entropy [3] with varying effectiveness. \n\nHowever, our goal is to showcase the effectiveness of the self-supervised approach combined with the single-step transformer. We view the choice of continuous penalty functions as a flexible and modular component of our framework, one that can benefit from further improvements, but is not the central focus of this work. We will include more discussion on this in the updated paper.\n\n[1] Michel, L., Hentenryck, P.V. (2018). Constraint-Based Local Search. In: Martí, R., Pardalos, P., Resende, M. (eds) Handbook of Heuristics.\n\n[2] Giannini, Francesco, et al. “T-norms driven loss functions for machine learning.”\n\n[3] Chen, Di, et al. “Deep reasoning networks: Thinking fast and slow.”", "claims_and_evidence": "See my other comments.", "methods_and_evaluation_criteria": "The evaluation makes sense and the CSP problems that were picked for the evaluation are reasonable.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "While the choice of benchmarks in the paper is sensible, I think the overall experimental evaluation and the ablations are lacking for a paper whose content is almost exclusively empirical. Below I provide a list of issues that I have with the evaluation in the paper:\n\n-  The paper compares the proposed transformer approach against Anycsp on particular problems like k-coloring but does not provide some of the other comparisons that could be done with Anycsp. For instance, Anycsp has really strong results on max-cut and also performs pretty well on SAT so seeing how this transformer approach stacks up on those benchmarks would be nice. Another candidate benchmark can be found in [1]. These are CNF-sat instances coming from different combinatorial problems.\n\n- Another comment related to the point above has to do with the scalability of the approach. Most of the results provided are evaluations on smaller instances. Coming back to the max-cut example from Anycsp, there are instances there with several thousands of edges (constraints). Can the proposed transformer approach scale up to that? If not, what are the current limitations and are there ways that they could be addressed?\n\n1. Li, Zhaoyu, Jinpei Guo, and Xujie Si. \"G4SATBench: Benchmarking and advancing sat solving with graph neural networks.\" arXiv preprint arXiv:2309.16941 (2023).", "relation_to_broader_scientific_literature": "The paper aims to provide a new self-supervised pipeline for constraint satisfaction problems. As I mention in other places in this rebuttal this has been explored with other architectures before. The loss function design for constraint satisfaction aspect has also been explored in the literature in the self-supervised setting. \n\nThe main innovation here is to create a neural solver that relies on a powerful architecture like the transformer. This is obviously worth exploring since transformers have been extremely successful and so far there hasn't been a particularly compelling transformer architecture for these kinds of problems in the literature.", "essential_references_not_discussed": "Below I provide a non-exhaustive list of references that should be mentioned in the context of constraint satisfaction.\n\nFor CSPs and constraint satisfaction:  \n- (self-supervised architecture for CSPs) Toenshoff, Jan, et al. \"Graph neural networks for maximum constraint satisfaction.\" Frontiers in artificial intelligence 3 (2021): 580607.\n- (cardinality constraints) Wang, Runzhong, et al. \"LinSATNet: the positive linear satisfiability neural networks.\" International Conference on Machine Learning. PMLR, 2023.\n - (on using gnns for CSPs) Yau, Morris, et al. \"Are Graph Neural Networks Optimal Approximation Algorithms?.\" Advances in Neural Information Processing Systems 37 (2024): 73124-73181.\n\nFor SAT: \n- (Self-supervised sat solving) Ozolins, Emils, et al. \"Goal-aware neural SAT solver.\" 2022 International joint conference on neural networks (IJCNN). IEEE, 2022.\n-  (RL for satisfiability without labels)Yolcu, Emre, and Barnabás Póczos. \"Learning local search heuristics for boolean satisfiability.\" Advances in Neural Information Processing Systems 32 (2019).\n\nFor loss function design:\n-  (continuous relaxation/extension design) Karalias, Nikolaos, et al. \"Neural set function extensions: Learning with discrete functions in high dimensions.\" Advances in Neural Information Processing Systems 35 (2022): 15338-15352.\n - (for combinatorial constraints in self-supervised learning )Bu, Fanchen, et al. \"Tackling prevalent conditions in unsupervised combinatorial optimization: Cardinality, minimum, covering, and more.\" arXiv preprint arXiv:2405.08424 (2024).\n-  (loss function design for self-supervised constrained optimization) Karalias, Nikolaos, and Andreas Loukas. \"Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs.\" Advances in Neural Information Processing Systems 33 (2020): 6659-6672.", "other_strengths_and_weaknesses": "- It is unclear to me what the purpose of the Gumbel-Softmax approach is when predicting the value for the variables. Why is the gumbel noise added? Isn't the softmax sufficient? Does the randomness somehow help? If yes, an ablation study is appropriate. The choice is not discussed in the paper so it's hard to figure out what it could achieve.\n\nOverall, I find this direction promising but the experimental evaluation is inadequate so I cannot recommend accepting this. The writing could also be improved by providing a more detailed discussion around the questions I have raised in this review.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- There has been work on encoding cardinality cardinality constraints (and other constraints) into the loss functions of neural networks [1]. The specific choice of functions that are used as proxies for constraint violation in the loss seems ad-hoc. Have the authors compared with other techniques from the literature? For example there are various published works on loss function design for self-supervised constrained optimization [1,2].  Have the authors compared those techniques to the ones proposed here?  Using a more ad-hoc approach is fine it works but I think it merits more discussion in the paper because there are different ways of encoding those constraints and their performance may vary.\n\n1. Bu, Fanchen, et al. \"Tackling prevalent conditions in unsupervised combinatorial optimization: Cardinality, minimum, covering, and more.\" arXiv preprint arXiv:2405.08424 (2024).\n2. Karalias, Nikolaos, and Andreas Loukas. \"Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs.\" Advances in Neural Information Processing Systems 33 (2020): 6659-6672.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DL1UGqEze9", "reviewer": "Reviewer_QdQE", "summary": "The paper introduces an iterative, local search approach towards solving constraint satisfaction problems with transformer models and self-supervision.\nA new encoding scheme and the self-supervised training scheme are introduced plus a differentiable approximation for the violation of key constraints. The main aspect is the combination of being able to differentiate the approximate constraints and the 1-step prediction approach of the transformer with an overall iterative solving loop.\nExperiments are performed and show the effectiveness of the approach.\n\n## update after rebuttal\nI thank the authors for their response and their effort during the rebuttal. I maintain my score.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the encouraging feedback and thoughtful comments.\n\n> self-supervision is more limited because it needs support for every constraint to be differentiable.\n\nYou're absolutely right to point out that a key limitation of the self-supervised approach is the need to define differentiable approximations for each constraint. As you noted, our method draws directly from the constraint-based local search literature [1], where constraint violations are quantified using \"violation degrees\" to guide iterative improvement. Our contribution builds on this idea by adapting it into a differentiable, neural-friendly form that allows gradient-based learning.\n\n[1] Michel, L., Hentenryck, P.V. (2018). Constraint-Based Local Search. In: Martí, R., Pardalos, P., Resende, M. (eds) Handbook of Heuristics.\n\n>In CSP practice there are more complex and larger datasets available, put a test on the scalability of the approach.\n\nThis is a valuable point and was also raised by other reviewers. In response, we have added new experiments on the MAXCUT problem (see our response to Reviewer tcHx). These instances include thousands of variables and constraints and serve as a stronger test of scalability. The results indicate that ConsFormer remains competitive, even under larger problem sizes. While our ultimate goal is to apply ConsFormer to a wide range of CSPs, we believe that the experimental results on four benchmark problems with different combinatorial structures provide ample evidence for the promise of our method.\n\n>The results for nurse scheduling were a bit lost in the text\n\nThank you for raising this, we will revise the paper to highlight the results better.\n\n>Have you evaluated the performance when decomposing the global constraints? How does the model balance having more variables vs more complex global constraints to learn?\n\nThis is an excellent question. To investigate, we conducted an additional experiment on Sudoku where the all-different constraints are decomposed to pairwise inequalities (36 inequality constraints per all-different). This can be effectively achieved by defining the continuous penalty as follows:\n$$AllDifferent(x_1, \\ldots, x_n) \\rightarrow \\sum_{i\\neq j, i< j} \\left( \\sum_{k} x_i^{(k)}\\cdot x_j^{(k)} \\right)$$\nWe present the instance solved percentage below:\n\n|#Iterations|AllDifferent|Decomposed|\n|-|-|-|\n|1K|59.22|58.47|\n|2K|65.88|65.91|\n|10K|77.74|77.96|\n\nInterestingly, we observe that in this case, decomposing the constraints does not significantly affect performance which suggests that the model can equally handle a larger number of simpler constraints. However, we note that the resulting number of constraints is still relatively small after decomposing alldifferent for sudoku. Other more complex problems with global constraints may reveal different trade-offs which we leave for future work.\n\n>Can you transfer learn, i.e. pretrain the model for individual constraints first and then merge them towards more complex problems?\n\nThis is a great insight and is something we are planning as a future direction! One limitation of our current approach (as well as other neural approaches) is the need to train a new model for a new problem domain that consists of a different combination of constraints. With the success of the transformer’s pre-train + fine-tune approach in the natural language setting [2], one could imagine this approach applied to our setting, where models are first pre-trained for all constraints, then combined modularly to be fine-tuned for new problems. Despite the potential promise of this direction, there are many open questions to resolve in future work in order to bridge from the current model to this ideal goal of a highly general and transferable pretrained model.  We will add this excellent future work discussion on revision.\n\n[2] Radford, Alec, et al. \"Improving language understanding by generative pre-training.\" (2018).", "claims_and_evidence": "The paper claims to avoid bottlenecks available in other approaches (supervised + RL) and does so through the self-supervision approach.\nThis is not novel (RL does it somehow), but it's more efficient because there is differentiation. \n\nIt is more limited though, because it needs support for every constraint to be differentiable. Seeing the approximations proposed in the paper, these differentations are a conceptualization of the constraint violations, which are commonly used in constraint-based local search too to judge the quality of an improvement, and should be derivable for every constraint. So, at this stage it's mostly a matter of defining them for all constraints and, maybe, there can even be a more general form derived by looking the overall CSP. In conclusion, the claim is sufficiently supported.", "methods_and_evaluation_criteria": "The selected methods make sense. A CSP is inherently either a graph or a sequence and using a transformer model is one way to model it in the ML paradigm (graph-based approaches being the other major one currently studied in the literature).\n\nIn terms of datasets, the selection is okay and in line with the literature. In CSP practice there are more complex and larger datasets available, which should be considered for future work and would really put a test on the scalability of the approach -- but not necessarily required here.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Experiments make sense. Baselines are okay. There is a lot of work in this area and other baselines might be suitable as well besides ANYCSP, but including OR-Tools is the most relevant one and they are sufficient to serve the point.", "relation_to_broader_scientific_literature": "Connections to the relevant areas (CP, ML, ML4CO) are made and supported with relevant references.", "essential_references_not_discussed": "I'm not aware of any missing literature.", "other_strengths_and_weaknesses": "This is a really good paper with a strong contribution. The proposed encoding and training scheme is sufficiently simple to be usable and adaptable for other settings and by relying on CP modelling for the CSP problems it can be very powerful.", "other_comments_or_suggestions": "- The results for nurse scheduling were a bit lost in the text, maybe you can include them in Table 3", "questions_for_authors": "- Have you evaluated the performance when decomposing the global constraints? How does the model balance having more variables vs more complex global constraints to learn?\n- Can you transfer learn, i.e. pretrain the model for individual constraints first and then merge them towards more complex problems?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "80nXFOyrdb", "reviewer": "Reviewer_3qja", "summary": "This paper presents a Transformer-based learning framework for solving CSPs. Specifically, they leverage a transformer architecture to refine the solution, where they show that decision variable position encoding is key for transformer learning. They adopt a continuous approximation as loss function, and show on three CSPs (Sudoku, Graph Coloring, Nurse Scheduling) that their proposed method outperform the baselines.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful feedback and questions. We’ve conducted new experiments and clarified key aspects of the method in response to your concerns, which we believe strengthen the submission significantly.\n\n> Can the authors benchmark on more complicated problems?\n\nWe have added experiments on the MAXCUT problem. Please refer to our response to reviewer tcHx for details.\n\n> CP-SAT takes more time than learning-based methods, so the authors should consider allowing CP-SAT to solve for longer.\n\nEfficiency is indeed a major advantage of our method and in many applications it is necessary to solve for a good feasible solution very quickly.\n\nThat said, we conducted new experiments where CP-SAT was allowed to run for 30 and 60 seconds on the Graph-Coloring task with 10 colors (where ConsFormer had previously outperformed it under 10s). Results are shown below:\n||n=100|n=200|\n|-|-|-|\n|OR-Tools(10s)|52.41|10.25|\n|OR-Tools(30s)|53.58|11.16|\n|OR-Tools(60s)|53.67|11.66|\n|ConsFormer(10s)|52.60|11.92|\n\nWe see that CP-SAT can outperform our method on small instances (nodes=100) with extended time, but it still underperforms on larger instances (nodes=200), even with 6x more time. Furthermore, in the new MAXCUT problem, 20 parallel runs–each with 180s limit–were used to compute the results.  ConsFormer also outperforms OR-Tools by a significant margin. \n\n> compare with more heuristic baselines\n\nWe include 3 additional heuristic baselines for graph coloring:\n- Greedy Coloring\n- Feasibility Jump\n- Random Search\n\nThe first is the greedy coloring algorithm implemented by networkx and the other two are local search approaches implemented by OR-Tools. We note that the LS algorithms are already present in the default OR-Tools used for the paper. \n|Color count = 10|n=100|n=200|\n|-|-|-|\n|Greedy|0.75|0.00|\n|FJ(10s)|35.66|6.0|\n|RS(10s)|49.75|9.08|\n|OR-Tools(10s)|52.41|10.25|\n|ANYCSP(10s)|0|0|\n|ConsFormer(10s)|52.60|11.92|\n\n|Color count = 5|n=50|n=100|\n|-|-|-|\n|Greedy|32.42|0.00|\n|FJ(10s)|82.83|54.5|\n|RS(10s)|83.08|56.91|\n|OR-Tools(10s)|83.08|57.16|\n|ANYCSP(10s)|79.17|34.83|\n|ConsFormer(10s)|78.16|42.50|\n\nWe observe that while the local-search based heuristics were able to perform well on the smaller instances, their performance significantly worsens on the larger instances with 10 colors. \n\n> nurse scheduling results\n\nThey were reported in-text in Section 4.3. We will revise the paper for better clarity.\n\n> I’m concerned that the paper may lack novelty.\n\nAs far as we know, we are the first to successfully apply a Transformer architecture to solve general CSPs in a self-supervised setting. Existing work often requires graph representations of the problems while we treat them as sequences.\n\n> How did you decide the lambda_i? Would an adaptive way to select different lambda_i l for different constraints lead to better performance?\n\nThis is a great suggestion and an adaptive lambda is indeed an interesting direction that we plan on exploring for future work. For now, each problem has a relatively simple mixture of constraints, so the weights are manually set.\n\n>Instead of the differentiable loss with GumbelSoftmax, I wonder if the authors have tried reinforcement learning?\n\nWe apologize if we have misunderstood, but we believe the reviewer may be referring to use of the REINFORCE trick (or score-function based gradient estimators) from RL that can be generally used to compute gradients of discrete variables.  However, we note that the Gumbel-Softmax paper[1] discusses that this gradient estimator has high variance (Section 3.2 of [1]) and performs very poorly (Section 4.1 of [1]) in practice -- in fact it is the worst performing of all discrete gradient estimators they compare.\n\n[1] Jang et al. \"Categorical Reparameterization with Gumbel-Softmax.\" \n\n>instead of feeding the entire solution back for refinement, have the authors consider only improving a subpart of the solution and fixing the rest\n\nWe completely agree with the intuition, and in fact, our model effectively incorporates this idea via the Variable Subset Selection step (Section 3.2, line 203). At each iteration, only a subset of variables is selected for update, mimicking local search behavior. We found that this strategy significantly improves generalization compared to updating the full assignment each time, as discussed in Section 4.4.", "claims_and_evidence": "The claims made in the submission generally are supported by clear and convincing evidence, although I have some questions / concerns regarding the evaluation. See my answer to “Experimental Designs or Analyses”.", "methods_and_evaluation_criteria": "The proposed methods and evaluation datasets seem to be reasonable, except for my concerns in “Experimental Designs or Analyses”.", "theoretical_claims": "There’s no theoretical claims nor proofs in this paper.", "experimental_designs_or_analyses": "I see the following issues regarding experimental design:\n- The authors set a time limit of 10s for solving graph coloring and nurse scheduling. I find the time limit to be too short (e.g. maybe this reflect that the CSPs the authors evaluation on are too simple to solve). Can the authors benchmark on more complicated problems? Also, can the authors increase the time limit for solving the instances? I think it makes sense for constraint programming solver CP-SAT to take more time than learning-based methods, so the authors should consider allowing CP-SAT to solve for longer.\n- Can the authors compare with more heuristic baselines (e.g. local search, genetic algorithm)? I find the comparison with heuristic baselines somewhat lacking.\n- Maybe I missed this, but I don’t see nurse scheduling results reported in the paper?", "relation_to_broader_scientific_literature": "This paper contributes an improved learning methods for solving constraint programming problems. I find the discussions / experiments regarding position encoding interesting.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I’m concerned that the paper may lack novelty: for example, encodeing positional information for iterative solution improvement has been explored in learning for combinatorial optimization literature before, and the Gumble-softmax differentiable loss isn’t new either.", "other_comments_or_suggestions": "Sec 2.2. “Yang et al. proposed a recurrent Transformer architecture” → You missed the year citation for Yang et al.", "questions_for_authors": "1. Sec 3.3 Eq (5): “hyperparameters lambda_i is the weight assigned to p_i”. How did you decide the lambda_i? Would an adaptive way to select different lambda_i l for different constraints lead to better performance? (potentially with learning, or some heuristic methods)\n2. Instead of the differentiable loss with GumbelSoftmax, I wonder if the authors have tried reinforcement learning? The benchmark tasks seem to be relatively standard to design RL rewards, so I feel like an ablation study of differentiable loss v.s. RL would further strengthen the paper.\n3. Sec 3.4 Iterative Test-Time Deployment: instead of feeding the entire solution back for refinement, have the authors consider only improving a subpart of the solution and fixing the rest (e.g. incorporate a local search procedure with learning)? How well would that work?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZvsAq8WJd0", "reviewer": "Reviewer_g9ez", "summary": "This paper mainly focuses on constraint satisfaction problems (CSPs). It proposes a transformer-based model to serve as an iterative solution improver, repeatedly revising the generated CSP solution until it is correct.\n\n- The main _idea_ is to leverage the self-supervised learning paradigm, that is, to train the model without using any labeled or pre-processed solution.\n- The main *contribution* is that this work adopts a self-supervised manner, which can avoid the pre-given solution for learning.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful comments and are glad that you see the potential for our method in aiding the development of large-scale CSP solving.\n\n>no discussion about RL-based methods both in theoretical analysis and experimental comparison. \n\nWe would like to clarify that both theoretical and experimental comparisons with RL-based approaches are included in the paper.\n- Theoretical considerations are discussed in Sections 2.2 and 3.3.\n- Experimentally, we directly compare against ANYCSP, a state-of-the-art RL-guided neural solver for CSPs. \n\nWe will revise the paper to make these points more prominent.\n\n> The reward signal in this setting seems much easier to define. For instance, we could simply set the reward as the difference in the number of satisfied constraints.\n\nDefining a reward as the number of satisfied constraints is indeed an intuitive design. However, prior work indicates that such rewards are not sufficient to guide learning effectively. \n\nANYCSP [1] experimented with the exact reward you have suggested and found that “models trained with this reward tend to get stuck in local maxima”. They comment that “intuitively, this simple reward scheme immediately punishes the policy for stepping out of a local maximum causing stagnating behavior”. \n\nTheir method implements a much sparser reward to avoid this issue by setting the reward to 0 in any step in which the new assignment is not an improvement over the previous best. \n\nIn contrast, our approach provides a dense training signal through differentiable penalty functions. These loss functions guide the model even when no constraint is fully satisfied. \n\n[1] Tönshoff, Jan, et al. \"One model, any CSP: graph neural networks as fast global search heuristics for constraint satisfaction.\" (2022).\n\n\n>Comparison to other methods is not fair. Du et al. (2024) do this experiment based on ResNet.\n\nWe note that Du et al. themselves compare against models like SATNet and RRN which are not ResNet based models. SATNet is a model that learns the SDP relaxation of a SAT formulation, while RRN is a graph-based model. \n\nWhile it’s true that Du et al.’s method uses a ResNet base model, We follow standard practice  and make comparisons between full frameworks for solving CSPs.\n\n\n> can this optimization approach also be applied to directly solve Constraint Satisfaction Problems (CSP) using local search? \n\nYes! And indeed the existing literature of local search was a prominent inspiration for us, specifically, our approach is grounded in principles from the constraint-based local search literature [2]. In this approach, constraints are associated with “violation degrees” that measure how far a solution is from satisfying the constraint (violation = 0 ⇔ satisfied). We adopt this principle and extend it to the neural domain by designing differentiable approximations of these violations that work with probabilistic assignments.\n\n[2] Michel, L., Hentenryck, P.V. (2018). Constraint-Based Local Search. In: Martí, R., Pardalos, P., Resende, M. (eds) Handbook of Heuristics.\n\n>Furthermore, can iterative improvement be achieved by addressing an optimization problem with Stochastic Gradient Descent (SGD)?\n\nThis is a great insight. Indeed if we ignore the transformer architecture and perform SGD on a set of variable assignments guided by our self-supervised loss, the variable assignments can be updated to become a (relaxed) satisfying solution. However, we found that in practice this method often leads to local optima, furthermore, we see a drastic decrease in performance as the SGD focus on a single instance and does not know how to generalize to other instances. Our framework essentially learns this update using a single-step transformer and is able to generalize by training on a larger set of instances.\n\nTo showcase this, we run a simple SGD on a Sudoku board where the missing values are randomly initialized and update it with SGD guided by the loss function for 10000 iterations. We observe the following results averaged over 10 runs:\n|#Missing Values|19|33|41|47|\n|-|-|-|-|-|\n|#AllDifferent Satisfied (Max 27)|26.8|25.8|24.5|21.8|\n\nWe see as the problem becomes harder with more missing cells, the number of satisfied alldifferent constraints became lower. We will include this discussion in the revision of the paper.", "claims_and_evidence": "There are a few claims that I think may not be supported in this paper: \n\n- 1.  The author claim that their paradigm, compared with RL-based methods, is more practical. But there is no discussion about RL-based methods both in theoretical analysis and experimental comparison.\n\n- 2. The author compared their method with other SOTAs in table 2, however, it seems to simply copy the results heavily from Du et al. (2024). This is not fair since the results are not based on the same base model. To my best knowledge, Du et al. (2024) do this experiment based on ResNet.", "methods_and_evaluation_criteria": "The proposed model makes sense.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Yes, I have checked the experiments. The main concern of this experiment is the unfair comparison between this work and others, especially copied from Du et al. (2024). Those methods are based on a ResNet structure, while this is a transformer-based model. Also, since the authors claim their method can avoid disadvantages of RL-based method, they should discuss more about by experiments.", "relation_to_broader_scientific_literature": "The key contributions *may* aid the development of large-scale CSP solving; however, the author did not discuss this perspective in the current version.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "PROS: \n- This paper is overall well written and easy to follow.\n- The proposed method makes sense, and I have run the code to validate the overall effectiveness.\n\n\nCONS:\n- The comparison of experiments is somehow unfair and too simple.", "other_comments_or_suggestions": "Overall, this paper presents an interesting approach to CSP solving and offers an effective method. However, it is not yet ready for publication due to unsupported claims and unfair comparisons. Additionally, there needs to be more discussion and comparison regarding RL-based methods. \n\nOne suggestion I have is that if the unsupported claims can be substantiated, either theoretically or practically, the paper would be significantly improved. If these concerns are adequately addressed, I would be inclined to raise my score.\n\n\n## After Reviewing the Rebuttal\n\nI appreciate the author's response; however, I find the comparison based on different architectures (backbones) to be flawed. Additionally, I disagree with the following statement:\n\n> \"We agree that a broader study—e.g., isolating the effect of ResNet vs. GNN vs. SATNet vs. Transformer under various learning paradigms—would be highly valuable, and we share your interest in such work. However, we view that as a larger, survey-level endeavor rather than the goal of the current contribution.\"\n\nIf the comparison is deemed unfair, it should not be included as a method of evaluation in the scope of this paper. I believe that comparing these works using the same architecture (in this case, the Transformer) would be more beneficial and equitable.\n\nFurthermore, the authors mention a theoretical discussion of reinforcement learning (RL) methods; however, this discussion lacks formal analysis and seems to lean more towards narrative rather than substantive content, which appears to be an overstatement in their rebuttal.\n\nConsidering these issues, I believe a weak reject is an appropriate score, and I think this paper has the potential for improvement.", "questions_for_authors": "Q1: If the iterative improvement method is effective, can this optimization approach also be applied to directly solve Constraint Satisfaction Problems (CSP) using local search? Furthermore, can iterative improvement be achieved by addressing an optimization problem with Stochastic Gradient Descent (SGD)?\n\nQ2: Why do reinforcement learning (RL) methods not fit into this scenario? I'm confused because the reward function or signal in this setting seems much easier to define. For instance, we could simply set the reward as the difference in the number of satisfied constraints.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes ConsFormer, a self-supervised Transformer framework for solving CSPs through iterative refinement. It avoids reliance on labeled solutions or complex RL rewards by using differentiable proxies for constraint violations. The idea is well-motivated and the method performs competitively across several CSP benchmarks. While some reviewers raised concerns about experimental depth and comparison fairness, the authors responded with new results (e.g., on MAXCUT) and detailed clarifications, which strengthened the case for the paper. Overall, this is a solid contribution with practical value and promising scalability.
Decision: Accept (poster)