acceptodds
Under review as a conference paper at ICLR 2027

Tree Search With Distributional Predictions

Abstract

Learning-augmented algorithms use machine-learned predictions to improve classical algorithmic guarantees when the predictions are accurate, while retaining rigorous performance guarantees when they are not. We study this paradigm for search on trees. Given a tree of pathwidth containing an unknown target vertex , an algorithm may query any vertex and learn which neighbor of lies on the unique path from to . The goal is to find using as few queries as possible. We consider the distributional setting, in which the target is drawn from an unknown distribution and the algorithm is given a predicted distribution of unknown quality. We give an algorithm with expected query complexity , where is the Shannon entropy of the true distribution and is the earth mover's distance between and in the tree metric. We also provide a matching lower bound that shows our algorithm is asymptotically tight. Finally, experiments on real-world and synthetic trees show that our prediction-based algorithm can use substantially fewer queries than a simple baseline that trusts the prediction completely.

Primary area:
learning theory
Keywords:
Predictions, Tree Search, Learning-Augmented Algorithms, Algorithms with Predictions

Reviews

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

The paper studies the distributional search problem on trees. In this problem, there is a hidden target vertex tt that is drawn from an unknown distribution pp. The task is to find the target vertex tt by executing a minimum number of queries. A query of an vertex vv reveals whether v=tv=t and, if not, it reveals the unique neighbour uu of vv which is on the path from vv to tt. In the setting with distributional predictions, the algorithm is given a predicated distribution p^\hat{p}. Goal is to obtain an improved query complexity when p^\hat{p} is "close" to pp (consistency) that smoothly degrades as p^\hat{p} and pp diverge, while still maintaining a worst-case guarantee. The settings where p=p^p = \hat{p} or where p^\hat{p} is a point distribution (a single vertex has predicted probability mass of one) have already been studied. This paper combines and generalises these results to obtain an algorithm with a query complexity of O(H(p)=klog⁡η)O(H(p) = k \log \eta) where H(p)H(p) is the entropy of pp, η\eta is the earth mover distance between pp and p^\hat{p}, and kk is the path width of the tree. The authors complement this result with an asymptotically tight lower bound, which is an implication of a classical lower bound by Mehlhorn, 1975 and by the lower bound for point predictions by Dinitz and Dong, 2026. The main result is the algorithmic upper bound. It combines the algorithm by Dinitz and Dong for point predictions with the approach by Berendsohn et al, 2023 for a known distribution. The main technical contribution is a compression technique which reduces the number of relevant boundary vertices to a constant, which then allows running the point prediction algorithm on these boundary vertices.

Critical strengths
  • A main strength of this paper is the model: distributional predictions are very well motivated by most ML methods. Yet, most papers on learning-augmented algorithms only study non-distributional predictions. This paper did not come up with the model, but extending the study of distributional predictions to more problems is a good contribution.
  • The paper obtains asymptotically tight bounds to a problem, which generalises existing results on binary search with distributional predictions and on tree search with point predictions.
Critical weaknesses
  • The technical contribution seems somewhat limited, as the paper is a combination of known ideas. The combination takes some technical work, but I'm not sure if there are any novel technical ideas.
Questions for authors
  • What would you say is the main new technical idea of your algorithm?
2 comments

We thank the reviewer for their thoughtful review and for recognizing the motivation of distributional predictions and the tightness of our bounds. We agree that our algorithm builds on the interlacing framework and the existing point-prediction algorithm. Our main technical contribution is the boundary-compression technique.

The obstacle is that, on a path, the remaining feasible region has at most two boundary vertices, whereas on a tree it can have many. Directly running point-prediction search from every boundary vertex would therefore introduce an overhead that our bound cannot afford. Our compression procedure uses O(log⁡∣A∣)O(\log |A|) queries to either find the target or reduce a boundary set AA to at most two candidate anchors. Crucially, at least one resulting anchor is no farther from the target than the closest original boundary vertex.

We also explored other approaches, including applying distributional binary search along the spine or complicatedly interlacing weighted-median search with distributional binary search. In our attempts, these approaches introduced additional losses in either the EMD or the entropy term, and we were unable to obtain the same tight bound. These difficulties motivated the boundary-compression technique, which allows us to achieve the stated dependence on both quantities.

Thank you to the authors for the response and clarifications. I will maintain my overall positive score.

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

