Anytime Safe PAC Efficient Reasoning

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.

Powerful AI models can now think step-by-step to solve highly complex problems, but this deep reasoning makes them slow and expensive—even when answering simple questions. A practical solution is a routing system: sending easy questions to a fast, cheap AI, while reserving the deep-thinking AI only for difficult tasks. However, current routing systems usually lead to uncontrollable error rates in real-world. To solve this, we introduce B-PAC reasoning, a new method that treats the routing decision like a mathematical betting game. Our system places "bets" on the confidence of the fast AI. Every time the fast AI proves it can safely handle a task, the system wins "virtual wealth", increasing its trust in the faster model. If errors start to exceed the tolerance level, it loses wealth and becomes more cautious. Extensive experiments show that B-PAC reasoning drastically reduces computational overhead, decreasing the expensive model usage by up to 81.01%, while controlling the performance loss below the user-specified level.