4 ms·

Binary vector search is better than FP32 vectors

137 points by gaocegege 3y ago

crucio 3y ago
how well would this work for 762 dimensional vectors? At 3072, they're starting with such a high number of dimensions that the accuracy loss may not be representative of what others would see
- esafak 3y ago
  You'd have to look at the precision-recall curves for your data set and make the trade-off. There are studies on this topic.
- mediaman 3y ago
  Generally, it seems that people are starting to see more problems when making vectors of fewer than 1,000 dimensions binary.
- blublubdub 3y ago
  seems to work pretty well check this out: https://huggingface.co/blog/embedding-quantization https://huggingface.co/blog/embedding-quantization
refulgentis 3y ago
Dear reader: your intuition is right: it's not "better" to reduce the information by a factor of 32. The game the article plays is to do a KNN search to deal with the fact this flattens similarity significantly. TL;DR from the field: - this is extremely helpful for doing a first pass over a _ton_ of documents in a resource constrained environment. - it is extremely unhelpful unless you're retrieving 10x the documents you want via binary, then doing re-ranking via the FP-32 to rank the remaining. - in general, it's unlikely you need the technique unless you're A) on the edge, i.e. on consumer devices from 3 years ago or B) you have tens of millions of vectors on a server. All this stuff sounds really fancy, but when you implement it from scratch, you quickly learn "oh its 384 numbers I gotta multiply together" Source: I do embeddings, locally, to do retrieval for RAG. I "discovered" this about a year ago, and it deeply pains me to see anything that will misinform a lot of people. Free bonus I haven't seen mentioned elsewhere yet*: you can take the average of the N embeddings forming a document to figure out if you should look at the N embeddings individually. This does over smooth too, ex. my original test document is the GPT-4 sparks paper, and the variety of subjects mentioned and length (100+ pages) meant it was over smooth when searching for the particular example I wanted it to retrieve (the unicorn SVG) * edited to clarify given reply. also my reaction to reading it, "that dude rocks!!", made me wanna go off a little bit: if you're not in AI/ML, don't be intimidated by it when its wrapped in layers of obscure vocabulary. once you have the time to go do it, things you would have thought that were "stupid" turn out to be just fine. and you find like-minded souls. It's exhilirating
- moralestapia 3y ago
  >I'll throw in a free bonus no one has mentioned yet, at least publicly: you can take the average of the N embeddings forming a document to figure out if you should look at the N embeddings individually. Hey, I do this! :D But I've seen it mentioned in several places, it wasn't completely my own idea.
  - VorticonCmdr 3y ago
    This reminds me a lot of simhashing e.g. https://matpalm.com/resemblance/simhash/ https://matpalm.com/resemblance/simhash/
- sgt101 3y ago
  >Free bonus I haven't seen mentioned elsewhere yet* This is a good idea. Is it a little like a version of HNSW?
- dleeftink 3y ago
  Binning and averaging is a well-known technique I'd say, whether applied to PCA components or even raw distributional data sorted over some dimension. A relatex technique that I've seen speed up retrieval tasks immensely is merging frequently co-occurring binned embeddings into new bins (similar to Byte Pair Encoding) and downweighing the resulting bins when the variance between its constituent dimensions is high. This effectively yields 'bins of interest' where documents agree on some dimension(s) while filtering out documents that contain information that is general to most.
- nblgbg 3y ago
  I agree with the comment. Especially if you index these quantized vectors with HNSW you will get even less precision. You need to retrieve lot more and do a kNN with the FP32 vectors is the way to go !
