Research map / Label-efficient and robust learning / Recognition and long-tail
Probing Neural Combinatorial Optimization Models
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.
Probes the embeddings of AM, POMO, and LEHD neural combinatorial optimization models with linear probing tasks and introduces CS-Probing, which analyzes probe coefficient magnitudes and significance to reveal inductive biases and generalization mechanisms.
Problem
Neural combinatorial optimization (NCO) models for routing problems are black boxes; their learned representations and decision rationale are poorly understood, which hinders research and practical deployment.
Approach
Adapt linear probing from NLP/CV to NCO by designing CO-specific probing tasks (Euclidean distance, avoidance of myopic decisions, demand sums, same-route) and propose CS-Probing, which inspects both coefficient magnitudes and statistical significance to identify key embedding dimensions linked to generalization.
Key results
- LEHD's decoder embeddings reach R^2 about 0.94 for Euclidean distance probing (w/o interaction terms), while AM-Init stays near 0.
- LEHD's top-2 embedding dimensions (31 and 97) retained alone yield a 100-node optimality gap of 0.65% versus 0.57% for the full 128 dimensions; zeroing them raises the gap above 60%.
- Adding L1-style sparsity regularization on LEHD final embeddings (lambda=1e-6) lowers TSP1000 gap from 3.17% to 2.87%, with TSPLib gap from 5.26% to 4.94%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add interaction terms to AM-Enc-l3 probe inputs | AM representations, TSP-20 Task 1 · TSP-20 | R²: 0.2529 -> 0.9282 | Helped |
| Add interaction terms to AM-Enc-l3 probe inputs | AM representations, TSP-20 Task 2 · TSP-20 | AUC: 0.76 -> 0.83 | Helped |
| Add interaction terms to LEHD-Dec-l6 probe inputs | LEHD representations, TSP-20 Task 1 · TSP-20 | R²: 0.9418 -> 0.9415 | No clear effect |
| Retain only dimensions 31 and 97 rather than all 128 dimensions | LEHD · TSP-1000 | Optimality gap: 3.17% -> 3.56% | Hurt |
| Zero dimensions 31 and 97 (ablation) | LEHD · TSP-100 | Optimality gap: 0.57% -> 60.43% | Hurt |
| Zero dimension 31 (ablation) | LEHD · TSP-100 | Optimality gap: 0.57% -> 0.90% | Hurt |
| Zero dimension 97 (ablation) | LEHD · TSP-100 | Optimality gap: 0.57% -> 1.80% | Hurt |
| Zero dimensions 98 and 126 (ablation) | LEHD · TSP-100 | Optimality gap: 0.57% -> 0.62% | No clear effect |
| Add final-layer embedding sparsity regularization (λ=1e-4) | LEHD · TSP-200 generalization | Optimality gap: 0.86% -> 0.73% | Helped |
| Add final-layer embedding sparsity regularization (λ=1e-6) | LEHD · TSP-1000 generalization | Optimality gap: 3.17% -> 2.87% | Helped |
| Add final-layer embedding sparsity regularization (λ=1e-6) | LEHD · TSPLib generalization | Optimality gap: 5.26% -> 4.94% | Helped |
| Use stronger final-layer embedding sparsity regularization (λ=1e-3) | LEHD · TSPLib generalization | Optimality gap: 5.26% -> 8.61% | Hurt |
Surprising findings
- Keeping only two of 128 LEHD output dimensions still gives nearly full-model performance on TSP100 through TSP1000.
Limitations
- Preliminary evidence from a single regularization experiment; the sparsity gains are small and not uniform across settings.
- Analysis focuses on three routing models and mainly on TSP; findings may not transfer to other NCO architectures.
- Probing tasks are designed by hand for CO and do not establish causal mechanisms beyond ablation.
Experimental setup
Datasets: randomly generated TSP instances (20, 100, 200 nodes) randomly generated CVRP instances (20, 100 nodes) TSPLib
Benchmarks: TSP20 TSP100 TSP200 TSP500 TSP1000 TSPLib
Metrics: R^2 AUC optimality gap coefficient significance level
Baselines: AM POMO LEHD DIFUSCO
Builds on: linear probing AM POMO LEHD
Closest papers by meaning
- Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks (NeurIPS 2026 · similarity 0.89)
- BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization (ICML 2025 · similarity 0.88)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.87)
- Complexity Scaling Laws for Neural Models using Combinatorial Optimization (NeurIPS 2025 · similarity 0.87)
- Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees (NeurIPS 2025 · similarity 0.85)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.85)
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.