The paper studies tree search with distributional predictions, where the target is drawn from an unknown distribution pp and the algorithm receives a predicted distribution p^\widehat{p}. It claims an expected query complexity of O(H(p)+klog⁡η)O(H(p)+k\log\eta), where kk is the tree's pathwidth and η=W1(p,p^)\eta=W_1(p,\widehat{p}). The algorithm alternates weighted-centroid queries with a point-prediction search procedure. Its main technical ingredient is a boundary-compression procedure that reduces the boundary of the feasible subtree to at most two vertices without increasing the distance from the target to the nearest boundary vertex. The paper also establishes lower bounds showing that the entropy and prediction-error terms are independently necessary. This extends prior results for distributional predictions on paths and point predictions on trees.

Critical strengths
  • The paper studies a natural extension of prior work by allowing distributional predictions for tree search. Earlier results considered either distributional predictions on paths or a single predicted vertex on trees. The present setting allows the algorithm to use a prediction that expresses uncertainty over several possible target locations while accommodating a branching search space.

  • The claimed expected query bound of O(H(p)+klog⁡η)O(H(p)+k\log\eta) separates the uncertainty in the true target distribution from the cost of prediction error. The pathwidth factor kk appears only in the error term, while the entropy contribution remains O(H(p))O(H(p)). Consequently, for trees of constant pathwidth, the bound matches the asymptotic guarantee previously obtained for paths. This is a useful feature of the generalisation, as the additional structural complexity does not multiply the entire query bound.

Critical weaknesses
  • The contribution builds closely on the two preceding works. The distributional prediction model and the entropy-plus-error form of the guarantee were already established for paths, while the recovery procedure and its pathwidth dependence come from the earlier tree-search result. The main additional ingredient is boundary compression, and the lower bound largely transfers an existing construction. Although this gives a natural extension, the extent of the new technical contribution appears limited.

  • The experiments provide limited evidence of practical benefit beyond the controlled setting studied. The target and predicted distributions are generated synthetically, and prediction error is introduced by replacing their support vertices. Although two trees are derived from road networks, the evaluation does not establish an application with realistic predictions and direction queries. It also omits ordinary centroid search as a standalone baseline, leaving unclear when the proposed method improves over simply ignoring the prediction.

Questions for authors
  1. I would appreciate clarification on the recovery guarantee used in Lemma 6.3. In the cited procedure, resetting the starting vertex to the entrance of the selected component can move it farther from the target when the previous guess already lies in that component. Does the implementation used here retain the previous guess in this situation, or is there another argument that establishes the required bound?

  2. How does the proposed algorithm compare with ordinary centroid search that ignores the prediction? This comparison would help assess the practical benefit of the method, particularly given its additional query cost when predictions are accurate.

2 comments

We thank the reviewer for their thoughtful review and for recognizing the motivation for distributional predictions and our asymptotically tight generalization from paths to trees.

We address the reviewer’s questions below.

I would appreciate clarification on the recovery guarantee used in Lemma 6.3. In the cited procedure, resetting the starting vertex to the entrance of the selected component can move it farther from the target when the previous guess already lies in that component. Does the implementation used here retain the previous guess in this situation, or is there another argument that establishes the required bound?

Yes, the implementation we use here first checks whether the previous starting vertex lies in the selected component. If it does, we retain it; otherwise, we reset to the entrance vertex. In the latter case, the entrance lies on the unique path from the previous starting vertex to the target, so this update never increases the distance to the target. This preserves the distance invariant needed for the recovery guarantee in Lemma 6.3. We thank the reviewer for pointing out this ambiguity and will clarify the update rule in the paper.

How does the proposed algorithm compare with ordinary centroid search that ignores the prediction? This comparison would help assess the practical benefit of the method, particularly given its additional query cost when predictions are accurate.

We refer the reviewer to our response to Reviewer xL2d and Reviwer unZS, where we present the additional experimental results.

Thank you for getting back to me. The explanation resolves my question about the recovery procedure, and the new experiments help clarify when the algorithm is useful. I will keep my rating at 3, as these additions support the result but do not change my overall assessment of the contribution.

Reviewer_unZSOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the problem of searching a tree using a directional oracle, but additionally assumes availability of a predicted distribution that captures the probability of the target being at each node. For distributional predictions, if the prediction reflects the true distribution of target locations, it is known that weighted-centroid search gives at most twice the optimal expected query cost (Berendsohn et al., 2023). In this paper, the authors consider settings where the predicted distribution may differ from the true distribution and present a robust algorithm whose performance is bounded in terms of how far the two distributions are.

In particular, for a tree of pathwidth kk, the paper gives an expected query bound of O(H(p)+klog⁡η)O(H(p)+k\log\eta), where H(p)H(p) is the entropy of the unknown true distribution pp, and η\eta is the EMD between the true and predicted distributions. They also give matching worst-case lower bounds showing that both terms are necessary.

