AlgBench: 대규모 추론 모델은 알고리즘을 어느 정도까지 이해하는가?

AlgBench: To What Extent Do Large Reasoning Models Understand Algorithms?

추론 능력은 대규모 추론 모델(LRM) 발전의 핵심 초점이 되었습니다. MATH500 및 LiveCodeBench와 같은 여러 추론 벤치마크에서 눈에 띄는 진전이 있었지만, 기존 알고리즘 추론 벤치마크는 여전히 제한적이며 'LRM이 알고리즘 추론을 진정으로 숙달했는가?'라는 중요한 질문에 답하지 못하고 있습니다. 이 질문에 답하기 위해, 우리는 알고리즘 중심 패러다임 하에서 LRM을 평가하는 전문가가 엄선한 벤치마크인 AlgBench를 제안합니다. AlgBench는 ACM 알고리즘 전문가들이 구축한 27개 알고리즘에 걸친 3,000개 이상의 독창적인 문제로 구성되어 있으며, 유클리드 구조, 비유클리드 구조, 비최적화, 지역 최적화, 전역 최적화 및 휴리스틱 최적화 범주를 포함하는 포괄적인 분류 체계 하에 조직되어 있습니다. 선도적인 LRM(예: Gemini-3-Pro, DeepSeek-v3.2-Speciale, GPT-o3)에 대한 실증적 평가 결과 상당한 성능 편차가 드러났습니다. 모델들은 비최적화 작업에서는 우수한 성능(최대 92%)을 보였지만, 동적 프로그래밍과 같은 전역 최적화 알고리즘에서는 정확도가 약 49%로 급격히 떨어졌습니다. 추가 분석을 통해 모델이 필요한 낮은 엔트로피 토큰으로 인해 올바른 알고리즘 설계를 조기에 포기하는 '전략적 과잉 전환(strategic over-shifts)' 현상을 밝혀냈습니다. 이러한 발견은 문제 중심 강화 학습의 근본적인 한계를 드러내며, 견고한 알고리즘 추론을 위한 알고리즘 중심 훈련 패러다임의 필요성을 강조합니다.

Reasoning ability has become a central focus in the advancement of Large Reasoning Models (LRMs). Although notable progress has been achieved on several reasoning benchmarks such as MATH500 and LiveCodeBench, existing benchmarks for algorithmic reasoning remain limited, failing to answer a critical question: Do LRMs truly master algorithmic reasoning? To answer this question, we propose AlgBench, an expert-curated benchmark that evaluates LRMs under an algorithm-centric paradigm. AlgBench consists of over 3,000 original problems spanning 27 algorithms, constructed by ACM algorithmic experts and organized under a comprehensive taxonomy, including Euclidean-structured, non-Euclidean-structured, non-optimized, local-optimized, global-optimized, and heuristic-optimized categories. Empirical evaluations on leading LRMs (e.g., Gemini-3-Pro, DeepSeek-v3.2-Speciale and GPT-o3) reveal substantial performance heterogeneity: while models perform well on non-optimized tasks (up to 92%), accuracy drops sharply to around 49% on globally optimized algorithms such as dynamic programming. Further analysis uncovers \textbf{strategic over-shifts}, wherein models prematurely abandon correct algorithmic designs due to necessary low-entropy tokens. These findings expose fundamental limitations of problem-centric reinforcement learning and highlight the necessity of an algorithm-centric training paradigm for robust algorithmic reasoning.