acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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 recurrent steps versus for the best heuristic gate calibrated by Learn-Then-Test. Across eight planning tasks and forty training runs, removes of recurrent steps at simultaneous coverage. On all five MinAtar games, the policy is trained by -learning for M frames with five seeds, using its own frozen critic as reference. Held-out coverage averages , with fewer recurrent steps and of full-compute return. Equivalence holds within (); a confidence gate at the same risk target requires the depth for indistinguishable return. CPU speedups range from to , 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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
adaptive computation, conformal prediction, risk control, early exit, reinforcement learning, test-time compute, recurrent policies, distribution shift

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_vuRqOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces RARE2\texttt{RARE}^2, a certified stopping framework for adaptive-compute policies that iteratively refine candidate actions through recurrent computation. Specifically, RARE2\texttt{RARE}^2 defines the remaining gain as the maximum improvement in a fixed reference utility achievable by any future computation prefix, and employs a prediction head with split-conformal calibration to construct a statistically valid upper bound on this gain. The paper further establishes theoretical guarantees on stopping risk, expected gain, oracle depth, critic error, distribution shift, and policy performance differences. Experiments on graph tasks, planning benchmarks, and MinAtar demonstrate substantial reductions in recurrent computation while maintaining high coverage and near-full-compute returns.

Critical strengths
  • The paper establishes theoretical guarantees on stopping risk, expected gain, and related quantities, providing a principled foundation for adaptive computation. Moreover, the simultaneous conformalization procedure supports adaptive stopping across recurrent depths, while allowing users to adjust the stopping tolerance without retraining the policy or recalibrating the conformal quantile, provided the calibration assumptions remain satisfied.

  • The experiments demonstrate consistent computational savings across graph, planning, and MinAtar tasks. For example, the proposed method reduces recurrent computation by 49.7% on MinAtar while retaining 99.2% of the full-compute return.

Critical weaknesses
  • The practical validity of this guarantee depends on the accuracy of the reference utility and the tightness of the critic-error bound. However, the robustness of the proposed method to varying levels of reference utility quality has not been empirically evaluated.

  • The conformal coverage guarantee relies on exchangeability between calibration and deployment samples. However, adaptive stopping may alter the state occupancy distribution in sequential decision-making, potentially violating this assumption and undermining the coverage guarantee. Although the paper investigates occupancy recalibration and reports improved empirical coverage, it remains unclear whether the guarantee can be maintained under more general distribution shifts or how robust the recalibration procedure is to such shifts.

Questions for authors
  • How well does the method generalize beyond the evaluated settings? It remains unclear how well the proposed method scales to more complex recurrent policies and high-dimensional tasks, such as vision-based robotic control. Evaluations in these settings would help establish the broader applicability of the framework.

  • Although the paper compares RARE2\texttt{RARE}^2 with several early-exit baselines, it is unclear whether the experiments directly validate the claim that agreement with the full-compute output is an inadequate proxy for decision utility. Can the authors provide evidence that the observed gains stem from certifying remaining decision utility, rather than from differences in calibration procedures or stopping-rule design?

Reviewer_hfWbOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Considering that current adaptive-compute policies (e.g., early exiting, recurrent depth in RL/LLMs) typically decide when to stop computing based on heuristics like confidence, action agreement, or latent convergence, these metrics fail to measure the actual consequence of stopping. This paper proposes RARE2 (Certified Remaining-Gain Stopping). Instead of measuring confidence, RARE2 certifies the remaining gain: the maximum possible improvement in a fixed reference utility. By experimenting on six graph tasks, the authors verify that the proposed method requires less recurrent steps and maintains high simultaneous coverage.

Critical strengths
  1. The most critical strength of this work is its motivation, which shifts adaptive-compute stopping from confidence-based heuristics to decision-value-based reasoning. RARE² provides a seemingly principled method for connecting computational effort to the potential value of further computation.
Critical weaknesses
  1. The paper is difficult to follow and lacks the clarity, coherence, and structure expected of a scientific paper. The presentation feels overly loose, making it unnecessarily difficult for readers to follow the logical progression of the arguments and identify the key contributions. Substantial improvements in writing and organization are needed to communicate the ideas effectively.

  2. The key to this work is how to estimate the reference utility qq, which determines whether further computation can meaningfully improve a decision. However, the experiments rely on task-specific utilities, such as shortest-path and puzzle utilities, or a frozen fitted-Q critic. These choices leave a fundamental question unanswered: How can the reference utility be reliably estimated in realistic settings where the true utility is not readily available? The concept of remaining gain itself is not particularly novel; the more interesting and technically challenging contribution would be a principled and effective method for estimating it. Without a more convincing solution to this problem, the practical novelty and applicability of the proposed approach remain limited.