The high-level idea of their algorithm is roughly as follows. They first use the standard weighted-centroid approach (Berendsohn et al., 2023) recursively to obtain a smaller subtree. The first important observation is that the target’s distance from the boundary of the resulting subtree can be related to the EMD between the true and predicted distributions. More specifically, once the subtree has sufficiently little predicted mass, if the EMD is small relative to the target’s probability, then the target should be close to a boundary vertex. This motivates searching near the boundary vertices, but there could be too many. The authors bypass this by using weighted-centroid queries to shrink this set while leaving at least one candidate no farther from the target than the nearest original boundary vertex. The algorithm then runs “recovery searches” from these candidates using an earlier algorithm of Dinitz and Dong (2026) for point-predictions. This exploits the pathwidth of the tree to find the target efficiently from a nearby candidate.

Critical strengths
  1. The paper is technically strong. The observations connecting the target’s distance from the boundary with the EMD between the true and predicted distributions are nice, and the idea of using weighted centroids to compress the boundary, while simple, is elegant.

  2. The problem is generally interesting, and the upper bounds combined with the lower bounds provide a tight worst-case characterization.

Critical weaknesses

None

Questions for authors

The real-world examples of low-pathwidth trees given have pathwidth relatively close to log⁡n\log n. Are there more convincing real-world examples where the pathwidth is substantially smaller than log⁡n\log n and the benefit over standard search is clearer?

1 comment

We thank the reviewer for their positive assessment of our technical contributions and tight worst-case characterization. We particularly appreciate their recognition of the connection between boundary distance and EMD, and of the weighted-centroid boundary compression technique.

To address the reviewer’s question, we have conducted an additional experiments on the molecular-dynamics structure of polyethylene, which is a pathwidth 1 tree.

On this graph, we let predictions to concentrate on a short backbone segment. The predicted distribution is uniform on 10 consecutive spine vertices and their attached hydrogen leaves; the true distribution is uniform on an equally sized segment shifted by dd spine edges. We average over ten random placements, evaluating every target in the true support.

The table below shows average query counts.

Shift ddUnweighted centroidWeighted on trueWeighted on predictedOurs
010.522.902.903.20
210.532.905.233.60
410.532.907.425.39
610.492.909.879.01
1010.682.9014.3815.21
10010.562.9014.2618.74

These results demonstrate clear benefits from spatially accurate predictions. For relatively accuarate predictions (d=2,4,6d=2,4,6), our algorithm significantly outperforms both unweighted centroid search and centroid search weighted by the predicted distribution. This is consistent with our claim that informative predictions can reduce query complexity.

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

This paper studies algorithms with predictions, a computational framework that has emerged over the past decade and is motivated by the use of (machine-learned) predictions in algorithm design. In this setting, we receive (along with the input) a prediction capturing useful information about the answer; the goal is to design an algorithm whose performance depends smoothly on the error of the prediction and does not degrade past the guarantees of a worst-case algorithm.

Perhaps the simplest application of this framework is for binary search, where given a predicted index at most η\eta from the target, one can find the target in O(log⁡η)O(\log\eta) queries. Dinitz & Dong (2026) study a natural generalization of binary search to trees. Here, the task is to locate a target vertex tt within a tree using neighbor queries, which, given a vertex vv, return the unique neighbor of vv along the path from vv to tt.

There are two primary types of predictions studied in this line of work. The first is point predictions, which take the form of a predicted vertex ss; Dinitz & Dong (2026) give an O(klog⁡dist(s,t))O(k\log\mathrm{dist}(s,t)) query algorithm for trees of pathwidth ≤k\le k. A more general notion is distributional predictions, previously studied for binary search by Dinitz et al. (2024). Here, the target is drawn from an unknown distribution pp over the vertices, and the prediction is an approximate distribution p^\hat{p}. The main contribution of this paper is the design of an algorithm for tree search achieving optimal expected query complexity in the distributional prediction setting.

Main Results

This paper gives matching upper and lower bounds for tree search with distributional predictions. Upper bound: an algorithm that finds the target using O(min⁡{log⁡n,H(p)+klog⁡η)}O(\min\{\log n, H(p) + k\log\eta)\} expected queries, where H(p)H(p) is the entropy of pp, kk is an upper bound on the tree’s pathwidth, and η\eta is the earth mover’s distance between pp and p^\hat{p}. Lower bound: a proof that for any algorithm, there is an instance requiring Ω(H(p)+klog⁡η)\Omega(H(p)+k\log\eta) expected queries.

There is also a brief experimental section showing that on real-world trees, the algorithm achieves better performance than a non-robust algorithm that fully trusts the prediction.

Techniques

