Dense Retrieval and Dual Encoders: Architecture, Expressivity, and the Cost of Negatives

Overview & motivation

Contrastive learning gave us a loss that teaches an encoder to place a query near its relevant document and far from everything else. It left one question deliberately unasked: what kind of encoder, and what does that choice buy and cost? This topic answers it. The architecture nearly every dense retriever uses is the dual encoder — two towers, a query encoder $E_Q$ and a document encoder $E_P$, whose relevance score is the inner product of their outputs. The choice looks innocuous. It is the most consequential decision in the whole pipeline.

The reason is a single structural fact: the score separates. Query and document never interact until one inner product at the very end. That separability is what we will follow through three movements. First, it is exactly what lets a system precompute every document offline and answer a query with a single maximum-inner-product lookup — the bridge to the entire approximate-nearest-neighbor track, and to the hardness of MIPS. Second, it imposes a hard expressivity ceiling: stack the scores into a relevance matrix and a $d$-dimensional dual encoder can only realize matrices of rank at most $d$, with the truncated SVD — Eckart–Young — the best it can do below that rank. Third, it makes training cheap in a precise, countable way: a batch of $B$ pairs yields a $B \times B$ Gram matrix of similarities, so $2B$ encoder passes buy $B(B-1)$ negative comparisons. The loss is the previous topic’s; here we read the matrix that loss consumes as the object the architecture produces.

A · factorization & MIPSB · the rank-d ceilingC · in-batch Gram trick

bi-encoder (dual)cross-encoder

query-time encoder passes

1 (the query) + MIPS

at |C| = 21,000,000

1 pass + index lookup

passages precomputable?

yes — encode once offline

A dual encoder's score separates: query and document meet only in a single inner product. So every document vector is encoded once, offline into the matrix G, and a query is answered by one matrix-vector product G·E_Q(q) followed by top-k — maximum-inner-product search whose query-time cost is constant in the corpus size. A cross-encoder fuses [q ; d] and must run a joint forward pass for everydocument at query time, so it cannot precompute anything. That separability is exactly what lets the rest of the curriculum index dense vectors (IVF, HNSW, PQ) — and why exact MIPS at scale is its own hard problem.

The first panel toggles the dual encoder against a cross-encoder and watches the query-time cost: the dual encoder is flat in the corpus size because its documents are precomputed, the cross-encoder linear because it must re-score every pair. The second is the rank ceiling — a relevance matrix with finance-sector block structure and its best rank-$d$ reconstruction, with recall collapsing as $d$ drops below the intrinsic rank. The third is the Gram trick: the $B \times B$ matrix whose diagonal is the positives, with the quadratic count of negatives appearing from a linear number of encodings.

The dual encoder and notation

Fix a query $q$ and a corpus of documents $\mathcal{C} = \{d_1, \dots, d_n\}$. A dual encoder is a pair of maps $E_Q, E_P$ into a shared space $\mathbb{R}^d$, and it scores a query–document pair by the inner product of their embeddings,

$$s(q, d) = \langle E_Q(q),\, E_P(d)\rangle.$$

Because dense retrievers L2-normalize, the embeddings are unit vectors and the score is the cosine similarity the retrieval problem took as the relevance functional — but now the vectors are learned, by the InfoNCE loss of the previous topic, rather than counted from term frequencies as in the vector-space model. The defining property is separability: the query appears only through $E_Q(q)$, the document only through $E_P(d)$, and they meet exactly once. Contrast a cross-encoder, which scores a fused input, $s(q,d) = h([q ; d])$, letting query and document attend to each other at every layer. The cross-encoder is strictly more expressive — and, as we are about to see, strictly more expensive. Throughout, $\|M\|_F = (\sum_{ij} M_{ij}^2)^{1/2}$ denotes the Frobenius norm and $\operatorname{rank}(M)$ the rank of a matrix $M$.

Movement 1 — separability ⇒ precomputability ⇒ MIPS

The first consequence of separability is the one that makes dense retrieval deployable at all. Because the document side of the score does not depend on the query, it can be computed before any query arrives.

This is one line, but it is the entire architectural justification for dense retrieval, so we prove it rather than assert it. Its force is in what it makes possible downstream. The precomputed matrix $P$ is precisely the object the approximate-nearest-neighbor track indexes: inverted file partitions, navigable graphs, and product quantization are all sublinear MIPS structures over a fixed $P$ that exists only because the score factorized. The laboratory’s first panel makes the cost gap concrete: a dual encoder’s query-time work is constant in the corpus size — one query encode plus an index lookup — while a cross-encoder, unable to precompute anything, must run a joint forward pass for every one of the $|\mathcal{C}|$ documents. At a Wikipedia-scale index of twenty-one million passages, that is one encode versus twenty-one million. The reduction also inherits an honest ceiling: MIPS hardness shows exact high-dimensional inner-product search has no truly sublinear worst-case algorithm, which is why the index must approximate — but that is a property of the MIPS instance this movement produces, not something it can wish away.

