# Anytime Safe PAC Efficient Reasoning

arXiv: https://arxiv.org/abs/2601.22446 · HTML: https://mlsanity.com/paper/2601.22446/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 25 of its 52 references that are in the map.
- First posted on arXiv 30 Jan 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 25 of 25)

- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs](https://mlsanity.com/paper/2412.21187/) (2024)
- [Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.16419/) (2025)
- [Chain of Draft: Thinking Faster by Writing Less](https://mlsanity.com/paper/2502.18600/) (2025)
- [To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoning](https://mlsanity.com/paper/2409.12183/) (2024)
- [Reasoning Models Can Be Effective Without Thinking](https://mlsanity.com/paper/2504.09858/) (2025)
- [The Danger of Overthinking: Examining the Reasoning-Action Dilemma in Agentic Tasks](https://mlsanity.com/paper/2502.08235/) (2025)
- [Thinkless: LLM Learns When to Think](https://mlsanity.com/paper/2505.13379/) (2025)
- [On Verbalized Confidence Scores for LLMs](https://mlsanity.com/paper/2412.14737/) (2024)
- [A Unified Approach to Routing and Cascading for LLMs](https://mlsanity.com/paper/2410.10347/) (2024)
- [Admissible anytime-valid sequential inference must rely on nonnegative martingales](https://mlsanity.com/paper/2009.03167/) (2020)
- [ThinkSwitcher: When to Think Hard, When to Think Fast](https://mlsanity.com/paper/2505.14183/) (2025)
- [Think or Not? Exploring Thinking Efficiency in Large Reasoning Models via an Information-Theoretic Lens](https://mlsanity.com/paper/2505.18237/) (2025)
- [Think More, Hallucinate Less: Mitigating Hallucinations via Dual Process of Fast and Slow Thinking](https://mlsanity.com/paper/2501.01306/) (2025)
- [Thinking Slow, Fast: Scaling Inference Compute with Distilled Reasoners](https://mlsanity.com/paper/2502.20339/) (2025)
- [DynaThink: Fast or Slow? A Dynamic Decision-Making Framework for Large Language Models](https://mlsanity.com/paper/2407.01009/) (2024)
- [Thinker: Learning to Think Fast and Slow](https://mlsanity.com/paper/2505.21097/) (2025)
- [Probably Approximately Correct Labels](https://mlsanity.com/paper/2506.10908/) (2025)
- [On the Provable Performance Guarantee of Efficient Reasoning Models](https://mlsanity.com/paper/2510.09133/) (2025)
- [DynamicMind: A Tri-Mode Thinking System for Large Language Models](https://mlsanity.com/paper/2506.05936/) (2025)
- [A note on conditional PAC-efficient reasoning in large language model routing](https://mlsanity.com/paper/2512.03057/) (2025)
- [A generalized e-value feature detection method with FDR control at multiple resolutions](https://mlsanity.com/paper/2409.17039/) (2024)

## Built on by (most cited first, 1 of 1)

- [On the Pitfalls of Verbalized Confidence Priors for Calibrating Large Reasoning Models](https://mlsanity.com/paper/2609.32470/) (2026)

## Abstract (arXiv)

Large Reasoning Models (LRMs) have demonstrated remarkable performance on complex tasks but suffer from high computational costs and latency. While selective thinking strategies improve efficiency by routing easy queries to non-thinking models, existing approaches often incur uncontrollable errors, especially in online settings where the performance loss of a non-thinking model is only partially observed and data are non-stationary. To address this, we propose Betting Probably Approximately Correct (B-PAC) reasoning, a principled method that enables anytime safe and efficient online reasoning under partial feedback. Specifically, we utilize inverse propensity scoring estimators to construct test supermartingales for candidate thresholds, and then dynamically adjust the routing threshold based on the accumulated statistical evidence of safety. Theoretically, we establish the anytime-valid performance loss control and the efficiency of B-PAC reasoning. Extensive experiments demonstrate that B-PAC reasoning significantly reduces computational overhead, decreasing thinking model usage by up to 81.01%, while controlling the performance loss below the user-specified level.