FrontierOR: Benchmarking LLMs’ Capacity for Efficient Algorithm Design in Large-Scale Optimization

Motivation

• Known: 기존 연구들은 LLM이 자연어 의사결정 문제를 수학적 formulation이나 solver-ready code로 정확히 변환할 수 있는지(NL4OPT, OptiMUS, OptiBench, MAMO, ORLM 등)를 주로 평가해왔으며, 고전적인 combinatorial optimization benchmark(OR-Library, TSPLIB, CVRPLIB, MIPLIB 등)는 알고리즘 비교를 위한 표준 인스턴스를 제공해왔다.
• Gap: 기존 benchmark들은 자연어 문제 설명이 없거나 지나치게 단순화되어 있고, 소규모 textbook-scale 사례에 한정되어 있어 실제 OR 문제에서 요구되는 problem structure를 활용한 확장 가능한 알고리즘 설계 능력을 측정하지 못하며, CO-Bench나 HeuriGym 같은 최근 시도들도 고전적 문제 유형과 소규모 task 집합에 머물러 있다.
• Why: 실무 OR 문제는 정확한 formulation뿐 아니라 대규모 인스턴스를 신뢰성 있고 효율적으로 해결하는 알고리즘 설계 능력을 요구하므로, LLM이 formulation-and-solve를 넘어 문제 구조를 활용한 알고리즘을 만들 수 있는지 측정하는 것은 LLM의 실질적 OR 활용 가능성을 가늠하는 핵심 질문이다.
• Approach: 최상위 OR 저널 논문에서 도출한 180개 task에 대해 자연어 문제 설명만을 LLM에 제공하고, 생성된 프로그램을 hidden expert-verified Gurobi baseline과 feasibility checker로 평가하는 two-stage(correctness 후 quality-time efficiency) 평가 프레임워크를 구축하였다.

Achievement

1. FrontierOR benchmark 구축: 102~107 규모의 decision variable과 constraint를 갖는 180개의 실세계 OR task를 최상위 저널 논문으로부터 수집하고, 15명의 OR 전문가가 3주간 multi-turn review를 통해 검증하였다.
2. 평가 결과 제시: one-shot 세팅에서 가장 강력한 모델도 Full-set instance의 31%에서만 Gurobi 대비 1% gap 이내의 solution quality를 더 짧은 runtime으로 달성했으며, test-time evolution을 사용한 coding agent조차 Hard-set의 50%에서만 성공하여 frontier model들이 여전히 efficient algorithm design에 취약함을 실증하였다.
3. 알고리즘 패턴 분석: 약한 모델은 monolithic solver call에 의존하는 반면 강한 frontier model은 decomposition, local-search, hybrid algorithm을 더 자주 생성한다는 모델 간 체계적 차이를 규명하였다.

How

• 각 task는 자연어 문제 설명, input/output format만 제공하고 mathematical formulation, reference solver, 알고리즘적 힌트는 제공하지 않음
• hidden evaluation suite는 대표 mathematical formulation, expert-verified Gurobi implementation, task-specific feasibility checker로 구성
• 1단계: standalone feasibility checker로 hard constraint 만족 여부를 확인하여 infeasible output에는 objective credit을 부여하지 않음
• 2단계: feasible solution에 대해 Gurobi 대비 objective gap(solution quality)과 동일 resource budget 하의 running time(efficiency)을 측정
• quality-time efficiency 지표: Gurobi reference 대비 1% 이내 objective와 Gurobi보다 느리지 않은 runtime을 동시에 만족해야 성공으로 카운트
• one-shot protocol과 self-evolve protocol(개발셋 피드백 기반 반복 개선 후 held-out test set 평가) 두 가지로 7개 LLM 평가

Originality

• 실제 top-tier OR 저널 논문에서 도출한 180개 task로 구성된 최초의 literature-grounded, large-scale(최대 ~107 변수/제약) 알고리즘 효율성 벤치마크
• formulation correctness가 아닌 algorithm efficiency(quality-time competitiveness against Gurobi)를 핵심 평가축으로 설정
• decomposability, temporal/network coupling, sparsity, routing/assignment, scenario structure 등 exploitable algorithmic structure를 가진 task만 선별
• 15명 전문가의 3주간 multi-turn review를 통한 hidden evaluation suite(수학적 formulation, verified Gurobi baseline, feasibility checker) 구축

Limitation & Further Study

• 각 task에 대해 하나의 대표 formulation과 Gurobi baseline만 사용하므로, 문제가 여러 valid formulation을 허용할 수 있다는 점에서 평가가 특정 formulation 선택에 편향될 가능성이 있음
• 평가 대상 LLM이 7개로 제한되어 있어 향후 더 많은 frontier 및 open-source model, 그리고 다양한 self-evolving agent 전략에 대한 확장 평가가 필요함
• Gurobi 자체가 46%의 대규모 인스턴스에서 1시간 내 optimality에 도달하지 못하는 상황에서 reference baseline의 신뢰성 및 대안적 ground-truth 검증 방법에 대한 추가 논의가 필요함

Evaluation

총평: LLM의 OR 알고리즘 설계 능력을 formulation 정확도를 넘어 실제 대규모 문제에서의 효율성 관점으로 체계적으로 측정한 시의적절하고 의미 있는 benchmark로, 현재 frontier LLM들의 명확한 한계를 드러내며 향후 연구를 위한 견고한 평가 플랫폼을 제공한다.