acceptodds
Under review as a conference paper at ICLR 2027

Learning structured metacontrol

Abstract

Recent results in large language model reasoning underscore a well-known truth in classical planning machine learning: the ability to intelligently control how compute is allocated is paramount. For tree search, the mechanisms for making these decisions often rely on handcrafted rules, such as running a fixed amount of iterations of search before deciding on a move. This contrasts heavily with the evaluation component of search, which has benefitted enormously over the years from the adoption of learned, rather than predefined, evaluators. Here, we present a method where a controller learns to decide whether to act or keep planning (i.e., metacontrol) based on a learned embedding of the current planning tree. We evaluate our model's performance on chess play, showing that it is a strong meta-controller and beats existing baselines on efficient allocation of tree search iterations. We examine different ways of parametrizing our idea and show that a key component is the proper integration and propagation of estimator uncertainty in the evaluator. Finally, we interpret the learned halting mechanism itself.

Primary area:
reinforcement learning
Keywords:
Planning, chess, GNNs, metareasoning

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_M4a6OpenReview ↗
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
  1. 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?
  2. 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.
1 comment
AuthorsOpenReview ↗

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:

  • Stopping control with GRAMR does indeed remain worthwhile when the overhead is included.
  • End-to-end, a run of GRAMR takes about 4ms which is almost entirely tree encoding. A single iteration of search, in contrast, takes about 84ms.
  • We show that if the other baselines are given extra computation equal to the GRAMR inference time “for free” then this is actually still not enough to outperform GRAMR (rendered as black lines over the regret bars in Figure 3 to show the “compute-adjusted” regret).
  • Looking only at move quality separate from planning costs (i.e., focusing just on the lc0 evaluations of the chosen moves), we titrated the halting threshold on GRAMR to match the average move quality of all the baselines and measured how much compute this used. We found that GRAMR, when matching the move quality of the baselines, always actually uses less compute to do so (sometimes drastically so). We present this in the entirely new Figure 4.

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.

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

This paper introduces GRAMR, a learned controller for deciding when MCTS should stop tree search and act. They use a GNN to encode the search tree and an MLP to estimate the advantage of further search. The uncertainty-aware lookahead variant achieves the lowest regret, compared to heuristic and learned baselines on offline LCZero trees.

Critical strengths
  • Addresses an important problem - allocating search computation adaptively instead of using a fixed budget.
Critical weaknesses
  • The paper filters out around 85% of the examples, including the non-monotonic ABA cases. This could remove many difficult cases. It may be important to report performance on the full dataset.
  • LCZero provides both the input value estimates and the evaluation targets. So, the results mostly show that GRAMR can predict the behavior of deeper LCZero search. It would be useful to evaluate using actual game outcomes or a different chess engine.
  • Minor concern: The encoder comparison is not fully controlled. The distributional encoder is larger and has an additional count channel. A FLOPs/ parameter matched comparison is needed to support the claim that the improvement comes from uncertainty modeling.
  • The paper only evaluates regret on precomputed search trees. I would like to see end-to-end chess games, Elo or win-rate results and comparisons under same runtime budgets.
  • The paper could benefit from existing baselines.
Questions for authors

Please see weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Weaknesses 1, 2, 4

We thank the reviewer for their time and effort in reviewing our work. We are happy to report that we have addressed each of their listed weaknesses in whole.

Weakness 1: Performance on the full dataset.

We thank the reviewer for highlighting that our submission could benefit from showing performance on the full dataset. The severe filtering was initially done for training purposes: the lc0 network is quite strong, and in many cases its first preference (without search) is correct under a deeper search. There is little to learn from such examples. The ABA motif was filtered for labeling difficulty reasons. Nevertheless, we should have shown performance on the full dataset. We now do this in Figures 3 and 4 via parallel bars, and in Figure 5 via an extra panel, showing the regret separately on the filtered subset as well as the full dataset. We are happy to report that GRAMR remains optimal in all cases.

Weakness 2 + 4: Actual game outcomes.

We agree with the reviewer that showing actual game outcomes was a missing piece in our submission. To address this, 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.

AuthorsOpenReview ↗

Response to Weakness 3

Weakness 3: Parameter-matching.

We thank the reviewer for highlighting the incongruence between the encoder regimes. We divide their point into two separate sub-issues: compute matching (i.e., FLOPs) and parameter matching (i.e., encoder width).

Compute matching: 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. This is reflected in a change in Figure 3, where black lines on each bar now show the “compute-adjusted” regret. Furthermore, looking only at move quality separate from planning costs (i.e., focusing just on the lc0 evaluations of the chosen moves), we titrated the halting threshold on GRAMR to match the average move quality of all the baselines and measured how much compute this used. We found that GRAMR, when matching the move quality of the baselines, always actually uses less compute to do so (sometimes drastically so). This is the entirely new Figure 4.

