# Conditional Performance Guarantee for Large Reasoning Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 29 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, 29 of 29)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [Qwen3 Embedding: Advancing Text Embedding and Reranking Through Foundation Models](https://mlsanity.com/paper/2506.05176/) (2025)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [The Lessons of Developing Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2501.07301/) (2025)
- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Dynamic Early Exit in Reasoning Models](https://mlsanity.com/paper/2504.15895/) (2025)
- [Reasoning Models Can Be Effective Without Thinking](https://mlsanity.com/paper/2504.09858/) (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)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Don't Overthink It: A Survey of Efficient R1-style Large Reasoning Models](https://mlsanity.com/paper/2508.02120/) (2025)
- [Fast-Slow Thinking GRPO for Large Vision-Language Model Reasoning](https://mlsanity.com/paper/2504.18458/) (2025)
- [OptimalThinkingBench: Evaluating Over and Underthinking in LLMs](https://mlsanity.com/paper/2508.13141/) (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)
- [FlashThink: An Early Exit Method For Efficient Reasoning](https://mlsanity.com/paper/2505.13949/) (2025)
- [Leveraging Uncertainty Estimation for Efficient LLM Routing](https://mlsanity.com/paper/2502.11021/) (2025)
- [A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning](https://mlsanity.com/paper/2510.15444/) (2025)
- [Thinker: Learning to Think Fast and Slow](https://mlsanity.com/paper/2505.21097/) (2025)
- [On the Provable Performance Guarantee of Efficient Reasoning Models](https://mlsanity.com/paper/2510.09133/) (2025)
- [A note on conditional PAC-efficient reasoning in large language model routing](https://mlsanity.com/paper/2512.03057/) (2025)

## Abstract (arXiv)

Large reasoning models have shown strong performance through extended chain-of-thought reasoning, yet their computational cost remains significant. Probably approximately correct (PAC) reasoning provides statistical guarantees for efficient reasoning by adaptively switching between thinking and non-thinking models, but the guarantee holds only in the marginal case and does not provide exact conditional coverage. We propose G-PAC reasoning, a practical framework that provides PAC-style guarantees at the group level by partitioning the input space. We develop two instantiations: Group PAC (G-PAC) reasoning for known group structures and Clustered PAC (C-PAC) reasoning for unknown groupings. We prove that both G-PAC and C-PAC achieve group-conditional risk control, and that grouping can strictly improve efficiency over marginal PAC reasoning in heterogeneous settings. Our experiments on diverse reasoning benchmarks demonstrate that G-PAC and C-PAC successfully achieve group-conditional risk control while maintaining substantial computational savings.