PaperlayerView exact revision on arXiv

Source-linked AI summary

Compact and Efficient Indexes for Learned Sparse Retrieval

Franco Maria Nardini, Luca Rizzo, Cosimo Rulli, Rossano Venturini

arXiv:2610.12300v1cs.IRcs.DB

TL;DR

Learned sparse retrieval indexes are difficult to make compact while preserving low-latency retrieval. The paper compresses SEISMIC’s selector and forward index, and reports faster, smaller indexes than SINDI at equal accuracy.

  • Problem

    Learned sparse vectors depart from the Zipfian patterns exploited by classical inverted indexes, while SEISMIC answers SPLADE queries in about 200 µs single-threaded but requires about 7 GiB.

    Source: §I · p. 1

  • Method

    The paper replaces SEISMIC’s per-block summaries with medoids and compresses forward-index components and values using reordered Δ-gaps and per-component quantization.

    Source: §I · pp. 1–2

  • Results

    At equal accuracy, SEISMIC is up to 5.3× faster than SINDI while using about 3× less memory; in the most memory-constrained regime, it remains up to 1.9× faster while using up to 3.9× less memory.

    Source: §I · p. 2

  • Takeaways & Limitations

    Forward-index compression is independent of the selector and can be used in other forward-index-based retrieval engines, including KANNOLO.

    Source: §I · p. 2

    Medoid scores are not upper bounds on block maxima, so the paper uses a heap-factor mechanism to recover recall when blocks might otherwise be skipped.

    Source: B. SEISMIC with medoids · p. 4

Abstract

from arXiv · show

This paper investigates how to substantially reduce the memory footprint of learned sparse retrieval indexes without sacrificing the efficiency of state-of-the-art retrieval data structures. Building on SEISMIC, we revisit both levels of its design: the inverted index used to select candidates and the forward index used to score them. For the inverted index, we replace costly per-block summaries with medoids, namely existing documents elected as block representatives, collapsing the per-block metadata from a sparse vector to a single document identifier. For the forward index, we compress both components and values. We reorder the vocabulary to place co-occurring components closer together and encode the resulting $\Delta$-gaps with DOTPACKING8, a SIMD-friendly bit-packing scheme that fuses decompression with dot-product evaluation; values are quantized with compact per-component 4-bit codebooks fitted to each component's distribution. We further introduce JUMPDOT, a blocked dot-product kernel tailored for queries that contain only a few non-zero entries. Our forward-index compression is independent of SEISMIC and can be plugged into any system relying on forward-index-based scoring, as we demonstrate by integrating it into KANNOLO. A comprehensive evaluation on MS MARCO with three state-of-the-art learned sparse encoders shows that our solutions markedly improve the speed-space trade-off of learned sparse retrieval: at equal accuracy, our indexes answer queries up to 5.3x faster than the best competitor while using about 3x less memory, and in the most memory-constrained regime, they remain up to 1.9x faster while using up to 3.9x less memory.

I. INTRODUCTION

The paper targets the memory footprint of learned sparse retrieval indexes while preserving efficient retrieval, revisiting both SEISMIC’s selector and forward index. Its medoid and forward-index compression methods improve the speed–space trade-off on MS MARCO, including when integrated into KANNOLO.

I. INTRODUCTION

  • Although learned sparse representations offer effectiveness, interpretability, and out-of-domain generalization, their non-Zipfian dimensions and weights make classical inverted-index machinery struggle to deliver low-latency top-k retrieval.As retrieval latency enters the microsecond regime, memory becomes the first-order bottleneck; SEISMIC is described as answering SPLADE queries in about 200 µs single-threaded while requiring about 7 GiB.Source: §I · p. 1
  • At equal accuracy, SEISMIC is up to 5.3× faster than SINDI while using about 3× less memory; in the most memory-constrained regime, it remains up to 1.9× faster while using up to 3.9× less memory.The evaluation covers MS MARCO with SPLADE, LILSR, and SPLADE-v3.Source: §I · p. 2
  • On SPLADE-v3, forward-index compression nearly halves KANNOLO’s memory footprint, and on SPLADE it reduces memory by 41% without deteriorating efficiency.Source: §I · p. 2
  • The selector replaces each synthetic per-block summary vector with an existing block document as medoid, reducing per-block metadata to one document identifier.Source: §I · p. 2
  • JUMPDOT uses blocked dot-product computation for extremely sparse queries against highly expanded documents, combining support-proportional computation with SIMD-friendly block matching to skip non-matching blocks.Source: §I · p. 2
  • The forward index compresses component identifiers through vocabulary reordering and SIMD-friendly Δ-gap bit-packing, and compresses values with per-component quantization, including compact 4-bit codebooks.This compression is independent of the selector and can be used in other forward-index-based retrieval engines.Source: §I · p. 2

