기술 요약: HeuriGym: 조합 최적화 분야의 LLM 제작 휴리스틱을 위한 에이전트 기반 벤치마크

문제 정의

현재 대규모 언어 모델(LLM)의 평가 방법론은 모델의 문제 해결 능력을 측정하는 데 있어 이중적 위기에 직면해 있다. 첫째, 정답 기반의 객관적 벤치마크(예: AIME, HumanEval)는 데이터 오염에 취약한 폐쇄형 질문에 의존하며, 솔루션이 유일하거나 미리 정의되어 있지 않은 실제 환경을 반영하지 못한다. 둘째, 심판 선호도 기반의 주관적 평가(예: Chatbot Arena)는 변동성이 높으며, 실질적인 추론 품질보다 표면적인 요소들을 우선시하는 경향이 있다.

LLM이 단순한 패턴 인식을 넘어, 복잡하고 반복적인 엔지니어링 워크플로에서 진정한 문제 해결의 독창성을 보여줄 수 있는지 평가하는 데에는 심각한 공백이 존재한다. 구체적으로, 기존 벤치마크들은 방대한 솔루션 공간을 탐색하고, 엄격한 제약 조건을 준-수하며, 실행 시간 피드백에 따라 전략을 조정해야 하는 조합 최적화(Combinatorial Optimization, CO) 문제를 위한 새로운 휴리스틱을 설계하는 능력을 평가하는 데 어려움을 겪고 있다.

방법론

저자들은 LLM이 조합 최적화 문제를 위한 휴리스틱 알고리즘을 생성, 실행 및 반복적으로 정교화하는 능력을 평가하기 위해 설계된 에이전트 기반 프레임워크인 HeuriGym을 소개한다.

프레임워크 개요

HeuriGym은 세 단계로 구성된 상호작용형 에이전트 루프를 통해 작동한다:

1. 문제 설명: LLM은 자연어 배경, 목적 함수 및 제약 조건의 수학적 정식화, 그리고 특정 입출력 파일 형식이 포함된 구조화된 프롬프트를 받는다. 부분적인 구현이나 스캐폴드(scaffold)를 제공하는 기존 연구와 달리, HeuriGym은 함수 인터페이스만을 제공하여 LLM이 데이터 구조와 알고리즘을 처음부터 직접 설계하도록 요구한다.
2. 실행 및 검증: 생성된 코드는 샌드박스 환경 내에서 컴파일되거나 해석된다. 도메인 특화 검증기(verifier)가 제약 조건 준수 여부(예: 의존성 보존)를 확인하며, 평가기는 최적화 목적 함수를 기준으로 비용을 계산한다.
3. 반복적 정교화: 소규모 데모 세트로부터 얻은 실행 로그, 검증 결과 및 성능 지표가 프롬프트에 추가된다. 이 피드백 루프를 통해 LLM은 오류를 디버깅하고, 제약 조건 위반을 수정하며, 여러 반복 과정을 거쳐 자신의 휴리스틱 전략을 정교화할 수 있다.

벤치마크 구축

본 벤치마크는 컴퓨터 시스템, 물류, 계산 생물학(예: 연산자 스케줄링, 기술 매핑, 항공사 승무원 배정, 단백질 서열 설계)을 아우르는 9개의 조합 최적화 문제로 구성된다.

• 선택 기준: 암기 위험을 최소적으로 줄이기 위해 문헌 노출이 적은(가장 많이 인용된 논문조차 인용 횟수 1,000회 미만) 문제들을 선정하였다. 이 문제들은 명확한 자연어 명세, 방대한 솔루션 공간, 그리고 확장 가능한 데이터 인스턴스를 특징으로 한다.
• 데이터셋: 각 문제는 퓨샷(few-shot) 프롬프팅 및 반복적 정교화를 위한 소규모 데모 세트(약 5개 인스턴스)와 최종 테스트를 위한 대규모 평가 세트(수십 개의 인스턴스)를 포함한다.

평가 지표

표준적인 PASS@k와 같은 지표의 한계를 해결하기 위해 저자들은 다음을 제안한다:

