Certified Late-Interaction Retrieval for RAG via Token-Level Triangle Bounds

Retrieval-augmented generation (RAG) is the practice of having a language model look up passages from a document collection before it answers. Its answers are only as good as the few passages it is shown. One of the most accurate ways to pick those passages is late-interaction retrieval, as in ColBERT. There, every query word and every document word gets its own vector. A document's score is the sum, over query words, of the best match each query word finds in the document. This set-to-set score, closely related to Chamfer distance, breaks the triangle inequality. That inequality is what lets classical search indexes skip whole regions of the collection without scoring them. So late-interaction systems today rely on approximate graph search with no guarantee, or on heuristic shortcuts. Nobody knows how the resulting search mistakes change the answers the language model gives.

This note argues that the triangle inequality has not actually been lost. It fails for whole documents but still holds between individual word vectors, because each vector lives in ordinary Euclidean space. We use that fact to derive cheap, provably valid bounds on the late-interaction score from compressed word vectors. The bounds let a retriever skip most exact scoring while still returning the exact top few passages, and they tell the system which queries it has certified. RAG readers only benefit from the top three to five passages; beyond that, extra passages add noise. The plan is therefore to make those few passages exact and cheap, and then to measure how much answer accuracy existing approximate search quietly gives up.

Core Claim

The closest work, α-Reachable Graphs for Multi-vector Nearest Neighbor Search (Chamfer-DiskANN), treats Chamfer distance as a k-quasimetric, a distance whose triangle inequality holds only up to a multiplicative slack. It builds a graph index with approximate guarantees in that setting. It reports only retrieval recall at depth 100, never answer quality. It also found that the obvious speedup, subsampling document vectors, hurt quality. Our work differs in mechanism and in target.

On mechanism, we apply the triangle inequality at the level of individual word vectors rather than whole documents. Let each document word vector $d$ be compressed to a codebook centroid $c(d)$, with residual length $\rho(d)=\|d-c(d)\|$. Let $\rho_D(c)$ be the largest residual among document $D$'s words assigned to centroid $c$, and $C(D)$ the set of centroids $D$ uses. Then for a query word set $Q$, the Chamfer distance satisfies

$$\mathrm{CH}(Q,D)=\sum_{q\in Q}\min_{d\in D}\|q-d\| \;\ge\; \sum_{q\in Q}\min_{c\in C(D)}\big(\|q-c\|-\rho_D(c)\big).$$

This follows from $\|q-d\|\ge\|q-c(d)\|-\rho(d)$ applied to each word pair. ColBERT uses unit-length vectors, so inner-product MaxSim is a monotone function of Euclidean distance and admits the matching upper bound $q\cdot d\le q\cdot c(d)+\rho(d)$.

The bound is cheap to compute. The query-to-centroid distances form one small table, built once per query. After that, bounding any document costs table lookups over its few distinct centroids instead of a full word-by-word comparison.

This is the step that TRIM cannot take. TRIM derives tight lower bounds from compressed codes and prunes up to 99% of distance computations, but it explicitly states that it applies only to metric distances. Our observation is that a non-metric set score built by summing and minimizing a metric score inherits usable bounds from that metric score.

On target, the bounds give a certificate. If the exact score of the $k$-th retrieved passage beats the bound of every document not yet scored, the top-$k$ is exact. We tune for the $k\le5$ regime that RAG actually uses. MIRAGE shows that moving from three to five retrieved chunks already hurts GPT-3.5-Turbo through noise. This makes depth-100 recall the wrong thing to optimize.

Research Program

The first component is the bound itself. We will derive the lower bound for Chamfer distance and the upper bound for MaxSim. We will also derive tighter variants that store a small per-document histogram of residuals per centroid rather than only the maximum. Finally, we will prove when the bound is exact: it is exact when residuals vanish and degrades gracefully as the codebook coarsens.

We will also connect the bound to the quasimetric view in Chamfer-DiskANN. At the set level, the slack factor arises because one document word can serve as the best match for many query words at once. At the word level, that multiplicity never enters.

The second component is a retrieval engine that uses the bounds in two places. The first is inside graph traversal: a neighbor is scored exactly only if its bound says it could enter the current top-$k$. The second is a certification pass. After traversal, a query's top-$k$ is certified exact if every remaining candidate from a cheap coarse index can be ruled out by its bound; otherwise the engine flags the query as uncertified.

We will release per-query certification status as a signal. As an exploratory secondary question, we will ask whether uncertified queries are the ones where the reader's answers go wrong.

The third component is an end-to-end measurement of how search error propagates into answers. Chamfer-DiskANN, Stitching Inner Product and Euclidean Metrics (MAG, a graph that combines Euclidean and inner-product edges for single-vector search), and Retrieval with Learned Similarities (RAILS, a heuristic search over multi-head learned scores) all stop at recall and latency. The ColBERT telecom RAG study runs late-interaction retrieval end to end but treats search as a black box. It still finds that missed passages are the main cause of wrong answers.

We will close this loop by sweeping each system's search budget. At each budget we record reader answer accuracy, not just recall. We use eRAG-style per-document utility, which scores each passage by prompting the reader on it alone. This lets us attribute each answer loss to a specific missed passage.

Baselines

