4 ms·
This works especially well if your embedding model was trained to perform well with quantized embeddings. Binary + hamming distance = incredibly fast. This pos
by emschwartz 2mo ago
This works especially well if your embedding model was trained to perform well with quantized embeddings. Binary + hamming distance = incredibly fast.
This post is from 2024 but I wrote about using this technique in https://emschwartz.me/binary-vector-embeddings-are-so-cool/ https://emschwartz.me/binary-vector-embeddings-are-so-cool/
- softwaredoug 2mo agoHamming w/xor+popcount is the only thing I can make numpy do faster than float32 dot products :) int8s, float16s are all fairly slow. I suppose it’s because BLAS does float32/64 very fast.
- emschwartz 2mo agoYeah that makes sense. I took the optimizations of my hamming distance library to a bit of an insane level. I wrote this about the first round https://emschwartz.me/unnecessary-optimization-in-rust-hamming-distances-simd-and-auto-vectorization/ https://emschwartz.me/unnecessary-optimization-in-rust-hammi... The second round brought the best result down to 0.8 nanoseconds per comparison on x86 with SIMD (for a batch of 1000). Separately, I’m a huge fan of your writing about search! It’s been very helpful while I’ve been building https://scour.ing https://scour.ing.
- softwaredoug 2mo agoThank you! <3
- dimatura 2mo agoI remember similar observations for an earlier use case in computer vision, loop closure and place recognition for visual SLAM algorithms. In this case the goal was to find a needle (or needles) in a big haystack of visual descriptors (in some sense, proto-embeddings for small image patches or in some cases, whole images). Several approaches used hierarchical data structures for the NN search such as k-mean trees. But linear search - especially with binary descriptors, also became popular as a fast and simple alternative.