Explainable Cluster Scans: Axis-Aligned Partitions That Contain Detector Systematics

Collider searches for new particles increasingly work by letting an algorithm carve events into many groups and then looking for a group whose count bumps up at one mass value. These analyses are limited less by the number of events than by residual systematic uncertainties: small, known-but-imprecise miscalibrations of the detector (for example, a 1–2% error in the jet energy scale) that slightly move every event. When the groups are ordinary $k$-means clusters, meaning cells around the nearest center (Voronoi cells), each cell boundary mixes all features at once. A shift in any single calibrated quantity therefore moves every boundary, and the effect on each cell's count is hard to write down. This note proposes replacing those cells with an explainable clustering tree: a tree whose every split tests one feature against a threshold, as in "jet mass above 120 GeV and $\tau_{21}$ below 0.4." A calibration shift on one feature then moves only the cuts on that feature, by an amount that can be computed exactly.

The central claim is that the "price of explainability," the loss from forcing clusters into axis-aligned boxes, has so far been measured in the wrong currency for this setting. Measured in $k$-means cost it is always at least 1. Measured in discovery significance after the systematics are profiled, meaning fitted as free parameters alongside the signal, it can shrink toward 1 or fall below it. Two facts support this. Axis-aligned cuts keep the effect of each calibration error inside the leaves that actually use the affected feature. And physics searches operate on a handful of high-level features with many clusters ($k=50$ in Cluster Scanning), which is exactly the low-dimensional regime ($d \ll k$) where dimension-dependent theory says the geometric price is smallest.

Core Claim

Cluster Scanning runs mini-batch $k$-means ($k=50$) on events inside a mass window, then scans cluster spectra across dijet mass for local excesses. It reports needing 0.61 times as many signal events for a $3\sigma$ discovery as a standard functional fit on the LHC Olympics R&D data. The same paper names its own weakness: the cluster centers stay correlated with the dijet mass $m_{jj}$, which distorts the background shape. Nobody has asked what happens to that distortion, or to robustness against calibration nuisances, when the clusters become boxes.

We claim three things. First, an explainable tree with $k$ leaves makes the sensitivity of every leaf's count to each calibration nuisance available in closed form. This allows those sensitivities to be penalized during tree construction rather than estimated afterwards. Second, on high-level jet features ($d$ around 4–8, $k$ around 50), the geometric price of explainability is small and grows like $d\log k$ rather than $k$. The upper bounds of On the price of explainability for some clustering problems, $O(d\log k)$ for $k$-medians and $O(kd\log k)$ for $k$-means, predict this, and we will test it directly. Third, the net effect on significance after profiling is at worst a modest loss and plausibly a gain over unconstrained $k$-means. Each leaf also comes with a readable cut-flow that physicists can audit.

The structural fact behind the first claim is simple. Let leaf $L$ be a box defined by thresholds, and let a scale nuisance $\nu_j$ rescale feature $j$ as $x_j \to (1+\nu_j)x_j$. Then the first-order change in the leaf's expected count $N_L$ is

$$\frac{\partial N_L}{\partial \nu_j}\Big|_{\nu=0} = \sum_{f \in F_j(L)} \pm\, \theta_f \int_{f} p(x)\, dA,$$

where $F_j(L)$ is the set of box faces of $L$ that come from cuts on feature $j$, $\theta_f$ is that cut's threshold, and $p$ is the event density on the face. The sign is set by which side of the cut the leaf lies. If feature $j$ never appears on the path to $L$, the derivative is exactly zero. A Voronoi cell has no such sparsity: generically, every face depends on every coordinate.

Research Program

The method, which we call a systematics-aware explainable cluster scan, builds the tree greedily in the style of Ex-Greedy from On the price of explainability for some clustering problems, which scores each candidate split by the clustering objective itself. We extend that score with two penalties. The first is the nuisance-sensitivity penalty above, weighted by each nuisance's prior width. The second is a decorrelation penalty: the variance of the leaf's occupancy fraction across $m_{jj}$ sidebands. This targets the mass sculpting that Cluster Scanning reports. Both penalties are sums over faces, so they can be evaluated with the same sorted-sweep dynamic programming that makes IMM's split search cost $O(dn\log n)$ per node in Explainable k-Means and k-Medians Clustering.

We add the depth term of Shallow decision trees for explainable k-means clustering, which penalizes the weighted average depth of leaves. Shallow trees help twice here: short rules are readable, and fewer features per path means fewer nonzero nuisance derivatives. The data used to build the tree and the data used for the final scan are kept disjoint.

The downstream test keeps the Cluster Scanning statistics, meaning standardized per-leaf spectra across mass bins, but wraps them in a binned profile likelihood. In that likelihood, each nuisance enters through the analytic leaf-count derivatives, extended beyond first order by reweighting templates. Following Robust resonant anomaly detection with NPLM, significance is calibrated against signal-free pseudo-experiments that include nuisance fluctuations. We also calibrate over the choice of penalty weights with the same hyper-test logic, so that tuning cannot manufacture a signal.

The theory component is deliberately modest. The computational complexity of some explainable clustering problems proves that the optimal explainable tree is APX-hard to find (it cannot even be approximated arbitrarily well in polynomial time), so we do not promise optimality. We will prove two results. The first is the sparsity statement: a leaf at depth $H$ has at most $H$ nonzero nuisance derivatives. The second is a bound on the extra $k$-means cost from the penalties when the penalty weights are small, relative to the unpenalized Ex-Greedy tree. Empirically, we will measure whether geometric price-of-explainability curves follow $d\log k$ or $k$ as $d$ and $k$ vary. For $k$-means specifically, the tight dependence on dimension remains open even after Near-Optimal Explainable k-Means for All Dimensions, so this measurement is informative in its own right.