The naive reference point is exhaustive exact late-interaction scoring over the full corpus. It defines "exact top-$k$" and the answer accuracy ceiling for a fixed encoder and reader. It will be run on the same hardware as everything else. It is not a competitor on speed; it is the target for accuracy.

The strongest existing competitor is Chamfer-DiskANN from α-Reachable Graphs for Multi-vector Nearest Neighbor Search. It is the only method in the file that searches the non-metric late-interaction score natively with a graph and a theoretical guarantee. It reports at least 61% more 100Recall@100 than MUVERA, a baseline that compresses each word-vector set into a single fixed vector, on MS MARCO, Quora, NQ and HotpotQA. The file gives this only as a relative figure, with no absolute value.

We will run it on the same ColBERT embeddings, graph degree, and beam-width grid as our system, with an equal tuning budget. Our pruning will be layered onto the same graph, so any difference comes from the bounds. Beating it means one of two things. The first is higher Recall@1–5 and higher reader exact match (EM) at equal query latency. The second is equal accuracy at clearly lower latency and fewer exact score evaluations, while also certifying a substantial fraction of queries, which Chamfer-DiskANN cannot do at all.

A second baseline is the two-stage pipeline most practitioners would build. It generates candidates with mean-pooled single vectors on a standard graph index, then rescores the top $N$ exactly with late interaction. We sweep $N$ to match latency. It has no guarantee, and it probes whether the non-metric difficulty matters in practice.

The key ablation removes the bounds but keeps everything else. It performs graph traversal with exact scoring of every visited node, and certification by brute-force rescoring of the coarse candidate list. This isolates the contribution of word-level triangle bounds.

A second ablation replaces the bounds with the naive vector subsampling that Chamfer-DiskANN reported to fail. It checks that we are not just rediscovering a cheaper but lossier score.

For the reader side, the reference is LongRAG. It groups text into 4,000-token units and gives a long-context reader about 30,000 tokens, reporting 62.7% EM on NQ and 64.3% EM on HotpotQA. We compare against it at matched reader compute, not only matched retrieval compute.

Why not just…?

Why not just map the score into Euclidean space and use a metric index? Efficient Nearest-Neighbor Search in the Probability Simplex shows that some divergences reduce exactly to Euclidean distance. No such reduction is known for Chamfer distance, a sum of minima over variable-size sets. The fixed-vector compression MUVERA is exactly this kind of projection, and Chamfer-DiskANN beats it by at least 61% in deep recall. MAG likewise reports that Euclidean transformations distort neighborhoods for inner-product search. Our approach keeps the original score and moves the metric reasoning down to the word vectors, where it is exact.

Why not just retrieve candidates with single vectors and rescore exactly? This is the most serious practical threat. With a generous rescoring depth it may match our accuracy. Its weakness is that it has no way to know when the true best passage never entered the candidate list. Retrieval with Learned Similarities argues that single dot products have a low-rank limit on what they can match, and the telecom study finds that missed passages are unrecoverable downstream. The latency-matched comparison will settle this. If two-stage retrieval equals our EM at equal latency on all datasets, the speed claim fails and only certification remains. We will say so.

Why not just use coarse chunks and a long-context reader? LongRAG gets strong EM this way, but reports degradation beyond roughly 30,000 tokens, and every query pays for a long reader pass. eRAG shows that short-context processing needs 1.5 GB of GPU memory versus 75.0 GB for its end-to-end setup. We will report EM against total GPU-seconds per query for both approaches. The claim is limited to the budget-constrained regime; if LongRAG dominates there too, that is a negative result worth publishing.

Why not just brute-force the score on a GPU? For corpora of a few million passages this may simply win on wall-clock time; Chamfer-DiskANN lists GPU scoring as open work. Our bounds also reduce brute-force work, because they skip documents before exact scoring. We will therefore report the GPU brute-force crossover point explicitly rather than claim universal speedups.

Proposed Experiments

Retrieval experiments use ColBERT embeddings on MS MARCO, NQ, HotpotQA and Quora, the corpora used by Chamfer-DiskANN. For each system and budget we report four quantities. These are Recall@1, @3 and @5; exact score evaluations per query; latency; and, for our engine, the fraction of queries whose top-5 is certified exact. The first decisive check is whether the bounds prune a large share of exact evaluations at word-vector compression levels already used in practice. TRIM's up-to-99% pruning in metric search sets the aspiration, not an expectation. If the bounds are too loose to prune much, the method fails and we will report that.

End-to-end experiments feed the top 3 and top 5 passages from each system to a fixed open reader, and report EM and F1 on NQ and HotpotQA. We use the TeleQnA setup from the telecom ColBERT study, whose ColBERT-retrieval Phi-2 system reaches 81.9% accuracy. That number serves as a reference only, since our reader and setup will differ. On MIRAGE we report its noise-vulnerability and context-acceptability measures.

The second decisive check is the error-propagation curve: answer EM against search budget for Chamfer-DiskANN and two-stage retrieval, set against the exact-search ceiling. A persistent gap would show that recall at depth 100 hides answer losses at depth 5, and that certification matters. A gap near zero at modest budgets would show that approximate search is already good enough for RAG. The third check asks whether uncertified queries have lower reader accuracy than certified ones at equal recall. If they do, certification status becomes a practical signal for when to retrieve more or abstain. On HotpotQA, where eRAG notes that single-passage utility misleads, we will report this separately rather than pool it.