Learned Sparse Retrieval

Retrieval that keeps the inverted index and learns what goes into it. A text becomes a weighted vector over the vocabulary, as in BM25, but a trained model sets the weights and may add terms the text lacks. DeepCT's learned term weights, document expansion by predicted queries, and SPLADE's expansion over the whole vocabulary with its FLOPS regularizer are set out, with an exact identity for the cost of a sparse index and proofs of the quantity the regularizer minimizes. A pretrained SPLADE model is run on Cranfield through an ordinary inverted index: its expansion measured, switched off, quantized to integer impacts, and compared with BM25 and a dense retriever. Five worked problems cover query term recall, pooling, the cost identity, the regularizer and quantization error.

Cranfield query 185 asks for experimental studies on panel flutter. To BM25 it is four stemmed terms, experiment, studi, panel and flutter, and an abstract that says panels, tests or wind-tunnel measurements scores only for the words it shares. A pretrained SPLADE model turns the same query into 46 weighted entries of its 30,522-word-piece vocabulary. Four are the query's own word pieces; its other two, on and the full stop, get weight zero. The other 42 entries include panels, experiment, study and experiments, words a relevant abstract might use in place of the query's. All 46 are still entries of an ordinary index of postings lists, looked up as BM25's terms are. Is it possible to learn which terms a text should be indexed under, and with what weights, while the index stays the ordinary kind?

Learned sparse retrieval represents a query and a document as vectors with one coordinate per vocabulary entry, most of them zero, whose weights are set by a trained model, and scores a document by the dot product of the two vectors, computed through postings lists. Two things can be learned: the weights on the terms a text contains (term weighting), and nonzero weights for terms it does not contain (expansion). This article treats both and asks what they cost.

Here is the route. First we place learned sparse retrieval among the other representations, starting from the fact that BM25 is already a sparse dot product. Then come three designs in historical order: DeepCT, which learns term weights; document expansion by predicted queries; and SPLADE, which does both in one forward pass. Next we derive what a sparse index costs per query, an exact identity, and what SPLADE's FLOPS regularizer minimizes. Finally we run a pretrained SPLADE model on Cranfield through postings lists, measure its expansion, switch the expansion off, and store its weights as integers. The article assumes Sentence and Passage Encoders for the transformer and the inverted index from the course. The numbers are computed by tools/experiments/neural-ranking/learned-sparse-retrieval.py.

A sparse vector over the vocabulary

Limits of Single-Vector Retrieval proves that BM25 is a dot product: the query is a vector in $\mathbb{R}^V$ holding each of its terms' inverse document frequency, the document a vector holding each term's saturated, length-normalized frequency, and $V$ is the size of the vocabulary. On Cranfield $V = 4{,}803$ stemmed terms, and an abstract has a nonzero weight for 68.1 of them on average. The document vectors do not depend on the query, which is why they can be stored in advance as postings, and the score of a document is a sum of per-term contributions, which is why an index of postings lists computes it by reading only the postings of the query's terms.

Lin (2021) proposed a frame in which this is one case of a general design. A retrieval model has a query encoder $\eta_q$, a document encoder $\eta_d$, and a comparison function $\phi$; the score is $\phi(\eta_q(q), \eta_d(d))$. BM25 and the dense passage retriever have the same form, with $\phi$ the dot product in both. They differ in two ways that Lin separates. The representation is sparse, with one dimension per vocabulary entry, or dense, with a few hundred dimensions chosen by training. And the weights are unsupervised, computed from term statistics, or learned from relevance data. BM25 is sparse and unsupervised; a bi-encoder is dense and learned. Learned sparse retrieval is the remaining useful corner: the basis stays the vocabulary, and the weights are learned.

Lin and Ma (2021) add a point that organizes the designs below. Learned sparse retrieval has two separable parts, an expansion model that decides which vocabulary entries get a nonzero weight, and a term weighting model that sets the weights. Without expansion, a document can only be found through terms it contains, and the vocabulary mismatch of query expansion remains.

