BM25 Index Optimization

1 post · May 2025

What this trail covers

Exa has significantly optimized its BM25 index, reducing memory overhead by over 50% across billions of documents. This was achieved through a combination of algorithmic improvements like smart candidate selection and dynamic pruning, and low-level memory structure optimizations. Key techniques include frequency-based organization, variable-length + delta encoding for document IDs, Zstd compression, consolidated buffers, singleton optimization, and further consolidation of buffers into a single consolidated buffer. This optimization has also led to a 10% average query latency drop.

All Exa trails

May 2025Optimizing BM25 for the Next Generation of Semantic Search TechnologyThis post details the optimization of Exa's BM25 index, achieving over 50% memory reduction across billions of documents. Key techniques include: 1. Frequency-Based Organization: Grouping documents by term frequency to reduce redundancy. 2. Variable-length + Delta Encoding for Document IDs: Storing sorted document ID deltas with variable-length encoding to reduce byte usage. 3. Zstd Compression: Applying streamable Zstd compression for further memory reduction. 4. Consolidated Buffers: Flattening inner lists into a single buffer with frequency bitsets and separator tokens to minimize overhead. 5. Singleton Optimization: Special casing tokens appearing only once to avoid metadata overhead. 6. Consolidated Buffers 2.0: Using a single continuous buffer for all compressed postings lists with offset/length pointers in the hash map. These optimizations resulted in a 10% average query latency drop.
Advertisement