Baselines

The naive reference point is a fixed rectangular grid: equal-quantile bins on each high-level feature, with the product truncated to about 50 cells. This is what a physicist would do by hand. Any learned tree must beat it on significance at matched cell count, or the learning adds nothing.

The direct predecessor is Cluster Scanning itself, meaning unconstrained mini-batch $k$-means with $k=50$ and the same standardized-spectrum scan. The comparison uses identical event selection, features, mass window, $k$, and pseudo-experiment calibration. Its reported result on LHCO R&D is the 0.61 factor in signal events needed for $3\sigma$ relative to functional fits. We will reproduce this number before comparing. Beating it means requiring fewer injected signal events to reach $3\sigma$ once injected energy-scale nuisances are profiled. Matching it on nominal data while degrading less under nuisances also counts.

The strongest existing sensitivity method is kernel NPLM with the hyper-test from Robust resonant anomaly detection with NPLM. On LHCO at signal-to-background ratio $8.2\times10^{-4}$, it reports a median Z-score of $0.30\pm0.04$, against $0.1\pm0.1$ for a BDT. We will run NPLM on the same features, with the same nuisances and the same pseudo-experiment budget. We do not expect a single explainable tree to beat it outright. The honest success criterion is to land within its error band, or clearly above the BDT, while providing auditable regions.

On the dimuon benchmark with momentum-scale systematics from Learning new physics from an imperfect machine, NPLM reports an agnostic tax of about 2.7 relative to the optimal model-dependent search. We will report the tree's tax in the same units.

Two ablations isolate the key ingredient. The first is plain Ex-Greedy and IMM trees built on the same $k$-means reference centers with no penalties. This separates "boxes" from "boxes chosen for systematics." The second is SpEx-kNN from SpEx: A Spectral Approach to Explainable Clustering, which builds the tree without reference centers and so tests whether a poor $k$-means solution is what drives tree quality. All tree variants receive the same tuning budget over penalty weights, and that budget is charged in the look-elsewhere calibration.

Why not just…?

Why not just fit CART to the Cluster Scanning labels? SpEx shows that CART implicitly optimizes an objective that rewards separating points in different clusters, so it tends to cut through dense clusters. Explainable k-Means and k-Medians Clustering shows that label-entropy splits can have arbitrarily bad clustering cost. We will still include CART on the $k$-means labels as a cheap comparator. If it matches our method on significance under nuisances, the penalties are unnecessary.

Why not just add a systematics penalty to ordinary $k$-means? This is the real threat. If Voronoi cells regularized for nuisance sensitivity match the tree's robustness, then the tree's only contribution is readability. We will build this baseline by estimating Voronoi count derivatives numerically, through reweighting under shifted calibrations, and penalizing them during Lloyd iterations. If it matches the tree, we will report that axis-alignment buys interpretability at no robustness cost, a weaker but still useful result. If the tree wins, the closed-form sparsity of the tree's derivatives is doing real work.

Why not just use NPLM or contrastive embeddings and explain afterwards? Anomaly preserving contrastive neural embeddings reaches $12.1\sigma$ on a black box where raw 57D inputs give $0\sigma$, so learned embeddings are powerful. But their coordinates carry no physical calibration, so a detector nuisance cannot be pushed through them analytically. Post-hoc attributions, rejected for high-stakes use in Explainable k-Means and k-Medians Clustering, do not yield regions that can be propagated through the likelihood. We use embeddings only as a controlled knob for dimension, not as the deliverable.

Why not just use boosted decision trees in a classification-based hunt? The reported LHCO median Z-score of $0.1\pm0.1$ for BDTs, and their sensitivity to threshold choices, argue against this. So does the fact that an ensemble of hundreds of trees is not an auditable cut-flow.

Proposed Experiments

The primary testbed is the LHC Olympics 2020 R&D dataset (1M QCD dijets, 100k signal events) from The LHC Olympics 2020, using standard high-level jet substructure features. We inject signal at a ladder of rates down to $8.2\times10^{-4}$. We also inject jet-energy-scale and jet-mass-scale shifts of a few percent as nuisances with known priors, because LHCO ships without systematics. The dimuon benchmark with momentum-scale systematics serves as a second testbed. The black boxes BB1–BB3 serve as blind checks, with BB2, which is background-only, used to measure false-discovery rates.

The first decisive check is the sensitivity price of explainability: the signal events needed for $3\sigma$ with the tree, divided by the same quantity for Cluster Scanning, measured with and without profiled nuisances. The hypothesis is confirmed if the ratio moves toward or below 1 when nuisances are switched on. It is refuted if the ratio is unchanged or grows.

The second check is mass sculpting. We compare the per-leaf correlation with $m_{jj}$ and the background-only pull distributions against those of Voronoi cells.

The third check is the dimension law. We measure geometric price-of-explainability for $k \in \{10,25,50,100\}$ and $d$ ranging over 4–8 physical features and over the 4D–64D contrastive embeddings, then fit whether cost grows like $d\log k$ or like $k$.

The fourth check is null calibration. Across nuisance-fluctuated background-only pseudo-experiments, including the scan over penalty weights, the test statistic must match its asymptotic reference. A method that improves significance but fails this check is counted as a failure.