The previous article ended with a list of things the engine couldn't do yet. The first one was BM25 — the scoring algorithm every modern search engine uses, and the obvious replacement for the tf-idf + cosine setup I'd built so far. While planning the move I realized I didn't want flat BM25. I wanted BM25F: BM25 with per-field weighting, where the same word appearing in a doc's title scores differently from when it appears in the body. AWS docs are structured — titles, headers, code blocks, prose — and the structure carries signal. Throwing all of it into one bag of words discards that signal.
This article is about the refactor that made BM25F possible. It's not about the math (that's the next article). It's about killing a feature I'd built and was proud of — tiered indexes — to make room for a different one, and rewriting the on-disk posting format so every term's positions know which field they came from.
What tiers were for
In the old engine, each term's postings were split into three tiers by term frequency. Tier 0 held docs where the term appeared more than 5 times. Tier 1 held docs where it appeared 3–5 times. Tier 2 held the long tail — 1 or 2 occurrences. At query time, the retriever read tier 0 first, scored it, and only fell through to tier 1 if it didn't have enough results. Most queries terminated at tier 0.
The reasoning made sense in a flat tf-idf world. With one tf number per (term, doc), you can't easily distinguish "this term is concentrated in this doc" from "this term is sprinkled through this doc." Tiers approximated that distinction by bucketing docs before scoring — high-tf docs were already in tier 0, so reading tier 0 first meant you got the strong matches without ever paying to read the weak ones.
It worked. Tier 0 hits had higher scores. Most queries never read tier 1 or 2. Posting retrieval was fast.
Why they had to go
BM25F changes the picture. Length normalization per field gives the scoring function a direct way to register an "intense match" — a single hit in a short title gets normalized differently from one hit in a long body. The signal tiers were approximating through tf thresholds is something BM25F captures through per-field normalization directly.
The harder question was what tiers would even mean in a BM25F world. With per-field tf, "term frequency" isn't one number anymore — it's tf_title, tf_headers, tf_code, tf_body. Which one do you tier by? Body would throw away the field signal I was about to build. Title would skip docs where a term appears 50 times in the body but never in the title. A weighted sum would add a new tunable on top of the 9 BM25F was already going to introduce.
What I landed on was: tiers were a workaround for flat tf-idf, BM25F made them redundant, and trying to layer them on top would mean tuning two systems against each other. Better to delete tiers, build BM25F clean, measure, and bring tiers back later if latency demands it.
I deleted the tier code. If that turns out to be wrong, it's in git.
The new posting format
The old format stored one positional posting per (term, doc):
{term: {doc_id: [positions]}}Where positions were a flat list. Token at position 47 of the doc was just position 47 — no information about which field that 47 referred to.
The new format adds a field layer:
{term: {doc_id: {field: [positions]}}}Same nesting, one extra level. Title position 0 and body position 0 now live in different coordinate spaces — they represent the first token of each field independently, not the same coordinate. This matters for per-field length normalization later: dl_title and dl_body are different numbers, and positions in each field are gap-encoded against the previous position in that same field, not globally.
The Field type itself is a Rust enum with explicit u8 representation, so it's both type-safe in code and one byte on disk:
#[repr(u8)]
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Field {
Title = 0,
Headers = 1,
Code = 2,
Body = 3,
}The #[repr(u8)] attribute is what makes this work cleanly. Field::Title as u8 is a free cast that produces 0 — the same byte the format writes to disk. The enum also gives me exhaustive matching: if I ever add a fifth field, every scoring site stops compiling until I handle the new case. That's useful for catching the places I'd otherwise forget.
For a single term, the on-disk layout looks like this. Take the term cloudfront appearing in doc 5 (in title position 0, body positions 12 and 47) and doc 9 (body position 88 only):
Three things worth noticing about this format.
Position gaps reset between fields, doc-id gaps don't. When the decoder finishes reading Title's positions and moves to Body, prev_pos resets to 0 — body positions are gap-encoded against each other, independent of where title ended. But prev_doc persists across the entire posting list. The asymmetry reflects the relationship: docs are a flat sorted sequence, fields inside a doc are a small unordered set with their own coordinate space.
Empty fields cost zero bytes. Doc 9 only has the term in its body. The format doesn't write placeholder zeros for the three fields that don't apply. field_count = 1 tells the reader exactly how many field blocks to expect, and that's all.
field_id is one raw byte, not vbyte. There are only 4 fields, so a single byte stores the value with room to spare. Vbyte would still write 1 byte for values under 128, but with framing overhead. Raw byte is simpler and the compression argument doesn't apply at this scale.
Refactor strategy
Seven files use the posting type directly or indirectly. The naive approach is to update them all at once and fight every compile error the Rust compiler produces. The better approach is to walk outward from the change.
Bottom-up means starting at the file with no dependents (or only dependents you're willing to break temporarily) and working up the call graph. For this refactor that order was: encode_decode.rs → traverse.rs → block_merge.rs → get_posting.rs → intersect.rs → tf_idf_index.rs → main.rs. Each file is the foundation for the ones below it.
The first compile produces ~9 errors. They all point back at the type change — every caller of serialize_postings, deserialize_postings, read_postings, and friends complains that the new shape doesn't match the old one. Every error is mechanical. The Rust compiler is acting as a refactoring audit: it walks the call graph for me and tells me every site that needs updating.
One file at a time, the error count drops by one or two per cycle. The errors march down the call graph the way I want them to — each fix unblocks the next layer, and by the time main.rs is reached, every type and function it touches already exists and compiles. main.rs goes from "wire it all together" to "delete the tier loop, replace it with a single pass."
The tier loop in the old main.rs was ~50 lines: iterate three tiers, dedup against a HashSet of seen doc_ids, terminate early when results hit K, and do a final sort across all tiers because cosine normalization made tier-2 short docs sometimes outscore tier-0 long ones. In the new main.rs that whole block is replaced with this:
let term_list = docid_list(&query_list, &term_index);
let results = intersect_all(term_list);
let mut ranked = rank_results(
results,
&query_list,
&term_index,
&doc_stats,
&avg_lengths,
&bm25f_params,
tot_docs,
);
ranked.truncate(k);One retrieval pass. One ranking pass. No dedup, no fallback, no final-merge sort across tiers.
What I lost and what I didn't
The tier system was an early-termination optimization. Reading tier 0 alone meant touching less data per query. The new system reads every term's full posting list, then scores every candidate doc. So I'm doing more work per query than before.
What I gained in exchange is honest field-level scoring. The same term in a title and in a body now scores through completely different normalization paths — and at query time, that's what makes BM25F do useful work. The old tiered tf-idf couldn't have used the new posting format. The new BM25F couldn't have run on the old tiered postings without ugly compromises. The format and the algorithm had to move together.
Latency hasn't blown up — most queries still complete in under 100ms on the 14,266-doc corpus. The dominant cost in query time is the disk seek + read for each term's posting list, and that's unchanged; I'm doing one seek per term either way, just with a different payload shape. If query latency does become a problem at larger scales, the tier code is still in git.
What's still broken
The new posting format exists. The new TermEntry exists. traverse.rs writes field-keyed positions during indexing. block_merge.rs walks all blocks and produces one contiguous posting blob per term. get_posting.rs reads them back. intersect.rs selects candidate docs. But tf_idf_index.rs still has the old tf-idf math. Nothing in this article actually does BM25F yet — the scaffold is in place, the scoring isn't.
That's the next article. It's where the math goes — IDF, per-field length normalization, the pseudo-tf trick that makes the field weights work mathematically. And it's also where I find out how to extract title, headers, code, and body from raw markdown in the first place, because every field needs a clean string going in.