A stored per-term weight is called an impact, and a sum of impacts is the score. Implementing BM25 describes precomputed impacts for BM25 itself, and this site's search box uses them in the browser (How This Search Works). Every learned sparse model ends as impacts in postings.

Learning term weights: DeepCT

Lin (2021) calls DeepCT (Dai and Callan, 2019; 2020) the first learned sparse representation of the BERT era. Here is the idea in one sentence: fit a regression that predicts, for each word of a passage, how often that word appears in the queries the passage answers, and index the passage with the predictions in place of its term frequencies.

The model reads a passage with BERT and maps each word's contextual vector $\vec{T}_{t,c}$ (word $t$ in text $c$) to a scalar by a linear layer, $\hat y_{t,c} = \vec{w} \cdot \vec{T}_{t,c} + b$. It is trained by regression, minimizing $\sum_{c} \sum_{t} (y_{t,c} - \hat y_{t,c})^2$. The target is the query term recall of the word in the passage,

$$\mathrm{QTR}(t, d) = \frac{\lvert Q_{d,t} \rvert}{\lvert Q_d \rvert},$$

where $Q_d$ is the set of training queries for which passage $d$ is judged relevant and $Q_{d,t}$ the subset that contains $t$. The assumption, in Dai and Callan's words, is that "search queries can reflect the key idea of a document". At indexing time every passage is run through the model, and the predicted weight of each of its terms is scaled to an integer, $\mathit{TF}_{\mathrm{DeepCT}}(t, d) = \mathrm{round}(100\, \hat y_{t,d})$, which replaces the term frequency in an ordinary index searched with BM25. Terms whose prediction rounds to 0 drop out of the index.

Example (query term recall on Cranfield). Cranfield's judgments supply the same signal. Abstract 856, some experimental studies of panel flutter at mach 1.3, is judged relevant to three queries: 2 (on structural and aeroelastic problems of high-speed flight), 185 and 191 (on the criterion for true panel flutter). With the course's stemmed terms, flutter and panel appear in two of the three, so their target is $2/3$; experiment, studi and structur each appear in one, $1/3$. The abstract has 96 distinct stemmed terms, and the other 91 have target 0, among them mach, tunnel and aluminum, which describe the experiment but appear in none of its queries. Only 830 of Cranfield's 1,400 abstracts are relevant to any query at all, so for the other 570 the target is undefined. A DeepCT model trained here would learn from fewer than 60% of the abstracts. Dai and Callan trained on MS MARCO, which pairs about half a million queries with relevant passages.

DeepCT raised BM25's MRR@10 on the MS MARCO passage development queries from 0.184 to 0.243 (Nogueira and Lin, 2019, Table 1, which tabulates both). Its limit is structural, and Lin (2021) states it: DeepCT "only assigns weights to terms that are already present in the document", so retrieval is still exact match.

Adding terms: documents expanded by predicted queries

The other half is expansion. Nogueira, Yang, Lin and Cho (2019) trained a sequence-to-sequence transformer on MS MARCO's pairs of a passage and a query it answers, to produce the query from the passage. At indexing time they generated 10 queries per passage by top-$k$ random sampling, appended them to the passage with no markup, and indexed the result for BM25. They called it doc2query.

The generated queries do two things, and the authors measured each. Excluding stop words, 69% of the predicted words were copied from the passage and 31% were new. Copying repeats a passage's important words and so re-weights them; new words are expansion. Expanding with the new words alone raised MRR@10 from 18.4 to 18.8, with the copied words alone to 19.7, and with both to 21.5. Replacing the transformer with the pretrained T5 model, docTTTTTquery (Nogueira and Lin, 2019) reached 0.277 with 40 sampled queries per passage, with recall at 1,000 of 0.947 against BM25's 0.853. The proportions of copied and new words were about the same, 67% and 33%.

The cost is at indexing time. Nogueira and Lin report that sampling 5 queries for each of MS MARCO's 8.8 million passages took about 40 hours on one TPU. The query side costs nothing: queries are searched with plain BM25. This article does not run document expansion; the SPLADE experiment below measures expansion directly, and the next section shows why one forward pass can do what sampled queries do.

