- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces , a certified stopping framework for adaptive-compute policies that iteratively refine candidate actions through recurrent computation. Specifically, 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 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?