Picture this. You have a large collection of text: passages from legal documents, snippets from books, or pages from the web. Given a question, you want to find the passages most likely to help answer it. A learned embedding model gives us a way to express that task mathematically: encode the question and each passage as vectors, then retrieve the vectors with the largest similarity scores.

Our algorithm, Seismic, makes this search efficient for learned sparse vectors (Bruch et al., SIGIR 2024). It combines a sketch of the collection, a geometric organization of inverted lists, full-vector scoring, and an optional nearest-neighbor graph. The extended paper develops the sketching analysis and evaluates this combination on collections of up to 138 million vectors. Let’s work through how the pieces fit together.

Learned sparse representations

A sparse vector has many zero coordinates. In learned sparse text representations, each dimension typically corresponds to a term in a fixed vocabulary, and its nonnegative value expresses that term’s importance. A model can give weight to a term absent from the input, allowing related passages to match even when they use different words. SPLADE and its variants are examples of this approach.

Only the nonzero coordinate–weight pairs need to be stored. A vector can therefore live in a vocabulary with tens of thousands of dimensions while requiring space for only a small fraction of them. Figure 1 illustrates the representation with invented weights; the encoder and its training procedure are separate from the search algorithm.

Text becomes a weighted sparse vector A toy text, a fox jumps, is encoded into a vocabulary-aligned sparse vector. Fox, jump and the related term hop have nonzero weights, while other dimensions are zero. These numbers are an illustrative example, not measurements from an embedding model. Text becomes a weighted sparse vector a fox jumps text input learned encoder fox 0.50 jump 0.30 hop 0.20 other terms 0 Only nonzero coordinate–weight pairs need to be stored. Toy values shown.
Figure 1. A toy learned sparse representation. Dimensions correspond to vocabulary terms, including related terms absent from the input. All weights are illustrative. View largerScroll sideways for the full sketch.

Sparsity helps with storage and arithmetic, but it does not make search trivial. A common term can still occur in millions of vectors. Efficient retrieval needs a way to avoid most of those vectors while retaining the ones that score highly for the query.

Inner product as a measure of similarity

Write the query as q and a document vector as u. Their inner product is the sum of products in matching coordinates:

⟨q,u⟩=∑i=1dqiui.

We seek the k documents with the largest scores: maximum inner product search, or MIPS. Geometrically, the score orders candidates by their projection along the query direction, as Figure 2 shows. Cosine similarity becomes an inner product after normalizing vectors. Euclidean nearest-neighbor search has the same ranking when candidate norms are equal; otherwise it needs an appropriate reduction.

Rank by the projection along the query For q equal to (0.6, 0.3), candidate a=(0.15,0.7) scores 0.30, b=(0.7,0.2) scores 0.48, and c=(0.35,0.6) scores 0.39. A line perpendicular to q through b marks the largest inner product among these candidates. Rank by the projection along the query q a b c q = (0.6, 0.3) a q · a = 0.30 c q · c = 0.39 b q · b = 0.48 b wins this query Moving a perpendicular line outward along q orders points by their inner product.
Figure 2. A two-dimensional MIPS example. The candidates score 0.30, 0.48, and 0.39 against q = (0.6, 0.3), so b wins. The dashed line is perpendicular to q and passes through b; moving it outward orders points by score. View largerScroll sideways for the full sketch.

A full scan computes every document’s score. An approximate index instead tries to discover a small, useful candidate set. The price of skipping work is that some true top-k documents can be missed.

The paper measures this with accuracy@k: the fraction of the exact top-k set present in the returned set. Returning nine of the true top ten gives 90% accuracy@10. This is agreement with exact vector search; the embedding model still determines how useful those documents are to a person.

Seismic’s three data structures

Seismic separates candidate discovery from candidate scoring. Its inverted index maps a dimension to document identifiers, organized into blocks with compact summaries. Its forward index maps each identifier to the complete original vector. An optional κ-nearest-neighbor graph maps each document to a short list of similar documents, giving search another way to discover candidates.

The inverted index guides where to look; the forward index supplies exact inner products for the documents we actually inspect. The graph can then refine that candidate set. Figure 3 gives the full pipeline before we unpack each stage.

