최적화하지 말고 형식화하라: LLM 생성 조합 문제 해결기에서의 휴리스틱 함정

대규모 언어 모델(LLMs)은 직접적인 추론만으로는 복잡한 조합 문제를 해결하는 데 어려움을 겪기 때문에, 최근의 신경-심볼릭 시스템들은 실행 가능한 솔버를 합성하기 위해 LLM을 점점 더 많이 사용하고 있습니다. 핵심 설계 질문은 LLM이 솔버를 어떻게 표현해야 하는지, 그리고 검색 최적화까지 시도해야 하는지에 관한 것입니다. 우리는 100개의 조합 문제(4,577개 인스턴스)로 구성된 벤치마크인 CP-SynC-XL을 소개하고, 세 가지 솔버 구축 패러다임을 평가합니다: 네이티브 알고리즘 검색(Python), Python 솔버 API를 통한 제약 모델링(Python + OR-Tools), 그리고 선언적 제약 모델링(MiniZinc + OR-Tools). 우리는 일관된 표현적 분기점을 발견했습니다. Python + OR-Tools가 LLM 전반에 걸쳐 가장 높은 정확도를 달성하는 반면, MiniZinc + OR-Tools는 동일한 OR-Tools 백엔드를 사용함에도 불구하고 낮은 절대 커버리지를 보였습니다. 네이티브 Python은 스키마 유효성이지만 검증에 실패하는 솔루션을 반환할 가능성이 가장 높았던 반면, 솔버 기반 경로는 더 높은 조건부 충실도를 유지했습니다. 휴리스틱 축에서, 검색 최적화를 위한 프롬프팅은 작은 중앙값 속도 향상(1.03-1.12배)만을 가져왔고 강한 이봉 효과를 보였습니다: 많은 인스턴스는 느려지고, 문제의 긴 꼬리 부분에서는 정확도가 급격히 떨어졌습니다. 쌍을 이루는 코드 레벨 감사를 통해 이러한 성능 저하가 반복되는 휴리스틱 함정으로 추적되었습니다.

효율성 지향적인 프롬프트 하에서, LLM은 완전한 탐색을 지역적 근사치로 대체하거나 (Python), 검증되지 않은 경계 조건을 주입하거나 (Python + OR-Tools), 모델에 과부하를 주거나 지나치게 제약하는 중복적인 선언적 장치를 추가할 수 있습니다 (MiniZinc + OR-Tools). 이러한 발견들은 LLM이 생성한 조합 최적화 솔버에 대한 보수적인 설계 원칙을 뒷받침합니다. 즉, LLM은 주로 검증된 솔버를 위한 변수, 제약 조건 및 목적 함수를 형식화하는 데 사용하고, LLM이 작성한 검색 최적화는 사용 전에 별도로 확인해야 합니다.