sqlite-sparse

The problem

Most semantic search today is dense retrieval. An embedding model turns each document into a vector, and at query time the same model turns the query into a vector so the two can be compared. Every search needs the model, so every place that searches needs the model too: the phone, the laptop, the serverless function, the browser. A learned sparse encoder moves all of that work to write time. A query is tokenized, each token looks up a fixed weight the model ships with, and a document's score is a sum of products. You can also read exactly which words matched and with what weight, which a dense vector never tells you.

How it works

These encoders are BERT models with the masked-language-model head still attached, the layer that scores every vocabulary word as a candidate for a blank. Pointed at every token of a document, it gives a sentence about heart attacks a weight on cardiac even though the word never appears. llama.cpp drops that head when it converts BERT models, because it only uses them for embeddings. sqlite-sparse copies the head into a small sidecar file at conversion time and applies it itself, in C on ggml, after llama.cpp has produced the token vectors.

The index is four ordinary tables, so any language reads it with its SQLite driver. The Python package ships a reference implementation in numpy with no extension at all, and the C code is tested against it for identical ranking. The extension in the browser demo is the same C source with llama.cpp left out: it can search and write indexes but not encode text, and its rankings matched the native binary exactly.

What it costs

Two rows go against it. The index is about twice the size of FTS5's, because the model writes 150 to 300 weighted terms per passage where FTS5 stores the words that are actually there. Indexing is slow: the transformer runs once per document, about 20 documents a second on this CPU, so a million-document index is a half-day job. Build the index where the hardware is and ship the file.

msmarco, 1M documents        FTS5 BM25   dense brute-force   sqlite-sparse
query p50, warm                 582 ms          735 ms           3.1 ms
query p99, warm               1,305 ms          739 ms           7.2 ms
cold process to first result     88 ms        6,989 ms            62 ms
peak RAM on the query path       37 MB          527 MB            28 MB
index size, bytes per document    540             807            1,092
indexing, documents per second ~43,000             167             20.5

Quantization did not cost quality. With a Q8 encoder, one-byte weights and 512-token truncation, the extension lands within 0.001 of the model card's own nDCG@10 on every BEIR set I ran.

Questions

Does sqlite-sparse need a model at query time?

No. The encoder runs once, at INSERT. A query is tokenized, each token looks up a weight stored in the database file, and scoring is an exact sum over posting lists.

How fast is it?

3.1 ms per query across one million MS MARCO passages, in 28 MB of memory, measured on 8 vCPUs with no GPU. On the same machine FTS5 BM25 took 582 ms and brute-force dense search took 735 ms.

Does the quantized encoder lose quality?

No. Within 0.001 nDCG@10 of the model card on SciFact, NFCorpus, SCIDOCS and FiQA, with a Q8 encoder and one-byte weights.

What are the trade-offs?

The index is about twice the size of an FTS5 index, and indexing runs at about 20 documents a second on CPU because the transformer runs once per document. Build the index where the hardware is and ship the file.

How do I install it?

pip install sqlite-sparse, or load the prebuilt sparse0 extension into any SQLite on Linux x86-64 or macOS arm64. It is MIT licensed, on GitHub and PyPI.

Try it

The writeup has a live demo: 4,799 movie overviews indexed into a 10 MB SQLite file, searched by SQLite compiled to WebAssembly with the extension inside, entirely in your tab. Nothing is sent anywhere. To run it yourself:

pip install sqlite-sparse

.load ./sparse0
CREATE VIRTUAL TABLE notes USING sparse0(model='mini');
INSERT INTO notes(rowid, text) VALUES (1, 'Aspirin lowers the risk of heart attack and stroke.');
SELECT rowid, score FROM notes WHERE notes MATCH 'what prevents cardiac arrest' LIMIT 5;

Source and prebuilt binaries: github.com/arbazsiddiqui/sqlite-sparse · package: PyPI · the full story with benchmarks: the writeup