Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks

While Neural Combinatorial Optimization (NCO) achieves strong performance, its black-box nature remains a key roadblock. Standard interpretability tools, such as Concept Bottleneck Models (CBMs), are ill-equipped for NCO, whose decisions are dynamic, state-dependent, and lack proper concept definition. To close this gap, we introduce Evolving Programmatic Bottlenecks (EPB), the first framework that distills black-box NCO models into human-readable program portfolios. EPB extends CBMs for sequential decision problems: it employs an LLM to autonomously evolve a bank of programs, where each program's per-step action distribution serves as the bottleneck. We realize this through an iterative framework: Block I fixes program bank capacity and introduces a hybrid textual-numerical gradient descent scheme to backpropagate gradients across the student router model and the LLM in-context learning; Block II dynamically adapts bank capacity via fault-targeted boosting and redundancy pruning. Extensive experiments demonstrate EPB's effectiveness and broad applicability, where the interpreted 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 complex sequential decision-making models.