PaperlayerView exact revision on arXiv

Source-linked AI summary

PLAID: An Efficient Engine for Late Interaction Retrieval

Keshav Santhanam, Omar Khattab, Christopher Potts, Matei Zaharia

arXiv:2205.09707v1cs.IRcs.CL

TL;DR

Late interaction retrieval provides strong quality but incurs substantial latency because it uses full token-level passage representations and lacks an end-to-end optimized engine. PLAID accelerates search with centroid interaction, centroid pruning, and optimized kernels that filter candidates before full residual scoring. Against vanilla ColBERTv2, it reports 2.5–7× GPU and 9–45× CPU speedups while retaining state-of-the-art quality, including at 140M passages.

  • Problem

    Late interaction offers state-of-the-art retrieval quality but requires specialized infrastructure because it encodes each passage as a full matrix and lacks a studied end-to-end optimized engine.

  • Method

    PLAID treats passages as bags of centroids, using centroid interaction and centroid pruning to filter candidates before full residual reconstruction and scoring.

  • Results

    2.5–7× GPU and 9–45× CPU latency reductions against vanilla ColBERTv2 are reported while retaining state-of-the-art retrieval quality at scales up to 140M passages.

  • Takeaways & Limitations

    PLAID ColBERTv2 achieves tens-of-milliseconds GPU latency and tens or a few hundred milliseconds CPU latency at very large scale.

  • Takeaways & Limitations

    The reported non-ColBERT latency comparisons use different hardware and implementations and are intended to establish competitiveness rather than absolute comparisons.

Abstract

from arXiv · show

Pre-trained language models are increasingly important components across multiple information retrieval (IR) paradigms. Late interaction, introduced with the ColBERT model and recently refined in ColBERTv2, is a popular paradigm that holds state-of-the-art status across many benchmarks. To dramatically speed up the search latency of late interaction, we introduce the Performance-optimized Late Interaction Driver (PLAID). Without impacting quality, PLAID swiftly eliminates low-scoring passages using a novel centroid interaction mechanism that treats every passage as a lightweight bag of centroids. PLAID uses centroid interaction as well as centroid pruning, a mechanism for sparsifying the bag of centroids, within a highly-optimized engine to reduce late interaction search latency by up to 7$\times$ on a GPU and 45$\times$ on a CPU against vanilla ColBERTv2, while continuing to deliver state-of-the-art retrieval quality. This allows the PLAID engine with ColBERTv2 to achieve latency of tens of milliseconds on a GPU and tens or just few hundreds of milliseconds on a CPU at large scale, even at the largest scales we evaluate with 140M passages.

1 INTRODUCTION

Late interaction delivers strong retrieval quality but is difficult to accelerate because it represents passages as full token-level matrices and lacks an end-to-end optimized search engine. PLAID addresses this gap with centroid-based filtering and optimized implementations, achieving major latency reductions while retaining quality at large scale.

  • Late interaction achieves state-of-the-art quality across passage ranking, open-domain question answering, and conversational retrieval, but represents queries and passages as token-level vectors.
  • Full-matrix passage representations require specialized infrastructure, preventing direct or optimal use of mature sparse and dense retrieval strategies.
  • 2.5–7× GPU and 9–45× CPU latency reductions against vanilla ColBERTv2 are reported while retaining high retrieval quality.
  • PLAID ColBERTv2 reaches tens of milliseconds on GPUs and tens or a few hundred milliseconds on CPUs, including at 140M passages.
  • PLAID uses centroid interaction and centroid pruning to filter low-scoring passages before loading larger residual representations.

2 RELATED WORK

Related work spans neural retrieval architectures from cross-encoders to independent sparse, single-vector, and multi-vector representations. This work focuses on late interaction, extending fast-search ideas from sparse and dense retrieval while addressing index lookup and decompression costs in ColBERTv2.

  • Neural IR models: Neural IR models range from cross-encoders to independent sparse, single-vector, and multi-vector representations.Multi-vector representations are the class studied in this work.
  • PLAID motivation: Vanilla ColBERTv2 is overwhelmingly bottlenecked by index lookup and decompression costs, which PLAID addresses.The latency breakdown concerns MS MARCO v1 dev queries on a TITAN V GPU.
  • Late interaction retrieval: ColBERTv2 combines late interaction with hard-negative and denoising supervision to achieve state-of-the-art quality among standalone retrievers.
  • Fast retrieval: Sparse retrieval commonly accelerates top-k search by storing score metadata, such as term-score upper bounds, to skip lower-scoring candidates.Most such methods use Document-At-A-Time scoring.
  • Fast retrieval: Dense single-vector retrieval relies on approximate k-nearest-neighbor search, whereas this work extends the focus to late interaction between two matrices.

3 ANALYSIS OF COLBERTV2 RETRIEVAL

This section analyzes ColBERTv2 retrieval latency and scoring patterns, showing that centroid-only retrieval can recover strong candidates while avoiding costly residual processing. It motivates centroid interaction and pruning as ways to accelerate late-interaction search.

  • Modeling, Storage, and Retrieval: ColBERTv2 represents queries and passages as token-level vectors and scores passages by summing each query token’s maximum similarity to passage tokens.This late-interaction scoring aligns each query token with its most similar passage token.
  • Modeling, Storage, and Retrieval: ColBERTv2’s residual compression reduces index size by up to an order of magnitude using centroid IDs and quantized residual vectors.The original retrieval strategy is referred to as vanilla ColBERTv2 retrieval.
  • ColBERTv2 Latency Breakdown: Index lookup and residual decompression are overwhelming vanilla ColBERTv2 bottlenecks, especially when the initial candidate set reaches approximately 10–40k passages.These costs arise from memory-bandwidth-heavy vector gathering, variable-length tensor construction, bit unpacking, and large-sum computations.
  • ColBERTv2 Latency Breakdown: Centroids can serve as proxies for passage embeddings, allowing low-scoring passages to be skipped before their larger residual representations are loaded.This motivates using centroid interaction to reduce the cost of exhaustive candidate scoring while maintaining retrieval quality.
  • Centroids Alone Identify Strong Candidates: At 10 · k retrieved candidates, centroid-only search contains 99+% of vanilla ColBERTv2’s top-k passages for both MS MARCO v1 and LoTTE Pooled queries.The experiment compares vanilla ColBERTv2’s top-k passages with rankings produced using centroids without residuals.
  • Not All Centroids Are Important Per Query: A small tail of highly weighted centroids has much larger relevance scores than the remaining centroids, supporting centroid pruning.This score pattern was observed for a random sample of 15 MS MARCO v1 queries and similarly for LoTTE pooled queries.

