Comment by jhj

Brute-force indices are usually arithmetic bound (e.g., GEMM). Cell-probe based indices are usually memory bandwidth bound (IVF, LSH bucketing, etc). Graph-based indices are usually memory latency bound (traversing linked lists / graph data structures).

(I wrote the GPU half of Faiss and work with the people who wrote this paper).