Late interaction is itself retrieve-then-rescore, one search per query token

MaxSim takes two matrices and returns one number. That is a function on a pair, and a search request is not a pair — it is one query against a corpus, the whole set of documents that have been encoded and stored, which for a production late-interaction system can be five million documents and four billion token vectors. No amount of tensor-level efficiency lets you run a per-pair function four billion vectors deep on every request. Something has to choose which few thousand documents are worth the tensor operation at all.

That decision machinery is a retrieval stage in its own right, with its own recall, its own tuning knobs and its own failure modes, sitting underneath a scoring stage. It is why late interaction is a two-stage cascade internally rather than the single-stage alternative to a cascade that it is sometimes sold as, and it is where most of a real system's tunable behaviour lives. The scoring function from the previous chapter is exact with respect to what is stored; everything that decides what reaches it is an approximation.

The trace of one query, stage by stage#

The first honest measurement anyone takes on a late-interaction service is a per-stage trace of a single query, and it usually looks worse than expected in a place nobody predicted. Here is one from a 5M-document corpus averaging 780 stored tokens, served from a ColBERTv2-style index on a machine with the residuals on NVMe and the centroids in RAM:

query="EntityTooSmall error retrying multipart upload"
  encode_query            2.1 ms   32 vectors
  centroid_probe          4.8 ms   32 tokens x 2 cells = 64 cells
  gather_token_hits       9.3 ms   412,014 token vectors touched
  distinct_documents      3.6 ms   96,318 documents
  centroid_prune          6.2 ms   8,104 documents survive threshold 0.45
  select_ndocs            1.4 ms   1,024 documents kept
  decompress + maxsim    71.5 ms   798,720 token vectors, 205 MB moved
  ------------------------------------------------------------------
  total                  98.9 ms   p50 34 ms / p95 118 ms

Add the seven stage timings and they come to 98.9 ms, which is exactly the total on the line below them. That is worth checking before reading anything else off a trace, because a column that closes on its own total with no residual is a column with no hidden stage in it — no unaccounted serialisation, no queueing before the first line, no network hop between the prune and the rescorer. Every millisecond this query spent is named. When the sum falls short of the total, the gap is the most interesting number in the trace, and here there is no gap.

The last stage is 71.5 of those 98.9 milliseconds, which is 72% of the time, and it is doing the only part of the work the previous chapter described. Everything above it exists to decide which thousand documents that work is performed on.

The p50 and p95 on the last line are the median and the ninety-fifth-percentile latency measured over a run of queries, so the p95 of 118 ms is the figure one query in twenty is worse than, and it is the number a service's timeouts and capacity are set from. Notice that this traced query took 98.9 ms while the median query took 34 ms. The trace is one query and a slow one, sitting between the median and the tail, so its stage breakdown gives the right shape and the wrong levels. The sentence a reader is likely to write after seeing it — that since the stages above the rescorer total a little over 27 ms, the median query must be 27 ms of candidate work and about 7 ms of rescoring — is false, and the table further down contradicts it directly. Fitting that table's median column against its byte column puts the median's rescoring at around twenty milliseconds rather than seven, on a fixed base well under 27. This query was slow at every stage, including the gather, and dividing a percentile by a single sample is the mistake the percentile exists to prevent.

One search per query token, then a union#

The candidate stage inverts the usual relationship between query and index. A single-vector system issues one approximate nearest-neighbour search with one vector. A late-interaction system issues one search per query token, so with query_maxlen=32 there are 32 independent searches, including the searches for the [MASK] positions, and their results are combined by union rather than by intersection.

The union is the step to look at hardest, because it is a design decision rather than a requirement. Nothing in MaxSim forces it. Intersecting the per-token hit lists would produce a much smaller candidate set, and it would also discard exactly the documents late interaction exists to find: a document whose only evidence for one query term sits in a clause the probe missed would be eliminated on that term alone, even though its MaxSim score would be excellent. A union keeps any document that any query token found interesting and pays for that generosity in candidates. Every cost below follows from choosing generosity here.

In ColBERTv2 the search is not run against raw token vectors at all. A k-means codebook — a set of representative points fitted by clustering the token vectors into groups and keeping each group's centre, on the order of 2^18 centroids for a four-billion-vector index — partitions the token embedding space, each stored vector is written as a centroid id plus a compressed residual, the residual being the small offset that carries you from the centroid back to the true vector, and a query token is matched against the centroids rather than against the vectors. The ncells setting controls how many centroids each query token probes, and every token vector assigned to a probed centroid becomes a hit. The trace above shows 64 probed cells yielding 412,014 hits, which is about 6,400 vectors per cell, and those hits belong to 96,318 distinct documents because a corpus this size scatters related tokens widely.