Seismic (2025): sketch, rank, then refine The extended algorithm applies Set alpha-MSS across dimensions, forms inverted lists, partitions each retained list into approximately beta times its length blocks, and forms gamma-mass sketches of coordinate-wise maximum summaries with scalar quantization. It also keeps a forward index of full vectors and an optional kappa-nearest-neighbor graph. Query alpha-q-MSS selects lists; full-query summary scores order blocks, the heap threshold guides heuristic pruning, and original vectors provide exact candidate scores. A final optional one-hop graph expansion reranks the candidate pool. Seismic (2025): sketch, rank, then refine BUILD ONCE Set α-MSSper dimension form theinverted lists ≈ β |Li|blocks per list full maximumthen γ-MSS quantizesummaries Keep full vectors in a forward index; optionally build a κ-NN graph. FOR EACH QUERY αq-MSS:select lists score & sortsummaries gate blocks;score fullvectors keep top-kcandidates optional κ-NNone-hop rerank heap controls the gate Compressed summaries guide pruning; full scores rank the candidates actually examined.
Figure 3. The current Seismic pipeline (paper, Algorithms 2–3). α controls collection sketching, β the block-count factor, γ summary mass, and κ graph refinement. The query sketch selects lists; full-query scores order summaries and rank candidates. View largerScroll sideways for the full sketch.

Sketching sparse vectors

Many learned sparse vectors concentrate much of their weight in relatively few coordinates. The extended paper studies how to exploit that pattern, starting with randomized ℓ₁ threshold sampling and then developing deterministic subvector sketches. For its sketching analysis, the paper places nonnegative vectors in the ℓ₁ unit ball, with total coordinate mass at most one. The practical attraction of a subvector is simple: it retains some coordinates and their original values, so ordinary sparse inner-product routines can process it.

For a single vector, an α-mass subvector sketch, or α-MSS, sorts coordinates by decreasing absolute value and retains the smallest prefix whose total absolute weight reaches at least α times the vector’s ℓ₁ mass. Here α is a fraction of mass, rather than a fraction of coordinates. With nonnegative vectors, dropping coordinates makes the resulting inner-product estimate an underestimate. Section 3.3 of the paper bounds that error in terms of omitted mass and overlapping coordinates.

Seismic uses a related but different rule for the collection: Set α-MSS. Imagine documents as rows of a matrix and dimensions as columns. In each column, retain a fraction α of its nonzero entries, choosing the largest values. Figure 4 contrasts these two rules; Figure 5 applies the collection rule to a small matrix.

Two sketches, two different retention rules For alpha equal to one half, a per-vector alpha-mass sketch of weights 0.4, 0.3, 0.15, 0.08, 0.05, and 0.02 retains the first two coordinates: they carry 0.7 mass and one coordinate alone is insufficient. By contrast, Set alpha-MSS in a dimension with six nonzeros keeps the three largest entries, a count fraction across documents. Two sketches, two different retention rules one vector: α-MSS one dimension: Set α-MSS 0.4 0.3 0.15 0.08 0.05 0.02 0.9 0.5 0.3 0.2 0.1 0.05 coordinates, sorted by weight documents, sorted by this coordinate α = 0.5: keep ≥ half the mass 0.40 + 0.30 = 0.70; only 2 of 6 α = 0.5: keep half the entries ⌈0.5 × 6⌉ = 3 of 6 Per-vector mass retention and per-dimension count retention are different operations.
Figure 4. Definitions 4 and 6 use different retention rules. At α = 0.5, the vector needs two coordinates to reach half its mass. Set α-MSS instead keeps three of six nonzero entries in the illustrated dimension. View largerScroll sideways for the full sketch.

More precisely, if dimension i has mi nonzeros across the collection, retain its largest ⌈αmi⌉ entries and set the rest to zero. Equivalently, mi = ρi|S| in the paper’s density notation. This controls the retained entry count per dimension. It does not promise that every document retains an α fraction of its own mass: in the toy matrix, one document loses all its entries.

Set α-MSS compares documents within each dimension A five-document, four-dimensional toy matrix is sketched with alpha equal to one half. Each column keeps the largest ceil(alpha times its nonzero count) entries. Retained counts are two in every column; the third originally has three nonzeros. Different documents keep different fractions of their own mass. Set α-MSS compares documents within each dimension original collection d1 d2 d3 d4 u1 0.4 0.05 0 0.15 u2 0.1 0.35 0.1 0 u3 0 0.2 0.4 0.1 u4 0.25 0 0.05 0.3 u5 0.05 0.15 0 0.05 rows = documents after Set α-MSS, α = 0.5 d1 d2 d3 d4 u1 0.4 0 0 0.15 u2 0 0.35 0.1 0 u3 0 0.2 0.4 0 u4 0.25 0 0 0.3 u5 0 0 0 0 rows = documents top half per column The retained entry count is controlled per dimension; mass kept varies by document.
Figure 5. Set α-MSS on a toy collection. Each column keeps its largest ⌈0.5mᵢ⌉ nonzeros. The columns originally contain 4, 4, 3, and 4 nonzeros, so each keeps two. The mass retained per document varies; u₅ loses all its entries. View largerScroll sideways for the full sketch.

