Sparse Vectors & SPLADE

Overview

Sparse vectors represent documents and queries as high-dimensional vectors where most dimensions are zero, with each non-zero dimension corresponding to a specific term or learned token weight. Unlike traditional bag-of-words approaches such as BM25 that rely on handcrafted term-frequency heuristics, learned sparse representations like SPLADE (SParse Lexical AnD Expansion) use a neural network to produce term importance weights. This gives them the interpretability and exact-match strength of lexical methods while capturing semantic relationships through learned term expansion.

SPLADE works by passing text through a pretrained language model (typically BERT) and applying a masked language model (MLM) head with log-saturation regularization. The result is a sparse vector over the entire vocabulary, where non-zero entries indicate which terms are important for the document or query — including terms that never appeared in the original text. This term expansion capability bridges the vocabulary mismatch problem that plagues pure lexical search without the computational overhead of dense retrieval at query time.

The real power emerges in hybrid search systems that combine sparse and dense retrieval. Dense vectors excel at capturing broad semantic similarity, while sparse vectors preserve precise lexical signals and offer superior performance on entity-heavy or out-of-domain queries. Modern production search systems combine both modalities, using chunked inverted indexes with Block-Max WAND traversal for efficient sparse search alongside HNSW-based dense search, then fusing the scores for state-of-the-art retrieval quality.

Core Concepts

Sparse vs Dense Representations

Dense vectors (typically 128–1024 dimensions) encode meaning across every dimension, making each individual dimension uninterpretable. Sparse vectors operate in vocabulary-sized space (e.g., 30,522 dimensions for BERT’s WordPiece vocabulary) with only 20–200 non-zero entries per document. This extreme sparsity is what makes inverted indexes viable: you only need to store and traverse posting lists for the non-zero terms, giving you sublinear search time instead of the brute-force or approximate nearest neighbor approaches required for dense vectors.

SPLADE Model Architecture

SPLADE builds on a pretrained transformer encoder. The input text is tokenized and passed through the transformer, producing contextual embeddings for each token. These embeddings are fed into a Masked Language Model (MLM) head — the same head used during BERT’s pretraining — which produces a logit for every vocabulary term at every input position. The final sparse vector is computed by applying a log(1 + ReLU(x)) saturation function to these logits and taking the max across input positions for each vocabulary term:

w_j = max_i log(1 + ReLU(MLM(h_i)_j))

The log-saturation serves two purposes: it prevents any single term from dominating the representation, and its sublinear growth naturally encourages sparsity. During training, an explicit L1 regularization term on the output vector further controls the number of non-zero entries, balancing retrieval effectiveness against index size and query latency.

Inverted Indexes for Sparse Vectors

Just like traditional text search engines, sparse vector search uses inverted indexes. Each vocabulary term maps to a posting list containing (document_id, weight) pairs for every document where that term has a non-zero weight. The critical difference from BM25-style indexes is that posting lists include documents where the term was expanded into by the neural model, not just documents where the term literally appears. This means posting lists tend to be longer, making efficient traversal algorithms essential.

SIMD-Accelerated Decoding

Posting lists are stored in compressed form (e.g., variable-byte or PFOR-delta encoding) and must be decoded during query processing. SIMD (Single Instruction, Multiple Data) instructions allow decoding 4–16 postings simultaneously on modern CPUs. In a Zig-based implementation, Zig’s @Vector built-in maps directly to hardware SIMD lanes, enabling the decoder to process posting blocks at memory bandwidth rather than being bottlenecked by scalar decode logic.

How It Works

SPLADE Encoding Process

At indexing time, each document is tokenized and passed through the SPLADE encoder. The MLM head produces logits over the full vocabulary at each token position, the log-saturation function is applied, and a max-pool across positions yields the final sparse vector. Terms with weights below a threshold (typically 0.1–0.5) are pruned to zero to control index size. The resulting sparse vector — a list of (term_id, weight) pairs — is then inserted into the inverted index by appending the document to each active term’s posting list.

Chunked Inverted Index Structure

Rather than storing each posting list as a single contiguous array, the index is divided into fixed-size chunks (typically 128 or 256 postings per block). Each chunk stores:

• Document IDs: Delta-encoded and optionally PFOR-compressed for cache-friendly sequential access.
• Weights: Quantized to 8-bit or 16-bit integers to reduce memory footprint, stored in a parallel array for SIMD-friendly alignment.
• Block metadata: The maximum weight in the block and the last document ID, used by Block-Max WAND for skip decisions.

Chunks are memory-mapped from disk, enabling the OS page cache to manage hot/cold data automatically. This is critical for production deployments where the full index may exceed available RAM.

Block-Max WAND Traversal

The query is encoded into a sparse vector the same way as documents. For each non-zero query term, the algorithm opens a cursor on the corresponding posting list. The traversal proceeds as follows:

1. Pivot selection: Sort cursors by their current document ID. Find the pivot term such that the sum of maximum possible contributions from the first few terms exceeds the current k-th best score (the threshold).
2. Document evaluation: If all cursors up to the pivot point to the same document, compute the exact score by summing query_weight * doc_weight across all matching terms, and insert into the top-k heap if it exceeds the threshold.
3. Block skipping: If a cursor’s current block’s max weight times the query weight cannot contribute enough to exceed the threshold, skip the entire block by advancing to the next block boundary.
4. Cursor advancement: Advance the lowest cursor to at least the pivot document ID, using block-level metadata to skip irrelevant blocks in O(1).

SIMD-Accelerated Posting Decoding

When a block is selected for evaluation, its compressed document IDs and quantized weights must be decoded. Using SIMD intrinsics, the decoder processes multiple postings in parallel. For example, with 256-bit AVX2 instructions, 8 x 32-bit document IDs can be delta-decoded in a single instruction sequence. The quantized 8-bit weights are widened to 16-bit, multiplied by the query term weight, and accumulated into partial scores — all operating on vectors of 16 or 32 elements at once.

Practical Applications

Hybrid Search in a Production Database

A production vector database implements a hybrid retrieval pipeline that runs sparse (SPLADE) and dense (HNSW) searches in parallel, then fuses results using reciprocal rank fusion (RRF) or weighted linear combination. The sparse path handles exact-match and entity-centric queries with high precision, while the dense path catches semantic matches that share no vocabulary with the query. This hybrid approach consistently outperforms either modality alone by 5–15% on standard benchmarks like BEIR.

High-Performance Sparse Index in Zig

A Zig-based implementation of the sparse vector index provides maximum control over memory layout and SIMD utilization. Zig’s comptime features enable generating specialized decode kernels for different block sizes and quantization levels at compile time, eliminating the branch overhead that would exist in a generic C++ implementation. The memory-mapped chunked index integrates with Zig’s allocator model, allowing precise control over page faulting behavior.

Comparison with Other Approaches

• BM25: Fast and well-understood, but cannot expand queries with related terms. SPLADE matches or exceeds BM25 quality on in-domain benchmarks and dramatically outperforms it on out-of-domain data.
• Dense-only retrieval: Strong semantic matching but struggles with rare entities, numbers, and exact phrases. Also requires expensive ANN index structures (HNSW, IVF) that are harder to update incrementally.
• Hybrid (SPLADE + Dense): State-of-the-art quality. The sparse component is cheaper to serve than a second dense index because inverted indexes support dynamic pruning. Typical latency overhead of adding sparse search is only 2–5ms at the 99th percentile.

Implementation Patterns

Chunked Posting Lists

Divide each posting list into fixed-size blocks (128 or 256 entries). Store block metadata (max_weight, last_doc_id) in a separate array for fast skip decisions. Within each block, delta-encode document IDs and store weights in a parallel array aligned to SIMD lane width. This layout maximizes cache utilization during sequential block scans.

Block-Max Scoring

Precompute and store the maximum weight for each block at index build time. During queries, use these block-max values as upper bounds to determine whether a block can possibly contribute enough score to enter the top-k results. Update the global threshold as better results are found, enabling progressively more aggressive pruning as the heap fills.

Quantized Weights

SPLADE weights are floating-point values typically in the range [0, 5]. Quantize these to 8-bit unsigned integers (0–255) by mapping round(w / max_w * 255). This 4x reduction in weight storage translates to proportionally smaller posting lists and better cache utilization. The quantization error is negligible for retrieval quality — typically less than 0.1% MRR degradation.