Movement 2 — the rank-d expressivity ceiling

Separability buys precomputability. It also charges a price, and the price is expressivity. Collect the scores of every query against every document into a relevance matrix; the dual encoder can only ever produce matrices of a bounded rank.

When the target relevance pattern has rank above $d$, the dual encoder cannot match it — and the best it can do has a name. By the Eckart–Young–Mirsky theorem (proved in formalML’s SVD topic, which we cite rather than reprove), the closest rank-$d$ matrix to $M$ in Frobenius norm is the truncated SVD $M_d = \sum_{i \le d} \sigma_i u_i v_i^\top$, with error $\|M - M_d\|_F = \big(\sum_{i > d} \sigma_i^2\big)^{1/2}$ — exactly the energy in the discarded singular values. The dual encoder’s reach is therefore the top-$d$ singular structure of the relevance matrix, and nothing more.

The laboratory’s second panel turns this into something you can watch. We build a synthetic finance relevance matrix — four market sectors, each split into two companies, one document per company — so the score matrix has intrinsic rank $8$, the company count. Its singular values fall in two groups: the four largest, $4.86, 3.63, 2.78, 1.84$, are the sectors; the next four, $0.86, 0.62, 0.55, 0.34$, are the finer within-sector company splits. Truncating to a low dimension keeps the sectors and discards the company distinctions, so the best rank-$d$ dual encoder confuses companies inside a sector. Recall@1, measured over all thirty-two queries, climbs from $0.25$ at $d = 1$ — barely better than guessing which of four sectors — through $0.78$ at $d = 3$, and recovers to a perfect $1.0$ only at $d = 6$, with exact reconstruction at $d = 8 = \operatorname{rank}$. Below the intrinsic rank the relevance pattern is literally unrepresentable; the collapse is a theorem, not a tuning artifact.

A cross-encoder has no such ceiling. Because it scores the fused pair rather than a product of separate embeddings, it can realize a full-rank relevance pattern a dual encoder of the same width cannot — the expressivity the bi-encoder trades away for precomputability. (How that extra power is spent in a retrieve-then-rerank cascade is the subject of a later topic; here it is only the rank-free counterpoint.) One caveat is load-bearing, and we state it plainly: $\operatorname{rank}(M) \le d$ says how many dimensions suffice to realize a real-valued score matrix. The dimension relevance actually needs to get the top-$k$ ordering right is governed by the sign-rank (equivalently the margin complexity) of the relevance pattern, which can be far smaller than the rank, or for adversarial patterns far larger. That tight measure is a topic of its own; the rank ceiling here is a clean upper bound, not the last word.

Movement 3 — in-batch negatives and the B²-from-2B Gram trick

The previous topic noted that in-batch negatives are “free.” This movement is the accounting that proves it, and it falls straight out of the same factorization. Training proceeds on batches of paired examples, and the architecture turns each batch into a matrix of similarities for almost nothing.

The companion notebook makes the reuse literal: it never reimplements the loss, only re-reads the Gram matrix the architecture produces, and asserts its row-wise $\log\sum\exp$-minus-diagonal value equals the imported InfoNCE batch loss to within floating-point error. The counting is the headline. A batch of $B = 8$ pairs costs $16$ encoder passes and yields $56$ negatives; $B = 64$ costs $128$ passes and yields $4{,}032$ negatives — the negatives grow as $B^2$ while the encoding grows as $B$, quadratic utility from linear cost. This is the entire reason in-batch-negative training is the default, and combined with Movement 1 of the previous topic — that more negatives raise the $\log(N{+}1)$ ceiling on the mutual information — it is why larger training batches are not just faster but better. The loss has a symmetric form too, $\mathcal{L}_{\text{sym}} = \tfrac12(\mathcal{L}(q \to d) + \mathcal{L}(d \to q))$, the second direction being the same loss on the transposed Gram matrix.

The trick is not free of subtlety, and the honesty matters. The in-batch negatives are shared across the batch — the same $B$ documents serve as negatives for every query — so they are correlated rather than the independent draws the mutual-information bound assumes, and because the positives are mined heuristically, some in-batch “negatives” are false negatives: unlabeled documents that really are relevant to another query, which the loss punishes anyway. Choosing better, harder negatives without falling into that trap is the work of the negative-sampling topic that follows; here we have only established what the in-batch matrix costs and contains.

Finance case study

Honest accounting

The dual encoder is the architecture; the engineering that makes it competitive is where the track goes next. Negative sampling — mining hard negatives without falling into the false-negative trap this topic flagged — turns the in-batch matrix from a cheap source of weak negatives into a strong training signal. The cross-encoder that this topic kept invoking as the rank-free, un-precomputable counterpoint becomes the reranker in a retrieve-then-rerank cascade. And late interaction escapes the single-vector rank ceiling entirely, replacing one pooled dot product with a token-level comparison between many vectors per document. Each builds on the architecture, the expressivity ceiling, and the cost law established here.