Explainable clustering replaces the usual cluster boundaries with a decision tree. Each internal node asks one question about one feature ("is feature 7 below 3.2?"), and each leaf is a cluster, so anyone can check why a point landed where it did. The theory of this setting is now mature for a single, fixed number of clusters $k$. The extra cost of using such a tree instead of the best unrestricted clustering is called the price of explainability, and it is known to depend sharply on the data dimension $d$. Yet practitioners rarely read a threshold tree at one fixed $k$. They drill down from the root, treating the first split as a 2-cluster answer, the first few splits as a coarse taxonomy, and the full tree as the fine-grained one. Nobody has asked whether a single threshold tree can be good at every level at once, or how the answer depends on dimension.
This note proposes to define, measure, and bound the price of explainable hierarchy: the worst ratio, taken over all levels $j = 2, \dots, k$, between the cost of the $j$-leaf prefix of one axis-aligned tree and the optimal unrestricted $j$-clustering. The central bet is that in low dimension this simultaneous ratio can be bounded independently of $k$, matching the low-dimensional single-$k$ results. The alternative is that errors made near the root compound with depth. The project delivers a dimension-sweep answer to that question, an algorithm designed for it, and an honest test against the obvious recipe of growing one tree and pruning it.
Core Claim
Current explainable-clustering algorithms, including Iterative Mistake Minimization (IMM, which builds the tree top-down by choosing cuts that separate the fewest points from their reference centers), random coordinate cuts, and Ex-Greedy, are all rounding procedures aimed at one target $k$. Their early splits are chosen to separate $k$ reference centers eventually. They are not chosen to make the 3-leaf prefix a good 3-clustering. Separately, the price of forcing unrestricted clusterings at successive $k$ to nest is known to be a constant for radius and diameter objectives, and is bounded by loose constants (16 for $k$-medians, 32 for $k$-means) otherwise (The Price of Hierarchical Clustering). That analysis puts no axis-alignment constraint on the boundaries.
We claim that the two penalties compose in a dimension-controlled way. Let $T$ be a threshold tree whose splits are ordered, let $T_j$ be the partition given by its first $j-1$ splits, and let $\mathrm{OPT}_j$ be the optimal unrestricted $j$-clustering cost. The quantity of interest is
$$\Pi(T) = \max_{2 \le j \le k} \frac{\mathrm{cost}(T_j)}{\mathrm{OPT}_j}.$$
We conjecture that for $k$-medians there are trees with $\Pi(T) = O(\mathrm{poly}(d))$ times the unrestricted price of hierarchy, independent of $k$, when $d \ll \log k$. For $k$-means, we conjecture the simultaneous ratio tracks the single-$k$ rate $k^{1-2/d}$ up to polylogarithmic factors. Either claim, or a lower bound refuting it, would be new.
Relation to Prior Work
The dimension-dependent single-$k$ results motivate the conjecture and constrain it. Almost Tight Approximation Algorithms for Explainable Clustering shows explainable $k$-medians costs $O(d \log^2 d)$ when $d \ll \log k$, with an $\Omega(\min(d, \log k))$ lower bound. On the price of explainability for some clustering problems gives $O(d \log k)$ for $k$-medians and proposes Ex-Greedy, which picks each cut to directly reduce clustering cost. Near-Optimal Explainable k-Means for All Dimensions pins the $k$-means rate at $k^{1-2/d}$ up to polylogarithmic factors. All three bound only the final $k$-leaf partition. We ask for the same kind of guarantee at every prefix of one tree.
The dimension-independent results set the high-dimensional reference point. Random Cuts are Optimal for Explainable k-Medians achieves $2\ln k + 2$ with uniformly random cuts, and The Price of Explainability for Clustering settles $k$-medians at exactly $1 + H_{k-1}$.
The main constraint comes from Impossibility of Depth Reduction in Explainable Clustering. Its 2D "blocking" construction forces any good tree to peel clusters off one at a time, so cutting depth to $k-2$ makes the cost unbounded. That result is about depth, not prefixes, but it signals that in $d=2$ the early splits of a good $k$-tree can be forced into shapes that are poor coarse clusterings. So a $k$-independent simultaneous bound may fail at $d=2$ and hold only once $d$ is large enough to escape blocking. Whether higher dimension helps here is exactly the open question that paper leaves. Our dimension sweep answers it for the hierarchical version.
Two other lines supply methods. SpEx: A Spectral Approach to Explainable Clustering builds hierarchical axis-aligned trees by minimizing graph conductance, with no worst-case guarantee. ExKMC: Expanding Explainable k-Means Clustering grows trees beyond $k$ leaves using a cost surrogate. Neither targets simultaneous quality across levels.
Research Program
The algorithm, which we call level-anchored cuts, takes as input a nested sequence of unrestricted reference clusterings. We obtain it from a hierarchical $k$-medians or Ward-style procedure whose own price of hierarchy is measurable. Going from level $j$ to $j+1$, exactly one reference cluster splits into two children with two new centers. The tree must make its $j$-th cut inside the leaf that currently holds that cluster.
That cut separates two centers inside a box. The single-$k$ theory makes this a cheap problem: for two centers IMM already achieves a factor 2 for $k$-medians (Explainable k-Means and k-Medians Clustering). We sample the cut coordinate with probability proportional to the centers' separation along that coordinate, restricted to the leaf's box. The difficulty is inheritance. Points misplaced at level $j$ stay misplaced below it.
We therefore add a bounded repair step. The level-$j$ cut may be chosen among candidates that also reduce the cost contributed by previously misplaced points, in the spirit of Ex-Greedy's cost-driven selection. The theoretical work is to bound accumulated error across levels as a function of $d$. The intuition is that in dimension $d$ a box holding one reference cluster can be carved by at most $O(d)$ "kinds" of separating directions. We expect this to be what lets error stay $k$-independent in low $d$. We will either prove this for $k$-medians or produce a lifted blocking construction showing it fails.
The empirical program measures $\Pi(T)$ directly. Because $\mathrm{OPT}_j$ is unknown on real data, we use the best of many restarts of unrestricted $k$-means or $k$-medians at each $j$ as the denominator, following the empirical practice of the PoE papers.
Baselines
The naive reference point takes a single-$k$ tree built by IMM or random coordinate cuts at $k = k_{\max}$ and reads off its prefixes in split order, with no hierarchical design. This measures how bad "just drill down" is today, and it isolates whether hierarchy-awareness matters at all.
The strongest competitor is grow-then-prune. Build a fine tree with ExKMC or random cuts, then apply weakest-link pruning with $k$-means cost of leaf means as the criterion. This yields a nested sequence of subtrees, one per size, so it is a genuine explainable hierarchy produced from existing tools. We give it the same data, the same reference clusterings, the same number of random restarts, and a matched wall-clock budget, and we tune its initial tree size over $\{2k, 4k\}$, the range ExKMC: Expanding Explainable k-Means Clustering found brings single-$k$ cost within 1–2% of unrestricted $k$-means. On its 2D synthetic set, that paper reports approximation ratio 1.26 for IMM at $k$ leaves and 1.02 for ExKMC at $2k$ leaves. For the simultaneous all-levels ratio, no reported result found on Lacuna for any method. Beating grow-then-prune means a lower median and a lower worst-case $\Pi(T)$ across datasets and restarts, at equal or smaller depth.
SpEx-kNN run top-down is the non-centroid hierarchical competitor. MaxSpacing (The computational complexity of some explainable clustering problems) is included because greedy top-down trees are provably optimal for spacing. Its $\Theta(n-k)$ price of explainability predicts it will do poorly on distance cost, and it serves as a check on that prediction.
The key ablation removes the repair step, and separately replaces the nested reference hierarchy with independent flat clusterings at each $j$. This isolates whether gains come from anchoring to a hierarchy or from the cost-aware repair.
Why not just…?
Why not just build a separate explainable tree for each $k$? Per-$k$ trees are individually near-optimal, but they are not nested, so there is no drill-down story: a point's 3-cluster rule need not be a prefix of its 5-cluster rule. We report both their per-level cost, as a lower envelope, and a nesting-violation rate. The first tells us how close our single tree gets to the unconstrained-by-nesting ideal. The second shows why that ideal is not an answer.
Why not just grow a big tree and prune it? This is a real threat, because weakest-link pruning already gives nested subtrees. Its weakness is that pruning can only remove splits chosen for the fine target, so the coarse levels inherit cuts that were placed to separate small clusters. That is the same mechanism behind the blocking example of Impossibility of Depth Reduction in Explainable Clustering. If pruning matches level-anchored cuts on real data and only loses on the lifted blocking instances, we will say so. The contribution then shifts to the theory explaining when pruning suffices.
Why not just fit CART to hierarchical cluster labels? SpEx: A Spectral Approach to Explainable Clustering shows CART's split rule rewards cutting through dense cluster interiors. Explainable k-Means and k-Medians Clustering shows impurity-based splits can have unbounded clustering cost. We include CART on level-labels as a sanity check rather than a main competitor.
Why not assume a Gaussian mixture, as in Explainable Clustering Beyond Worst-Case Guarantees? That method reports a price of explainability of 1.04 on Wine under well-separated mixtures, but only for a single $k$. Its guarantee disappears under misspecification. We run it per level on Wine and Rice to show where the easy regime ends.
Proposed Experiments
The first experiment is a dimension sweep on synthetic data. We generate Gaussian mixtures with a planted nested hierarchy for $d \in \{2, 3, 4, 8, 16, 64\}$ and $k$ up to 256. We also lift the 2D blocking construction to $d$ dimensions by embedding and by adding coordinates in which the nested clusters become separable. For each method we plot $\Pi(T)$ against $k$. The decisive check is whether level-anchored cuts give a curve flat in $k$ for moderate $d$ while the naive prefix baseline grows. A second check is whether the lifted blocking instances stop hurting once $d \ge 3$, which would settle the hierarchical form of the depth question.
The second experiment uses real data. We use Iris, Wine, Rice, Covtype, MNIST, CIFAR-10, and SBERT-embedded 20 Newsgroups. Together these span $d = 4$ to $d = 3{,}072$, the range On the price of explainability for some clustering problems used, where Ex-Greedy beat IMM on 5 of 10 datasets and tied on the rest. We add R15 and Pathbased for non-spherical structure.
We report $\Pi(T)$, the per-level cost ratio curve, tree depth, and runtime. On Covtype the runtime target is the "under 15 minutes" ExKMC reports for over 500,000 points. For the high-dimensional sets, we also measure how many distinct coordinates the top levels use. This tests whether an effective low dimension, not the ambient $d$, governs the simultaneous ratio.
The result that would falsify the proposal is grow-then-prune matching level-anchored cuts within noise on all synthetic and real sets, including the lifted blocking instances. In that case the practical recommendation is pruning, and the theoretical question becomes why pruning is enough.
References
- The Price of Hierarchical Clustering
- Almost Tight Approximation Algorithms for Explainable Clustering
- On the price of explainability for some clustering problems
- Near-Optimal Explainable k-Means for All Dimensions
- Random Cuts are Optimal for Explainable k-Medians
- The Price of Explainability for Clustering
- Impossibility of Depth Reduction in Explainable Clustering
- SpEx: A Spectral Approach to Explainable Clustering
- ExKMC: Expanding Explainable k-Means Clustering
- Explainable k-Means and k-Medians Clustering
- The computational complexity of some explainable clustering problems
- Explainable Clustering Beyond Worst-Case Guarantees