Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction

Yudong W. Xu, Wenhao Li, Scott Sanner, Elias B. Khalil · 2025

Read Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction by Yudong W. Xu, Wenhao Li, Scott Sanner, Elias B. Khalil (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-15794.txt.

Introduction

Transformers can improve their own draft solutions to constraint problems, Yudong Xu and co-authors show in a 2025 paper. Their framework is called ConsFormer. Constraint satisfaction problems appear in many fields, and speeding them up with machine learning is of wide interest. Prior methods need labeled feasible solutions or large reinforcement learning budgets with hand-made rewards.

ConsFormer is self-supervised and acts as a solution refiner. It builds a solution step by step in a process that mimics local search. Training uses differentiable approximations to the discrete constraints, so no feasible labels are required. The model is trained to improve a random assignment by one step, then applied again and again at test time. Tests cover Sudoku, graph coloring, nurse rostering, and MAXCUT.

Catalog record

CREATORYudong W. Xu, Wenhao Li, Scott Sanner, Elias B. Khalil
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-15794

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction Yudong W. Xu, Wenhao Li, Scott Sanner, Elias B. Khalil 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. 1 Introduction Figure 1: ConsFormer 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, a ConsFormer model is invoked iteratively until a feasible solution is found or an iteration limit is met. Constraint Satisfaction Problems (CSPs) are fundamental to many real-world applications such as scheduling, planning, and resource management. However, solving CSPs efficiently in practice remains a significant challenge due to their NP-complete nature. Traditional solvers based on constraint propagation and backtracking search can be computationally expensive, especially for large problem instances. This has motivated the exploration of learning-based approaches as fast neural heuristics for CSP solving ( Dai et al., 2017 ; Selsam et al., 2019 ; Bengio et al., 2021 ) . Most existing learning-based methods use either supervised or reinforcement learning (RL). Supervised approaches train models on 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 quantities of data often needed to train a model that generalizes well. This is especially true for hard instances that traditional solvers struggle to solve quickly. Second, CSPs often have multiple feasible solutions ( Russell & Norvig, 2016 ) , making it difficult to apply supervised learning unambiguously when there are many possible labels for the same input. RL-based methods, on the other hand, search for solution strategies through black-box optimization of a 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 Transformer-based self-supervised framework for solving CSPs. Inspired by Constraint-based Local Search ( Hentenryck & Michel, 2009 ) , ConsFormer learns to iteratively refine variable assignments through a self-supervised training paradigm that approximates discrete constraints with continuous differentiable penalty functions. Our model is trained to improve an initial random assignment in a single refinement step, but is applied iteratively at test time. While a single step may not yield a feasible solution, a sufficiently large number of improving iterations (on average) does. Examples of ConsFormer solutions are shown in Figure 1 . Transformers provide a natural fit for this approach due to their strong generalization capabilities and their ability to process structured data efficiently ( Lewkowycz et al., 2022 ; Achiam et al., 2023 ) . They are particularly effective at learning with tokenized inputs, making them well-suited for combinatorial problems formulated in the Constraint Programming paradigm ( Rossi et al., 2006 ) . Furthermore, recurrence has been shown to enhance the generalization abilities of Transformers ( McLeish et al., 2024 ; Fan et al., 2025 ) , reinforcing their suitability for our setting. Our iterative solution improvement strategy enables ConsFormer to generalize beyond its training distribution, effectively solving out-of-distribution (OOD) CSP instances simply by performing more refinement steps. We evaluate ConsFormer on a diverse set of CSP problems, including Sudoku, Graph Coloring, and Nurse Scheduling, demonstrating its ability to generalize across problem domains. Our implementation is available on GitHub 1 1 1 https://github.com/khalil-research/ConsFormer . The following high-level findings summarize our work: – Self-supervised learning can be applied to solve CSPs. We show that a 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 is key for Transformer learning. We show that by representing variable positional information as absolute and relational positional encodings in the Transformer, we enable solution improvement in variable space. – ConsFormer can generalize when trained to perform solution improvement. While trained to perform a single improvement step, ConsFormer generalizes to out-of-distribution instances and achieves state-of-the-art results for generalizing to OOD tasks in Sudoku, outperforming all existing neural methods. 2 Background 2.1 Constraint Satisfaction and Programming A Constraint Satisfaction Problem (CSP) is a mathematical model used to represent problems that involve finding values for a set of variables subject to (possibly discrete and non-linear) constraints. Formally, a CSP is defined as a tuple (X,D,C) , where X=\{x_{1},x_{2},\dots,x_{n}\} is a finite set of variables, D=\{D_{1},D_{2},\dots,D_{n}\},D_{i}\subset\mathbb{Z}\;\forall i\in[n] represents the discrete domains of these variables, and C=\{c_{1},c_{2},\dots,c_{m}\} is the set of constraints, where each constraint c_{i} is defined over a subset of variables X_{i}\subseteq X , restricting the values that can be simultaneously assigned to them. The goal in solving a CSP is to assign to each variable a value from its domain such that all constraints in C are satisfied. Constraint Programming (CP) ( Rossi et al., 2006 ) is the study of mathematical models and solution algorithms for CSPs. CP uses highly expressive global constraints ( Beldiceanu et al., 2005 ) that involve multiple variables and are designed to capture common constraint structures that appear in a wide range of real-world applications. One prominent example of a global constraint is the AllDifferent constraint ( Régin, 1994 ) , which ensures that a subset of the variables take on distinct values. 2.2 Related Work Constraint solving with supervised learning. Supervised learning has been extensively applied to constraint solving. For example, Pointer Networks ( Vinyals et al., 2015 ) are used for the sequential generation of combinatorial problems involving permutations such as the traveling salesperson problem. Palm et al. (2018) propose a graph-based recurrent network to model CSPs, effectively leveraging the graph structure to refine variable assignments iteratively. SATNet ( Wang et al., 2019 ) differentiates through semidefinite programming relaxations in a supervised setting to handle logical constraints. Du et al. (2024) introduce a method for iterative reasoning through energy diffusion, focusing on progressive refinement of solutions. More recently, 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 supervised approaches is the need for labels, which is not easy to

Read the complete text