CS-PQ: Cache-Friendly SIMD Product Quantization for Large-Scale ANNS Index Construction

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

CS-PQ: Cache-Friendly SIMD Product Quantization for Large-Scale ANNS Index Construction

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

databases datamanagement sql storage

databases, sql, data management, storage

arXiv:2605.25521v1 [cs.DB] 25 May 2026

CS-PQ: Cache-Friendly SIMD Product Quantization for Large-Scale ANNS Index Construction Yutang MA

Kecheng HUANG

Xikun JIANG

The Chinese University of Hong Kong [email protected]

Beijing Institute of Technology, Zhuhai [email protected]

The Chinese University of Hong Kong [email protected]

Meiling WANG

Xin YAO

Renhai CHEN

Huawei Technologies Co., Ltd. [email protected]

Gong ZHANG

Zili SHAO

Huawei Technologies Co., Ltd. [email protected]

The Chinese University of Hong Kong [email protected]

ABSTRACT

Product Quantization (PQ) construction is deeply integrated into vector index construction for Approximate Nearest Neighbor Search (ANNS). The rapid growth in vector dimensionality and volume has significantly increased the computational cost of PQ. Existing GPU-based PQ accelerations are ill-suited for PQ construction due to its “one-to-one” execution pattern (one compute, one data load, i.e., data transfer overhead dominates). Although CPU-based solutions are prevalent, they are essentially general-purpose designs that fail to capture the intrinsic characteristics of PQ construction. In this paper, we propose CS-PQ, a Cache-friendly, SIMD-optimized PQ framework based on modern CPUs. CS-PQ introduces a vectororiented SIMD paradigm that decouples quantization granularity from SIMD width by vectorizing across PQ centroids rather than subvector dimensions. It further restructures the execution pipeline to improve cache locality and reformulates PQ computation to eliminate redundant operations while preserving correctness. Experiments on large-scale datasets show that CS-PQ achieves up to 10.7× speedup over state-of-the-art CPU-based PQ implementations without sacrificing ANNS accuracy.

Approximate nearest neighbor search (ANNS) [9, 10, 12, 50] has become a core primitive in modern data management systems [47, 48] and is widely used in applications such as vector databases [27, 36, 37, 49], information retrieval [11, 14, 55], recommendation systems [24, 42, 51], and large-scale machine learning pipelines [17, 33, 41, 45]. In modern ANNS systems, Product Quantization (PQ) is deeply integrated into index construction to support vector searches towards large-scale vector data [8, 19, 29, 35]. In recent years, advances in representation learning have led to a steady increase in vector dimensionality, with embeddings often reaching hundreds or even thousands of dimensions [13, 15, 44]. At the same time, the number of vectors managed by ANNS systems continues to grow rapidly, with existing practices already operating at the scale of hundreds of millions or billions of vectors [27, 49]. As a result, the computational cost of PQ during index construction has increased substantially. In addition, many real-world systems must handle continuous or frequent data insertion due to streaming inputs, model retraining, or dataset updates. Under these workloads, PQ is no longer performed only once during offline preprocessing, but is repeatedly executed during dynamic insertion, making its efficiency an important factor in large-scale ANNS index construction. Intuitively, leveraging GPUs is a natural choice to enhance the computational efficiency of PQ construction [12, 31, 54]. However, prior research has shown that while GPUs can accelerate PQ-based distance computations during query processing, they do not deliver the same advantages during index construction. Specifically, GPUs excel in the “many-to-one” computation pattern, where dense computations are performed with minimized data transfers and kernel invocations. This aligns well with the query processing phase, where a batch of PQ-encoded vectors is loaded onto the GPU for repeated distance calculations, returning only the top candidate to the host for subsequent traversal. In contrast, PQ applied during index construction follows a different “one-to-one” pattern. PQ is performed once per vector [27, 49], meaning that for each PQ operation, the GPU receives a single high-dimensional vector, performs a one-time computation, and returns one encoded (compressed) vector to the host. Consequently, the overhead associated

PVLDB Reference Format: Yutang MA, Kecheng HUANG, Xikun JIANG, Meiling WANG, Xin YAO, Renhai CHEN, Gong ZHANG, and Zili SHAO. CS-PQ: Cache-Friendly SIMD Product Quantization for Large-Scale ANNS Index Construction. PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/codinghardwear/CS-PQ.

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

INTRODUCTION

that setting 𝑑/𝑚 ≤ 8 provides competitive ANNS accuracy while it is still far less than the SIMD register width provided by modern CPUs. Essentially, the mismatch between compression units (𝑑/𝑚) and compute lanes (width) introduces an unwanted dependency between computational efficiency and quantization quality. Issue ♯2: Asymmetric behaviors between subspace and codebook. This subspace-oriented execution model not only affects the computation efficiency, but also introduces redundant intermediate results that are repeatedly moved between CPU cache and main memory, which further degrades the PQ efficiency. As shown in Figure 1(c), taking PQ code generation as an example, to better utilize the SIMD parallelism, contemporary SIMD optimizations, represented by FAISS CPU implementation [15] and Intel MKL-based vectorized distance kernels [26], arrange all subvectors residing in the subspace into a matrix and then perform distance calculations between the matrix and the codebook. Although this model is proven efficient in various domains such as dense linear algebra [22] and batched nearest neighbor search [31, 54], it fails to grasp the workload characteristics of PQ construction. The matrix processing in PQ construction is inherently asymmetric: the subspace matrix is huge since billions of vectors may be processed at a time, while the codebook is relatively small (e.g., only 256 centroids involved). Moreover, the codebook is frequently reused during computation as each subvector needs to compare with all centroids in the codebook. Intermediate results generated by this matrix processing can easily pollute the CPU cache and trigger frequent eviction and reloading for the codebook. These long-latency codebook movements result in SIMD waits, further prolonging the PQ construction time. Issue ♯3: Neglecting the ranking nature of PQ construction. By further investigating these intermediate results, we observe that a significant portion is redundant and contributes nothing to PQ results. Unfortunately, these redundant results and their associated computations remain largely neglected. PQ is inherently ranking-oriented, but this feature is not favored by common SIMD optimizations. The best match (i.e., relative distance) is sufficient for both codebook generation and PQ code generation, while absolute distance calculations, with additional overhead, are performed in common practice. Specifically, state-of-the-art (SOTA) SIMD optimizations treat this best match demand as an absolute distance calculation problem, explicitly computing complete distance expressions for each subvector against all centroids [15]. In Figure 1(d), to determine the best match (i.e., closest) centroid for subvector v1 , a common practice is to perform absolute distance calculations for v1 and all centroids. However, during these calculations, ∥v1 ∥ 2 is explicitly redundant and would not affect the final choice. Moreover, ∥c1 ∥ 2, ∥c2 ∥ 2, . . . can be precomputed and reused for not only the current subvector but also other subvectors. These extra arithmetic operations do not change the final selection but increase PQ construction cost in terms of cache pressure and redundant computation.

Figure 1: An Overview of PQ execution and its inefficiencies. with transferring these high-dimensional vectors to GPU memory and then returning the resulting encoded representations to host memory becomes the dominant factor. Recognizing the data transfer inefficiencies of GPU-based acceleration, contemporary ANNS systems increasingly favor CPU-based PQ during index construction. The objective of PQ is to reduce vector dimensions from 𝑑 to 𝑚 (𝑚 ≪ 𝑑) by dividing the original vector into 𝑚 subvectors, with each subvector retaining one dimension (i.e., a PQ code). To achieve this, CPU-based PQ treats subvectors with identical dimensionality as a subspace, and encodes the subvectors into PQ codes based on a per-subspace codebook. To generate the codebook, the K-means algorithm is widely adopted, which clusters subvectors and produces centroids (e.g., c1 ). To generate the PQ code for each subvector, distance calculations are performed to find the closest centroid from the codebook (e.g., assigning PQ code 2 to compressed vector v1′ ’s subvector based on centroid c2 ). This procedure repeats until the entire vector is encoded.

1.1

Critical Issues

Although opening a door for CPU-based PQ, this execution model is essentially a general-purpose approach, not tailored for workload characteristics of PQ on large-scale, high-dimensional datasets. Simply adopting this model still induces ultra-long time consumption for PQ. We analyze three critical issues as follows. Issue ♯1: Dilemma between PQ efficiency and generation quality. The subvector-oriented execution model poses an unexpected constraint on computation efficiency. In Figure 1(a), PQ construction, including both codebook generation and PQ code generation, is performed by feeding each subvector into SIMD registers for parallel distance calculation. As each subvector involves 𝑑/𝑚 dimensions, the SIMD is leveraged in a single-instruction (i.e., distance calculation), multiple-data (i.e., 𝑑/𝑚 dimensions) manner. This execution model encounters a tough dilemma between PQ efficiency and generation quality. Specifically, existing SIMD, represented by AVX-512, provides 512-bit width of registers for parallel processing [25]. Ideally, the perfect utilization of SIMD is to set 𝑑/𝑚 equal to this width. However, although increasing 𝑑/𝑚 to match this width contributes to better SIMD efficiency, it results in poor accuracy for future ANNS tasks as fewer PQ codes are produced after PQ compression (Figure 1(b)). Preliminary experiments indicate

1.2

Our Solution

In this paper, we revisit the design of CPU-based PQ for large-scale ANNS index construction and address the aforementioned challenges through a system-level redesign. To this end, we propose CSPQ, a Cache-friendly and SIMD-optimized Product Quantization framework that decouples the subspace-oriented PQ model from 2