The analysis in Section 3.4 connects the collection sketch to mass retention under its distributional assumptions, including independent or weakly dependent dimensions. Empirically, the paper also examines mass concentration and preservation of inner-product rankings. Those results motivate the design; a particular sketch still has to be evaluated for the embeddings and accuracy target at hand.

Building the index

After applying Set α-MSS, form an inverted list Li for each dimension: it contains the identifiers of documents whose retained coordinate in that dimension is nonzero. These lists are substantially smaller than the lists from the original collection when α is small. Original vectors remain available in the forward index.

Geometric blocks

Next, partition each retained list into geometrically cohesive blocks. The parameter β is a block-count factor: a list of length |Li| is organized into approximately β|Li| blocks. A larger β allows more, smaller blocks and more summaries to examine.

The paper uses a shallow clustering procedure. Sample representatives from the list, then assign each document to the representative with which its full vector has the largest inner product. Each resulting cluster becomes a block. Grouping similar vectors gives a summary a better chance of describing the block usefully. Lists are partitioned independently, so a document can appear in blocks belonging to several dimensions.

Compact block summaries

For a block B, first form its coordinate-wise maximum over the original document vectors. The summary’s coordinate i is φ(B)i = maxu ∈ B ui. For a nonnegative query, this full summary is conservative: its score is at least the score of every document in the block.

But a maximum can accumulate many nonzero coordinates. Seismic compresses it with a γ-MSS, retaining enough of its largest coordinates to reach a fraction γ of its mass. It also applies 8-bit scalar quantization to summary values, storing a subinterval identifier within the summary’s value range.

These smaller summaries are cheaper to store and score. They also lose the full maximum’s upper-bound guarantee. Figure 6 makes that loss concrete: a coordinate with little summary mass can matter greatly to a particular query. The compressed score is therefore a guide for approximate pruning.

A full maximum is conservative; a mass sketch may not be Three nonnegative block vectors have coordinate-wise maximum (0.5, 0.4, 0.08). A gamma-mass sketch with gamma=0.9 keeps the first two coordinates, whose mass is 0.9 out of 0.98, and drops the third. For query q=(0,0,1), the full summary score is 0.08 but the compressed score is zero, demonstrating loss of the upper-bound property. A full maximum is conservative; a mass sketch may not be a geometric block B [ 0.5, 0.3, 0.02 ] [ 0.4, 0.2, 0.08 ] [ 0.2, 0.4, 0.05 ] full maximum φ(B) [0.5, 0.4, 0.08] mass = 0.98 γ-MSS, γ = 0.9 [0.5, 0.4, 0] 0.90 ≥ 0.9 × 0.98 q = [0, 0, 1] best full-vector score = 0.08 compressed summary score = 0 Seismic also quantizes summaries to 8-bit values; pruning uses approximate scores.
Figure 6. A toy block summary before quantization. The full maximum upper-bounds every document score for nonnegative queries. Its γ = 0.9 mass sketch drops the third coordinate, losing that property for q = (0, 0, 1). Seismic further applies 8-bit scalar quantization. View largerScroll sideways for the full sketch.

Full vectors and the optional graph

The forward index retains every document’s complete sparse representation. Whenever a block is selected, Seismic fetches its documents and computes their full inner products with the query. The paper’s implementation uses prefetching to reduce the cost of these scattered accesses, since documents grouped together in one inverted list cannot generally be consecutive in every list.

With κ > 0, index construction also stores κ neighbors per document, measured by inner product. Finding exact neighbors for every document would be expensive, so the experiments build an approximate, high-accuracy graph using Seismic itself without graph refinement. Its storage grows with the collection size and κ, and its construction adds substantial work. Setting κ = 0 omits it.

The parameters now have distinct roles:

ParameterRole
αFraction of nonzero entries retained per dimension by Set α-MSS.
βFactor determining the number of geometric blocks per retained list.
γFraction of each maximum summary’s mass retained before quantization.
κStored neighbors per document; zero disables graph refinement.
αqMass retained in the query sketch that selects inverted lists.
heap_factorQuery-time factor controlling how aggressively blocks are skipped.

Processing a query

