Think Until No Future Thought Can Help: Certified Remaining-Gain Stopping for Adaptive-Compute Policies

Adaptive-compute policies commonly stop on confidence or latent convergence rather than the decision consequence of further computation. We introduce , which certifies the remaining gain: the largest improvement in a fixed reference utility that any uncomputed future prefix could provide over the current action. A normalized split-conformal score gives simultaneous coverage across depths under exchangeability, supporting adaptive stopping and post-calibration tolerance choice. We derive stopping-risk, expected-gain, oracle-depth, critic-error, shift and performance-difference guarantees, and distinguish population occupancy calibration from empirical recalibration. At matched violation rates on six graph tasks, requires $2.54$ recurrent steps versus $5.29$ for the best heuristic gate calibrated by Learn-Then-Test. Across eight planning tasks and forty training runs, removes $70.2\%$ of recurrent steps at $95.14\%$ simultaneous coverage. On all five MinAtar games, the policy is trained by $Q$-learning for $5$M frames with five seeds, using its own frozen critic as reference. Held-out coverage averages $95.26\%$, with $49.7\%$ fewer recurrent steps and $99.2\%$ of full-compute return. Equivalence holds within $\pm 5\%$ ($p=0.041$); a confidence gate at the same risk target requires $1.82\times$ the depth for indistinguishable return. CPU speedups range from $3.91\times$ to $4.91\times$, and a scalar remaining-gain head matches the structured lattice at lower cost. Empirical occupancy recalibration restores near-nominal held-out coverage on average after adaptive deployment shifts the state distribution.