A graph-aware tiny recursive model that iterates on a latent state with adaptive halting and needs only a lightweight problem-specific decoder is proposed, which achieves a better balance between solution quality and inference speed on both the Traveling Salesman Problem and the Maximum Independent Set problem.
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\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.
The Dual-GNN Multilevel Coarsening framework uses learning to guide multilevel graph coarsening while retaining combinatorial search for final decision making and achieves the best mean solution quality among all evaluated methods.
This work proposes Hybrid Neural Solver for Combinatorial Optimization (HyCO), a hybrid inference algorithm that constructs a solution prefix with an RL solver and adaptively switches to a conditional DM to complete the remaining decisions, and designs a lightweight adaptive trigger that combines policy entropy and RL-...
Yu-Heng Li, Dian-Qiang Yang, Hai-Peng Chen et al.· 1 citation
Discrete diffusion models have emerged as a powerful paradigm for solving combinatorial optimization (CO) problems on graphs by learning to sample high-quality solutions. A common inference-time approach is to generate multiple candidate solutions independently and return the best-performing sample, improving solution...
Neural algorithmic reasoning, or aligning a neural network with an algorithmic paradigm, has emerged as an approach to solving polynomial-time-solvable and computationally harder combinatorial optimization problems. We propose a new message-passing framework based on the Chambolle-Pock Primal--Dual Hybrid Gradient (PDH...
Samantha Chen, Jesse He, Coleman Clougherty et al.· 0 citations
This work investigates a data-driven selection of the L-BFGS memory parameter (mem) for large-scale unconstrained optimization and proposes a two-stage hybrid machine-learning framework that predicts intermediate solver quantities and then forecasts runtime for each candidate memory value.
Yu-Chen Gao· Journal of Computing, Data,...· 0 citations
When optimizing computing architecture for specific computationally intensive tasks, such as evaluating or training a neural network, it is important to identify what computational subtasks will offer the greatest decrease in cost (e.g., wall clock time or energy usage). This problem is known as Hardware-Software (HS)...
Cameron Ibrahim, S. Ferdous, Erdal Mutlu et al.· 0 citations
Related blog posts
MIT News · Artificial Intelligence· news.mit.eduNov 17, 2026
By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.
Microsoft Research Blog· microsoft.comNov 16, 2026
AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.
MIT News · Artificial Intelligence· news.mit.eduNov 13, 2026