II. RELATED WORK

Related work addresses learned sparse retrieval’s mismatch with classical inverted indexes, memory overhead in selector metadata, and compression of forward indexes. The paper’s methodology establishes sparse-vector and query notation for describing those retrieval operations.

II. RELATED WORK

  • Learned sparse encoders produce term distributions that depart from Zipfian natural-text patterns, while SEISMIC and related selectors use per-block metadata that adds storage overhead.The paper’s medoid selector replaces synthetic summary vectors with existing block documents as representatives.Source: §II · pp. 2–3
  • Prior forward-index compression couples component decoding with dot-product evaluation, while this work adds vocabulary reordering and per-component quantization; its forward-index compression can be reused in other retrieval engines.The related work contrasts per-component codebooks with collection-level quantization and joint vector quantization.Source: §II · p. 3

III. METHODOLOGY

  • The methodology represents each sparse vector as component-value pairs, defines its support as the components with nonzero values, and treats queries as sparse vectors for top-k search.Source: §III · p. 3

A. SEISMIC

SEISMIC uses a pruned, blocked inverted index to select candidate documents and a forward index to score them exactly. Its per-block summary vectors support safe pruning but contribute substantial memory overhead.

A. SEISMIC

  • For each component, SEISMIC sorts postings by value, truncates the inverted list, partitions the remaining postings into geometrically coherent blocks, and equips each block with a summary vector.Source: A. SEISMIC · pp. 3–4
  • Because query and document vectors are nonnegative, a block summary upper-bounds every member document’s dot product, allowing a block to be safely skipped when its score falls below the current top-k threshold.The summary retains an α-mass subvector and quantizes its surviving values to one byte.Source: A. SEISMIC · p. 4
  • When a block is selected for evaluation, the forward index supplies each document’s complete sparse vector for exact query dot-product scoring and top-k updates.Source: A. SEISMIC · p. 4
  • The forward index grows with collection nonzeros, while the selector adds one summary per block; on the cited SPLADE MS MARCO index, roughly 5M summaries retaining around 100 components each account for nearly half of its about 7 GiB footprint.Source: A. SEISMIC · p. 4

B. SEISMIC with medoids

SEISMIC’s block summaries are replaced by existing documents chosen as medoids, reducing per-block metadata to a document identifier. Because medoid scores are estimates rather than upper bounds, the design retains heap-factor pruning to help recover recall.

B. SEISMIC with medoids

  • Replacing each sparse block summary with a medoid reduces its metadata to a single document identifier, whose coordinates are read from the forward index.The reported storage falls from about 400 bytes to an 8-byte identifier.Source: B. SEISMIC with medoids · p. 4
  • The medoid is the block member with the highest inner product with the block centroid, defined as the component-wise mean.This selects an existing document as the block representative.Source: B. SEISMIC with medoids · p. 4
  • Because a medoid score is not an upper bound on block scores, a block whose maximum score is much higher may be wrongly skipped.The heap-factor mechanism enters blocks when their medoid score exceeds heap_factor · θ_k, with heap_factor in (0, 1).Source: B. SEISMIC with medoids · p. 4
  • Medoid scoring loses SIMD batching and incurs scattered forward-index accesses and L3 cache misses, so the implementation prefetches batches of eight medoids.It issues prefetches before computing the batch’s eight dot products so accesses can overlap with computation.Source: B. SEISMIC with medoids · p. 4