large-scale machine learning pipelines [17, 33, 41, 45]. To support efficient similarity search over high-dimensional and large-scale vector data, SOTA ANNS systems rely on carefully designed index structures that balance search accuracy, memory footprint, and index construction cost [6, 39, 40, 43]. The ANNS index construction comprises three components. First, the input vector corpus is organized into a topological index structure, commonly a proximity graph, to facilitate efficient candidate set exploration during vector search processing [16, 23, 38]. Second, to optimize retrieval efficiency, vector data are compressed (e.g., via product quantization or its variants) and then preserved in-memory for instant retrieval; this reduces per-vector footprint while enhancing cache locality and throughput [8, 19, 29, 35]. Third, auxiliary metadata structures, including neighbor lists, centroid assignments, and graph connectivity information, are synthesized to accelerate distance calculation, guide index traversal, and enable dynamic insertions or deletions [40, 46]. Among these subsystems, vector compression is a critical scalability enabler. As vector dimensionalities scale and corpus sizes reach hundreds of millions to billions of vectors, storing uncompressed floating-point representations becomes prohibitive, which often exceed feasible DRAM budgets by an order of magnitude. Consequently, modern ANNS systems integrate quantization within the index construction pipeline, trading marginal accuracy loss for substantial memory footprint reduction and improved memory subsystem efficiency. This design choice is not merely optional but architecturally necessary to achieve sub-linear vector search latency at wide-scale vector volumes. Product Quantization (PQ) is a foundational vector compression technique widely deployed in large-scale ANNS systems, which compresses each vector by quantizing its subspaces. To achieve this, PQ represents a 𝑑-dimensional vector by partitioning it into 𝑚 disjoint subvectors and independently quantizing each subvector into several bits through a dedicated codebook. Formally, given a 𝑑-dimensional input vector v𝑖 ∈ R𝑑 , it is partitioned as 𝑚 independent subvectors v𝑖(1) , v𝑖(2) , . . . , v𝑖(𝑚) , and we have:

Figure 2: Illustration of the PQ workflow. SIMD execution constraints, mitigates cache pollution and redundant data movement, and thus improves end-to-end PQ construction performance. Rather than adhering to the conventional matrixoriented SIMD design, we introduce a new design paradigm termed a PQ-favored, vector-oriented SIMD (pvSIMD) computation pipeline. This paradigm better aligns with the intrinsic properties of PQ workloads, enabling effective SIMD parallelization without imposing algorithmic compromises on PQ construction. Furthermore, we propose a PQ-oriented computation pipeline to enhance SIMD utilization on modern CPUs. Rather than mapping SIMD lanes to subvector dimensions, we organize data and computation to enable vectorized processing across multiple centroids. Partial distance results are accumulated and compared directly in registers, avoiding horizontal reductions over low-dimensional subvectors and preventing the materialization of full distance tables in memory. This design improves effective SIMD utilization and reduces instruction overhead, which is particularly important for PQ workloads with low arithmetic intensity. We restructure the execution organization of PQ construction to improve cache locality. By reducing the active working set during construction, the large-volume, short-lived intermediate results can be eliminated. Our vectorized processing model enables aligning PQ execution order with data reuse patterns. As a result, frequently reused centroid data can remain resident in cache across continuous PQ operations, while input vectors are isolated and streamed through the CPU cache. This cache-friendly execution can significantly reduce memory traffic and mitigate cache eviction effects during bulk PQ processing. We also reformulate the computational paradigm of PQ construction to match its ranking-oriented nature. This reformulation mitigates the arithmetic operations performed per subvector while guaranteeing that the resulting encoding decisions are identical to those produced by the original formulation. We have developed a full-featured prototype to evaluate the effectiveness of CS-PQ, and conduct comprehensive experiments on multiple large-scale datasets spanning different vector dimensionalities. Experimental results show that compared to SOTA CPU-based PQ construction approaches, CS-PQ speeds up PQ construction by up to 10.7× without degrading ANNS accuracy.

v𝑖 = [v𝑖(1) , v𝑖(2) , . . . , v𝑖(𝑚) ]

(1)

where each subvector v𝑖( 𝑗 ) ∈ R𝑑/𝑚 . For all to-be-compressed 𝑑dimensional vectors v1, v2, . . . , v𝑖 , . . . , they can also be partitioned following the same partitioning rule. Then we define 𝑚 subspaces 𝑠𝑝 (1) , 𝑠𝑝 (2) , . . . , 𝑠𝑝 (𝑚) where each 𝑠𝑝 ( 𝑗 ) represents all subvectors v1( 𝑗 ) , v2( 𝑗 ) , . . . residing in the same subspace. For each subspace 𝑠𝑝 ( 𝑗 ) , a dedicated codebook C ( 𝑗 ) is learned using clustering algorithms such as 𝑘-means. C ( 𝑗 ) = {c1( 𝑗 ) , c2( 𝑗 ) , . . . , c𝑘( 𝑗 ) }

(2)

In this equation, each codebook C ( 𝑗 ) contains 𝑘 codes, corresponding to 𝑘 centroids obtained by clustering subvectors within this subspace into 𝑘 groups. For v𝑖( 𝑗 ) , which is originally a 𝑑/𝑚-dimensional subvector, it can be represented by its closest centroid inside C ( 𝑗 ) . This processing is termed encoding. Specifically, during encoding, each subvector v𝑖( 𝑗 ) is assigned to its nearest centroid based on distance calculations. We use the centroid index 𝑧𝑖( 𝑗 ) to represent

2 BACKGROUND 2.1 ANNS Index Construction and PQ Approximate nearest neighbor search (ANNS) [9, 10, 12, 50] is a core primitive in modern data management systems [18, 32, 52] and is widely used in vector databases [9, 10, 50], recommendation systems [24, 42, 51], information retrieval [11, 14, 55], and 3

the centroid in the codebook C ( 𝑗 ) we select to represent v𝑖( 𝑗 ) . 𝑧𝑖( 𝑗 ) = arg min v𝑖( 𝑗 ) − cℓ( 𝑗 )

of subspaces and codebooks, materializes intermediate results in matrix form, and relies on dimension-wise SIMD parallelism over the 𝑑/𝑚 dimensions. As introduced in Section 1, these critical issues fundamentally constrain the performance and scalability of CPU-based PQ. In the subsequent section, we conduct a rigorous micro-architectural analysis of CPU-based PQ designs, identifying three critical inefficiencies that hinder scalability: (i) suboptimal SIMD instruction utilization due to misaligned memory access patterns; (ii) excessive cache pollution induced by non-contiguous traversal of highdimensional vectors across subspaces; and (iii) redundant arithmetic operations arising from unoptimized centroid assignment logic.

(3)

ℓ ∈ [1,𝑘 ]

The same encoding processing can be performed for all subspaces based on their dedicated codebooks. The final PQ representation of v𝑖 is the concatenation of centroid indices. PQ(v𝑖 ) = 𝑧𝑖(1) , 𝑧𝑖(2) , . . . , 𝑧𝑖(𝑚) . (4) During PQ construction, Equation 3 is applied independently to every vector in the dataset. Since PQ operates over all vectors and all 𝑚 subspaces, the total computational cost scales linearly with both dataset size and vector dimensionality 𝑑, making PQ construction a dominant factor in large-scale ANNS index construction.

2.2

3 MOTIVATION 3.1 PQ Construction Shifts the Cost Balance

GPU Acceleration and CPU-Based PQ

GPU acceleration has been extensively investigated to optimize PQ construction, yet its efficacy is highly phase-dependent [31, 54]. Specifically, during vector search processing, GPUs deliver substantial throughput gains: as codebooks and to-be-searched vector codes can be preserved in GPU memory, these asymmetric distance computations across large query batches exhibit high arithmetic intensity and data reuse, enabling efficient utilization of GPU parallelism and memory bandwidth. Because each query code is decomposed into subspace codes that repeatedly access the same small codebook centroids, multiple distance lookups can reuse the resident codebook in parallel across thousands of threads, amortizing memory access costs. In contrast, PQ during index construction presents a fundamentally distinct computational regime. Each highdimensional vector undergoes a one-time quantization with minimal cross-vector data reuse, resulting in a memory-bound, latencysensitive workload. During PQ construction, every input vector must be sequentially partitioned into subvectors and compared against its corresponding subspace codebook only once, with little opportunity to reuse loaded vector data across different inputs, thereby limiting arithmetic intensity and cache locality. Critically, the uncompressed input vectors typically reside in host memory, necessitating per-vector PCIe transfers to the device. For billion-scale datasets, the cumulative overhead of host–device data movement, coupled with GPU kernel launch latency and limited GPU memory occupancy due to irregular memory access patterns, often dominates the PQ construction time. Consequently, the benefits that make GPUs effective at query time fail to materialize during construction, rendering GPU offloading suboptimal. Consequently, most contemporary ANNS systems rely on CPUbased PQ during index construction. On CPUs, PQ construction is commonly organized as a subspace-oriented, matrix-style distance computation process. Specifically, for each subspace 𝑠𝑝 ( 𝑗 ) , distances between a batch of subvectors (v1( 𝑗 ) , v2( 𝑗 ) , . . . ) and all centroids in C ( 𝑗 ) are computed in a matrix-like formulation. This design resembles dense linear algebra operations and enables the reuse of SIMDbased CPU optimizations developed for general-purpose matrix workloads [22]. However, although this matrix-style abstraction provides a uniform and predictable execution model, it is inherently general-purpose and not specifically tailored to the workload characteristics of PQ construction over high-dimensional, largescale vector datasets. In particular, it assumes symmetric treatment

