Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization

Created by

Haebom

저자

Xia Jiang, Jing Chen, Cong Zhang, Jie Gao, Chengpeng Hu, Chenhao Zhang, Yaoxin Wu, Yingqian Zhang

💡 개요

본 연구는 LLM의 조합 최적화(CO) 문제 해결 능력을 평가하기 위해 자연어 기반의 CO 벤치마크인 NLCO를 제안합니다. NLCO는 43개의 CO 문제와 체계적인 분류 체계를 통해 LLM이 코딩이나 외부 솔버 없이도 언어로 설명된 의사 결정 시나리오에서 이산적인 해답을 도출하는 능력을 평가합니다. 실험 결과, 최신 LLM들은 작은 규모의 문제에서는 우수한 성능을 보였으나, 문제 크기가 커짐에 따라 성능이 저하되는 경향을 보였으며, 특히 그래프 구조 문제와 병목 목표에서 실패율이 높았습니다.

🔑 시사점 및 한계

•

LLM은 간단한 조합 최적화 문제에 대한 자연어 기반의 추론 능력을 일부 보여주지만, 복잡하고 큰 규모의 문제 해결에는 한계가 있습니다.

•

NLCO 벤치마크는 LLM의 조합 최적화 추론 능력을 세부적으로 평가할 수 있는 체계적인 프레임워크를 제공합니다.

•

문제의 구조(예: 그래프 기반)와 목표의 특성(예: 병목)이 LLM의 성능에 큰 영향을 미치며, 이를 극복하기 위한 LLM 아키텍처 또는 학습 방법론 개선이 필요합니다.

•

문제 규모 증가에 따른 LLM 성능 저하 현상과 더 많은 토큰을 사용하더라도 성능 개선이 제한적인 점은 향후 LLM의 효율적인 추론 능력 향상을 위한 연구 방향을 제시합니다.

PDF 보기

Made with Slashpage