Research map / Reinforcement learning / Visual and representation RL
INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer
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.
Proposes INViT, a Transformer routing solver using invariant nested local views around the last visited node, trained with REINFORCE plus augmentation to generalize across TSP/CVRP sizes and distributions.
Problem
Neural constructive solvers for TSP and CVRP generalize poorly to larger scales and unseen node distributions, due to embedding aliasing and interference from irrelevant distant nodes.
Approach
Encode multiple nested k-NN views around the last visited node with separate single-view encoders, add an invariant normalization/projection layer, and aggregate views channel-wise in a multi-view decoder that only attends to candidate nodes (the smallest view).
Key results
- INViT-3V reaches 6.46% gap on TSP-5000 uniform and 6.01% on TSP-10000 uniform, versus POMO's 61.81% and 84.99%.
- On CVRP-5000 uniform, INViT-3V gets 5.32% gap, versus 277.63% for POMO and 36.17% for Omni-VRP.
- On TSPLIB instances with more than 10000 nodes, INViT-3V gets 9.11% average gap, versus 26.73% for ELG-v1 and 43.61% for LEHD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace one sparsified encoder with a global-information encoder (ablation) | INViT-2V · TSP-10000 | gap: 8.01% -> 15.58% | Hurt |
| remove invariant layers (ablation) | INViT-2V · TSP-10000 | gap: 8.01% -> 66.38% | Hurt |
| reduce MHA heads from 8 to 4 (ablation) | INViT-2V · TSP-10000 | gap: 8.01% -> 8.41% | No clear effect |
| reduce augmented instances from 8 to 4 (ablation) | INViT-2V · TSP-10000 | gap: 8.01% -> 8.13% | No clear effect |
| remove training data augmentation (ablation) | INViT-2V · TSP-10000 | gap: 8.01% -> 8.93% | No clear effect |
| remove training data augmentation (ablation) | INViT-3V · TSP-10000 | gap: 7.86% -> 8.28% | No clear effect |
| train on size 50 rather than size 100 (ablation) | INViT-2V · TSP-10000 | gap: 8.01% -> 9.47% | Hurt |
| train on size 50 rather than size 100 (ablation) | INViT-3V · TSP-10000 | gap: 7.86% -> 8.85% | Hurt |
| use one single-view encoder instead of nested views (ablation) | INViT · TSP-10000 | gap: 7.86% -> 15.14% | Hurt |
| add a fourth single-view encoder (ablation) | INViT-3V · TSP-10000 | gap: 7.86% -> 7.64% | Helped |
| use INViT-3V rather than the strongest reported baseline | routing solvers · TSPLIB >10000 nodes | gap: 26.73% -> 9.11% | Helped |
| use INViT-3V rather than the strongest reported baseline | routing solvers · CVRPLIB Set-X >500 nodes | gap: 11.21% -> 10.21% | Helped |
Surprising findings
- Attention scores of farther nodes accumulate to near 1 as instance size grows, indicating distant nodes dominate the embedding in full-graph attention encoders.
- On small and medium instances such as TSP-100 and CVRP-500, INViT does not beat the best baseline (e.g., POMO/LEHD/Omni-VRP).
Limitations
- Underperforms baselines on small and medium-scale instances such as TSP-100 and CVRP-500.
- Baseline models evaluated with pretrained checkpoints from authors, and some baselines run out of memory on large instances.
- Reference optima for large instances come from heuristics (LKH3, HGS), not exact solutions.
Experimental setup
Datasets: uniform random TSP-100 and CVRP-100 instances (training) TSPLIB CVRPLIB Set-X
Benchmarks: MSVDRP TSPLIB CVRPLIB Set-X
Metrics: optimality gap (%) inference time
Baselines: POMO Omni-TSP Omni-VRP PointerFormer ELG-v1 LEHD BQ-NCO
Builds on: POMO Attention Model LEHD PointerFormer
Closest papers by meaning
- SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solver (NeurIPS 2026 · similarity 0.86)
- Rethinking Light Decoder-based Solvers for Vehicle Routing Problems (ICLR 2025 · similarity 0.86)
- Memory-Enhanced Neural Solvers for Routing Problems (NeurIPS 2025 · similarity 0.86)
- GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time (AAAI 2024 · similarity 0.85)
- SiT: Symmetry-invariant Transformers for Generalisation in Reinforcement Learning (ICML 2024 · similarity 0.85)
- Learning to Handle Complex Constraints for Vehicle Routing Problems (NeurIPS 2024 · 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.