Modern ANNS systems increasingly operate under compressionsensitive regimes driven by the interaction between dataset scale and accuracy requirements. As data scale grows, the quality of distance approximation provided by Product Quantization becomes a dominant factor in search efficiency. Using larger PQ code sizes preserves finer-grained information of the original vectors, which directly reduces the search effort required to achieve a target recall. As a result, large-scale workloads naturally favor high-precision PQ configurations, corresponding to larger PQ code sizes. This trend is reflected in practical performance measurements. We perform a preliminary evaluation to exhibit the sensitive coupling of search quality and PQ overheads. The detailed experimental setups can be found in Section 5. As illustrated in Figure 3, we first profile index construction time across increasing PQ code size (i.e., total bits per vector, 𝑚 · 𝑏 where 𝑏 denotes the bit size per subspace, more centroids per subspace necessitate a larger 𝑏). Two clear trends emerge: First, PQ construction time increases significantly with code size due to the growth in per-subspace distance computations. Specifically, increasing 𝑚 increases the number of subspaces, while increasing 𝑏 expands the centroid cardinality (2𝑏 ), both of which enlarge the total number of distance computations. Second, beyond a critical code size threshold (approximately 64–96 bits per vector in our evaluation), PQ construction transitions from a secondary overhead to the dominant factor, constituting over 70% of total construction time. This underscores PQ construction as the primary scalability bottleneck in large-scale index construction pipelines and motivates the need for architecture-aware acceleration of the quantization kernel. We also evaluate vector search throughput at a fixed accuracy target (Recall@10 = 0.95) across varying PQ code sizes. As depicted, throughput increases substantially with code size up to a moderate configuration (e.g., 240 bytes): higher-bit representations reduce quantization error, thereby decreasing the false positive rate during candidate retrieval. This, in turn, minimizes unnecessary candidate expansion and exact distance re-ranking overhead (i.e., two dominant costs in graph-based ANNS pipelines). Consequently, these reductions directly translate to higher vector search throughput. Furthermore, scaling the corpus size from 1M to 10M vectors induces a pronounced throughput degradation. Critically, this degradation is most severe under aggressive quantization (small code sizes), where elevated false positive rates compound memory access 4

PQ Non-PQ

1200 800 400 0

120

240

480

Throughput

624

360

676

630

600 450

390

300 201 150

PQ Code Size (bytes)

120

240

480

Throughput (Queries/s)

750 Throughput (Queries/s)

Construction Time (s)

1600

340

Throughput 312

320

279

280

254

240 200

PQ Code Size (bytes)

241

Dataset Size (Million Vectors)

Figure 3: Experimental results related to the sensitive coupling of search quality and PQ overheads. substantially below the threshold required to saturate modern CPU SIMD units. Empirical profiling reveals sustained SIMD utilization below 45% in conventional implementations [27], as short inner loops over small subspaces fail to amortize instruction-level overhead and memory-bound stalls dominate execution. Under these memory-bound conditions, scaling compute resources alone (e.g., through wider vector units or deeper pipeline parallelism) yields diminishing returns. • Poor cache locality. Although PQ codebooks themselves are compact (KBs to several MBs) and exhibit high reuse potential across millions of vectors, conventional PQ construction implementations suffer from suboptimal cache utilization. Specifically, these approaches materialize full intermediate distance matrices (of size 𝑚 × 𝑘 per vector) prior to centroid selection. This design inflates the active working set far beyond the intrinsic codebook footprint, introducing substantial pressure on the cache hierarchy. Consequently, despite the theoretical potential for codebook residency in L2/L3 caches, the expanded memory footprint displaces frequently accessed codebook entries, increasing cache miss rates and forcing repeated DRAM accesses for centroid data. Our preliminary experiment reveals that codebook reuse distance exceeds L3 capacity under typical batch sizes, directly translating to increased memory traffic and stalled execution units. • Ranking objective mismatch. During PQ construction, centroid assignment within each subspace reduces to a nearest-centroid search problem: for a subvector v𝑖( 𝑗 ) ∈ R𝑑/𝑚 , the objective is to identify the centroid cℓ( 𝑗 ) ∈ C ( 𝑗 ) minimizing distance ∥v𝑖( 𝑗 ) − cℓ( 𝑗 ) ∥ 2 . Conventional implementations compute the full squared distance expression for every candidate centroid: D E 2 2 2 v𝑖( 𝑗 ) − cℓ( 𝑗 ) = v𝑖( 𝑗 ) − 2 v𝑖( 𝑗 ) , cℓ( 𝑗 ) + cℓ( 𝑗 ) (5)

Figure 4: Execution breakdown of baseline PQ construction. costs. Investing in higher-fidelity PQ representations yields desired gains in search efficiency at scale. These results demonstrate that PQ code size is tightly coupled with the recall-efficiency trade-off. Large-scale ANNS deployments simultaneously face increasing vector dimensionality and rapidly growing data volumes. Under such scenarios, tuning search-time parameters alone is often insufficient to compensate for short PQ codes without incurring prohibitive latency or recall degradation. Consequently, practical systems are increasingly pushed toward operating vectors with larger PQ code sizes in order to sustain high recall and throughput at scale.

3.2

Limitations of Existing PQ Construction

Figure 4 presents the execution breakdown of CPU-based PQ construction time 1 . The construction cost is decomposed into memory accesses, arithmetic operations, and other overhead. Across different datasets, memory-related costs account for the largest fraction of execution time, while arithmetic operations contribute a smaller portion. These results indicate that PQ construction exhibits memory-sensitive execution behavior on modern CPUs. From an algorithmic perspective, PQ construction evaluates distances between each subvector and a set of codebook centroids, which suggests a computation-dominated workload. However, the profiling results show that the practical execution cost is largely driven by the memory overheads. This discrepancy reflects a mismatch between the abstract computation structure of PQ construction and its realized execution behavior under current formulations. • Sub-optimal SIMD efficiency. PQ construction exhibits intrinsically low arithmetic intensity due to its operational characteristics during index construction. Each high-dimensional vector is partitioned into low-dimensional subvectors (typically 8–16 dimensions per subspace), and each subvector undergoes a single nearest-centroid assignment against its dedicated codebook. This workflow entails minimal computation per memory access: for a subvector of dimensionality 𝑑/𝑚 and a codebook of size 𝑘, only O (𝑑/𝑚 · 𝑘) floating-point operations are performed per subvector, while the entire uncompressed vector must be loaded from memory. Crucially, intermediate results, such as partial distance computations across subspaces, exhibit negligible cross-vector reuse due to the independence of quantization across vectors and subspaces. Consequently, the ratio of computation to data movement remains

𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡

v𝑖( 𝑗 )

𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑-𝑑𝑒𝑝𝑒𝑛𝑑𝑒𝑛𝑡

the term is invariant across all centroid comparisons within a subspace and therefore does not influence the argmin decision. Nevertheless, standard formulations redundantly evaluate this term per subvector, introducing O (𝑑/𝑚) superfluous floating-point operations that contribute neither to the encoding outcome nor to numerical stability. This arithmetic redundancy inflates instruction counts by up to 40% in typical configurations (𝑘 = 256), directly degrading instruction-level parallelism and exacerbating the memory-bound nature of the kernel without improving accuracy. 2

In addition, for the centroid-dependent term cℓ( 𝑗 ) , it can be computed once and reused multiple times for all subvectors residing in this subspace. However, it is repeatedly computed in existing practices.

1 To distinguish between the distinct use cases of PQ, we use the term PQ construction

in this paper referring to PQ during index construction. 5

tables in memory, which is critical for PQ construction workloads with low arithmetic intensity and limited data reuse. ② Cache-friendly execution organization. The second component organizes PQ construction execution in a cache-friendly, streaming manner. Within each PQ chunk, subvectors from a block of input vectors are processed sequentially, while distance computations are performed on the fly. This execution organization minimizes the active working set of distance accumulators and codebook accesses, allowing codebooks to remain resident in cache during bulk PQ processing and markedly reducing memory traffic. ③ Ranking-oriented distance reformulation. The third component reformulates distance computation to better align with the ranking-oriented nature of PQ. PQ construction only requires identifying the nearest centroid for each subvector, and therefore depends solely on the relative ordering of distances rather than their absolute values. Based on this observation, we eliminate ranking-invariant terms in the distance formulation. The reformulated distance preserves the exact centroid ranking and produces identical PQ codes as the original formulation, while reducing redundant arithmetic operations and enabling more efficient downstream execution.

Figure 5: Design overview of CS-PQ. Design challenges. Addressing these inefficiencies necessitates a holistic co-design spanning algorithmic reformulation, data layout optimization, and instruction-level scheduling, rather than isolated micro-optimizations. Specifically, we aim to orchestrate finegrained vectorization that achieves high occupancy despite minimal per-element computation; restructure memory access patterns to enforce codebook residency within private caches; and eliminate ranking-irrelevant computations through algebraic simplification. This multi-directional optimization requirement directly motivates our PQ construction framework introduced in the following section, which jointly addresses parallelism, memory, and arithmetic bottlenecks while preserving bit-identical encoding semantics.

Algorithm 1: Centroid-Parallel SIMD Computation Input: Subvector v𝑖( 𝑗 ) ∈ R𝑑/𝑚 ; transposed codebook C ( 𝑗 )⊤ ∈ R (𝑑/𝑚) ×𝑘 ; bias terms b ( 𝑗 ) ∈ R𝑘 where bℓ( 𝑗 ) = 12 ∥cℓ( 𝑗 ) ∥ 2 ; SIMD width 𝑤. Output: PQ code index 𝑧𝑖( 𝑗 ) ∈ [1, 𝑘].