Parameter matching: All encoder regimes were fit via a sweep of several architectural hyperparameters, including the encoding width. We initially found that the backup + point (B+P) encoder best performed with width 128 while the other encoders best performed with width 512 (in the previous version there was a typo stating that we used 128 for lookahead + point, but it is in fact 512). However, in investigating the reviewer’s feedback further, we found that the B+P learning rate was accidentally set to an old value during optimization; when this was fixed, the width 512 encoder was indeed optimal. We have now replaced all the B+P mentions in the paper with a width 512 B+P encoder and all GRAMR encoder widths are now aligned.

Separately, with respect to the count channel: To be clear, the distributional regime includes the count channel, it is not auxiliary information. In brief, in the metareasoning context, an agent ought to track not just its value estimate (be it a point estimate or a CDF, as in the distributional encoders) but also the uncertainty around that estimate. That is, they ought not to track only (a distribution over) the mean value estimate, but also to track the variance over that estimate. You can imagine that the CDF propagated by the GNN really should also come with a “third” dimension capturing how reliable that estimated CDF is (for example, it is quite different if the same CDF is from a single evaluation at a leaf node or from aggregating across tens of thousands of nodes in a subtree). We could have, in principle, computed that 3D object and propagated it directly, but we found that performing these computations is quite intractable and it was much easier to factorize it into a marginal (the CDF) and then an associated uncertainty metric (the count). Thus, the count channel is not separate auxiliary information but rather a key piece of the encoder representation and it was by design that the point encoders (which are not metareasoners) were excluded from it. Nevertheless, for completeness, we also tested adding a count channel to the point encoders. We found that it did indeed significantly improve the performance of the downstream controllers, but not enough to overtake the full distributional encoders (see Appendix).

AuthorsOpenReview ↗

Response to Weakness 5

Weakness 5: Existing baselines.

We appreciate the reviewer’s request for additional baselines from the literature. We first wish to note that many of our baselines are indeed based on the literature as well as actual practice in the real world:

  • Action gap is a frequently-used heuristic for the value of metareasoning (Kuperwajs & Ma, 2021)
  • KL stability is used by lc0 during training
  • Smart pruning is STOP-A (Baier & Winands, 2015), and used by lc0 during deployment
  • MLP on search statistics is (Lan et al. 2020)
  • VOI comes from Russell and Wefald (1991)

In practice, many of the methods from the LLM inference allocation literature (eg, policy-guided tree search), while ostensibly relevant, would be a poor fit for our particular context. The chess inference setting requires being able to account for the state of the clock, and explicit budget constraints generally do not feature in this literature.

Nevertheless, in scouring the literature, we found that we overlooked another potential baseline: the adaptive consistency rule by Aggarwal et al. (2023). We have now added this additional baseline to our submission.

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

The paper proposes GRAMR, a learned controller that decides whether to continue tree search or execute the currently preferred action. A graph neural network encodes the search tree using either point or distributional representations and either backup or lookahead objectives. The controller is trained using advantages computed by backward induction on preconstructed chess-search trees. Experiments measure regret relative to an oracle stopping policy and analyze the learned representations.

Critical strengths
  1. Learning stopping decisions from a structured representation of the search tree is well motivated. The separation between tree encoding and control makes the approach interpretable, while comparisons with both heuristic stopping rules and learned search-statistic baselines provide useful context.

  2. The representation ablations, ten-seed experiments, and controller interventions provide evidence about which information supports stopping decisions. In particular, the results motivate further investigation of prospective search representations and uncertainty-related features.

Critical weaknesses
  1. The evaluation establishes lower regret under an offline, evaluator-defined objective rather than demonstrated end-to-end computational savings. Rewards come from deeper searches with the same evaluator, planning is capped at 48 expansions, and the cost of repeatedly encoding the tree is not incorporated into a measured wall-clock comparison. Appendix B also filters the controller-training corpus to approximately 15% of the original trees, including removal of ABA preference reversals. Performance on the broader, unfiltered distribution needs clarification.

  2. The uncertainty comparison is confounded by representational capacity and auxiliary information. Appendix A uses 512-dimensional distributional embeddings versus 128-dimensional point embeddings, with an additional count channel and auxiliary losses for the distributional models. Consequently, the observed advantage cannot be attributed specifically to uncertainty encoding without stronger capacity- and feature-matched controls.

