Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems

Geri Skenderi; Lorenzo Buffoni; Francesco D'Amico; David Machado; Raffaele Marino; Matteo Negri; Federico Ricci-Tersenghi; Carlo Lucibello

cond-mat.dis-nnFeb 20, 2026

Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems

Authors: Geri Skenderi, Lorenzo Buffoni, Francesco D'Amico, David Machado, Raffaele Marino, Matteo Negri, Federico Ricci-Tersenghi, Carlo Lucibello,

Organizations: Department of Computing Sciences, Bocconi University, Milan, Italy · Bocconi Institute for Data Science and Analytics (BIDSA) · Department of Physics and Astronomy and INFN, University of Florence · Dipartimento di Fisica, Sapienza Universit`a di Roma ·

Abstract

Graph neural networks (GNNs) are increasingly applied to hard optimization problems, often claiming superiority over classical heuristics. However, such claims risk being unsolid due to a lack of standard benchmarks on truly hard instances. From a statistical physics perspective, we propose new hard benchmarks based on random problems. We provide these benchmarks, along with performance results from both classical heuristics and GNNs. Our fair comparison shows that classical algorithms still outperform GNNs. We discuss the challenges for neural networks in this domain. Future claims of superiority can be made more robust using our benchmarks, available at https://github.com/ArtLabBocconi/RandCSPBench.

Figures & tables

Panel of Figure 1 — Figure 1: Probability of finding a satisfying assignment to 3-SAT problems as a function of $\alpha=M/N$ with the supervised (top row) and unsupervised (bottom row) NeuroSAT GNN model. To validate claims regarding the importance of scaling the inference time message-passing iterations of GNNs with the problem size ( $N$ ), we test the model in three different scenarios by performing a small number of fixed iterations (left), a large number of fixed iterations (center), and linearly scaling the number of iterations with the problem size (right). The figure shows that the linear scaling procedure produces excellent results. It is worth noting that with the scaling, inference time is handled more consistently (by definition). For instance, using 512 iterations takes significantly longer for smaller sizes compared to employing linear scaling. Finally, it is clear to see that training an unsupervised model produces much better results compared to the supervised case.

Panel of Figure 2 — Figure 2: Probability of finding a satisfiable assignment using different algorithms at fixed size ( $N=256$ on the left and $N=1024$ on the right) for the $K$ -SAT ( $K=3,4$ ) and $q$ -col ( $q=3,5$ ) problems. We focus on two sizes: $N=256$ is the largest size in the training set, and $N=1024$ , which is out-of-distribution, to check the generalization power.

SAT	$K=3$ ; S $\uparrow$	$K=4$ ; S $\uparrow$	$K=3$ ; RE $\downarrow$	$K=4$ ; RE $\downarrow$
NeuroSAT	84.48	47.52	0.0072	0.0028
QuerySAT	92.38	66.57	0.0068	0.0027
FMS	99.98	95.15	0.0061	0.0032
SA	98.75	82.61	0.0063	0.0027
SP + dec.	82.28	60.02	-	-

Table 1: Score (S) and Residual Energy (RE) reached by each algorithm . The Score is the ratio of solved instances over the satisfiable ones in the test dataset (

N\leq 256

and any

\alpha

c

values). An instance is considered satisfiable if at least one of the analyzed algorithms found a solution (see Sec. 4.5 ). The ratio of sat instances

\text{n}_{\text{sat}}/\text{n}_{\text{tot}}

are 28656/42000 (3-SAT), 19806/21000 (4-SAT), 11750/20000 (3-col), and 9184/20000 (5-col). RE is the average of the intensive energy computed on instances for which the algorithm is not finding a solution. The running steps are

1000N

for SA,

100N

for FMS in the

K

-SAT problem, and

1000N

for SA,

625N

for FMS in the

q

-col problem, with each step involving

N

attempted single-variable updates. The number of recurrent iterations is

2N

for NeuroSAT and QuerySAT. Best results are in bold. RE values for the SP algorithm are missing because SP sometimes does not converge on hard instances, and in this case it does not output a configuration of the variables (see Sec. 4.3.3 for details).

Panel of Figure 3 — Figure 3: Estimation of the algorithmic threshold in the large size limit for different algorithms and problems, indicated in the label under the panel. The left panel shows the easy situation, when crossings of curves for different sizes take place at the same point (apart from small finite-size corrections), and the crossing point corresponds to the algorithmic threshold in the large $N$ limit. Instead, in the central and the right panels, we report more difficult situations, where the crossings are not present or happen very close to boundaries ( $P=0$ or $P=1$ ). In the latter cases, the curves measured at finite $N$ provide a bound to the algorithmic threshold in the large $N$ limit. Data in the central panel provide a lower bound, while those in the right panel provide an upper bound.

SAT	$K=3$	$K=4$
NeuroSAT	3.8	$\lesssim$ 8.1
QuerySAT	4.1	9.1
FMS	4.2	9.8
SA	4.1	9.5
SP + dec.	4.2	9.7

Table 2: Algorithmic threshold for different algorithms By definition, the algorithmic threshold is computed taking the limit of large

N

. In this limit, Neural Solvers behave much worse than classical algorithms, especially in the hard 1RSB problems (

4

-SAT and

5

-col). FMS is the algorithm that has the best algorithmic thresholds.

SAT	$K=3$	$K=4$
NeuroSAT	14.57	24.91
QuerySAT	134.43	322.53
FMS	1.83	3.80
SA	1.82	13.04
SP + dec.	2.61	3.06

Table 3: Average running times (in seconds) for different algorithms over

400

instances with

N=1024

variables. For neural solvers, we report the testing time. We fix

\alpha=4.1

for 3-SAT,

\alpha=9.4

for 4-SAT,

c=3.68

for 3-col and

c=11.1

5-col. For

K

-SAT, we ran the algorithms using Lenovo Hardware AMD Ryzen Threadripper PRO 5975WX 32-Cores with 251 GB of RAM. For

q

-col, we ran the rPI-GNN using the NVIDIA Tesla V100 SXM2 32G GPU and QuerySAT on NVIDIA TITAN RTX GPU, while all other algorithms were run on a single CPU Intel Xeon Gold 6248 2.5G.

	$n_{\text{tot}}$	$n_{\text{sat}}$
3-SAT	42000	28656
4-SAT	21000	19806
3-col	20000	11750
5-col	20000	9184

Table 4: The total number of instances and the number of satisfiable ones for each (in-distribution,

N\leq 256

) test dataset.

Constraint Satisfaction

Constraint satisfaction studies how to find or optimize assignments that obey interacting rules across discrete and structured problems.

See all 86 papers

Graph Neural Networks are Heuristics
Jan 19, 2026Yimeng Min, Carla P. GomesTraveling Salesperson Problem Graph Neural Networks
Department of Computer Science Cornell University Ithaca, NY, USA
Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks
Feb 16, 2026Sungwoo KangAlgorithm Selection Combinatorial Optimization
Department of Electrical and Computer Engineering Korea University Seoul 02841, Republic of Korea
Hard Instances on Demand
Oct 15, 2026Jamie Fravel, Martin Koutecký, Pavlo TsitseiSynthetic Benchmark Generation
Computer Science Institute, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic.

Jan 19, 2026J/K move · Enter open · S save

Graph Neural Networks are Heuristics

Yimeng Min, Carla P. Gomes

Department of Computer Science Cornell University Ithaca, NY, USA

Traveling Salesperson Problem Graph Neural Networks Combinatorial Optimization Neural Combinatorial Optimization

Open paper AskPDF arXiv

Graph neural networks are usually treated as auxiliaries for combinatorial optimization: they imitate algorithms, guide search, or supply scores to classical procedures. We show that this auxiliary role is not intrinsic. A GNN can itself be a heuristic. For the Euclidean Travelling Salesman Problem, we train a non-autoregressive GNN with no labels, rewards, sequential decoding, search, or local improvement. A differentiable Hamiltonian-cycle objective is the only supervision. The trained model produces a complete tour in one forward pass, while dropout and snapshots from a single training trajectory provide solution diversity without engineered moves. The heuristic is therefore learned, not programmed. It is also fast: batched inference remains in the millisecond regime on GPUs. Experiments on TSP100, TSP200, and TSP500 show that the model consistently improves over nearest-neighbor greedy baselines. These results identify unsupervised GNNs as a class of fast learned heuristics for combinatorial optimization.

Abstract

Constraint Satisfaction

Explore similar work

Graph Neural Networks are Heuristics

Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks

Hard Instances on Demand