Ninety-six thousand candidates is far too many to run MaxSim over, so PLAID, the engine ColBERTv2 ships with, inserts an approximation between the two. Since the residual is a correction to a centroid, the centroid alone gives a usable estimate of each token's similarity, and a MaxSim computed purely over centroid similarities costs no decompression and no random reads. That estimate prunes 96,318 candidates to 8,104 at a score threshold of 0.45, then the top ndocs of those — 1,024 here — are the only documents whose real vectors are ever fetched. The configuration that ships with ColBERTv2 scales these together, using roughly ncells=1, threshold 0.5 and ndocs=256 when asking for ten results, and widening to ncells=4, threshold 0.4 and ndocs=4096 when asking for a thousand.

Hold the traced configuration against those two shipped ones and it lands between them on every knob at once, exactly. Its ncells=2 is the geometric midpoint of 1 and 4. Its threshold 0.45 is the arithmetic midpoint of 0.5 and 0.4. Its ndocs=1024 is the geometric midpoint of 256 and 4096, since 1,024 squared is 256 times 4,096. Three knobs, three midpoints, no residual on any of them. What that licenses is a reading of the trace as a rung on the shipped ladder rather than as somebody's tuned outlier, which in turn means the latencies either side of it can be reasoned about by the same interpolation instead of being measured from scratch.

Running 32 searches instead of one sounds like a 32x tax on the candidate stage and is not, because the searches share their target. Matching 32 query vectors against 262,144 centroids is a single 32 × 128 by 128 × 262,144 matrix multiply, which is 2.1 GFLOP and finishes in under 5 ms on a CPU with a good BLAS, the tuned linear-algebra library that NumPy and PyTorch call into for matrix multiplication, and the per-token work after that is a lookup rather than a traversal. The multiplier that does hurt is on the gather: 32 tokens each pulling their cells' contents means 32 times as many hit lists to merge and deduplicate, which is why gather_token_hits and distinct_documents together cost more than the probe that produced them.

The [MASK] positions probe the index like any other query token, and they are worth watching because they are two thirds of the query. Their vectors are learned expansions rather than words the user typed, so they widen the candidate set toward documents that are plausibly related without containing the query terms, which is useful for recall and expensive at the gather. Trimming query_maxlen from 32 to 16 on short queries roughly halves the token hits and typically costs a point or two of recall@10, recall@k being the share of the documents that should have been in the top k which actually are; it is the cheapest latency knob in the system and the one least often tried, because the setting is buried in the encoder config rather than the search config.

Every candidate costs its whole document#

The line in the trace that decides the latency budget is the one that reads 798,720 token vectors for 1,024 documents. A candidate qualifies because one or two of its tokens landed in a probed cell, but scoring it exactly requires all of its tokens, since MaxSim takes the maximum over the complete document and the winning match for some query token may be a vector that was never a hit. The per-candidate cost is therefore the document's full token count, not the number of hits it contributed.

That asymmetry is what makes the arithmetic feel unfamiliar coming from single-vector retrieval, where a candidate costs one 3 KB vector and rescoring a thousand of them is 3 MB. Here a thousand candidates at 780 tokens and 256 bytes per token is 205 MB of vectors moved per query — and if the index is compressed to two-bit residuals at roughly 36 bytes per vector, it is 29 MB read from storage and 205 MB after decompression into fp16 for the matrix multiply. The FLOPs are almost beside the point: 32 × 780 × 128 × 2 is 6.4 MFLOP per document and 6.5 GFLOP for the batch, which a modern GPU absorbs in single-digit milliseconds. The system is bound by memory bandwidth and by random reads, so the useful mental model is bytes per query rather than operations per query.

Divide the third column by the second on any row and you get 780, the corpus average, every time. That is not a coincidence and it is not a measurement: the table was built by assuming each candidate is an average-length document, so its byte column contains no variance at all. Read that way, the table is a statement about the expected cost of a depth setting rather than about the cost of any particular query — which matters, because the whole difference between the p50 and the p95 columns is variance the byte column does not have.

