진화하는 프로그래밍 방식의 병목 현상을 통한 신경망 기반 조합 최적화 해석

Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks

신경망 기반 조합 최적화(NCO)는 뛰어난 성능을 보이지만, 블랙박스 특성으로 인해 실제 적용과 과학적인 분석에 어려움이 있습니다. 기존의 개념 병목 모델(CBM)과 같은 해석 도구는 NCO의 동적인 의사 결정 과정, 상태 의존성, 그리고 명확한 개념 어휘 정의 부족으로 인해 적합하지 않습니다. 이러한 간극을 해소하기 위해, 본 연구에서는 인간이 이해할 수 있는 프로그램 포트폴리오로 블랙박스 NCO 모델을 변환하여 NCO 정책을 해석하는 최초의 프레임워크인 진화하는 프로그래밍 방식의 병목 현상(EPB)을 제안합니다. EPB는 LLM을 사용하여 프로그램들을 자율적으로 생성하고, 각 프로그램의 단계별 행동 분포를 병목 지점으로 활용합니다. EPB는 반복적인 방식으로 작동하며, 블록 I에서는 프로그램 은행의 용량을 고정하고 텍스트 기반 및 수치 기반 그래디언트 하이브리드 방식을 사용하여 학생 네트워크 업데이트와 LLM 기반 프로그램 수정에 대한 가중치를 조절합니다. 블록 II에서는 오류 분석을 통해 프로그램 은행 용량을 동적으로 조정하여 필요한 경우 확장을 수행하고, 불필요한 부분을 제거합니다. 광범위한 실험 결과는 EPB의 효과성과 다양한 적용 가능성을 입증하며, 변환된 프로그램 포트폴리오가 원래 성능과 거의 일치하는 것을 보여줍니다. 또한, EPB는 NCO의 행동이 최적화 단계에 따라 변화하며, 기존 휴리스틱 방법들의 조합으로 근사될 수 있음을 밝혀냅니다. 본 연구는 해석 가능한 NCO 분야를 발전시키고, EPB가 순차적 의사 결정 모델을 해석하는 데 유망한 도구임을 제시합니다.

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.