Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Theoretical Limitations of Embedding-Based Retrieval

arxiv.org

Post reply on HN
Print view View original

31–40 of 42 posts

Re: The Theoretical Limitations of Embedding-Based Retrieval

#31

Post by anothernewdude »

mingtianzhang wrote: post #25

We are always looking for representations that can capture the meaning of information. However, most representations that compress information for retrieval are lossy. For example, embeddings are a form of lossy compression. Similar to the no-free-lunch theorem, no lossy compression method is universally better than another, since downstream tasks may depend on the specific information that gets lost. Therefore, the…

> Similar to the no-free-lunch theorem, no lossy compression method is universally better than another,

No lunch theorem only works, because they assume you care about every single value of noise. Nobody does. There's a free lunch to be had, and it's order. You don't care about a single pixel difference between two cat pictures, NFL does.

Lossy compression is precisely where NFL does not apply.

Re: The Theoretical Limitations of Embedding-Based Retrieval

#32

Post by mingtianzhang »

anothernewdude wrote: post #31
mingtianzhang wrote: post #25

We are always looking for representations that can capture the meaning of information. However, most representations that compress information for retrieval are lossy. For example, embeddings are a form of lossy compression. Similar to the no-free-lunch theorem, no lossy compression method is universally better than another, since downstream tasks may depend on the specific information that gets lost. Therefore, the…

> Similar to the no-free-lunch theorem, no lossy compression method is universally better than another, No lunch theorem only works, because they assume you care about every single value of noise. Nobody does. There's a free lunch to be had, and it's order. You don't care about a single pixel difference between two cat pictures, NFL does. Lossy compression is precisely where NFL does not apply.

Just similar in theorem style, I try to emphasise that no lossy representation is universally (i.e. for all downstream tasks) better than another.

Re: The Theoretical Limitations of Embedding-Based Retrieval

#33

Post by jdthedisciple »

tkfoss wrote: post #5
gdiamos wrote: post #2

Their idea is that capacity of even 4096-wide vectors limits their performance. Sparse models like BM25 have a huge dimension and thus don’t suffer from this limit, but they don’t capture semantics and can’t follow instructions. It seems like the holy grail is a sparse semantic model. I wonder how splade would do?

Wouldn't holy grail then be parallel channels for candidate generation; euclidean embedding hyperbolic embedding sparse BM25 / SPLADE lexical search optional multi-vector signatures ↓ merge & deduplicate candidates followed by weight scoring, expansion (graph) & rerank (LLM)?

that is pretty much exactly what we do for our company-internal knowledge retrieval:

    embedding search (0.4)
    lexical/keyword search (0.4)
    fuzzy search (0.2)
might indeed achieve the best of all worlds

Re: The Theoretical Limitations of Embedding-Based Retrieval

#34

Post by quadhome »

mingtianzhang wrote: post #25

We are always looking for representations that can capture the meaning of information. However, most representations that compress information for retrieval are lossy. For example, embeddings are a form of lossy compression. Similar to the no-free-lunch theorem, no lossy compression method is universally better than another, since downstream tasks may depend on the specific information that gets lost. Therefore, the…

Humans only retrieve information in a library in that way due to the past limitations on retrieval and processing. The invention of technologies like tables of contents or even the Dewey Decimal Classification are strongly constrained by fundamental technologies like ... the alphabet! And remember, not all languages are alphabetic. And embeddings aren't alphabetic and don't share the same constraints.

I recommend Judith Flanders' "A Place for Everything" as a both a history and survey of the constraints in sorting and organising information in an alphabetic language. It's also a fun read!

tl;dr why would we want an LLM do something as inefficiently as a human?

Re: The Theoretical Limitations of Embedding-Based Retrieval

#35

Post by simne »

Could somebody suggest good introduction to simulation of complex behavior with neural networks?

I mean, I hear, about experiments of running Turing machine simulation on NN, or even simulation of some physics on NN, but I have not seen any good survey on these topics, and they could be very interest on subject.

Re: The Theoretical Limitations of Embedding-Based Retrieval

#36

Post by cap11235 »

zwaps wrote: post #16
CuriouslyC wrote: post #8

Earlier quoted context omitted.

If you consider the actual latent space the full higher dimensional representation, and you take the first principle component, the other vectors are zero. Pretty sparse. No it's not a linked list sparse matrix. Don't be a pedant.

No one means Matryoshka embeddings when they talk about sparse embeddings. This is not pedantic.