SPLADE: weights and expansion in one forward pass

BERT is pretrained to predict masked words. Its masked language model head turns the contextual vector at each position into a score for every entry of the vocabulary. An earlier model, SparTerm, read those scores as term importances; Formal, Piwowarski and Clinchant (2021) describe it and build on it to make SPLADE, and their notation is used here.

Let the input have tokens $t_1, \dots, t_N$ with contextual vectors $\vec h_1, \dots, \vec h_N$. The importance of vocabulary entry $j$ for input position $i$ is the head's logit,

$$w_{ij} = \mathrm{transform}(\vec h_i)^{\mathsf{T}} \vec E_j + b_j, \qquad j \in \{1, \dots, \lvert V \rvert\},$$

where $\vec E_j$ is BERT's input embedding of entry $j$, $b_j$ a bias, and $\mathrm{transform}$ a linear layer with GeLU activation and layer normalization (their equation 1). SPLADE pools these over the input positions. The first version summed (their equation 4); SPLADE v2 replaced the sum with a maximum (Formal et al., 2021, equation 6), and the model run below uses the maximum:

$$w_j = \max_{i = 1, \dots, N} \ln\big(1 + \mathrm{ReLU}(w_{ij})\big).$$

The vector $(w_1, \dots, w_{\lvert V \rvert})$ represents the text, a query and a document alike, and the score is the dot product of the two.

Three properties of this weight follow from its form.

Proposition 1. (a) $w_j = 0$ exactly when $w_{ij} \le 0$ at every position $i$. (b) $w_j$ is the weight of the single position that gives entry $j$ the largest logit, so with max pooling no number of other positions with lower logits changes it; with sum pooling every position with a positive logit adds to it. (c) If some position gives entry $j$ a positive logit, then $w_j = \ln(1 + \max_i w_{ij})$; since $\ln$ grows slowly, a logit of 20 gives a weight of only $\ln 21 = 3.04$.

Proof. The function $g(x) = \ln(1 + \mathrm{ReLU}(x))$ is 0 for $x \le 0$ and strictly increasing for $x > 0$, with $g(x) > 0$ there. (a) A maximum of nonnegative numbers is 0 exactly when all of them are 0, that is when every $w_{ij} \le 0$. (b) Since $g$ is nondecreasing, $\max_i g(w_{ij}) = g(\max_i w_{ij})$, which depends only on the largest logit; a sum $\sum_i g(w_{ij})$ instead increases with every position whose logit is positive. (c) By (b), $w_j = g(\max_i w_{ij})$, and $g(x) = \ln(1 + x)$ for $x > 0$. $\square$

Part (a) is where sparsity comes from: the ReLU sets every negative logit to zero, and an entry stays zero unless some position votes for it. Part (c) is the saturation Formal and colleagues introduced, which they relate to the logarithmic term frequency of classical models: it "prevents some terms to dominate". Worked problem 2 computes both poolings on a small case.

SPLADE is trained like a bi-encoder, with the contrastive loss of Contrastive Training for Retrieval: one positive passage, a BM25 negative and in-batch negatives (their equation 5). What makes it sparse enough to index is a second term in the loss, which the next section derives. The model used below, SPLADE++ in its "CoCondenser-EnsembleDistil" form (Formal, Lassance, Piwowarski and Clinchant, 2022), was further trained by distillation from a cross-encoder with the Margin-MSE loss of Hard Negatives and Distillation, on negatives mined by BM25 and twelve dense retrievers, starting from a CoCondenser checkpoint. They report an MRR@10 of 38.0 on MS MARCO's development queries (their Table 1); the model card of the released checkpoint gives 38.3.

What a sparse index costs

The cost is postings read

A postings-list index scores a query by reading the postings lists of the query's nonzero entries. Every posting read is one multiplication and one addition into a document's running score, as in the accumulator loop of Implementing BM25, which takes the query's terms one after another. So the cost of a query is

$$\mathrm{cost}(q) = \sum_{j \,:\, w_j(q) > 0} \mathit{df}_j,$$