Start by taking an αq-MSS of the query. Its nonzero coordinates select which inverted lists to visit. The full query is still used to score both summaries and document vectors. This distinction lets list selection be cheap without throwing away query information when evaluating a candidate.

Maintain a size-k min-heap of the best distinct documents examined so far. Within each selected list, compute every block’s summary score rj = ⟨q, Si,j⟩, then process blocks in decreasing score order. Promising blocks come first, helping establish a strong heap threshold early.

Once the heap contains k documents, let θ be its minimum score and write h for heap_factor, with 0 < h ≤ 1. Following Algorithm 3, skip a block when:

rj<θh.

A smaller h raises this threshold and makes pruning more aggressive. Until the heap is full, this test does not skip blocks. For a block that passes, fetch its documents from the forward index, score them with the full query, and update the heap. Figure 7 shows how the threshold rises when better documents arrive.

Process blocks in summary-score order A toy snapshot begins with a full size-three heap scored 0.40,0.55,0.70 and heap_factor=0.8. The threshold is 0.40/0.8=0.50. The first block has summary score 0.68 and is evaluated, yielding new candidate scores 0.65 and 0.60. The heap becomes 0.60,0.65,0.70, so the threshold rises to 0.75. Remaining blocks scored 0.48 and 0.21 are skipped. Process blocks in summary-score order one selected list first r = 0.68 next r = 0.48 last r = 0.21 a full heap from earlier work [0.40, 0.55, 0.70] h = 0.8 → threshold θ/h = 0.50 r = 0.68 passes: fetch full vectors new full scores: 0.65 and 0.60 [0.60, 0.65, 0.70] new threshold = 0.60 / 0.8 = 0.75 The remaining 0.48 and 0.21 blocks fail the updated test. Values are a toy snapshot.
Figure 7. A toy snapshot of Algorithm 3, with a full heap carried over from earlier work. After the first block improves the heap, θ rises from 0.40 to 0.60. With h = 0.8, the skip threshold rises from 0.50 to 0.75. Later blocks in this list fail the test. View largerScroll sideways for the full sketch.

The sketch, list selection, and compressed summaries all help reduce the search space. Full-vector scoring gives accurate scores for the candidates found, but it cannot restore a document that was never visited. The heap thus contains the best candidates examined, with accuracy controlled empirically through the index and query parameters.

Refining the candidate set with neighbors

Summary-score ordering and graph refinement were introduced in SeismicWave, our CIKM 2024 paper.

If the graph is enabled, take a snapshot of the document identifiers in the heap after inverted-index search. Add the stored neighbors of those initial candidates, compute their full-query scores, and retain the top k over the expanded set.

This is a one-hop expansion: newly discovered neighbors are not recursively expanded. A document missed by the selected lists or skipped blocks can still enter through a strong initial candidate’s neighborhood. Figure 8 shows the deduplicated candidate pool and the resulting reranking.

One-hop graph expansion can recover missed candidates A toy example starts with two candidates u and v. With kappa=2, u links to a,b and v links to b,c. The union adds three distinct neighbors. Full-query reranking of u,v,a,b,c returns a and c. Newly added neighbors are not themselves expanded in this stage. One-hop graph expansion can recover missed candidates initial heap: k = 2 u score .71 v score .62 a .83 b .68 c .77 κ = 2 full-query rerank a .83 c .77 Expand only the initial candidates’ stored neighbors; κ = 0 disables this stage.
Figure 8. A toy one-hop expansion with κ = 2. The initial heap contains u and v; their stored links add a, b, and c. Full-query scores select a and c from the deduplicated pool. The newly added neighbors are not expanded again. View largerScroll sideways for the full sketch.

What the extended experiments show

The draft evaluates MS MARCO v1 (8.8 million passages), Natural Questions, and, for scalability, MS MARCO v2 (138 million passages). Across its experiments it uses SPLADE, Efficient SPLADE, SPLADE-v3, and uniCOIL-T5. Query latency measures index search from an already embedded query to the returned neighbors, using a single query-processing thread; it excludes embedding time.

Figure 9 redraws one slice of Table 1: SPLADE on MS MARCO v1 at 95% accuracy@10. Seismic without graph refinement takes 324 microseconds per query. The other reported latencies range from 836 microseconds for kANNolo to 31,843 for Ioqp. In this setting, the relative speedup is about 2.6× against the fastest listed baseline and 98× against Ioqp. The comparison depends on the baseline, embeddings, and accuracy target.

