The running example · Close Enough

PPriya, co-founder of MarginaliaWEEK 1 · THE PITCH

“Marginalia is search for the inside of books. You type the part where she falls so long she wonders if she’ll come out on the other side of the world, and we take you to the paragraph in Alice in Wonderland. No keywords, just meaning. We start with the public-domain catalogue on Project Gutenberg, about 75,000 books.”

Priya and her co-founder are two people with a GPU budget and a single search server. They are about to discover that the hard part of their product is not the model. It is storing what the model produces.

1From a book to a sequence of vectors

Cut each book into short overlapping windows of text and embed each one.

Fig 3.2.1From a book to vectors

The pipeline 48-word windows with a stride of 24, so each window shares half its words with the next. Each coloured column on the right is one real embedding (the first 24 of its 384 coordinates; colour shows sign and size). Neighbouring columns look alike. Hold on to that.

Embed a booksentence-transformers

from sentence_transformers import SentenceTransformer
import numpy as np

def windows(words, size=48, stride=24):
    for s in range(0, max(1, len(words) - size + 1), stride):
        yield " ".join(words[s:s + size])

model = SentenceTransformer("sentence-transformers/all-MiniLM-L6-v2")   # 384-d
words = open("alice.txt").read().split()
X = model.encode(list(windows(words)), batch_size=256,
                 normalize_embeddings=True)   # (n_windows, 384) float32, unit length
np.save("alice.f32.npy", X)                   # 1,536 bytes per window

2The data used in this book

18 books from the NLTK Gutenberg corpus
88,942 windows (48 words, stride 24)
384 dimensions, float32, unit length
63,120 / 23,490 windows for training / for the database

The split mimics Marginalia’s reality:

Train on 12 books. Codebooks, rotations and probability models are fitted here.
Database: four other books (Moby-Dick, Emma, The Innocence of Father Brown, Leaves of Grass). Everything is scored here.
Queries: 500 windows from two more (Alice in Wonderland, Hamlet).

3Two jobs, two budgets

PPriyaWEEK 3 · THE SPREADSHEET

“75,000 books at about 4,000 windows each is 300 million vectors. At 384 floats each that’s 461 GB. Our search box has 8 GB we can give to the index. And separately, we need to keep the exact embeddings somewhere: re-embedding everything costs real GPU money, and the model we use today will be retired someday.”

300 M windows
1,536 B per vector as 384 × float32
≈ 16 B per vector to fit an 8 GB index, with ids
bit-exact for the archive copy, as small as possible

So Marginalia has two different compression problems.

The search index (lossy) About a 100× reduction. Information may be lost, as long as nearest neighbours stay nearest. → Parts 3, 4 and 5
The archive and the wire (lossless) Every bit must come back. Here the tools of the first half become predictors and probability models. → Part 6

Fig 3.2.2Encode once, compare often

The asymmetry A vector is encoded once, when it enters the index. It is decoded or compared every time a query touches it. This is why it can be worth making encoding very expensive.

4The five-number scorecard

Every method is a different trade between five quantities. After each method you will see a strip like this:

EXAMPLEdistortion lowencode expensivesearch cheaptraining moderate

Rate: bits per vector. Mostly held fixed at 64 bits (8 bytes) for comparisons.
Distortion: relative squared error $\lVert x-\hat x\rVert^2 / \lVert x - \bar x\rVert^2$ , and search recall@10.
Encode cost: compute to turn $x$ into its code. Paid once per vector.
Search cost: compute to compare a query with a code. Paid on every query, for every candidate.
Training cost: compute and data to learn the codebooks.