- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes \textbf{Hierarchical Distance Decomposition (HDD)}, a training-free post-hoc method that improves long-horizon distance estimates from an already learned quasimetric distance model. The key idea is to decompose long-range distance queries into compositions of short-range predictions. The method first builds a landmark set from an offline state-only trajectory dataset using a greedy two-sided -net, where a state is retired only if an existing landmark is close to it in both forward and backward directions. It then constructs a directed landmark graph retaining only edges whose predicted distance is at most , computes all-pairs shortest paths via Floyd--Warshall, and at query time combines an entry leg, a landmark shortest path, and an exit leg. The estimator returns the base model's direct prediction when the closest forward and backward landmarks coincide, and otherwise minimizes over candidate landmark routes.
The paper provides a theoretical analysis under two assumptions: local accuracy of the base model and coverage of relevant reference paths by the dataset. Theorem~1 gives a two-sided bound: no underestimation beyond accumulated local error along the returned route, and bounded overestimation with a per-hop cost depending on $\delta$ and $\epsilon$. The paper also discusses why the two-sided landmark rule is necessary, gives a counterexample for one-sided nets, and extends the discussion to stochastic options.
Empirically, HDD is evaluated on PointMaze and AntMaze from OGBench, across medium, large, and giant sizes, with navigate and stitch splits, and additionally explore for AntMaze Medium. Three base distance models are used: MadDist, TDMAD, and HILBERT. HDD improves Spearman rank correlation with grid-geodesic distance as the evaluated range increases, and substantially improves downstream planning success rates, especially on giant mazes where flat base models often fail completely. Ablations over $\delta$ and $\kappa$ show that smaller $\delta$ and smaller $\kappa$ generally work best, with $\kappa$ having a stronger effect.
Critical strengths
1: Simple, training-free, and broadly applicable method. The proposed HDD is conceptually simple and easy to implement. It does not require retraining the base distance model or learning a new representation. It can be applied post-hoc to any locally accurate quasimetric distance model. This is consequential because it makes the method practical and easy to adopt. The empirical results show that it can turn near-zero planning success on giant mazes into high success rates, which is a substantial practical improvement.
2: Strong empirical gains on long-horizon tasks. The paper demonstrates consistent improvements in both distance-quality correlation and planning success rate across multiple environments, datasets, and base models. The gains are largest precisely where base models fail: on giant mazes and long-horizon tasks. This is consequential because it directly addresses the motivating problem of long-range distance degradation. The ablation over and also provides useful practical guidance.
3: Theoretical analysis with clear assumptions and two-sided bound. The paper provides a formal analysis of the estimator's error, including a no-underestimation bound and a bounded-overestimation bound. The two-sided landmark construction is well motivated and the counterexample for one-sided nets is convincing. This is consequential because it gives the method a principled foundation and clarifies when it can be expected to work.
Critical weaknesses
1: Strong dependence on local accuracy of the base model, with limited practical guidance. The method's theoretical guarantees and empirical success depend on the base model being locally accurate. However, the paper does not provide a practical procedure to check whether this assumption holds for a given base model and dataset. In practice, if the base model is locally inaccurate, HDD may compose unreliable local estimates and produce poor long-range estimates. The paper acknowledges this as a limitation, but it is central to the method's applicability. A practical diagnostic or fallback mechanism would strengthen the paper.
2: Limited isolation of the source of planning gains. The planning results show large improvements, but the planner is deliberately weak and the hierarchical decomposition may act as a form of test-time search or subgoal selection. The paper does not fully disentangle whether the gains come from better distance estimates or from the hierarchical structure itself. This matters because the claimed contribution is a distance-estimation method, not a planner. Additional analysis, such as comparing against a planner that uses the same landmark graph but a different distance model, or measuring the correlation between distance error and planning success, would help.
3: Theoretical assumptions and constants are conservative and not empirically validated. The theoretical bound depends on assumptions that are difficult to verify in practice, and the constants are worst-case. The paper does not empirically validate the assumptions or the tightness of the bound. This limits the practical utility of the theory. It would be useful to report, for example, the empirical local error of each base model and the coverage of reference paths by the dataset.
Questions for authors
-
Practical verification of local accuracy: Can you provide a practical procedure to estimate whether a given base model satisfies Assumption~1 on a given dataset? For example, could one use held-out local pairs to estimate ? How would you recommend practitioners decide whether HDD is applicable?
-
Disentangling planning gains: The planning improvements are large. Can you provide an ablation that isolates whether the gains come from improved distance estimates or from the hierarchical graph acting as a test-time search mechanism? For example, what happens if the planner uses the same landmark graph but with a random or constant distance model?
-
Empirical validation of assumptions: Can you report empirical estimates of the local error for each base model, and the coverage of reference paths by the dataset? This would help assess how often Assumptions
1 and2 hold in practice. -
Sensitivity to and : The ablation shows that smaller and smaller are better, but smaller increases the number of landmarks and preprocessing cost. Can you provide a more detailed cost-benefit analysis, including preprocessing time and memory, for the recommended settings?
-
Stochastic environments: The paper discusses options-style abstraction for stochastic control but does not evaluate it. Can you provide at least a preliminary experiment on a stochastic navigation task to show whether the deterministic shortest-path approximation remains reasonable?
-
Comparison to alternative post-hoc methods: The paper compares HDD to flat base models. Are there other post-hoc distance-improvement methods, such as graph-based smoothing or local averaging, that could serve as stronger baselines? How does HDD compare to these?
-
Failure cases: Can you provide examples where HDD fails or degrades performance? Understanding the failure modes would help assess the method's robustness.
Practical verification of local accuracy: Can you provide a practical procedure to estimate whether a given base model satisfies Assumption~1 on a given dataset? For example, could one use held-out local pairs to estimate ? How would you recommend practitioners decide whether HDD is applicable?
Without access to the ground truth, it is challenging to design a reliable procedure to estimate whether Assumption~1 is respected. In case one has access to the ground truth only on a small subset of the state space, practitioners could use held-out local pairs from this subset to empirically assess whether Assumption 1 is satisfied. In more realistic scenarios where such ground-truth information is unavailable, practitioners would need to assess the applicability of Hierarchical Distance Decomposition (HDD) empirically, as is common with many other algorithms, by evaluating whether it improves performance on downstream task benchmarks, such as goal-conditioned planning.
Disentangling planning gains: The planning improvements are large. Can you provide an ablation that isolates whether the gains come from improved distance estimates or from the hierarchical graph acting as a test-time search mechanism? For example, what happens if the planner uses the same landmark graph but with a random or constant distance model?
We would like to clarify that our method does not require any additional distance computations during test-time search. The distances between landmarks are computed when building the landmark graph and stored in the matrix DH, which is then used at inference time. We also believe that the proposed experiment would provide limited additional insight, since the landmark graph is closely tied to the base distance model used to construct it. In particular, the graph is built using the (δ)-net rule, where an edge between two landmark centroids is added only if their estimated distance is below (δκ). As a result, the graph already implicitly captures information from the base distance model, and replacing it with a random or constant distance model would not reproduce the same graph structure or distance information.
Sensitivity to κ and δ: The ablation shows that smaller δ and κ smaller are better, but smaller increases the number of landmarks and preprocessing cost. Can you provide a more detailed cost-benefit analysis, including preprocessing time and memory, for the recommended settings?
In the revised version of the paper, we added Section 4.3, Computational Cost, where we provide a more detailed analysis of construction and querying time. We also want to highlight that most of the additional computational cost of our method comes during construction rather than at inference time. As discussed in the new section, we make several design choices to keep these costs manageable while still benefiting from smaller values of δ and κ.
Comparison to alternative post-hoc methods: The paper compares HDD to flat base models. Are there other post-hoc distance-improvement methods, such as graph-based smoothing or local averaging, that could serve as stronger baselines? How does HDD compare to these?
To the best of our knowledge, there are currently no established post-hoc methods that directly address the problem we consider in our paper: improving the long-range estimates of an existing learned distance model without requiring further training. We discuss the most closely related prior work in the Related Work section. For example, Plan2Vec (Yang et al., 2020) uses graph-derived distance estimates to train a new representation, while Bagatella and Martius (2023) use graph-based aggregation to improve goal-conditioned value estimates for planning. Although these approaches share some methodological similarities with ours, they address different problems and are not directly comparable as general-purpose distance estimation methods.
Regarding the suggested alternatives of graph-based smoothing and local averaging, we are not aware of established methods that apply these techniques to improve learned temporal distance estimates. We would welcome references to any specific methods the reviewer has seen that use these ideas, particularly if they would help identify appropriate additional baselines. However, without a concrete existing method to compare against, such experiments would require developing and validating new algorithms from scratch rather than evaluating established and well-understood alternatives to our approach.