ACL Findings2026
AlgBench: To What Extent Do Large Reasoning Models Understand Algorithms?
Henan Sun, Kaichi Yu, Yuyao Wang, Bowen Liu, Xunkai Li, Rong-Hua Li, Nuo Chen, Jia Li
Abstract
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-Euclideanstructured, 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 strategic overshifts, 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on12
- Beyond the 80/20 Rule: High-Entropy Minority Tokens Drive Effective Reinforcement Learning for LLM ReasoningShenzhi Wang, Le Yu, Chang Gao, Chujie Zheng et al.NeurIPS 2025 · 592 citations
- KoLA: Carefully Benchmarking World Knowledge of Large Language ModelsJifan Yu, Xiaozhi Wang, Shangqing Tu, Shulin Cao et al.ICLR 2024 · 91 citations
- Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language GenerationLorenz Kuhn, Yarin Gal, Sebastian FarquharICLR 2023 · 49 citations
- OlympiadBench: A Challenging Benchmark for Promoting AGI with Olympiad-Level Bilingual Multimodal Scientific ProblemsChaoqun He, Renjie Luo, Yuzhuo Bai, Shengding Hu et al.ACL 2024 · 18 citations
- GraphWiz: An Instruction-Following Language Model for Graph Computational ProblemsNuo Chen, Yuhan Li, Jianheng Tang, Jia LiKDD 2024 · 14 citations
Related papers
- Can LLMs Reason Structurally? Benchmarking via the lens of Data StructuresYu He, Yingxi Li, Colin White, Ellen VitercikICML 2026 · 3 citations
- BeyondBench: Contamination-Resistant Evaluation of Reasoning in Language ModelsGaurav Srivastava, Aafiya Hussain, Zhenyu Bi, Swastik Roy et al.ICLR 2026 · 4 citations
- ARBench: Algorithmic Reasoner or API Alchemist? Evaluating LLMs Beyond API CallsRenbiao Liu, Chao-Zeng Ma, Anqi Li, Hui Sun et al.AAAI 2026
- Exposing Weaknesses of Large Reasoning Models through Graph Algorithm ProblemsQifan Zhang, Jianhao Ruan, Aochuan Chen, Kang Zeng et al.ICLR 2026 · 4 citations
- LiveOIBench: Can Large Language Models Outperform Human Contestants in Informatics Olympiads?Kaijian Zou, Feiyang Xiong, Yunxiang Zhang, Xinliang Frederick Zhang et al.ICML 2026 · 3 citations
