MIT team proves any tree hierarchy fits in just 3 dimensions
Constant-dimension reachability embeddings for directed trees — a breakthrough in compact representations.
Modern machine learning often relies on dual encoders that map queries and documents into a shared embedding space for similarity search. The 2025 NeurIPS work by You et al. extended this to hierarchical retrieval, where relevance depends on ancestor-descendant relationships in a directed acyclic graph (DAG). However, their embeddings required dimensions as large as the total number of nodes for deep hierarchies, limiting scalability. A new paper from MIT researchers (Gokhale, Indyk, Liu, Silwal, Wang, Xu), published at COLT 2026, tackles this by investigating compact reachability embeddings that depend only on structural graph parameters.
The team proves a groundbreaking result: any directed tree can be embedded in just 3 dimensions, independent of the tree's size or depth. For more complex DAGs characterized by treewidth t, they construct embeddings of dimension O(t log n), where n is the number of nodes. They also prove matching or near-matching lower bounds — Ω(n) for general DAGs and Ω(t/ log(n/t)) for treewidth-t graphs. In real-world datasets, their embeddings achieve high recall with dramatically smaller dimensions than prior theoretical methods, making them practical for large-scale hierarchical retrieval systems.
- Any directed tree can be represented as a reachability embedding in constant 3 dimensions, independent of tree size or depth.
- For DAGs with treewidth t, embeddings require only O(t log n) dimensions, with a near-matching lower bound of Ω(t/ log(n/t)).
- Real-world tests show these embeddings achieve high recall using far fewer dimensions than previous theoretically-guaranteed methods.
Why It Matters
Enables scalable, efficient hierarchical retrieval for search and AI systems without exploding embedding dimensions.