C. Efficient Dot Product Computation

The section compares merge-based and densified sparse dot products, then introduces JUMPDOT to combine support-proportional storage with SIMD-friendly block matching. Its block skipping is suited to short queries scored against longer documents.

C. Efficient Dot Product Computation

  • Merge-based dot product traverses the sorted query and document supports with two pointers, taking O(|s_q| + |s_x|) time but exposing branch-heavy control flow.It touches only non-zero entries and uses memory proportional to the supports.Source: C. Efficient Dot Product Computation · pp. 4–5
  • Densified dot product scatters query weights into a vocabulary-sized array, enabling branch-free vectorized document scans at a memory cost that grows with |C|.Each document component directly indexes the densified query array; large vocabularies can push lookups beyond cache.Source: C. Efficient Dot Product Computation · p. 5
  • JUMPDOT stores documents in blocks of 16 non-zero entries and uses SIMD comparisons to match query components while skipping blocks whose maximum index is too small.The 16 indices and half-precision values occupy one 64-byte cache line; the method retains support-proportional memory without the merge’s per-entry branching.Source: C. Efficient Dot Product Computation · p. 5
  • Block skipping is especially effective for short queries over longer documents, where it discards most document entries at negligible cost.This matches the intended setting of queries with only a few non-zero components.Source: C. Efficient Dot Product Computation · p. 5

D. Forward Index Components Compression

The section develops compressed forward-index component encodings that integrate decoding with scoring, adapting bit-packing and block layouts to short, locally variable document vectors. It also examines reordered gaps and clustered reference compression, with SIMD scoring strategies for both.

D. Forward Index Components Compression

  • Vocabulary reordering by Recursive Graph Bisection places co-occurring terms closer, reducing empirical Shannon entropy from 8.29 to 6.92 and median gap from 72 to 13.The p75 gap also falls from 202 to 63, motivating finer-grained coding than byte-aligned DOTVBYTE.Source: D. Forward Index Components Compression · p. 5
  • Short document vectors make large fixed blocks wasteful: in SPLADE-v3, the median length is 166, while one outlier can force a 128-integer block to use a wider bit-width.The evaluation reports SIMPLE16 outperforming SIMPLE8B and BP32 by adjusting its packing configuration more frequently.Source: D. Forward Index Components Compression · p. 6
  • On remapped SPLADE-v3–MS MARCO identifiers, binary interpolative coding uses 7.06 bits per integer, while Elias–Fano uses 9.30.The passage attributes the former’s result to exploiting dense local clusters and says fixed-bit allocation does not capture that proximity.Source: D. Forward Index Components Compression · p. 6
  • 7.50 bits per integer for DOTPACKINGDP versus 8.24 for DOTPACKING8 on reordered SPLADE-v3–MS MARCO components.The comparison is for sparse embedding components after remapping and Δ-gap encoding.Source: Table I · p. 6, D. Forward Index Components Compression · p. 7
  • DOTPACKING8 packs consecutive Δ-gaps in eight-integer blocks and decodes them into SIMD registers for gather-driven scoring without a separate decompression buffer.Its horizontal bitstream layout uses selectors and a branchless spread-shuffle-shift-mask decoding pipeline.Source: D. Forward Index Components Compression · pp. 6–7
  • DOTPACKING8-J stores each block’s maximum component in an uncompressed header, allowing query processing to skip blocks without decompressing their components.Blocks whose maximum is at least the current query component are decompressed and evaluated in SIMD registers.Source: D. Forward Index Components Compression · p. 7
  • DOTPACKINGDP chooses variable-length blocks to reduce bit waste from local outliers while constraining segments to fit deterministic SIMD loading windows.Its partitioning supports one register for lengths up to eight and at most two deterministic loads for longer blocks; scoring zips decoded chunks into eight-element batches.Source: D. Forward Index Components Compression · p. 7
  • Clustered reference compression splits each embedding into components mapped to a cluster reference list and residual components, then scores mapped entries with two SIMD gathers.The first gather retrieves global identifiers from the reference list; the second fetches query weights for accumulation.Source: D. Forward Index Components Compression · pp. 7–8

