PaperlayerView exact revision on arXiv

Source-linked AI summary

Compute Time Scaling with Recursive Models for Combinatorial Optimization

Zhengxi Zhang, Paul Swoboda

arXiv:2609.34585v1cs.LG

TL;DR

Combinatorial optimization demands substantial computation, while large neural networks can be slow and prone to overfitting. TRM4CO uses a small recursive model that scales computation through depth and parallel rollouts, with problem-specific encoders and decoders. It reports strong results on TSP and MIS, and self-relabeling can improve models trained with or without solver labels.

  • Problem

    Neural combinatorial optimization must reconcile optimization’s high computational demands with networks that often have many parameters but do relatively little computation per parameter.

    Source: §1 · p. 1

  • Method

    TRM4CO repeatedly applies a small recursive model to latent and answer states, scaling test-time computation through depth and parallel rollouts with problem-specific encoding and decoding.

    Source: §1 · pp. 1–2, §2.2 · p. 4

  • Results

    On TSP-500 and TSP-1000, TRM4CO has the lowest gap among learned solvers and matches the best diffusion solver on TSP-10000; with 200 rollouts, it surpasses general-purpose neural solvers and KaMIS on ER-700–800 MIS.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Self-relabeling improves models trained with solver labels or without them, while the backbone remains general and the encoders and decoders remain problem-specific.

    Source: §5 · p. 9

    The backbone is general, but the encoder and decoder remain problem-specific.

    Source: §5 · p. 9

Abstract

from arXiv · show

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\H{o}s--R\'enyi-[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.

1 INTRODUCTION

TRM4CO addresses the mismatch between optimization’s need for extensive computation and neural networks’ tendency toward many parameters with little computation per parameter. It uses recursive depth and parallel sampling to scale compute, and reports strong learned-solver results on TSP and MIS.

1 INTRODUCTION

  • The paper targets a mismatch: optimization algorithms do much computation in short programs, while neural networks often use many parameters but little computation per parameter.The stated design challenge is to obtain deep computational graphs from relatively few parameters, preserving speed and avoiding overfitting.Source: §1 · p. 1
  • TRM4CO applies a small recursive model repeatedly to latent and answer states, scaling test-time compute through recursion depth and parallel solution sampling.It can train from solver labels or self-supervised labels that it improves through repeated sampling and hill-climbing.Source: §1 · p. 1
  • Prior neural solvers either construct solutions sequentially or predict heatmaps that still require search; scalable diffusion variants iterate on a fixed noise schedule or scale compute in heatmap space.Earlier supervised GNN edge classifiers are described as no longer competitive on their own.Source: §1 · pp. 1–2
  • The method combines problem-structure-aware encodings, lightweight problem-specific decoders, and decoded-solution-driven halting and selection, while keeping network size constant.The paper reports both supervised training from solver labels and self-supervised training through self-relabeling.Source: §1 · p. 2
  • TRM4CO achieves the lowest learned-solver gaps on TSP-500 and TSP-1000, matches the best diffusion solver on TSP-10000, and with 200 rollouts surpasses general-purpose neural solvers and KaMIS on ER-700–800 MIS.Self-relabeling raises 16% of training labels above KaMIS and yields the best MIS checkpoint; without solver labels, its own labels match or beat KaMIS on 42% of training graphs.Source: §1 · p. 2

2 METHOD

TRM4CO encodes an instance, iteratively updates latent and answer states, and uses depth and parallel rollouts to generate feasible candidates. It trains with adaptive halting and can periodically replace labels with better model-generated solutions.

2 METHOD

  • The framework encodes an instance, updates latent and answer states iteratively, and keeps the best feasible solution across steps and rollouts; training may replace labels whenever a better solution is found.The encoder supplies node tokens, and the problem-agnostic recursive backbone is paired with a problem-specific decoder.Source: §2 · p. 2

2.1 BACKGROUND: TINY RECURSIVE MODEL (TRM)

  • The TRM backbone repeatedly updates latent reasoning and answer states with shared weights, applies deep supervision across recursion steps, and halts solved instances early so remaining steps go to harder ones.Adding noise to latent states and running parallel copies supplies extra samples at test time.Source: §2.1 · pp. 2–3

2.2 THE TRM4CO FRAMEWORK

  • Depth D counts recursion steps and width K counts parallel noisy copies; feasible candidates are decoded with MIS peeling or TSP edge insertion plus 2-opt, then ranked by objective.Compute cost scales linearly with K × D on the same weights, without adding parameters or training.Source: Figure 1 · p. 3, §2.2 · p. 4

