Research map / Probabilistic and scientific modeling / Bayesian optimization

Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks

NeurIPS 2026 · Probabilistic and scientific modeling › Bayesian optimization · approach: Offline black-box optimization with surrogates · 0 citations (OpenAlex)

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 black-box NCO policies (POMO, LEHD) on TSP/CVRP into LLM-evolved executable heuristic banks combined by a state-dependent attention router, using alternating hybrid textual-numerical gradient descent and bank add/drop.

Problem

Neural combinatorial optimization policies are black boxes; standard concept bottleneck models lack a fixed concept vocabulary and do not fit sequential, state-dependent construction decisions.

Approach

Use LLM-generated executable heuristics as the bottleneck concepts, mix their per-step action distributions with a state-conditioned router, and jointly optimize code (via TextGrad-style LLM revisions) and router weights (via SGD), while adapting bank size through fault-targeted add and redundancy-based drop.

Key results

• Under search, the student's gap to POMO is 0.03% (TSP-50) to 1.25% (CVRP-100), and to LEHD 0.40% (TSP-100) to 2.16% (CVRP-100).
• On zero-shot OOD POMO-TSP-500, the student beats the teacher by -15.01% (greedy) and -14.32% (search).
• On POMO-CVRP-500 the student leads by -13.57% (greedy) and -15.22% (search).

Surprising findings

• Distilled student substantially outperforms its POMO teacher on larger OOD instances (TSP-500, CVRP-500), suggesting the bottleneck filters overfitted patterns.
• POMO-distilled bank is phase-based while LEHD-distilled bank is geometry-based on TSP.

Limitations

• The router remains a black-box neural network, so the student is not fully transparent.
• The distilled surrogate cannot guarantee a perfect proxy for the original policy.
• Heavy reliance on LLM API calls (e.g., ~5,471 calls and ~30M tokens for LEHD-TSP-100); weaker LLMs struggle with complex CVRP code.

Experimental setup

Datasets: TSP-50 TSP-100 CVRP-50 CVRP-100 TSP-500 CVRP-500

Benchmarks: TSP-50 TSP-100 CVRP-50 CVRP-100 TSP-500 CVRP-500

Metrics: mean tour cost optimality gap (%) top-1 accuracy

Baselines: static-key routing (ablation) numerical-gradient-only (ablation) fixed-capacity bank (ablation)

Builds on: Concept Bottleneck Models TextGrad POMO LEHD FunSearch EoH

Closest papers by meaning

• Probing Neural Combinatorial Optimization Models (NeurIPS 2025 · similarity 0.89)
• Teacher-Aware Evolution of Heuristic Programs from Learned Optimization Policies (NeurIPS 2026 · similarity 0.87)
• Complexity Scaling Laws for Neural Models using Combinatorial Optimization (NeurIPS 2025 · similarity 0.87)
• Evolution Fine-Tuning: Learning to Discover Across 371 Optimization Tasks (NeurIPS 2026 · similarity 0.86)
• Measuring What Matters: Synthetic Benchmarks for Concept Bottleneck Models (NeurIPS 2026 · similarity 0.86)
• EvoOptiGraph: Weakness-Driven Coevolution via Graph-Based Structural Generation for Optimization Modeling (NeurIPS 2026 · similarity 0.86)