Questions for authors
  1. The writing and organization of the paper make it difficult to follow the theoretical arguments, particularly the proof of the proposed guarantee. In the rebuttal, the authors should provide a clearer, step-by-step explanation of how the remaining gain is computed and how the theoretical guarantee is established, explicitly connecting the key assumptions, intermediate steps, and final result.
Reviewer_6ndHOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper trains a recurrent policy that can stop "thinking" early (fewer recurrent steps per decision) and gives a guarantee for when to stop. With split conformal prediction, it certifies that stopping loses at most ϵ\epsilon in utility compared with any later step (the "remaining gain", so they need a clear reward or gain concept). One calibration covers all later steps at once, and ϵ\epsilon can be chosen after calibration. This conformal step is actually very standard, and paper also mentions this (Sec. 3.3). What is new is what gets certified: the remaining gain, i.e., how much better the action could still get from more thinking, instead of whether the action would change. Experiments use small puzzle- and game-like environments where every action can be scored or evaluated, either exactly or by the policy's own critic: 8 small planning tasks (graph navigation and the LightsOut puzzle), 5 MinAtar mini-games, and CartPole. The proposed method more than halves the thinking steps without losing performance or very small margin.

Critical strengths
  1. The idea is clear and intuitive because the policy predicts how much better its action could still get from more thinking, and stops when that remaining gain is small. This uses the consequence of stopping, not a confidence heuristic.

  2. The comparisons are fair because every baseline stopping rule is recalibrated to the same risk before comparison. At matched violation, RARE2 needs 2.54 steps vs 5.29 for the best heuristic gate.

Critical weaknesses
  1. The experimental results are very weak to conclude the usefulness of the method. The headline comes from planning graphs (up to 49 nodes) and LightsOut, where 7 of 8 tasks are trained by imitating exact optimal actions. So, most of the results are not from RL training. The RL tests are MinAtar (10x10) and a 6-step CartPole that saves only 4.6% of compute. There is no Atari, Procgen, robotics (the paper says so), or language model.

  2. The guarantee needs a score for every action at every state, not just an episode reward. In 7 of 8 planning tasks this score is an exact oracle, which real problems do not have. In MinAtar it is the policy's own critic, so the guarantee only says the critic would not prefer a later action. The return bound that would link this to real return is never tested, and at deployment coverage falls below nominal (19/25 MinAtar runs at round zero; CartPole 84.1%) until recalibrated.

  3. The compute cost is only partly measured. Speed-ups are CPU-only on the six graph tasks (2.29-7.47x). There is no accelerator timing, no timing for MinAtar, and no cost for building the scored training and calibration data, which needs the policy run at all depths and every action scored, and could dominate when scoring needs rollouts.

Questions for authors
  1. The best gate's 5.29 steps comes from rows where Maze-7 falls back to maximum depth. What is the speed-up without Maze-7?

  2. Can the return bound (Eq. 5) be checked on any task, even a small one?

  3. In deployment, how many recalibration rounds and how much fresh data does the loop need before coverage reaches nominal?

  4. How does certifying remaining gain differ from [1] and [2]? One way to show it: run the same head and calibration with a target that compares only with the final step (close to the target in [1] and to certified-agreement early exit). This would show what comparing with every later step buys.

  5. How much does it cost to build the scored training and calibration data, compared with the inference savings? Can you report the speed-up on an accelerator?

  6. What does RARE2 stand for? Please define LTT and exchangeability in the main text.

  7. The training setup seems to be mixed: in 7 of 8 planning tasks the policy imitates exact optimal actions, while Cycle-FQI, MinAtar, and CartPole use RL. Why this choice? Does the 2.09x gain hold when the planning policies are trained with RL (as in Cycle-FQI) and scored by a learned critic instead of an exact oracle?

[1] S. Clarke and B. Stellato. Conformal Prediction for Early Stopping in Mixed Integer Optimization. ICML 2026.

[2] X. Wang el al. Conformal Thinking: Risk Control for Reasoning on a Compute Budget. ICML 2026.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.