2.3 TRAINING AND INFERENCE

  • Training supervises predictions at successive steps and halts instances when problem-specific checks pass; periodic self-relabeling replaces labels only with strictly better solutions.Without an external solver, one initial pass seeds labels from the model’s guesses before later relabeling passes improve them.Source: §2.3 · p. 4

3 EXPERIMENTS

The experiments compare TRM4CO with neural, learning-free, and classical reference solvers on MIS and TSP, then examine test-time scaling, ablations, and self-relabeling. Results show strong learned-solver performance on both tasks, with different trade-offs against search-based methods.

3.1 SETUP

  • Benchmarks use ER-[700-800] and SATLIB for MIS, and uniform TSP instances at 500, 1000, and 10000 cities; quality is reported as objective values and gaps against reference solvers.Runtime is measured from input to final solution on one RTX 4090, while classical reference-solver times come from the original papers.Source: §3.1 · p. 5

3.2 MAIN RESULTS ON MIS

  • With more rollouts, TRM4CO passes Moco and the KaMIS reference on ER-[700-800] as the only learned solver without a sampler to do so; learning-free samplers reach slightly lower gaps.RLSA, alone and with COExpander, dominates on ER graphs, while TRM4CO closes much of that distance at higher cost because peeling reruns the recursion about |S|/kp times.Source: §3.2 · p. 5, Table 1 · p. 6

3.5 ABLATIONS

  • For MIS, edge-biased attention avoids the message-passing encoder whose one-shot gap can be twice as high; for TSP, raw coordinates have 5.6× the gap of sinusoidal features.A k-nearest-neighbor edge bias adds nothing for TSP, and a finer sinusoidal embedding hurts.Source: §3.5 · pp. 6–7

3.3 MAIN RESULTS ON TSP

  • At n = 500 and 1000, TRM4CO has the lowest gap among learned solvers; at n = 10000 it matches COExpander and beats every other diffusion solver.Hybrid methods using Lin–Kernighan or destroy-and-repair search reach lower gaps at lower cost.Source: §3.3 · p. 5, Table 2 · p. 7

3.5 ABLATIONS

  • Sequential peeling cuts the same MIS checkpoint’s gap by two thirds, while edge insertion avoids stranded nodes and one 2-opt pass brings raw tours within 1% of optimal.Removing prefix tokens raises the one-shot MIS gap by half; the prefixes provide global memory that node tokens alone do not.Source: §3.5 · p. 7

3.4 SCALING TEST-TIME COMPUTE

  • On ER-[700-800], finer peeling (kp = 2) lowers the gap at every K and crosses the KaMIS reference; on TSP, gaps fall with K at both depths.At kp = 8, ER gaps fall steadily with K while depths 16 and 32 overlap; overall cost is linear in K × D because rollouts use a batched forward.Source: §3.4 · p. 6, Figure 2 · p. 8

3.6 SELF-RELABELING AS SELF-SUPERVISION

  • Continuing supervised MIS training with self-generated better labels cuts test gap by more than half and yields the best checkpoint; from-scratch relabeling approaches KaMIS on MIS, but TSP remains 20× worse than supervised.The continuation's relabeling raises about 16% of training instances above their KaMIS labels, by one node on average.Source: §3.6 · p. 8

4 RELATED WORK

Prior neural combinatorial optimizers build solutions sequentially, predict heatmaps for later search, or allocate extra compute around the network. This work places refinement inside recursive reasoning and applies it to combinatorial optimization at scale.

Constructive policies

  • Autoregressive policies build solutions one decision at a time, while several methods reach larger instances through decomposition [Kwon et al., 2020] [Ye et al., 2024; Zheng et al., 2024].HyperNS guides Lin–Kernighan search with a heatmap, while GOAL injects edges into attention [Lu et al., 2026; Drakulić et al., 2025].Source: §4 · p. 9

Heatmap solvers and search

Unsupervised and self-improving solvers

  • Unsupervised solvers optimize relaxed objectives, while SIL improves constructive policies on their own locally searched solutions; TRM4CO self-relabels with its decoded solutions and no relaxed objective [Min et al., 2023; Sanokowski et al., 2024; 2025; Feng et al., 2026b; Luo et al., 2024].Moco allocates compute at test time to a learned heatmap optimizer, while iSCO and ReSCO require no learning [Dernedde et al., 2025; Sun et al., 2023; Li & Zhang, 2025].Source: §4 · p. 9

Recursive reasoning

5 CONCLUSION

TRM4CO uses a small recursive network with problem-specific encoding and decoding, scaling test-time computation in depth and width across MIS and TSP. The paper reports code, checkpoints, and relabeled datasets will be released upon acceptance.

