PAC Reasoning: Controlling the Performance Loss for Efficient Reasoning

• URL: http://arxiv.org/abs/2510.09133v1
• Date: Fri, 10 Oct 2025 08:33:47 GMT
• Title: PAC Reasoning: Controlling the Performance Loss for Efficient Reasoning
• Authors: Hao Zeng, Jianguo Huang, Bingyi Jing, Hongxin Wei, Bo An,
• Abstract summary: Large reasoning models (LRMs) have achieved remarkable progress in complex problem-solving tasks.<n>LRMs typically suffer from high computational costs during deployment.<n>We propose Probably Approximately Correct (PAC) reasoning that controls the performance loss under the user-specified performance loss tolerance.
• Score: 33.71268958080582
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• ODAR: Principled Adaptive Routing for LLM Reasoning via Active Inference [60.958331943869126]
  ODAR-Expert is an adaptive routing framework that optimize the accuracy-efficiency trade-off via principled resource allocation.<n>We show strong and consistent gains, including 98.2% accuracy on MATH and 54.8% on Humanity's Last Exam.
  arXiv  Detail & Related papers  (2026-02-27T05:22:01Z)
• Conformal Thinking: Risk Control for Reasoning on a Compute Budget [60.65072883773352]
  Reasoning Large Language Models (LLMs) enable test-time scaling, with dataset-level accuracy improving as the token budget increases.<n>We re-frame the budget setting problem as risk control, limiting the error rate while minimizing compute.<n>Our framework introduces an upper threshold that stops reasoning when the model is confident and a novel lower threshold that preemptively stops unsolvable instances.
  arXiv  Detail & Related papers  (2026-02-03T18:17:22Z)
• EntroCut: Entropy-Guided Adaptive Truncation for Efficient Chain-of-Thought Reasoning in Small-scale Large Reasoning Models [42.49934375597466]
  Large Reasoning Models (LRMs) excel at complex reasoning tasks through extended chain-of-thought generation.<n>We find that the entropy of the model's output distribution in early reasoning steps reliably distinguishes correct from incorrect reasoning.<n>We propose EntroCut, a training-free method that dynamically truncates reasoning by identifying high-confidence states.
  arXiv  Detail & Related papers  (2026-01-30T06:19:16Z)
• Anytime Safe PAC Efficient Reasoning [8.618430092165498]
  Large Reasoning Models (LRMs) have demonstrated remarkable performance on complex tasks but suffer from high computational costs and latency.<n>We propose Betting Probably Approximately Correct (B-PAC) reasoning, a principled method that enables anytime safe and efficient online reasoning under partial feedback.
  arXiv  Detail & Related papers  (2026-01-30T01:30:17Z)
• Conditional Advantage Estimation for Reinforcement Learning in Large Reasoning Models [50.84995206660551]
  We introduce Conditional advANtage estimatiON (CANON) to amplify the impact of a target metric without presuming its direction.<n>CANON based on entropy consistently outperforms prior methods on both math reasoning and high-complexity logic tasks.
  arXiv  Detail & Related papers  (2025-09-28T16:33:07Z)
• Exploring and Exploiting the Inherent Efficiency within Large Reasoning Models for Self-Guided Efficiency Enhancement [101.77467538102924]
  Large reasoning models (LRMs) exhibit overthinking, which hinders efficiency and inflates inference cost.<n>We propose two lightweight methods to enhance LRM efficiency.<n>First, we introduce Efficiency Steering, a training-free activation steering technique that modulates reasoning behavior via a single direction.<n>Second, we develop Self-Rewarded Efficiency RL, a reinforcement learning framework that dynamically balances task accuracy and brevity.
  arXiv  Detail & Related papers  (2025-06-18T17:18:12Z)
• How Far Are We from Optimal Reasoning Efficiency? [23.593914897406943]
  Large Reasoning Models (LRMs) demonstrate remarkable problem-solving capabilities through extended Chain-of-Thought (CoT) reasoning.<n>LRMs often produce excessively verbose and redundant reasoning traces.<n>Existing fine-tuning methods aim to improve reasoning efficiency, but assessing their efficiency gains remains challenging.
  arXiv  Detail & Related papers  (2025-06-08T12:18:50Z)
• When to Continue Thinking: Adaptive Thinking Mode Switching for Efficient Reasoning [20.233873556056487]
  Large reasoning models (LRMs) achieve remarkable performance via long reasoning chains, but often incur excessive computational overhead due to redundant reasoning.<n>We propose Adaptive Self-Recovery Reasoning (ASRR), a framework that suppresses unnecessary reasoning and enables implicit recovery.<n>Our results highlight the potential of ASRR for enabling efficient, adaptive, and safer reasoning in LRMs.
  arXiv  Detail & Related papers  (2025-05-21T11:41:39Z)
• The Larger the Merrier? Efficient Large AI Model Inference in Wireless Edge Networks [56.37880529653111]
  The demand for large computation model (LAIM) services is driving a paradigm shift from traditional cloud-based inference to edge-based inference for low-latency, privacy-preserving applications.<n>In this paper, we investigate the LAIM-inference scheme, where a pre-trained LAIM is pruned and partitioned into on-device and on-server sub-models for deployment.
  arXiv  Detail & Related papers  (2025-05-14T08:18:55Z)
• ConCISE: Confidence-guided Compression in Step-by-step Efficient Reasoning [64.93140713419561]
  Large Reasoning Models (LRMs) perform strongly in complex reasoning tasks via Chain-of-Thought (CoT) prompting, but often suffer from verbose outputs.<n>Existing fine-tuning-based compression methods either operate post-hoc pruning, risking disruption to reasoning coherence, or rely on sampling-based selection.<n>We introduce ConCISE, a framework designed to generate concise reasoning chains, integrating Confidence Injection to boost reasoning confidence, and Early Stopping to terminate reasoning when confidence is sufficient.
  arXiv  Detail & Related papers  (2025-05-08T01:40:40Z)
• Thought Manipulation: External Thought Can Be Efficient for Large Reasoning Models [32.49420948390984]
  Large reasoning models (LRMs) often suffer from an overthinking'' problem, where the model generates excessively redundant reasoning steps with limited performance gains.<n>We propose a simple yet efficient pipeline, Method, to enable LRMs to bypass unnecessary intermediate steps, thereby significantly reducing computational costs.
  arXiv  Detail & Related papers  (2025-04-18T11:07:19Z)
• Bridging Internal Probability and Self-Consistency for Effective and Efficient LLM Reasoning [53.25336975467293]
  We present the first theoretical error decomposition analysis of methods such as perplexity and self-consistency.<n>Our analysis reveals a fundamental trade-off: perplexity methods suffer from substantial model error due to the absence of a proper consistency function.<n>We propose Reasoning-Pruning Perplexity Consistency (RPC), which integrates perplexity with self-consistency, and Reasoning Pruning, which eliminates low-probability reasoning paths.
  arXiv  Detail & Related papers  (2025-02-01T18:09:49Z)
• Reward-Guided Speculative Decoding for Efficient LLM Reasoning [80.55186052123196]
  We introduce Reward-Guided Speculative Decoding (RSD), a novel framework aimed at improving the efficiency of inference in large language models (LLMs)<n>RSD incorporates a controlled bias to prioritize high-reward outputs, in contrast to existing speculative decoding methods that enforce strict unbiasedness.<n>RSD delivers significant efficiency gains against decoding with the target model only, while achieving significant better accuracy than parallel decoding method on average.
  arXiv  Detail & Related papers  (2025-01-31T17:19:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.