PaperlayerView exact revision on arXiv

Source-linked AI summary

COIL: Revisit Exact Lexical Match in Information Retrieval with Contextualized Inverted List

Luyu Gao, Zhuyun Dai, Jamie Callan

arXiv:2104.07186v1cs.IRcs.CL

TL;DR

Information retrieval needs to preserve the efficiency of exact lexical matching while addressing vocabulary and semantic mismatch handled by neural systems. COIL stores contextualized token representations in inverted lists and scores overlapping tokens with vector similarities. On two large-scale ad hoc retrieval benchmarks, it substantially improves lexical retrieval and outperforms state-of-the-art dense retrieval systems.

  • Problem

    Exact lexical retrieval is efficient but limited by semantic mismatch, while soft-matching neural systems address richer matching without retaining the same exact-match retrieval structure.

  • Method

    COIL stores deep-LM contextualized representations for document tokens in surface-token inverted lists and compares them with contextualized query tokens during exact matching.

  • Results

    COIL substantially improves lexical retrieval and outperforms state-of-the-art dense retrieval systems on two large-scale ad hoc retrieval benchmarks.

  • Takeaways & Limitations

    Contextualized exact matching gives efficient lexical retrieval richer semantic-aware token signals and the capability to model matching patterns classical systems did not capture.

  • Takeaways & Limitations

    ColBERT’s multi-vector comparison is engineering- and hardware-demanding because document tokens require a single huge index and query-time consideration.

Abstract

from arXiv · show

Classical information retrieval systems such as BM25 rely on exact lexical match and carry out search efficiently with inverted list index. Recent neural IR models shifts towards soft semantic matching all query document terms, but they lose the computation efficiency of exact match systems. This paper presents COIL, a contextualized exact match retrieval architecture that brings semantic lexical matching. COIL scoring is based on overlapping query document tokens' contextualized representations. The new architecture stores contextualized token representations in inverted lists, bringing together the efficiency of exact match and the representation power of deep language models. Our experimental results show COIL outperforms classical lexical retrievers and state-of-the-art deep LM retrievers with similar or smaller latency.

1 Introduction

Classical lexical retrieval is efficient and explainable but struggles with semantic mismatch, while neural soft matching addresses richer matching at higher computational cost. COIL restores contextualized representations to exact lexical matching through inverted lists, combining semantic signals with efficient search.

  • Motivation: Neural IR uses soft matching across query and document terms to address vocabulary and semantic mismatch.Vocabulary mismatch includes different terms expressing the same concept, while semantic mismatch occurs when the same term has different meanings in context.
  • Motivation: Exact lexical matching remains efficient because inverted lists restrict scoring to documents containing query terms.This approach also produces more explainable and controlled matching patterns than soft matching.
  • COIL: COIL replaces heuristic lexical scoring with vector similarities between contextualized representations of overlapping query-document tokens.Documents are encoded offline, token representations are grouped by surface token in inverted lists, and query tokens retrieve and compare against those vectors at search time.
  • COIL: COIL introduces contextualized inverted lists to bring semantic matching into lexical information retrieval systems.The architecture is designed to retain exact query-document token matching while using deep language model representations.
  • Results: COIL outperforms classical lexical retrievers, deep-LM-augmented lexical retrievers, and state-of-the-art dense retrievers on two retrieval tasks.The contribution passage reports significant improvement across these retriever classes.

2 Related Work