Memory-Mapped Indexes

Use mmap to map the on-disk index into virtual memory. The OS page cache handles eviction of cold posting lists automatically. For frequently accessed terms (stopwords and common expansions), the relevant pages stay resident. For tail terms, pages are loaded on demand with minimal overhead. This pattern avoids the complexity of a custom buffer pool while achieving comparable performance for read-heavy workloads.

Score Fusion

When merging sparse and dense results, normalize scores to a comparable range before combining. Two common approaches:

• Reciprocal Rank Fusion (RRF): score = sum(1 / (k + rank_i)) across retrievers. Simple, parameter-free (except k, typically 60), and robust.
• Weighted Linear Combination: score = alpha * sparse_score + (1 - alpha) * dense_score after min-max normalization. Allows tuning the balance per-query or per-domain, but requires score normalization.

Code Examples

Zig: Block-Max WAND with SIMD Decoding

const std = @import("std");
const Allocator = std.mem.Allocator;

const BlockSize = 128;

const BlockMeta = struct {
    max_weight: u8,
    last_doc_id: u32,
};

const PostingBlock = struct {
    doc_ids: [BlockSize]u32,    // delta-encoded
    weights: [BlockSize]u8,     // quantized weights
    len: u32,                   // actual entries in block
};

const PostingList = struct {
    blocks: []PostingBlock,
    block_metas: []BlockMeta,
    num_blocks: u32,
};

const Cursor = struct {
    list: *const PostingList,
    block_idx: u32,
    pos_in_block: u32,
    current_doc: u32,
    query_weight: f32,

    fn maxBlockScore(self: *const Cursor) f32 {
        if (self.block_idx >= self.list.num_blocks) return 0;
        const bm = self.list.block_metas[self.block_idx];
        return self.query_weight * @as(f32, @floatFromInt(bm.max_weight)) / 255.0;
    }

    fn advanceToDoc(self: *Cursor, target: u32) void {
        // Skip entire blocks using block metadata
        while (self.block_idx < self.list.num_blocks) {
            const meta = self.list.block_metas[self.block_idx];
            if (meta.last_doc_id >= target) break;
            self.block_idx += 1;
            self.pos_in_block = 0;
        }
        // Linear scan within the block
        if (self.block_idx < self.list.num_blocks) {
            const block = &self.list.blocks[self.block_idx];
            while (self.pos_in_block < block.len) {
                if (block.doc_ids[self.pos_in_block] >= target) {
                    self.current_doc = block.doc_ids[self.pos_in_block];
                    return;
                }
                self.pos_in_block += 1;
            }
        }
        self.current_doc = std.math.maxInt(u32); // sentinel
    }
};

/// SIMD-accelerated block scoring: multiply doc weights by query weight
/// and accumulate partial scores for documents in a block.
fn simdScoreBlock(
    weights: []const u8,
    query_weight: f32,
    len: u32,
) [BlockSize]f32 {
    var scores: [BlockSize]f32 = [_]f32{0} ** BlockSize;
    const VecLen = 16;

    var i: u32 = 0;
    while (i + VecLen <= len) : (i += VecLen) {
        // Load 16 x u8 weights, widen to f32, multiply
        const raw: @Vector(VecLen, u8) = weights[i..][0..VecLen].*;
        const widened: @Vector(VecLen, f32) = @floatFromInt(raw);
        const qw: @Vector(VecLen, f32) = @splat(query_weight / 255.0);
        const result = widened * qw;
        inline for (0..VecLen) |j| {
            scores[i + j] = result[j];
        }
    }
    // Scalar tail
    while (i < len) : (i += 1) {
        scores[i] = @as(f32, @floatFromInt(weights[i])) *
                    query_weight / 255.0;
    }
    return scores;
}