- gwern 3y ago
  > Free bonus I haven't seen mentioned elsewhere yet: you can take the average of the N embeddings forming a document to figure out if you should look at the N embeddings individually. This does over smooth too, ex. my original test document is the GPT-4 sparks paper, and the variety of subjects mentioned and length (100+ pages) meant it was over smooth when searching for the particular example I wanted it to retrieve (the unicorn SVG) This is something I've been pondering for doing lookups across essays! That is, I saw some people doing per-paragraph embeddings, so you could do something like mouse-select a paragraph in an essay, and then get a list of all other paragraphs site-wide which are 'similar'. However, it seems to me like this would run into trouble with small or generic paragraphs (because their embeddings will be noisy & extreme & there's a lot of them and you may wind up pulling up only sibling paragraphs, defeating the point)... But what if you did it as a tree? Embed each paragraph, then average a couple paragraphs, then average the paragraphs embeddings, and so on to the whole-essay level. Then do the lookups as usual. Any given paragraph might instead pull up a genuinely relevant section, or a range of paragraphs, or a whole essay, rather than some spurious paragraph. (And you could constrain the lookup to be tree-like too: first find the most similar essay-level embedding, then see if any of that essay's section embeddings are more relevant, then check its paragraphs embeddings etc, and stop when the distance stops decreasing compared to the parent node. This would let you enforce diversity of results: eg take only 1 hit per essay, so you don't wind up showing the reader 10 hits which are all on the same page.) Does that correspond to anything? https://en.wikipedia.org/wiki/Hierarchical_Navigable_Small_World_graphs https://en.wikipedia.org/wiki/Hierarchical_Navigable_Small_W... seems tree-like but the trees used in it do not seem to correspond to the actual document structure like I'm proposing, and solely is an optimization on pre-existing embeddings which mostly ignore any document structure.
barefeg 3y ago
This technique had a very recent resurgence via https://txt.cohere.com/int8-binary-embeddings/ https://txt.cohere.com/int8-binary-embeddings/. Hugging face also covered the technique here https://huggingface.co/blog/embedding-quantization https://huggingface.co/blog/embedding-quantization. It seems like a very good tradeoff compared to the shorter embeddings which require fine tuning via the matryoshka technique. On the other hand, Nils Reimers suggests that trivial quantization of the full precision embeddings is not as good as using “compression friendly” embeddings like Cohere’s Embed V3. Does anyone know what’s the difference in precision between trivial quantization and optimized embeddings?
rurban 3y ago
April 1 jokes already? Storing floats as bit, great idea!
- riku_iki 3y ago
  bit embeddings are different to float, they are trained separately.
- marginalia_nu 3y ago
  I think the the technique is best understood as a special case of random projection. It's well understood that there are a class of dimensional reduction techniques that preserve distances well (via the J-L lemma), owing to the countrerintuitive fact that most high dimensional vectors are nearly orthogonal.
heipei 3y ago
To the people dismissing the idea of binarising vectors: Fair criticism, but consider the fact that you can also train a model with a loss function that approaches a binary behaviour, i.e. so that the magnitude per dimension plays an insignificant role and only the sign of the dimension carries information. In that case you can use the binary vector for search and ranking.
- mjburgess 3y ago
  in practice, learning_rate * grad(L) is mostly about the direction anyway.
  - niederman 3y ago
    But the direction is not at all binary, it's a direction in a very high-dimensional weight space.
    - bjourne 3y ago
      But the vectors discussed can represent 2^3072 directions. It's close enough.
jn2clark 3y ago
What is accuracy in this case? is it meant to be recall or is it some evaluation metric?
- gaocegege 3y ago
  Yeah, it is recall.
dicey 3y ago
This reminds me somewhat of the iSAX papers from ~2010 [0], which was focused on time series but used a pretty cool method to binarize/discretize the real values data and do search. I wonder how folks building things like FAISS or vector DBs incorporate ideas like this , or if the two worlds don’t overlap very often. [0]. https://www.cs.ucr.edu/~eamonn/iSAX_2.0.pdf https://www.cs.ucr.edu/~eamonn/iSAX_2.0.pdf
kookamamie 3y ago
> our experiments showed that the decrease in accuracy was not as big as expected A decrease, nevertheless. This is always the issue with pruning, sparsification, etc. - to get SOTA, you will not want a decrease of any kind.
- gaocegege 3y ago
  In certain situations, we might have to make a trade-off between performance and cost. There are many scenarios where a high level of recall is not necessary.

137 points by gaocegege 3y ago

how well would this work for 762 dimensional vectors? At 3072, they're starting with such a high number of dimensions that the accuracy loss may not be representative of what others would see

esafak 3y ago
You'd have to look at the precision-recall curves for your data set and make the trade-off. There are studies on this topic.
mediaman 3y ago
Generally, it seems that people are starting to see more problems when making vectors of fewer than 1,000 dimensions binary.
blublubdub 3y ago
seems to work pretty well check this out: https://huggingface.co/blog/embedding-quantization https://huggingface.co/blog/embedding-quantization

refulgentis 3y ago

Dear reader: your intuition is right: it's not "better" to reduce the information by a factor of 32. The game the article plays is to do a KNN search to deal with the fact this flattens similarity significantly. TL;DR from the field: - this is extremely helpful for doing a first pass over a _ton_ of documents in a resource constrained environment. - it is extremely unhelpful unless you're retrieving 10x the documents you want via binary, then doing re-ranking via the FP-32 to rank the remaining. - in general, it's unlikely you need the technique unless you're A) on the edge, i.e. on consumer devices from 3 years ago or B) you have tens of millions of vectors on a server. All this stuff sounds really fancy, but when you implement it from scratch, you quickly learn "oh its 384 numbers I gotta multiply together" Source: I do embeddings, locally, to do retrieval for RAG. I "discovered" this about a year ago, and it deeply pains me to see anything that will misinform a lot of people. Free bonus I haven't seen mentioned elsewhere yet*: you can take the average of the N embeddings forming a document to figure out if you should look at the N embeddings individually. This does over smooth too, ex. my original test document is the GPT-4 sparks paper, and the variety of subjects mentioned and length (100+ pages) meant it was over smooth when searching for the particular example I wanted it to retrieve (the unicorn SVG) * edited to clarify given reply. also my reaction to reading it, "that dude rocks!!", made me wanna go off a little bit: if you're not in AI/ML, don't be intimidated by it when its wrapped in layers of obscure vocabulary. once you have the time to go do it, things you would have thought that were "stupid" turn out to be just fine. and you find like-minded souls. It's exhilirating