Related retrieval systems trade off lexical efficiency, semantic matching, and index complexity. Classical inverted lists support fast exact matching, whereas neural and deep-LM systems add soft or contextualized matching, often with greater computational demands.

  • Lexical Retriever: Classical lexical retrievers use inverted indexes for fast exact matching but struggle with vocabulary and semantic mismatch.Examples include Boolean Retrieval, BM25, and statistical language models.
  • Neural Ranker: Neural retrievers use numerical representations and soft matching to address vocabulary mismatch.Approaches range from word-embedding similarity to single-vector query-document representations.
  • Deep LM Based Ranker and Retriever: Deep-LM rerankers use full cross-attention between contextualized query and document tokens to address vocabulary and semantic mismatch.A common approach concatenates query and document text and uses BERT’s [CLS] output to produce a relevance score.
  • Deep LM Based Ranker and Retriever: Deep-LM-augmented lexical retrievers expand document surface forms or alter term weights, but still suffer from vocabulary and semantic mismatch.Examples include DocT5Query and DeepCT.
  • Deep LM Based Ranker and Retriever: Dense retrievers store document vectors in dense indexes and retrieve them through nearest-neighbor search.Deep language models have produced promising results for these systems on several retrieval tasks.
  • Deep LM Based Ranker and Retriever: Multi-vector systems represent queries and documents with multiple vectors and compute all-to-all soft token matching.ColBERT is described as a representative system in this family.
  • Deep LM Based Ranker and Retriever: ColBERT’s full-token indexing adds another order of magnitude of index complexity and creates engineering and hardware demands.Its collection-wide token vectors must be stored in a single large index and considered at query time.

3 Methodologies

COIL augments exact lexical matching with contextualized token representations while retaining inverted-list retrieval. Its index stores token and optional CLS representations, enabling efficient matching over only query-relevant lists.

  • Comparison with Other Retrievers: COIL retains the efficiency advantage of exact lexical retrieval, whose inverted lists avoid scoring every document, while adding richer semantic representations.Unlike all-to-all soft matching, COIL considers only overlapping query-document tokens, reducing the amount of interaction computation.
  • Contextualized Exact Lexical Match: COIL replaces heuristic exact-match scoring with vector similarities between contextualized representations of overlapping query and document tokens.Documents and queries are encoded with a Transformer language model, and token representations are projected to a lower dimension.
  • Contextualized Exact Lexical Match: For each overlapping query token, COIL compares it with all same-token document representations and retains the maximum similarity before summing token scores.The maximum is intended to capture the most important matching signal while preserving exact lexical overlap.
  • Contextualized Exact Lexical Match: COIL-full adds CLS matching to COIL-tok, providing high-level semantic matching that addresses vocabulary mismatch.COIL-tok uses exact token matching, whereas COIL-full additionally indexes and matches CLS vectors.
  • Index and Retrieval with COIL: COIL builds contextualized inverted lists by grouping offline-computed document-token vectors according to their surface tokens.COIL-full also maintains a separate CLS index for document representations.
  • Index and Retrieval with COIL: At search time, query-token vectors access only the subset of inverted lists corresponding to query tokens, and matrix products compute similarities efficiently.Stacking vectors into matrices enables optimized BLAS operations; different inverted-list scores can be computed in parallel.

4 Experiment Methodologies

The experiments evaluate COIL on two large-scale MSMARCO retrieval benchmarks against lexical, deep-LM-augmented, dense, and soft all-to-all retrievers. They report retrieval effectiveness and latency using matrix-based inverted-list implementations.

  • Datasets: Experiments use MSMARCO passage and document benchmarks, training on MSMARCO Train queries and evaluating on Dev and TREC DL 2019 test queries.The passage collection contains 8M passages averaging around 60 tokens, while the document collection contains 3M documents averaging around 900 tokens.
  • Evaluation: Reported effectiveness metrics include MRR@1K, NDCG@10, MRR@10, and recall across the test and Dev settings.The evaluation mainly covers full-corpus retrieval and also includes the MSMARCO rerank task.
  • Compared Systems: Baselines include BM25, DeepCT, DocT5Query, dense retrievers, and ColBERT, while COIL-tok and COIL-full represent token-only and token-plus-CLS matching.The dense retrievers use BM25 negatives or mixed BM25 and random negatives; rankings for DeepCT and DocT5Query come from their authors.
  • Implementation: COIL uses BERT-base representations, token dimension n_t = 32, and COIL-full CLS dimension n_c = 768, resulting in 110M parameters by default.Models are trained for five epochs with AdamW, a learning rate of 3e-6, and a 0.1 warm-up ratio.
  • Implementation: The inverted-list implementation computes token similarities with matrix products, scatters token scores to documents, and sorts documents for ranking.Matrices are implemented with NumPy on CPU and PyTorch on GPU; latency is measured on dual Xeon E5-2630 v3 and RTX 2080 Ti hardware.

