Pith. sign in

REVIEW 2 minor 55 references

Reachability in directed trees can be represented by embeddings in just three dimensions.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Proves constant-dimension 3 reachability embeddings for directed trees, O(t log n) for treewidth-t graphs, with lower bounds of Omega(n) for general DAGs and Omega(t/log(n/t)) for treewidth t, plus real-dataset results.

T0 review reviewed 2026-06-26 challenge →

load-bearing objection Constant dimension 3 for any directed tree is the real advance, with the treewidth parameterization as a useful follow-on.

arxiv 2606.18520 v1 pith:OID3SMJP submitted 2026-06-16 stat.ML cs.CGcs.CLcs.DScs.IRcs.LG

Compact Geometric Representations of Hierarchies

Prashant Gokhale , Piotr Indyk , Yuhao Liu , Sandeep Silwal , Tony Chang Wang , Haike Xu This is my paper
classification stat.ML cs.CGcs.CLcs.DScs.IRcs.LG
keywords reachability embeddingsdirected treestreewidthhierarchiesDAGsgeometric representationsembedding dimension
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that any directed tree admits a geometric embedding of constant dimension 3 in which ancestor-descendant reachability is preserved exactly. This bound is independent of tree size or depth and improves on earlier constructions whose dimension grew with the number of nodes in deep hierarchies. The result extends to graphs of treewidth t with embeddings of dimension O(t log n), accompanied by nearly matching lower bounds. The constructions are shown to produce smaller dimensions than prior guaranteed methods when applied to real datasets at high recall. These guarantees matter because they allow hierarchical retrieval systems to use fixed low-dimensional vectors while retaining exact theoretical correctness for tree-structured data.

Core claim

For any directed tree there exists a reachability embedding in dimension 3. For graphs of treewidth t the paper constructs embeddings of dimension O(t log n). Matching or near-matching lower bounds are given: dimension Omega(n) is necessary for arbitrary DAGs and Omega(t / log(n/t)) for treewidth-t graphs. Additional bounds are obtained in terms of the number of cross-edges. The embeddings are realized on real-world data and yield smaller dimensions than previous theoretical embeddings in high-recall regimes.

What carries the argument

Reachability embedding: a mapping from nodes of a DAG to points in Euclidean space such that one node reaches another precisely when the corresponding points satisfy the geometric condition that encodes the ancestor-descendant partial order.

Load-bearing premise

The ancestor-descendant ordering of the input DAG can be captured exactly by some geometric relation on points in low-dimensional space without requiring extra metric or inner-product constraints.

What would settle it

Exhibit one directed tree together with an explicit enumeration of its reachability pairs such that no assignment of 3-dimensional coordinates makes the geometric condition hold exactly for those pairs and fail for the others.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Hierarchical retrieval on tree data can use fixed three-dimensional vectors instead of vectors whose length scales with depth or node count.
  • Graphs of bounded treewidth admit embeddings whose dimension grows only logarithmically with n once the treewidth parameter is fixed.
  • Lower bounds show that dimension linear in n is unavoidable for arbitrary DAGs, so the tree and treewidth restrictions are essential.
  • Embeddings parameterized by cross-edge count give further dimension reductions when the DAG is close to a tree.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The constant-dimension result for trees suggests that practical hierarchy-aware models could keep embedding size fixed while scaling to arbitrarily large trees.
  • The treewidth parameterization may extend to other sparse graph families that admit low-treewidth decompositions, such as series-parallel graphs.
  • Efficient construction algorithms for the embeddings would turn the existence proofs into practical preprocessing routines for retrieval systems.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The paper claims that any directed tree admits a reachability embedding in constant dimension 3 independent of size or depth; that graphs of treewidth t admit embeddings of dimension O(t log n); that these are complemented by lower bounds of Omega(n) for general DAGs and Omega(t / log(n/t)) for treewidth-t graphs; that additional upper/lower bounds exist parameterized by the number of cross-edges; and that the embeddings can be constructed on real-world datasets and yield smaller dimensions than prior work in high-recall regimes.

Significance. If the existence proofs and constructions hold, the results would be significant for geometric representations in hierarchical retrieval. The constant-dimension result for arbitrary trees (independent of depth or n) and the treewidth parameterization provide dimension bounds that depend only on structural parameters rather than instance size, improving on prior work whose bounds degrade with depth. The matching or near-matching lower bounds and the empirical demonstration on real data are additional strengths; the parameter-free character of the tree result is noteworthy.