5 CONCLUSION

  • TRM4CO is competitive with or better than search-heavy pipelines on MIS and TSP, and self-relabeling improves it with solver labels or without them.The backbone is general, but the encoder and decoder remain problem-specific; reducing that dependence is identified as the natural next step.Source: §5 · p. 9

REPRODUCIBILITY STATEMENT

  • Code, checkpoints for every reported run, and relabeled datasets will be released upon acceptance.Appendices list hyperparameters, datasets and reference solutions, and the runtime protocol.Source: REPRODUCIBILITY STATEMENT · p. 10

A ALGORITHM AND PROBLEM-SPECIFIC HOOKS

Algorithm 1 describes procedures shared by MIS and TSP, while Table 4 lists their problem-specific hooks. Figure 4 unrolls one recursion step and highlights changes to the TRM schedule.

A ALGORITHM AND PROBLEM-SPECIFIC HOOKS

  • Algorithm 1 gives the procedures shared by MIS and TSP, and Figure 4 unrolls one recursion step.The step uses L latent updates and one answer update per cycle, with H cycles and gradients only through the last cycle; detached states carry forward.Source: A ALGORITHM AND PROBLEM-SPECIFIC HOOKS · p. 14, Figure 4 · p. 14
  • At test time, noise on z produces K independent rollouts, and every TSP step or MIS peeling round is decoded into a feasible solution and scored.During training, the solved check halts an instance in place of the learned halting signal.Source: Figure 4 · p. 14
  • Table 4 lists problem-specific hooks; the core, recursion schedule, deep supervision, and self-relabeling loop are shared.Source: Table 4 · p. 14

B HYPERPARAMETERS

The appendix specifies the shared recursion, inference and training procedures, then documents task-specific augmentation and implementation choices. Reported model settings and continued-run epoch counts are summarized alongside those procedures.

B HYPERPARAMETERS

  • Inference initializes K copies, runs D recursion steps with noise on z, decodes and scores each answer, and returns the best-scoring solution.Algorithm 1 defines one recursion step with H cycles, each using L latent updates followed by an answer update.Source: B HYPERPARAMETERS · p. 15
  • Training applies cross-entropy supervision after each step, detaches states, refills slots when instances are solved or reach D steps, and periodically replaces labels with better wrapper outputs.The solved check uses problem-specific criteria, and self-relabeling compares the wrapper's solution with each stored label.Source: B HYPERPARAMETERS · p. 15
  • Reported training uses D = 16 for TSP and 32 for MIS, with P = 16 prefix tokens, H = 3 cycles, L = 6 latent updates, and 12-step random-walk positional encoding for MIS.The ER supervised checkpoint uses 10,000 epochs, followed by a 3000-epoch self-relabeling continuation; other run-stage epoch counts are specified by task.Source: B HYPERPARAMETERS · pp. 14–15, Table 5 · p. 16
  • TSP relabeling repairs tours with 2-opt and canonicalizes them before comparing them with stored labels; main-table numbers use a full 2-opt scan.The 2-opt repair may be restricted to the m longest tour edges in other settings.Source: B HYPERPARAMETERS · p. 16
  • MIS training randomly peels labeled nodes with their closed neighborhoods, while TSP training applies one of the square's eight symmetries and keeps tour orientation canonical.Source: B HYPERPARAMETERS · p. 16

C DATASETS AND REFERENCES

The section documents how MIS and TSP training labels and test references are constructed. It distinguishes solver budgets and reference sources across benchmarks.

MIS references

  • ER training graphs are labeled with KaMIS at 10 seconds per graph, averaging 44.52 on training graphs and 44.63 on test graphs.Table 1 and Figures 2–3 use a longer KaMIS test reference averaging 44.87, obtained in 24 seconds per graph; Table 7 uses the 44.63 test labels.Source: C DATASETS AND REFERENCES · p. 16
  • SATLIB labels are exact, computed with Gurobi, and average 425.96 on test graphs, matching the cited papers’ KaMIS reference.The SATLIB graphs come from DIMES; ER-[700-800] and SATLIB labels are sourced as described for the MIS benchmarks.Source: C DATASETS AND REFERENCES · p. 16

TSP references

  • TSP references are recomputed: Concorde certifies the n = 500 and 1000 optima, while LKH-3 supplies the n = 10000 reference.The shipped tours were nonoptimal at n = 500 and 1000, and the n = 10000 file contained placeholder tours; all reported gaps use the recomputed references.Source: C DATASETS AND REFERENCES · p. 16