Questions for authors
  1. What is the net runtime–decision-quality trade-off after including GNN and controller inference, and how does the controller perform on unfiltered held-out positions, including ABA reversals?

  2. Does the distributional advantage remain when point and distributional models have matched embedding widths, comparable auxiliary objectives, and equivalent access to subtree-size information?

2 comments
AuthorsOpenReview ↗

Response to Weakness 1

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 have addressed in full.

Weakness 1: Metrics on runtime-decision-quality tradeoffs and performance on the full dataset.

We thank the reviewer for highlighting that our submission could benefit from examinations of a) how the inference time required for running GRAMR trades off against simply allowing the other baseline methods to run longer for an equivalent period of time, b) end-to-end performance comparisons in the form of win rates or net Elo in games played against the baselines, and c) how GRAMR performs on the full dataset, not just the subset we filtered for triviality. We address each of these separately below.

a) 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 still had much smaller regret both on the filtered trees and on the whole dataset. This has been reflected in Figure 3, where black bars now indicate the “compute-adjusted” regret. Furthermore, looking only at move quality separate from planning costs (i.e., focusing just on the lc0 evaluations of the chosen moves), we titrated the halting threshold on GRAMR to match the average move quality of all the baselines and measured how much compute this used. We found that GRAMR, when matching the move quality of the baselines, always actually uses less compute to do so (sometimes drastically so). We present this in the entirely new Figure 4.

b) 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.

c) Originally, we filtered the full dataset mostly for triviality reasons to do with training: the lc0 network is very good, and in most positions its preference with 0 search is also its preference after a deep search. We also removed the XABA motif, as discussed, due to labeling difficulty. Nevertheless, we should have reported final performance on this full dataset as well. These now appear as parallel bars in Figures 3 and 4, which plot regret both on the filtered subset and on the full dataset, and as a second panel in Figure 5. GRAMR remains optimal amongst the tested methods even in this case.

AuthorsOpenReview ↗

Response to Weakness 2

Weakness 2: Hyperparameter matching across encoder regimes.

We thank the reviewer for highlighting that the parameterizations of the distributional and point regimes differ in three ways: a) encoder width, b) count channel, c) auxiliary losses. We address each of these in turn below.

a) All encoder regimes were fit via a sweep of several architectural hyperparameters, including the encoding width. We initially found that the backup + point (B+P) encoder best performed with width 128 while the other encoders best performed with width 512 (in the previous version there was a typo stating that we used 128 for lookahead + point, but it is in fact 512). However, in investigating the reviewer’s feedback further, we found that the B+P learning rate was accidentally set to an old value during optimization; when this was fixed, the width 512 encoder was indeed optimal. We have now replaced all the B+P mentions in the paper with a width 512 B+P encoder and all GRAMR encoder widths are now aligned.

b) We thank the reviewer for highlighting the asymmetric access to the count channel, which we did not do a sufficient job motivating. To be clear, the distributional regime includes the count channel, it is not auxiliary information. In brief, in the metareasoning context, an agent ought to track not just its value estimate (be it a point estimate or a CDF, as in the distributional encoders) but also the uncertainty around that estimate. As a motivating example: the CDF could be generated by a single engine evaluation or by aggregating across thousands of leaves; we want some way to distinguish these cases. That is, an agent ought not to track only (a distribution over) the mean value estimate, but also to track the variance over that estimate. You can imagine that the CDF propagated by the GNN really should also come with a “third” dimension capturing how reliable that estimated CDF is. We could have, in principle, computed that 3D object and propagated it directly, but we found that performing these computations is quite intractable and it was much easier to factorize it into a marginal (the CDF) and then an associated uncertainty metric (the count). Thus, the count channel is not separate auxiliary information but rather a key piece of the encoder representation and it was by design that the point encoders (which are not metareasoners) were excluded from it. Nevertheless, for completeness, we also tested adding a count channel to the point encoders. We found that it did indeed significantly improve the performance of the downstream controllers, but not enough to overtake the full distributional encoders (see Appendix).

c) The auxiliary losses are distinct between the point and distributional encoder regimes due to the different needs of the encoders. In particular, the distributional encoders are primarily trained under a combination of Cramer loss, which roughly attempts to get the decoded and target CDFs to align but doesn’t necessarily care much about where individual mass goes, and cross-entropy loss which also encourages it to get specific atoms of the discretized distribution correct. It then has a separate auxiliary loss to ensure that the mean of the distribution is correct in particular (since it may lie in between atoms) and a loss for the count channel (which does not appear in the point encoders). In contrast, the point encoders can be thought of as “mean-only” estimators relative to the above. Thus they do not need the distributional loss (no distribution to fit), they don’t need the mean loss (they are only estimating the mean), and they don’t need the count loss (no count channel).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.