Research map / Label-efficient and robust learning / Self-supervised and contrastive

Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction

ICML 2025 · Label-efficient and robust learning › Self-supervised and contrastive · approach: Self-supervision in supervised pipelines · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes ConsFormer, a Transformer trained with a self-supervised differentiable constraint-violation loss to improve random CSP assignments in a single step, then applied iteratively at test time.

Problem

Solving constraint satisfaction problems (CSPs) quickly with learned heuristics, avoiding the need for feasible-solution labels in supervised learning and the large budgets and hand-designed rewards of reinforcement learning.

Approach

A single-step Transformer is trained self-supervised on differentiable continuous penalties approximating discrete CSP constraints, using stochastic variable subset selection and APE/RPE encodings of variable indices and constraint graph; at test time it is iterated like local search so that more iterations solve harder out-of-distribution instances.

Key results

• ConsFormer solves 100% of in-distribution Sudoku test instances and 77.74% of harder OOD Sudoku instances with 10k iterations, versus 62.1% for the best prior neural baseline.
• On Graph-Coloring-10 (n=100 to 200), ConsFormer reaches 11.92% OOD solve rate vs 10.25% for OR-Tools under 10s; multi-start with 100 candidates raises Graph-Coloring-5 OOD to 55.67%.
• On GSET MAXCUT, ConsFormer achieves average gaps of 0.31% to 1.27%, but ANYCSP remains best (0.02% to 0.42%).

Measured effects reported in the paper

Surprising findings

• ANYCSP solved 0% of Graph-Coloring-10 instances within 10 seconds despite strong results on Graph-Coloring-5.
• Softmax with low temperature matched or beat Gumbel-Softmax on Sudoku and Graph Coloring, with Gumbel-Softmax helping mainly on large MAXCUT instances.

Limitations

• Assumes a fixed constraint structure; parametric constraints (e.g., SAT clauses with negations) cannot be handled.
• Does not match state-of-the-art ANYCSP on MAXCUT GSET and lags OR-Tools on harder OOD Graph Coloring k=5.
• Single-step training with a fixed selection probability and grid-searched hyperparameters per problem.

Experimental setup

Datasets: SATNet Sudoku dataset RRN Sudoku dataset Randomly generated graph coloring instances (Erdos-Renyi, Barabasi-Albert, random geometric) Nurse rostering generated instances Random graphs for MAXCUT training

Benchmarks: SATNet Sudoku RRN Sudoku (harder OOD) Graph Coloring k=5 and k=10 Nurse Scheduling GSET MAXCUT

Metrics: % instances solved average relative gap to best known cut

Baselines: OR-Tools ANYCSP RRN SATNet Greedy SDP RUNCSP ECO-DQN ECORD

Builds on: Transformer Gumbel-Softmax constraint-based local search ANYCSP

Closest papers by meaning

• Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.87)
• Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces (NeurIPS 2026 · similarity 0.86)
• Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.86)
• Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error (NeurIPS 2025 · similarity 0.85)
• GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.85)
• Self-Labeling the Job Shop Scheduling Problem (NeurIPS 2024 · similarity 0.85)