/// Block-Max WAND top-k search
fn blockMaxWand(
    cursors: []Cursor,
    k: usize,
    allocator: Allocator,
) ![]struct { doc_id: u32, score: f32 } {
    var heap = std.PriorityQueue(
        struct { doc_id: u32, score: f32 },
        void,
        struct {
            fn cmp(_: void, a: anytype, b: @TypeOf(a)) std.math.Order {
                return std.math.order(a.score, b.score);
            }
        }.cmp,
    ).init(allocator, {});
    defer heap.deinit();

    var threshold: f32 = 0;

    while (true) {
        // Sort cursors by current_doc
        std.mem.sort(Cursor, cursors, {}, struct {
            fn lt(_: void, a: Cursor, b: Cursor) bool {
                return a.current_doc < b.current_doc;
            }
        }.lt);

        // Find pivot: smallest prefix whose max scores sum > threshold
        var upper_bound: f32 = 0;
        var pivot: usize = 0;
        for (cursors, 0..) |*c, idx| {
            upper_bound += c.maxBlockScore();
            if (upper_bound > threshold) {
                pivot = idx;
                break;
            }
        }
        if (upper_bound <= threshold) break; // exhausted

        const pivot_doc = cursors[pivot].current_doc;
        if (pivot_doc == std.math.maxInt(u32)) break;

        // Check if all cursors up to pivot point to same doc
        if (cursors[0].current_doc == pivot_doc) {
            // Score this document
            var score: f32 = 0;
            for (cursors) |*c| {
                if (c.current_doc == pivot_doc) {
                    const block = &c.list.blocks[c.block_idx];
                    const w = block.weights[c.pos_in_block];
                    score += c.query_weight *
                             @as(f32, @floatFromInt(w)) / 255.0;
                }
            }
            if (score > threshold) {
                if (heap.count() >= k) _ = heap.removeOrNull();
                try heap.add(.{ .doc_id = pivot_doc, .score = score });
                if (heap.count() >= k) {
                    threshold = heap.peek().?.score;
                }
            }
            // Advance all cursors past pivot_doc
            for (cursors) |*c| {
                if (c.current_doc == pivot_doc) {
                    c.advanceToDoc(pivot_doc + 1);
                }
            }
        } else {
            // Advance cursors before pivot to pivot_doc
            for (cursors[0..pivot]) |*c| {
                c.advanceToDoc(pivot_doc);
            }
        }
    }

    // Drain heap into sorted results
    var results = try allocator.alloc(
        struct { doc_id: u32, score: f32 }, heap.count()
    );
    var i: usize = results.len;
    while (heap.removeOrNull()) |item| {
        i -= 1;
        results[i] = item;
    }
    return results;
}

Python: SPLADE Encoding and Sparse Vector Representation

import torch
import torch.nn.functional as F
from transformers import AutoModelForMaskedLM, AutoTokenizer
from dataclasses import dataclass
from typing import Dict, List, Tuple


@dataclass
class SparseVector:
    """A sparse vector as a dict of term_id -> weight."""
    indices: List[int]
    values: List[float]

    def to_dict(self) -> Dict[int, float]:
        return dict(zip(self.indices, self.values))

    def dot(self, other: "SparseVector") -> float:
        """Compute dot product between two sparse vectors."""
        a = self.to_dict()
        b = other.to_dict()
        shared = set(a.keys()) & set(b.keys())
        return sum(a[k] * b[k] for k in shared)

    def nnz(self) -> int:
        return len(self.indices)


