New Framework Interprets Black-Box Neural Combinatorial Optimization

Neural Combinatorial Optimization (NCO) models often achieve high performance but are difficult to understand due to their black-box nature, hindering their deployment and diagnostic analysis. Traditional interpretability tools are inadequate for NCO's dynamic and state-dependent decision-making processes. This research addresses this challenge by proposing Evolving Programmatic Bottlenecks (EPB), a framework designed to interpret NCO policies. EPB works by distilling complex NCO models into a collection of human-readable programs. It leverages a Large Language Model (LLM) to autonomously develop these programs, where each program's step-by-step action distribution acts as a bottleneck for interpretation. The framework operates iteratively, using a hybrid gradient descent scheme to update a student router and revise programs, while also dynamically adjusting the program bank's capacity. Experiments demonstrate EPB's effectiveness and broad applicability, showing that the distilled program portfolios can largely match the original NCO performance. The framework also reveals that NCO behavior evolves across different optimization stages and can be approximated by a combination of classic heuristic variants. This work significantly advances interpretable NCO and positions EPB as a valuable tool for understanding sequential decision-making models.