At a high level, the algorithm combines two ideas from past papers: The first is the weighted centroid algorithm, which repeatedly queries a vertex whose removal leaves components, each with at most 1/21/2 the total weight (with respect to p^\hat{p}). Berendsohn et al. (2023) showed that when p^=p\hat{p} = p, this approach yields a 22-approximation to the optimal expected query complexity. The second is the point-prediction algorithm of Dinitz & Dong (2026), which gives asymptotically optimal query complexity when the prediction is a single vertex, p^=δs\hat{p}=\delta_s. The algorithm alternates between these two procedures over geometrically increasing query budgets. Weighted-centroid queries reduce the predicted mass of the current feasible subtree (the one containing tt), while point-predictions applied to the “boundary vertices” of this subtree recovers performance when the prediction is inaccurate. A core nuance is that in trees, a subtree can have many boundary vertices; so, the authors devise a boundary compression algorithm that makes additional queries to “anchor” a subtree to at most two boundary points.

The lower bound (in my reading) is more immediate, following from the existing lower bound for the point prediction setting of Dinitz & Dong (2026) and the Ω(H(p))\Omega(H(p)) lower bound for distributional binary search from Mehlhorn (1975).

Critical strengths

The paper is very well-written, introducing the key ideas and techniques clearly and motivating the tree search problem and distributional prediction model from prior work. The algorithm is simple and achieves optimal guarantees. The core technical idea of boundary compression clarifies the key nuance when extending from paths to trees.

Critical weaknesses

While the focus of the paper is on query complexity, it would be good to have a concrete discussion of runtime. The final paragraph of Section 2 (“Robustness and Running Time”) mentions that weighted-centroid search and boundary compression both run in polynomial time, but no justification or concrete bounds are given. In the experimental section, a very natural baseline is absent: a prediction-independent algorithm.

Questions for authors

None.

1 comment

We sincerely thank the reviewer for their positive review and very constructive feedback. We appreciate their recognition of our writing style, the simplicity of our algorithm, and our boundary compression technique.

We address the reviewer’s concerns below.

While the focus of the paper is on query complexity, it would be good to have a concrete discussion of runtime. The final paragraph of Section 2 (“Robustness and Running Time”) mentions that weighted-centroid search and boundary compression both run in polynomial time, but no justification or concrete bounds are given.

We certainly agree that a more concrete discussion of runtime would strengthen the presentation. More specifically, each iteration of weighted-centroid search takes O(n)O(n) time to compute the subtree weights and identify a weighted centroid. With O(log⁡n)O(\log n) iterations (by the weighted centroid property), the total running time is therefore O(nlog⁡n)O(n \log n). Similarly, since our boundary compression technique is built directly on weighted-centroid search, it has the same O(nlog⁡n)O(n\log n) running time.

In the experimental section, a very natural baseline is absent: a prediction-independent algorithm.

We thank the reviewer for this helpful suggestion. We have added unweighted centroid search, to our experiments on trees derived from the Luxembourg and US road networks.

TreeSupport mmSupport replacedUnweighted centroidWeighted on trueWeighted on predictedOurs
Luxembourg160%12.044.064.065.23
Luxembourg1650%12.044.069.9010.64
Luxembourg16100%12.044.0616.0416.16
Luxembourg2560%12.156.726.728.06
Luxembourg25650%12.156.7212.7711.77
Luxembourg256100%12.156.7218.9215.53
Luxembourg4,0960%12.029.309.3011.87
Luxembourg4,09650%12.029.3015.3813.55
Luxembourg4,096100%12.029.3021.2415.33
US160%11.313.893.895.38
US1650%11.313.899.6310.48
US16100%11.313.8915.2115.59
US2560%11.306.586.588.54
US25650%11.306.5812.1912.15
US256100%11.306.5817.8615.83
US4,0960%11.439.239.2312.40
US4,09650%11.439.2314.8113.72
US4,096100%11.439.2320.5415.27

These results demonstrate substantial reductions in query complexity over unweighted centroid search when predictions are accurate and the support is small or moderate. For m=256m=256 and 4,0964{,}096, our algorithm also improves over weighted-centroid search on the predicted distribution under complete support replacement, illustrating the benefit of recovery. Intuitively, a prediction spread roughly evenly over a large support has high entropy and is less informative about the target’s location. This helps explain the smaller gains for larger supports and is consistent with the entropy dependence in our theoretical guarantee. Moreover, unweighted centroid search has a query bound of O(log⁡n)O(\log n), whereas our prediction-dependent bound is controlled by entropy, prediction error, and pathwidth. This suggests the potential for greater advantages on larger trees when these quantities remain small.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.