E. Forward Index Values Compression

The section compresses forward-index values with per-component quantization and optimizes their dot-product evaluation. Four-bit quantization offers a favorable memory–accuracy trade-off, while implementation choices affect scoring speed.

E. Forward Index Values Compression

  • Per-component quantizers fit each component’s non-zero value distribution, avoiding the resolution loss of a collection-wide scalar quantizer.The paper describes per-component metadata as negligible relative to the forward index because the vocabulary is small.Source: E. Forward Index Values Compression · p. 8
  • For SPLADE and SPLADE-v3, dropping the quantization offset lets each matched component use a single fma, matching f16 or f32 multiplication cost.The ReLU upstream of the encoder ensures nonnegative values, and average component minima are below 10^-4 on these encoders.Source: E. Forward Index Values Compression · p. 8
  • Four-bit quantization halves the memory of the 8-bit configuration at a marginal accuracy cost.The figure reports results for SPLADE on MS MARCO, with 1,000 sampled queries.Source: E. Forward Index Values Compression · p. 8, Figure 1 · p. 8
  • Per-component k-means quantization improves effectiveness over scalar quantization, especially at low bit budgets.At 4 bits, k-means improves effectiveness by 2 points for k=10.Source: E. Forward Index Values Compression · p. 8, Figure 1 · p. 8
  • The dense-query implementation vectorizes codebook lookups, but its larger buffer slows dot products by 30% in a full-scan scenario.The buffer is 2^nbits times larger than the densification array used for scalar quantization.Source: E. Forward Index Values Compression · p. 8

IV. EXPERIMENTAL EVALUATION

The evaluation uses MS MARCO passage retrieval and three learned sparse encoders with differing sparsity profiles. It measures latency, approximation quality, and memory under multiple memory budgets.

IV. EXPERIMENTAL EVALUATION

  • The evaluation uses MS MARCO, with 8.8 million passages and 6,980 dev.small queries.The benchmark is a public English passage-retrieval dataset.Source: §IV · p. 8
  • SPLADE, LILSR, and SPLADE-v3 provide encoder settings with distinct sparsity and retrieval-effectiveness profiles.SPLADE has 119 document and 43 query nonzeros on average, with MRR@10 = 38.3; LILSR has 387 and 6, with MRR@10 = 38.8; SPLADE-v3 has 170 and 25, with MRR@10 = 40.2.Source: §IV · p. 9
  • Indexes are assessed by single-threaded end-to-end latency, Accuracy@k, and memory relative to a 16-bit forward-index baseline.The fastest configuration meeting each target Accuracy@k is reported for each memory budget; experiments run on an Intel Core i9-9940X server.Source: §IV · p. 9

A. Preliminary Ablation Study

The ablations compare medoids with SEISMIC summaries, test forward-index component encodings, and evaluate dot-product kernels. They expose trade-offs among index space, latency, and query sparsity.

Medoids vs. Summary

  • Medoids substantially reduce inverted-index memory versus summaries but increase latency; recovering 95% accuracy requires a lower heap factor and scores 2,875 rather than 664 documents per query.With medoids, the mean pruning-score-to-true-maximum ratio falls from 0.92 to 0.86, and Accuracy@10 drops from 95% to 90% before the heap-factor adjustment.Source: Table II · p. 9, A. Preliminary Ablation Study · p. 9

Forward Index Compression

  • DOTPACKING8 gives the best tested component-encoding speed–space trade-off, reducing the forward index to 2.13 GiB while improving latency over PLAIN-U16 and using 9.4% less space than DOTVBYTE.It is slightly faster than DOTVBYTE at 90% and 99% accuracy and essentially tied at 95%; more aggressively compressed alternatives are slower.Source: Table III · p. 10, A. Preliminary Ablation Study · p. 10