class SPLADEEncoder:
    """Encode text into SPLADE sparse vectors using a pretrained model."""

    def __init__(
        self,
        model_name: str = "naver/splade-cocondenser-ensembledistil",
        device: str = "cpu",
        threshold: float = 0.1,
    ):
        self.tokenizer = AutoTokenizer.from_pretrained(model_name)
        self.model = AutoModelForMaskedLM.from_pretrained(model_name)
        self.model.to(device).eval()
        self.device = device
        self.threshold = threshold

    @torch.no_grad()
    def encode(self, text: str) -> SparseVector:
        """Encode a single text into a sparse vector.

        Steps:
        1. Tokenize input text
        2. Forward pass through transformer + MLM head
        3. Apply log(1 + ReLU(x)) saturation
        4. Max-pool across token positions
        5. Prune entries below threshold
        """
        tokens = self.tokenizer(
            text, return_tensors="pt",
            truncation=True, max_length=256, padding=True
        ).to(self.device)

        # MLM head produces logits over vocabulary at each position
        output = self.model(**tokens)
        logits = output.logits  # shape: [1, seq_len, vocab_size]

        # Log-saturation: log(1 + ReLU(x))
        saturated = torch.log1p(F.relu(logits))

        # Max-pool across sequence positions
        # Mask padding tokens before pooling
        mask = tokens["attention_mask"].unsqueeze(-1)  # [1, seq_len, 1]
        saturated = saturated * mask
        pooled = saturated.max(dim=1).values.squeeze(0)  # [vocab_size]

        # Extract non-zero entries above threshold
        nonzero_mask = pooled > self.threshold
        indices = nonzero_mask.nonzero(as_tuple=True)[0].tolist()
        values = pooled[indices].tolist()

        return SparseVector(indices=indices, values=values)

    def encode_batch(self, texts: List[str]) -> List[SparseVector]:
        """Encode a batch of texts into sparse vectors."""
        tokens = self.tokenizer(
            texts, return_tensors="pt",
            truncation=True, max_length=256, padding=True
        ).to(self.device)

        with torch.no_grad():
            output = self.model(**tokens)
            logits = output.logits
            saturated = torch.log1p(F.relu(logits))
            mask = tokens["attention_mask"].unsqueeze(-1)
            saturated = saturated * mask
            pooled = saturated.max(dim=1).values  # [batch, vocab_size]

        results = []
        for i in range(len(texts)):
            vec = pooled[i]
            nonzero_mask = vec > self.threshold
            indices = nonzero_mask.nonzero(as_tuple=True)[0].tolist()
            values = vec[indices].tolist()
            results.append(SparseVector(indices=indices, values=values))

        return results

    def explain(self, text: str, top_k: int = 20) -> List[Tuple[str, float]]:
        """Show top expanded terms for interpretability."""
        sv = self.encode(text)
        pairs = list(zip(sv.indices, sv.values))
        pairs.sort(key=lambda x: x[1], reverse=True)
        return [
            (self.tokenizer.decode([idx]), weight)
            for idx, weight in pairs[:top_k]
        ]


# Usage example
if __name__ == "__main__":
    encoder = SPLADEEncoder()

    doc_vec = encoder.encode(
        "This database uses HNSW for dense vector search "
        "and chunked inverted indexes for sparse retrieval."
    )
    query_vec = encoder.encode("sparse vector database search")

    print(f"Document sparsity: {doc_vec.nnz()} non-zero entries "
          f"out of 30522 vocab terms")
    print(f"Query sparsity: {query_vec.nnz()} non-zero entries")
    print(f"Dot product score: {doc_vec.dot(query_vec):.4f}")

    print("\nTop expanded terms for query:")
    for token, weight in encoder.explain("sparse vector database search"):
        print(f"  {token:<20s} {weight:.3f}")

Common Pitfalls

1. Ignoring sparsity regularization tuning. SPLADE’s L1 regularization coefficient (lambda) directly controls the trade-off between retrieval quality and index size. Too low and posting lists explode in size, increasing latency and storage. Too high and term expansion is suppressed, degrading quality to BM25 levels. Always benchmark multiple lambda values for your domain.
2. Skipping weight quantization. Storing full 32-bit floats for weights quadruples index size compared to 8-bit quantization, with negligible quality benefit. The continuous weight values from SPLADE are not precise enough to justify float32 storage. Always quantize to at least 16-bit, and prefer 8-bit for production indexes.
3. Using naive score-all traversal instead of Block-Max WAND. Without dynamic pruning, query latency scales linearly with index size. Block-Max WAND typically evaluates only 5–20% of postings while producing identical top-k results. The implementation complexity is modest and the speedup is substantial.
4. Failing to align posting blocks to SIMD widths. If block sizes or weight arrays are not aligned to 16-byte or 32-byte boundaries, SIMD load instructions fall back to slower unaligned paths or require extra shuffle operations. Always pad blocks to the SIMD lane width and ensure proper memory alignment in your allocator.
5. Fusing sparse and dense scores without normalization. Raw SPLADE scores and dense cosine similarities are on different scales. Directly adding them biases the fusion toward whichever modality produces larger numbers. Use min-max normalization per query or rank-based fusion (RRF) to ensure both modalities contribute meaningfully.

Key Takeaways