4 PLAID

PLAID uses centroid-based candidate generation, pruning, and interaction to filter passages before reconstructing embeddings for final ranking. Its implementation adds compact passage indexing and optimized MaxSim and decompression kernels.

  • 4 PLAID: PLAID’s multi-stage pipeline generates candidates, applies centroid pruning and interaction, and performs full residual decompression only for final ranking.Stage 3 uses a heuristic output size of ndocs^4 in the reported experiments.
  • 4.1 Candidate Generation: PLAID generates initial candidates by scoring centroids against query embeddings and retrieving passages assigned to top centroids per query token.The top-t centroids define the candidate set, with t retaining the nprobe terminology from ColBERTv2.
  • 4.1 Candidate Generation: 2.7× space savings reduces the MS MARCO v2 inverted list from 71 GB to 27 GB by mapping centroids to unique passage IDs.PLAID stores passage IDs rather than embedding IDs because there are fewer passages than embeddings.
  • 4.2 Centroid Interaction: Centroid interaction approximates per-passage relevance using centroid IDs, allowing PLAID to filter candidates without reconstructing their residual embeddings.The filtered candidates are then ranked with approximate MaxSim scores, and the top k passages proceed to final scoring.
  • 4.3 Centroid Pruning: Centroid pruning removes low-magnitude centroid scores before approximate scoring, while ndocs specifies the number of candidates selected by Stage 2.The final candidate set is reconstructed through residual decompression and ranked with MaxSim.
  • 4.5 Fast Kernels: Padding-Free MaxSim & Optimized Decompression: Custom CPU kernels compute padding-free MaxSim with O(|Q|) per-thread memory, while optimized decompression uses lookup tables for packed 8-bit values.Corresponding GPU kernels for these implementations remain future work.

5 EVALUATION

The evaluation measures PLAID’s end-to-end latency, retrieval quality, scalability, and optimization contributions across multiple benchmarks, corpus sizes, and hardware settings. PLAID substantially accelerates ColBERTv2 retrieval while generally preserving quality, with gains arising from both centroid-based scoring and implementation optimizations.

  • 5.2 End-to-end Results: PLAID ColBERTv2 matches vanilla ColBERTv2’s MRR@10 and Recall@100 on MS MARCO v1 while achieving 6.8× GPU and 45× CPU speedups.With minimal quality reduction, speedups increase to 12.9–22.6× on GPU and 86.4–145× on CPU.
  • 5.2 End-to-end Results: On Wikipedia OpenQA, PLAID achieves 3.7× GPU and 22× CPU speedups with no quality loss versus vanilla ColBERTv2.With minimal quality loss, speedups reach 7.6–15× on GPU and 42.3–75.7× on CPU.
  • 5.2 End-to-end Results: On LoTTE pooled, PLAID is 2.5× faster on GPU and 9.2× faster on CPU at k=1000 while improving quality over vanilla ColBERTv2.The reported CPU latency is higher than on MS MARCO v1 because LoTTE passages are roughly twice as long on average.
  • 5.2 End-to-end Results: On MS MARCO v2 with 138M passages, PLAID is 20.8× faster than vanilla ColBERTv2 on CPU with no quality loss up to 100 passages.At k=1000, both systems run out of GPU memory; the authors suggest custom padding-free GPU MaxSim kernels as a possible remedy.
  • 5.3 Ablation: Centroid interaction alone provides 5.2× GPU and 8.6× CPU speedups, while implementation optimizations add 1.3× GPU and 4.9× CPU speedups.CPU optimized kernels without centroid interaction yield only a 3× end-to-end speedup, versus 42.4× with complete PLAID.
  • 5.4 Scalability: PLAID latency generally scales with the square root of dataset size, consistent with ColBERTv2’s centroid-count and partitioning design.The scalability evaluation varies both dataset size and CPU parallelism degree.

6 CONCLUSION

PLAID accelerates late-interaction retrieval by filtering candidate passages with centroid-based scoring and optimized kernels. Across several benchmarks, PLAID ColBERTv2 delivers large speedups with virtually no quality loss and scales to 140 million passages.

  • 6 CONCLUSION: PLAID accelerates late-interaction retrieval by cheaply filtering candidate passages using centroid interaction across multiple scoring stages.The method exploits high recall from ColBERTv2 centroids and incorporates centroid pruning into the scoring pipeline.
  • 6 CONCLUSION: PLAID combines centroid interaction with custom padding-free MaxSim and residual-decompression kernels.These algorithmic and implementation components form the optimized PLAID ColBERTv2 engine.
  • 6 CONCLUSION: Across several IR benchmarks, PLAID ColBERTv2 achieves 2.5–6.8× GPU and 9.2–45× CPU speedups with virtually no quality loss versus vanilla ColBERTv2.The evaluation also finds effective scaling to a dataset containing 140 million passages.
Loading 2205.09707v1…