D RUNTIME PROTOCOL

Runtime comparisons measure the complete inference pipeline, with several settings requiring explicit qualifications. The section also reports learned-network parameter counts.

Runtime protocol

  • Runtime measurements cover the full pipeline from instance to final solution, including heatmap generation, decoding, and post-processing.Measurements use one RTX 4090 with released code and checkpoints, in the inference setting associated with the quoted quality number.Source: D RUNTIME PROTOCOL · p. 16

Parameter counts

  • Table 6 lists learned-network parameter counts; ours and Moco are counted from checkpoints, while other counts use stated hyperparameters or official code.The other papers do not state their parameter counts.Source: Table 6 · p. 17

Runtime protocol

  • Our runtimes use full test sets in batches of 320 rollouts, exclude the compilation batch, and report MIS K = 200 timings from six graphs in batches of two.Other batched solvers are timed on batches of two to eight instances, with batch time divided by batch size; this overstates their per-instance cost relative to paper batch sizes.Source: D RUNTIME PROTOCOL · p. 17
  • The TSP-10000 runtime is estimated at 364 seconds per instance by scaling an RTX 5090 measurement to RTX 4090 speed, because 40 rollouts exceed 24 GB.The TSP-10000 row was measured at 340 seconds on an RTX 5090 and scaled using the TSP-1000 runtime ratio.Source: D RUNTIME PROTOCOL · p. 17

E NOTES ON THE MAIN TABLES

The notes clarify the provenance and comparability of the main-table results, as well as the labels used for method types and search procedures.

Quality numbers

  • Compared-method quality values generally come from each method’s own paper and main sampling setting, with specified reruns or reimplementations filling some benchmark gaps.For TSP, printed lengths or gaps are converted against the paper’s references, and gaps using other references are recomputed against this paper’s references.Source: E NOTES ON THE MAIN TABLES · p. 17

Own instance sets

  • A dagger marks methods tested on their own generated instances; lengths and set sizes across different instances are not directly comparable, so gaps are the comparison metric.Released methods are reevaluated on the paper’s test sets where possible; unreleased code or checkpoints leave some methods on own-instance sets.Source: E NOTES ON THE MAIN TABLES · p. 17

Type and Search columns

  • Table 1’s S + self means supervised training followed by self-relabeling, while its other suffixes identify search, sampler, evolution, or meta-optimizer procedures.S + RL covers supervised pretraining followed by RL fine-tuning for CADO, and an RL constructor completed by supervised diffusion for HyCO.Source: E NOTES ON THE MAIN TABLES · pp. 17–18
  • Table 2’s MCTS, RRC, PRC, revisers, and conquer labels denote iterative neural reconstruction or search procedures; reference-solver CPU times are not comparable with GPU times.MCTS uses the search of Fu et al. (2021) at each codebase’s time limit; the reconstruction labels correspond to LEHD, SIL, GLOP, and UDC.Source: E NOTES ON THE MAIN TABLES · p. 18

F FULL ABLATIONS

Table 7 lists the variants underlying the findings reported in Section 3.5.

Full ablations

G SELF-RELABELING DETAILS

Self-relabeling outcomes depend on matching label generation and checkpoint selection to the deployment decoder. The section also tracks training-label trajectories and specifies the scope of its ablations.

G SELF-RELABELING DETAILS

  • Figure 5 tracks mean MIS label size and TSP-500 label length across self-relabeling epochs for a supervised MIS continuation and label-free chains from random initialization.Warm-started stages restart labels from the model’s first pass, producing curve steps; the dotted line marks mean solver-label values.Source: Figure 5 · p. 18, G SELF-RELABELING DETAILS · p. 18
  • One-shot-decoded relabeling yields the best one-shot checkpoint, yet sequential peeling gains 3 to 5 points on supervised models and loses 1 to 3 on relabeled models.Relabeling and selecting checkpoints with the deployment decoder removes this inversion and gives the best MIS checkpoint.Source: G SELF-RELABELING DETAILS · p. 18
  • The authors conjecture that relabeled scores favor the model’s preferred set rather than nodes safe across near-optimal sets, stranding later peeling rounds.Using the deployment decoder for relabeling and checkpoint selection removes the inversion.Source: G SELF-RELABELING DETAILS · p. 18
  • Table 7 reports gaps against KaMIS labels for ER-[700-800] MIS and against Concorde and LKH-3 for TSP-500 and TSP-10000, varying one factor at a time.Its rollout and Gumbel rows use an earlier checkpoint, so their gaps are not directly comparable with Table 1.Source: Table 7 · p. 19
Loading 2609.34585v1…