How do memory access patterns and cache misses influence the latency and throughput of vector search algorithms, especially in graph-based vs. flat indexes?

Memory access patterns and cache misses significantly impact the performance of vector search algorithms by determining how efficiently data is retrieved from memory. When data is accessed in a predictable, sequential manner (like in flat indexes), the CPU can prefetch data into its cache, reducing latency. However, if accesses are random (common in graph-based indexes), the CPU cannot anticipate the next memory location, leading to frequent cache misses. Each cache miss forces the CPU to wait for data from slower main memory, increasing latency and reducing throughput. The total time spent waiting for data often outweighs the raw computation time, making memory efficiency a critical factor in algorithm design.

Flat indexes, such as brute-force linear search or inverted files, process vectors sequentially. For example, a linear search computes distances between a query and every vector in the dataset. This sequential access pattern is cache-friendly because the CPU can prefetch contiguous blocks of data into the cache, minimizing misses. However, for large datasets that exceed cache capacity, even flat indexes suffer from cache thrashing as data is evicted and reloaded repeatedly. Throughput here depends on how much data can fit into the cache and how well SIMD (Single Instruction, Multiple Data) instructions parallelize computations. For smaller datasets, flat indexes perform well, but latency grows linearly with dataset size, making them impractical for large-scale applications.

Graph-based indexes, like HNSW (Hierarchical Navigable Small World), use pointer-rich structures to navigate connections between vectors. During a search, the algorithm jumps between nodes in the graph, which are often scattered in memory. This random access pattern causes frequent cache misses, as each hop may require fetching a distant memory location. For instance, traversing an HNSW graph might involve checking neighbors of a node stored far from the current working set. While graph-based methods reduce the number of distance computations compared to flat indexes, their latency per operation is higher due to memory stalls. However, their ability to skip irrelevant vectors often leads to better overall throughput for large datasets, as fewer total operations are needed. Optimizations like grouping related graph nodes in memory or using approximate distance calculations can mitigate cache inefficiencies, but the trade-off between computation and memory access remains a key consideration when choosing between index types.