PAC Reasoning: Controlling the Performance Loss for Efficient Reasoning

Hao Zeng, Jianguo Huang, Bingyi Jing, Hongxin Wei, Bo AnSubmission to ICLR 2026 · Rejected

TL;DR

Large reasoning models (LRMs) spend substantial compute generating long chains of thought, even on simple problems. PAC Reasoning provides a mathematically principled way to route queries between a cheap "non-thinking" model and an expensive "thinking" model while guaranteeing—with user-specified statistical confidence ($1 - \alpha$)—that performance degradation remains below a chosen tolerance level ($\epsilon$).

What Problem Does This Paper Address?

Recent reasoning-focused language models (such as DeepSeek-R1) excel at complex tasks by spending extra test-time compute on long deliberation steps. However, they frequently suffer from overthinking—expending hundreds of unnecessary reasoning tokens on simple questions.

To curb inference latency and operational costs, practitioners often switch dynamically between fast "non-thinking" modes and slow "thinking" modes. Unfortunately, existing routing mechanisms are purely heuristic: when the cheap model fails, it can introduce subtle calculation errors, logical invalidity, or hallucinations. High-stakes applications lack any formal guarantee of how much accuracy is being sacrificed for efficiency.

Methods

The authors formalize the concept of an $(\epsilon, \alpha)$-PAC Efficient Model, where the expected risk relative to the full expert thinking model $f$ does not exceed error tolerance $\epsilon$ with probability at least $1 - \alpha$: $$\mathbb{P}(R(\hat{f}) \le \epsilon) \ge 1 - \alpha$$

The core pipeline operates as follows:

  1. Uncertainty Quantification: For an input $x$, the cheap model $\tilde{f}$ generates a response and an uncertainty score $U(x) \in [0, 1]$. The paper tests both white-box scores (average negative token log-probabilities) and black-box scores (verbalized self-confidence prompts).
  2. Monotone Cumulative Error Function: The error rate incurred by accepting the cheap model when $U(x) \le u$ is monotonically non-decreasing in threshold $u$.
  3. Statistical Upper Confidence Bound (UCB): Using an importance-sampled calibration dataset, the authors build an empirical upper confidence bound $\hat{L}_u(\alpha)$ via the Central Limit Theorem (CLT) or finite-sample concentration inequalities (e.g., Hoeffding's inequality).
  4. Learn-Then-Test (LTT) Calibration: Because the cumulative loss function is monotonic, the system selects the maximum threshold $\hat{u} = \max\{u : \hat{L}_u(\alpha) \le \epsilon\}$ using fixed-sequence testing. This avoids multi-hypothesis correction penalties while preserving distribution-free finite-sample guarantees.
  5. Deployment: On new queries, if $U(x) < \hat{u}$, the system serves the fast model; if $U(x) \ge \hat{u}$, it invokes the full reasoning model.

Datasets

The authors evaluated their framework on standard open benchmarks; no new benchmark datasets were created. The evaluation datasets include:

  • MATH-500: High-level mathematical problem solving (300 calibration / 200 test).
  • ZebraLogic: Grid-based logical deduction puzzles (500 calibration / 500 test).
  • Arena-Hard: Alignment-focused open-ended text generation benchmark (450 calibration / 300 test).
  • GPQA and HumanEval: Tested in extended experiments for domain-expert scientific QA and code generation.

Evaluations were performed across Qwen3-4B (Thinking vs. Instruct) and Llama-3.1-8B (DeepSeek-R1-Distill-8B vs. Instruct) model pairs using both binary 0–1 accuracy loss and semantic embedding cosine distance.

Key Insights and Ideas

  • Monotonicity bypasses multi-testing penalties: In standard hypothesis testing across multiple thresholds, strict corrections (like Bonferroni) usually make bounds overly conservative. Because cumulative error strictly grows with the uncertainty threshold, the threshold selection reduces to single-start fixed-sequence testing under the Learn-Then-Test framework.
  • Perfect calibration is unnecessary: Even when uncertainty estimators exhibit miscalibration (e.g., non-zero Expected Calibration Error), PAC guarantees remain valid. The framework only relies on the scores providing an informative ranking of disagreement likelihood.
  • Logits outperform verbalized confidence: White-box token probabilities provide smoother, lower-variance thresholds than verbalized confidence scores, which tend to cluster and show overconfidence.
  • Plug-and-play scoring: The uncertainty metric is modular; replacing internal logits with off-the-shelf Process Reward Models (PRMs) preserves rigorous error control.

Key Results

  • Guaranteed Error Control: Across all tasks, the empirical error strictly respected user-specified bounds ($\epsilon$). For example, on Arena-Hard with target semantic tolerance $\epsilon = 0.08$, logits-based PAC reasoning held empirical error at $\approx 0.06$.
  • Significant Token Savings:
  • On Arena-Hard, the method called the thinking expert only $\sim 20\%$ of the time, achieving $>40\%$ Saved Token Percentage (STP).
  • On MATH-500 ($\epsilon = 0.03$), it saved $37.61\%$ of tokens while preserving a Pass@1 of $0.95$.
  • Failures of Heuristic Baselines: A naive fixed threshold ($U_i \ge 0.05$) either violated the error budget on MATH-500 ($0.0346$ error vs. $0.03$ target) or severely hurt efficiency on ZebraLogic ($-34.78\%$ STP, requiring more compute than default thinking due to overhead). Meanwhile, methods like Chain of Draft and NoThinking suffered drastic accuracy drops (Pass@1 dropping to $0.61$ and $0.50$).

Limitations and Future Work

  • Dependence on Uncertainty Metrics: The system requires an uncertainty score correlated with true error. If the non-thinking model is completely blind to its own mistakes, savings diminish.
  • Calibration Overhead: Labeling calibration instances with the full reasoning model introduces upfront computational cost (partially mitigated via importance sampling).
  • I.I.D. Assumption: Theoretical guarantees rely on calibration and test data being independently drawn from the same distribution. Severe out-of-distribution drift invalidates standard bounds.
  • Future Directions Outlined:
  • Conditional PAC: Computing separate thresholds per subject category (preliminary results show an additional 5–10% token savings).
  • Anytime-Valid PAC: Streaming inference using martingale-based confidence sequences and drift-detecting $e$-processes.
  • Multi-Tier Routing: Cascading through $K > 2$ models (e.g., tiny model $\rightarrow$ medium model $\rightarrow$ full reasoning model).

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},
}

Loading related content...

Figure