Why?

Re: The Theoretical Limitations of Embedding-Based Retrieval

#37

Post by miven »

CuriouslyC wrote: post #4
gdiamos wrote: post #2

Their idea is that capacity of even 4096-wide vectors limits their performance. Sparse models like BM25 have a huge dimension and thus don’t suffer from this limit, but they don’t capture semantics and can’t follow instructions. It seems like the holy grail is a sparse semantic model. I wonder how splade would do?

We already have "sparse" embeddings. Google's Matryoshka embedding schema can scale embeddings from ~150 dimensions to >3k, and it's the same embedding with layers of representational meaning. Imagine decomposing an embedding along principle components, then streaming the embedding vectors in order of their eigenvalue, kind of the idea.

Correct me if I'm misinterpreting something in your argument but as I see it Matryoshka embeddings just sort the vector bases of the output space roughly by order of their importance for the task, PCA-style, so when you truncate your 4096-dimensionnal embedding down to a set of let's say 256 dimensions, those are the exact same 256 vector bases doing the core job of encoding important information for each sample, so you're back to dense retrieval on 256-dimensional vectors, just that all the minor miscellaneous slack useful for a very low fraction of queries has been trimmed away.

True sparsity would imply keeping different important vector bases for different documents, but MRL doesn't magically shuffle vector bases around depending on what's your document contains, were that the case cosine similarity between the resulting documents embeddings would simply make no sense as a similarity measure.

Re: The Theoretical Limitations of Embedding-Based Retrieval

#38

Post by jandrewrogers »

mingtianzhang wrote: post #26
mingtianzhang wrote: post #25

We are always looking for representations that can capture the meaning of information. However, most representations that compress information for retrieval are lossy. For example, embeddings are a form of lossy compression. Similar to the no-free-lunch theorem, no lossy compression method is universally better than another, since downstream tasks may depend on the specific information that gets lost. Therefore, the…

A follow-up question is: what is the lossless way to represent knowledge? That would mean reading all the knowledge at once, which is the most accurate but also the least efficient method. Therefore, for different applications, we need to find an appropriate trade-off between accuracy and efficiency. In systems like real-time recommendation, we prefer efficiency over accuracy, so vector-based search is suitable. In d…

This is the subject of the Hutter Prize and the algorithmic information theory that underpins it. There are some hard algorithm and data structure problems underlying lossless approximations of general learning even for relatively closed domains.

As an example, current AI is famously very poor at learning relationships between non-scalar types, like complex geometry, which humans learn with ease. That isn’t too surprising because the same representation problem exists in non-AI computer science.

Re: The Theoretical Limitations of Embedding-Based Retrieval

#39

Post by mingtianzhang »

quadhome wrote: post #34
mingtianzhang wrote: post #25

We are always looking for representations that can capture the meaning of information. However, most representations that compress information for retrieval are lossy. For example, embeddings are a form of lossy compression. Similar to the no-free-lunch theorem, no lossy compression method is universally better than another, since downstream tasks may depend on the specific information that gets lost. Therefore, the…

Humans only retrieve information in a library in that way due to the past limitations on retrieval and processing. The invention of technologies like tables of contents or even the Dewey Decimal Classification are strongly constrained by fundamental technologies like ... the alphabet! And remember, not all languages are alphabetic. And embeddings aren't alphabetic and don't share the same constraints. I recommend Jud…

"why would we want an LLM do something as inefficiently as a human?" -- That is a good point. Maybe we should rename artificial intelligence (AI) to super-artificial intelligence (SAI).

Re: The Theoretical Limitations of Embedding-Based Retrieval

#40

Post by faxipay349 »

gdiamos wrote: post #2

Their idea is that capacity of even 4096-wide vectors limits their performance. Sparse models like BM25 have a huge dimension and thus don’t suffer from this limit, but they don’t capture semantics and can’t follow instructions. It seems like the holy grail is a sparse semantic model. I wonder how splade would do?

I just came across an evaluation of state-of-the-art SPLADE models. Yeah they utilize BERT's vocabulary size as their sparse vector dimensionality and do capture semantics. As expected, they significantly outperform all dense models in this benchmark. https://github.com/frinkleko/LIMIT-Sparse-Embedding OpenSearch team seemed has been working on inference-free versions of these models. Similar to BM25, these models only encode documents offline. So now we have sparse, small and efficient models while is much better than dense ones, at least on LIMIT
Post reply on HN