# LM-GRASP: Instance-Specific Language Models for Combinatorial Construction via Online Imitation Learning

arXiv: https://arxiv.org/abs/2607.28135 · HTML: https://mlsanity.com/paper/2607.28135/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Language-conditioned policies and VLAs, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 11 of its 27 references that are in the map.
- First posted on arXiv 30 Jul 2026.

## Placed in

- Offline RL and imitation learning from data / [Language-conditioned policies and VLAs](https://mlsanity.com/offlinerl/language-conditioned-policies-and-vlas/)

## Builds on (most cited first, 11 of 11)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [LLMs for Mathematical Modeling: Towards Bridging the Gap between Natural and Mathematical Languages](https://mlsanity.com/paper/2405.13144/) (2024)
- [Visual Reasoning and Multi-Agent Approach in Multimodal Large Language Models (MLLMs): Solving TSP and mTSP Combinatorial Challenges](https://mlsanity.com/paper/2407.00092/) (2024)
- [Revisiting OPRO: The Limitations of Small-Scale LLMs as Optimizers](https://mlsanity.com/paper/2405.10276/) (2024)
- [Learning to Deliver: a Foundation Model for the Montreal Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2403.00026/) (2024)

## Abstract (arXiv)

Machine learning for combinatorial optimization typically relies on neural constructors trained via reinforcement learning on large offline datasets for a fixed problem class-incurring high pretraining costs and generalizing poorly outside the training distribution. We propose an alternative: a metaheuristic framework that reformulates the randomized constructive phase of GRASP as an online imitation learning task, trained from scratch on each problem instance. A local search procedure acts as an expert oracle, while a decoder-only Transformer serves as the constructive policy. Unlike classical GRASP, which relies on static, myopic heuristic rules based on localized scalar costs, our approach is fully data-driven: the construction policy emerges from high-quality solutions discovered during the search itself, with no problem-specific feature engineering required. We instantiate this as LM-GRASP, a hybrid metaheuristic following an iterative learn-infer-improve cycle, training the policy online via behavioral cloning on a dynamic archive of elite trajectories-no external data or offline pretraining needed. The pipeline interfaces with the domain solely through the objective evaluator used by local search. Evaluated on the Taillard PFSP benchmark (ta51-ta60), the most discriminating block due to half its optima being unknown, LM-GRASP outperforms GPU-GRASP by 28.4 makespan units on average-comparable to the gain from GPU acceleration over sequential execution (27.2 units), though with overlapping standard deviations. This suggests instance-specific, online-trained language models are a promising, practical alternative to hand-engineered constructors, especially for landscapes resistant to classical greedy construction.