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.

We consider the ℓ0-Low Rank Approximation problem, where the input consists of a matrix A ∈ ℝnR×nc and an integer k, and the goal is to find a matrix B of rank at most k that minimizes ‖A — B‖0, which is the number of entries where A and B differ. For any constant k and ɛ > 0, we present a polynomial time (1 + ɛ)- approximation time for this problem, which significantly improves the previous best poly(k)-approximation.