4 DESIGN 4.1 Design Overview

This section introduces Cache-friendly SIMD-optimized Product Quantization (CS-PQ), a CPU-centric PQ construction framework to overcome the memory-bound bottlenecks of large-scale ANNS index construction. Our design co-optimizes algorithmic formulation and execution semantics to exploit three intrinsic properties of PQ construction workloads: (1) fine-grained data parallelism across low-dimensional subspaces to fully utilize SIMD-granted parallelism; (2) high reuse of compact codebooks across millions of vectors; and (3) ranking-oriented computation where only centroid ordering determines output. To achieve this, rather than processing vectors sequentially or as a monolithic matrix, CS-PQ operates on PQ chunks. Specifically, similar to the conventional approaches, each vector is partitioned into 𝑚 disjoint subvectors (PQ chunks). The key difference is rather than constructing PQ over a single matrix containing all PQ chunks, CS-PQ proceeds ”subspace-bysubspace” with strict cache-conscious scheduling: for subspace 𝑠𝑝 (𝑘 ) , all subvectors are quantized against codebook C (𝑘 ) before advancing to 𝑠𝑝 (𝑘+1) . This strided execution pattern ensures that each codebook C (𝑘 ) remains resident in L2/L3 cache throughout its reuse window, eliminating redundant DRAM fetches. For each PQ chunk, we introduce a new design paradigm termed a PQ-favored, vector-oriented SIMD (pvSIMD) computation pipeline as follows: ① Centroid-parallel SIMD computation. The first component performs distance computation using SIMD instructions in a centroidparallel manner, where multiple centroids are evaluated concurrently for each subvector. We reorganize the codebook layout to enable contiguous, vectorized access across centroids, and accumulate partial distance results directly in SIMD registers. This design improves SIMD utilization and avoids materializing full distance

2 3 4

best_score ← +∞ best_idx ← 1 for ℓ ← 1 to 𝑘 step 𝑤 do acc ← VecZero(𝑤)

5 6 7

for 𝑡 ← 1 to 𝑑/𝑚 do

x ← VecLoad C ( 𝑗 )⊤ [𝑡] [ℓ : ℓ + 𝑤 − 1] vt ← VecBroadcast v𝑖( 𝑗 ) [𝑡]

acc ← FMA(x, vt, acc) end bias ← VecLoad b ( 𝑗 ) [ℓ : ℓ + 𝑤 − 1]

score ← bias − acc

8 9

(blk_min, blk_arg) ← VecArgMin(score) if blk_min < best_score or (blk_min = best_score ∧ ℓ + blk_arg < best_idx) then 14 best_score ← blk_min 15 best_idx ← ℓ + blk_arg 16 end 17 end 18 return best_idx 12 13

4.2

Centroid-Parallel SIMD Computation

In this section, we describe a centroid-parallel SIMD computation scheme that exploits this structure to improve arithmetic efficiency and reduce per-subvector instruction overhead. 6

As defined in Equation 3, for each subspace 𝑠𝑝 ( 𝑗 ) and each subvector v𝑖( 𝑗 ) ∈ R𝑑/𝑚 , PQ construction requires evaluating its squared Euclidean distance to all centroids in the corresponding codebook C ( 𝑗 ) = {c1( 𝑗 ) , . . . , c𝑘( 𝑗 ) }:

𝑧𝑖( 𝑗 ) = arg min v𝑖( 𝑗 ) − cℓ( 𝑗 )

Discussion. Centroid-parallel SIMD computation restructures PQ construction to better match low-dimensional, one-pass workloads. By avoiding horizontal reductions and performing accumulation entirely in registers, the computation reduces instruction overhead and improves SIMD utilization. Equally importantly, this register-resident execution style produces a compact intermediate state, which enables higher-level execution organization to explicitly control cache behavior, as described in Section 4.3. Algorithm 1 summarizes the SIMD computation procedure.

ℓ ∈ [1,𝑘 ]

4.3 Centroid-parallel execution. Existing CPU implementations of PQ construction typically apply SIMD parallelism across dimensions or across input vectors. However, during index construction, each vector is encoded only once and each subvector has low dimensionality, which limits the effectiveness of such strategies. Instead, our design applies SIMD parallelism across centroids. For a fixed subvector v𝑖( 𝑗 ) , scores for multiple centroids are evaluated concurrently using wide SIMD registers. Centroids are processed in blocks of width 𝑤, corresponding to the SIMD width of the target architecture. For each block [ℓ, ℓ + 𝑤 − 1], a SIMD register maintains the partial scores associated with these 𝑤 centroids (lines 9–15 in Algorithm 1). Iterating over centroid blocks allows all centroids to be evaluated with a bounded and predictable register footprint. SIMD-friendly codebook layout. To support centroid-parallel SIMD access, we reorganize the codebook into a transposed, structureof-arrays (SoA) layout. For each subspace 𝑠𝑝 ( 𝑗 ) , the transposed codebook C ( 𝑗 )⊤ ∈ R (𝑑/𝑚) ×𝑘 stores centroid coordinates such that all 𝑘 centroid values for a given dimension are contiguous in memory. Under this layout, the values C ( 𝑗 )⊤ [𝑡] [ℓ : ℓ + 𝑤 − 1] can be loaded using a single SIMD load (line 11). Compared to the conventional array-of-structures (AoS) representation, this layout enables contiguous access across centroids and aligns naturally with centroid-parallel SIMD computation. Register-resident accumulation. For each centroid block, accumulation registers are initialized to zero (line 8). The algorithm then iterates over the 𝑑/𝑚 dimensions of the subvector. At each iteration, the scalar value v𝑖( 𝑗 ) [𝑡] is broadcast into a SIMD register and multiplied with centroid values loaded from C ( 𝑗 )⊤ [𝑡] [ℓ : ℓ + 𝑤 − 1] (lines 11–13). The products are accumulated directly into the score registers using fused multiply-add (FMA) instructions (line 13). All partial scores remain resident in registers throughout the computation, avoiding horizontal reductions over low-dimensional subvectors and maintaining a uniform multiply-accumulate pattern. After all dimensions are processed, the registers contain the inner products for the current centroid block; the final scores are formed by combining them with the bias terms (lines 17–18). Reduction and deterministic selection. Once the scores for a centroid block are computed, a SIMD reduction identifies the minimum score within the block and its corresponding centroid index (line 21). This block-level minimum is compared against a running global minimum. If the block minimum is smaller, the global minimum is updated; ties are resolved by selecting the centroid with the smaller global index (lines 23–26). This rule ensures deterministic behavior and reproducible PQ codes. By structuring the kernel as an accumulate-then-reduce pipeline, the algorithm limits live state to SIMD registers and a small number of scalar variables.

Cache-Friendly Execution Organization

The centroid-parallel SIMD computation described in Section 4.2 optimizes the innermost PQ construction kernel by keeping accumulation and reduction entirely in registers. However, overall PQ construction performance during index construction is also determined by how this kernel is invoked across vectors and codebooks. In large-scale settings, even an efficient kernel can suffer from poor end-to-end performance if its invocation pattern induces excessive memory traffic or cache thrashing. In this section, we describe a cache-aware execution organization that explicitly controls the working set and data access order during bulk PQ processing, complementing the SIMD computation kernel. Working set and cache pressure. During PQ construction, input vectors and codebooks exhibit fundamentally different reuse patterns. Input vectors are accessed in a streaming fashion and are typically consumed only once during index construction. In contrast, each codebook and its associated bias terms are reused across a large number of vectors. From a cache perspective, these two data types should ideally be treated differently: codebooks should remain resident in cache, while vectors should flow through the memory hierarchy without displacing reusable data. Existing matrix-style PQ construction formulations fail to preserve this separation. By expressing PQ construction as a matrix-like distance computation, they materialize large, short-lived distance tables whose size scales with the product of batch size and codebook size. Although these tables are transient, they introduce substantial write traffic and significantly inflate the effective working set. As a result, cache capacity is dominated by intermediate distance data that has little or no reuse. This cache pressure repeatedly evicts codebooks from cache, forcing them to be reloaded across batches. Consequently, the potential reuse of codebooks is largely negated in practice, even when the codebooks themselves are small enough to fit within cache capacity. Chunk-centric execution order. To avoid working set inflation and preserve codebook reuse, our design adopts a chunk-centric execution organization. PQ is performed in blocks of input vectors to amortize the cost of codebook access. Within each block, the algorithm iterates over PQ chunks as the outer loop and processes all subvectors belonging to the same chunk before moving to the next chunk. For a fixed chunk, the corresponding codebook and bias terms are accessed repeatedly while subvectors from multiple vectors are streamed through the SIMD kernel. This execution order creates a well-defined reuse window for each codebook. Once a codebook is loaded into cache, it can be reused across many vectors within the same block before eviction pressure is introduced by accesses to other chunks. Importantly, this reuse window is determined by the execution order rather than by the dataset size. 7

