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

11–20 of 42 posts

Re: The Theoretical Limitations of Embedding-Based Retrieval

#11

Post by namibj »

Straw wrote: post #9

In the theoretical section, they extrapolate assuming a polynomial from 40 to thousands of dimensions. Why do they trust a polynomial fit to extrapolate two orders of magnitude? Why do we even think it's polynomial instead of exponential in the first place? Most things like this increase exponentially with dimension. In fact, I think we can do it in d=2k dimensions, if we're willing to have arbitrarily precise query…

In practice you're actually hitting further problems because you don't have those synthetic top-k tasks but rather open-domain documents and queries to support. And if you hope to get better than "just" having the top-k correct and instead get some sort of inclusion/exclusion boundary between what should be matched and what should not be matched, you'll hit the same bounds as apply to context length limitations for kq dimenionality in a transformer's attention layers, as I mentioned about 6 weeks ago: https://news.ycombinator.com/item?id=44570650

Re: The Theoretical Limitations of Embedding-Based Retrieval

#12

Post by CuriouslyC »

3abiton wrote: post #10
CuriouslyC wrote: post #4

Earlier quoted context omitted.

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.

Doesn't PCA compress the embeddings in this case, ie reduce the accuracy? It's similar to quantization.

Component analysis doesn't fundamentally reduce information, it just rotates it into a more informative basis. People usually drop vectors using the eigenvalues to do dimensionality reduction, but you don't have to do that.

Re: The Theoretical Limitations of Embedding-Based Retrieval

#13

Post by lunarmony »

Researchers have discussed limitations of vector-based retrieval from a rank perspective in various forms for a few years. It's further been shown that better alternative exists; some low-rank approaches can theoretically approximate arbitrary high-rank distribution while permitting MIPS-level efficient inference (see e.g., Retrieval with Learned Similarities, https://arxiv.org/abs/2407.15462). Such solutions are already being used in production at Meta and at LinkedIn.

Re: The Theoretical Limitations of Embedding-Based Retrieval

#14

Post by yorwba »

lunarmony wrote: post #13

Researchers have discussed limitations of vector-based retrieval from a rank perspective in various forms for a few years. It's further been shown that better alternative exists; some low-rank approaches can theoretically approximate arbitrary high-rank distribution while permitting MIPS-level efficient inference (see e.g., Retrieval with Learned Similarities, https://arxiv.org/abs/2407.15462 ). Such solutions are al…

I don't think Mixture of Logits from the paper you link circumvents the theoretical limitations pointed out here, since their dataset size mostly stays well below the limit.

In the end they still rely on Maximum Inner Product Search, just with several lookups for smaller partitions of the full embedding, and the largest dataset is Books, where this paper suggests you'd need more than 512 embedding dimensions, and MoL with 256-dimensional embeddings split into 8 parts of 32 each has an abysmal hit rate.

So that's hardly a demonstration that arbitrary high-rank distributions can be approximated well. MoL seems to approximate it better than other approaches, but all of them are clearly hampered by the small embedding size.

Re: The Theoretical Limitations of Embedding-Based Retrieval

#15

Post by yorwba »

Straw wrote: post #9

In the theoretical section, they extrapolate assuming a polynomial from 40 to thousands of dimensions. Why do they trust a polynomial fit to extrapolate two orders of magnitude? Why do we even think it's polynomial instead of exponential in the first place? Most things like this increase exponentially with dimension. In fact, I think we can do it in d=2k dimensions, if we're willing to have arbitrarily precise query…

I'm not following your construction. In the k=2 case, how do you construct your 4-dimensional query vector so that the dot product is maximized for two different angles theta and phi, but lower for any other arbitrary angle?

Re: The Theoretical Limitations of Embedding-Based Retrieval

#16

Post by zwaps »

CuriouslyC wrote: post #8
jxmorris12 wrote: post #7

Earlier quoted context omitted.

Matryoshka embeddings are not sparse. And SPLADE can scale to tens or hundreds of thousands of dimensions.

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.

Re: The Theoretical Limitations of Embedding-Based Retrieval

#18

Post by CuriouslyC »

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.

No one means wolves when they talk about dogs, obviously wolves and dogs are TOTALLY different things.

Re: The Theoretical Limitations of Embedding-Based Retrieval

#19

Post by yorwba »

CuriouslyC wrote: post #8
jxmorris12 wrote: post #7

Earlier quoted context omitted.

Matryoshka embeddings are not sparse. And SPLADE can scale to tens or hundreds of thousands of dimensions.

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.

When you truncate Matryoshka embeddings, you get the storage benefits of low-dimensional vectors with the limited expressiveness of low-dimensional vectors. Usually, what people look for in sparse vectors is to combine the storage benefits of low-dimensional vectors with the expressiveness of high-dimensional vectors. For that, you need the non-zero dimensions to be different for different vectors.
Post reply on HN