内存访问模式和缓存未命中通过决定从内存中检索数据的效率，显著影响向量搜索算法的性能。 当以可预测的顺序方式（如在平面索引中）访问数据时，CPU 可以将数据预取到其缓存中，从而减少延迟。 但是，如果访问是随机的（在基于图的索引中很常见），则 CPU 无法预测下一个内存位置，从而导致频繁的缓存未命中。 每次缓存未命中都会迫使 CPU 等待来自较慢的主内存的数据，从而增加延迟并降低吞吐量。 等待数据所花费的总时间通常超过原始计算时间，因此内存效率是算法设计中的一个关键因素。
平面索引（例如暴力线性搜索或倒排文件）按顺序处理向量。 例如，线性搜索计算查询与数据集中每个向量之间的距离。 这种顺序访问模式对缓存友好，因为 CPU 可以将连续的数据块预取到缓存中，从而最大限度地减少未命中。 但是，对于超出缓存容量的大型数据集，即使是平面索引也会因数据反复被驱逐和重新加载而导致缓存抖动。 此处的吞吐量取决于有多少数据可以放入缓存以及 SIMD（单指令，多数据）指令并行计算的程度。 对于较小的数据集，平面索引表现良好，但是延迟随数据集大小线性增长，这使得它们对于大规模应用程序不切实际。
基于图的索引（例如 HNSW（分层可导航小世界））使用指针丰富的结构来导航向量之间的连接。 在搜索期间，该算法在图中的节点之间跳转，这些节点通常分散在内存中。 这种随机访问模式会导致频繁的缓存未命中，因为每次跳转可能都需要获取遥远的内存位置。 例如，遍历 HNSW 图可能涉及检查存储在远离当前工作集的位置的节点的邻居。 尽管基于图的方法减少了与平面索引相比的距离计算次数，但是由于内存停顿，每次操作的延迟更高。 但是，它们跳过不相关向量的能力通常可以为大型数据集带来更好的整体吞吐量，因为需要的总操作更少。 在内存中对相关图节点进行分组或使用近似距离计算等优化可以缓解缓存效率低下，但是在选择索引类型时，计算和内存访问之间的权衡仍然是一个关键的考虑因素。