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 · Department of Statistics and Data Science, Southern University of Science and Technology, China
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
Figure 1: Error control, ECP and STP of PAC Reasoning for semantic loss across three benchmarks at α=0.05 . Uncertainty score includes the logits-based score and the verbalized score. All experiments are repeated 100 times, and the shaded areas represent standard deviations.
Method
Score
MATH-500
ZebraLogic
Error ↓
ECP (%) ↓
STP (%) ↑
Error ↓
ECP (%) ↓
STP (%) ↑
Naive threshold
Logits-based
0.0179±0.0068
14.44±2.02
43.58±4.78
0.0062±0.0026
77.28±1.36
−34.78±1.26
Verbalized
0.0346±0.0095
2.83±0.94
66.67±4.91
0.0631±0.0074
12.49±1.07
32.70±2.11
Naive control
Logits-based
0.0351±0.0098
6.04±2.75
61.52±6.10
0.0959±0.0099
5.47±1.63
46.59±2.43
Verbalized
0.0351±0.0098
6.04±2.75
61.52±6.10
0.0948±0.0093
6.56±0.92
42.75±1.95
PAC Reasoning
Logits-based
0.0206±0.0126
21.48±17.85
37.61±23.19
0.0618±0.0181
22.50±7.47
23.13±9.09
Table 1: PAC Reasoning enables safe, effective inference-cost reduction over heuristic baselines . Green cells indicate valid loss control. Experiments use binary loss with ϵ=0.03 on MATH-500 and ϵ=0.08 on ZebraLogic.
Appendix figures & tables24 assets
Supplementary material from the paper’s appendix.
Appendix
Method
Objective and controlled quantity
Calibration or analysis
FrugalGPT
Maximize task accuracy under an average inference-cost budget.
Maximize answer accuracy under a total cost budget.
Learned reinforcement-learning policy; theory for oracle ordering and answer-consistency rules.
C3PO
Minimize strongest-model disagreement under a probabilistic cost constraint.
Conformal cost calibration under exchangeability; additional regret generalization bounds.
Trust or Escalate
Control human-disagreement risk among accepted LLM evaluations.
I.i.d. human-labelled calibration, exact binomial bounds, and fixed-sequence testing.
Online Cascade
Learn a cascade and deferral policy for input streams.
Online imitation learning from LLM demonstrations with a no-regret algorithm.
Appendix
Table 2: Objectives and statistical analyses of related LLM routing and cascade methods. The PAC Reasoning row states the conditions used by our selection theorem.
System prompt: You are a reasoning assistant. For each question and proposed answer, you must estimate how likely the proposed answer is correct.
User prompt:
Question: {QUESTION}
Answer: {ANSWER}
Provide a probability (between 0.0 and 1.0) that your answer is correct. Only output the probability.
Appendix
Table 3: Prompt for the verbalized confidence scores.
Dataset
Dataset Type
Dataset Size
Split Setting
Size
MATH-500
Math Reasoning
500
PAC Calibration
300
PAC Test
200
ZebraLogic
Text reasoning
1000
PAC Calibration
500
PAC Test
500
Arena-Hard
Alignment Task
750
PAC Calibration
450
PAC Test
300
Appendix
Table 4: The details of datasets and splitting settings for PAC experiments
System prompt: Think step by step, but only keep a minimum draft for each thinking step, with at most five words. Finally, put your final answer within \boxed{} . User prompt:
Question: {QUESTION}
Appendix
Table 5: Prompt for Chain of Draft.
Figure 2: Error control, ECP and STP of PAC Reasoning for semantic loss across three benchmarks under a confidence level of α=0.05 , on the Llama-3.1-8B–based models. Uncertainty score includes the logits-based score and the verbalized score. All experiments are repeated 100 times, and the shaded areas represent standard deviations.
Figure 3: Error control, ECP and STP of PAC Reasoning for semantic loss for GPQA and HumanEval at a confidence level of α=0.05 . Uncertainty score includes the logits-based score and the verbalized score. The red dashed line ϵ denotes the target tolerance, and the shaded areas represent standard deviations. All experiments are repeated 100 times.
Figure 4: Accuracy of PAC Reasoning based on semantic loss across reasoning benchmarks at a confidence level of α=0.05 . Uncertainty score includes the logits-based score and the verbalized score. All experiments are repeated 100 times, and the shaded areas represent standard deviations.
MATH-500
ZebraLogic
Method / score
Success / 100
95% interval
Success / 100
95% interval
Qwen pair (logits score)
PAC Reasoning
89
[81.17,94.38]
85
[76.47,91.35]
Naive threshold
15
[8.65,23.53]
100
[96.38,100.00]
Naive control
36
[26.64,46.21]
0
[0.00,3.62]
CoD
0
[0.00,3.62]
100
[96.38,100.00]
Appendix
Table 6: Empirical test-loss success counts and two-sided exact 95% binomial intervals over 100 runs. Qwen uses ϵ=0.03 on MATH-500 and ϵ=0.08 on ZebraLogic; the Llama pair uses ϵ=0.1 on both datasets. The intervals are in percent.
Dataset
Method
Total Latency (s)
Dollar Cost ($)
Cheap Model Tokens
Thinking Model Tokens
MATH-500
Only Thinking Model
266.4k
1.71
–
1358.9k
PAC Reasoning
82.2k
0.78
724.4k
125.5k
ZebraLogic
Only Thinking Model
59.8k
4.64
–
3670.1k
PAC Reasoning
43.8k
1.98
1713.3k
981.6k
Appendix
Table 7: Wall-clock latency, token usage, and dollar cost comparison.
Figure 5: Expected Calibration Error across two reasoning benchmarks.
Figure 6: Error control, ECP and STP of PAC Reasoning for semantic loss for different calibration ratios at a confidence level of α=0.05 . Uncertainty score includes the logits-based score and the verbalized score. The red dashed line ϵ denotes the target tolerance, and the shaded areas represent standard deviations. All experiments are repeated 100 times.
Figure 7: Error control, ECP and STP of PAC Reasoning for semantic loss across two reasoning benchmarks at a confidence level of α=0.05 . Uncertainty score is the reward score . All experiments are repeated 100 times, and the shaded areas represent standard deviations.
Uncertainty Score
AIME Size
Error
STP (%)
ECP (%)
Time Saving (%)
Money Saving (%)
Logits-based score
20
0.0193
19.02
26.92
69.02
36.50
40
0.0220
6.56
32.55
67.38
26.51
60
0.0211
0.51
36.97
66.00
21.17
Verbalized score
20
0.0208
19.76
30.18
64.62
37.24
40
0.0278
7.27
35.49
63.04
27.21
60
0.0289
1.19
39.58
61.73
21.86
Appendix
Table 8: Empirical performance under distribution shift with varying proportions of AIME problems. Calibration is performed on MATH-500 ( ϵ=0.03 ).
Target ECP
Method
ϵ
Loss
ECP (%)
Accuracy (%)
≈10%
PAC Reasoning
0.050
0.031±0.015
8.8±8.9
93.7±1.7
Naive control
0.030
0.031±0.014
7.8±2.8
93.6±1.7
≈15%
PAC Reasoning
0.040
0.026±0.013
13.4±12.1
94.1±1.6
Naive control
0.020
0.022±0.012
13.6±6.8
94.4±1.5
≈40%
PAC Reasoning
0.020
0.014±0.010
38.5±21.9
95.1±1.4
Naive control
0.010
0.013±0.009
40.9±17.0
95.1±1.3
Appendix
Table 9: Accuracy–cost operating points on MATH-500 with 300 calibration and 200 test examples. Entries are mean ± standard deviation over 100 splits; ECP and accuracy are percentages.
Target ECP
Method
ϵ
Loss
ECP (%)
Accuracy (%)
≈10%
PAC Reasoning
0.105
0.083±0.021
10.3±5.8
83.2±2.1
Naive control
0.082
0.084±0.016
9.7±3.1
83.1±1.6
≈15%
PAC Reasoning
0.090
0.071±0.020
15.0±6.4
84.2±2.0
Naive control
0.068
0.070±0.015
14.8±3.3
84.2±1.5
≈40%
PAC Reasoning
0.043
0.032±0.012
39.5±7.8
87.1±1.3
Naive control
0.030
0.031±0.010
40.6±4.8
87.2±1.2
Appendix
Table 10: Accuracy–cost operating points on ZebraLogic with 500 calibration and 500 test examples. Entries are mean ± standard deviation over 100 splits; ECP and accuracy are percentages.
Dataset
CoD
NoThinking
MATH-500
54.93±2.70
43.95±2.38
ZebraLogic
88.06±1.06
88.12±1.11
Appendix
Table 11: Accuracy of the fixed baselines without escalation, in percent. Entries are mean ± standard deviation.
Figure 8: MATH-500 comparison with naive control using logits scores. The curves show mean semantic loss over 100 random calibration/test splits, and the shaded areas show one standard deviation. The dashed line marks the target tolerance.
Score
Loss
ECP (%)
STP (%)
Logits
0.0305±0.0021
14.63
23.33
Verbalized
0.0732±0.0018
0.61
45.82
Appendix
Table 12: MATH-500 calibration followed by HumanEval evaluation at ϵ=0.1 . Loss is mean ± standard deviation over 100 repetitions; ECP and STP are percentages.
Score
Test set
Loss
ECP (%)
STP (%)
Logits
MATH-500
0.0209
20.32
39.10
AIME
0.0000
98.33
−33.20
Verbalized
MATH-500
0.0198
25.32
34.44
AIME
0.0100
78.33
−14.29
Appendix
Table 13: MATH-500 reference results and AIME-only evaluation with MATH-500 calibration at ϵ=0.02 for the AIME-only setting. Values are point summaries; ECP and STP are percentages.
Method
Score
Loss
ECP (%)
STP (%)
SR (%)
MATH-500
Naive threshold
Logits
0.0000±0.0000
100.00
−10.06
100
Verbalized
0.2575±0.1129
4.75
81.34
3
Naive control
Logits
0.1713±0.1026
14.62
72.83
14
Verbalized
0.2550±0.1158
7.00
79.62
4
PAC Reasoning
Logits
0.0898±0.1137
68.88
11.75
92
Appendix
Table 14: Results for the Llama-based model pair at ϵ=0.1 . Loss is mean ± standard deviation; ECP and STP are mean percentages over 100 runs. SR is the reported percentage of runs with empirical test loss at most ϵ ; a dash marks an entry not reported in the source table.
Levels K
Tie mass
Two-sided routing jump
Mean fast-route rate
100
0.01
0.02
0.6716
20
0.05
0.10
0.6516
5
0.20
0.40
0.5760
Appendix
Table 15: Score quantization for the CLT rule with n=500 and λ=1 . Values average four bin phases; rates and jumps are fractions.
n
λ
CLT
Exact binomial
Hoeffding
500
1
6.70[5.23,8.43]
4.10[2.96,5.52]
0.00[0.00,0.37]
500
0.25
11.70[9.77,13.86]
4.30[3.13,5.75]
0.00[0.00,0.37]
2000
1
5.00[3.73,6.54]
3.80[2.70,5.18]
0.00[0.00,0.37]
2000
0.25
5.80[4.43,7.43]
3.40[2.37,4.72]
0.00[0.00,0.37]
Appendix
Table 16: Population-risk violation rates and two-sided exact 95% binomial intervals for continuous scores. All entries are percentages, with 1,000 repetitions per setting and α=0.05 .
Figure 9: Score resolution and UCB choice in the full-observation synthetic experiment, with α=0.05 and 1,000 repetitions. (a) Mean fast-route rate and two-sided one-level routing jump for n=500 , λ=1 , and the CLT UCB, averaged over four bin phases. The dashed line is the full-precision fast-route rate. (b) Population-risk violation rates for continuous scores at n=500 , with two-sided exact 95% binomial intervals. The dashed line marks the nominal 5% level.
Method
MATH-500
ZebraLogic
NoThinking
9.63
7.38
CoD
6.63
7.34
PAC Reasoning
6.06
7.53
Appendix
Table 17: Reported mean token use, in thousands of tokens. PAC Reasoning includes calibration-stage token use.
Large Reasoning Models (LRMs) often overthink easy problems and underthink hard ones, leading to inefficient computation allocation. Existing methods regulate generated computation or select between direct answering and explicit reasoning, but do not jointly control whether}to reason and how much computation to allocate within reasoning. We call the resulting difficulty-dependent loss in accuracy under computation reduction the efficiency tax. We propose When2Think, an RLVR-based post-training framework for instance-adaptive computation allocation. Its core mechanism, Instance-level Difficulty-Aware Control (IDAC), uses cached reference statistics of success and token cost to modulate a correctness-gated efficiency bonus based on generated token count. Importance sampling supports exploration of Think and NoThink, while Batch-Wise Standardization constructs standardized advantages for critic-free optimization. The framework requires neither a learned reward model nor a learned critic, and offline reference caching avoids online reference-model queries during policy updates. On AIME24, When2Think improves Pass@3 by 10.0 percentage points while reducing token usage by 27.9% relative to the backbone.
Large Reasoning Models (LRMs) have shown remarkable reasoning capabilities, yet they often suffer from overthinking, expending redundant computational steps on simple problems, or underthinking, failing to explore sufficient reasoning paths despite inherent capabilities. These issues lead to inefficiencies and potential inaccuracies, limiting practical deployment in resource-constrained settings. Existing methods to mitigate overthinking, such as suppressing reflective keywords or adjusting reasoning length, may inadvertently induce underthinking, compromising accuracy. Therefore, we propose ReBalance, a training-free framework that achieves efficient reasoning with balanced thinking. ReBalance leverages confidence as a continuous indicator of reasoning dynamics, identifying overthinking through high confidence variance and underthinking via consistent overconfidence. By aggregating hidden states from a small-scale dataset into reasoning mode prototypes, we compute a steering vector to guide LRMs' reasoning trajectories. A dynamic control function modulates this vector's strength and direction based on real-time confidence, pruning redundancy during overthinking, and promoting exploration during underthinking. Extensive experiments conducted on four models ranging from 0.5B to 32B, and across nine benchmarks in math reasoning, general question answering, and coding tasks demonstrate that ReBalance effectively reduces output redundancy while improving accuracy, offering a general, training-free, and plug-and-play strategy for efficient and robust LRM deployment. Project page and code are available at https://rebalance-ai.github.io .
Yulin Li, Tengyao Tu, Li Ding +5
Harbin Institute of Technology (Shenzhen) · Zhongguancun Academy · Huawei Noah’s Ark Lab +3
Large Reasoning Models (LRMs) have shown remarkable reasoning capabilities, yet they still suffer from overthinking, generating redundant reasoning steps which incur substantial token consumption. Existing methods, such as suppressing reflective keywords or forcing shorter reasoning lengths, attempt to mitigate this issue but inevitably truncate necessary steps and induce underthinking, thereby compromising performance. To address this dilemma, we investigate the latent representations and observe that efficient reasoning steps naturally cluster into a concentrated region in latent space, while those deviating from this region tend to produce verbose sequences. To leverage this, we keep reasoning focused within this region via a quadratic program which projects deviating hidden states back into the region. Then we propose a novel training-free framework to achieve efficient reasoning that reduces token generation costs without sacrificing performance. Extensive experiments conducted on four models ranging from 1.5B to 14B, and across six benchmarks in math reasoning, coding, and scientific QA, validate the effectiveness of our method, up to a 12.1% improvement in accuracy while reducing generated tokens by 11.8% to 52.8%. Codes are available at https://github.com/hzn18/Opt4Reasoning.