Dot Product Computation

  • On LILSR, DOTPACKING8-J is 2.3× faster at 90% and 2.4× faster at 95% Accuracy@10 than DOTPACKING8, with an 11–14% memory overhead.For expanded-query encoders such as SPLADE and SPLADE-v3, the densified kernel remains faster.Source: A. Preliminary Ablation Study · p. 10

B. Experimental Results

The evaluation compares SEISMIC and KANNOLO variants with learned sparse retrieval baselines across encoders, accuracy targets, and memory budgets. Results vary with the encoder’s sparsity pattern, while compression moves the indexes into lower-memory regimes.

Evaluation setup

  • The evaluation tests SPLADE, LILSR, and SPLADE-v3 at k ∈ {10, 100}, reporting the fastest configuration meeting 90%, 95%, or 99% accuracy within each memory-budget regime.Source: B. Experimental Results · p. 11

SPLADE

  • On SPLADE, SEISMIC [new] saves up to 4.2 GiB with near-original efficiency at memory budgets ≥1; below that, it saves up to 5.4 GiB at a 1.6–3.8× slowdown.KANNOLO [new] is as fast as its base version and uses 41% less memory, reducing space from 4.6 to 2.7 GiB.Source: B. Experimental Results · p. 11

SPLADE-v3

  • On SPLADE-v3, SEISMIC [new] remains near the original SEISMIC latency above the dataset-size budget and reaches 90% and 95% targets below it for both k values.KANNOLO [new] retains the original graph index’s latency profile at moderate accuracy while nearly halving memory.Source: B. Experimental Results · p. 11

LILSR

  • On LILSR, SEISMIC [new] with JUMPDOT and DOTPACKING8-J is the fastest and most memory-efficient specialized method, while both KANNOLO variants are slower than SINDI.The passage attributes the different results to very sparse queries paired with highly expanded documents.Source: B. Experimental Results · p. 11

QDRANT

  • QDRANT makes exact sparse-vector search compact, but its latency is two orders of magnitude above specialized approximate learned sparse indexes.Source: B. Experimental Results · p. 11

C. Ultra Compact Index

The ultra-compact experiment combines compressed components with 4-bit value quantization to bring the total index footprint close to 2 GiB. Centroid-based quantization reaches higher accuracy regimes than scalar quantization, though scalar can be faster in some low-latency settings.

Ultra-compact index

  • The combined 4-bit value and component compression brings the total index close to 2 GiB, about half the dataset-size budget, while preserving about 90% Accuracy@10.Source: C. Ultra Compact Index · p. 12

Value quantization

  • Centroid quantization reaches about 90% Accuracy@10 with a 2.1 GiB index at k = 10 and exceeds 92% Accuracy@100 using 2.2 GiB at k = 100.Scalar quantization is slightly faster in some low-latency configurations but saturates earlier and does not reach the same high-accuracy regime.Source: C. Ultra Compact Index · p. 12
  • Scalar quantization assigns values to 16 uniformly spaced bins per component, whereas centroid quantization learns 16 reconstruction values independently for each component.Source: C. Ultra Compact Index · p. 12

V. CONCLUSIONS AND FUTURE WORK

The paper reduces memory in both parts of SEISMIC’s index while retaining retrieval efficiency. Its MS MARCO evaluation reports improved speed–space trade-offs, and future work will study alternative block representatives.

Conclusion

  • At equal accuracy, SEISMIC is up to 5.3× faster than SINDI while using about 3× less memory; in the most memory-constrained regime, it remains up to 1.9× faster while using up to 3.9× less memory.Source: §V · p. 12
  • The selector replaces per-block sparse summaries with medoids, while the forward index compresses reordered component Δ-gaps with DOTPACKING8 and uses per-component 4-bit value codebooks.Source: §V · p. 12

Conclusion and future work

  • Forward-index compression is orthogonal to SEISMIC and can be used in systems that score candidates through a forward index; future work will test whether multiple or learned representatives recover tighter pruning while retaining compactness.Source: §V · p. 12

Related papers

Loading 2610.12300v1…