# A note on conditional PAC-efficient reasoning in large language model routing

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

## Key facts

- Cited by 3 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 29 of its 41 references that are in the map.
- First posted on arXiv 25 Nov 2025.

## 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)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.16419/) (2025)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Conformal Prediction With Conditional Guarantees](https://mlsanity.com/paper/2305.12616/) (2023)
- [Testing for Outliers with Conformal p-values](https://mlsanity.com/paper/2104.08279/) (2021)
- [Localized Conformal Prediction: A Generalized Inference Framework for Conformal Prediction](https://mlsanity.com/paper/2106.08460/) (2021)
- [A Unified Approach to Routing and Cascading for LLMs](https://mlsanity.com/paper/2410.10347/) (2024)
- [On the Algorithmic Bias of Aligning Large Language Models with RLHF: Preference Collapse and Matching Regularization](https://mlsanity.com/paper/2405.16455/) (2024)
- [Conformalized Survival Analysis](https://mlsanity.com/paper/2103.09763/) (2021)
- [Selection and Aggregation of Conformal Prediction Sets](https://mlsanity.com/paper/2104.13871/) (2021)
- [Conformal prediction with local weights: randomization enables local guarantees](https://mlsanity.com/paper/2310.07850/) (2023)
- [OptimalThinkingBench: Evaluating Over and Underthinking in LLMs](https://mlsanity.com/paper/2508.13141/) (2025)
- [LAMBDA: A Large Model Based Data Agent](https://mlsanity.com/paper/2407.17535/) (2024)
- [Fast Exact Conformalization of Lasso using Piecewise Linear Homotopy](https://mlsanity.com/paper/1708.00427/) (2017)
- [CP-Router: An Uncertainty-Aware Router Between LLM and LRM](https://mlsanity.com/paper/2505.19970/) (2025)
- [A Two-Sample Conditional Distribution Test Using Conformal Prediction and Weighted Rank Sum](https://mlsanity.com/paper/2010.07147/) (2020)
- [Debiasing Watermarks for Large Language Models via Maximal Coupling](https://mlsanity.com/paper/2411.11203/) (2024)
- [Conformalized survival analysis with adaptive cutoffs](https://mlsanity.com/paper/2211.01227/) (2022)
- [Towards Better Statistical Understanding of Watermarking LLMs](https://mlsanity.com/paper/2403.13027/) (2024)
- [Conformal Prediction for Network-Assisted Regression](https://mlsanity.com/paper/2302.10095/) (2023)
- [Selective conformal inference with false coverage-statement rate control](https://mlsanity.com/paper/2301.00584/) (2023)
- [On the Provable Performance Guarantee of Efficient Reasoning Models](https://mlsanity.com/paper/2510.09133/) (2025)

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

- [RACER: Risk-Aware Calibrated Efficient Routing for Large Language Models](https://mlsanity.com/paper/2603.06616/) (2026)
- [Anytime Safe PAC Efficient Reasoning](https://mlsanity.com/paper/2601.22446/) (2026)
- [Conditional Performance Guarantee for Large Reasoning Models](https://mlsanity.com/paper/2601.22790/) (2026)

## Abstract (arXiv)

We study distribution-free risk control for model routing, motivated by large language model reasoning. We formalize pointwise conditional efficiency under a probably approximately correct guarantee and show that it forces a nearly impossible router: at almost every input where the fast model exceeds the target loss, the algorithm must route to the expert with probability at least one minus the prescribed error level. We therefore introduce a restricted conditional formulation based on a prespecified family of conditioning sets, together with an explicit router. The proposed router achieves finite-sample conditional validity and, under separation and margin conditions, near-oracle expert usage. The main insight is that the level of conditioning determines whether distribution-free reliability can coexist with computational savings: pointwise control is too strong, whereas structured setwise control remains feasible.