Composable Exact Bounds: A Self-Configuring Hybrid of PCA and Triangle-Inequality Pruning

Exact nearest-neighbor search can be accelerated by cheap lower bounds that prune candidates without computing full distances. Our prior work used bounds from truncated PCA projections, which are tight precisely when variance concentrates in few dimensions. We observe that such bounds are one member of a family: any region that provably contains a set of points yields an exact lower bound via the query-to-region distance, and different region shapes are tight for different data structures. We compose two complementary families—PCA truncation (tight for linearly correlated data) and triangle-inequality ball bounds around k-means centroids (tight for clustered data, and exact for any centers, so approximation quality affects only speed, never correctness)—into a single exact cascade. Because neither family helps on all data, the index configures itself: a three-tier diagnostic measures a sample's eigenvalue decay, detects structure beyond the covariance with two cheap statistics, and settles the question with a measured trial of the real cascade. We report results in hardware-independent work units—full-vector fetches, total bytes touched (charging the pruning machinery itself), and resident RAM per vector—because wall-clock proved regime-dependent: the same algorithm measured 4.7×, 3.6×, 2.7×, and parity under changes of numeric type, machine load, and implementation tuning, while its work counts never moved. On SIFT1M with official queries, the cascade computes full distances for 0.06% of the dataset and keeps 8–40 bytes per vector resident in RAM (versus 512 for a flat scan); on clustered data with a flat eigenvalue spectrum, the ball level prunes to 3% before a single projection is computed (13.9× wall-clock versus 2.1× for PCA alone); on SIFT the ball level's bound work cancels its savings—a verdict the diagnostic correctly predicts from a sample, protecting the practitioner from building a useless level. Exactness is verified against ground truth on every query. All code, diagnostics, and experiments are public.