As the dataset grows, the number of vectors processed within each reuse window increases, but the size of the resident working set remains unchanged. This property allows cache behavior to remain stable and predictable even when PQ is applied to hundreds of millions or billions of vectors. Eliminating intermediate results. A critical enabler of the chunk-centric execution organization is that centroid-parallel SIMD computation does not materialize intermediate distance results in memory. Distance values exist only as transient register-resident state and are reduced on the fly to a single minimum per subvector. At no point are full distance vectors or tables written to memory. This design choice fundamentally changes the cache footprint of PQ construction. Because intermediate distance data never enters the cache hierarchy, cache capacity is no longer consumed by short-lived, non-reusable arrays. Instead, the effective working set during construction is dominated by the codebook, its associated bias terms, and a small amount of scalar and register state. By eliminating intermediate result materialization, the execution organization ensures that cache resources are primarily allocated to data structures with high reuse potential. Streaming behavior and cache residency. Under the proposed execution organization, input subvectors are accessed sequentially and exhibit clear streaming behavior. Such access patterns can be efficiently handled by hardware prefetching mechanisms, allowing vector data to be delivered to the processor without incurring unnecessary cache pollution. Because intermediate results are not written to memory, streaming accesses to input vectors do not displace resident cache lines associated with codebooks. Meanwhile, codebooks and bias terms remain the primary resident data in cache and can be reused across successive PQ processing operations within the same chunk. This separation between resident data (codebooks and bias terms) and streaming data (input vectors) is essential for maintaining a compact and stable working set. It allows PQ construction performance to scale with dataset size without relying on explicit cache management or architecture-specific tuning. Discussion. The cache-friendly execution organization operates at a different layer of the system stack than SIMD computation. While SIMD optimizes efficiency within a single kernel, execution organization governs data flow across kernels during bulk PQ processing. By eliminating intermediate distance materialization and aligning execution order with codebook reuse, the design maintains a compact and stable working set throughout index construction. This co-design of computation and execution organization addresses the memory-sensitive nature of PQ construction and enables high, predictable performance at scale while preserving identical encoding results.

4.4

computation semantics and execution behavior complicates SIMD vectorization and increases instruction and cache overhead. In this section, we reformulate the distance computation to preserve exact centroid ranking while simplifying computation semantics. This reformulation serves as the foundation for the SIMD-friendly computation and cache-aware execution organization introduced in later stages. Problem setup. An input vector of dimensionality 𝐷 is partitioned into 𝑀 PQ chunks (subspaces), each of dimensionality 𝑑𝑠 = 𝐷/𝑀. For a fixed chunk 𝑚 ∈ {1, . . . , 𝑀 }, its subvector v ∈ R𝑑𝑠 is assigned to the nearest centroid from a codebook C (𝑚) = {c0, . . . , c𝐾 −1 }, where 𝐾 is the codebook size (typically 𝐾 = 256). The PQ code for this subvector is defined as code(v) = arg

min 𝑘 ∈ [0,𝐾 −1]

∥v − c𝑘 ∥ 2 .

(6)

During index construction, this operation is executed once per (vector, chunk) pair for every vector in the dataset. Because PQ encoding is applied to all vectors and all chunks, its cumulative cost grows linearly with dataset size and dimensionality, making it a dominant component of index construction time at scale. Standard distance formulation. A common implementation expands the squared Euclidean distance as ∥v − c𝑘 ∥ 2 = ∥v∥ 2 + ∥c𝑘 ∥ 2 − 2 v · c𝑘 .

(7)

While algebraically convenient, this formulation exposes a key inefficiency. For a fixed subvector v, the term ∥v∥ 2 is constant across all centroids and therefore cannot affect their relative ordering. Nevertheless, conventional implementations still compute this term and incorporate it into every distance score. This leads to redundant arithmetic across all 𝐾 centroids and inflates the amount of intermediate state that must be carried through the computation. In practice, these redundant operations contribute to instruction overhead, limit effective SIMD utilization, and increase pressure on registers and caches. Ranking-oriented reformulation. PQ encoding only requires identifying the centroid that minimizes the distance. For any function 𝛼 (v) that depends solely on the subvector v and is independent of the centroid index, arg min ∥v − c𝑘 ∥ 2 = arg min ∥v − c𝑘 ∥ 2 − 𝛼 (v) . (8) 𝑘

𝑘

By setting 𝛼 (v) = ∥v∥ 2 and applying it to Equation 7, we obtain an equivalent optimization objective: arg min ∥c𝑘 ∥ 2 − 2 v · c𝑘 . (9) 𝑘

For implementation convenience and to expose a regular computation structure, we divide by 2 and define the transformed score

Ranking-Oriented Distance Reformulation

1 ∥c𝑘 ∥ 2 − v · c𝑘 . (10) 2 The positive scaling factor does not affect the argmin. This reformulation removes the subvector-dependent norm term entirely and expresses PQ encoding as an inner-product-dominant computation, in which each centroid contributes through a uniform multiplyaccumulate pattern. As a result, the computation becomes more regular and better aligned with SIMD execution on modern CPUs.

PQ encoding assigns each low-dimensional subvector to the nearest centroid in a corresponding codebook. Although this operation is typically expressed as a squared-distance computation, its objective is fundamentally ranking-oriented: only the identity of the closest centroid matters, not the absolute distance value. However, existing implementations evaluate full distance expressions and materialize intermediate results, which introduces unnecessary arithmetic and memory traffic. On modern CPUs, this mismatch between

𝑠 (v, c𝑘 ) =

16k

Dataset SIFT100M-1024D [30] ARGILLA21M [5] ANTON19M [4] LAION100M [2] SIFT100M-768D SIFT100M-512D SSNPP100M [1]

#Vectors

Dim

#Queries

Type

100M 21M 19M 100M 100M 100M 100M

1024 1024 1024 768 768 512 256

10,000 100,000 100,000 100,000 10,000 10,000 100,000

float32 (synthetic) float32 float32 float32 float32 (synthetic) float32 (synthetic) float32

Correctness. Let 𝐷𝑘 = ∥v − c𝑘 Equation 7,

∥ 2 and 𝑆

PQ Construction Time (s)

Table 1: Dataset specifications.

12k

7782.06

4731.49

4357.96

3606.88

2843.45 721.38

1 2 𝑘 = 2 ∥c𝑘 ∥ − v · c𝑘 . From

14785.92

DiskANN-PQ CS-PQ

SIFT100M-1024D

1405.79

1752.41

ARGILLA21M

ANTON19M

LAION100M

2047.91

SSNPP100M

Figure 6: Overall comparison of PQ construction time. PQ Parameters. We adopt standard 8-bit per-subspace Product Quantization (PQ8), corresponding to 𝐾 = 256 centroids per subspace. Unless otherwise specified, we fix the subvector dimensionality to 16, resulting in a 64× compression ratio relative to the original float32 representation. Under this configuration, the PQ code size scales proportionally with the original dimensionality (e.g., 64 bytes for 1024-dimensional vectors and 16 bytes for 256-dimensional vectors). This compression setting is commonly used in large-scale ANN systems and provides a balanced trade-off between memory footprint, quantization fidelity, and time consumption [19, 27]. The default codebook size is set to 𝐾 = 256, and all distances are computed using the squared Euclidean (L2) metric [40]. Construction Parameters. We use the standard DiskANN implementation [27] as the baseline. Specifically, we set the maximum graph out-degree to 𝑅 = 64 and the candidate pool size during construction to 𝐿 = 128. Indices are built in a block-based manner to accommodate memory constraints when processing large datasets. Our optimized implementation modifies only the PQ construction stage of the DiskANN construction pipeline; all other components, including graph construction, neighbor pruning, and index layout, remain unchanged to ensure a fair comparison. Measurement. We primarily report PQ construction time as well as overall index build time. Each experiment is executed multiple times, and we report the average execution time over five runs. A warm-up run is performed before measurement to eliminate cold-start effects. We observe minimal variance across runs and therefore omit error bars unless otherwise noted.

𝐷𝑘 = ∥v∥ 2 + 2𝑆𝑘 . For any two centroids 𝑖 and 𝑗, 𝐷𝑖 < 𝐷 𝑗 if and only if 𝑆𝑖 < 𝑆 𝑗 . Therefore, minimizing 𝑆𝑘 preserves the exact centroid ranking for every subvector, and the reformulated computation produces identical PQ codes to the baseline squared-distance formulation. This equivalence holds for all vectors and all codebooks used during index construction. Offline and online computation. Equation 10 naturally separates PQ encoding into two components. The offline component is performed once per codebook, where centroid bias terms 𝑏𝑘 = 12 ∥c𝑘 ∥ 2 are precomputed and stored. These values are reused across all vectors encoded with the same codebook, thereby amortizing their computation cost over the entire dataset. The online component is executed per subvector. For each subvector, inner products v · c𝑘 are computed across all 𝐾 centroids, and the minimum of 𝑏𝑘 − v · c𝑘 is selected. This structure avoids computing ∥v∥ 2 entirely and reduces distance evaluation to a sequence of regular multiply-accumulate operations with minimal intermediate state.

5 EVALUATION 5.1 Experimental Setup System Configuration. All experiments are conducted on a dedicated server to ensure a controlled and reproducible evaluation environment. The server is equipped with a 40-core (80 vCPU) Intel Xeon Gold 6230 CPU, 375 GB of DDR4 main memory, and a high-performance SSD array with approximately 1.7 TB capacity. The processor supports AVX2 and AVX-512 instruction sets, which are fully enabled in our implementation. The system runs Ubuntu 20.04 LTS with Linux kernel 5.15 and the Ext4 file system. Unless otherwise specified, all evaluations employ a fixed thread count of 80 to saturate available hardware parallelism, with thread affinity pinned to physical cores to minimize migration overhead. All implementations are compiled with GCC 11.4.0 using -O3 -march=native -flto -fopenmp flags to enable architecture-specific optimizations. Datasets. We conduct evaluations on seven large-scale vector datasets with varying dimensionalities and data sources, as summarized in Table 1. The SIFT100M datasets are synthesized from the original SIFT1B benchmark to enable controlled experiments under different dimensionalities while keeping the data distribution fixed. This allows us to isolate the impact of vector dimensionality on PQ construction behavior. The remaining datasets consist of real-world embeddings collected from different application domains. Each dimension is single-precision floating-point. No dimensionality reduction (e.g., PCA) is applied unless explicitly stated.

