acceptodds
Withdrawn from ICLR 2027

Compute Time Scaling with Recursive Models for Combinatorial Optimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We propose Tiny Recursive Models for Combinatorial Optimization (TRM4CO), 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, TRM4CO 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 which 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.

Primary area:
optimization
Keywords:
combinatorial optimization, tiny recursive models, self-supervised learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_N7MJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes TRM4CO, a weight-tied recursive neural framework for combinatorial optimization with test-time scaling through additional recursion steps and parallel stochastic rollouts. Problem-specific encoders and decoders support TSP and MIS, while self-relabeling enables further improvement using the model’s own solutions.

Critical strengths

The framework provides a coherent adaptation of recursive models to CO, combining structural encoding, intermediate supervision, and objective-based selection, which is practically meaningful and the paper is clearly well-presented.

Critical weaknesses
  1. The gains seem to be strongly influenced by parallel sampling and problem-specific decoding, without compute-matched non-recursive controls.
  2. Runtime comparisons use different batching settings and extrapolated TSP-10000 timings. At that scale, TRM4CO matches COExpander’s gap while being approximately 15× slower, somewhat contradicting the broad lower-cost claim.
  3. Experiments are restricted to TSP and MIS, leaving broader applicability insufficiently validated. Additional tasks could include ATSP, maximum clique, Max-Cut, constrained routing problems such as CVRP/PCTSP, and structurally different problems such as KP/JSSP. Broader evaluation, or a concrete discussion of how the problem-specific encoders and decoders accommodate these tasks and constraints, would strengthen the generality claim. Related frameworks such as COExpander, DiffUCO, M²GenCO, and MaskCO provide useful comparisons.
  4. Self-relabeling comparisons lack matched training budgets, while label-free TSP performance remains substantially below supervised training.
  5. Incomplete coverage of test-time scaling baselines. Relevant approaches such as GenSCO, L2C, L2R, InViT, and NexCO exploit additional inference computation in different ways but are insufficiently covered. These methods, alongside the already included DualOpt, warrant more systematic discussion and, where applicable, quality–runtime comparisons under matched compute budgets to establish the distinct benefits of TRM4CO’s recursive depth and parallel width.
  6. The mentioned additional works are worth further discussion, if not empirically compared.

References:

  1. Generation as Search Operator for Test-Time Scaling of Diffusion-based Combinatorial Optimization(GenSCO)

  2. Learning to Insert for Constructive Neural Vehicle Routing Solver(L2C-Insert)

  3. Learning to Reduce Search Space for Generalizable Neural Routing Solver(L2R)

  4. INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer

  5. NExCO: Native Solution Expansion for Diffusion-based Combinatorial Optimization

  6. DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem

  7. A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization(DiffUCO)

  8. Problem Distributions as Tasks: Repurposing Meta Learning for Generative Combinatorial Optimization towards Multi-task Pretraining and Adaptation(M²GenCO)

  9. MaskCO: Masked Generation Drives Effective Representation Learning and Exploiting for Combinatorial Optimization

Questions for authors

see weaknesses

Reviewer_Jy4KOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This work proposes Tiny Recursive Models for Combinatorial Optimization (TRM4CO), a general neural method for combinatorial optimization that scales both depth and width.

Critical strengths

S1: The paper is well written and easy to understand.

S2: The paper compares the proposed method with comprehensive baseline methods.

Critical weaknesses

W1 (limited novelty): This work is a straightforward combination of a few existing ideas (TRM, compute scaling). The only novelty seems to be the neural architecture and the self-relabeling technique. The paper should focus on the novel ideas instead of spending substantial effort in explaining TRM and compute scaling.

W2 (unclear advantage): On the ER dataset, the proposed method still does not outperform quite a few baselines even though it is already scaling compute substantially. Consequently, the advantage of the proposed method seems a bit unclear to me.

W3 (ablation on depth vs width): The efficacy of depth scaling vs width scaling is a bit unclear. There should be more detailed ablation studies on depth scaling and width scaling separately.

Questions for authors

See weaknesses.

Reviewer_prt1OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces TRM4CO, adapting TRM to TSP and MIS. It combines a shared backbone architecture with problem-specific encodings and decoders, and scales test-time computation through recursion depth and parallel rollouts. It also evaluates self-relabeling to improve training labels. The method reports strong results on TSP-500 and TSP-1000 and competitive MIS performance at high compute budgets.

Critical strengths
  • The paper applies a shared recursive backbone to two distinct CO problems and evaluates problem-specific design choices through ablations. (§2, Table 7)
  • It reports the lowest gaps among the compared learned solvers on TSP-500 and TSP-1000. It also examines solution quality across inference budgets. (Table 2, Figure 2)
Critical weaknesses
  1. The small-model claim lacks sufficient support.

    TRM4CO has more parameters than several baselines. Using few shared blocks does not itself establish lower model capacity or reduced overfitting. Without model-size ablations or generalization analysis, the claim that a small network is essential remains unsupported. (Table 6, §3.5)

  2. The independent benefit of recursive refinement is insufficiently established.

    Figure 2 shows performance changes with depth and width. However, it does not clearly establish whether deeper refinement is preferable to additional sampling under comparable compute budgets. The ablations do not sufficiently separate the contributions of model capacity, recursion, decoding, and inference budget. (Figure 2, Table 7)

  3. The contribution of self-relabeling is difficult to interpret.

    The MIS improvement comes from a continuation that includes additional training. Without a matched continuation on unchanged labels, the effects of better labels and longer training cannot be separated. It is also unclear whether self-relabeling has a specific connection to the recursive architecture or is a general training extension. (Table 3, Appendix B)

Questions for authors
  1. Does “small” refer to the number of shared blocks or total model capacity? What evidence connects model size to overfitting or generalization?
  2. Under comparable inference budgets, does deeper recursion outperform additional shorter rollouts? Can the benefit of recursive refinement be isolated?
  3. Is there a control that continues training on unchanged labels for the same duration as self-relabeling?
  4. Is self-relabeling intended as a general training extension, or is a specific interaction with recursion claimed? If the latter, what evidence supports it?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.