Locally Rotated Tail Scoring for Anomaly Detection

A cheap way to find anomalies is to treat every feature as independent. You measure how far into the tail of its own distribution each coordinate of a point falls, then add up those per-feature surprises. The method ECOD does exactly this and ranks first in ROC-AUC across 30 standard outlier benchmarks while running in time linear in samples and features (ECOD). Its authors also name its blind spot. A point can look ordinary on every single feature and still be anomalous because it breaks a correlation (a tall person with a child's weight), or because it sits in the empty gap between two clusters. Principal component analysis (PCA), which rotates data onto orthogonal axes ordered by variance, removes correlation. In the rotated frame, a point that breaks a correlation becomes an extreme value on a low-variance axis. The catch is that a single global rotation cannot straighten out data made of several differently shaped clusters.

We propose to split the data into regions, give each region its own PCA frame, and score points with ECOD-style nonparametric tail probabilities in that local frame. The split is not tuned by hand. A region is divided further only while a classifier can still tell its rotated data apart from a copy in which each rotated coordinate has been shuffled independently. That test, borrowed from adversarial random forests, directly checks whether independence holds in the rotated coordinates. The result is a detector that keeps linear-time, assumption-light tail scoring. It also turns the two failure cases ECOD's authors list, broken correlations and between-cluster gaps, into ordinary tail events. The same machinery gives a principled way to compress 768- to 3072-dimensional text embeddings before tail scoring.

Core Claim

The independence assumption behind tail-sum detectors fails for a reason that can be fixed and measured: dependence between the axes. It can be restored locally with a rotation instead of a richer density model. We claim three things. First, per-region PCA frames combined with nonparametric per-coordinate tails will close most of ECOD's gap on "dependency" and "clustered" anomalies as defined by ADBench, while matching ECOD on "global" anomalies. Second, the gain over a single global PCA rotation will appear specifically on multimodal data. Third, a shuffle-discrimination test of leftover dependence will predict, before any labels are seen, on which datasets rotation will help.

For a point $x$ assigned to region $k$, with region mean $\mu_k$ and orthogonal rotation $Q_k$ from that region's PCA, write $z = Q_k^\top (x - \mu_k)$ and score

$$S(x) = -\log \pi_k + \sum_{j=1}^{d} -\log \min\big(F_{kj}(z_j),\, 1 - F_{kj}(z_j)\big).$$

Here $\pi_k$ is the fraction of training points in region $k$, and $F_{kj}$ is the empirical cumulative distribution function of rotated coordinate $j$ within region $k$. The two-sided minimum replaces ECOD's skewness rule, because rotated coordinates are roughly centered. The sum runs over all $d$ rotated axes, including the smallest-variance ones. Those minor axes are where points that break correlations become extreme, so dropping them, as compression usually does, would throw away exactly the signal we want.

Research Program

The build has three parts.

The first is the partition-and-rotate procedure. It starts from one region. In each region it computes PCA, rotates, and builds a companion sample by permuting each rotated coordinate independently. It then trains a small random forest to separate real from permuted rows. If the out-of-bag accuracy stays meaningfully above 0.5, the region is split in two with 2-means and the step recurses, subject to a minimum region size so the empirical tails stay reliable. This stopping rule adapts the convergence criterion of adversarial random forests, which alternate between fitting trees and generating synthetic data until leaves look independent. It departs from them in two ways. The adversarial random forest cuts along the original feature axes and models each leaf with truncated Gaussian or uniform marginals (arfpy). We cut in rotated coordinates and keep fully empirical marginals. The adversarial random forest authors note that its convergence can fail under complex dependence in finite samples. Rotation should reduce how many cuts are needed.

The second part is the scoring path. Scoring is linear in $d$ per region, plus a $d \times d$ rotation. For embeddings, we first apply the mean-removal and dominant-direction removal of PPA+PCA, then truncate to the dimension at which PCA compression of retrieval vectors reports a plateau (about 256 dimensions capturing roughly 90% of variance). The minor axes of that truncated space are kept.

The third part is analysis. We check whether the final discriminator accuracy of each region, a label-free number, predicts the per-dataset gain over plain ECOD.

The closest existing link between the two directions is the mixture of probabilistic PCA models used for rare-event importance sampling in Scalable Importance Sampling with Low-Rank Mixture Proposals. It shares our idea of local low-rank frames and shows these frames beat full-rank mixtures badly at $d=40$ (relative error −0.024 versus −0.997 on Branches). That result supplies part of the method and also motivates it. Its components are Gaussian, however, and it treats the off-subspace residual as isotropic noise. We keep nonparametric tails on every axis and choose the number of regions by an independence test rather than by likelihood. La RoSA and Loki show that PCA rotations make LLM activations and attention keys axis-aligned and more Gaussian. They use this only for pruning and speed, never for density or anomaly scoring. Kernel PCA for OOD detection is a constraint on our design: it finds that linear PCA fails when in- and out-of-distribution data are tangled nonlinearly. Our partition is the piecewise-linear answer to that failure, and kernel features are tested as a competitor rather than assumed away.

Baselines

The naive reference is ECOD on the raw coordinates, run through its standard implementation with no tuning, since it has none (ECOD). Its published standing is that it ranked first in ROC-AUC across 30 ODDS/DAMI datasets, on average 2% above Isolation Forest, with about 5% higher average precision than the next detector. We found no per-dataset ECOD results on Lacuna for ADBench, so we rerun it ourselves. Beating it means a statistically significant rank improvement on the dependency and clustered anomaly types without a loss on global anomalies.

The most important ablation is global PCA followed by our two-sided tail sum, which is the same pipeline with one region. It isolates the local ingredient. If it matches the full method on the multimodal ADBench datasets and the clustered anomaly type, the partitioning is unjustified and we will report that.

The strongest parametric competitor is a mixture of probabilistic PCA models, and alongside it a full-covariance Gaussian mixture, both scored by negative log-likelihood. They get the same number of regions our test selects, plus a separate budget of the same number of likelihood-selected configurations. This tests whether nonparametric tails matter once rotation is fixed.

The strongest competitors that make no independence assumption are Isolation Forest, kNN and LOF on tabular data, and LUNAR on text. NLP-ADBench reports that OpenAI embeddings with LUNAR win on 5 of 8 datasets, reaching 0.9732 AUROC on BBCNews (NLP-ADBench). All detectors receive identical splits, identical preprocessing, and default or equal-size hyperparameter grids, as ADBench advises for unsupervised model selection. On text we count matching LUNAR within one AUROC point at a fraction of its latency as a win, and exceeding it as a strong win.

The last ablation is the stopping rule itself. We replace it with a fixed number of regions chosen by BIC. If the fixed choice is as good, the independence test adds nothing beyond interpretability.

Why not just…?

Why not just run ECOD on globally PCA-rotated data? This is a real threat. On unimodal, linearly correlated data it should capture most of the benefit, and it is the one-region special case of our method. We expect it to fail where a single covariance mixes clusters with different orientations: a minor axis of one cluster becomes a major axis of the pooled data, so broken correlations hide again. The global-PCA ablation, split by ADBench anomaly type and by a label-free measure of multimodality, settles this. We will state openly if the local version wins only on synthetic clustered anomalies.

Why not just fit a Gaussian mixture or a mixture of probabilistic PCA models and use its likelihood? Low-rank mixtures clearly beat full-rank mixtures in high dimension (MPPCA sampling). Their Gaussian tails, though, misjudge heavy-tailed or skewed coordinates, and ECOD's advantage over parametric scores rests on empirical tails. Our matched-region comparison separates the effect of the rotation from the effect of the tail model.

Why not use ICA instead of PCA, since independence is the goal? PCA only removes correlation, not dependence. Independent component analysis targets independence directly but is iterative, sensitive to initialization, and unstable in small regions. We run a per-region ICA variant. The shuffle-discrimination accuracy after each rotation shows directly whether ICA leaves less dependence, and whether that difference changes detection.

Why not just use kNN, LOF, or LUNAR, which assume nothing about independence? They may win on accuracy. Kernel PCA for OOD detection reports kNN needing 20 GiB and running roughly 180 times slower than a projection method on ImageNet-1K, while ECOD reports linear scaling. Our claim is about the accuracy-cost frontier, so we report both axes rather than accuracy alone.

Proposed Experiments

On ADBench's 47 tabular datasets we use its generators for local, global, dependency and clustered anomalies (ADBench). We report ROC-AUC, average precision, fit and score time, and critical-difference ranks, and repeat the anomaly-duplication stress test, under which ADBench reports a −16.43% median drop for unsupervised models. On NLP-ADBench's eight datasets with BERT and OpenAI embeddings, we compare raw, PCA-256, and PPA+PCA inputs across all detectors. This fills the gap that the benchmark never compresses its embeddings.

Three checks decide the question. The first: on dependency anomalies the full method should beat raw ECOD by a wide margin, and on clustered or multimodal data it should beat global PCA-ECOD. If neither happens, the claim is false. The second: across datasets, the leftover discriminator accuracy after global rotation should correlate with the gain from going local. That would make the diagnostic useful by itself as a label-free rule for when to rotate. The third: on text, PPA+PCA compression should leave tail-based detectors no worse and markedly faster. If compression hurts ECOD but not LUNAR, that would be evidence that the dropped low-variance directions carry the anomaly signal, as our scoring rule assumes.