엄격한 제약과 유연한 생성의 만남: LLM 기반 조합 최적화를 위한 실행 가능성 보장

Hard Constraints Meet Soft Generation: Guaranteed Feasibility for LLM-based Combinatorial Optimization

대규모 언어 모델(LLM)은 조합 최적화(CO)를 위한 유망한 범용 솔버로 부상했으나, 실제 배포에 필수적인 솔루션의 실행 가능성(feasibility)을 보장하는 메커니즘이 근본적으로 부족하다. 본 연구에서는 세 가지 핵심 혁신을 통해 100% 실행 가능성을 보장하는 프레임워크인 FALCON을 소개한다. (i) 문법 제약 디코딩(grammar-constrained decoding)은 구문적 타당성을 강제하고, (ii) 실행 가능성 복구 계층(feasibility repair layer)은 의미론적 제약 위반을 수정하며, (iii) 적응형 Best-of-N 샘플링은 추론 연산 자원을 효율적으로 할당한다. 기반 LLM을 학습시키기 위해 우리는 BOPO(Best-anchored Objective-guided Preference Optimization)를 도입하였다. 이는 목적 함수 격차(objective gap)에 따라 선호 쌍의 가중치를 조정하여, 인간 레이블 없이도 밀도 높은 지도(supervision)를 제공한다. 이론적으로 우리는 BOPO의 수렴성을 증명하고 복구 과정에서 발생하는 품질 손실의 한계를 제시한다. 실증적으로 7가지 NP-hard 조합 최적화 문제에서 FALCON은 완벽한 실행 가능성을 달성하는 동시에 최신 신경망 및 LLM 기반 솔버와 대등하거나 이를 능가하는 솔루션 품질을 보였다.

Large language models (LLMs) have emerged as promising general-purpose solvers for combinatorial optimization (CO), yet they fundamentally lack mechanisms to guarantee solution feasibility which is critical for real-world deployment. In this work, we introduce FALCON, a framework that ensures 100\% feasibility through three key innovations: (i) \emph{grammar-constrained decoding} enforces syntactic validity, (ii) a \emph{feasibility repair layer} corrects semantic constraint violations, and (iii) \emph{adaptive Best-of-$N$ sampling} allocates inference compute efficiently. To train the underlying LLM, we introduce the Best-anchored Objective-guided Preference Optimization (BOPO) in LLM training, which weights preference pairs by their objective gap, providing dense supervision without human labels. Theoretically, we prove convergence for BOPO and provide bounds on repair-induced quality loss. Empirically, across seven NP-hard CO problems, FALCON achieves perfect feasibility while matching or exceeding the solution quality of state-of-the-art neural and LLM-based solvers.