CRISP: Correlation-Resilient Indexing via Subspace Partitioning

Dimitris Dimitropoulos, Achilleas Michalopoulos, Dimitrios Tsitsigkos, Nikos Mamoulis · 2026

Read CRISP: Correlation-Resilient Indexing via Subspace Partitioning by Dimitris Dimitropoulos, Achilleas Michalopoulos, Dimitrios Tsitsigkos, Nikos Mamoulis (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-05180.txt.

Introduction

Dimitris Dimitropoulos and colleagues introduce CRISP, a framework for approximate nearest-neighbor search in high-dimensional learned representations. Graph methods grow memory-hungry at thousands of dimensions, and other methods carry heavy preprocessing costs. CRISP redistributes variance only when needed through a lightweight correlation-aware strategy, coupled with a compressed sparse row index. Its dual-mode engine offers a Guaranteed Mode preserving recall bounds and an Optimized Mode cutting latency by rank-weighted scoring and early stopping. Tests at up to 4096 dimensions show throughput, low build costs, and memory efficiency.

Catalog record

CREATORDimitris Dimitropoulos, Achilleas Michalopoulos, Dimitrios Tsitsigkos, Nikos Mamoulis
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64040
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.05180

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

CRISP: Correlation-Resilient Indexing via Subspace Partitioning Dimitris Dimitropoulos, Achilleas Michalopoulos, Dimitrios Tsitsigkos, Nikos Mamoulis Abstract . As the dimensionality of modern learned representations increases to thousands of dimensions, the state-of-the-art Approximate Nearest Neighbor (ANN) indices exhibit severe limitations. Graph-based methods (e.g., HNSW) suffer from prohibitive memory consumption and routing degradation, while recent randomized quantization and learned rotation approaches (e.g., RaBitQ, OPQ) impose significant O ⁡ ( N ​ D 2 ) O(ND^{2}) preprocessing overheads. We introduce CRISP, a novel framework designed for ANN search in very-high-dimensional spaces. Unlike rigid pipelines that apply expensive orthogonal rotations indiscriminately, CRISP employs a lightweight, correlation-aware adaptive strategy that redistributes variance only when necessary, effectively reducing the preprocessing complexity. We couple this adaptive mechanism with a cache-coherent Compressed Sparse Row (CSR) index structure. Furthermore, CRISP incorporates a multi-stage dual-mode query engine: a Guaranteed Mode that preserves rigorous theoretical lower bounds on recall, and an Optimized Mode that leverages rank-based weighted scoring and early termination to reduce query latency. Extensive evaluation on datasets of very high dimensionality (up to D = 4096 D=4096 ) demonstrates that CRISP achieves state-of-the-art query throughput, low construction costs, and peak memory efficiency. † † authors: . PVLDB Reference Format: PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/dabouledidia/CRISP . 1. Introduction Approximate Nearest Neighbor (ANN) search in a high-dimensional space is a core component of modern data systems, supporting applications ranging from content-based image retrieval to retrieval-augmented generation (RAG) for Large Language Models (LLMs). While recent indexing approaches for ANN search are highly effective for medium-to-high dimensional data (e.g., D\leq 256 ), scaling these indices to higher dimensions remains a significant challenge. Modern foundation models typically output vectors with very high dimensionalities, such as OpenAI’s text embeddings ( D=3072 ) or domain-specific descriptors like Trevi ( D=4096 ). Scaling vector databases to manage such vectors breaks the performance trade-offs of existing ANN algorithms ( 26 ; 25 ) . In particular, graph-based methods, such as HNSW ( 22 ) , which currently dominate industry deployments due to their high query throughput, in very-high-dimensional regimes ( D\geq 600 ) require substantial memory to store adjacency lists alongside the raw vectors, exhibit slow sequential index construction, and often have degraded routing efficiency on complex data distributions ( 31 ; 36 ) . To address memory limitations, recent research has pivoted toward methods based on subspace partitioning ( 34 ; 5 ; 4 ) and quantization ( 10 ; 16 ; 11 ; 23 ) . Unlike graph methods, these approaches offer compact memory footprints through inverted index structures that scale linearly with dataset size and cache-efficient linear access patterns. Two prominent examples are SuCo (Subspace Collision) ( 34 ) and RaBitQ (Randomized Bit Quantization) ( 10 ) . Nevertheless, applying these methods to thousands of dimensions reveals two practical limitations: they either struggle to process highly correlated features effectively, or their preprocessing costs are too high. SuCo’s framework ( 34 ) assumes that the dimensions carry independent information, but real-world high-dimensional embeddings often violate this assumption. In correlated feature spaces (e.g., Gist and Fashion-MNIST), variance concentrates heavily in a small fraction of dimensions, causing subspaces to capture largely redundant information and rendering the collision proxy unable to discriminate between neighbors. This effect is illustrated in our evaluation (Figure 5 ), where retrieval quality of SuCo exhibits a clear recall ceiling on correlated datasets. To handle highly correlated feature spaces, Optimized Product Quantization (OPQ) ( 11 ) and recent randomized quantization frameworks like RaBitQ ( 10 ) apply global orthogonal rotations to redistribute variance across all dimensions. While effective, this transformation requires O(ND^{2}) time for N vectors of dimensionality D . This quadratic complexity to D creates a significant preprocessing overhead for modern representation-learning models which produce embeddings with thousands of dimensions. Since RaBitQ applies this transformation indiscriminately to all datasets, the O(ND^{2}) overhead is paid even on naturally uncorrelated data where the original distribution is already suitable for indexing. Figure 1 . Overview of the CRISP Architecture. In this paper, we argue that a one-size-fits-all preprocessing pipeline is fundamentally incompatible with the demands of very-high-dimensional ANN search. We propose CRISP, an adaptive framework designed for feature spaces of very high dimensionality that dynamically adjusts its preprocessing strategy based on the correlation structure of the data, achieving robust retrieval, while whenever unnecessary bypassing the O(ND^{2}) preprocessing cost. CRISP’s architecture is described in Figure 1 . In its preprocessing phase, CRISP employs a lightweight heuristic that analyzes data correlation to decide the necessity of variance redistribution. CRISP fundamentally bridges two complementary paradigms: it inherits the low indexing cost of collision-based methods ( 34 ) and the distributional robustness of quantization approaches ( 10 ) . After applying the rotation decision mechanism and potentially applying rotation, CRISP partitions the feature space into M disjoint subspaces. Within each subspace, we employ an Inverted Multi-Index (IMI) partitioning scheme by decomposing the subspace into lower-dimensional segments and performing independent k-means clustering on each to create a fine-grained grid of cells. This approach builds on the subspace collision paradigm introduced by SuCo as a proxy for Euclidean distance, while introducing optimizations specifically tailored for the high-dimensional and correlated distributions where existing indices fail to scale. We couple the subspace partitioning structure with a highly optimized system architecture designed to maximize cache efficiency and instruction-level parallelism. We introduce a cache-coherent Compressed Sparse Row (CSR) index structure for each subspace, replacing the pointer-chasing overhead of traditional hash-based inverted lists with sequential memory access patterns. In our implementation, all point IDs for a given subspace are stored in a single contiguous array, while a secondary offsets array explicitly marks the start and end of each partition bucket. This design significantly reduces Translation Lookaside Buffer (TLB) misses during the candidate voting and collision counting phase, where the system must rapidly retrieve and aggregate point IDs from activated buckets. By linearizing the index, hardware prefetchers can stream bucket contents efficiently into cache, resulting in substantial query speedups in very-high-dimensional regimes. To maximize query efficiency, we design a multi-stage query pipeline that progressively filters the dataset into a candidate set. The process begins by applying subspace collision counting to retrieve the set of points most likely to contain the true nearest neighbors. We then apply dual-mode verification to these filtered candidates. In Guaranteed Mode, the system performs exhaustive exact Euclidean verification on the candidate set, preserving rigorous theoretical lower bounds on recall derived from subspace collision statistics. In Optimized Mode, we prioritize throughput by introducing a rank-based weighted scoring mechanism. This refines the coarse collision counting used in SuCo into a distance-aware ranking by assigning higher importance to collisions occurring in proximal subspaces. This mode further accelerates queries through Hamming distance re-ranking, ADSampling, and a dynamic patience termination mechanism. Our

Read the complete text