5.2

Overall Performance

We first evaluate the overall impact of CS-PQ on index construction from two complementary perspectives: the cost of PQ construction itself and its effect on the end-to-end construction-accuracy tradeoff. Figures 6 and 7 summarize the results from both perspectives across the evaluated datasets. PQ construction time. Figure 6 shows the total PQ time under five distinct datasets during index construction. Across all datasets, CS-PQ consistently reduces PQ construction cost, achieving speedups ranging from approximately 2.7× to over 5.2× compared to the baseline PQ implementation of DiskANN (DiskANNPQ ). The improvement is observed on datasets spanning a wide range of dimensionalities (from 256 to 1024) and data sources, indicating that the benefit is not specific to a particular vector distribution. The magnitude of improvement correlates with the effective PQ workload. Higher-dimensional datasets and those using larger PQ codes (e.g., ARGILLA, ANTON, and LAION) benefit more from CS-PQ, as DiskANN-PQ performs a larger amount of rankinginvariant computation and materializes larger intermediate states. 9

DiskANN-PQ

CS-PQ

1.0

0.8 0.6

0.8 0.7

0.6

0.4

Recall@10

0.9

0.8

(a) SIFT100M-1024D

0.2 22k

24k

26k

28k

(b) ARGILLA21M

0.4

30k

0.8

10k

15k

20k

25k

12k

80k

100k

120k

140k

(e) SSNPP100M 0.4

160k

24k

30k

0.6

(d) LAION100M

0.4

18k

0.8

0.6

30k

60k

75k

90k

(f) SIFT100M-512D

0.4 10k

105k

12k

14k

16k

18k

Index Construction Time (s)

Figure 7: Overall comparison of index construction time at comparable Recall@10 levels.

PQ Construction Time (s)

24k

CS-PQ

120k

10.7

16k 8k 0 15k

6.7

5.1

3.2

8.3

12 9 6 3

64 128 256 PQ Code Size (bytes)

(a) SIFT100M-1024D

10k 5k

Speedup

(a) SIFT100M-1024D

512

6.98 6.22

7 5

512 Codebook Size

40k 0 30k

1024

5.2

10k 0

7.8

6.5

3.4

40k

20k

48 96 192 PQ Code Size (bytes)

(b) LAION100M

20k

5.1 256

12 60k

(b) LAION100M

80k

384

4.86

4.46 3.8 256

60k

40k

4 512 Codebook Size

7.5

6.4

5.3

3.8

2.6

16 32 64 PQ Code Size (bytes)

128 9 8

7.52

6.51

20k

1024

Speedup (x)

DiskANN-PQ

5.2 256

512 Codebook Size

1024

Figure 8: PQ construction time comparison under varying PQ code and codebook sizes. 4k 3k 2k

5.4 DiskANN-PQ CS-PQ Speedup

3606.88

5.1

5 2705.16

4.8

4.7

1803.44

4.5 4.3

Speedup (x)

PQ Construction Time (s)

In addition, after pvSIMD restructuring PQ construction to maintain a compact execution footprint, CS-PQ exhibits favorable scaling behavior as dimensionality increases. Even for lower-dimensional datasets such as SSNPP, where PQ construction is not the sole bottleneck, CS-PQ still delivers noticeable reductions in PQ time. These results reflect the efficacy of CS-PQ in structural improvements to the encoding pipeline rather than dataset-specific effects. Trade-off of construction time and search accuracy. Figure 7 plots index construction time versus Recall@10 (i.e., recall at top-10 nearest neighbor search) across varying PQ code sizes. CS-PQ consistently achieves higher Recall@10 than DiskANN-PQ at equivalent construction latencies. At low recall rates, construction time is dominated by non-PQ phases (e.g., graph initialization and neighbor pruning), since coarse-grained PQ configurations, with lower overhead to establish, can satisfy the low recall rates requirement. As recall requirements increase, finer-grained PQ codes become necessary, causing PQ to dominate the construction pipeline. In high-recall scenarios (Recall@10 > 0.9), i.e., the operational target for most production ANNS systems, PQ acceleration directly translates to proportional end-to-end construction speedups, with CS-PQ reducing total build time by up to 4.1× while preserving search quality. Accordingly, the improvement varies across datasets in a foreseeable manner. For datasets with higher dimensionality or finergrained PQ requirements, CS-PQ exhibits preferable gains in providing competitive indexing quality with substantially reduced construction time. Overall, these results demonstrate that CS-PQ not only reduces the cost of PQ construction in isolation, but also reshapes the cost structure of index construction. By lowering the

721.3764

575.57

419.4

SIFT100M-512D

SIFT100M-768D

SIFT100M-1024D

4.2

Figure 9: PQ construction time comparison under varying vector dimensionalities. dominant compression cost without affecting recall, CS-PQ enables faster index construction with high quality.

5.3

Microbenchmark Analysis

This section presents microbenchmarks that isolate PQ stages and examine how CS-PQ behaves under the critical parameters: PQ code size, codebook size, and vector dimensionality, respectively. In this evaluation, we use three large-scale benchmarks—SIFT100M-1024D, LAION100M, and SSNPP100M—for the code size and codebook size studies, and SIFT100M with dimensionalities of 512D, 768D, and 1024D for the dimensionality study. These evaluations aim to explain why CS-PQ delivers consistent improvements by analyzing how its benefits evolve as the intrinsic PQ workload increases. Effect of PQ Code Size. In Figure 8(top), we first vary PQ code size while keeping other parameters fixed. Increasing PQ code size corresponds to higher-precision representation, which is increasingly favored in large-scale ANNS systems to sustain high recall and throughput. As shown in Figure 8(top), CS-PQ achieves progressively larger speedups over DiskANN-PQ as PQ code size 10

16k PQ Construction Time (s)

increases across all tested ranges. The advantage grows monotonically with code size on all evaluated datasets, demonstrating that CS-PQ scales more effectively as the intrinsic PQ workload becomes heavier. This is because DiskANN-PQ increasingly suffers from two side-effects as PQ code size increases. First, larger PQ codes amplify ranking-irrelevant computation. The baseline formulation evaluates additional arithmetic terms whose values do not affect centroid ordering, causing instruction count to grow faster than the useful work required for encoding decisions. Second, larger code sizes exacerbate cache pressure by increasing the volume of intermediate state and streamed data, further degrading execution efficiency. Differently, CS-PQ optimizes the side-effects by (1) Ranking-oriented distance reformulation that ensures PQ precision translating directly into useful computation rather than redundant arithmetic; (2) Register-resident accumulation that avoids materializing intermediate distance results in memory. As a result, CS-PQ scales more gracefully with PQ code size, contributing to better speedups at higher-precision scenarios. Effect of codebook Size. We then evaluate the effects of increased codebook size. In this evaluation, vector dimensionality and compression ratio remain the default setting. Larger codebooks are commonly used to improve quantization fidelity, but they also increase the number of candidate centroids evaluated per subvector. As shown in Figure 8(bottom), across all tested settings, CS-PQ exhibits increasing PQ time reductions as codebook size grows. On the other hand, this trend also highlights a key limitation of existing PQ approaches: as the number of centroids increases, DiskANN-PQ amplifies memory traffic and cache interference due to less structured access patterns and expanded intermediate state. Even when codebooks themselves are small enough to fit in cache, reuse is undermined by cache pollution from transient distance data. In contrast, CS-PQ is explicitly designed to scale with codebook size. Our pvSIMD execution pipeline processes multiple centroids concurrently using contiguous memory access enabled by the transposed codebook layout. More importantly, the cache-friendly execution organization ensures that codebooks remain resident in cache while subvectors stream through the computation. As a result, increasing codebook size can positively increase SIMD’s computation density while the memory overheads are well mitigated, which allows CSPQ to convert additional PQ complexity into predictable compute cost. These results further demonstrate that CS-PQ does not merely optimize a fixed configuration, but remains effective as systems move toward larger codebooks to meet accuracy requirements. Effect of Dimensionality. We also study the effect of vector dimensionality across datasets with different embedding sizes, for which we assign a fixed compression ratio, i.e., PQ8 with fixed subvector dimensionality, which is a common practical setting where systems adopt a standard PQ configuration. Figure 9 shows that CS-PQ delivers significant speedups across all tested dimensionalities, indicating that its effectiveness is not tied to a particular dataset. While the absolute speedup varies with dimensionality, the qualitative behavior remains stable: CS-PQ reduces PQ time by 76.7%, 78.7%, and 80.0% under SIFT100M-512D, SIFT100M-768D, and SIFT100M-1024D, respectively. Higher dimensionality increases the amount of arithmetic per subvector, which improves the payoff of centroid-parallel SIMD execution. At the same time, DiskANNPQ becomes more sensitive to cache behavior as the volume of

12k

DiskANN-PQ +SIMD +Cache +Formula

8k 4k 0

SIFT100M-1024D

LAION100M

SSNPP100M

Figure 10: Impact of individual optimization components on PQ construction time. streamed data grows. CS-PQ alleviates this sensitivity by maintaining a compact working set and separating streaming vector access from cache-resident codebooks. Importantly, these experiments demonstrate that fixing compression ratio does not diminish the speedup gains of PQ optimization.