minor comments (2)
  1. [Abstract] Abstract: the citation 'You et al. [NeurIPS '25]' should include a full bibliographic entry or arXiv identifier for completeness.
  2. [Section on treewidth embeddings] The manuscript should clarify in the main text (e.g., near the treewidth construction) whether the O(t log n) bound is achieved by an explicit polynomial-time algorithm or only by an existence argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment, the recognition of the constant-dimension result for trees, the treewidth parameterization, the lower bounds, and the empirical results. The recommendation for minor revision is appreciated. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; existence proofs are self-contained against external graph parameters

full rationale

The paper presents theoretical existence results and matching lower bounds for reachability embeddings of trees (constant dimension 3) and treewidth-t graphs (O(t log n) dimension). These are stated as constructions and proofs parameterized by standard graph invariants (treewidth, n, cross-edges) with no fitted parameters, no self-referential definitions of the embedding predicate, and no load-bearing self-citations that reduce the claimed bounds to prior unverified results by the same authors. The abstract and stated claims contain no equations or reductions that equate the output dimension to an input fit or ansatz smuggled via citation; the derivation chain is therefore independent of the target quantities.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard definition of reachability embeddings and the graph-theoretic notion of treewidth; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Reachability in a DAG can be represented by a geometric embedding that preserves ancestor-descendant ordering.
    This is the defining property of the embeddings studied and is invoked throughout the claimed results.

reviewed 2026-06-26 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Compact Geometric Representations of Hierarchies." pith.science (2026). https://pith.science/paper/OID3SMJP

@misc{pith2026260618520,
  author       = {Pith},
  title        = {Pith review of: Compact Geometric Representations of Hierarchies},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OID3SMJP}},
  note         = {Machine review of arXiv:2606.18520}
}
Share X Bluesky LinkedIn Reddit HN
abstract

