🤖 AI

Large Language Models as Optimizers: A Survey of Direct vs. Tool-Augmented Approaches and Their Performance Frontiers

이 설문 조사는 수학적 최적화 분야에서의 거대 언어 모델 활용을 직접적, 도구 증강적, 도구 생성적 패러다임으로 분류하여 이들의 성능 한계를 분석하며, 직접적인 방식이 미래의 잠재력을 보유하고 있는 반면 도구 증강적 접근 방식이 현재 더 우수한 감사 가능성을 제공하고 도구 생성 전략이 궁극적으로 반복적인 문제에 대해 최고의 운영 효율성을 제공할 수 있다고 주장한다.

원저자: Roko Peran, Luka Hobor, Mihael Kovac, Mario Brcic

게시일 2026-06-16

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Roko Peran, Luka Hobor, Mihael Kovac, Mario Brcic

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신에게는 퍼즐을 풀 줄 아는 매우 똑똑하고 박학다식한 사서(대규모 언어 모델, 즉 LLM)가 있다고 상상해 보세요. 당신은 이 사서에게 "50개의 택배를 각기 다른 집들에 배달하면서 연료가 떨어지지 않게 하는 가장 좋은 방법을 찾아내라"와 같이 일상적인 영어로 된 복잡하고 실제적인 문제를 던져줍니다.

이 논문은 이 사서가 그 문제를 해결하기 위해 시도할 수 있는 세 가지 서로 다른 방법들을 조사합니다. 이것들을 사서의 세 가지 서로 다른 '직무 기술서'라고 생각하면 됩니다.

1. "추측하고 확인하기" 사서 (직접 최적화)

작동 방식: 사서는 자신의 머릿속에서 문제를 완전히 해결하려고 노력합니다. 해결책을 적어보고, 그것이 좋은지 확인한 뒤, 조금 어긋났다는 것을 깨달으면 약간 더 나은 새로운 해결책을 다시 적습니다. 이 "추측, 확인, 개선"의 루프를 계속해서 반복합니다.

비유: 이것은 지도 없이 미로를 헤매는 것과 같습니다. 길을 가다가 벽에 부딪히면, 뒤로 돌아가서 다른 길을 시도하는 식입니다.
함정: 작은 미로(단순한 문제)에서는 아주 잘 작동합니다. 하지만 미로가 거대해지면(수천 개의 거리가 있는 도시처럼), 사서는 혼란에 빠집니다. 존재하지 않는 규칙을 만들어내거나 중요한 세부 사항을 잊어버리기 시작합니다. 논문은 문제가 너무 복잡해지면 이 방식이 "추론 절벽(reasoning cliff)"에 부딪혀 제대로 작동하지 않게 된다고 언급합니다.

2. "번역가이자 프로젝트 매니저" 사서 (도구 증강 최적화)

작동 방식: 사서는 스스로 문제를 해결하는 대신 번역가 역할을 수행합니다. 그들은 당신의 복잡한 영어 설명을 엄격하고 형식적인 수학적 언어(코드나 설계도 같은 것)로 변환합니다. 그런 다음 그 설계도를 숫자를 계산하는 데 특화된 매우 빠르고 전문적인 로봇(솔버, solver)에게 전달합니다. 로봇이 문제를 해결하다가 실수를 하면, 사서는 설계도를 수정하여 로봇에게 다시 요청합니다.

비유: 사서는 설계도를 그리는 건축가이고, 로봇은 실제로 집을 짓는 건설팀입니다. 사서는 벽돌을 쌓지 않습니다. 단지 설계도가 올바른지 확인하는 역할만 합니다.
함정: 이 방식은 크고 구조화된 문제에 대해 가장 정확한 방법입니다. 하지만 사서의 번역 능력에 전적으로 의존합니다. 만약 사서가 설계도를 잘못 작성한다면(예: 벽이나 문 하나를 빠뜨린 경우), 로봇은 완벽한 집을 짓겠지만 당신이 실제로 원했던 것과는 다른 집을 짓게 될 것입니다. 논문은 로봇은 수학에 완벽하지만, 사서가 번역 과정에서 알아채기 어려운 "침묵의 실수(silent mistakes)"를 저지르는 경우가 많다고 강조합니다.

3. "도구 제작자" 사서 (도구 생성 최적화)