• SOLVEs@i: 제약이 있는 문제를 $i$번의 반복 내에 해결할 확률을 추적하며, 세 단계(단계 I: 실행, 단계 II: 솔루션 생성, 단계 III: 검증)를 통과하는 성공 여부를 측정한다.
• 품질-수율 지수 (Quality-Yield Index, QYI): 품질(솔루션이 전문가 베이스라인에 얼마나 근접했는지)과 수율(검증을 통과한 인스턴스의 비율)의 조화 평균으로 정의되는 통합 지표이다.
  • $Quality = \frac{1}{\hat{N}} \sum \min(1, \frac{c^*_n}{c_n})$, 여기서 $c_n$은 LLM 비용이고 $c^*_n$은 전문가 비용이다.
  • $Yield = \frac{\hat{N}}{N}$, 여기서 $\hat{N}$은 검증된 솔루션의 수이다.
  • $QYI = \frac{(1 + \beta^2) \cdot Quality \cdot Yield}{(\beta^2 \cdot Quality) + Yield}$ ($\beta=1$일 때).

주요 결과

저자들은 9개의 최첨단 모델(GPT-o4-mini-high, Gemini-2.5-Pro, DeepSeek-R1, LLaMA 변형 모델 포함)을 HeuriGym 벤치마크로 평가하였다.

• 성능 격차: 최상위 모델들조차 전문가 수준의 성능을 달리는 데 어려움을 겪는다. 가장 우수한 성능을 보인 모델인 Gemini-2.5-Pro는 약 0.62의 QYI 점수를 기록하였는데, 이는 해당 모델의 솔루션이 평균적으로 전문가가 설계한 휴리스틱만큼 효과적이지 않음(약 60% 수준)을 나타낸다. 다른 모델들은 현저히 낮은 점수(예: LLaMA-3.3 및 LLaMA-4-Maverick은 0.30 미만)를 기록했다.
• 반복적 개선: 반복 횟수를 늘릴수록 성능이 유의미하게 향상된다. 예를 들어, GPT-o4-mini-high의 성공률(SOLVEIII)은 1회 반복 시 53.2%에서 10회 반복 시 74.8%로 상승하였으며, 이는 반복적 정교화의 중요성을 강조한다.
• 실패 모드: 분석 결과, 환각된 API 호출, 잘못된 알고리즘 로직, 제약 조건 오해, 타임아웃 등 공통적인 실패 유형이 발견되었다.
• 진화적 프레임워크: 표준적인 진화 탐색 프레임워크(예: ReEvo, HSEvo)는 베이스라인 모델에 비해 저조한 성능을 보였는데, 이는 실행 피드백을 효과적으로 통합하지 못하고 반복 간에 컨텍스트가 끊어지는 경우가 많았기 때문이다.

의의 및 기여

본 논문은 세 가지 주요 기여를 주장한다:

1. 오픈 소스 벤치마크 스위트: 단순 암기된 패턴을 넘어 다단계 추론 및 알고리즘 설계 능력을 평가하는, 현실적이고 영향력 있는 9개의 조합 최적화 문제 모음집을 제공한다.
2. 엔드 투 엔드 에이전트 프레임워크: 솔루션 생성, 자동 검증 및 반복적 정교화를 지원하는 시스템으로서, 고급 프롬프팅 기법과 진화 전략을 위한 테스트베드 역할을 한다.
3. 경험적 통찰: 현재의 LLM들이 뛰어난 추론 능력에도 불구하고, 복잡한 실제 과학 및 엔지니어링 문제에 적용될 때 도구 사용, 계획 수립, 적응형 추론 측면에서 지속적인 한계에 직면해 있음을 밝히는 포괄적인 연구를 제시한다.

저자들은 HeuriGym을 최적해를 구하는 것이 작은 인스턴스에 대해서만 가능한 영역, 즉 휴리스틱 발견이 필수적인 분야에서 LLM 개발을 보다 효과적이고 현실적인 문제 해결로 유도하기 위한 필수적인 단계로 규정한다. 이 벤치마크는 현재의 모델 역량과 실제 엔지니어링 워크플로의 요구 사이의 간극을 드러내어, 단순한 패턴 매칭을 넘어 진정한 휴리스틱 발명을 수행할 수 있는 모델의 개발을 독려하는 것을 목표로 한다.