그래프 알고리즘 문제를 통한 대규모 추론 모델의 약점 규명

Exposing Weaknesses of Large Reasoning Models through Graph Algorithm Problems

대규모 추론 모델(Large Reasoning Models, LRM)은 급격히 발전했으나, 수학, 코드, 상식 추론에 초점을 맞춘 기존 벤치마크는 여전히 한계가 있습니다. 기존 벤치마크는 긴 문맥(long-context) 평가가 결여되어 있고, 난이도가 충분하지 않으며, 프로그래밍 방식으로 검증하기 어려운 정답을 제공합니다. 본 논문에서는 그래프 알고리즘 문제를 통해 LRM을 평가하도록 설계된 벤치마크인 GrAlgoBench를 제안합니다. 그래프 알고리즘 문제는 긴 문맥 추론을 요구하고, 난이도의 세밀한 조정이 가능하며, 표준화된 프로그래밍 방식의 평가를 지원하므로 추론 능력을 탐색하는 데 특히 적합합니다. 9가지 과제에 대한 체계적인 실험 결과, 현재 LRM의 두 가지 주요 약점이 드러났습니다. 첫째, 문맥 길이가 길어질수록 정확도가 급격히 하락하여, 그래프 노드가 120개를 초과할 경우 정확도가 50% 미만으로 떨어집니다. 이러한 성능 저하는 빈번한 실행 오류, 기억력 부족, 중복된 추론에 기인합니다. 둘째, LRM은 '과잉 사고(over-thinking)' 현상을 겪습니다. 이는 주로 광범위하지만 실효성이 없는 자기 검증 과정에서 비롯되며, 정답률을 개선하지 못한 채 추론 과정만 비대하게 만듭니다. GrAlgoBench는 이러한 한계를 규명함으로써, 그래프 알고리즘 문제를 LRM 추론 연구의 발전을 위한 엄격하고 다차원적이며 실용적인 테스트베드로 정립합니다. 코드는 https://github.com/Bklight999/GrAlgoBench 에서 제공됩니다.

Large Reasoning Models (LRMs) have advanced rapidly; however, existing benchmarks in mathematics, code, and common-sense reasoning remain limited. They lack long-context evaluation, offer insufficient challenge, and provide answers that are difficult to verify programmatically. We introduce GrAlgoBench, a benchmark designed to evaluate LRMs through graph algorithm problems. Such problems are particularly well suited for probing reasoning abilities: they demand long-context reasoning, allow fine-grained control of difficulty levels, and enable standardized, programmatic evaluation. Across nine tasks, our systematic experiments reveal two major weaknesses of current LRMs. First, accuracy deteriorates sharply as context length increases, falling below 50% once graphs exceed 120 nodes. This degradation is driven by frequent execution errors, weak memory, and redundant reasoning. Second, LRMs suffer from an over-thinking phenomenon, primarily caused by extensive yet largely ineffective self-verification, which inflates reasoning traces without improving correctness. By exposing these limitations, GrAlgoBench establishes graph algorithm problems as a rigorous, multidimensional, and practically relevant testbed for advancing the study of reasoning in LRMs. Code is available at https://github.com/Bklight999/GrAlgoBench.