- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
This paper studies when an agent should stop tree search and execute an action. The proposed method, GRAMR, uses a graph neural network to encode the current search tree and combines this representation with the remaining budget to predict the advantage of continued planning over immediate action. The authors compare four combinations of backup/lookahead encoding and point-estimate/distributional representations, and train the controller using precomputed deep search trees and backward induction.
In experiments on chess positions, GRAMR achieves lower mean regret than the evaluated baselines, with the lookahead distributional variant performing best. The authors further investigate the information used by the controller through probing, ablation, and budget perturbation experiments.
Critical strengths
- The method is straightforward and offers a potentially useful alternative to handcrafted stopping rules.The controller learns to predict the advantage of continued planning and uses the budget input to adapt to different resource constraints. Its inference-time decision criterion is simple and does not introduce a complicated collection of manually designed stopping thresholds. This makes it a natural approach to learned stopping.
- The method achieves reasonably consistent improvements within the evaluated setting.The authors compare several stopping baselines and four encoder configurations, and report results across multiple random seeds. These experiments support the usefulness of learned search-tree representations for stopping decisions in the setting considered. The comparisons involving uncertainty and lookahead encoding also provide useful empirical findings.
Critical weaknesses
-
The practical computational benefit of the additional control mechanism has not been sufficiently established. The main value of this work should lie in more effective use of computational resources, but making stopping decisions also consumes computation. The current experiments primarily compare mean regret under a specified cost function and do not sufficiently establish performance under matched total computational budgets that include all control overhead. The central question is whether allocating the computation used to decide whether to continue searching directly to additional search would yield comparable or better results. The paper includes fixed-search and budget-dependent search baselines, but these do not replace a comparison that accounts for all overhead.
-
The experiments cover only a single real-world decision, leaving the value for long-term budget allocation unclear. Training and evaluation operate on individual chess positions, each assigned an initial budget, with an episode ending once a move is selected. This does not explicitly account for how computation spent on the current decision affects subsequent real decisions. In sequential decision-making under a shared total budget, additional search may improve the current choice while consuming resources needed for later critical positions. The paper represents computational cost through a function of the remaining budget, without explicitly accounting for this opportunity cost across decisions. Consequently, evidence is still lacking that lower regret in local stopping decisions translates into better long-term task performance. This is a limitation concerning scope and practical significance, rather than a rejection of the method’s effectiveness for local stopping.
Questions for authors
- Does stopping control remain worthwhile when all overhead is included? Could the authors report the actual costs of search, tree encoding, and controller inference, together with curves showing move quality versus total runtime or computational cost? In particular, under the same total computational budget, does GRAMR outperform baselines that allocate the resources saved by omitting control overhead to additional search? How much total computation does each method require to achieve comparable move quality?
- Can the method effectively handle budgets shared across multiple decisions? Could the authors provide an experiment involving sequential decisions under a shared total budget, where the remaining budget is carried into the next decision after an action is executed? If the contribution is restricted to single-position stopping control, please clarify this boundary and narrow the interpretation of its implications for long-term resource allocation.
Response to Weaknesses 1 and 2
We thank the reviewer for their time and effort in reviewing our work. We are gladdened that they found our presentation clear and easy to follow, and learned something useful from it. We also appreciate their constructive feedback on the weaknesses of the submission, which we are happy to say we can address in full.
Weakness 1: Full compute accounting.
We thank the reviewer for highlighting that our submission could benefit from a full accounting of the involved compute. In practice, since the networks involved in the GNN encoder and the MLP controller are fairly small, GRAMR’s inference time is only ~5% of a single iteration of MCTS in wall-clock time, and about ~10% in multiply-add operations. As such, we expect the effect of the saved compute to be minimal. To test this, we took the total decision time of GRAMR (i.e., inference time) on the test-trees, converted it to expansions, and then gave that number of expansions “for free” (meaning, not incurring a planning cost) to all the other baseline methods. We found that even when this is done, GRAMR had much smaller regret both on the non-trivial subset and on the whole dataset. We have rendered this in Figure 3 by adding black lines to the regret bars indicating the “compute-adjusted” regret.
Thus, in response to the reviewer’s direct questions, we can say that:
Weakness 2: Time savings across multiple steps.
We agree with the reviewer’s point that the submission’s results focus only on optimizing for a single decision and do not show savings across multiple iterated decisions (i.e., as in a chess game). To be clear, our parameterization of the cost of planning as an explicit cost was designed as a heuristic stand-in for the opportunity cost of thinking; in future work, it is our goal to remove this explicit cost term and instead teach GRAMR to estimate the advantage of planning over acting actual game-play, as the reviewer points out.
Nevertheless, we set out to see how well GRAMR would perform in actual games. We found that even though GRAMR is not actually optimized for game-play per se, it actually performed well in this context. To show end-to-end performance gains, we conducted chess matches featuring the lc0 network controlled by GRAMR against its top three competitors by the regret metric: halting immediately, using an MLP to predict stopping from search statistics, and fitting a separate bespoke expansion count per bucket of available budgets. In these matches, both players started with a budget of 500 expansions that they could spend as they liked. Games were played with an increment of 1, meaning after every made move, the players received +1 to their budget. Each pair of opponents played 600 games against each other in the style of typical engine matches (meaning that 300 positions are fixed and each position is played twice, alternating colours). GRAMR outperformed all three competitors in these matches, netting +17 Elo against halting immediately, +5 Elo against the MLP, and +5 Elo against the fixed per bucket opponent.