Quadratic Complexity

The self-attention mechanism in a standard transformer encoder has quadratic complexity because it computes pairwise interactions between all tokens in the input sequence. For a sequence of length n, it generates an n x n attention matrix.

• Core Operation: Each token attends to every other token.
• Cost: The number of computations scales as O(n²).
• Reranking Impact: In a cross-encoder, the query and document are concatenated into a single sequence. A long document (e.g., 1000 tokens) with a short query creates a sequence where n is large, making the attention calculation prohibitively expensive for real-time applications.

Processing time doesn't just double when sequence length doubles; it quadruples. This makes cross-encoders acutely sensitive to document and chunk sizes.

• Example: If processing a 500-token sequence takes 100ms, a 1000-token sequence will take approximately 400ms (4x longer), not 200ms.
• Practical Constraint: This forces strict limits on the reranking depth (k) and the maximum document chunk size that can be feasibly processed in a latency-sensitive pipeline like RAG.

Quadratic complexity is the key differentiator between cross-encoders and more scalable architectures.

• Bi-Encoders (O(n)): Encode queries and documents independently with linear complexity relative to total text length, enabling pre-computation of document embeddings.
• Late-Interaction Models (e.g., ColBERT): Use sub-quadratic token-level late interaction, providing deeper matching than bi-encoders without the full O(n²) cost.
• Sparse-Attention Models: Architectures like Longformer or BigBird use engineered attention patterns to reduce complexity to O(n) or O(n log n), enabling longer contexts.

The O(n²) cost translates directly to operational metrics that concern CTOs and engineers.

• Latency: The dominant factor in reranking latency, often making it the slowest stage in a multi-stage retrieval pipeline.
• Compute Cost: Requires more GPU memory (to hold the large attention matrix) and higher FLOPs, increasing cloud inference costs.
• Throughput Limitation: Limits the number of query-document pairs that can be processed per second, constraining system scalability.

Engineering teams employ specific techniques to manage quadratic complexity.

• Input Truncation: Aggressively truncating documents to a fixed token limit (e.g., 512) before feeding to the cross-encoder.
• Cascading Architectures: Using a fast bi-encoder first-stage to narrow candidates to a small k (e.g., 100) before applying the costly cross-encoder on the top k.
• Model Distillation: Training a smaller, more efficient student model (like a bi-encoder) to mimic the ranking behavior of the large cross-encoder teacher.
• Hardware Optimization: Using inference-optimized runtimes (e.g., ONNX, TensorRT) and techniques like quantization to speed up the core matrix operations.

Quadratic complexity is the price paid for the highest accuracy. The full cross-attention in a cross-encoder allows for deep, nuanced understanding of query-document relevance that linear models often cannot match.

• Benchmark Result: On tasks like MS MARCO passage ranking, cross-encoders consistently outperform bi-encoders in terms of NDCG and MRR.
• Design Decision: Choosing a cross-encoder reranker is an explicit decision to prioritize precision and ranking quality over throughput and low latency. This trade-off must be evaluated based on application-specific SLAs.

These models, which jointly encode a query and a candidate document into a single sequence, are acutely affected. The quadratic cost scales with the combined length of the query + document sequence. In a multi-stage retrieval pipeline, reranking just 100 candidates, each 512 tokens long, requires the model to process over 50,000 tokens with quadratic interactions, creating a major latency bottleneck. This cost forces pragmatic limits on reranking depth and document chunk size.

Early neural ranking models that performed full cross-attention between queries and all documents in a corpus were rendered impractical by quadratic complexity. Comparing a query to M documents of length n would incur O(M * n²) cost, making real-time search over large corpora impossible. This limitation drove the adoption of more efficient two-tower bi-encoder architectures for first-stage retrieval.

In computational biology, aligning N biological sequences (like DNA or protein strings) of length L using dynamic programming often involves O(N² * L²) operations. While not a transformer, this is a classic example of quadratic (and quartic) scaling that limits the analysis of large datasets. AI models applied to this domain must contend with similar pairwise comparison challenges.

Message-passing in Graph Neural Networks (GNNs) can exhibit quadratic complexity in the number of nodes when applied to densely connected graphs, as each node may aggregate information from all others. Processing large, dense graphs (e.g., representing social networks or interaction matrices) becomes computationally prohibitive, requiring sampling techniques or simplified aggregation functions.

A reranking model that jointly encodes a query and a candidate document into a single sequence using a transformer encoder. This architecture enables full cross-attention between every token in the query and every token in the document, which is the source of its high accuracy and its O(n²) quadratic complexity. It is the most computationally intensive component in a multi-stage retrieval pipeline.

A fundamental architectural comparison in neural retrieval.

• Bi-Encoder: Encodes the query and document independently into dense vector embeddings. Relevance is computed via a simple, fast similarity function (e.g., cosine). Complexity is O(n), enabling large-scale search.
• Cross-Encoder: Performs joint encoding, allowing deep token-level interaction. This yields superior accuracy for reranking but at quadratic cost O(n²), limiting its use to reordering a small candidate set (e.g., top 100 documents).

The standard pipeline architecture designed to mitigate the cost of quadratic models. It employs a cascade of models with increasing accuracy and computational cost:

1. First Stage (Recall): A fast, high-recall retriever (e.g., BM25, bi-encoder) fetches a large candidate set (e.g., 1000 documents).
2. Second Stage (Reranking): A precise, computationally expensive cross-encoder reranks a much smaller subset (e.g., top 100). This confines the quadratic complexity operation to a manageable scale, optimizing the trade-off between latency and precision.

An intermediate architecture that balances the efficiency of bi-encoders with the expressive power of cross-encoders. Models like ColBERT encode queries and documents independently but compute relevance via a sum of maximum similarity (MaxSim) across all token embeddings. This allows for deeper interaction than simple vector similarity without the full O(n²) pairwise attention of a cross-encoder, offering a favorable performance-cost trade-off.

A class of optimization techniques that modify the transformer's self-attention mechanism to reduce quadratic complexity. Models like Longformer or BigBird use pattern-based sparse attention, where each token only attends to a subset of other tokens (e.g., a local window + global tokens). This reduces complexity from O(n²) to O(n) or O(n log n), enabling the reranking of much longer query-document sequences that would be prohibitive for standard cross-encoders.

The critical operational metric directly impacted by quadratic complexity. It is the end-to-end time delay introduced by applying a reranking model to a candidate set. For a cross-encoder, latency scales quadratically with total sequence length (query + document). Engineers manage this through:

• Controlling reranking depth (k)
• Implementing inference optimizations (quantization, GPU batching)
• Using model distillation to replace large cross-encoders with faster student models Latency is the primary constraint determining the feasibility of a reranker in a real-time system.