작동 방식: 사서는 특정 문제 하나를 해결하거나 특정 요청을 번역하는 대신, 유사한 유형의 문제 전체를 해결할 수 있는 완전히 새로운 기계나 재사용 가능한 규칙 모음을 발명합니다. 일단 이 기계를 만들고 나면, 사서의 도움 없이도 이 기계를 사용하여 반복적으로 문제를 해결할 수 있습니다.

비유: 매번 미로를 통과하는 대신, 사서는 어떤 미로든 통과할 수 있는 로봇을 설계합니다. 도구를 만드는 데 많은 시간과 에너지를 들여 한 번 구축해 놓으면, 그다음부터는 1,000개의 미로를 즉시, 그리고 무료로 통과할 수 있습니다.
함정: 도구를 처음 만드는 데 많은 노력과 컴퓨팅 자원이 필요합니다. 또한, 그들이 만든 도구가 때로는 천재적이지만, 때로는 재현 불가능한 운 좋은 추측에 불과할 수도 있습니다. 논문은 일단 도구가 구축되면 믿을 수 없을 정도로 효율적이기 때문에, 이 분야가 가장 빠르게 성장하고 있는 영역이라고 언급합니다.

핵심 요약: 무엇이 가장 좋은가?

이 논문은 이 세 가지 접근 방식을 다음과 같은 '트레이드오프(trade-off) 메뉴'처럼 비교합니다.

직접 방식 (추측하고 확인하기): 명확한 규칙 책이 없는 작고 복잡한 문제에 좋습니다. 하지만 상황이 복잡해지면 신뢰도가 떨어집니다.
도구 증강 방식 (번역가): 번역이 완벽하다면, 크고 구조화된 문제(물류나 스케줄링 등)에 가장 신뢰할 수 있는 방식입니다. 로봇으로부터 "정답 인증서"를 받을 수 있지만, 이는 사서가 지침을 틀리지 않았을 때만 유효합니다.
도구 생성 방식 (도구 제작자): 장기적으로 가장 효율적입니다. 동일한 유형의 문제를 반복해서 풀어야 한다면, 매번 사서에게 처음부터 해결해 달라고 요청하는 것보다 에너지를 한 번 써서 재사용 가능한 도구를 만드는 것이 더 낫습니다.

"추론 격차 (Reasoning Gap)"
논문은 결론적으로 경고를 던집니다. 아무리 똑똑한 사서(가장 발전된 AI 모델)라도 깊고 복잡한 논리에는 어려움을 겪는다는 점입니다. 그들은 이전에 보았던 패턴을 인식하는 데는 매우 뛰어나지만, 완전히 새로운 논리적 경로를 발명해야 할 때는 종종 실패합니다.

미래 전략
저자들은 미래의 가장 현명한 전략이 모든 문제를 직접 해결할 수 있도록 사서를 더 똑똑하게 만드는 것이 아니라고 주장합니다. 대신, 미래는 **'도구 제작(Tool-Making)'**에 달려 있습니다. 미래에 초지능 AI가 등장하더라도, 그 AI가 전문적인 도구를 한 번 만들게 하고, 그 후에는 더 작고 저렴한 AI가 그 도구를 사용하여 수천 개의 문제를 즉시 해결하게 하는 것이 훨씬 효율적일 것입니다. 이것은 레스토랑의 모든 식사를 직접 요리하기 위해 마스터 셰프를 고용하는 것과, 레시피와 기계를 발명하게 한 뒤 일반 요리사가 그 기계를 운영하도록 하는 것의 차이와 같습니다.

기술 요약: 최적화 도구로서의 대규모 언어 모델 (Large Language Models as Optimizers)

문제 정의

실제 세계의 최적화 문제들은 종종 자연어 설명(예: 물류 제약 조건, 실험 목표)에서 기인하며, 이는 전통적인 솔버(예: Gurobi, CPLEX, Z3)가 처리할 수 있도록 정식 수학적 프로그램으로 번역되어야 합니다. 대규모 언어 모델(LLM)은 이 간극을 메우는 데 유망한 가능성을 보여주었으나, 복잡한 수학적 최적화에 적용될 때는 상당한 장애물에 직면합니다. 핵심 과제는 LLM의 직접적인 추론이 가진 유연성과 외부 솔버의 수학적 엄밀성 사이의 절충안을 탐색하는 것이며, 특히 문제의 복잡도가 증가함에 따라 이 문제가 심화됩니다. 현재의 아키텍처는 LLM이 진정한 알고리즘적 추론보다는 패턴 매칭에 의존함에 따라 발생하는 "추론 격차(reasoning gap)" 문제로 인해 어려움을 겪고 있습니다. 이는 솔버가 구문 오류 없이 코드를 실행하더라도 수식 자체에 오류가 지속되는 현상으로 이어집니다.