moralestapia 3y ago
>I'll throw in a free bonus no one has mentioned yet, at least publicly: you can take the average of the N embeddings forming a document to figure out if you should look at the N embeddings individually. Hey, I do this! :D But I've seen it mentioned in several places, it wasn't completely my own idea.
- VorticonCmdr 3y ago
  This reminds me a lot of simhashing e.g. https://matpalm.com/resemblance/simhash/ https://matpalm.com/resemblance/simhash/
sgt101 3y ago
>Free bonus I haven't seen mentioned elsewhere yet* This is a good idea. Is it a little like a version of HNSW?
dleeftink 3y ago
Binning and averaging is a well-known technique I'd say, whether applied to PCA components or even raw distributional data sorted over some dimension. A relatex technique that I've seen speed up retrieval tasks immensely is merging frequently co-occurring binned embeddings into new bins (similar to Byte Pair Encoding) and downweighing the resulting bins when the variance between its constituent dimensions is high. This effectively yields 'bins of interest' where documents agree on some dimension(s) while filtering out documents that contain information that is general to most.
nblgbg 3y ago
I agree with the comment. Especially if you index these quantized vectors with HNSW you will get even less precision. You need to retrieve lot more and do a kNN with the FP32 vectors is the way to go !
gwern 3y ago
> Free bonus I haven't seen mentioned elsewhere yet: you can take the average of the N embeddings forming a document to figure out if you should look at the N embeddings individually. This does over smooth too, ex. my original test document is the GPT-4 sparks paper, and the variety of subjects mentioned and length (100+ pages) meant it was over smooth when searching for the particular example I wanted it to retrieve (the unicorn SVG) This is something I've been pondering for doing lookups across essays! That is, I saw some people doing per-paragraph embeddings, so you could do something like mouse-select a paragraph in an essay, and then get a list of all other paragraphs site-wide which are 'similar'. However, it seems to me like this would run into trouble with small or generic paragraphs (because their embeddings will be noisy & extreme & there's a lot of them and you may wind up pulling up only sibling paragraphs, defeating the point)... But what if you did it as a tree? Embed each paragraph, then average a couple paragraphs, then average the paragraphs embeddings, and so on to the whole-essay level. Then do the lookups as usual. Any given paragraph might instead pull up a genuinely relevant section, or a range of paragraphs, or a whole essay, rather than some spurious paragraph. (And you could constrain the lookup to be tree-like too: first find the most similar essay-level embedding, then see if any of that essay's section embeddings are more relevant, then check its paragraphs embeddings etc, and stop when the distance stops decreasing compared to the parent node. This would let you enforce diversity of results: eg take only 1 hit per essay, so you don't wind up showing the reader 10 hits which are all on the same page.) Does that correspond to anything? https://en.wikipedia.org/wiki/Hierarchical_Navigable_Small_World_graphs https://en.wikipedia.org/wiki/Hierarchical_Navigable_Small_W... seems tree-like but the trees used in it do not seem to correspond to the actual document structure like I'm proposing, and solely is an optimization on pre-existing embeddings which mostly ignore any document structure.

barefeg 3y ago

This technique had a very recent resurgence via https://txt.cohere.com/int8-binary-embeddings/ https://txt.cohere.com/int8-binary-embeddings/. Hugging face also covered the technique here https://huggingface.co/blog/embedding-quantization https://huggingface.co/blog/embedding-quantization. It seems like a very good tradeoff compared to the shorter embeddings which require fine tuning via the matryoshka technique. On the other hand, Nils Reimers suggests that trivial quantization of the full precision embeddings is not as good as using “compression friendly” embeddings like Cohere’s Embed V3. Does anyone know what’s the difference in precision between trivial quantization and optimized embeddings?

rurban 3y ago

April 1 jokes already? Storing floats as bit, great idea!

riku_iki 3y ago
bit embeddings are different to float, they are trained separately.
marginalia_nu 3y ago
I think the the technique is best understood as a special case of random projection. It's well understood that there are a class of dimensional reduction techniques that preserve distances well (via the J-L lemma), owing to the countrerintuitive fact that most high dimensional vectors are nearly orthogonal.

heipei 3y ago

To the people dismissing the idea of binarising vectors: Fair criticism, but consider the fact that you can also train a model with a loss function that approaches a binary behaviour, i.e. so that the magnitude per dimension plays an insignificant role and only the sign of the dimension carries information. In that case you can use the binary vector for search and ranking.

mjburgess 3y ago
in practice, learning_rate * grad(L) is mostly about the direction anyway.
- niederman 3y ago
  But the direction is not at all binary, it's a direction in a very high-dimensional weight space.
  - bjourne 3y ago
    But the vectors discussed can represent 2^3072 directions. It's close enough.

jn2clark 3y ago

What is accuracy in this case? is it meant to be recall or is it some evaluation metric?

gaocegege 3y ago
Yeah, it is recall.

dicey 3y ago

This reminds me somewhat of the iSAX papers from ~2010 [0], which was focused on time series but used a pretty cool method to binarize/discretize the real values data and do search. I wonder how folks building things like FAISS or vector DBs incorporate ideas like this , or if the two worlds don’t overlap very often. [0]. https://www.cs.ucr.edu/~eamonn/iSAX_2.0.pdf https://www.cs.ucr.edu/~eamonn/iSAX_2.0.pdf

kookamamie 3y ago

> our experiments showed that the decrease in accuracy was not as big as expected A decrease, nevertheless. This is always the issue with pruning, sparsification, etc. - to get SOTA, you will not want a decrease of any kind.

gaocegege 3y ago
In certain situations, we might have to make a trade-off between performance and cost. There are many scenarios where a high level of recall is not necessary.