Measured latency at the same accuracy target Table 1 of the extended paper, SPLADE on MS MARCO v1 at 95 percent accuracy at ten: Seismic without the neighbor graph takes 324 microseconds per query; kANNolo 836; PyAnn 1016; GrassRMA 1271; SparseIvf 10254; Ioqp 31843. Ratios divide each reported latency by 324. Measured latency at the same accuracy target SPLADE / MS MARCO v1 · 95% accuracy@10 method μs / query latency / Seismic Seismic (κ = 0) 324 1.0× kANNolo 836 2.6× PyAnn 1,016 3.1× GrassRMA 1,271 3.9× SparseIvf 10,254 31.6× Ioqp 31,843 98.3× Source: paper Table 1. Single query-processing thread; embedding time excluded.
Figure 9. Reported mean search latencies from the extended paper’s Table 1, SPLADE / MS MARCO v1, at 95% accuracy@10. Ratios divide each latency by Seismic’s 324 μs. Query processing uses one thread and excludes embedding time. View largerScroll sideways for the full sketch.

Graph refinement adds another tradeoff. Table 3 tunes both variants under explicit memory budgets, expressed relative to forward-index size. With SPLADE on MS MARCO v1 and a 2× budget, the reported latency falls from 255 to 156 microseconds at 95% accuracy@10, and from 715 to 387 at 99%. These are separately tuned configurations within the budget. The graph is not faster for every model and target: on SPLADE-v3 at the same 2× budget, for example, the graph-free configuration is faster at 95%.

Figure 10 pairs those SPLADE query results with the larger collection’s construction costs. Table 4 reports MS MARCO v2 indexes of 98.5 GB without the graph and 98.4 GB with it, taking 0.5 and 16.6 hours to build, respectively. The two configurations allocate their memory differently. Similar total index sizes do not make the graph free: neighbor identifiers consume memory that can otherwise support the inverted index and summaries.

The graph trades construction work for stronger search Table 3 reports SPLADE on MS MARCO v1 at twice the forward-index memory budget: at 95 percent accuracy at ten, latency is 255 microseconds without the graph and 156 with it; at 99 percent, 715 and 387. Table 4 separately reports MS MARCO v2 configurations: index sizes 98.5 GB without the graph and 98.4 with it, and build times 0.5 and 16.6 hours. These are separately reported configurations, not a fixed-index controlled ablation. The graph trades construction work for stronger search MS MARCO v1 / SPLADE · 2× memory budget (Table 3) accuracy@10 without κ-NN with κ-NN 95% 255 μs 156 μs 99% 715 μs 387 μs MS MARCO v2 · 138 million vectors (Table 4) configuration index size build time Without κ-NN 98.5 GB 0.5 h With κ-NN 98.4 GB 16.6 h Separate reported configurations: the benefits come with memory and build-time choices.
Figure 10. Selected measurements from Tables 3 and 4. The upper rows compare tuned SPLADE configurations on MS MARCO v1 within a 2× forward-index memory budget. The lower rows report separate MS MARCO v2 build configurations. They are different experiments, rather than a fixed-index graph ablation. View largerScroll sideways for the full sketch.

The scalability study builds on our ECIR 2025 paper and uses a different server with enough local memory for the large indexes. At its 2× memory budget and 98% accuracy cutoff, the extended paper reports Seismic with graph refinement as 6.9× faster than kANNolo, and the graph-free variant as 4.4× faster. These results support the overall design while showing why accuracy, query latency, memory, and construction time should be considered together. Section 5 of the extended paper provides the full tuning protocol, hardware, and results.

Paper, code, and citation

The extended paper contains the sketching definitions and analysis in Section 3, index construction and search in Section 4, and experiments in Section 5. Our open-source implementation is available on GitHub. This work is a collaboration with Franco Maria Nardini, Cosimo Rulli, and Rossano Venturini.

For the development of Seismic, see the SIGIR 2024 paper, the CIKM 2024 SeismicWave paper, the ECIR 2025 scalability study (with Leonardo Venuta), and the extended paper.

The original SIGIR’24 paper, which gives this post its title, received the ACM SIGIR Best Paper Runner-Up Award. For the extended work described here, use:

@misc{bruch2025efficientsketching,
  title = {Efficient Sketching and Nearest Neighbor Search
           Algorithms for Sparse Vector Sets},
  author = {Bruch, Sebastian and Nardini, Franco Maria and
            Rulli, Cosimo and Venturini, Rossano},
  year = {2025},
  eprint = {2509.24815},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi = {10.48550/arXiv.2509.24815},
  url = {https://arxiv.org/abs/2509.24815}
}