Research map / Large language models / Reasoning and chain of thought
Anytime Safe PAC Efficient Reasoning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes B-PAC reasoning, an anytime-valid betting-supermartingale routing method with IPS estimates that switches between a thinking and non-thinking Qwen3 model while bounding performance loss relative to the thinking model under partial feedback.
Problem
Selective thinking routes queries between thinking and non-thinking LRMs with heuristic rules that lack risk guarantees; offline PAC reasoning needs i.i.d. calibration data and cannot handle online partial feedback or non-stationary streams.
Approach
Construct inverse-propensity-scored risk estimates of the non-thinking model's loss, build test supermartingales (betting wealth) per candidate routing threshold, and pick the largest threshold whose wealth stays above 1/alpha (fixed sequence testing), with an online convex-optimization betting rule and mixture-of-martingales extension for non-stationary data.
Key results
- On Magpie with epsilon=0.08, B-PAC routes only 18.99% of queries to the thinking model (ECP) and yields 58.63% token percentage while keeping empirical loss below epsilon.
- On MMLU-Pro, B-PAC reasoning achieves ECP=47.04% and TP=78.07% while O-naive violates risk and IPS+Hoeff uses near 100% expert calls.
- Abstract claims thinking model usage reduced by up to 81.01% while controlling performance loss below the user-specified level.
Surprising findings
- Heuristic baselines CoD and NoThinking violate the risk tolerance on MATH and MMLU-Pro, while the naive online routing (O-naive) also fails to control risk.
Limitations
- Routes between only two models; extension to multiple models unresolved.
- Efficiency depends on uncertainty score quality, and selecting among multiple scores is unresolved.
- Evaluation uses filtered subsets where thinking model is correct or preferred, and risk is measured relative to the thinking model rather than ground truth.
Experimental setup
Datasets: MATH MMLU-Pro BIG-Bench Hard Magpie
Benchmarks: MATH MMLU-Pro BIG-Bench Hard Magpie
Metrics: empirical risk expert call percentage token percentage
Baselines: PAC reasoning O-naive IPS+Hoeff Chain of Draft NoThinking
Builds on: PAC reasoning Ville's inequality fixed sequence testing inverse propensity scoring Learn then Test
Closest papers by meaning
- Conformal Thinking: Risk Control for Reasoning on a Compute Budget (ICML 2026 · similarity 0.87)
- Reasoning Is Not Free: Robust Adaptive Cost-Efficient Routing for LLM-as-a-Judge (ICML 2026 · similarity 0.87)
- Optimizing Anytime Reasoning via Budget Relative Policy Optimization (NeurIPS 2025 · similarity 0.86)
- How Far Are We from Optimal Reasoning Efficiency? (NeurIPS 2025 · similarity 0.86)
- Promoting Efficient Reasoning with Verifiable Stepwise Reward (AAAI 2026 · similarity 0.86)
- SuCo: Sufficiency-guided Continuous Adaptive Reasoning (ICML 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.