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

Abstract: Classical information retrieval systems such as BM25 rely on exact lexical match and can carry out search efficiently with inverted list index. Recent neural IR models shifts towards soft 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, where 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.

## introduction widely used, bag-of-words (bow) information retrieval (ir) systems such as bm25 rely on exact lexical match 2 between query and document terms. recent study in neural ir takes a different approach and compute soft matching between all query and document terms to model complex matching. the shift to soft matching in neural ir models attempts to address vocabulary mismatch problems, that query and the relevant documents use different terms, e.g. cat v.s. kitty, for the same concept @xcite @xcite . later introduction of contextualized representations @xcite ) from deep language models (lm) further address semantic mismatch, that the same term can refer to different concepts, e.g., bank of river vs. bank in finance. fine-tuned deep lm rerankers produce token representations based on context and achieve state-of1 our code is available at https://github.com/ luyug/coil . though the idea of soft matching all tokens is carried through the development of neural ir models, seeing the success brought by deep lms, we take a step back and ask: how much gain can we get if we introduce contextualized representations back to lexical exact match systems? in other words, can we build a system that still performs exact querydocument token matching but compute matching signals with contextualized token representations instead of heuristics? this may seem a constraint on the model, but exact lexical match produce more explainable and controlled patterns than soft matching. it also allows search to focus on only the subset of documents that have overlapping terms with query, which can be done efficiently with inverted list index. meanwhile, using dense contextualized token representations enables the model to handle semantic mismatch, which has been a long-standing problem in classic lexical systems. to answer the question, we propose a new lexical matching scheme that uses vector similarities between query-document overlapping term contextualized representations to replace heuristic scoring used in classical systems. we present contextualized inverted list (coil), a new exact lexical match retrieval architecture armed with deep lm representations. coil processes documents with deep lm offline and produces representations for each document token. the representations are grouped by their surface tokens into inverted lists. at search time, we build representation vectors for query tokens and perform contextualized exact match: use each query token to look up its own inverted list and compute vector similarity with document vectors stored in the inverted list as matching scores. coil enables efficient search with rich-in-semantic matching between query and document. our contributions include 1) introduce a novel retrieval architecture, contextualized inverted lists (coil) that brings semantic matching into lexical ir systems, 2) show matching signals induced from exact lexical match can capture complicated matching patterns, 3) demonstrate coil significantly outperform classical and deep lm augmented lexical retrievers as well as state-of-theart dense retrievers on two retrieval tasks. ## methodologies in this section, we first provide some preliminaries on exact lexical match systems. then we discuss coil's contextualized exact match design and how its search index is organized. we also give a comparison between coil and other popular retrievers. ## experiment methodologies datasets we experiment with two large scale ad hoc retrieval benchmarks from the trec 2019 deep learning (dl) shared task: msmarco passage (8m english passages of average length around 60 tokens) and msmarco document (3m english documents of average length around 900 tokens) 4 . for each, we train models with the msmarco train queries, and record results on msmarco dev queries and trec dl 2019 test queries. we report mainly full-corpus retrieval results but also include the rerank task on msmarco dev queries where we use neural scores to reorder bm25 retrieval results provided by msmaro organizers. official metrics include mrr@1k and ndcg@10 on test and mrr@10 on msmarco dev. we also report recall for the dev queries following prior work @xcite . ## results this section studies the effectiveness of coil and how vector dimension in coil affects the effectiveness-efficiency tradeoff. we also provide qualitative analysis on contextualized exact match. ## conclusion and future work exact lexical match systems have been widely used for decades in classical ir systems and prove to be effective and efficient. in this paper, we point out a critical problem, semantic mismatch, that generally limits all ir systems based on surface token for matching. to fix semantic mismatch, we introduce contextualized exact match to differentiate the same token in different contexts, providing effective semantic-aware token match signals. we further propose contextualized inverted list (coil) search index which swaps token statistics in inverted lists with contextualized vector representations to perform effective search. on two large-scale ad hoc retrieval benchmarks, we find coil substantially improves lexical retrieval and outperforms state-of-the-art dense retrieval systems. these results indicate large headroom of the simple-but-efficient exact lexical match scheme. when the introduction of contextualization handles the issue of semantic mismatch, exact match system gains the capability of modeling complicated matching patterns that were not captured by classical systems. vocabulary mismatch in coil can also be largely mitigated with a high-level cls vector matching. the full system performs on par with more expensive and complex all-to-all match retrievers. the success of the full system also shows that dense retrieval and coil's exact token matching give complementary effects, with coil making up dense system's lost token level matching signals and dense solving the vocabulary mismatch probably for coil. with our coil systems showing viable search latency, we believe this paper makes a solid step towards building next-generation index that stores semantics. at the intersection of lexical and neural systems, efficient algorithms proposed for both can push coil towards real-world systems.