PAC Reasoning: Controlling the Performance Loss for Efficient Reasoning

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

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 popular direction of efficiency improvement is to switch the LRM between thinking and nonthinking 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 performance loss tolerance. In particular, we construct an upper confidence bound on the performance loss, formulated as a monotone function of the uncertainty score, and subsequently determine a threshold for switching to the nonthinking model. Theoretically, using the threshold to switch between the thinking and nonthinking modes ensures bounded performance loss in a distribution-free manner. Our comprehensive experiments on reasoning benchmarks show that the proposed method can save computational budgets and control the user-specified performance loss.

Introduction

The recent surge in Large Reasoning Models (LRMs), such as DeepSeek-R1, has highlighted the challenge of "overthinking." These models often expend massive computational effort on simple tasks where a shorter, "non-thinking" response would suffice. While routing queries between fast and slow models can save costs, existing heuristic methods offer no safety net—users cannot be certain of the accuracy sacrifice. For high-stakes applications in medicine, law, or engineering, this lack of a provable performance guarantee is a major barrier to adoption.

Methodology: PAC-Guaranteed Routing

The authors propose a framework based on Probably Approximately Correct (PAC) theory. The goal is to build a composite model that satisfies a specific safety condition: the probability that the performance loss exceeds a user-defined tolerance $\epsilon$ is no more than a risk level $\alpha$ (e.g., 5%).

The Core Mechanism

  1. Uncertainty-Based Routing: For every input, the system calculates an uncertainty score $U(x)$. If the score is low (high confidence), it uses a cheap "non-thinking" model. If the score is high, it defers to the expensive "thinking" model.
  2. Calibration via UCB: Instead of picking a threshold based on average performance, the framework uses an Upper Confidence Bound (UCB). By applying the Central Limit Theorem or Hoeffding’s inequality, they calculate a threshold $\hat{u}$ that accounts for statistical noise in calibration data.
  3. Monotonicity: The authors prove that performance loss is non-decreasing with respect to the uncertainty threshold. This allows them to find the largest possible threshold that still respects the safety guarantee.
Figure 1: Empirical error control on the Arena-Hard benchmark. The dashed "Diagonal" line represents the target error tolerance. Both logits-based and verbalized scores successfully maintain error below this bound.

Experimental Evaluation

The researchers evaluated PAC Reasoning across several challenging benchmarks, including MATH-500 (mathematics), ZebraLogic (logical deduction), and Arena-Hard (instruction following). The models tested included the Qwen3-4B series and DeepSeek-R1-Distill-Llama-8B paired with Llama-3.1-8B-Instruct.

Key Results and Insights

PAC Reasoning is the only method that consistently stays within the user-specified error budget. Heuristic baselines often exceed the allowed error rate to save more compute.

Figure 6: Comprehensive performance metrics across MATH-500, ZebraLogic, and Arena-Hard. Columns show Error control, Expert Call Percentage (ECP), and Saved Token Percentage (STP) as a function of the tolerance epsilon.

As illustrated in Figure 6, the framework achieves significant efficiency gains:

  • Arena-Hard: With a tolerance of $\epsilon=0.08$, the method achieved token savings (STP) of approximately 40% while calling the expert model only 20% of the time.
  • MATH-500: The system saved roughly 23% of the computational budget while maintaining a binary error rate below 0.03.
  • Logits vs. Verbalization: Internal "white-box" uncertainty scores (logits) proved much more stable and better calibrated than "verbalized" confidence (where the model states its own certainty).

Conclusion

PAC Reasoning provides a robust, distribution-free method for balancing efficiency and accuracy. While the current framework uses a binary switch, future work may explore multi-level hierarchies (e.g., routing through 1B, 8B, and 70B models). The method's efficiency depends on the quality of uncertainty estimation, but its safety guarantee remains a provable constant, making it suitable for deployment in rigorous environments.

Summary updated

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 popular direction of efficiency improvement is to switch the LRM between thinking and nonthinking 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 performance loss tolerance. In particular, we construct an upper confidence bound on the performance loss, formulated as a monotone function of the uncertainty score, and subsequently determine a threshold for switching to the nonthinking model. Theoretically, using the threshold to switch between the thinking and nonthinking modes ensures bounded performance loss in a distribution-free manner. Our comprehensive experiments on reasoning benchmarks show that the proposed method can save computational budgets and control the user-specified performance loss.
BibTeX
@misc{zeng2025pac,
  author = {Hao Zeng and Jianguo Huang and Bingyi Jing and Hongxin Wei and Bo An},
  title = {{PAC Reasoning: Controlling the Performance Loss for Efficient Reasoning}},
  year = {2025},
  eprint = {2510.09133},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.09133},
}
Figure