Compute Time Scaling with Recursive Models for Combinatorial Optimization

Zhengxi Zhang; Paul Swoboda

cs.LGSep 28, 2026

Compute Time Scaling with Recursive Models for Combinatorial Optimization

Authors: Zhengxi Zhang, Paul Swoboda

Abstract

We propose Tiny Recursive Models for Combinatorial Optimization (\ours{}), a general neural method for combinatorial optimization that scales both depth (how often we recursively invoke our network) and width (how much we sample in parallel). Both are fundamental for combinatorial optimization: hard instances demand a large amount of compute, while a small network is essential to avoid overfitting and capture the algorithmic essence of optimization. In particular, our method consists of a graph-aware tiny recursive model that iterates on a latent state with adaptive halting and needs only a lightweight problem-specific decoder. Compared with previous heatmap-based general neural solvers, it achieves a better balance between solution quality and inference speed on both the Traveling Salesman Problem~(TSP) and the Maximum Independent Set~(MIS) problem, and remains competitive with hybrid methods that combine neural components with heuristics specific to each problem. With the same backbone architecture for both tasks, \ours{} outperforms every diffusion-based solver on TSP from 500 to 10,000 cities at a lower inference cost, and on the standard Erdős--Rényi-[700-800] MIS benchmark it surpasses all neural solvers except those that only work well on MIS. We then explore self-relabeling for self-supervised training. We periodically replace the current set of training labels with the model's own better solutions, as an alternative training signal. Self-relabeling can, while forgoing supervision from near-optimal solutions, still result in on-par quality.

Figures & tables

General-purpose neural solvers (MIS and TSP)
Dataset		ER-[700-800]			SATLIB
Method	Type	Size	Gap %	s/inst	Size	Gap %	s/inst
KaMIS (reference)	heuristic	44.87	0.00	24	425.96	0.00	4.5
DIMES ( Qiu et al., 2022 )	RL	42.06	6.26	–	423.28	0.63	–
DIFUSCO ( Sun and Yang, 2023 )	S	41.12	8.36	7.4	425.13	0.19	1.6
T2T ( Li et al., 2023 )	S + search	41.37	7.80	9.0	425.22	0.17	1.5

Table 1: MIS results. We list mean independent set size on ER-[700-800] and SATLIB, gap in % with respect to the KaMIS reference, and seconds per instance on one RTX 4090. Type: S = supervised, U = unsupervised, RL = reinforcement learning (details in Appendix E ). “–” means that the number is not available, and “ † ” marks evaluation on the method’s own instances from the same distribution. The KaMIS time is measured on CPU. Bold marks the lowest gap on each benchmark.

Dataset		TSP-500			TSP-1000			TSP-10000
Method	Search	Len.	Gap %	s/inst	Len.	Gap %	s/inst	Len.	Gap %	s/inst
Concorde / LKH-3 (reference)	–	16.55	0.00	18	23.12	0.00	187	71.77	0.00	1980
General-purpose neural solvers (MIS and TSP)
DIMES ( Qiu et al., 2022 )	MCTS	16.84	1.76	67	23.69	2.46	136	74.06	3.19	1219
DIFUSCO ( Sun and Yang, 2023 )	2-opt	16.65	0.57	2.9	23.45	1.43	12.4	73.89	2.95	266
DIFUSCO	MCTS	16.63	0.46	51	23.39	1.17	104	73.62	2.58	1076

Table 2: TSP results on uniform instances. We report mean tour length, gap in % against Concorde (

n=500,1000

) and LKH-3 (

n=10000

), and seconds per instance on one RTX 4090. The Search column indicates the search procedure that produces each result, either post-processing after the network or a custom refinement loop (details in Appendix E ). The meanings of “–”, “ † ”, and the reference solver time follow those of Table 1 . Bold marks the lowest gap at each problem size.

Run	Labels	Gap %
MIS ER-[700-800]
Supervised	KaMIS	2.53
Self-relabel continuation	KaMIS, then own	1.11
Self-relabel from scratch	Own only	1.43
TSP-500
Supervised	LKH-3	0.11

Table 3: Self-relabeling. Test gap in % for MIS on ER-[700-800] against KaMIS, decoded with sequential peeling at the setting of Table 1 (

k_{\mathrm{p}}=2

\tau=0.5

K=10

D=32

), and for TSP-500 against Concorde at the setting of Table 2 (

K=40

D=32

, 2-opt). The supervised rows train on solver labels, the continuation row trains on top of the supervised checkpoint, and the from-scratch rows start from random initialization without any solver labels.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Hook	MIS	TSP
Instance $x$	Adjacency $A\in\{0,1\}^{n\times n}$	Coordinates $X\in[0,1]^{n\times 2}$
Tokens $\mathrm{Emb}(x)$	Linear $[\deg,\ \mathrm{RWPE},\ u\sim\mathcal{U}(0,1)]$	Linear $[X,\ \sin/\cos(2^{l}\pi X)]_{l<L_{\mathrm{pe}}}$
Attention bias	Adjacency $A$	None (standard self-attention)
Head $g_{\theta}(y)$	Node logits $[n,2]$	Bilinear successor logits $[n,n]$
Decoder $\mathrm{Dec}$	Greedy independent set in score order	Greedy edge insertion by $\bar{g}_{ij}/d_{ij}$
Wrapper $\mathcal{W}$	Sequential peeling around the recursion	2-opt on the tour returned by Solve

