기술 요약: 최적화가 아닌 형식화: LLM 생성 조합 솔버의 휴리스틱 함정

문제 제기

대형 언어 모델 (LLM) 은 광대한 탐색 공간을 탐색하고 장기간 제약 조건 하에서 전역 일관성을 유지하는 데 내재된 "추론 병목 현상"으로 인해 직접적인 자기회귀 추론을 통해 복잡한 조합 문제를 해결하는 데 어려움을 겪습니다. 최근의 신경-심볼릭 접근법은 LLM 이 실행 가능한 솔버를 생성하도록 함으로써 이를 완화하려 시도하지만, 두 가지 중요한 설계 질문은 여전히 해결되지 않았습니다:

1. 표현: LLM 은 솔버를 어떻게 표현해야 하는가? 네이티브 알고리즘적 접근법 (Python) 이 선언적 모델링 (MiniZinc) 이나 솔버 API 통합 (Python + OR-Tools) 보다 우월한가?
2. 최적화: LLM 에게 휴리스틱, 가지치기, 또는 경계값과 같은 방법을 통해 탐색 과정을 능동적으로 최적화하도록 프롬프트를 입력해야 하는가, 아니면 검증된 백엔드를 위해 문제를 엄격하게 형식화하도록 해야 하는가?

이전 연구들은 종종 이러한 설정들을 고립적으로 또는 문제 수준에서 집계하여 평가했으며, 인스턴스 수준의 결과를 정확성, 스키마 유효성, 그리고 충실도로 분해하지 못했습니다. 또한, 생성된 솔버의 신뢰성에 대한 효율성 중심의 프롬프팅의 영향은 체계적으로 감사되지 않았습니다.

방법론

저자들은 100 개의 이질적인 제약 충족 문제 (CSP) 와 제약 최적화 문제 (COP) 를 포함하여 총 4,577 개의 매개변수화된 인스턴스로 구성된 CP-SynC 데이터셋을 확장한 CP-SynC-XL이라는 벤치마크를 소개합니다. 본 연구는 세 가지 솔버 구성 패러다임에 걸쳐 세 가지 최첨단 LLM(GPT-5.3-CODEX, GEMINI 3.1 PRO, DEEPSEEK-V3.2) 을 평가합니다:

1. 네이티브 알고리즘적 탐색 (Python): LLM 은 표준 라이브러리만을 사용하여 독립적인 Python 알고리즘을 생성하며, 분기 한정법 (branch-and-bound) 또는 동적 계획법 (DP) 과 같은 전체 탐색 절차를 설계합니다.
2. Python API 를 통한 제약 모델링 (Python + OR-Tools): LLM 은 OR-Tools CP-SAT Python API 를 사용하여 변수, 제약 조건 및 목적 함수를 인코딩하며, 탐색은 솔버에 위임합니다.
3. 선언적 제약 모델링 (MiniZinc + OR-Tools): LLM 은 MiniZinc 모델을 생성하며, 이는 동일한 OR-Tools CP-SAT 백엔드에 의해 컴파일되고 해결됩니다.

본 연구는 정확성만 요구하는 기준 프롬프트와 효율성 중심 설계 (더 엄격한 경계값, 가지치기, 또는 탐색 주석 등) 를 명시적으로 요청하는 휴리스틱 프롬프트를 비교하는 통제된 요인 설계를 사용합니다.

평가 파이프라인은 다음을 포함합니다:

• 정제 프로토콜: 실패한 실행 (크래시, 시간 초과, 형식 오류) 을 LLM 에게 피드백하는 4 회 반복 정정 루프.
• 지표:
  • 제공됨 (Provided): 스키마 준수 출력을 반환한 인스턴스의 비율.
  • 정확함 (Correct): 제공된 출력 중 참조 검증기를 통과한 비율.
  • 충실도 (Fidelity): 정확함/제공됨의 비율 (반환된 솔루션 중 실제로 유효한 것의 비율).
• 코드 수준 감사: 특정 실패 모드와 코드 패턴을 식별하기 위한 기준 대비 휴리스틱 솔버의 쌍별 분석.

주요 기여

1. CP-SynC-XL 벤치마크

저자들은 인스턴스 수준에서 LLM 생성 솔버를 평가하고, 제공된 출력과 검증된 정확성을 분리하여 조건부 충실도를 측정하도록 설계된 대규모 벤치마크 (4,577 개 인스턴스) 를 소개합니다.

2. 표현적 분기

본 연구는 동일한 솔버 백엔드 (OR-Tools CP-SAT) 를 사용하더라도 모델링 표면 (surface) 에 따라 솔버 성능에 상당한 분기가 있음을 보여줍니다:

• Python + OR-Tools는 모든 LLM 에서 가장 높은 절대 정확성을 달성합니다.
• MiniZinc + OR-Tools는 동일한 백엔드를 사용함에도 불구하고 더 낮은 절대 커버리지 (더 많은 "해 없음" 시간 초과) 를 보이며, 이는 솔버의 능력보다는 LLM 의 선언적 표면에서의 유창성 부족이 병목 현상임을 시사합니다.
• 네이티브 Python은 검증에 실패하는 스키마 유효 솔루션을 반환하는 "침묵하는 실패" 비율이 가장 높으며, 이는 LLM 이 처음부터 완전하고 타당한 탐색 알고리즘을 설계하는 데 어려움을 겪고 있음을 나타냅니다.

