Technical Summary: LLM-as-Trainer for Multi-Task Vehicle Routing Solvers

1. Problem Statement

Vehicle Routing Problems (VRPs) encompass a wide variety of combinatorial optimization variants (e.g., Capacitated VRP, VRP with Time Windows, Backhaul constraints). While neural solvers based on deep reinforcement learning have shown promise in generating feasible solutions efficiently, early approaches typically required training separate models for each specific constraint combination. This lack of scalability is problematic given the existence of over 60 VRP variants in real-world applications.

Multi-task neural solvers aim to unify these variants within a single model to avoid separate training. However, a significant challenge remains: different VRP variants possess varying levels of optimization difficulty. Existing multi-task training methods often coordinate shared parameters through loss or gradient balancing but lack explicit stage-wise feedback regarding the relative performance of different tasks during training. Consequently, models may become biased toward easier variants, limiting the overall solution quality. While meta-learning offers adaptive training, it typically relies on bi-level optimization, which incurs substantial computational costs and additional gradient updates.

2. Methodology: LLM-as-Trainer (LaT)

The authors propose LaT (LLM-as-Trainer), a plug-and-play training paradigm that utilizes a pretrained Large Language Model (LLM) as an external trainer to regulate the joint training of multi-task neural solvers. The core innovation lies in using the LLM to analyze cross-task validation metrics and generate a stage-wise guidance vector without modifying the solver's architecture or requiring bi-level optimization.

2.1 Training Framework

LaT operates on a standard autoregressive Transformer encoder-decoder architecture (e.g., POMO, CaDA, ReLD) but introduces a lightweight side branch at each encoder layer. The process follows these steps:

1. Cross-Task Validation: At predefined intervals (every $T_{ctrl}$ epochs), the current policy is evaluated on a fixed validation set for all 16 VRP variants.
2. State Construction: The system computes the relative reference gap ($\eta_{r,k}$) for each task $k$ against a pre-computed reference solution (generated by HGS or OR-Tools). It also tracks the change in this gap ($\Delta \eta_{r,k}$) and maintains a history of recent validation records.
3. LLM Guidance Generation: This structured training state (including task constraints, current gaps, gap changes, and historical trends) is formatted into a prompt and fed to a frozen, pretrained LLM (specifically GLM-5.1 in the experiments). The LLM outputs a 5-dimensional guidance vector $\gamma_r = [\gamma_C, \gamma_O, \gamma_B, \gamma_L, \gamma_{TW}]$, where each dimension corresponds to one of the five elementary constraints (Capacity, Open Route, Backhaul, Route-Length, Time Window).
4. Injection into Solver: During subsequent training epochs, the guidance vector $\gamma_r$ is concatenated with the current task's binary constraint vector $z_k$. This combined vector is injected into a lightweight side branch at every encoder layer. The side branch output is added to the backbone output via a learnable coefficient $\alpha$.
5. Policy Optimization: The solver is updated using standard policy gradient methods (e.g., POMO-style). The LLM receives no gradients and is not queried during inference.

2.2 Inference

After training concludes, the final guidance vector is fixed, and the LLM is removed. The deployed solver retains only the learned side branches and the fixed guidance vector, requiring no LLM API calls and introducing negligible computational overhead.

3. Key Contributions

The paper highlights three primary contributions:

• Novel Training Paradigm: LaT is the first training paradigm to introduce a pretrained LLM as an external trainer specifically for multi-task vehicle routing solvers. It explicitly incorporates cross-task validation performance into the policy optimization loop.
• Lightweight Guidance Mechanism: The authors design a mechanism that generates a stage-wise guidance vector from validation metrics. This vector is combined with task constraints and injected into encoder layers, providing additional training information without the computational burden of bi-level optimization or inner-loop updates.
• Plug-and-Play Generality: The method is designed to be integrated with existing neural solvers (demonstrated on ReLD and CaDA backbones) without altering the core autoregressive policy or decoder architecture.

4. Experimental Results

Experiments were conducted on 16 VRP variants formed from five elementary constraints, with problem sizes of 50 and 100 nodes.

• Performance on Trained Variants: LaT variants (LaT-ReLD and LaT-CaDA) consistently achieved lower relative reference gaps compared to their backbone models across all six training variants. For instance, LaT-CaDA reduced the mean gap on trained variants from 1.810% to 1.669%.
• Zero-Shot Generalization: On the remaining ten unseen VRP variants, LaT demonstrated strong generalization. LaT-CaDA outperformed the baseline CaDA in all 20 unseen settings (50 and 100 nodes), reducing the mean gap from 5.490% to 5.067%.
• Comparison with SOTA: LaT variants achieved the lowest gaps in the majority of settings compared to other state-of-the-art multi-task solvers (e.g., MVMoE, CCL, PoMtVRS).
• Efficiency: The method introduced negligible inference time overhead (3–4 seconds for 50-node instances), comparable to the backbones. Training time increased by less than 1.5% due to periodic LLM calls.
• Ablation Studies:
  • Removing the LLM-generated guidance (replacing it with a fixed vector) degraded performance, confirming the value of the adaptive guidance.
  • Removing the task constraint vector also worsened performance, showing the necessity of explicit task information.
  • Replacing the LLM with an MLP-based guidance generator resulted in higher gaps, suggesting the improvement stems from the LLM's reasoning capabilities rather than just increased model capacity.
  • Injecting guidance after every encoder layer (LaT EncAll) proved superior to injecting it only at the input, output, or decoder context.

5. Significance and Claims

The paper claims that LaT effectively addresses the limitation of existing multi-task solvers by explicitly responding to current cross-task performance differences. By leveraging a frozen LLM as a periodic "trainer," the method provides stage-wise feedback that guides the neural solver to balance learning across variants of differing difficulty.

The authors emphasize that LaT improves solution quality on both trained and unseen variants while maintaining inference efficiency. They note that while LaT shows consistent improvements, its effectiveness can depend on the specific backbone architecture (e.g., LaT-CaDA showed more consistent gains than LaT-ReLD on unseen variants). The paper concludes that this approach offers a general and effective training paradigm for complex multi-constraint scenarios, though future work could explore broader constraint sets and more consistent guidance mechanisms across diverse solvers.