4 ms·

This is so true. A plain old exhaustive SIMD-optimized similarity search will do just fine in many cases and not have any of the approximation tradeoffs of HNSW

This is so true. A plain old exhaustive SIMD-optimized similarity search will do just fine in many cases and not have any of the approximation tradeoffs of HNSW.

PhilippGille 2y ago
In chromem-go [1] I'm searching through 100,000 vectors in 40ms on a mid-range laptop CPU, even without SIMD. It's quick enough for many use cases. [1] https://github.com/philippgille/chromem-go https://github.com/philippgille/chromem-go
- PaulHoule 2y ago
  It would be very hard to find a problem that has better mechanical sympathy than full-scan similarity search. Even if the operation count of some other algorithm was 1/10 on paper it might not be faster if the prefetcher and branch predictor aren't running at their best. People who want to start with RAG should not start with a vector search engine but instead download https://sbert.net/ https://sbert.net/ and start messing around w/ Jupyter notebooks and maybe FAISS. People who think I'm going to upload vectors to an expensive cloud service over a slow ADSL connection are delusional.
  - rockwotj 2y ago
    Swap out FAISS with usearch, you get all the awesome SIMD acceleration (via dynamic dispatch), optional compression. Not affiliated but really cool tech. https://github.com/unum-cloud/usearch https://github.com/unum-cloud/usearch
    - zackangelo 2y ago
      fwiw faiss, although a bit unwieldy, has an optimized full scan search built into it as well
      - ashvardanian 2y ago
        Yes, it does, but it may be somewhat limited. If you need AVX2 float32 kernels for cosine distance, you are in luck. If you want dynamic dispatch from 200+ SIMD kernels across 4 generations of AVX-512 (Skylake-X, Ice Lake, Sapphire Rapids, and AMD Genoa), AVX2, Arm NEON, Arm SVE, and SVE2 for different mixed-precision distance functions, you may find other options more capable :)
        zackangelo 2y ago
        lol good to know! I've had the luxury of only needing the first one :)
    - vegabook 2y ago
      Just tried usearch against ol’ faithful np.dot, and found the latter to be 8x faster than usearch on 10m brute force scan as described in their readme [1] for top 50 matches. Identical output result. 1.74 seconds for numpy and around 12 seconds for usearch on an M2 max with enough ram to hold the vectors without swapping. [1] https://github.com/unum-cloud/usearch?tab=readme-ov-file#exact-vs-approximate-search https://github.com/unum-cloud/usearch?tab=readme-ov-file#exa...
      - ashvardanian 2y ago
        Author here :) This might not be an apples-to-apples comparison. NumPy uses BLAS for matrix multiplication, which benefits from tiling to make better use of CPU caches. USearch, on the other hand, computes L2 distance directly (not the dot product) and supports a variety of metrics. It doesn't use tiling, so it's expected to be slower than BLAS GEMM routines for single or double-precision vectors. Things might get more interesting with half-precision, brain-float16, or integer representations, where the trade-offs are less straightforward. Let me know if you decide to try it with those — I'd love to hear how it performs. PS: You may find related benchmarks here: https://github.com/ashvardanian/SimSIMD https://github.com/ashvardanian/SimSIMD
        vegabook 2y ago
        It turns out, my bad and I apologise, that although 10e6 x 1e3 FP32 fits well within 96GB of RAM, during the np.random.rand initialization phase intermediate allocations mean we go to about 32GB of swap files. These only get cleared if more ram is demanded and that happens on the first bench run. So whichever gets run first, np or usearch, gets penalised bigtime. So now I have re-run with sizes that never reach swap threshold, and the results are MUCH more impressive for usearch. Basically usearch is twice as fast. 7e6x1e3 scan for 1e3 top 50 is 1.32 seconds for numpy and 0.633 seconds for usearch. Swapped the order of benchmarks as well to rerun, and results check out. Nice work. usearch is now in my toolkit and I apologise again for the misleading comment. As an aside, it's kind of amazing how it takes essentially just over half a second to scan 7m 1032-size vectors for semantic similarity, on a (beefy but not extraordinary) desktop computer. Modern hardware is so awesome. And I'm guessing I could get another order of magnitude or two speedup if I got Metal involved. EDIT: Linux on tiny el-cheapo 100 dollar Intel n95 mini PC with 32GIG of (single channel) RAM, and dropping size to 3mx1024: usearch: 0.65 seconds numpy: 0.99 seconds. Amazing.
  - abhgh 2y ago
    I strongly advocate this! If you're starting off in this space, check if this barebones implementation isn't all you need. You can't beat the accuracy of a full search; in theory, you're trading off scalability, but validate if you need the scale where this tradeoff begins to show. And yes, sbert is great, and it gives you options to choose [1] between accuracy (MPNet) and speed (MiniLM). There are also multi-lingual options. And remember, you can also fine-tune MPNet with SetFit. And there are always new and interesting embeddings being released, so remember to re-assess the fitment of embeddings once in a while against what you're using, e.g., LLM2vec or ModernBERT. A good idea would be to keep checking MTEB [2]. [1] https://www.sbert.net/docs/sentence_transformer/pretrained_models.html#original-models https://www.sbert.net/docs/sentence_transformer/pretrained_m... [2] https://huggingface.co/spaces/mteb/leaderboard https://huggingface.co/spaces/mteb/leaderboard
    - VoVAllen 2y ago
      Hi, I'm the author of the article. I agree with your point. The model from https://www.mixedbread.ai/blog/mxbai-embed-xsmall-v1 https://www.mixedbread.ai/blog/mxbai-embed-xsmall-v1 also looks great, though I haven’t had the chance to try it yet.