5 Results

COIL improves exact lexical retrieval by adding contextualized token representations and achieves strong effectiveness with practical latency. Its token-level matching captures context-sensitive meanings while retaining efficient inverted-list search.

  • Main results: COIL-tok reaches 0.34 MRR versus BM25’s 0.18 on the MSMARCO passage collection.
  • Main results: COIL-tok outperforms dense retrievers in MRR and NDCG while matching the best dense system in recall.COIL-full further improves performance through CLS matching and outperforms all dense retrievers.
  • Main results: COIL-full captures matching patterns as effectively as ColBERT using exact-match signals from query-token mentions plus one CLS match.This avoids considering all token mentions in the collection for every query token.
  • Main results: In reranking, COIL-tok outperforms dense retrievers, while COIL-full is on par with ColBERT.BERT rerankers require over 2700 ms compared with around 10 ms for COIL.
  • Main results: On the MSMARCO document collection, COIL significantly outperforms lexical and dense systems in MRR and NDCG while retaining a small recall advantage.The results suggest applicability to longer documents with a consistent effectiveness advantage.
  • Dimensionality and latency: Reducing COIL-full’s CLS dimension from 768 to 128 produces a small performance drop but a large speedup, while lower token dimensions add further speedup.Token dimensions of 32 and 8 show very small performance differences in COIL-full when CLS dimension is 128.

6 Conclusion and Future Work

COIL combines contextualized representations with exact lexical matching to address semantic mismatch while preserving efficient inverted-list retrieval. On two large-scale ad hoc retrieval benchmarks, it improves lexical retrieval and outperforms state-of-the-art dense systems, with complementary benefits when combined with dense retrieval.

  • 6 Conclusion and Future Work: COIL replaces token statistics in inverted lists with contextualized vector representations for semantic-aware exact matching.It differentiates identical surface tokens by context while retaining exact token overlap.
  • 6 Conclusion and Future Work: COIL substantially improves lexical retrieval and outperforms state-of-the-art dense retrieval systems on two large-scale ad hoc retrieval benchmarks.The results indicate remaining performance headroom in efficient exact lexical matching.
  • 6 Conclusion and Future Work: The full COIL system performs on par with more expensive and complex all-to-all match retrievers.High-level CLS vector matching largely mitigates vocabulary mismatch in COIL.
  • 6 Conclusion and Future Work: COIL and dense retrieval provide complementary effects by combining token-level matching signals with dense handling of vocabulary mismatch.COIL supplies token-level signals lost by dense retrieval, while dense retrieval addresses vocabulary mismatch for COIL.

A.1 Index Building Illustration

COIL builds an index by processing a document with a fine-tuned deep language model and organizing each token’s contextualized vector under its surface term. The illustration uses the document “apple pie baked ...”.

  • A.1 Index Building Illustration: The document “apple pie baked ...” is first processed by a fine-tuned deep language model.This processing produces a contextualized vector for each document token.
  • A.1 Index Building Illustration: Vectors for each term, including “apple” and “juice”, are collected into the corresponding inverted-list indexes.Each collection is stored with the document identifier for lookup.

A.2 Search Illustration

COIL processes the query “apple juice” by placing contextualized term vectors into matching inverted-list indexes, then computes scores and produces a ranked result.

  • A.2 Search Illustration: Contextualized vectors for the query terms “apple” and “juice” are sent to their corresponding inverted-list indexes.Each index contains a lookup identifier array and a matrix of stacked document-term vectors.
  • A.2 Search Illustration: Matrix-vector products generate score arrays for each query-term index.The search operates on the indexed document vectors associated with the exact lexical matches.
  • A.2 Search Illustration: A max-scatter followed by sorting produces the final document ranking.The figure illustrates this process for the query “apple juice”.
Loading 2104.07186v1…