# Hierarchical Clustering With Confidence

arXiv: https://arxiv.org/abs/2512.06522 · HTML: https://mlsanity.com/paper/2512.06522/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 6 Dec 2025.

## Builds on (most cited first, 15 of 15)

- [Optimal Inference After Model Selection](https://mlsanity.com/paper/1410.2597/) (2014)
- [Selective Inference for Hierarchical Clustering](https://mlsanity.com/paper/2012.02936/) (2020)
- [Selective inference for k-means clustering](https://mlsanity.com/paper/2203.15267/) (2022)
- [Splitting strategies for post-selection inference](https://mlsanity.com/paper/2102.02159/) (2021)
- [Data fission: splitting a single data point](https://mlsanity.com/paper/2112.11079/) (2021)
- [Approximate selective inference via maximum likelihood](https://mlsanity.com/paper/1902.07884/) (2019)
- [Generalized Data Thinning Using Sufficient Statistics](https://mlsanity.com/paper/2303.12931/) (2023)
- [Winners with Confidence: Discrete Argmin Inference with an Application to Model Selection](https://mlsanity.com/paper/2408.02060/) (2024)
- [Exact Selective Inference with Randomization](https://mlsanity.com/paper/2212.12940/) (2022)
- [Selective inference for clustering with unknown variance](https://mlsanity.com/paper/2301.12999/) (2023)
- [A (tight) upper bound for the length of confidence intervals with conditional coverage](https://mlsanity.com/paper/2007.12448/) (2020)
- [Selective inference using randomized group lasso estimators for general models](https://mlsanity.com/paper/2306.13829/) (2023)
- [Inference with Randomized Regression Trees](https://mlsanity.com/paper/2412.20535/) (2024)
- [Testing for a difference in means of a single feature after clustering](https://mlsanity.com/paper/2311.16375/) (2023)
- [Classification Trees with Valid Inference via the Exponential Mechanism](https://mlsanity.com/paper/2511.15068/) (2025)

## Abstract (arXiv)

Agglomerative hierarchical clustering is one of the most widely used approaches for exploring how observations in a dataset relate to each other. However, its greedy nature makes it highly sensitive to small perturbations in the data, often producing different clustering results and making it difficult to separate genuine structure from spurious patterns. In this paper, we show how randomizing hierarchical clustering can be useful not just for measuring stability but also for designing valid hypothesis testing procedures based on the clustering results. We propose a simple randomization scheme together with a method for constructing a valid p-value at each node of the hierarchical clustering dendrogram that quantifies evidence against performing the greedy merge. Our test controls the Type I error rate, works with any hierarchical linkage without case-specific derivations, and simulations show it is substantially more powerful than existing selective inference approaches. To demonstrate the practical utility of our p-values, we develop an adaptive α-spending procedure that estimates the number of clusters, with a probabilistic guarantee on overestimation. Experiments on simulated and real data show that this estimate yields powerful clustering and can be used, for example, to assess clustering stability across multiple runs of the randomized algorithm.