This is so true. A plain old exhaustive SIMD-optimized similarity search will do just fine in many cases and not have any of the approximation tradeoffs of HNSW.

PhilippGille 2y ago

In chromem-go [1] I'm searching through 100,000 vectors in 40ms on a mid-range laptop CPU, even without SIMD. It's quick enough for many use cases. [1] https://github.com/philippgille/chromem-go https://github.com/philippgille/chromem-go

PaulHoule 2y ago
It would be very hard to find a problem that has better mechanical sympathy than full-scan similarity search. Even if the operation count of some other algorithm was 1/10 on paper it might not be faster if the prefetcher and branch predictor aren't running at their best. People who want to start with RAG should not start with a vector search engine but instead download https://sbert.net/ https://sbert.net/ and start messing around w/ Jupyter notebooks and maybe FAISS. People who think I'm going to upload vectors to an expensive cloud service over a slow ADSL connection are delusional.
- rockwotj 2y ago
  Swap out FAISS with usearch, you get all the awesome SIMD acceleration (via dynamic dispatch), optional compression. Not affiliated but really cool tech. https://github.com/unum-cloud/usearch https://github.com/unum-cloud/usearch
  - zackangelo 2y ago
    fwiw faiss, although a bit unwieldy, has an optimized full scan search built into it as well
    - ashvardanian 2y ago
      Yes, it does, but it may be somewhat limited. If you need AVX2 float32 kernels for cosine distance, you are in luck. If you want dynamic dispatch from 200+ SIMD kernels across 4 generations of AVX-512 (Skylake-X, Ice Lake, Sapphire Rapids, and AMD Genoa), AVX2, Arm NEON, Arm SVE, and SVE2 for different mixed-precision distance functions, you may find other options more capable :)
      - zackangelo 2y ago
        lol good to know! I've had the luxury of only needing the first one :)
  - vegabook 2y ago
    Just tried usearch against ol’ faithful np.dot, and found the latter to be 8x faster than usearch on 10m brute force scan as described in their readme [1] for top 50 matches. Identical output result. 1.74 seconds for numpy and around 12 seconds for usearch on an M2 max with enough ram to hold the vectors without swapping. [1] https://github.com/unum-cloud/usearch?tab=readme-ov-file#exact-vs-approximate-search https://github.com/unum-cloud/usearch?tab=readme-ov-file#exa...
    - ashvardanian 2y ago
      Author here :) This might not be an apples-to-apples comparison. NumPy uses BLAS for matrix multiplication, which benefits from tiling to make better use of CPU caches. USearch, on the other hand, computes L2 distance directly (not the dot product) and supports a variety of metrics. It doesn't use tiling, so it's expected to be slower than BLAS GEMM routines for single or double-precision vectors. Things might get more interesting with half-precision, brain-float16, or integer representations, where the trade-offs are less straightforward. Let me know if you decide to try it with those — I'd love to hear how it performs. PS: You may find related benchmarks here: https://github.com/ashvardanian/SimSIMD https://github.com/ashvardanian/SimSIMD
      - vegabook 2y ago
        It turns out, my bad and I apologise, that although 10e6 x 1e3 FP32 fits well within 96GB of RAM, during the np.random.rand initialization phase intermediate allocations mean we go to about 32GB of swap files. These only get cleared if more ram is demanded and that happens on the first bench run. So whichever gets run first, np or usearch, gets penalised bigtime. So now I have re-run with sizes that never reach swap threshold, and the results are MUCH more impressive for usearch. Basically usearch is twice as fast. 7e6x1e3 scan for 1e3 top 50 is 1.32 seconds for numpy and 0.633 seconds for usearch. Swapped the order of benchmarks as well to rerun, and results check out. Nice work. usearch is now in my toolkit and I apologise again for the misleading comment. As an aside, it's kind of amazing how it takes essentially just over half a second to scan 7m 1032-size vectors for semantic similarity, on a (beefy but not extraordinary) desktop computer. Modern hardware is so awesome. And I'm guessing I could get another order of magnitude or two speedup if I got Metal involved. EDIT: Linux on tiny el-cheapo 100 dollar Intel n95 mini PC with 32GIG of (single channel) RAM, and dropping size to 3mx1024: usearch: 0.65 seconds numpy: 0.99 seconds. Amazing.
- abhgh 2y ago
  I strongly advocate this! If you're starting off in this space, check if this barebones implementation isn't all you need. You can't beat the accuracy of a full search; in theory, you're trading off scalability, but validate if you need the scale where this tradeoff begins to show. And yes, sbert is great, and it gives you options to choose [1] between accuracy (MPNet) and speed (MiniLM). There are also multi-lingual options. And remember, you can also fine-tune MPNet with SetFit. And there are always new and interesting embeddings being released, so remember to re-assess the fitment of embeddings once in a while against what you're using, e.g., LLM2vec or ModernBERT. A good idea would be to keep checking MTEB [2]. [1] https://www.sbert.net/docs/sentence_transformer/pretrained_models.html#original-models https://www.sbert.net/docs/sentence_transformer/pretrained_m... [2] https://huggingface.co/spaces/mteb/leaderboard https://huggingface.co/spaces/mteb/leaderboard
  - VoVAllen 2y ago
    Hi, I'm the author of the article. I agree with your point. The model from https://www.mixedbread.ai/blog/mxbai-embed-xsmall-v1 https://www.mixedbread.ai/blog/mxbai-embed-xsmall-v1 also looks great, though I haven’t had the chance to try it yet.