where $\mathit{df}_j$ is the number of documents whose weight for entry $j$ is nonzero, the length of its postings list. Expansion raises it twice: a query with more entries reads more lists, and documents with more entries make every list longer.

Paria et al. (2020) turned this into a quantity a model can be trained against. Here is the idea: the average cost over many queries depends only on how often each entry is active in queries and in documents.

Proposition 2 (the cost identity). Let a collection have $N$ documents and let $Q$ be a set of queries. Write $p_j^D = \mathit{df}_j / N$ for the share of documents with a nonzero weight for entry $j$, and $p_j^Q$ for the share of the queries in $Q$ with a nonzero weight for it. Then the mean number of postings read per query is exactly

$$\frac{1}{\lvert Q \rvert} \sum_{q \in Q} \mathrm{cost}(q) = N \sum_{j=1}^{\lvert V \rvert} p_j^Q\, p_j^D .$$

Proof. Write $\mathbb{1}_j(q)$ for 1 if $w_j(q) > 0$ and 0 otherwise. Then $\mathrm{cost}(q) = \sum_j \mathbb{1}_j(q)\, \mathit{df}_j$, and exchanging the two finite sums,

$$\frac{1}{\lvert Q \rvert} \sum_{q} \sum_j \mathbb{1}_j(q)\, \mathit{df}_j = \sum_j \mathit{df}_j \cdot \frac{1}{\lvert Q \rvert} \sum_q \mathbb{1}_j(q) = \sum_j N p_j^D\, p_j^Q. \qquad \square$$

Paria and colleagues state the expected form: if queries and documents are drawn independently from one distribution with activation probabilities $p_j$, the expected number of operations to score one document is $\sum_j p_j^2$ (their equation 2), which they call FLOPs per row. Proposition 2 is the exact version for a fixed query set and collection; it needs no independence, because it is an identity about counts. Divided by $N$, it is the expected number of entries that a query and a document share, for a random pair.

What the FLOPS regularizer minimizes

To be trained against, the cost must be small when the index is sparse and also when the postings are spread evenly. A second proposition shows that $\sum_j p_j^2$ does both.

Proposition 3. Let documents have, on average, $c = \sum_j p_j$ nonzero entries. Then

$$\sum_{j=1}^{\lvert V \rvert} p_j^2 \;\ge\; \frac{c^2}{\lvert V \rvert},$$

with equality exactly when all $p_j$ are equal.

Proof. By the Cauchy-Schwarz inequality applied to the vectors $(p_1, \dots, p_{\lvert V \rvert})$ and $(1, \dots, 1)$, $\big(\sum_j p_j \cdot 1\big)^2 \le \big(\sum_j p_j^2\big)\big(\sum_j 1^2\big)$, that is $c^2 \le \lvert V \rvert \sum_j p_j^2$, with equality exactly when the two vectors are proportional, that is when all $p_j$ are equal. $\square$

So for a fixed number of nonzeros per document, the cost is least when every vocabulary entry is used equally often, and it grows as the postings pile up in a few long lists. An $\ell_1$ penalty $\sum_j p_j$ sees only the total $c$. Formal and colleagues adopt the FLOPS regularizer for this reason, citing Paria and colleagues' observation that minimizing the $\ell_1$ norm of the representations does not make the most efficient index, since nothing ensures that the postings lists are evenly distributed. Worked problem 4 gives two indexes with the same $\ell_1$ total and costs that differ by a factor of four.

The activations $p_j$ are counts and have no gradient. Paria and colleagues replace each by the mean absolute weight, $\bar a_j = \frac{1}{B} \sum_{i=1}^{B} \lvert w_j(d_i) \rvert$ over a batch of $B$ documents, and SPLADE trains with

$$\ell_{\mathrm{FLOPS}} = \sum_{j \in V} \bar a_j^2 = \sum_{j \in V} \Big(\frac{1}{B} \sum_{i=1}^{B} w_j(d_i)\Big)^2,$$