5.4

Ablation Study

In this section, we study the effectiveness of CS-PQ’s design components by incrementally enabling the key optimizations shown in Figure 10. Starting from DiskANN-PQ, we progressively add (1) centroid-parallel SIMD execution, (2) cache-friendly execution organization, and (3) ranking-oriented distance reformulation, and then measure the PQ time consumption on three large-scale datasets under the same index configuration as introduced in Section 5.1. Baseline DiskANN-PQ incurs the highest PQ construction time across all datasets, taking approximately 3.6K seconds on SIFT100M1024D, 14.5K seconds on LAION100M, and 7.8K seconds on SSNPP100M (Figure 10). This is because the baseline suffers from both inefficient SIMD usage and memory-system inefficiencies, leaving substantial headroom for co-design across computation and cache behavior. +SIMD. Enabling centroid-parallel SIMD reduces construction time to roughly 2.4K seconds, 9.6K seconds, and 4.8K seconds on the three datasets, yielding about 1.5×–1.6× speedup over DiskANNPQ. These improvements demonstrate that, once SIMD lanes are mapped to centroid blocks and score accumulation is kept registerresident, instruction overhead and suboptimal vector-lane utilization become materially reduced. However, the remaining time is still large especially on LAION100M, showing that memory traffic and cache misses remain the critical factors for PQ efficiency. +Cache. Adding cache-friendly execution organization delivers the largest incremental gain, which reduces the PQ construction time to about 0.8K seconds (SIFT100M-1024D), 3.2K seconds (LAION100M), and 2.3K seconds (SSNPP100M), respectively. Compared to the DiskANN baseline, this corresponds to ∼4.5×, ∼4.5×, and ∼3.3× speedups, respectively. The results demonstrate that PQ construction is primarily memory-sensitive at scale: reorganizing the execution order to preserve codebook residency and shrinking the active working set directly reduces cache thrashing and DRAM traffic, which in turn translates into substantial end-to-end construction time reduction. +Formula (CS-PQ). Finally, enabling ranking-oriented distance reformulation also yields substantial PQ construction time reductions, bringing construction time down to about 0.7K seconds, 2.8K seconds, and 2.0K seconds on the three datasets. Overall, CS-PQ 11

IPC

LLC MPKI

2.0 1.5 1.0 0.5 0.0 40 30 20 10 0

DiskANN-PQ

CS-PQ

1.34 0.78

1.21 0.64

subspaces and independently quantizing each subvector, PQ balances memory footprint, approximation fidelity, and distance evaluation efficiency. Numerous extensions refine the basic formulation, including rotation-based variants such as Optimized PQ (OPQ) [20], residual and multi-stage quantization schemes [7, 53], and other accuracy-oriented improvements [28] that reduce quantization error or enhance search recall. These efforts primarily target representation quality or accelerate query-time distance evaluation through lookup tables and asymmetric distance computation. Beyond model-level refinements, PQ has been deeply integrated into modern ANN index designs [8, 27, 29, 49], particularly in graphbased systems where compressed vectors are stored in memory to reduce bandwidth pressure during search. In such systems, PQ is often treated as a fixed compression primitive, while optimization efforts concentrate on graph traversal, candidate pruning, and query-time scoring. However, as vector dimensionality and dataset scale continue to grow, the cost of applying PQ across the entire dataset during index construction becomes increasingly significant. In high-precision configurations required to sustain high recall, PQ can dominate construction time, exposing system-level inefficiencies that are orthogonal to the quantization model itself. Prior works on SIMD PQ acceleration and cache-aware optimization have provided general techniques for improving distance computation kernels [3], including vectorized fused multiply-accumulate pipelines [21], data layout transformations [21, 34], and blocking strategies to enhance locality[34]. While these approaches are effective for dense linear algebra and high-arithmetic-intensity workloads, they cannot directly be applied to PQ construction due to its distinct characteristics. In contrast to prior efforts that modify the PQ model or focus primarily on query-time acceleration, our work focus on PQ construction. By aligning distance computation with PQ’s ranking objective, vectorizing across centroids, and structuring execution to preserve codebook residency in cache, we systematically address the arithmetic redundancy, SIMD underutilization, and memorysystem inefficiency issues while preserving bit-identical quantization semantics.

1.46 0.92

31.9

24.7 11.6 SIFT100M-1024D

15.2 LAION100M

18.3 8.9 SSNPP100M

Figure 11: Microarchitectural analysis of IPC and LLC MPKI. achieves end-to-end speedups of approximately 5.5× (SIFT100M1024D), 5.2× (LAION100M), and 3.9× (SSNPP100M) compared to DiskANN-PQ. At this stage, the reformulation mainly removes ranking-invariant arithmetic and simplifies the score data path, which complements the pvSIMD pipeline.

5.5

Microarchitectural Evidence

To further demonstrate the PQ construction time reduction, we evaluate the microarchitectural behavior of PQ construction during index construction. Figure 11 illustrates two hardware-level metrics, instructions per cycle (IPC) and last-level cache misses per thousand instructions (LLC MPKI), which are measured during PQ construction for both the baseline and CS-PQ. IPC. In Figure 11, CS-PQ consistently achieves higher IPC than the baseline across all evaluated datasets. For the baseline, IPC remains below 1.0, indicating that execution is frequently stalled and that available compute resources are not fully utilized. For CSPQ, IPC increases to above 1.2, reflecting improved utilization of the processor execution pipeline. This improvement demonstrates that CS-PQ achieves better effectiveness in SIMD utilization. LLC MPKI. Figure 11 also shows that CS-PQ substantially reduces LLC MPKI compared with the baseline. Across all evaluated datasets, CS-PQ decreases LLC MPKI by 51.4% to 53.0% compared to the baseline, which demonstrates that PQ construction under CS-PQ incurs significantly fewer last-level cache misses. The lower miss rate indicates a more stable active working set, allowing frequently accessed codebooks to be reused more effectively before eviction, and thus reducing long-latency memory accesses. Viewed jointly, the IPC and LLC MPKI measurements provide concrete evidence for the bottleneck shift identified in Section 5.4. The early-stage optimizations primarily improve instruction-level efficiency, and the pronounced reduction in LLC MPKI shows that memory behavior plays a decisive role in the final performance gains. Fewer cache misses reduce memory stall time, enabling the processor to sustain higher IPC and make steady progress through the pvSIMD pipeline. Consequently, improvements in cache locality and memory access efficiency are directly reflected in lower PQ construction time. These results demonstrate that the performance gains of CS-PQ stem from coordinated improvements in both computation efficiency and cache behavior.

CONCLUSION

We present CS-PQ, a cache-friendly, SIMD-optimized PQ construction pipeline for CPU-based large-scale ANNS index construction. CS-PQ realigns the PQ construction pipeline with modern SIMD architecture to reduce redundant calculations, improve SIMD efficiency, and preserve codebook residency in cache during bulk PQ processing. Experiments on large-scale datasets show that CSPQ consistently reduces PQ construction cost and improves the end-to-end index construction time without affecting recall.

REFERENCES [1] 2021. Billion-Scale Approximate Nearest Neighbor Search Challenge: NeurIPS’21 Competition Track. https://big-ann-benchmarks.com/neurips21.html. Accessed January 7, 2026. [2] 2024. The LAION2B and Projections. https://sisap-challenges.github.io/2024/ datasets/. Accessed January 7, 2026. [3] Frédéric André et al. 2019. Quicker ADC: Unlocking the Hidden Potential of Product Quantization with SIMD. IEEE TPAMI (2019). [4] anton-l. 2024. wiki-embed-mxbai-embed-large-v1. https://huggingface.co/ datasets/anton-l/wiki-embed-mxbai-embed-large-v1. Accessed January 7, 2026. [5] Argilla Warehouse. 2024. Personahub FineWeb-Edu 4 Embeddings. https://huggingface.co/datasets/argilla-warehouse/personahub-fineweb-

RELATED WORK

Product Quantization (PQ) is a foundational vector compression technique for large-scale approximate nearest neighbor (ANN) search. By decomposing a high-dimensional vector into multiple 12

