cs.AIOct 10, 2025

PAC Reasoning: Controlling the Performance Loss for Efficient Reasoning

Authors: Hao Zeng, Jianguo Huang, Bingyi Jing, Hongxin Wei, Bo An

Organizations: School of Mathematical Sciences, University of Electronic Science and Technology of China, China · College of Computing and Data Science, Nanyang Technological University, Singapore · School of Artificial Intelligence, The Chinese University of Hong Kong, Shenzhen, China · Shenzhen Loop Area Institute, China · 

Abstract

Large reasoning models (LRMs) have achieved remarkable progress in complex problem-solving tasks. Despite this success, LRMs typically suffer from high computational costs during deployment, highlighting a need for efficient inference. A practical direction is to switch the LRM between thinking and non-thinking modes dynamically. However, such approaches often introduce additional reasoning errors and lack statistical guarantees for the performance loss, which are critical for high-stakes applications. In this work, we propose Probably Approximately Correct (PAC) Reasoning that controls the performance loss under the user-specified tolerance. Specifically, we construct an upper confidence bound on the performance loss and determine a threshold for switching to the non-thinking model. Theoretically, using the threshold to switch between the thinking and non-thinking modes ensures bounded performance loss in a distribution-free manner. Our experiments on reasoning benchmarks show that the proposed method can save computational budgets and control the user-specified performance loss.

Figures & tables

Appendix figures & tables24 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. When2Think: Learning When and How Much to Reason

    Sep 17, 2026Jaejun Shim, HyunJin Kim, Young Jin Kim +1adaptive reasoning resource allocation for language modelsOverthinking in Language Models

  2. Efficient Reasoning with Balanced Thinking

    Mar 12, 2026Yulin Li, Tengyao Tu, Li Ding +5Efficient Language Model ReasoningLarge Reasoning Models