Score the fast answer
Use a logits-based or verbalized uncertainty score. The score guides routing; its quality affects the savings.
¹ University of Electronic Science and Technology of China² Nanyang Technological University³ The Chinese University of Hong Kong, Shenzhen⁴ Southern University of Science and Technology⁵ Shenzhen Loop Area Institute
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 selective thinking, which switches 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.
01 / The idea
Reasoning models can spend many tokens on easy questions. Switching to a non-thinking model saves work, but may add errors. PAC Reasoning calibrates selective thinking, with an explicit tolerance for the loss relative to a reference thinking model.
First, generate a fast answer and measure its uncertainty. Accept it when the score is below a calibrated threshold; otherwise, call the thinking model. A statistical upper bound, rather than the score alone, sets the threshold.
02 / The method
A fixed sequence of tests turns a pointwise risk bound into a guarantee for the selected policy.
Use a logits-based or verbalized uncertainty score. The score guides routing; its quality affects the savings.
Test a pre-specified grid of thresholds from small to large. Stop at the first bound above the tolerance.
Use the preceding threshold. Low uncertainty keeps the fast answer; high uncertainty routes to the thinking model.
Interactive explanation
Move the tolerance line. A threshold passes if its upper bound is at most \(\epsilon\). The first failure ends the search, even if a later bound drops below \(\epsilon\).
Illustration only: these bound values are synthetic. This explains the selection rule in the paper; it is not an experiment or a new guarantee.
03 / The guarantee
Confidence over calibration data and UCB randomization.
The risk is the expected nonnegative loss relative to the thinking model. For binary loss, it counts cases where the thinking model is correct and the routed answer is wrong. It is not the model’s total error rate.
The selection theorem uses a fixed finite grid, non-decreasing true risk, valid pointwise population-risk upper bounds, and stopping at the first failed test. It does not require the estimated upper bounds to be monotone.
The model pair and score are fixed before calibration, and calibration and deployment follow the stated sampling setup. A bound for a fixed empirical pool alone does not establish population-risk coverage.
The CLT construction gives asymptotic validity under its regularity conditions. The Hoeffding construction gives finite-sample validity under its stated boundedness and sampling-weight conditions. The selection rule inherits the validity of the bound used.
A held-out batch can fluctuate above its population risk. The paper gives a separate bound for empirical test loss, with an extra test-sample tail term. Distribution shift requires fresh justification or recalibration.
See Section 3 and the appendices ↗04 / The evidence
Results from the paper, not simulated data. Compare the mean loss and savings of each method at the reported operating points.
Source: Table 1, Qwen3-4B model pair, 100 repeated runs; values are mean ± standard deviation (SD), not confidence intervals. The shaded region marks mean loss \(\le\epsilon\); a mean below \(\epsilon\) does not imply that every run meets the tolerance. Negative token savings mean more tokens were used than by thinking alone.
| Method / score | Binary loss | Expert calls (%) | Tokens saved (%) |
|---|
Beyond the mean
These are repeated-protocol empirical test-loss success rates on fixed benchmark data, not estimates of population-risk coverage.
Table 6 ↗The cost in practice
Separate aggregate measurements from the paper. Token savings in Table 1 average per-query ratios; aggregate token totals use a different calculation.
Table 7 ↗05 / Read & build
The full paper includes semantic-loss results on MATH-500, ZebraLogic, and Arena-Hard, additional model pairs and datasets, proofs, and deployment limits.
@inproceedings{zeng2026pacreasoning,
title = {PAC Reasoning: Controlling the Performance Loss
for Efficient Reasoning},
author = {Zeng, Hao and Huang, Jianguo and Jing, Bingyi
and Wei, Hongxin and An, Bo},
booktitle = {Advances in Neural Information Processing Systems},
year = {2026},
url = {https://zenghao-stat.github.io/pages/pac_reasoning/}
}