Cranfield query 185 asks for experimental studies on panel flutter. BM25 puts abstract 856 first with a score of 18.038 and abstract 857 second with 16.564, a difference that comes from counting four stems in 1,400 abstracts over a vocabulary of 4,803 stems. A bi-encoder replaces all of that with one vector of a few hundred numbers per abstract, computed before any query is known. Can 384 numbers keep abstract 856 ahead of abstract 857, for this query and for every other query that might be asked?
Not in general, and how far they fall short can be calculated. A single-vector retriever scores a passage $p$ for a query $q$ by the dot product $\vec{q} \cdot \vec{p}$ of two vectors in $\mathbb{R}^m$, the design of dense passage retrieval. Its limits are of three kinds. Some follow from geometry and can be proved: a fixed dimension $m$ can keep only so many fine distinctions between documents. Some are measured: on collections unlike its training data a dense retriever often scores below BM25. And some are visible in particular queries, where a name, a number or an exact phrase decides the answer.
Here is the route. First we write BM25 itself as a dot product, in as many dimensions as the vocabulary has, so that the question becomes one of compression. Then we compress it with a random projection, state the bound of Luan and colleagues with the idea of its proof, and derive the exact error probability for the Gaussian case, which shows how tight their bound is. Next come two other geometric limits, a counting bound and crowding. After the theory we turn to measurements: a word-overlap test on this site's passages, the BEIR benchmark, and this site's own queries. The article assumes dense passage retrieval and cosine similarity. Its numbers are computed by tools/experiments/dense/limits-of-single-vector-retrieval.py with the unit's pinned encoder, sentence-transformers/all-MiniLM-L6-v2 at revision 1110a243fdf4, which gives $m = 384$.
BM25 is already a single-vector retriever
A lexical ranker and a dense one are closer in form than they look. Here is the idea in one sentence: BM25's score is a dot product of a query vector and a document vector, both with one coordinate per vocabulary term.
Let the vocabulary have $V$ terms. Give the query a vector $\vec{q} \in \mathbb{R}^V$ whose coordinate for term $t$ is the term's inverse document frequency weight times the number of times $t$ occurs in the query, and zero for terms the query lacks. Give document $d$ a vector $\vec{d} \in \mathbb{R}^V$ whose coordinate for term $t$ is the saturated, length-normalized term frequency
$$\frac{\mathit{tf}_{t,d}\,(k_1 + 1)}{\mathit{tf}_{t,d} + k_1\left(1 - b + b\,\dfrac{L_d}{L_{\text{avg}}}\right)},$$
with $L_d$ the document's length and $L_{\text{avg}}$ the average length. The sum over the query's terms that defines BM25 in its article is then exactly $\vec{q} \cdot \vec{d}$. The document vector does not depend on the query, so it can be computed in advance, which is what an inverted index stores. Luan, Eisenstein, Toutanova and Collins (2021, section 2) start from this observation, and note that the Boolean overlap count and TF-IDF fit the same form.
On Cranfield, with the analyzer of comparing ranking models, $V = 4{,}803$. The script builds the 1,400 document vectors and 225 query vectors and checks that their dot products reproduce the unit's BM25 ranking. So BM25 is a single-vector retriever with $m = 4{,}803$, in which almost every coordinate of every vector is zero. A dense retriever is a single-vector retriever with $m$ of a few hundred and no zeros. The second is a compression of something like the first, and the question of this article becomes: what does the compression lose?
Compressing with a random projection
The simplest compression is a random linear map. Luan and colleagues use it as a baseline for what they call the fidelity of a compressive encoder: how far the input can be compressed while the encoder still reproduces the distinctions a bag-of-words ranker makes. A random projection is not a trained encoder, and a trained encoder is not trying to reproduce BM25. The baseline is useful because it can be analyzed completely, and because exact term overlap is one of the two things a retriever must detect, the other being similarity of meaning.
Let $A$ be an $m \times V$ matrix whose entries are independent draws from a normal distribution with mean 0 and variance $1/m$. The compressed vectors are $A\vec{q}$ and $A\vec{d}$, and the compressed score is $A\vec{q} \cdot A\vec{d}$. (Luan and colleagues write the dimension as $k$, and also treat matrices of random signs $\pm 1/\sqrt{m}$; this unit writes $m$.) The variance $1/m$ is chosen so that lengths are preserved on average: for any fixed vector $\vec{x}$, the expected value of $\lvert A\vec{x} \rvert^2$ is $\lvert \vec{x} \rvert^2$.
A pairwise ranking error occurs for a query $q$ and two documents with $\vec{q} \cdot \vec{d}_1 > \vec{q} \cdot \vec{d}_2$ when the projection reverses them, $A\vec{q} \cdot A\vec{d}_1 \le A\vec{q} \cdot A\vec{d}_2$. How likely that is depends on one number.
Definition (Luan et al., Definition 2.1). For a query and two documents with $\vec{q} \cdot \vec{d}_1 \ge \vec{q} \cdot \vec{d}_2$, the normalized margin is
$$\mu(q, d_1, d_2) = \frac{\vec{q} \cdot (\vec{d}_1 - \vec{d}_2)}{\lvert \vec{q} \rvert \; \lvert \vec{d}_1 - \vec{d}_2 \rvert}.$$
It is the cosine of the angle between the query and the difference of the two documents, a number between 0 and 1. The numerator is the score difference. The denominator grows with everything in which the two documents differ, including all the terms the query never mentions. Two long documents that differ in a hundred terms, of which the query cares about one, have a small normalized margin however clear the score difference looks.
For query 185 the margins between abstract 856 and three lower-ranked abstracts are these:
| BM25 rank | Abstract | BM25 score | Normalized margin against abstract 856 |
|---|---|---|---|
| 2 | 857 | 16.564 | 0.0294 |
| 10 | 391 | 12.587 | 0.0884 |
| 100 | 704 | 3.820 | 0.2124 |
Abstract 704 scores less than a quarter of what abstract 856 scores, and its normalized margin is still only 0.21. Over all 225 queries, the normalized margin between BM25's first and second abstracts has a median of 0.0219, with quartiles 0.0086 and 0.0538.
The bound of Luan and colleagues
Lemma 1 (Luan et al., 2021). Let $A$ be a Gaussian or random-sign projection to $m$ dimensions and let $\epsilon = \mu(q, d_1, d_2) > 0$. Then the probability $\beta$ of a ranking error on this pair satisfies
$$\beta \le 4 \exp\!\left(-\frac{m}{2}\left(\frac{\epsilon^2}{2} - \frac{\epsilon^3}{3}\right)\right).$$
Solving for the dimension, an error probability of at most $\beta$ is guaranteed when
$$m \ge \frac{2}{\epsilon^2/2 - \epsilon^3/3}\,\ln\frac{4}{\beta},$$
and their Corollary 1 loosens this to the simpler sufficient condition $m > 12\,\epsilon^{-2} \ln(4/\beta)$, using $\epsilon^2/2 - \epsilon^3/3 \ge \epsilon^2/6$ for $\epsilon \le 1$.
The proof idea, as we read it in their appendix A.1. There are three steps, and the second and third can be written out in full.
Step 1 (cited). A random projection nearly preserves the squared length of any one fixed vector: for a fixed $\vec{x}$,
$$\Pr\!\left(\,\bigl\lvert\, \lvert A\vec{x} \rvert^2 - \lvert \vec{x} \rvert^2 \bigr\rvert > \epsilon \lvert \vec{x} \rvert^2\right) < 2\exp\!\left(-\frac{m}{2}\left(\frac{\epsilon^2}{2} - \frac{\epsilon^3}{3}\right)\right).$$
This is the concentration inequality behind the Johnson-Lindenstrauss lemma. Luan and colleagues take it from Achlioptas (2003, Lemma 5.1), which we have not opened, so it is cited here through them. Nearest neighbor search in high dimensions proves the Johnson-Lindenstrauss lemma, in the form of Dasgupta and Gupta, from a concentration inequality of this kind for Gaussian projections.
Step 2 (lengths to dot products). A dot product can be written with lengths alone. For any $\vec{x}$ and $\vec{y}$,
$$\vec{x} \cdot \vec{y} = \tfrac14\left(\lvert \vec{x} + \vec{y} \rvert^2 - \lvert \vec{x} - \vec{y} \rvert^2\right),$$
as expanding the two squares shows. The map $A$ is linear, so the same identity holds for $A\vec{x}$ and $A\vec{y}$ with $A(\vec{x} + \vec{y})$ and $A(\vec{x} - \vec{y})$ on the right. Suppose the projection preserves the squared lengths of the two fixed vectors $\vec{x} + \vec{y}$ and $\vec{x} - \vec{y}$ to within the relative error $\epsilon$. Then
$$\bigl\lvert A\vec{x} \cdot A\vec{y} - \vec{x} \cdot \vec{y} \bigr\rvert \le \tfrac{\epsilon}{4}\left(\lvert \vec{x} + \vec{y} \rvert^2 + \lvert \vec{x} - \vec{y} \rvert^2\right) = \tfrac{\epsilon}{2}\left(\lvert \vec{x} \rvert^2 + \lvert \vec{y} \rvert^2\right),$$
where the last step is the parallelogram law $\lvert \vec{x} + \vec{y} \rvert^2 + \lvert \vec{x} - \vec{y} \rvert^2 = 2\lvert \vec{x} \rvert^2 + 2\lvert \vec{y} \rvert^2$. By step 1 each of the two lengths fails with probability below $2\exp(\cdot)$, so both hold except with probability below $4\exp(\cdot)$. That is where the factor 4 comes from. For unit vectors the right side is $\epsilon$: the dot product is distorted by at most $\epsilon$.
Step 3 (distortion to ranking error). Scale the query and the difference vector to unit length, $\bar{q} = \vec{q}/\lvert \vec{q} \rvert$ and $\bar{\delta} = (\vec{d}_1 - \vec{d}_2)/\lvert \vec{d}_1 - \vec{d}_2 \rvert$, so that $\bar{q} \cdot \bar{\delta} = \epsilon$. Scaling by positive numbers does not change the sign of a dot product, so a ranking error is the event $A\bar{q} \cdot A\bar{\delta} \le 0$. The true value is $\epsilon$, so an error requires the projected dot product to be off by at least $\epsilon$. Now take any $\epsilon'$ with $0 < \epsilon' < \epsilon$ and apply steps 1 and 2 to the unit vectors $\bar{q}$ and $\bar{\delta}$ with $\epsilon'$ in place of $\epsilon$. Except with probability below $4\exp\!\left(-\frac{m}{2}(\epsilon'^2/2 - \epsilon'^3/3)\right)$ the dot product is distorted by at most $\epsilon'$, which is less than $\epsilon$, and then there is no error. So the error probability is below that quantity for every $\epsilon' < \epsilon$. The exponent is a continuous function of $\epsilon'$, and letting $\epsilon'$ tend to $\epsilon$ gives $\beta \le 4\exp\!\left(-\frac{m}{2}(\epsilon^2/2 - \epsilon^3/3)\right)$. $\blacksquare$ (given step 1)
The detour through $\epsilon'$ is needed for one case. Step 2 allows a distortion of exactly $\epsilon$ while both lengths are preserved, and a distortion of exactly $\epsilon$ is also enough for an error, so applying step 2 at $\epsilon$ itself would leave that case uncovered. The appendix of Luan and colleagues passes over it.
Their Lemma 2 extends the pairwise bound to a whole collection by the union bound. Let $D$ be the collection without the target document $d_1$, suppose every normalized margin $\mu(q, d_1, d_2)$ for $d_2$ in $D$ is positive, so that $d_1$ is strictly first in the sparse ranking, and let $\epsilon$ be the $r_0$-th smallest of those margins, with no other document at exactly that margin (they note that ties complicate the statement only slightly). Then $d_1$ stays in the top $r_0$ with probability at least $1 - \beta$ when
$$m \ge \frac{2}{\epsilon^2/2 - \epsilon^3/3}\,\ln\frac{4\,(\lvert D \rvert - r_0 + 1)}{\beta}.$$
The collection size enters only through a logarithm. The margin enters as $\epsilon^{-2}$. That asymmetry is the main message of the analysis: for this kind of encoder, the dimension needed is set far more by how fine the distinctions are than by how many documents there are.
The exact law for a Gaussian projection
Lemma 1 is an upper bound, and its authors examine its tightness only by experiment. For Gaussian projections the error probability can be found exactly, which shows what the bound gives away. The result below is derived here and is not in their paper.
Here is the plan. The projected score difference depends on $A$ only through two independent Gaussian vectors, and the event that it is negative turns out to be the event that a Student $t$ variable falls below a fixed point.
Proposition. Let $A$ be an $m \times V$ matrix of independent normal entries with mean 0 and variance $1/m$, and let $\epsilon = \mu(q, d_1, d_2)$ with $0 < \epsilon < 1$. Then
$$\Pr\left(A\vec{q} \cdot A\vec{d}_1 \le A\vec{q} \cdot A\vec{d}_2\right) = \Pr\!\left(T_m \le -\epsilon\sqrt{\frac{m}{1 - \epsilon^2}}\right),$$
where $T_m$ has Student's $t$ distribution with $m$ degrees of freedom.
Proof. With $\bar{q}$ and $\bar{\delta}$ as in step 3, the error is the event $A\bar{q} \cdot A\bar{\delta} \le 0$. Split $\bar{\delta}$ into its part along $\bar{q}$ and the rest: $\bar{\delta} = \epsilon\,\bar{q} + \sqrt{1 - \epsilon^2}\,\vec{u}$, where $\vec{u}$ is a unit vector orthogonal to $\bar{q}$. (Such a $\vec{u}$ exists because $\bar{\delta}$ has length 1 and component $\epsilon$ along $\bar{q}$.) Write $\vec{g} = A\bar{q}$ and $\vec{h} = A\vec{u}$. Each coordinate of $\vec{g}$ is a combination of one row of $A$ with the weights $\bar{q}$, so it is normal with mean 0 and variance $\lvert \bar{q} \rvert^2/m = 1/m$, and likewise for $\vec{h}$. The covariance of the matching coordinates of $\vec{g}$ and $\vec{h}$ is $(\bar{q} \cdot \vec{u})/m = 0$, and jointly normal variables with zero covariance are independent. Different rows of $A$ are independent. So $\vec{g}$ and $\vec{h}$ are independent vectors of $m$ independent normal coordinates with variance $1/m$. By linearity,
$$A\bar{q} \cdot A\bar{\delta} = \epsilon\,\lvert \vec{g} \rvert^2 + \sqrt{1 - \epsilon^2}\;\vec{g} \cdot \vec{h}.$$
Given $\vec{g}$, the product $\vec{g} \cdot \vec{h}$ is a sum of independent normal terms and is normal with mean 0 and variance $\lvert \vec{g} \rvert^2/m$. So $\vec{g} \cdot \vec{h} = \lvert \vec{g} \rvert\,Z/\sqrt{m}$ with $Z$ standard normal and independent of $\vec{g}$. Put $X = m\lvert \vec{g} \rvert^2$, a sum of $m$ squared standard normal variables, which has the chi-squared distribution with $m$ degrees of freedom. Then $\lvert \vec{g} \rvert = \sqrt{X/m}$, and the error event is
$$\epsilon\,\frac{X}{m} + \sqrt{1 - \epsilon^2}\,\sqrt{\frac{X}{m}}\,\frac{Z}{\sqrt{m}} \le 0 \iff \frac{Z}{\sqrt{X/m}} \le -\epsilon\sqrt{\frac{m}{1 - \epsilon^2}},$$
after dividing by $\sqrt{1 - \epsilon^2}\,X/m^{3/2}$, which is positive with probability 1. A standard normal variable divided by the square root of an independent chi-squared variable over its degrees of freedom is the definition of Student's $t$, as the chi-squared and t distributions sets out. $\blacksquare$
Two consequences follow at once. First, the error probability depends on the pair only through $\epsilon$: not on the vocabulary size, nor on the lengths of the vectors. Second, for large $m$ the $t$ distribution is close to the standard normal, so the error is close to $\Phi\!\left(-\epsilon\sqrt{m/(1 - \epsilon^2)}\right)$, with $\Phi$ the standard normal distribution function. An error of at most $\beta$ then needs about
$$m \approx z_\beta^2\,\frac{1 - \epsilon^2}{\epsilon^2}$$
dimensions, where $z_\beta$ is the point the standard normal exceeds with probability $\beta$. For $\beta = 0.05$, $z_\beta^2 = 2.71$. Lemma 1's sufficient dimension for small $\epsilon$ is $4\ln(4/\beta)/\epsilon^2$, which is $17.53/\epsilon^2$ at $\beta = 0.05$, and Corollary 1's is $52.58/\epsilon^2$. All three scale as $\epsilon^{-2}$. So the bound has the right shape, and its constant is about six and a half times the true one at this $\beta$.
The script checks the proposition on the real pair of abstracts 856 and 391 ($\epsilon = 0.0884$) by drawing 20,000 Gaussian matrices (seed 185) and projecting the actual BM25 vectors:
| Dimension $m$ | Simulated error rate | Exact, from the $t$ law | Bound of Lemma 1 |
|---|---|---|---|
| 64 | 0.239 | 0.240 | 3.556 (no information) |
| 256 | 0.078 | 0.078 | 2.498 (no information) |
A bound above 1 on a probability says nothing. At $m = 2{,}048$ the bound is 0.093, while the exact error is 30.6 in a million. The dimensions needed to hold the pairwise error to 0.05 for the three margins of query 185 are:
| Pair (rank of the lower abstract) | Margin $\epsilon$ | Exact smallest $m$ | Lemma 1 | Corollary 1 |
|---|---|---|---|---|
| 2 | 0.0294 | 3,124 | 20,649 | 60,730 |
| 10 | 0.0884 | 346 | 2,383 | 6,728 |
| 100 | 0.2124 | 60 | 453 | 1,166 |
Lemma 1 asks for 6.6 to 7.5 times the exact dimension in these three cases.
Example (reading the first row). To keep abstract 856 ahead of abstract 857 nineteen times in twenty, a Gaussian projection needs 3,124 dimensions. The vocabulary has 4,803. For the closest pairs, then, a random projection saves almost nothing over storing the sparse vector itself, and the bound's 20,649 exceeds the vocabulary, which shows only that a sufficient condition can be far from necessary: the identity map on 4,803 dimensions makes no errors at all.
All of Cranfield, projected
The table above concerns single pairs. The script also projects every BM25 vector of the collection and asks, for each of the 225 queries, whether BM25's first abstract is still first, and whether it is still in the top 10. Each dimension is run with 30 seeds (1 to 30); the cells give the median share of queries over the seeds, with the quartiles in brackets.
| Dimension $m$ | BM25's first abstract still first | Still in the top 10 |
|---|---|---|
| 64 | 0.089 [0.076, 0.102] | 0.300 [0.280, 0.319] |
| 128 | 0.213 [0.204, 0.222] | 0.527 [0.494, 0.547] |
| 384 | 0.451 [0.436, 0.477] | 0.829 [0.810, 0.840] |
| 1,024 | 0.624 [0.604, 0.636] | 0.956 [0.943, 0.968] |
| 4,096 | 0.791 [0.783, 0.800] | 1.000 [0.996, 1.000] |
At $m = 384$, the dimension of this unit's encoder, a random projection keeps BM25's first abstract first for 45% of the queries. Even at 4,096 dimensions, most of the vocabulary's 4,803, one query in five loses its first abstract, because first and second place are so often separated by a margin near 0.02. Lemma 2's guarantee for query 185 is correspondingly large: with $\lvert D \rvert = 1{,}399$ and the smallest margin 0.0294, keeping abstract 856 first with probability 0.95 is guaranteed from 54,780 dimensions; keeping it in the top 10, where the tenth smallest margin is 0.0904, from 6,053.
Example (a common misreading). "A 384-dimensional encoder can therefore reproduce BM25 on under half the queries." The experiment does not show that. It shows what a random linear map of BM25's vectors does. A trained, non-linear encoder is a different function, and Luan and colleagues list this among the caveats of their analysis: it "might be possible to eliminate ranking errors without achieving low inner product distortion", and real documents may be easier to encode than the worst case. What the analysis supplies is a scaling law, dimension proportional to $\epsilon^{-2}$, and a reason to expect fine lexical distinctions to be the first thing a compressed representation loses.
Why long documents are harder
The margin connects the dimension to document length. For the Boolean overlap score, where $\vec{q}$ and $\vec{d}$ have coordinates 0 or 1 and the score counts shared terms, the connection can be made exact.
Corollary 2 (Luan et al., 2021). Let $L_Q = \lvert \vec{q} \rvert^2$ be the number of distinct terms of the query and $L_D$ the largest number of distinct terms in any document. If $m \ge 24\,L_Q L_D \ln(4/\beta)$, then for every pair of documents with $\vec{q} \cdot \vec{d}_1 > \vec{q} \cdot \vec{d}_2$ the probability of a ranking error is at most $\beta$.
Proof (theirs, written out). Scores are whole numbers, so two documents with different scores differ by at least 1: $\vec{q} \cdot (\vec{d}_1 - \vec{d}_2) \ge 1$. The coordinates of both documents are 0 or 1, so each coordinate of $\vec{d}_1 - \vec{d}_2$ is $-1$, 0 or 1, and it is nonzero only where one of the documents has a term. Hence $\lvert \vec{d}_1 - \vec{d}_2 \rvert^2 \le \lvert \vec{d}_1 \rvert^2 + \lvert \vec{d}_2 \rvert^2 \le 2L_D$. The normalized margin is therefore at least
$$\epsilon_{\min} = \frac{1}{\sqrt{L_Q}\,\sqrt{2L_D}} = (2L_QL_D)^{-1/2}.$$
Take any pair, with margin $\epsilon \ge \epsilon_{\min}$. By Lemma 1 and the inequality $\epsilon^2/2 - \epsilon^3/3 \ge \epsilon^2/6$ used for Corollary 1, its error probability is at most $4\exp(-m\epsilon^2/12)$, which is at most $4\exp(-m\epsilon_{\min}^2/12)$. That is at most $\beta$ exactly when $m \ge 12\,\epsilon_{\min}^{-2}\ln(4/\beta) = 24\,L_QL_D\ln(4/\beta)$. $\blacksquare$
(Corollary 1 was stated with a strict inequality on $m$ and this corollary with $\ge$. Going back to Lemma 1, as here, shows that $\ge$ is enough.)
The sufficient dimension grows in proportion to the number of distinct terms in the longest document. For BM25 no such closed form exists, because inverse document frequencies let two documents come arbitrarily close in score. Luan and colleagues measure it instead. On the TREC-CAR collection they report that normalized margins fall as documents lengthen (their Figure 3a), and that the smallest normalized margin they observed was $6.8 \times 10^{-6}$ for BM25 against 0.0169 for the Boolean score.
They then test trained encoders on a task built to need exact overlap: retrieving the Wikipedia passage that contains a given run of 5 to 25 words, from a collection of three million documents that includes synthetic distractors, which in their words "contain the large majority of words" of the query "but differ by one or two tokens". The distractors are what make exact overlap necessary. Their Table 3 reports mean reciprocal rank at 10, in percent, by the maximum passage length in tokens:
| Model | 50 | 100 | 200 | 400 |
|---|---|---|---|---|
| BERT bi-encoder, 768 dimensions | 90.2 | 85.6 | 72.9 | 63.0 |
| BERT bi-encoder, 32 dimensions | 70.1 | 53.2 | 34.0 | 27.6 |
| BM25, unigrams | 92.1 | 88.6 | 84.6 | 81.8 |
| BM25, unigrams and bigrams | 98.0 | 97.1 | 95.9 | 94.5 |
The trained bi-encoder falls behind BM25 at every length, falls faster as passages lengthen, and falls faster still at low dimension. That is the pattern the random-projection analysis predicts. On their second task, finding passages that answer Natural Questions queries, the same 768-dimensional bi-encoder is ahead of BM25 at every length (44.2 against 30.1 at length 50 and 32.2 against 30.1 at length 400, recall within 400 tokens), since that task rewards matching meaning. Their own reading is that the theory makes no direct prediction for it.
The same test on this site
The containing-passage test can be run on this site at small scale. The collection is the site's 11,264 passages, cut at headings into runs of about 150 to 400 words as dense passage retrieval describes. For each of 30 seeds the script draws 400 passages and, from each, a run of 5 to 12 consecutive words. The run is taken from the part of the passage the encoder actually reads (see the next paragraph) and not from the title and heading that are prefixed to it. The query is that run of words, and a system succeeds when it ranks the source passage first among all 11,264. The lexical system is BM25 over the passages' lowercased words, with no stemming and no stop list. The dense system is the unit's encoder with cosine scoring.
| System | Passages | Recall@1, median [quartiles] | MRR@10, median [quartiles] |
|---|---|---|---|
| BM25 | all | 0.786 [0.773, 0.807] | 0.845 [0.837, 0.863] |
| BM25 | under 150 words | 0.880 [0.867, 0.897] | 0.915 [0.911, 0.931] |
| BM25 | 150 to 299 words | 0.794 [0.774, 0.803] | 0.850 [0.835, 0.861] |
| BM25 | 300 words or more | 0.699 [0.671, 0.730] | 0.778 [0.760, 0.798] |
| Dense, $m = 384$ | all | 0.165 [0.152, 0.170] | 0.219 [0.206, 0.229] |
| Dense, $m = 384$ | under 150 words | 0.215 [0.197, 0.243] | 0.279 [0.251, 0.302] |
| Dense, $m = 384$ | 150 to 299 words | 0.130 [0.109, 0.153] | 0.176 [0.164, 0.206] |
| Dense, $m = 384$ | 300 words or more | 0.133 [0.117, 0.147] | 0.197 [0.191, 0.222] |
Given a run of 5 to 12 consecutive words of a passage, BM25 finds the passage about four times in five and the dense model about one time in six. Both do better on short passages. The dense model was trained to match meanings and not to detect containment, and a run of words cut from the middle of a sentence is an odd query, so this is a test of fidelity in the sense of Luan and colleagues and not of usefulness. It is also easier than theirs, since this collection has no distractors built to differ from a passage by a token or two. Of BM25's own 2,542 misses over the 30 seeds, 206 are cases in which the passage it ranked first contains the very same run of words, so the source passage was not the only right answer. The other misses were not classified.
A second limit showed up while building the test. The pinned encoder reads at most 256 word pieces. Of the site's 11,264 passages, 6,721 (59.7%) are longer than that as encoded, and the median passage has 293 word pieces. For most passages, then, the vector describes only the beginning. A run of words from the unread tail cannot be found by the dense system at all, which is why the test draws only from the part that is read. An input window is a limit of the particular encoder and not of single vectors, but it bounds every dense result on this site reported in this unit.
A counting limit: which result sets a dimension can return
The projection analysis asks whether an encoder can copy one ranker. A different question is how many distinct answers the geometry allows at all. Weller, Boratko, Naim and Lee (2026) answer it with a volume argument, short enough to give in full. In the notation of this unit, the passages have unit vectors $\vec{p}_1, \dots, \vec{p}_n \in \mathbb{R}^m$ and queries are unit vectors. A set $S$ of $k$ passages is realized with margin $\gamma$ if some unit query vector $\vec{u}_S$ scores every passage in $S$ at least $2\gamma$ above every passage outside it:
$$\min_{i \in S}\,\vec{u}_S \cdot \vec{p}_i \;\ge\; \max_{j \notin S}\,\vec{u}_S \cdot \vec{p}_j + 2\gamma.$$
Theorem (Weller et al., 2026, Theorem 1). If every set of $k$ of the $n$ passages is realized with margin $\gamma$, where $1 \le k < n$, then
$$\binom{n}{k} \le \left(1 + \frac{1}{\gamma}\right)^{m}, \qquad\text{so}\qquad m \ge \frac{\ln\binom{n}{k}}{\ln(1 + 1/\gamma)}.$$
Proof (theirs, in our words). Take two different sets $S$ and $T$ of $k$ passages. They have the same size, so some passage $i$ is in $S$ and not in $T$, and some passage $j$ is in $T$ and not in $S$. The query for $S$ prefers $i$ to $j$ by the margin, and the query for $T$ prefers $j$ to $i$:
$$\vec{u}_S \cdot (\vec{p}_i - \vec{p}_j) \ge 2\gamma, \qquad \vec{u}_T \cdot (\vec{p}_j - \vec{p}_i) \ge 2\gamma.$$
Adding the two gives $(\vec{u}_S - \vec{u}_T) \cdot (\vec{p}_i - \vec{p}_j) \ge 4\gamma$. By the Cauchy-Schwarz inequality the left side is at most $\lvert \vec{u}_S - \vec{u}_T \rvert\,\lvert \vec{p}_i - \vec{p}_j \rvert$, and two unit vectors are at most 2 apart, so $\lvert \vec{u}_S - \vec{u}_T \rvert \ge 2\gamma$. The query vectors of different sets are therefore at least $2\gamma$ apart, and the open balls of radius $\gamma$ around them do not overlap. Each query vector has length 1, so each of these balls lies inside the ball of radius $1 + \gamma$ about the origin. The volume of a ball of radius $r$ in $\mathbb{R}^m$ is a constant times $r^m$. Comparing volumes, $\binom{n}{k}\,\gamma^m \le (1 + \gamma)^m$, which is the first claim, and taking logarithms gives the second. $\blacksquare$
The script reproduces the authors' table of this bound for $\gamma = 0.1$ and adds this site:
| Passages $n$ | $k$ | Smallest $m$ allowed by the bound |
|---|---|---|
| 11,264 (this site) | 2 | 8 |
| 11,264 (this site) | 10 | 33 |
| 11,264 (this site) | 100 | 238 |
| $10^6$ | 10 | 52 |
| $10^9$ | 100 | 713 |
What the theorem does and does not say needs care. It is a necessary condition for returning every possible set of $k$ passages, each with a margin. No query load asks for every set. So the theorem does not say that 384 dimensions fail on this site; for $k = 10$ the bound, 33, is far below 384. It says that the number of distinct top-$k$ answers is capped by the dimension, and that the cap matters as queries combine passages freely, for instance through conjunctions of unrelated conditions. The authors call it "an extreme lower bound", and their experiment with freely optimized vectors (no encoder, vectors fitted directly to the test relevance) needed more than 18 dimensions for 100 passages and $k = 2$, where the bound says 4.
They also built a collection, LIMIT, to show the cap in natural language: 50,000 short documents of the form "Jon Durben likes Quokkas and Apples", 1,000 queries of the form "Who likes Quokkas?", two relevant documents per query. The relevant pairs are 1,000 of the 1,035 pairs that can be formed from 46 of the documents, 46 being the smallest number whose pairs exceed 1,000; the other documents are relevant to no query. They report that embedding models "struggle to reach even 20% recall@100" on it and that BM25 comes "close to perfect scores". On a smaller version that keeps only the 46 documents, they replaced every liked item by a synonym and report that there BM25 "drops the most" and falls below the neural models. All three statements are theirs (their section 5 and Figures 3 and 6), for the models they tested as of their paper, and the last one is the other half of the picture: a lexical retriever has the dimensions and lacks the synonyms.
Crowding on the sphere
A third geometric limit concerns false positives. Reimers and Gurevych (2021) ask how likely an unrelated vector is to score above the relevant one, and give the answer for vectors spread uniformly over the unit sphere. If the relevant passage has cosine $c$ with the query, a random unit vector in $\mathbb{R}^m$ exceeds it with probability
$$\Pr(\cos > c) = \tfrac12\,I_{1 - c^2}\!\left(\tfrac{m - 1}{2}, \tfrac12\right),$$
where $I_x(a, b)$ is the regularized incomplete beta function (their equation 1, which they take from a formula for the area of a spherical cap; the script checks it by simulation at $m = 32$). The probability falls quickly with the dimension and multiplies with the size of the index:
| Dimension $m$ | $\Pr(\cos > 0.3)$ | Expected such vectors among one million |
|---|---|---|
| 32 | 0.045 | 44,920 |
| 64 | 0.0076 | 7,592 |
| 128 | 0.00028 | 276.1 |
| 384 | $9.5 \times 10^{-10}$ | 0.0009 |
On this model 384 dimensions leave ample room. Real embeddings are not spread uniformly, though. Cosine similarity shows that random unit vectors in $m$ dimensions have cosines with mean 0 and standard deviation $1/\sqrt{m}$, which is 0.051 for $m = 384$. Random pairs of this site's passage vectors (200,000 pairs, seed 20261117) have a mean cosine of 0.160 and a standard deviation of 0.124. A share 0.134 of the pairs exceed 0.3, and a share 0.011 exceed 0.5. The vectors occupy a small part of the sphere, as one would expect of passages from one site about a few subjects, and the effective room is much less than the nominal dimension suggests. Reimers and Gurevych report the consequence they measured: as the index grows, the quality of dense retrieval falls faster than that of sparse retrieval, and faster at lower dimensions.
Outside the training domain: BEIR
The limits so far are geometric. The best-known measured limit is statistical: an encoder is a trained function, and it is accurate where its training data was. Thakur, Reimers, Rücklé, Srivastava and Gurevych (2021) assembled BEIR to test that. It has 18 English datasets from nine retrieval tasks, evaluated zero-shot: the systems were trained elsewhere, most of them on MS MARCO, and are tested without further training. The measure is nDCG@10. The table below is the paper's Table 2 (arXiv version 4) for BM25, the three dense retrievers, the late-interaction model ColBERT, and BM25 followed by a cross-encoder re-ranker.
| Dataset | BM25 | DPR | ANCE | TAS-B | ColBERT | BM25 + cross-encoder |
|---|---|---|---|---|---|---|
| TREC-COVID | 0.656 | 0.332 | 0.654 | 0.481 | 0.677 | 0.757 |
| BioASQ | 0.465 | 0.127 | 0.306 | 0.383 | 0.474 | 0.523 |
| NFCorpus | 0.325 | 0.189 | 0.237 | 0.319 | 0.305 | 0.350 |
| NQ | 0.329 | 0.474 | 0.446 | 0.463 | 0.524 | 0.533 |
| HotpotQA | 0.603 | 0.391 | 0.456 | 0.584 | 0.593 | 0.707 |
| FiQA-2018 | 0.236 | 0.112 | 0.295 | 0.300 | 0.317 | 0.347 |
| Signal-1M (RT) | 0.330 | 0.155 | 0.249 | 0.289 | 0.274 | 0.338 |
| TREC-NEWS | 0.398 | 0.161 | 0.382 | 0.377 | 0.393 | 0.431 |
| Robust04 | 0.408 | 0.252 | 0.392 | 0.427 | 0.391 | 0.475 |
| ArguAna | 0.315 | 0.175 | 0.415 | 0.429 | 0.233 | 0.311 |
| Touché-2020 | 0.367 | 0.131 | 0.240 | 0.162 | 0.202 | 0.271 |
| CQADupStack | 0.299 | 0.153 | 0.296 | 0.314 | 0.350 | 0.370 |
| Quora | 0.789 | 0.248 | 0.852 | 0.835 | 0.854 | 0.825 |
| DBPedia | 0.313 | 0.263 | 0.281 | 0.384 | 0.392 | 0.409 |
| SCIDOCS | 0.158 | 0.077 | 0.122 | 0.149 | 0.145 | 0.166 |
| FEVER | 0.753 | 0.562 | 0.669 | 0.700 | 0.771 | 0.819 |
| Climate-FEVER | 0.213 | 0.148 | 0.198 | 0.228 | 0.184 | 0.253 |
| SciFact | 0.665 | 0.318 | 0.507 | 0.643 | 0.671 | 0.688 |
Counting from the table as printed, DPR is above BM25 on 1 of the 18 datasets (NQ, one of the datasets it was trained on), ANCE on 4 and TAS-B on 8. ColBERT is above BM25 on 9 and the re-ranking pipeline on 16, the two counts the paper's text also gives. The unweighted means over the 18 datasets are 0.423 for BM25, 0.237 for DPR, 0.389 for ANCE, 0.415 for TAS-B, 0.431 for ColBERT and 0.476 for the re-ranker. (The table's own last row, "Avg. Performance vs. BM25", gives −47.7% for DPR, −7.4% for ANCE and −2.8% for TAS-B. A mean of relative differences recomputed from the printed scores gives −42.2%, −7.2% and +0.6%, so that row was evidently computed in some other way; the counts and means here are computed from the printed scores.)
The authors' conclusions, in their words, are that "BM25 is a robust baseline", that re-ranking and late-interaction models "on average achieve the best zero-shot performances" at high computational cost, and that dense retrievers "perform strongly on certain datasets, while on many other datasets perform significantly worse than BM25". They single out BioASQ as a large shift of domain and Touché-2020 as a shift of task. The rows bear that out: on BioASQ, ANCE scores 0.306 against BM25's 0.465, and on Quora, where queries and documents are both short questions, it scores 0.852 against 0.789.
Two cautions belong with the table. First, it describes the models of 2021 and says nothing about later ones; evaluating embedding models takes up what such benchmark scores do and do not show. Second, the authors found that the benchmark itself leans toward lexical systems. Relevance judgments are made on a pool of documents that some systems retrieved (see relevance judgments), unjudged documents count as not relevant, and many of BEIR's datasets were pooled with lexical retrievers. On TREC-COVID they measured the share of each system's top 10 that had never been judged: 6.4% for BM25, 14.4% for ANCE and 31.8% for TAS-B. After they judged the missing documents themselves, ANCE rose from 0.654 to 0.735, above BM25.
A separate study isolates one cause of out-of-domain failure. Sciavolino, Zhong, Lee and Chen (2021) wrote simple questions about entities from Wikidata facts, such as "Where was Arve Furset born?". They report that DPR trained on Natural Questions retrieves the answer in the top 20 for 49.7% of them, averaged over the kinds of question, against 72.0% for BM25 (the figures of version 3 of the arXiv paper; the version in the EMNLP proceedings gives 71.2% for BM25), and that the dense retriever does well on common entities and degrades on rare ones. A rare name is a rare token for BM25, which is exactly what its inverse document frequency rewards. For an encoder it is a string that training seldom or never showed it.
This site's queries
The site's own search engine is the lexical side of the comparison: BM25F over titles, summaries, headings and bodies, as how this search works describes. The dense side embeds the 11,264 passages and scores a page by its best passage. The site has two sets of test queries, and the same caution about pools applies to one of them.
The 60 topical queries have graded judgments, and the pool that was judged is as narrow as a pool can be: for each query, the top 20 pages of the site's own BM25F ranker and nothing else (tools/search/eval/pool.tsv). BM25F's nDCG@10 on them is 0.753 and the dense run's is 0.626. But 97.8% of the pages in BM25F's top tens have a judgment, against 61.0% for the dense run, and the two top tens share only 4.6 pages on average. Nearly four in ten of the dense run's results are counted as not relevant without anyone having looked. On the 12 queries where both top tens are at least 90% judged, which are the queries on which the dense run mostly re-orders BM25F's own top 20, the scores are 0.896 and 0.828. That comparison is therefore biased against the dense run by an unknown amount, the effect the BEIR authors measured on TREC-COVID, and this article does not rest on it.
The 200 known-item queries have no such bias. Each was written for one target page, and the only question is where that page is ranked. They have a different bias, stated in the evaluation's own notes: they were written from the pages' summaries, so they reuse the pages' words, which favors a lexical ranker.
| Measure, 200 known-item queries | BM25F | Dense |
|---|---|---|
| Mean reciprocal rank | 0.942 | 0.795 |
| Target ranked first | 0.905 | 0.705 |
| Target in the top 10 | 1.000 | 0.950 |
The difference in mean reciprocal rank is 0.147, with a 95% bootstrap interval of 0.102 to 0.192 over queries. Both systems rank the target first for 136 queries, BM25F alone for 45, the dense run alone for 5, and neither for 14. The dense run's rank is better than BM25F's on 7 queries and worse on 53.
Queries the lexical engine answers and the dense model misses
For 8 queries BM25F ranks the target first and the dense run ranks it outside the top 10. The table identifies each by its number in the evaluation's query file (tools/search/eval/known_items.tsv) and by the kind of word in it that picks out the target. Neither the queries nor their deciding words are quoted, because a page that repeats the rare words of a test query becomes a match for that query and would change the evaluation it describes.
| Query | What picks out the target | Target page | Dense rank |
|---|---|---|---|
| K052 | a count of kinds, in a general description | Why Data Science | 55 |
| K116 | a month and year | System Card: Claude Sonnet 4.6 | 26 |
| K007 | a number, spelled out | Automated Alignment Researchers | 25 |
| K113 | a month and year | System Card: Claude Haiku 5.5 | 22 |
| K069 | a model name with its version | Welfare Regard in Multi-Agent Systems | 16 |
| K023 | a model name with its version | Sabotage Evaluations for Frontier Models | 14 |
| K075 | a year | Garcon | 12 |
| K096 | two proper nouns | Designing more efficient quantum circuits with Claude | 12 |
In seven of the eight, the page is one of many on closely related subjects, and what picks it out is a date, a model name, a number or a proper noun. The site has a system card for each of several models, and their passages are near one another in the embedding space, as near-duplicates should be. A rare proper noun, such as one of the two in K096 that occurred in a single page of the site when the experiment was run, is decisive for BM25F and is one detail among many for the encoder. This is the exact-match failure in the form this site produces it: the dense model finds the right neighborhood and cannot tell the houses apart. It is the same shape as the small normalized margin: two long texts that differ in one term the query cares about. The eighth, K052, is of another kind, a general description that many pages about data fit.
A simple count does not capture the pattern. Queries that contain a term found in at most 10 pages are easier for both systems (target first for 0.958 of them under BM25F and 0.823 under the dense run, against 0.856 and 0.596 for the other queries), perhaps because a rare term usually comes with other specific words. Queries containing a digit put the target in the dense run's top 10 less often than the rest, 0.872 against 0.969, with 39 such queries, which is a small sample. The failures seen here are among near-duplicate pages and are not a property of every rare term.
Queries the dense model answers and the lexical engine misses
In the other direction there are 5 queries for which the dense run ranks the target first and BM25F does not:
| Query | What the query does | Target page | BM25F rank |
|---|---|---|---|
| K169 | lists the subjects of a course unit | Text Clustering (unit page) | 4 |
| K172 | lists the subjects of a course unit | The Vector Space Model (unit page) | 6 |
| K173 | asks why a product of two negatives is positive, from the axioms | Basic Properties of Rings | 2 |
| K175 | lists the subjects of a course unit | Congruence and Modular Arithmetic (unit page) | 2 |
| K176 | describes congruence without the word, and names an arithmetic check that the page calls something else | Congruence Modulo n | 2 |
Three of these targets are short unit pages. The search evaluation's failure analysis (tools/search/eval/failure-analysis.md) had already classed such misses: a unit page loses to one of its own articles, which repeats the query's specific terms many times and has one of them in its title. It classed K176 as a vocabulary mismatch, since the page describes the check in its own terms and never uses the query's name for it. The dense model is not counting repeated terms, and it places a description near the page it describes. On the four misses that the analysis classed as vocabulary mismatch (K106, K107, K162 and K176), the dense run ranks the target at 4, 3, 3 and 1, where BM25F ranks it at 10, 2, 8 and 2: better in three of the four. On the topical queries the largest gains of the dense run are of the same kind: a question about how an interval estimate should be read (T56, 0.843 against BM25F's 0.573) and one about pursuing more than one goal at a time in optimization (T48, 0.782 against 0.529), both scored with unjudged pages counted against the dense run. These are the vocabulary mismatches that query expansion works around and that the course met as a limit of the vector space model.
When BM25 wins
Putting the theory and the measurements together, a lexical ranker is the better first stage, or a necessary partner, in these conditions:
- The query's exact tokens decide relevance. Names, numbers, codes, quoted phrases, and any query that is a fragment of the text: the containing-passage test here (0.786 against 0.165, on a test built to need exact overlap and not on real queries), the entity questions of Sciavolino and colleagues, LIMIT.
- The collection is unlike the encoder's training data. BEIR's biomedical and argument datasets for the encoders of its time.
- Many documents are near-duplicates that differ in one detail. This site's system cards and course units.
- Documents are long. Margins shrink with length (Corollary 2, and the measurements of Luan and colleagues), and an encoder with a fixed input window does not read the tail at all.
- The index is very large and the dimension small. The crowding result of Reimers and Gurevych.
A dense retriever is the better first stage where queries and documents use different words for the same thing, and where the encoder was trained on similar text: Natural Questions in the table of Luan and colleagues and in BEIR, Quora's paraphrased questions, and the handful of descriptive queries above.
Since the two fail on different queries, the usual answer is to use both. Luan and colleagues keep several vectors per document, a multi-vector model, and add BM25's score to that model's score with a learned weight. They report that the hybrid improves on both of its parts, and by more over the multi-vector model as documents lengthen. Those designs are the subject of the unit on neural ranking: hybrid retrieval, rank fusion, late interaction, which keeps one vector per token, and learned sparse retrieval, which keeps the vocabulary's dimensions and learns the weights.
What is proved here, what is cited, and what the experiments show
Proved on this page. That BM25 is a dot product of a query vector and a document vector in $\mathbb{R}^V$. Steps 2 and 3 of Lemma 1, from lengths to dot products and from distortion to ranking error. The exact error probability of a Gaussian projection as a Student $t$ probability, and its large-$m$ form. Corollary 2 for the Boolean score, given Lemma 1. The counting bound of Weller and colleagues.
Cited. The concentration inequality of step 1 (through Luan and colleagues; not opened). The spherical-cap formula (through Reimers and Gurevych). Every measurement on TREC-CAR, Wikipedia, Natural Questions, MS MARCO, BEIR, EntityQuestions and LIMIT, each as its paper reports it, with the table or figure named.
Shown by the experiments, for these collections and this encoder only. The simulated error rates that match the $t$ law. The share of Cranfield queries whose first BM25 abstract survives a random projection. The containing-passage results on this site's passages. The distribution of cosines among the site's passage vectors. The known-item and topical comparisons of BM25F with one small pretrained encoder, used as shipped, on queries written by a model from the pages' summaries.
Worked problems
The unit has no course assignments, so the problems are posed on small exact cases and on the collections above; the script recomputes every number.
Problem 1. A query has the vector $\vec{q} = (1, 1, 0, 0)$ and two documents have $\vec{d}_1 = (1, 1, 1, 0)$ and $\vec{d}_2 = (1, 0, 1, 1)$, scored by dot product. Find the normalized margin. For a Gaussian projection, find the exact error probability at $m = 4$, 16 and 64, the smallest $m$ with error at most 0.05, and the dimensions Lemma 1 and Corollary 1 call sufficient.
The scores are $\vec{q} \cdot \vec{d}_1 = 2$ and $\vec{q} \cdot \vec{d}_2 = 1$. The difference vector is $\vec{d}_1 - \vec{d}_2 = (0, 1, 0, -1)$ with length $\sqrt2$, and $\lvert \vec{q} \rvert = \sqrt2$, so
$$\epsilon = \frac{2 - 1}{\sqrt2 \cdot \sqrt2} = \frac12.$$
By the proposition the error probability is $\Pr\!\left(T_m \le -\tfrac12\sqrt{m/(1 - \tfrac14)}\right) = \Pr\!\left(T_m \le -\sqrt{m/3}\right)$. For $m = 4$ the point is $-1.155$ and the probability is 0.156. For $m = 16$ it is $-2.309$ and the probability is 0.017. For $m = 64$ it is $-4.619$ and the probability is 9.6 in a million, where the bound of Lemma 1 gives 0.278. The smallest $m$ with error at most 0.05 is 10. Lemma 1 requires $2 \ln(80)/(\tfrac18 - \tfrac1{24}) = 24 \ln 80 = 105.2$, so 106 dimensions. Corollary 1 requires $12 \cdot 4 \cdot \ln 80 = 210.3$, so 211. The vectors have only four coordinates, so both sufficient dimensions exceed the dimension of the space they are compressing: bounds of this kind are informative only when the margin is small and the original dimension large.
Problem 2. Apply Corollary 2 to Cranfield query 185 under the Boolean overlap score, with $\beta = 0.05$.
After stemming and stop-word removal the query has 4 distinct stems, so $L_Q = 4$. The abstract with the most distinct stems has 212, so $L_D = 212$. The corollary's dimension is
$$24 \cdot 4 \cdot 212 \cdot \ln 80 = 20{,}352 \times 4.382 = 89{,}183.$$
The corollary asks for 89,183 dimensions. The vocabulary has 4,803 stems, and the sparse vectors in that many dimensions make no errors. The corollary's value is in its form, a dimension proportional to $L_Q L_D$, and not in this number. The smallest possible margin it rests on is $(2 \cdot 4 \cdot 212)^{-1/2} = 0.0243$, and the exact law says a Gaussian projection would need about $2.71/0.0243^2 \approx 4{,}600$ dimensions to hold the error on such a pair to 0.05, again about the size of the vocabulary.
Problem 3. Four passages, any two of which might be the pair a query wants ($n = 4$, $k = 2$). What does the counting bound require at margin $\gamma = \tfrac12$? Is the dimension it gives enough?
There are $\binom42 = 6$ pairs. The bound requires $6 \le (1 + 2)^m = 3^m$, so $m \ge \ln 6/\ln 3 = 1.631$, that is, $m \ge 2$.
Two dimensions are not enough, at this margin or any other. In the plane, unit vectors lie on a circle, and the score $\vec{u} \cdot \vec{p}$ is the cosine of the angle between query and passage, which decreases as the angle grows. The two best passages for a query are therefore the two nearest to it along the circle, one on each side or two on the same side, and in either case they are neighbors on the circle. Four points on a circle have four neighboring pairs, so only 4 of the 6 pairs can ever be returned. The bound is necessary and not sufficient.
Three dimensions are enough. Place the four passages at the corners of a regular tetrahedron, where any two unit vectors have dot product $-\tfrac13$. For the pair $\{i, j\}$ take the query along $\vec{p}_i + \vec{p}_j$, whose length is $\sqrt{2 + 2(-\tfrac13)} = 2/\sqrt3$. Its score for $\vec{p}_i$ and for $\vec{p}_j$ is $(1 - \tfrac13)/(2/\sqrt3) = 1/\sqrt3 = 0.577$. Its score for each of the other two is $(-\tfrac13 - \tfrac13)/(2/\sqrt3) = -0.577$. The gap is $1.155 = 2\gamma$ with $\gamma = 0.577 \ge \tfrac12$. So $m = 3$ realizes all six pairs at the required margin, and the true answer is 3 where the bound says 2.
Problem 4. An index holds one million vectors spread uniformly on the unit sphere, and a query's relevant passage has cosine 0.5 with it. How many unrelated vectors are expected to outscore the passage at $m = 32$ and at $m = 64$? What does the same threshold catch among this site's real passage vectors?
From the cap formula, $\Pr(\cos > 0.5)$ is 0.001524 at $m = 32$ and $1.114 \times 10^{-5}$ at $m = 64$. Among a million vectors that is 1,524 expected false positives at 32 dimensions and 11.1 at 64, so the relevant passage would be buried at 32 dimensions and would be near rank 12 at 64. Among the site's real vectors at $m = 384$, a share 0.0115 of random pairs have cosine above 0.5, so a passage at cosine 0.5 from a query placed like a random passage would have about $0.0115 \times 11{,}264 \approx 130$ passages above it. The uniform model predicts essentially none at 384 dimensions. Real passage vectors are crowded together far more than the model assumes, and a relevant passage has to score well above 0.5 to be found.
Problem 5. From the BEIR table, compute the relative difference of ANCE from BM25 on BioASQ and on Quora, and say what each number reflects.
On BioASQ, $(0.306 - 0.465)/0.465 = -34.2\%$. On Quora, $(0.852 - 0.789)/0.789 = +8.0\%$. BioASQ pairs biomedical questions with abstracts, which the authors single out as a large shift of domain from the web search questions ANCE was trained on, and they note that its candidates for judging were retrieved by term matching. Quora asks for a duplicate of a short question, where the words often differ and the meaning is the same. The same encoder is 34% behind in one and 8% ahead in the other, which is the paper's first conclusion: performance on the training domain does not predict performance elsewhere.
What we have learned
One vector per passage is a compression, and the compression has a price that can be stated. BM25 is itself a dot product in as many dimensions as the vocabulary has. Projecting it to $m$ dimensions at random reverses a pair of documents with a probability that depends only on their normalized margin $\epsilon$: exactly a Student $t$ probability for a Gaussian projection, and at most the bound of Luan and colleagues, both of which make the dimension needed proportional to $\epsilon^{-2}$. Margins shrink as documents grow longer and as they come to differ in only one detail, which is why exact wording in long or near-duplicate texts is what a single vector loses first. A fixed dimension also caps the number of distinct result sets, by the volume argument of Weller and colleagues, and real embeddings crowd into a small part of the sphere. Measured results agree with the theory's direction: on the BEIR benchmark the dense retrievers of 2021 fell below BM25 on most datasets outside their training domain, and on this site, in a test built to need exact overlap, the lexical engine finds a passage from a short run of its own words four times in five where the encoder manages one in six. The dense model wins where the query describes a page in other words.
Every measurement in this article depended on a test collection, and two of them turned out to favor one kind of system by construction. How to measure an embedding model fairly, what the public benchmarks report, and how to choose a model for one's own corpus are the subject of evaluating embedding models.
References
- Luan, Y., Eisenstein, J., Toutanova, K., and Collins, M. (2021). Sparse, dense, and attentional representations for text retrieval. Transactions of the Association for Computational Linguistics, 9, 329–345. arXiv:2005.00181. record · 2 pages
- Reimers, N., and Gurevych, I. (2021). The curse of dense low-dimensional information retrieval for large index sizes. In Proceedings of ACL-IJCNLP 2021 (Short Papers), 605–611. arXiv:2012.14210. record
- Sciavolino, C., Zhong, Z., Lee, J., and Chen, D. (2021). Simple entity-centric questions challenge dense retrievers. In Proceedings of EMNLP 2021, 6138–6148. arXiv:2109.08535; figures here are from version 3 of the arXiv paper. record
- Thakur, N., Reimers, N., Rücklé, A., Srivastava, A., and Gurevych, I. (2021). BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In Proceedings of the NeurIPS 2021 Datasets and Benchmarks Track. arXiv:2104.08663; read in version 4 of the arXiv paper, whose Table 2 agrees with the published version. record · 7 pages
- Weller, O., Boratko, M., Naim, I., and Lee, J. (2026). On the theoretical limitations of embedding-based retrieval. In Proceedings of ICLR 2026. arXiv:2508.21038; read in version 2 of the arXiv paper. record