방법론: 세 가지 패러다임

본 조사는 LLM 기반 최적화를 세 가지 뚜렷한 패러다임으로 분류하며, 각 패러다임은 고유한 메커니즘과 성능 특성을 가집니다.

1. 직접 최적화 (Direct Optimization)

이 패러다임에서 LLM은 외부 솔버 없이 스스로 최적화 도구 역할을 수행하며 해 공간(solution space)을 탐색합니다.

메커니즘: 모델은 후보 해를 생성하고, 목적 함수 값에 대한 피드백을 받으며, Chain-of-Thought (CoT), Tree-of-Thought (ToT), 그리고 반복적 프롬프팅(예: OPRO, SGE)과 같은 전략을 사용하여 반복적으로 이를 정교화합니다.
진화: 이 접근 방식은 단순한 프롬프팅에서부터, 모델이 처음부터 추론하는 대신 지도 미세 조정(SFT) 및 강화 학습(RL)을 통해 최적화 휴리스틱을 내재화하는 미세 조정(예: E2E CO Solver, LLaMoCo) 단계로 진화했습니다.
범위: 구조가 불분명한 문제나 도메인 지식이 탐색을 가속화할 수 있는 비용이 많이 드는 평가 환경(예: 하이퍼파라미터 튜닝, 화학 합성)에 효과적입니다.

2. 도구 증강 최적화 (Tool-Augmented Optimization)

여기서 LLM은 번역기이자 오케스트레이터 역할을 하며, 자연어를 외부 솔버로 전달될 정식 명세(LP, MILP, SAT)로 변환합니다.

메커니즘: 워크플로우는 다음과 같은 파이프라인을 따릅니다: 자연어 $\rightarrow$ LLM 수식화 $\rightarrow$ 솔버 코드 $\rightarrow$ 실행 $\rightarrow$ 오류 피드백. 고급 시스템은 다중 에이전트 아키텍처(Formulator/Programmer/Evaluator)를 채택하거나, 수식 정확도를 높이기 위해 데이터 중심 미세 조정(예: ORLM, SIRL)을 사용합니다.
초점: 주요 과제는 "수식의 정확성(formulation correctness)"입니다. 최근 연구(2025–2026)는 코드는 깔끔하게 실행되지만 잘못된 문제를 인코딩하는 "침묵하는 수식 실패(silent formulation failures)"를 탐지하는 데 집중하고 있습니다. 기술로는 의미론적 앵커 재구성(SAC-Opt), 대안 모델을 위한 조합 탐색(Autoformulation), 행동 검증(ReLoop) 등이 포함됩니다.

3. 도구 생성 최적화 (Tool-Creating Optimization)

이 패러다임은 개별 문제 인스턴스를 해결하기보다는, 솔버 또는 메타휴리스틱 프레임워크 내에서 작동하는 재사용 가능한 알고리즘이나 휴리스틱을 발견하는 데 LLM을 사용합니다.

메커니즘: LLM은 진화적 탐색(예: FunSearch, EoH)의 돌연변이 연산자로 작용하거나, 휴리스틱을 정교화하기 위해 "언어적 경사도(verbal gradients)"를 생성합니다(ReEvo).
경제적 모델: 도구를 생성하는 데 높은 초기 LLM 비용이 발생하지만, 이 접근 방식은 배포 시점에 실질적인 한계 비용(marginal cost)이 거의 제로에 가깝습니다. 왜냐하면 재사용 가능한 도구가 반복적인 사용을 통해 비용이 분산(amortized)되기 때문입니다.

주요 기여 및 결과

성능의 경계와 벤치마크

본 논문은 최근 문헌의 성능 데이터를 종합하여 현재의 경계를 설정합니다:

직접 최적화: 소규모 또는 특정 도메인에서 강력한 결과를 달성합니다(예: OPRO를 통한 BBH에서의 +50% 개선; LLAMBO를 통한 화학 수율 개선 25.2% $\rightarrow$ 60.7%). 그러나 변수가 약 20개를 넘어서는 경우(예: TSP), 단순한 휴리스틱이 LLM보다 우수한 성능을 보이며 성능이 크게 저하됩니다.
도구 증강 최적화: 단순 벤치마크에서는 완벽에 가까운 정확도를 달성하지만(예: NL4Opt에서 97.3%), "복잡성 절벽(complexity cliff)"에 직면합니다. 실제 산업 문제(IndustryOR)에서는 정확도가 57%로 떨어지며, 복합적인 다중 제약 시나리오(RetailOpt-190)에서는 31.1%까지 급락합니다.
도구 생성 최적화: 알고리즘 발견 분야에서 최첨단(SOTA) 결과를 만들어냈습니다. 예를 들어, 클래식 휴리스틱을 능가하는 빈 패킹(bin-packing) 전략(FunSearch)이나, Google의 Borg 클러스터에 배포되어 23%의 속도 향상을 가져온 스케줄링 휴리스틱(AlphaEvolve) 등이 있습니다.

추론 격차 (The Reasoning Gap)

본 조사의 핵심적인 기여는 "추론 격차"를 식별한 것입니다.

실행 가능성 vs. 정확성: DeepSeek-V3.2와 같은 모델은 복합 시나리오에서 91.1%의 솔버 실행 가능성(feasibility)을 달ach하지만, 수식 정확성(formulation correctness)은 0.5%에 불과합니다.
패턴 매칭: LLM이 알고리즘적 추론보다는 패턴 매칭에 의존한다는 증거가 나타납니다. 문제 복잡도가 증가함에 따라 추론 노력이 정점에 도달했다가 다시 감소하며, 결국 "완전한 정확도 붕괴(complete accuracy collapse)"로 이어집니다.
오류 유형: 체계적인 오류로는 제약 조건 누락, 잘못된 변수 유형, 목적 함수 불일치 등이 있습니다.

비교 트레이드오프

본 조사는 (표 II)를 통해 다음과 같은 비교 분석을 제공합니다:

도구 증강(Tool-Augmented) 방식은 (수식이 정확하다는 전제하에) 가장 높은 감사 가능성(auditability)과 형식적 보증을 제공하지만, 수식 정확도가 병목 구간입니다.
직접(Direct) 방식은 감사 가능성이 낮고 형식적 보증이 없지만, 소규모 또는 구조가 불분명한 맥락에서 뛰어납니다.
도구 생성(Tool-Creating) 방식은 중간 정도의 감사 가능성을 가진 새로운 SOTA 휴리스틱을 제공하며, 높은 초기 비용과 제로에 가까운 배포 한계 비용 사이의 균형을 맞춥니다.

의의 및 주장

본 논문은 선택하는 패러다임이 특정 문제의 제약 조건과 모델의 능력에 달려 있다고 주장합니다.

직접 접근 방식의 한한계: 직접 최적화가 확장되고는 있으나, 높은 복잡도에서의 추론 격차가 확장성을 제한합니다.
도구 제작의 당위성: 저자들은 "도구 제작"(재사용 가능한 솔버 구성 요소 또는 수식 템플릿 생성)이 미래의 가장 유망한 방향이라고 상정합니다. 모델이 더욱 강력해지더라도, 직접 해결하는 방식의 인스턴스당 기회비용은 그 이점을 상쇄할 수 있습니다. 재사용 가능한 도구를 만드는 것은 LLM의 추론 비용을 전체 문제군에 걸쳐 분산시킴으로써, 인스턴스별 추론보다 더 운영 효율적인 경로를 제공합니다.
재현성 위기: 본 조사는 도구 생성 분야의 재현성 위기를 강조합니다. FunSearch의 cap set과 같은 SOTA 주장들은 종종 독점적인 인프라나 경로 의존성 때문에 독립적인 재현이 어렵습니다. 저자들은 폐쇄형 시스템에 대한 주장에 라벨을 붙이고, 최선의 결과(best-case outcomes)가 아닌 결과의 분포를 보고하도록 하는 커뮤니티 규범을 촉구합니다.

결론적으로, 본 조사는 LLM이 최적화에 점점 더 많이 관여하고 있지만, 분야 전체가 "복잡성 절벽"과 "수식 정확성"이라는 병목 현상을 해결해야 한다고 지적합니다. 향ical한 궤적은 LLM을 알고리즘 발견 및 템플릿 생성에 활용하고, 실행 및 검증에는 정식 솔버를 사용하는 하이브리드 또는 도구 생성 전략을 선호할 것으로 보입니다.