←back to thread

The Theoretical Limitations of Embedding-Based Retrieval

(arxiv.org)
147 points fzliu | 1 comments | 29 Aug 25 20:25 UTC | HN request time: 0s | source
Show context
Straw ◴[30 Aug 25 01:01 UTC] No.45071026[source]▶
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 vectors.

Embed our points as (sin(theta), cos(theta), sin(2 x theta), cos(2 x theta)..., sin(k x theta), cos(k x theta)), with theta uniformly spaced around the circle, and we should be able to select any k of them.

Using a few more dimensions we can then ease the precision requirements on the query.

replies(2): >>45071266 #>>45072420 #
yorwba ◴[30 Aug 25 06:42 UTC] No.45072420[source]▶
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?
replies(1): >>45072550 #
1. Straw ◴[30 Aug 25 07:10 UTC] No.45072550[source]▶
Viewing our space as two complex points instead of four real:

Let H(z) = (z- exp(i theta)) (z - exp(i phi))

H(z) is zero only for our two points. We'll now take the norm^2, to get something that's minimized on only our two chosen points.

|H(exp(i x))|^2 = H(z) x conj(H(z)) = sum from -2 to 2 of c_j x exp(i j x)

For some c_j (just multiply it out). Note that this is just a Fourier series with highest harmonic 2 (or k in general), so in fact our c_j tell us the four coefficients to use.

For a simpler, but numerically nastier construction, instead use (t, t^2, t^3, ...), the real moment curve. Then given k points, take the degree k poly with those zeros. Square it, negate, and we get a degree 2k polynomial that's maximized only on our selected k points. The coefficients of this poly are the coefficients of our query vector, as once expanded onto the moment curve we can evaluate polynomials by dot product with the coefficients.

The complex version is exactly the same idea but with z^k and z ranging on the unit circle instead.