3 ms·

SCaNN (the paper) is roughly two different things: 1. a SIMD-optimized form of product quantization (PQ), where code to distance lookup can be performed in SIM

by jhj 3y ago

SCaNN (the paper) is roughly two different things: 1. a SIMD-optimized form of product quantization (PQ), where code to distance lookup can be performed in SIMD registers 2. anisotropic quantization to bias the database towards returning better maximum inner product search (MIPS) candidates, versus usual quantization (such as PQ) that aims to minimize compressed vector reconstruction error. In MIPS it is much more likely that the query data set may be of a completely different distribution than the database vectors. If your application needs L2 lookup rather than MIPS which does not admit a metric, then only the PQ part is relevant. For cosine similarity, you can get that by normalizing all vectors to the surface of a hypersphere, in which case it has the same order as L2 (see "L2 normalized Euclidean distance" on https://en.wikipedia.org/wiki/Cosine_similarity https://en.wikipedia.org/wiki/Cosine_similarity ). SCaNN is implemented in Faiss CPU, on the GPU the fast PQ part is less relevant due to the greater register set size and throughput (rather than latency) optimized nature of the hardware, but the GPU version is more geared towards batch lookup in any case. https://github.com/facebookresearch/faiss/wiki/Fast-accumulation-of-PQ-and-AQ-codes-(FastScan) https://github.com/facebookresearch/faiss/wiki/Fast-accumula... https://github.com/facebookresearch/faiss/wiki/Indexing-1M-vectors#4-bit-pq-comparison-with-scann https://github.com/facebookresearch/faiss/wiki/Indexing-1M-v... We have not found the anisotropic quantization part to be that useful for large datasets, but results may vary. Graph-based ANN techniques tend to be better in many cases for these small datasets than IVF based strategies. (I'm the author of GPU Faiss)

chuckcode 3y ago
Thanks for details! Few follow up questions: - I've seen neural nets using int8 for matrix multiplication to reduce memory size [1]. Do you think something similar could be useful in the ANN space? - Do you know of any studies using Faiss looking at speed/cost tradeoffs of RAM vs flash vs Disk for storage? - Are there recommended ways to update Faiss index with streaming data, e.g. updating the vectors continuously? Seems like more and more use cases for Faiss as neural nets become more and more core to workflows. Would like to try and figure out the configurations that are optimized to minimize carbon usage in addition to latency and recall metrics. [1] https://arxiv.org/abs/2208.07339 https://arxiv.org/abs/2208.07339 (edit for formatting)
- jhj 3y ago
  Regarding reduced precision, depending upon what you are trying to do, I think it doesn't work quite as well in similarity search as it does for, say, neural networks. If you are concerned about recall of the true nearest neighbor (k=1), in many datasets I've seen (especially large ones) in float32 the distance from a query vector to candidate nearest neighbor vectors may only differ by some thousands of ULPs when performing brute force search, which if done in float16 would result in the true nearest neighbor being the same as (or perhaps behind even, due to rounding error) other proximate vectors. If you are performing approximate lookup and you have the luxury of performing reranking (you store the compressed / approximate index for lookup, but return a larger candidate set like k=100 or k=1000 and refine the results based on true distances computed from the uncompressed vectors via brute-force, so you have to keep all the original vectors around) then this problem can go away. If however you are looking at recall@100 (is the true nearest neighbor reported within the top k=100) or set intersection (of the k=100 approximate nearest neighbors, how much overlap is there with the true set of the 100 nearest neighbors), then this doesn't matter as much. Certainly a lot of the options in the Faiss library are geared towards compression and quantization anyways (e.g., storing a billion high-dimensional vector dataset in 8/16 GB of memory) so this is a tradeoff as with everything else. In Faiss there are the scalar quantizer indexes which do store vectors in int4/int8 etc for which int8 GEMM (accumulate in int32) would be great, but using this would require that the query vector itself be quantized to int4/int8 as well. This is the difference between "asymmetric distance computation" (ADC) where you compute the distance between int4 encoded vectors (or product quantized encoded vectors, etc) versus a float32 query vector, where we reconstruct the database vectors in floating point and compare in floating point, versus symmetric distance computation (you have to convert the query vector to int4 say, and compare in the quantized regime). ADC tends to work a lot better than symmetric computation, so this is why we don't use pure int8 GEMM, but maybe in many applications (NN inference, say, instead of image database search) the non-ADC comparison would be ok.
  - chuckcode 3y ago
    Thanks for the very helpful and detailed reply!

by jhj 3y ago

chuckcode 3y ago

Thanks for details! Few follow up questions: - I've seen neural nets using int8 for matrix multiplication to reduce memory size [1]. Do you think something similar could be useful in the ANN space? - Do you know of any studies using Faiss looking at speed/cost tradeoffs of RAM vs flash vs Disk for storage? - Are there recommended ways to update Faiss index with streaming data, e.g. updating the vectors continuously? Seems like more and more use cases for Faiss as neural nets become more and more core to workflows. Would like to try and figure out the configurations that are optimized to minimize carbon usage in addition to latency and recall metrics. [1] https://arxiv.org/abs/2208.07339 https://arxiv.org/abs/2208.07339 (edit for formatting)

jhj 3y ago
Regarding reduced precision, depending upon what you are trying to do, I think it doesn't work quite as well in similarity search as it does for, say, neural networks. If you are concerned about recall of the true nearest neighbor (k=1), in many datasets I've seen (especially large ones) in float32 the distance from a query vector to candidate nearest neighbor vectors may only differ by some thousands of ULPs when performing brute force search, which if done in float16 would result in the true nearest neighbor being the same as (or perhaps behind even, due to rounding error) other proximate vectors. If you are performing approximate lookup and you have the luxury of performing reranking (you store the compressed / approximate index for lookup, but return a larger candidate set like k=100 or k=1000 and refine the results based on true distances computed from the uncompressed vectors via brute-force, so you have to keep all the original vectors around) then this problem can go away. If however you are looking at recall@100 (is the true nearest neighbor reported within the top k=100) or set intersection (of the k=100 approximate nearest neighbors, how much overlap is there with the true set of the 100 nearest neighbors), then this doesn't matter as much. Certainly a lot of the options in the Faiss library are geared towards compression and quantization anyways (e.g., storing a billion high-dimensional vector dataset in 8/16 GB of memory) so this is a tradeoff as with everything else. In Faiss there are the scalar quantizer indexes which do store vectors in int4/int8 etc for which int8 GEMM (accumulate in int32) would be great, but using this would require that the query vector itself be quantized to int4/int8 as well. This is the difference between "asymmetric distance computation" (ADC) where you compute the distance between int4 encoded vectors (or product quantized encoded vectors, etc) versus a float32 query vector, where we reconstruct the database vectors in floating point and compare in floating point, versus symmetric distance computation (you have to convert the query vector to int4 say, and compare in the quantized regime). ADC tends to work a lot better than symmetric computation, so this is why we don't use pure int8 GEMM, but maybe in many applications (NN inference, say, instead of image database search) the non-ADC comparison would be ok.
- chuckcode 3y ago
  Thanks for the very helpful and detailed reply!