# Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks

arXiv: https://arxiv.org/abs/2606.19741 · HTML: https://mlsanity.com/paper/2606.19741/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 47 references that are in the map.
- First posted on arXiv 18 Jun 2026.

## Builds on (most cited first, 30 of 32)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Visualizing and Understanding Convolutional Networks](https://mlsanity.com/paper/1311.2901/) (2013)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Interpretability Beyond Feature Attribution: Quantitative Testing with Concept Activation Vectors (TCAV)](https://mlsanity.com/paper/1711.11279/) (2017)
- [Concept Bottleneck Models](https://mlsanity.com/paper/2007.04612/) (2020)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Post-hoc Concept Bottleneck Models](https://mlsanity.com/paper/2205.15480/) (2022)
- [TextGrad: Automatic "Differentiation" via Text](https://mlsanity.com/paper/2406.07496/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Causal Abstraction: A Theoretical Foundation for Mechanistic Interpretability](https://mlsanity.com/paper/2301.04709/) (2023)
- [Programmatically Interpretable Reinforcement Learning](https://mlsanity.com/paper/1804.02477/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [Efficient Active Search for Combinatorial Optimization Problems](https://mlsanity.com/paper/2106.05126/) (2021)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [Discover and Cure: Concept-aware Mitigation of Spurious Correlation](https://mlsanity.com/paper/2305.00650/) (2023)
- [VLG-CBM: Training Concept Bottleneck Models with Vision-Language Guidance](https://mlsanity.com/paper/2408.01432/) (2024)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [Interpretable and Explainable Logical Policies via Neurally Guided Symbolic Abstraction](https://mlsanity.com/paper/2306.01439/) (2023)
- [Concept Bottleneck Large Language Models](https://mlsanity.com/paper/2412.07992/) (2024)
- [Learning to Intervene on Concept Bottlenecks](https://mlsanity.com/paper/2308.13453/) (2023)
- [Opening the AI black box: program synthesis via mechanistic interpretability](https://mlsanity.com/paper/2402.05110/) (2024)

## Abstract (arXiv)

Neural Combinatorial Optimization (NCO) achieves strong performance, yet its black-box nature remains a key roadblock to deployment and scientific diagnosis. Standard interpretability tools, such as Concept Bottleneck Models (CBMs), are ill-equipped for NCO, whose decisions are dynamic, state-dependent, and lack proper concept vocabulary definition. To close this gap, we introduce Evolving Programmatic Bottlenecks (EPB), to our knowledge, the first framework for interpreting NCO policies by distilling black-box NCO models into human-readable program portfolios. EPB employs an LLM to autonomously evolve a bank of programs, where each program's per-step action distribution serves as the bottleneck. EPB works through an iterative framework: Block I fixes program bank capacity and introduces a hybrid textual-numerical gradient descent scheme that couples numerical gradients for student router updates and textual gradients for LLM-based program revision; Block II dynamically adapts bank capacity via fault-targeted expansion and redundancy pruning. Extensive experiments demonstrate EPB's effectiveness and broad applicability, where the distilled program portfolios largely match original performance. EPB also reveals that NCO behavior shifts across optimization stages and can be approximated as a composition of classic heuristic variants. Our work advances interpretable NCO and establishes EPB as a promising tool for interpreting sequential decision-making models.