added to the ranking loss with separate weights for queries and documents (their equation 6; SPLADE's weights are nonnegative, so the absolute value can be dropped). Its gradient shows how it works. For a document weight $w_j(d_i) > 0$,

$$\frac{\partial \ell_{\mathrm{FLOPS}}}{\partial w_j(d_i)} = 2\, \bar a_j \cdot \frac{1}{B} .$$

The push toward zero on one document's weight for entry $j$ is proportional to how much the whole batch uses entry $j$. A common term is pressed hard everywhere and a rare term barely at all. An $\ell_1$ penalty $\sum_j \bar a_j$ has gradient $1/B$ for every positive weight, the same for every entry, and so does nothing to spread the postings.

SPLADE on Cranfield

The pinned model is naver/splade-cocondenser-ensembledistil at revision 49cf4c7b0db5b870a401ddf5e2669993ef3699c7, a 12-block BERT with its masked language model head, released under a CC BY-NC-SA 4.0 licence. Each of Cranfield's 1,400 abstracts (title and text) and 225 queries is read up to 256 word pieces, the length the model card gives for reproducing its evaluation, and turned into its vector of max-pooled weights as defined above. The weights go into a plain inverted index, a dictionary from vocabulary entry to a list of (abstract, weight), and each query is scored with one accumulator per abstract, query entry after query entry. Nothing is approximated, and nothing about the model was trained on Cranfield: it was trained on MS MARCO.

Index Postings Vocabulary entries used Mean entries per abstract Mean entries per query Mean postings read per query
BM25 (stemmed terms) 95,362 4,803 68.1 11.4 2,071
SPLADE 229,434 8,830 163.9 76.0 23,148

The SPLADE index has 2.4 times as many postings, and a query reads 11.2 times as many. By Proposition 2, the second ratio is the ratio of the expected number of entries a query and an abstract share: 16.5 for SPLADE against 1.48 for BM25, with the identity asserted in exact rational arithmetic on both indexes. The postings also pile up. Twenty-five of SPLADE's lists cover more than half the collection; the longest, for experiment, has 1,238 of the 1,400 abstracts. With abstracts in both roles, $\sum_j (p_j^D)^2$ is 28.5 for SPLADE, against a floor of $c^2/\lvert V \rvert = 0.88$ from Proposition 3 had its 163.9 entries per abstract been spread evenly over the vocabulary. For BM25 the same numbers are 7.97 and 0.97.

Effectiveness

Ranker nDCG@10 Recall@10 Recall@100 Recall@1000
BM25 0.368 0.397 0.737 0.952
Dense (unit 1's bi-encoder) 0.382 0.416 0.772 0.989
SPLADE 0.390 0.432 0.774 0.986

The measures are those of Dense Passage Retrieval: nDCG@10 with gain $5 - \text{grade}$, recall with any graded abstract counted as relevant. Against BM25, SPLADE is ahead by 0.022 in nDCG@10, with $t = 1.95$ and $p = 0.052$ (randomization $p = 0.053$; 95% bootstrap interval $[0.000, 0.045]$; better on 106 queries, worse on 87), a difference on the edge of what 225 queries can detect. At depth the difference is clear: recall@100 is higher by 0.037 ($t = 3.68$, $p = 0.0003$; higher on 66 queries, lower on 27). Against the dense retriever, no difference is detectable: $+0.009$ in nDCG@10 ($p = 0.49$) and $+0.001$ in recall@100 ($p = 0.91$).

What SPLADE indexed

Query 185. Its 46 entries, by weight, begin flutter 2.843, panel 2.377, experimental 1.378, panels 1.297, studies 1.255, experiment 1.157 and study 1.134; the query's own word pieces and their morphological variants carry the top of the list, the stemming that BM25 does by rule, done by the model. Further down, at weights between 0.3 and 0.65, come wave, research, theory, model, test and technique, related words that an abstract on the subject might use. Among them are entries that have nothing to do with panel flutter: inhibitor 0.493, mutation 0.407, crash 0.302 and tumor 0.292. The model was trained on web questions, and a plausible reading, which the experiment does not test, is that these are what "experimental studies" are usually about in its training data.

Abstract 856 has 204 entries. Its top weights are flutter 2.68, mach 2.205, panel 1.977 and then buckle 1.726, which the abstract does not contain (it says buckled), followed by rectangular, tunnel, stab, buckled, magnesium and brass. Its score for query 185 is the sum over the 32 entries the two vectors share. The largest products are flutter $2.843 \times 2.68 = 7.62$, panel $2.377 \times 1.977 = 4.70$, panels $1.297 \times 1.383 = 1.79$, experimental 1.70 and studies 1.42, and the total is 22.56. The query's expansion entry panels matches a word the abstract really contains; its entry inhibitor matches an expansion of the abstract's, at a product of 0.149. SPLADE's top ten for query 185 are abstracts 856, 857, 1008, 390, 766, 627, 658, 858, 948 and 15, with an nDCG@10 of 0.720, between BM25's 0.807 and the dense retriever's 0.290.

Over the collection. Of the entries in an abstract's vector, 64.5% on average are not among its own word pieces, and they carry 37.4% of its total weight. In the other direction, 35.9% of an abstract's own word pieces get weight 0: the model drops them, as DeepCT drops terms whose prediction rounds to zero. For queries the expansion is larger: 83.0% of a query's entries are not its own word pieces. Two of Cranfield's abstracts, 471 and 995, have no text at all; each still receives 126 entries, from the special tokens alone.

Switching the expansion off

How much of SPLADE's effectiveness is expansion? The trained model can be asked at query time to give up its expansion, by keeping only the entries that are a text's own word pieces. This is not the same as a model trained without expansion, which Formal and colleagues compared in their own Table 1; it measures what this model's expansion contributes.

Variant (same trained model) nDCG@10 Difference $p$ Recall@100 Difference $p$
Full 0.390 0.774
Abstracts limited to their own word pieces 0.373 −0.018 0.004 0.757 −0.016 0.006
Queries limited to their own word pieces 0.371 −0.020 0.001 0.753 −0.021 0.013
Both limited 0.363 −0.027 0.0004 0.731 −0.043 0.0001

The $p$ values are from paired $t$-tests over the 225 queries. Removing expansion on either side costs about 0.02 in nDCG@10, and removing both costs about as much as BM25's deficit to the full model; recall@100 falls by 0.043, below BM25's 0.737. What remains, the model's own weights on the texts' own word pieces, is a DeepCT-like term weighting, and on this collection it scores close to BM25: 0.363 against 0.368.

Running on an ordinary inverted index

A learned sparse model needs no new search machinery. Its document vectors are postings lists with a weight per posting, and its query is a short list of (entry, weight) pairs. Two engineering choices remain.

Integer impacts. Indexes store integers. DeepCT multiplied its weights by 100 and rounded; uniCOIL, a later learned sparse model, quantized its weights to 8 bits (Lin and Ma, 2021). Rounding changes scores by a bounded amount.

Proposition 4. If every document weight is replaced by the nearest multiple of $1/s$ (and dropped if that is 0), the score of every document for query $q$ changes by at most $\frac{1}{2s} \sum_j w_j(q)$.

Proof. Each rounded weight $\hat w_j(d)$ satisfies $\lvert w_j(d) - \hat w_j(d) \rvert \le 1/(2s)$, including those rounded to 0. The change in score is $\sum_j w_j(q) \big(w_j(d) - \hat w_j(d)\big)$, whose absolute value is at most $\sum_j w_j(q) \cdot \frac{1}{2s}$ by the triangle inequality, since query weights are nonnegative. Entries of the query that the document lacks contribute 0 before and after. $\square$

On Cranfield, with $s = 100$, 2,329 postings round to 0 and disappear, nDCG@10 is 0.390 to three decimals (0.3895 against 0.3904 unrounded), and 196 of the 225 queries keep exactly the same top ten. Storing 8 bits, with 255 standing for the largest document weight, 3.248, gives the same nDCG@10 and 187 unchanged top tens. The script checks Proposition 4's bound for every query and abstract; the largest error observed is a third of the bound.

This site. The site's engine keeps positional postings per field and computes BM25F at query time, but its browser copy is already an impact index: for every pair of a term and a page, the server precomputes the term's contribution to the page's score, and the browser only adds numbers (How This Search Works). A learned sparse model's document vectors would fit that format with no change to the browser's arithmetic. The query side would not: a query must be encoded by the model before its entries are known, which needs the model at search time. Formal and colleagues' SPLADE v2 paper describes a document-only variant, SPLADE-doc, whose query is just its own tokens; they report it matching the first SPLADE model on MS MARCO and outperforming doc2query-T5 there. Nothing of this was run on the site's pages here.

What is proved here, what is cited, and what the experiment shows

Proved on this page. Proposition 1, the zero set, max-pooling behavior and saturation of SPLADE's weight. Proposition 2, the exact identity between the mean number of postings read and $N \sum_j p_j^Q p_j^D$. Proposition 3, that for a fixed number of nonzeros the FLOPS cost is least when postings are spread evenly. The gradient of the FLOPS regularizer and of the $\ell_1$ penalty. Proposition 4, the quantization error bound. BM25 as a sparse dot product is proved in Limits of Single-Vector Retrieval.

Cited. The designs and every result on MS MARCO: DeepCT (Dai and Callan); doc2query and docTTTTTquery (Nogueira, Yang, Lin and Cho; Nogueira and Lin); SPLADE, SPLADE v2 and SPLADE++ (Formal and colleagues); the FLOPS regularizer and its expectation (Paria et al.); the conceptual frame and the expansion and weighting decomposition (Lin; Lin and Ma); the training of the pinned model, from its paper and model card.

Shown by the experiment, for one pretrained model on one small collection. SPLADE's index is 2.4 times as large as BM25's, and a query reads 11.2 times as many postings. Its effectiveness is borderline above BM25 at ten results, clearly above at one hundred, and indistinguishable from the dense retriever. On average 64.5% of an abstract's entries are expansion, carrying over a third of its weight. Switching expansion off at query time costs about 0.02 to 0.03 in nDCG@10. Integer impacts change almost nothing.

Worked problems

These problems are posed on Cranfield and on small exact cases; the unit has no course assignments. The script recomputes each number under "Worked problems".

Problem 1 (query term recall). Abstract 856 is relevant to Cranfield queries 2, 185 and 191, whose stemmed terms are: query 2, what, structur, aeroelast, problem, associ, flight, high, speed, aircraft; query 185, experiment, studi, panel, flutter; query 191, what, criterion, true, panel, flutter, oppos, small, amplitud, vibrat, aris, from, acoust, disturb. Compute DeepCT's target for flutter, panel, structur and mach in this abstract, and the integer DeepCT would index if its model predicted the targets exactly.

Solution. $\lvert Q_d \rvert = 3$. flutter is in queries 185 and 191, so $\mathrm{QTR} = 2/3$; the same for panel. structur is only in query 2: $1/3$. mach is in none: 0. With exact predictions, $\mathit{TF}_{\mathrm{DeepCT}} = \mathrm{round}(100 \times 2/3) = 67$ for flutter and panel, $\mathrm{round}(100/3) = 33$ for structur, and 0 for mach, which therefore leaves the index for this abstract although the abstract's title contains it. The target rewards the words that the abstract's queries happened to use, and Cranfield's queries ask about panels and flutter, not about the Mach number of the test.

Problem 2 (sum and max pooling). A text has three positions, and the head's logits for three vocabulary entries $A$, $B$, $C$ are $(3, 1, -2)$ at position 1, $(0.5, 2, -1)$ at position 2 and $(3, -0.5, 0)$ at position 3. Compute the weights under sum pooling and under max pooling.

Solution. Apply $g(x) = \ln(1 + \mathrm{ReLU}(x))$: $g(3) = \ln 4 = 1.386$, $g(1) = \ln 2 = 0.693$, $g(0.5) = \ln 1.5 = 0.405$, $g(2) = \ln 3 = 1.099$, and $g$ of a nonpositive logit is 0. Sum pooling: $A = 1.386 + 0.405 + 1.386 = 3.178$, $B = 0.693 + 1.099 + 0 = 1.792$, $C = 0$. Max pooling: $A = 1.386$, $B = 1.099$, $C = 0$. Entry $A$ has its highest logit at two positions; the sum counts it twice and the maximum once, as Proposition 1(b) says. $C$ has no positive logit and is zero either way, Proposition 1(a).

Problem 3 (the cost identity). A collection of four documents has postings $t_1$: documents 1, 2, 3, 4; $t_2$: 1, 2; $t_3$: 3. Query $q_1$ has entries $t_1, t_2$ and query $q_2$ has $t_2, t_3$. Compute the mean postings read per query directly and by Proposition 2.

Solution. Directly: $q_1$ reads $4 + 2 = 6$ postings and $q_2$ reads $2 + 1 = 3$, a mean of $9/2$. By the identity: $p^D = (1, 1/2, 1/4)$ and $p^Q = (1/2, 1, 1/2)$ for $t_1, t_2, t_3$, so $N \sum_j p_j^Q p_j^D = 4\,(1/2 + 1/2 + 1/8) = 4 \times 9/8 = 9/2$. The same.

Problem 4 (same $\ell_1$, different cost). Two indexes over four documents and four vocabulary entries each give every document exactly one entry with weight 1. In index I every document uses entry 1; in index II document $i$ uses entry $i$. Compare the $\ell_1$ penalty, the FLOPS regularizer and the expected cost.

Solution. Mean weights: I has $\bar a = (1, 0, 0, 0)$, II has $(1/4, 1/4, 1/4, 1/4)$. The $\ell_1$ penalties $\sum_j \bar a_j$ are both 1. The FLOPS regularizers $\sum_j \bar a_j^2$ are 1 and $4 \times 1/16 = 1/4$. Here $p_j = \bar a_j$, so the expected number of entries a random query from the same distribution shares with a random document is $\sum_j p_j^2$: 1 for I, where every query reads the one list of length 4, and $1/4$ for II, where every query reads a list of length 1. The $\ell_1$ penalty cannot tell the indexes apart; the FLOPS regularizer prefers II by a factor of 4, the floor $c^2/\lvert V \rvert = 1/4$ of Proposition 3. Its gradient on a document's weight is $2 \bar a_j / B$ with $B = 4$ documents in the batch: $1/2$ in I and $1/8$ in II.

Problem 5 (quantization error). For query 185 the SPLADE weights sum to $\sum_j w_j(q) = 20.98$. Bound the change in the score of any abstract when document weights are rounded to hundredths, and compare with the actual change for abstract 856.

Solution. By Proposition 4 with $s = 100$, the bound is $20.98/200 = 0.105$. Abstract 856's score is 22.5632 unrounded and 22.5614 with rounded weights, a change of 0.0018, less than 2% of the bound. The bound assumes every rounding error has its largest size and the same sign; in fact the errors are spread over $[-0.005, 0.005]$ and cancel in part, and only the 32 entries the query and abstract share contribute.

What we have learned

Learned sparse retrieval keeps BM25's machinery, a vector over the vocabulary scored by a dot product through postings lists, and learns what goes into the vector. DeepCT learned weights for the words a passage contains; doc2query and docTTTTTquery added the words of predicted queries; SPLADE does both in one pass by reading BERT's masked language model head, with a log saturation and max pooling that keep most entries at zero and none very large. The price of expansion is cost, and the cost has an exact form: postings read equal $N \sum_j p_j^Q p_j^D$, which the FLOPS regularizer controls by pressing hardest on the most used entries. On Cranfield a pretrained SPLADE model, trained on web questions, read eleven times as many postings as BM25, found more relevant abstracts at depth, was even with a dense retriever, and lost about as much as its lead over BM25 when its expansion was switched off.

Learned sparse vectors keep one weight per term. Late Interaction and ColBERT keeps a whole vector per token, and compares them at query time. How lexical, learned sparse and dense lists are combined into one is the subject of Hybrid Retrieval.

References