Appendix

Table 4: Problem-specific hooks of Algorithm 1 . Everything not listed here (the core, the recursion schedule, deep supervision, and the self-relabeling loop) is shared.

Parameter	Value
Hidden size, heads, blocks	512, 8, 2
MLP expansion	4
Recursion $H$ , $L$	3, 6
Prefix tokens $P$	16
Structure, MIS	Edge-biased attention, 12-step random-walk positional encoding
Structure, TSP	Self-attention, $L_{\mathrm{pe}}=6$ coordinate encoding

Appendix

Table 5: Hyperparameters of the reported models. Epochs are passes over the training set, summed over all stages of a continued run. The self-relabeling continuation of Table 3 adds 3000 epochs with a 2000-step warm-up. Test-time

K

D

\sigma

\tau

k_{\mathrm{p}}

, and

m

are given with each table.

Method	MIS	TSP
Moco	0.36M	0.85M
T2T / Fast T2T	1.34M	5.33M
DIFUSCO / DISCO	–	5.33M
CAM	0.18M	5.20M
UDC	4.35M	1.56M
DRHG	–	2.65M

Appendix

Table 6: Learned parameters of each network. Ours and Moco are counted from checkpoints; the others are derived from stated hyperparameters or official code, since no paper states its count.

Factor	Variant	Gap %
MIS structure injection (one-shot, $K{=}1$ )
	3-layer GNN encoder + self-attention	20.2
	6-layer GNN encoder + self-attention	13.5
	No encoder + edge-biased attention (default)	10.0
MIS prefix tokens (same schedule, best checkpoint of the last training window)
	$P=0$	15.0

Appendix

Table 7: Ablations, one factor at a time. MIS on ER-[700-800] (gap in % against our KaMIS labels, 44.63), TSP-500 (gap in % against Concorde), and TSP-10000 (gap in % against LKH-3). Each block varies one factor of the default configuration, with

K

D

, and

\sigma

as noted. The MIS decoding block uses the supervised checkpoint of Table 3 with

\sigma=0.5

and

\tau=0

, and the rollout and Gumbel rows an earlier checkpoint with

\sigma=0.7

, so their gaps are not directly comparable with Table 1 .

Explore similar work

Leveraging Structural Constraints for Diffusion-based Neural TSP Solvers
Jun 8, 2026Mickaël Basson, Philippe PreuxSalesman Problem Neural Combinatorial Optimization
CRIStAL, Scool · Université de Lille, France · CNRS, France +2
Recurrent State Encoders for Efficient Neural Combinatorial Optimization
Sep 5, 2025Tim Dernedde, Daniela Thyssens, Lars Schmidt-ThiemeNeural Combinatorial Optimization Vehicle Routing Problem
Information Systems and Machine Learning Lab (ISMLL) Institute of Computer Science University of Hildesheim
LoRe: Adaptive Interaction-Evaluation Routing with Per-Step Interaction Budgets for Iterative Graph Solvers
May 27, 2026Jintao Li, Yong-Yi Wang, Zheng-An Wang +1Neural Solvers Solver Iterations
Beijing Key Laboratory of Fault-Tolerant Quantum Computing, Beijing Academy of Quantum Information Sciences, Beijing, China · Beijing National Laboratory for Condensed Matter Physics, Institute of Physics, CAS, Beijing, China · Beijing Key Laboratory of Advanced Quantum Technology, Beijing, China +1

Jun 8, 2026, cs.AIJ/K move · Enter open · S save

Leveraging Structural Constraints for Diffusion-based Neural TSP Solvers

Mickaël Basson, Philippe Preux

CRIStAL, Scool · Université de Lille, France · CNRS, France+2

Salesman Problem Neural Combinatorial Optimization Inference-Time Structural Constraints Hamiltonian Generative Models

Open paper AskPDF arXiv

Neural combinatorial optimization has recently achieved strong results on the Euclidean Traveling Salesman Problem (TSP) using generative models such as diffusion and consistency models. State-ofthe-art approaches like FT2T combine fast consistency-based prediction with gradient-based inference time refinement. However, gradient search often incurs significant computational overhead and may not align with the discrete structure of feasible solutions. We introduce Projected Consistency Inference (PCI), a plug-and-play, retraining-free alternative that replaces gradient refinement with structure-aware projections: PCI decodes valid Hamiltonian tours from the consistency model output and applies a lightweight local search (e.g., 2-opt). PCI achieves an average optimality gap (OG) of 0.17% on TSP with 500 cities, and 0.31% on TSP with 1000 cities, outperforming FT2T best settings (OG 0.22% and 0.36%, respectively) while reducing the inference time up to 30 to 40%. PCI also exhibits lower variance and memory usage, and can surpass classical heuristics such as LKH3 in rapid solution generation. Our results demonstrate that structure-aware inference time operations provide a practical and principled path for neural TSP solvers, complementing training time objectives.

Abstract

Explore similar work

Leveraging Structural Constraints for Diffusion-based Neural TSP Solvers

Recurrent State Encoders for Efficient Neural Combinatorial Optimization

LoRe: Adaptive Interaction-Evaluation Routing with Per-Step Interaction Budgets for Iterative Graph Solvers