[31] Haodi Jiang, Hao Guo, Minhui Xie, Jiwu Shu, and Youyou Lu. 2025. HighThroughput, Cost-Effective Billion-Scale Vector Search with a Single GPU. Proc. ACM Manag. Data 3, 6 (2025), 27. [32] Zhengbao Jiang, Frank F. Xu, Luyu Gao, Zhiqing Sun, Qian Liu, Jane DwivediYu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023. Active Retrieval Augmented Generation. In Conference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, Singpore, 7969– 7992. [33] M. V. Koroteev. 2021. BERT: A Review of Applications in Natural Language Processing and Understanding. CoRR abs/2103.11943 (2021). https://arxiv.org/ abs/2103.11943 [34] Monica Lam, Edward Rothberg, and Michael Wolf. 1991. The Cache Performance and Optimizations of Blocked Algorithms. In ASPLOS. [35] Stuart P. Lloyd. 1982. Least squares quantization in PCM. IEEE Trans. Inf. Theory 28, 2 (1982), 129–136. [36] Yury A. Malkov and Dmitry A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 42, 4 (2020), 824–836. [37] Malkov, Yury and Ponomarenko, Alexander and Logvinov, Andrey and Krylov, Vladimir. 2014. Approximate Nearest Neighbor Algorithm based on Navigable Small World Graphs. Information Systems 45 (2014), 61–68. [38] Ootomo, Hiroyuki and Naruse, Akira and Nolet, Corey and Wang, Ray and Feher, Tamas and Wang, Yong. 2024. CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs. In International Conference on Data Engineering (ICDE). IEEE, Netherlands, 4236–4247. [39] James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Vector Database Management Techniques and Systems. In International Conference on Management of Data (SIGMOD) . ACM, USA, 597–604. [40] Pan, James Jie and Wang, Jianguo and Li, Guoliang. 2024. Survey of vector database management systems. The VLDB Journal 33, 5 (2024), 1591–1615. [41] Qin, Ruoyu and Li, Zheming and He, Weiran and Cui, Jialei and Ren, Feng and Zhang, Mingxing and Wu, Yongwei and Zheng, Weimin and Xu, Xinran. 2025. Mooncake: Trading More Storage for Less Computation—A KVCache-centric Architecture for Serving LLM Chatbot. In USENIX Conference on File and Storage Technologies (FAST). USENIX Association, USA, 155–170. [42] Amit Sharma, Hua Li, Xue Li, and Jian Jiao. 2024. Optimizing Novelty of Top-k Recommendations using Large Language Models and Reinforcement Learning. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD). ACM, Spain, 5669–5679. [43] Ji Sun, Guoliang Li, James Pan, Jiang Wang, Yongqing Xie, Ruicheng Liu, and Wen Nie. 2025. GaussDB-Vector: A Large-Scale Persistent Real-Time Vector Database for LLM Applications. Proc. VLDB Endow. 18, 12 (2025), 4951–4963. [44] Toni Taipalus. 2024. Vector database management systems: Fundamental concepts, use-cases, and current challenges. Cognitive Systems Research 85 (2024), 101216. [45] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017. Attention is All you Need. In Advances in Neural Information Processing Systems, I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc., USA. [46] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search. Proc. VLDB Endow. 14, 11 (2021), 1964–1978. [47] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2022. Manu: a Cloud Native Vector Database Management System. Proc. VLDB Endow. 15, 12 (2022), 3548–3561. [48] Wang, Jianguo and Yi, Xiaomeng and Guo, Rentong and Jin, Hai and Xu, Peng and Li, Shengjun and Wang, Xiangyu and Guo, Xiangzhou and Li, Chengming and Xu, Xiaohai and others. 2021. Milvus: A purpose-built vector data management system. In ACM International Conference on Management of Data (SIGMOD). ACM, China, 2614–2627. [49] Wang, Mengzhao and Xu, Weizhi and Yi, Xiaomeng and Wu, Songlin and Peng, Zhangyang and Ke, Xiangyu and Gao, Yunjun and Xu, Xiaoliang and Guo, Rentong and Xie, Charles. 2024. Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment. Proc. ACM Manag. Data 2, 1, Article 14 (March 2024), 27 pages. [50] Mingyu Yang, Wentao Li, Jiabao Jin, Xiaoyao Zhong, Xiangyu Wang, Zhitao Shen, Wei Jia, and Wei Wang. 2025. Effective and General Distance Computation for Approximate Nearest Neighbor Search. In International Conference on Data Engineering (ICDE). IEEE, Hong Kong, 1098–1110. [51] Yang, Xiwang and Steck, Harald and Guo, Yang and Liu, Yong. 2012. On Top-K Recommendation Using Social Networks. In ACM Conference on Recommender Systems (RecSys). ACM, Ireland, 67–74. [52] Qinggang Zhang, Shengyuan Chen, Yuanchen Bei, Zheng Yuan, Huachi Zhou, Zijin Hong, Hao Chen, Yilin Xiao, Chuang Zhou, Junnan Dong, et al. 2025. A survey of graph retrieval-augmented generation for customized large language models. arXiv preprint arXiv:2501.13958 (2025).

edu-4-embeddings. Accessed January 7, 2026. [6] Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2025. Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art. Proc. ACM Manag. Data 3, 1, Article 43 (2025), 31 pages. [7] Artem Babenko and Victor Lempitsky. 2014. Additive Quantization for Extreme Vector Compression. In CVPR. [8] Artem Babenko and Victor S. Lempitsky. 2014. Additive Quantization for Extreme Vector Compression. In Conference on Computer Vision and Pattern Recognition (CVPR). IEEE Computer Society, USA, 931–938. [9] Babenko, Artem and Lempitsky, Victor. 2015. The Inverted Multi-Index. IEEE Transactions on Pattern Analysis and Machine Intelligence 37, 6 (2015), 1247–1260. [10] Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (1975), 509–517. [11] Nolwenn Bernard and Krisztian Balog. 2025. A Systematic Review of Fairness, Accountability, Transparency, and Ethics in Information Retrieval. ACM Comput. Surv. 57, 6 (2025), 29. [12] Bing Tian and Haikun Liu and Yuhang Tang and Shihai Xiao and Zhuohui Duan and Xiaofei Liao and Hai Jin and Xuecang Zhang and Junhua Zhu and Yu Zhang. 2025. Towards High-throughput and Low-latency Billion-scale Vector Search via CPU/GPU Collaborative Filtering and Re-ranking. In USENIX Conference on File and Storage Technologies (FAST). USENIX Association, USA, 171–185. [13] Cheng Chen, Chenzhe Jin, Yunan Zhang, Sasha Podolsky, Chun Wu, SzuPo Wang, Eric Hanson, Zhou Sun, Robert Walzer, and Jianguo Wang. 2024. Singlestore-v: An Integrated Vector Database System in Singlestore. Proc. VLDB Endow. 17, 12 (2024), 3772–3785. [14] Jia Chen, Qian Dong, Haitao Li, Xiaohui He, Yan Gao, Shaosheng Cao, Yi Wu, Ping Yang, Chen Xu, Yao Hu, Qingyao Ai, and Yiqun Liu. 2025. Qilin: A Multimodal Information Retrieval Dataset with APP-level User Sessions. In International Conference on Research and Development in Information Retrieval (SIGIR). ACM, USA, 3670–3680. [15] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The Faiss library. CoRR abs/2401.08281 (2024). [16] Fu, Cong and Xiang, Chao and Wang, Changxu and Cai, Deng. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proc. VLDB Endow. 12, 5 (2019), 461–474. [17] Fiona Fui-Hoon Nah, Ruilin Zheng, Jingyuan Cai, Keng Siau, and Langtao Chen. 2023. Generative AI and ChatGPT: Applications, challenges, and AI-human collaboration. , 277–304 pages. [18] Gao, Yunfan and Xiong, Yun and Gao, Xinyu and Jia, Kangxiang and Pan, Jinliu and Bi, Yuxi and Dai, Yi and Sun, Jiawei and Wang, Haofen and Wang, Haofen. 2023. Retrieval-Augmented Generation for Large Language Models: A survey. arXiv preprint arXiv:2312.10997 2 (2023). [19] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search. In Conference on Computer Vision and Pattern Recognition (CVPR). IEEE Computer Society, USA, 2946–2953. [20] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR. [21] Kazushige Goto and Robert van de Geijn. 2008. Anatomy of High-Performance Matrix Multiplication. ACM TOMS (2008). [22] Kazushige Goto and Robert A. van de Geijn. 2008. Anatomy of High-Performance Matrix Multiplication. ACM Trans. Math. Software 34, 3 (2008), 12:1–12:25. [23] Groh, Fabian and Ruppert, Lukas and Wieschollek, Patrick and Lensch, Hendrik P. A. 2023. GGNN: Graph-Based GPU Nearest Neighbor Search. IEEE Transactions on Big Data 9, 1 (2023), 267–279. [24] Emrul Hasan, Mizanur Rahman, Chen Ding, Jimmy Xiangji Huang, and Shaina Raza. 2025. Review-based Recommender Systems: A Survey of Approaches, Challenges and Future Perspectives. ACM Comput. Surv. 58, 1 (2025), 41. [25] Intel Corporation. 2023. Intel® 64 and IA-32 Architectures Optimization Reference Manual. Available at: https://www.intel.com/content/www/us/en/developer/articles/technical/intelsdm.html. [26] Intel Corporation. 2023. Intel® oneAPI Math Kernel Library Developer Guide. Available at: https://www.intel.com/content/www/us/en/developer/tools/oneapi/onemkl.html. [27] Jayaram Subramanya, Suhas and Devvrit, Fnu and Simhadri, Harsha Vardhan and Krishnawamy, Ravishankar and Kadekodi, Rohan. 2019. Diskann: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In Annual Conference on Neural Information Processing Systems (NeurIPS), Vol. 32. MIT Press, Canada. [28] Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product Quantization for Nearest Neighbor Search. In IEEE TPAMI. [29] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Trans. Pattern Anal. Mach. Intell. 33, 1 (2011), 117–128. [30] Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. 2011. Searching in One Billion Vectors: Re-Rank with Source Coding. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 861–864. 13

[55] Yutao Zhu, Huaying Yuan, Shuting Wang, Jiongnan Liu, Wenhan Liu, Chenlong Deng, Haonan Chen, Zheng Liu, Zhicheng Dou, and Ji-Rong Wen. 2025. Large Language Models for Information Retrieval: A Survey. ACM Trans. Inf. Syst. 44, 1 (2025), 54.

[53] Ting Zhang, Chao Du, and Jingdong Wang. 2014. Composite Quantization for Approximate Nearest Neighbor Search. In ICML. [54] Zhao, Weijie and Tan, Shulong and Li, Ping. 2020. SONG: Approximate Nearest Neighbor Search on GPU. In International Conference on Data Engineering (ICDE). IEEE, USA, 1033–1044.

CS-PQ: Cache-Friendly SIMD Product Quantization for Large-Scale ANNS Index Construction

Related documents