3. 휴리스틱 함정

본 논문은 LLM 에게 탐색을 최적화하도록 프롬프트를 입력하면 신뢰할 수 없는 결과가 산출되는 "휴리스틱 함정"을 규명합니다:

• 미미한 이득, 높은 위험: 휴리스틱 프롬프트는 중앙값 기준 1.03~1.12 배의 미미한 속도 향상만 제공하지만, 강한 이분산 효과를 유발합니다. 일부 인스턴스는 속도가 빨라지지만, 많은 다른 인스턴스는 느려지며, 긴 꼬리 (long tail) 에 있는 문제들에서 정확도가 급격히 떨어집니다.
• 여섯 가지 실패 모드: 코드 수준 감사는 휴리스틱 프롬프트에 의해 촉발된 여섯 가지 패러다임별 실패 모드를 식별합니다:
  • 검증되지 않은 경계값 (Python + OR-Tools): LLM 이 정리가 아닌 "엄격한" 경계값을 주입하여 비실현 가능성을 초래합니다.
  • 약화된 전파 (Python + OR-Tools): 솔버의 전파 엔진을 마비시키는 의미상 동등한 재작성 (예: Big-M) 입니다.
  • 경성 시딩 (Hard Seeding, Python + OR-Tools): 휴리스틱 후보를 경성 제약 조건으로 변환하여 실현 가능한 영역을 제거합니다.
  • 완전성 상실 (Python): 완전한 탐색을 불완전한 국소 탐색이나 반복 제한으로 대체합니다.
  • COP→SAT 붕괴 (MiniZinc): 최적 값을 잘못 가정하고 최적화를 충족 문제로 변환합니다.
  • 중복된 기계장치 (Redundant Machinery, MiniZinc): 솔버의 평탄화 과정을 압도하는 과도한 보조 제약 조건을 추가합니다.

결과

• 정확성 순위: Python + OR-Tools > Python ≳ MiniZinc + OR-Tools. 검증된 백엔드 (CP-SAT) 에 탐색을 위임하는 것이 네이티브 알고리즘 설계보다 훨씬 우수합니다.
• 충실도 순위: MiniZinc + OR-Tools > Python + OR-Tools > Python. 솔루션이 제공될 때, MiniZinc 모델이 가장 정확할 가능성이 높습니다 (최고의 조건부 충실도). 이는 언어의 타입 시스템과 잘 형성된 검사 (well-formedness checks) 가 솔버 실행 전에 많은 인코딩 오류를 필터링하기 때문입니다. 네이티브 Python 은 가장 충실도가 낮아, 종종 자신감 있지만 잘못된 솔루션을 반환합니다.
• 휴리스틱 영향: 더 강력한 LLM(GPT-5.3-CODEX, GEMINI 3.1 PRO) 에서는 휴리스틱 프롬프트가 미미하고 일관성 없는 이득 (±3.6 퍼센트 포인트) 을 제공합니다. 반면, 더 약한 LLM(DEEPSEEK-V3.2) 에서는 휴리스틱 프롬프트가 상당한 저하를 초래합니다 (예: Python + OR-Tools 에서 정확도 -7.4 pp).
• 실패 분석: 지배적인 기준 실패 모드는 UNSAT(참조 검증기가 솔루션을 거부함) 이며, 주로 자연어에서 형식 언어로의 오역 (제약 조건 누락, 출력 스키마 오해석 등) 으로 인해 발생합니다. 휴리스틱 프롬프트는 검증되지 않은 경계값을 도입하고 모델을 과도하게 제약함으로써 이를 악화시킵니다.

중요성과 설계 원칙

본 논문은 LLM 생성 조합 솔버의 주요 병목 현상이 솔버의 능력 자체가 아닌 모델링 표면의 유창성이라고 주장합니다. 이러한 발견은 다음과 같은 보수적 설계 원칙을 지지합니다:

"최적화가 아닌 형식화 (Formalize, Don't Optimize)."

LLM 은 검증된 솔버를 위해 변수, 제약 조건 및 목적 함수를 형식화하는 데 주로 사용되어야 합니다. LLM 에게 탐색 최적화 (휴리스틱, 경계값, 가지치기 전략) 를 생성하도록 하는 시도는 회의적으로 접근해야 합니다. 본 논문은 LLM 이 작성한 모든 탐색 최적화는 "휴리스틱 함정"이 종종 정확성과 충실도를 모두 저하시키는 검증되지 않은 경계값이나 알고리즘적 대체를 도입하므로, 사용 전에 독립적으로 검증되어야 한다고 결론지었습니다. 가장 신뢰할 수 있는 전략은 LLM 을 형식화 인터페이스에 가깝게 유지하고 솔버의 네이티브 메커니즘에 탐색을 의존하는 것입니다.