Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks

Neural Combinatorial Optimization (NCO) models, such as those used for routing and scheduling, achieve high performance but operate as black boxes. This lack of transparency hinders their deployment in critical industrial settings. The authors seek to bridge this gap by creating an interpretability framework that translates these opaque neural policies into human-understandable, executable programs.

To address the limitations of standard Concept Bottleneck Models (CBMs)—which typically rely on static, predefined concepts—the authors introduce Evolving Programmatic Bottlenecks (EPB). EPB treats the decision policy as a mixture of executable heuristics. It uses an iterative, two-block optimization framework:

1. Block I (Hybrid Optimization): At a fixed bank capacity, the model uses a hybrid approach. It employs numerical gradient descent (SGD) to update a routing network that decides which heuristic to use at each state, while simultaneously using TextGrad—a technique that leverages LLMs to provide textual feedback—to rewrite and improve the code of the heuristics themselves.
2. Block II (Capacity Evolution): The framework dynamically adjusts the number of heuristics in the bank. It adds new specialists to address failure modes that the current bank cannot explain and prunes redundant heuristics to keep the portfolio concise and interpretable.

EPB successfully distills complex NCO models (like POMO and LEHD) into program portfolios that match the original performance while providing clear, stage-wise insights into the decision-making process. For instance, in Vehicle Routing Problems (VRP), the model reveals a shift from sector-based partitioning to capacity-aware selection as the construction progresses. Furthermore, the distilled student models often exhibit better out-of-distribution generalization than the original black-box teachers, suggesting that the programmatic bottleneck helps filter out overfitted noise.