Research map / Architectures and efficiency / RNNs and normalization
Distilling Autoregressive Models to Obtain High-Performance Non-autoregressive Solvers for Vehicle Routing Problems with Faster Inference Speed
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Distills Transformer-based autoregressive VRP solvers (AM, POMO, TM) into non-autoregressive students via guided knowledge distillation, achieving 4-5x faster inference with a 2-3% optimality drop.
Problem
Autoregressive neural VRP solvers give high-quality tours but have high inference latency due to sequential decoding, while existing NAR solvers are fast but notably less accurate and mostly limited to TSP.
Approach
Convert the AR decoder into a parallel NAR form (removing action-history context, positional encoding and masks, and scoring edges via node-pair tightness) and train it by KL distillation from the AR teacher's temperature-sharpened action distributions, with the teacher's actions guiding the student's decoding order.
Key results
- GNARKD students run 4-5x faster than their AR teachers (average acceleration 4.42x for n=50 and 6.03x for n=100) with an average learning gap of 1.61% (n=50) and 3.25% (n=100).
- GNARKD-TM achieves 0.01% optimality gap on TSP-50 versus 0.02% for TM teacher and reaches state-of-the-art among the compared models on TSP-50.
- Guided KD yields 0.36%, 0.01%, and 0.05% optimality gap for GNARKD-AM, -TM, -POMO with beam search 1000 on TSP-50, outperforming SL (7.35-9.30%) and RL (1.83-2.42%) training.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| distill AM into GNARKD-AM | AM · TSP-50 | average length: 5.714 -> 5.706 | Helped |
| distill TM into GNARKD-TM | TM · TSP-50 | average length: 5.690 -> 5.689 | Helped |
| distill AM into GNARKD-AM | AM · CVRP-50 | average length: 10.602 -> 10.754 | Hurt |
| distill POMO into GNARKD-POMO | POMO · CVRP-100 | average length: 15.750 -> 16.240 | Hurt |
| use guided KD instead of supervised learning (ablation) | GNARKD students · TSP-50 | optimality gap: 9.30% -> 0.36%; 7.69% -> 0.01%; 7.35% -> 0.05% | Helped |
| use guided KD instead of reinforcement learning (ablation) | GNARKD students · TSP-50 | optimality gap: 2.42% -> 0.36%; 1.83% -> 0.01%; 1.99% -> 0.05% | Helped |
| raise distillation temperature from 0.1 to 0.5 or 1 (ablation) | GNARKD-TM · TSP-50 | performance | No clear effect |
| raise distillation temperature to 5 or 10 (ablation) | GNARKD-TM · TSP-50 | performance | Hurt |
| use GNARKD-TM instead of TM | TM · TSP-50 | average time (Sec): 0.422 -> 0.043 | Helped |
| use GNARKD-AM instead of AM | AM · TSPLIB 20 instances | average optimality gap: 6.93% -> 5.88% (Sampling~(B=2000)); 7.96% -> 10.98% (Greedy) | Mixed |
Surprising findings
- Some GNARKD students (GNARKD-AM and GNARKD-TM on TSP-50) achieve slightly higher solution quality than their AR teachers despite full supervision from the teacher.
- Lowering the distillation temperature to 0.1 made students more confident, while high temperatures (5, 10) markedly degraded performance.
Limitations
- Performance is bounded by the teacher; students cannot exceed their AR teacher's quality in principle.
- Constraint handling for CVRP is done via post-processing of the output matrix, and the NAR CVRP models do not outperform baselines in solution quality (e.g., 2-3% or larger gaps on CVRP).
- The current version may not perform well with complex constraints.
Experimental setup
Datasets: synthetic uniform TSP and CVRP instances TSPLIB (20 instances, 51-159 nodes, evaluation only)
Benchmarks: TSP-50 TSP-100 CVRP-50 CVRP-100 TSPLIB (20 instances)
Metrics: optimality gap average length inference time acceleration ratio learning gap
Baselines: Concorde LKH3 MDAM GCN NAR4TSP AM POMO TM
Builds on: Attention Model POMO Transformer-based AR TSP model (TM) NAR4TSP
Closest papers by meaning
- MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver (NeurIPS 2025 · similarity 0.88)
- MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts (ICML 2024 · similarity 0.87)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.86)
- Memory-Enhanced Neural Solvers for Routing Problems (NeurIPS 2025 · similarity 0.86)
- Adversarial Generative Flow Network for Solving Vehicle Routing Problems (ICLR 2025 · similarity 0.85)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.