Read the remaining columns as gaps rather than as levels and three things fall out. First, the byte budget quadruples down the table, and the p50 increments — the jumps from one row to the next — quadruple with it, which means the median is linear in bytes moved at about a tenth of a millisecond per megabyte, plus a fixed cost. Second, the p95 increments also track the bytes, but at a rate close to five times the median's, while extrapolating back to a fixed cost of the same order in the mid-teens of milliseconds. The tail and the median therefore share a floor and differ almost entirely in what a megabyte costs them, which says the tail is the same work on longer documents rather than a different stage misbehaving. Third, the quality column moves the other way: each quadrupling of the budget cuts the remaining miss — the gap between the recall figure and a perfect one — to roughly a third of what it was, so the bytes spent per eliminated miss rise steeply while the recall number itself looks almost flat. A column that flattens and a column that does not is the ordinary shape of a depth knob, and the flattening is only visible as a level; the cost is only visible as a gap.

Two queries with ndocs=1024 can differ by a factor of five in bytes moved if one of them pulls in a handful of very long documents, and that variance is the subject of chapter 5.

Four counters that explain a latency number#

A latency number alone cannot tell you which stage to tune, because 118 ms at p95 is a different problem depending on whether it came from 96,000 candidates surviving the prune or from 1,024 candidates that happened to be enormous. The four counters worth emitting on every query are the token hits, the distinct candidate documents, the documents actually rescored, and the token vectors touched during rescoring — the last being the one that predicts latency, since it is the byte count in disguise.

from dataclasses import dataclass, asdict

@dataclass
class RetrievalTrace:
    query_tokens: int          # always query_maxlen, but log it to catch config drift
    cells_probed: int
    token_hits: int
    candidate_docs: int        # distinct documents owning those hits
    rescored_docs: int         # after centroid pruning and ndocs
    vectors_rescored: int      # sum of token counts over rescored docs
    latency_ms: float

def observe(trace: RetrievalTrace) -> None:
    metrics.histogram("lir.vectors_rescored", trace.vectors_rescored)
    metrics.histogram("lir.candidate_docs", trace.candidate_docs)
    metrics.histogram("lir.latency_ms", trace.latency_ms)
    if trace.vectors_rescored > 2_000_000:
        log.warning("oversized candidate set", extra=asdict(trace))

The reason to log rescored_docs explicitly rather than assuming it equals ndocs is that the centroid prune can return fewer documents than the budget allows, and a query that rescores 80 documents against a budget of 1,024 is a query whose recall is being set by the threshold rather than by the depth. That distinction is invisible in latency and obvious in the counters.

There is an order to moving these knobs that saves a lot of confused benchmarking, and the order follows from which stage each one lands on. Start from ndocs, because it maps directly onto bytes moved and its effect on quality is measurable within an afternoon; the table above was produced by sweeping only that. Move the centroid threshold second, since it changes how many documents reach the ndocs selection and therefore changes what ndocs is choosing among. Move ncells last, because widening the probe changes the composition of the candidate pool rather than its treatment, and its cost lands on the gather rather than on the rescorer. Changing two of them in one experiment produces a result that cannot be attributed.

A cascade over one encoder, and the recall it can withdraw#

This is not the cascade from the previous topic. A reranking cascade uses two different models, a cheap one to select and an expensive one to reorder, and its second stage sees information the first stage never had. Both stages here use the same token vectors from the same encoder, and the second stage is exact with respect to what is stored while the first is an approximation of it. Improving the candidate stage cannot improve the ranking of documents that already reach the rescorer; it can only stop the rescorer from missing documents. That is a narrower kind of upside than a reranker's, and it caps what tuning the probe can ever be worth.

It is also not a guarantee of recall, and the failure runs against the exact case late interaction was adopted for. A document whose sole evidence for a query is one clause has few tokens capable of being hit, and if none of them fall inside a probed cell, that document never becomes a candidate and its excellent MaxSim score is never computed. The scoring function's headline ability to find a fact buried in a long document is delivered downstream of a stage that can see it quietly withdrawn, which is why the recall column in the table above is measured against exhaustive MaxSim rather than against a relevance judgment. Those are two different questions and only the first one is about the index.

The distinction matters when a quality regression lands. A drop measured against relevance judgments tells you the system got worse and says nothing about where; a drop measured against exhaustive MaxSim isolates the candidate stage from the scorer, because exhaustive MaxSim is what the scorer would have produced given every document. Instrumenting both is how you avoid retuning a threshold to fix a problem that lives in the encoder.

The stage boundary also explains a cost that has been implicit since the first trace line. Everything the rescorer touches has to be fetched from somewhere, and how expensive that fetch is depends entirely on whether four billion vectors fit in memory, on disk, or across a fleet.

That is an arithmetic problem with a specific answer, and the answer is usually larger than the one people carry into the meeting.