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

Jun 8, 2026cs.AI

Leveraging Structural Constraints for Diffusion-based Neural TSP Solvers

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.

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

Ask PDF

Sep 5, 2025cs.LG

Recurrent State Encoders for Efficient Neural Combinatorial Optimization

The primary paradigm in Neural Combinatorial Optimization (NCO) consists of construction methods, where a neural network is trained to sequentially add one solution component at a time until a complete solution is formed. We observe that the typical changes to the state between two steps are small, since usually only the node added to the solution is removed from the state. An efficient model should be able to reuse computation from prior steps. To that end, we propose a recurrent encoder that computes state embeddings based not only on the current state but also on embeddings from the previous state. We show that this recurrent encoder can achieve equivalent or better performance than a non-recurrent encoder even with

3\times

fewer layers, thus significantly improving latency. We demonstrate our findings on three different problems: the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), and the Orienteering Problem (OP), and integrate the models into a large neighborhood search algorithm to showcase the practical relevance of our findings.

Tim Dernedde, Daniela Thyssens, Lars Schmidt-Thieme

Information Systems and Machine Learning Lab (ISMLL) Institute of Computer Science University of Hildesheim

Neural Combinatorial Optimization Vehicle Routing Problem Recurrent State Neural Network Optimization

Ask PDF

May 27, 2026cs.LG

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

Diffusion-based neural solvers for combinatorial optimization repeatedly re-evaluate dense edge/factor interactions, making inference expensive in wall-clock time and often memory-bound at scale. Inspired by the computational methodologies of many-body physics, we introduce LoRe, a training-free, inference-time drop-in wrapper that enforces per-step interaction-evaluation budgeting: at each iteration, it evaluates only a fixed fraction of interactions by dynamically routing computation to high-conflict or high-uncertainty interactions, instead of using a fixed sparsification (e.g., static kNN graphs or static masks). Under fully inclusive end-to-end wall-clock accounting, LoRe substantially improves scalability on the Maximum Independent Set (MIS) problem, extending feasible inference more than

3\times

beyond the baseline's out-of-memory limit, delivering a

\sim 8\times

speedup and a

\sim 12\times

peak-memory reduction, with solution quality preserved in this regime. Demonstrating cross-task generality on the large-scale Traveling Salesperson Problem (TSP) and zero-shot robustness to topology shifts, LoRe achieves a

\sim 15\times

speedup at

n=1000

with a

44\times

memory reduction and competitive tour quality.

Jintao Li, Yong-Yi Wang, Zheng-An Wang +1

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

Neural Solvers Solver Iterations Inference-Time Token Budget Allocation Peak Memory Many-Body Physics

Ask PDF