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
- 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.
- 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.
- 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.
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.
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