[round · platform shape] Ten billion documents, fifty milliseconds

[akash-coded]

Simulated interview round. The shape a large-scale search or platform panel runs.

The prompt

"Rank ten billion documents against a query in under fifty milliseconds. Walk me down the stack —
from the inverted index to the cache line."

What this shape is testing

Whether you can reason about what the big-O hides. At this scale the constants are the design,
and a candidate who says "it's O(log n) so it's fine" has not built one.

The staging, and the arithmetic at each stage

10^10 docs
  |  stage 0  shard + route            ~200 shards, query hits all
  |  stage 1  posting-list intersect   10^10 -> 10^5   skip lists, WAND
  |  stage 2  cheap scoring            10^5  -> 10^3   BM25, no model
  |  stage 3  ANN / learned            10^3  -> 10^2
  |  stage 4  cross-encoder            10^2  -> 10^1   the only place a model can afford to run

The whole game is the funnel. Fifty milliseconds buys roughly one model call over ~100
documents. Everything above stage 4 exists to make those 100 the right 100.

The follow-ups they will actually ask

"Why is your posting list sorted by document id and not by score?" Because intersecting sorted
lists is a merge, and score order destroys the property that makes it linear. Score-sorted lists
serve single-term queries, which are not the hard case.

"Where does the cache line come in?" Posting lists are compressed and decoded in blocks. A skip
pointer jumping outside the current cache line costs a memory round trip — ~100ns against ~1ns of
arithmetic. At 10^5 candidates that is the difference between 10ms and the whole budget.

"What breaks first as you add filters?" WAND's upper-bound pruning assumes it can skip
documents whose maximum possible score is below the threshold. A filter not in the index means you
cannot skip — you must score, then discard. Below ~1% selectivity the funnel inverts.

The trap

Reaching for a vector database. At this scale the dense leg is stage 3, not stage 1 — you
cannot compute 10^10 dot products in 50ms and no index makes that free. Lexical retrieval survives
because posting-list intersection is sublinear in a way full-corpus ANN is not.

[akash-coded]

Marking this, with the rubric and the two answers that separate candidates.

How it is scored

Signal	Weak	Strong
Staging	One retrieval step, then rerank	Names the funnel and the order of magnitude at each stage
Constants	"It's logarithmic"	Names what the big-O hides — cache lines, decode cost, round trips
Filters	An afterthought	Knows filters break WAND pruning, and at what selectivity
Honesty	Confident numbers	"I would measure this; here is roughly what I expect and why"

The two answers that decide it

1 · "The dense leg cannot be stage one at this scale." Most candidates put the vector index
first because that is what tutorials do. Saying why it cannot be — and that lexical intersection is
sublinear in a way full-corpus ANN is not — is the clearest signal available in this round.

2 · Naming the filtered-recall number. ANN benchmarks almost never filter; production always
does. "I would want recall against exhaustive search at 1% filter selectivity, and I would expect
it to be bad" is a sentence almost nobody says, and it is the whole gap between published numbers
and production behaviour.

In this repository, at one ten-millionth of the scale

Issue #2 is the same failure at 2,430 chunks: a graph with no long-range links
where recall@20 = 0.00 at ef=64. Same mechanism, visible on a laptop, and the derivation is
here.

The scale changes the constants. It does not change which thing breaks.