Computing geometric representations of data is a cornerstone of modern machine learning, typically achieved by training dual encoders which map queries and documents into a shared embedding space. Recent work of You et al. [NeurIPS '25] has extended this approach to hierarchical retrieval, where relevance is determined by the ancestor-descendant relationships in a Directed Acyclic Graph (DAG). While previous work has shown that valid embeddings exist when the number of descendants is small, these bounds degrade significantly for deep hierarchies, requiring dimensions as large as the total number of nodes. In this paper, we investigate compact reachability embeddings for more general graph classes and provide theoretical guarantees for representing hierarchies using embeddings whose dimension depends on structural graph parameters. We prove that for any directed tree, there exists a reachability embedding in constant dimension 3, independent of the tree's size or depth. We generalize this result to graphs characterized by treewidth $t$, constructing embeddings of dimension $O(t \log n)$, where $n$ is the number of nodes. Complementing these upper bounds, we provide matching or near-matching lower bounds, showing that dimension $\Omega(n)$ is necessary for general DAGs and $\Omega(t/\log(n/t))$ is required for graphs of treewidth $t$. We also obtain upper and lower bounds parameterized by the number of cross-edges in the DAG. We additionally show that our embeddings can be constructed on real world datasets, and that they give much smaller dimensions in high recall regimes compared to prior embeddings with theoretical guarantees.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

55 extracted references · 6 canonical work pages · 1 internal anchor

  1. [1]

    IEEE transactions on pattern analysis and machine intelligence , volume=

    Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs , author=. IEEE transactions on pattern analysis and machine intelligence , volume=. 2018 , publisher=

    2018

  2. [2]

    Advances in Neural Information Processing Systems , volume=

    Diskann: Fast accurate billion-point nearest neighbor search on a single node , author=. Advances in Neural Information Processing Systems , volume=

  3. [3]

    Communications of the ACM , volume=

    Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions , author=. Communications of the ACM , volume=. 2008 , publisher=

    2008

  4. [4]

    Siegel, Michael Tang, Ruoxi Sun, Jinsung Yoon, Sercan O

    Bright: A realistic and challenging benchmark for reasoning-intensive retrieval , author=. arXiv preprint arXiv:2407.12883 , year=

    work page arXiv

  5. [5]

    2015 , publisher=

    Parameterized algorithms , author=. 2015 , publisher=

    2015

  6. [6]

    Advances in neural information processing systems , volume=

    Learning bounded treewidth Bayesian networks , author=. Advances in neural information processing systems , volume=

  7. [7]

    Advances in neural information processing systems , volume=

    Learning treewidth-bounded Bayesian networks with thousands of variables , author=. Advances in neural information processing systems , volume=

  8. [8]

    Advances in Neural Information Processing Systems , volume=

    Breaking the glass ceiling for embedding-based classifiers for large output spaces , author=. Advances in Neural Information Processing Systems , volume=

  9. [9]

    Weller, M

    On the theoretical limitations of embedding-based retrieval , author=. arXiv preprint arXiv:2508.21038 , year=

    work page arXiv

  10. [10]

    Approximation, Randomization, and Combinatorial Optimization

    Lower bound methods for sign-rank and their limitations , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) , pages=. 2022 , organization=

    2022

  11. [11]

    The Thirty-ninth Annual Conference on Neural Information Processing Systems , year=

    Hierarchical Retrieval: The Geometry and a Pretrain-Finetune Recipe , author=. The Thirty-ninth Annual Conference on Neural Information Processing Systems , year=

  12. [12]

    SIAM journal on discrete mathematics , volume=

    Low rank matrices with a given sign pattern , author=. SIAM journal on discrete mathematics , volume=. 1989 , publisher=

    1989

  13. [13]

    Sign rank versus

    Alon, Noga and Moran, Shay and Yehudayoff, Amir , booktitle =. Sign rank versus. 2016 , editor =

    2016

  14. [14]

    Asymptotic enumeration of partial orders on a finite set

    Kleitman, D J and Rothschild, B L. Asymptotic enumeration of partial orders on a finite set. Trans. Am. Math. Soc

  15. [15]

    Approximation, Randomization, and Combinatorial Optimization

    Hatami, Hamed and Hatami, Pooya and Pires, William and Tao, Ran and Zhao, Rosie , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) , pages =. 2022 , volume =. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.22 , annote =

    work page doi:10.4230/lipics.approx/random.2022.22 2022

  16. [16]

    ACM SIGMOD Record , volume=

    Efficient management of transitive relationships in large data and knowledge bases , author=. ACM SIGMOD Record , volume=. 1989 , publisher=

    1989

  17. [17]

    Proceedings of the VLDB Endowment , volume=

    Grail: Scalable reachability index for large graphs , author=. Proceedings of the VLDB Endowment , volume=. 2010 , publisher=

    2010

  18. [18]

    22nd International Conference on Data Engineering (ICDE'06) , pages=

    Dual labeling: Answering graph reachability queries in constant time , author=. 22nd International Conference on Data Engineering (ICDE'06) , pages=. 2006 , organization=

    2006

  19. [19]

    ACM Transactions on Database Systems (TODS) , volume=

    Path-tree: An efficient reachability indexing scheme for large directed graphs , author=. ACM Transactions on Database Systems (TODS) , volume=. 2011 , publisher=

    2011

  20. [20]

    Proceedings of the 2008 ACM SIGMOD international conference on Management of data , pages=

    Efficiently answering reachability queries on very large directed graphs , author=. Proceedings of the 2008 ACM SIGMOD international conference on Management of data , pages=

    2008

  21. [21]

    Proceedings of the 2007 ACM SIGMOD international conference on Management of data , pages=

    Fast and practical indexing and querying of very large graphs , author=. Proceedings of the 2007 ACM SIGMOD international conference on Management of data , pages=

    2007

  22. [22]

    2022 , publisher=

    Introduction to algorithms , author=. 2022 , publisher=

    2022

  23. [23]

    Graph minors. II. Algorithmic aspects of tree-width , author=. Journal of algorithms , volume=. 1986 , publisher=

    1986

  24. [24]

    2025 , publisher=

    Graph theory , author=. 2025 , publisher=

    2025

  25. [25]

    SIAM Journal on Computing , volume=

    The transitive reduction of a directed graph , author=. SIAM Journal on Computing , volume=. 1972 , publisher=

    1972

  26. [26]

    Journal of Computer and System Sciences , volume=

    A linear lower bound on the unbounded error probabilistic communication complexity , author=. Journal of Computer and System Sciences , volume=. 2002 , publisher=

    2002

  27. [27]

    Proceedings of the American mathematical Society , volume=

    The number of finite topologies , author=. Proceedings of the American mathematical Society , volume=

  28. [28]

    Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval , pages=

    Optimizing dense retrieval model training with hard negatives , author=. Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval , pages=

  29. [29]

    ACM Transactions on Information Systems , volume=

    Dense text retrieval based on pretrained language models: A survey , author=. ACM Transactions on Information Systems , volume=. 2024 , publisher=

    2024

  30. [30]

    Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval , pages=

    Scaling laws for dense retrieval , author=. Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval , pages=

  31. [31]

    Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing , pages=

    Dense x retrieval: What retrieval granularity should we use? , author=. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing , pages=

    2024

  32. [32]

    Developments in Theoretical Computer Science , volume=

    A tourist guide through treewidth , author=. Developments in Theoretical Computer Science , volume=. 1994 , publisher=

    1994

  33. [33]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

    An improved parameterized algorithm for treewidth , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  34. [34]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Embedding Planar Graphs into Graphs of Treewidth O (log3 n) , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    2025

  35. [35]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Losing treewidth in the presence of weights , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    2025

  36. [36]

    Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

    Treewidth inapproximability and tight eth lower bound , author=. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

  37. [37]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

    Approximate max-flow min-multicut theorem for graphs of bounded treewidth , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  38. [38]

    2023 IEEE 64th annual symposium on foundations of computer science (FOCS) , pages=

    Planar and minor-free metrics embed into metrics of polylogarithmic treewidth with expected multiplicative distortion arbitrarily close to 1 , author=. 2023 IEEE 64th annual symposium on foundations of computer science (FOCS) , pages=. 2023 , organization=

    2023

  39. [39]

    2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Dynamic treewidth , author=. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2023 , organization=

    2023

  40. [40]

    Proceedings of the 19th ACM international conference on Information and knowledge management , pages=

    Path-hop: efficiently indexing large graphs for reachability queries , author=. Proceedings of the 19th ACM international conference on Information and knowledge management , pages=

  41. [41]

    Artificial Intelligence and Statistics , pages=

    Learning optimal bounded treewidth Bayesian networks via maximum satisfiability , author=. Artificial Intelligence and Statistics , pages=. 2014 , organization=

    2014

  42. [42]

    Artificial Intelligence and Statistics , pages=

    Exact learning of bounded tree-width Bayesian networks , author=. Artificial Intelligence and Statistics , pages=. 2013 , organization=

    2013

  43. [43]

    Journal of Combinatorial Theory, Series B , volume=

    Directed tree-width , author=. Journal of Combinatorial Theory, Series B , volume=. 2001 , publisher=

    2001

  44. [44]

    Journal of Combinatorial Theory, Series B , volume=

    The dag-width of directed graphs , author=. Journal of Combinatorial Theory, Series B , volume=. 2012 , publisher=

    2012

  45. [45]

    ACM Computing Surveys , volume=

    Indexing techniques for graph reachability queries , author=. ACM Computing Surveys , volume=. 2025 , publisher=

    2025

  46. [46]

    Proceedings of the 31st international conference on Very large data bases , pages=

    Stack-based algorithms for pattern matching on dags , author=. Proceedings of the 31st international conference on Very large data bases , pages=

  47. [47]

    2012 , publisher=

    Hadamard matrices and their applications , author=. 2012 , publisher=

    2012

  48. [48]

    Think Locally, Act Globally: Highly Balanced Graph Partitioning

    Sanders, Peter and Schulz, Christian. Think Locally, Act Globally: Highly Balanced Graph Partitioning. Experimental Algorithms. 2013

    2013

  49. [49]

    W ord N et: A Lexical Database for E nglish

    Miller, George A. W ord N et: A Lexical Database for E nglish. H uman L anguage T echnology: Proceedings of a Workshop held at P lainsboro, N ew J ersey, M arch 8-11, 1994. 1994

    1994

  50. [50]

    Nucleic Acids Research , volume =

    The Gene Ontology Consortium , title =. Nucleic Acids Research , volume =. 2025 , month =. doi:10.1093/nar/gkaf1292 , url =

    work page doi:10.1093/nar/gkaf1292 2025

  51. [51]

    Gene ontology: tool for the unification of biology

    Ashburner, M and Ball, C A and Blake, J A and Botstein, D and Butler, H and Cherry, J M and Davis, A P and Dolinski, K and Dwight, S S and Eppig, J T and Harris, M A and Hill, D P and Issel-Tarver, L and Kasarskis, A and Lewis, S and Matese, J C and Richardson, J E and Ringwald, M and Rubin, G M and Sherlock, G. Gene ontology: tool for the unification of ...

  52. [52]

    Cora Dataset

    McCallum, Andrew. Cora Dataset

  53. [53]

    $\mathbb{R}^{2k}$ is Theoretically Large Enough for Embedding-based Top-$k$ Retrieval

    Zihao Wang and Hang Yin and Lihui Liu and Hanghang Tong and Yangqiu Song and Ginny Wong and Simon See , year=. 2601.20844 , archivePrefix=

    work page internal anchor Pith review Pith/arXiv arXiv

  54. [54]

    DReX: Accurate and Scalable Dense Retrieval Acceleration via Algorithmic-Hardware Codesign , year =

    Quinn, Derrick and Y\". DReX: Accurate and Scalable Dense Retrieval Acceleration via Algorithmic-Hardware Codesign , year =. Proceedings of the 52nd Annual International Symposium on Computer Architecture , pages =. doi:10.1145/3695053.3731079 , abstract =

    work page doi:10.1145/3695053.3731079

  55. [55]

    2026 , eprint=

    IMRNNs: An Efficient Method for Interpretable Dense Retrieval via Embedding Modulation , author=. 2026 , eprint=

    2026

This paper was first reviewed by grok-4.3 on June 26, 2026.