Neural networks are being increasingly used as heuristics for constraint satisfaction. These neural methods are often recurrent, learning to iteratively refine candidate assignments. In this work, we make explicit the connection between such iterative neural heuristics and Large Neighborhood Search (LNS), and adapt an existing neural constraint satisfaction method-ConsFormer-into an LNS procedure. We decompose the resulting neural LNS into two standard components: the destroy and repair operators. On the destroy side, we instantiate several classical heuristics and introduce novel prediction-guided operators that exploit the model's internal scores to select neighborhoods. On the repair side, we utilize ConsFormer as a neural repair operator and compare the original sampling-based decoder to a greedy decoder that selects the most likely assignments. Through an empirical study on Sudoku, Graph Coloring, and MaxCut, we find that adapting the neural heuristic to an LNS procedure yields substantial gains over its vanilla settings and improves its competitiveness with classical and neural baselines. We further observe consistent design patterns across tasks: stochastic destroy operators outperform greedy ones, while greedy repair is more effective than sampling-based repair for finding a single high-quality feasible assignment. These findings highlight LNS as a useful lens and design framework for structuring and improving iterative neural approaches.
Figures & tables
Figure 1: Comparison between the original ConsFormer update and our ConsFormer-LNS. Top: ConsFormer takes the current assignment x(t) , selects a random subset of variables, applies the Transformer, and samples a new assignment x(t+1) . Bottom: In ConsFormer-LNS, a destroy operator selects variables to modify, and the Transformer acts as part of a neural repair operator that proposes the next assignment x(t+1) .
Dataset
Repair
Random
Worst
Related
Gradient
Confidence
Gr.
St.
Gr.
St.
Gr.
St.
Gr.
St.
Test
Sampled
100
94.3
100
99.7
100
20.6
100
0.0
100
Greedy
100
85.6
100
99.9
100
0.0
100
0.0
100
OOD
Sampled
85.8
16.7
71.7
32.1
48.7
0.1
90.6
0.0
90.8
Greedy
81.2
11.8
91.8
30.9
63.9
0.1
84.1
0.0
91.5
Table 1: Sudoku instances solved (%) for different combinations of destroy and repair operators. Columns correspond to the destroy operators specified in Section 3.2 where the Greedy and Stochastic variants are labeled (Gr.) and (St.) respectively. Rows vary the repair operator (sampling-based vs. greedy). Test instances contain 1,000 instances from the SATNet dataset, OOD refers to Out-of-Distribution evaluation on the RRN test dataset which contains 18K instances. All configurations are evaluated for 2K iterations.
Size
Repair
Random
Worst
Related
Gradient
Confidence
Gr.
St.
Gr.
St.
Gr.
St.
Gr.
St.
∣V∣=800
Sampled
16.33
430.11
473.00
923.67
472.33
167.78
45.11
489.67
9.78
Greedy
31.67
503.11
38.56
915.00
71.33
137.00
4.44
397.00
21.00
∣V∣=1K
Sampled
12.44
382.89
417.67
781.00
418.56
154.89
30.89
469.22
9.78
Greedy
25.00
414.11
33.22
714.33
57.00
116.56
8.00
364.11
18.78
∣V∣=2K
Sampled
52.11
832.89
944.78
1646.11
944.67
297.00
69.89
1014.00
37.11
Table 2: MaxCut performance on GSET: average gap to the best known cut (lower is better) for different graph sizes. Columns and Rows correspond to destroy and repair operators as in Table 1 . All configurations are evaluated with a 180s time limit.
Dataset
Repair
Random
Worst
Related
Gradient
Confidence
Gr.
St.
Gr.
St.
Gr.
St.
Gr.
St.
Graph-Coloring-5 ( n=50→n=100 )
Test
Sampled
81.6
33.4
77.8
32.0
81.8
41.7
79.9
25.7
82.3
Greedy
82.9
32.9
82.5
22.1
82.8
41.2
82.9
32.7
81.8
OOD
Sampled
46.3
0.0
41.0
0.0
47.6
0.7
44.8
0.0
49.0
Greedy
54.2
0.1
52.5
0.0
53.7
2.6
54.0
0.0
49.4
Table 3: Graph-Coloring instances solved (%). Top: Coloring-5, Bottom: Coloring-10. Columns and Rows correspond to destroy and repair operators as in Table 1 . OOD refers to Out-of-Distribution evaluation for ANYCSP and ConsFormer where the number of vertices n in the graph is larger than that of the training instances. All datasets have 1200 instances. All configurations are evaluated with a 10s time limit.
Figure 2: Sudoku instances solved (%) over LNS steps for the baseline random destroy and the best-performing classical (stochastic worst removal) and prediction-guided (stochastic confidence-margin removal) destroy operators. Both heuristics outperform random removal, with confidence-margin removal improving fastest early on and stochastic worst removal eventually achieving the highest solved percentage.
Figure 3: Cell accuracy for Sudoku over iterations for greedy (blue) and stochastic (orange) variants of Worst and Confidence destroy operators. Greedy variants plateau early, while stochastic variants continue to improve and reach substantially higher accuracies.
Figure 4: Sudoku constraint accuracy on OOD Test dataset over LNS steps for greedy (blue) and sampling-based (orange) repair under Random and two best-performing destroy operators (Stochastic Confidence-margin, Stochastic Worst). Split violin plots show the distribution of per-instance constraint satisfaction at selected steps, while the lines on the right axis show the cumulative fraction of instances solved. Greedy repair achieves higher final solved percentages but exhibits a wider tail of unsolved instances, whereas sampling attains higher average constraint accuracy at intermediate steps.
Dataset
SATNet
RRN
Recurrent
IRED
ConsFormer
ConsFormer
[ 37 ]
[ 22 ]
Trans. [ 40 ]
[ 9 ]
-LNS
Test
98.3
99.8
100
99.4
100
100
OOD
3.2
28.6
32.9
62.1
85.8
91.8
Table 4: Performance comparison for Sudoku. In-distribution test instances contain 1,000 instances; OOD refers to RRN test dataset (18K instances). For all but ConsFormer and ConsFormer-LNS, the reported instance solved (%) are based on the results from Xu et al. [ 39 ] .
Dataset
Greedy
OR-Tools
ANYCSP
ConsFormer
ConsFormer
[ 23 ]
[ 35 ]
-LNS
Graph-Coloring-5 ( n=50→n=100 )
Test
32.42
83.08
79.17
81.60
82.90
OOD
0.00
57.16
34.83
47.33
54.20
Graph-Coloring-10 ( n=100→n=200 )
Test
0.75
52.41
0.00
53.60
53.90
Table 5: Performance comparison for Graph-Coloring tasks. All methods are evaluated with a 10s time limit. OOD refers to Out-of-Distribution evaluation where n is larger than training instances. For all but ConsFormer and ConsFormer-LNS, the reported instance solved (%) are based on the results from Xu et al. [ 39 ] .
Size
Greedy
SDP
RUNCSP
ECO-DQN
ECORD
ANYCSP
OR-Tools
ConsFormer
ConsFormer
[ 14 ]
[ 34 ]
[ 1 ]
[ 2 ]
[ 35 ]
[ 23 ]
-LNS
∣V∣=800
411.44
245.44
185.89
65.11
8.67
1.22
143.89
16.33
4.44
∣V∣=1K
359.11
229.22
156.56
54.67
8.78
2.44
112.78
12.44
8.0
∣V∣=2K
737.00
-
357.33
157.00
39.22
13.11
365.89
52.11
30.56
∣V∣≥3K
774.25
-
401.00
428.25
187.75
51.63
378.62
115.25
63.63
Table 6: Performance comparison for MaxCut tasks on GSET. Numbers reported are the average gap to the best known cut size, the lower the better. Values are as reported in Xu et al. [ 39 ] . We similarly set a time limit of 180 seconds.