Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks

원문 초록

While Neural Combinatorial Optimization (NCO) achieves strong performance, its interpretability remains an open question. In this paper, we introduce Evolving Programmatic Bottlenecks (EPB), the first post-hoc, surrogate-based interpretability method for NCO, which explains a black-box policy by distilling it into an interpretable behavior surrogate. A natural surrogate is a Concept Bottleneck Model (CBM), yet standard concepts are input attributes, whereas NCO is better explained by decision rules that are hard to predefine. EPB thus uses LLMs to evolve a bank of programmatic decision rules as concepts, each producing an action distribution, where a learned state-dependent router then mixes them to form the surrogate action. We optimize EPB through an iterative framework: Block I fixes the bank size and introduces the hybrid textual-numerical gradient descent to jointly optimize the textual programs and the numerical router; Block II adapts the bank size via failure-targeted expansion and redundancy pruning. Extensive experiments demonstrate that the EPB surrogate closely matches the teacher's behavior and solution quality. We then analyze the distilled rules, reveal several NCO decision patterns, and verify the rules' faithfulness to the surrogate's decisions. Moreover, the surrogate allows targeted program edits that improve its generalization beyond the teacher. Our work advances interpretable NCO and establishes EPB as a promising direction for interpreting complex learned decision-making policies.