question:Please summarize the following paper. Provide a deep understanding: ""ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction Keshav Santhanam∗ Stanford University Omar Khattab∗ Stanford University Jon Saad-Falcon Georgia Institute of Technology Christopher Potts Stanford University Matei Zaharia Stanford University Abstract Neural information retrieval (IR) has greatly advanced search and other knowledgeintensive language tasks. While many neural IR methods encode queries and documents into single-vector representations, late interaction models produce multi-vector representations at the granularity of each token and decompose relevance modeling into scalable token-level computations. This decomposition has been shown to make late interaction more effective, but it inflates the space footprint of these models by an order of magnitude. In this work, we introduce ColBERTv2, a retriever that couples an aggressive residual compression mechanism with a denoised supervision strategy to simultaneously improve the quality and space footprint of late interaction. We evaluate ColBERTv2 across a wide range of benchmarks, establishing state-of-the-art quality within and outside the training domain while reducing the space footprint of late interaction models by 6–10×. 1 Introduction Neural information retrieval (IR) has quickly dominated the search landscape over the past 2–3 years, dramatically advancing not only passage and document search (Nogueira and Cho, 2019) but also many knowledge-intensive NLP tasks like opendomain question answering (Guu et al., 2020), multi-hop claim verification (Khattab et al., 2021a), and open-ended generation (Paranjape et al., 2022). Many neural IR methods follow a single-vector similarity paradigm: a pretrained language model is used to encode each query and each document into a single high-dimensional vector, and relevance is modeled as a simple dot product between both vectors. An alternative is late interaction, introduced in ColBERT (Khattab and Zaharia, 2020), where queries and documents are encoded at a finergranularity into multi-vector representations, and ∗Equal contribution. relevance is estimated using rich yet scalable interactions between these two sets of vectors. ColBERT produces an embedding for every token in the query (and document) and models relevance as the sum of maximum similarities between each query vector and all vectors in the document. By decomposing relevance modeling into tokenlevel computations, late interaction aims to reduce the burden on the encoder: whereas single-vector models must capture complex query–document relationships within one dot product, late interaction encodes meaning at the level of tokens and delegates query–document matching to the interaction mechanism. This added expressivity comes at a cost: existing late interaction systems impose an order-of-magnitude larger space footprint than single-vector models, as they must store billions of small vectors for Web-scale collections. Considering this challenge, it might seem more fruitful to focus instead on addressing the fragility of single-vector models (Menon et al., 2022) by introducing new supervision paradigms for negative mining (Xiong et al., 2020), pretraining (Gao and Callan, 2021), and distillation (Qu et al., 2021). Indeed, recent single-vector models with highlytuned supervision strategies (Ren et al., 2021b; Formal et al., 2021a) sometimes perform on-par or even better than “vanilla” late interaction models, and it is not necessarily clear whether late interaction architectures—with their fixed token-level inductive biases—admit similarly large gains from improved supervision. In this work, we show that late interaction retrievers naturally produce lightweight token representations that are amenable to efficient storage off-the-shelf and that they can benefit drastically from denoised supervision. We couple those in ColBERTv2, 1 a new late-interaction retriever that employs a simple combination of distillation from 1Code, models, and LoTTE data are maintained at https: //github.com/stanford-futuredata/ColBERT arXiv:2112.01488v3 [cs.IR] 10 Jul 2022 a cross-encoder and hard-negative mining (§3.2) to boost quality beyond any existing method, and then uses a residual compression mechanism (§3.3) to reduce the space footprint of late interaction by 6–10× while preserving quality. As a result, ColBERTv2 establishes state-of-the-art retrieval quality both within and outside its training domain with a competitive space footprint with typical singlevector models. When trained on MS MARCO Passage Ranking, ColBERTv2 achieves the highest MRR@10 of any standalone retriever. In addition to in-domain quality, we seek a retriever that generalizes “zeroshot” to domain-specific corpora and long-tail topics, ones that are often under-represented in large public training sets. To this end, we evaluate ColBERTv2 on a wide array of out-of-domain benchmarks. These include three Wikipedia Open-QA retrieval tests and 13 diverse retrieval and semanticsimilarity tasks from BEIR (Thakur et al., 2021). In addition, we introduce a new benchmark, dubbed LoTTE, for Long-Tail Topic-stratified Evaluation for IR that features 12 domain-specific search tests, spanning StackExchange communities and using queries from GooAQ (Khashabi et al., 2021). LoTTE focuses on relatively long-tail topics in its passages, unlike the Open-QA tests and many of the BEIR tasks, and evaluates models on their capacity to answer natural search queries with a practical intent, unlike many of BEIR’s semanticsimilarity tasks. On 22 of 28 out-of-domain tests, ColBERTv2 achieves the highest quality, outperforming the next best retriever by up to 8% relative gain, while using its compressed representations. This work makes the following contributions: 1. We propose ColBERTv2, a retriever that combines denoised supervision and residual compression, leveraging the token-level decomposition of late interaction to achieve high robustness with a reduced space footprint. 2. We introduce LoTTE, a new resource for outof-domain evaluation of retrievers. LoTTE focuses on natural information-seeking queries over long-tail topics, an important yet understudied application space. 3. We evaluate ColBERTv2 across a wide range of settings, establishing state-of-the-art quality within and outside the training domain. 2 Background & Related Work 2.1 Token-Decomposed Scoring in Neural IR Many neural IR approaches encode passages as a single high-dimensional vector, trading off the higher quality of cross-encoders for improved efficiency and scalability (Karpukhin et al., 2020; Xiong et al., 2020; Qu et al., 2021). ColBERT’s (Khattab and Zaharia, 2020) late interaction paradigm addresses this tradeoff by computing multi-vector embeddings and using a scalable “MaxSim” operator for retrieval. Several other systems leverage multi-vector representations, including Poly-encoders (Humeau et al., 2020), PreTTR (MacAvaney et al., 2020), and MORES (Gao et al., 2020), but these target attention-based re-ranking as opposed to ColBERT’s scalable MaxSim end-to-end retrieval. ME-BERT (Luan et al., 2021) generates tokenlevel document embeddings similar to ColBERT, but retains a single embedding vector for queries. COIL (Gao et al., 2021) also generates token-level document embeddings, but the token interactions are restricted to lexical matching between query and document terms. uniCOIL (Lin and Ma, 2021) limits the token embedding vectors of COIL to a single dimension, reducing them to scalar weights that extend models like DeepCT (Dai and Callan, 2020) and DeepImpact (Mallia et al., 2021). To produce scalar weights, SPLADE (Formal et al., 2021b) and SPLADEv2 (Formal et al., 2021a) produce a sparse vocabulary-level vector that retains the term-level decomposition of late interaction while simplifying the storage into one dimension per token. The SPLADE family also piggybacks on the language modeling capacity acquired by BERT during pretraining. SPLADEv2 has been shown to be highly effective, within and across domains, and it is a central point of comparison in the experiments we report on in this paper. 2.2 Vector Compression for Neural IR There has been a surge of recent interest in compressing representations for IR. Izacard et al. (2020) explore dimension reduction, product quantization (PQ), and passage filtering for single-vector retrievers. BPR (Yamada et al., 2021a) learns to directly hash embeddings to binary codes using a differentiable tanh function. JPQ (Zhan et al., 2021a) and its extension, RepCONC (Zhan et al., 2022), use PQ to compress embeddings, and jointly train the query encoder along with the centroids produced by PQ via a ranking-oriented loss. SDR (Cohen et al., 2021) uses an autoencoder to reduce the dimensionality of the contextual embeddings used for attention-based re-ranking and then applies a quantization scheme for further compression. DensePhrases (Lee et al., 2021a) is a system for Open-QA that relies on a multi-vector encoding of passages, though its search is conducted at the level of individual vectors and not aggregated with late interaction. Very recently, Lee et al. (2021b) propose a quantization-aware finetuning method based on PQ to reduce the space footprint of DensePhrases. While DensePhrases is effective at Open-QA, its retrieval quality—as measured by top-20 retrieval accuracy on NaturalQuestions and TriviaQA—is competitive with DPR (Karpukhin et al., 2020) and considerably less effective than ColBERT (Khattab et al., 2021b). In this work, we focus on late-interaction retrieval and investigate compression using a residual compression approach that can be applied off-theshelf to late interaction models, without special training. We show in Appendix A that ColBERT’s representations naturally lend themselves to residual compression. Techniques in the family of residual compression are well-studied (Barnes et al., 1996) and have previously been applied across several domains, including approximate nearest neighbor search (Wei et al., 2014; Ai et al., 2017), neural network parameter and activation quantization (Li et al., 2021b,a), and distributed deep learning (Chen et al., 2018; Liu et al., 2020). To the best of our knowledge, ColBERTv2 is the first approach to use residual compression for scalable neural IR. 2.3 Improving the Quality of Single-Vector Representations Instead of compressing multi-vector representations as we do, much recent work has focused on improving the quality of single-vector models, which are often very sensitive to the specifics of supervision. This line of work can be decomposed into three directions: (1) distillation of more expressive architectures (Hofstätter et al., 2020; Lin et al., 2020) including explicit denoising (Qu et al., 2021; Ren et al., 2021b), (2) hard negative sampling (Xiong et al., 2020; Zhan et al., 2020a, 2021b), and (3) improved pretraining (Gao and Callan, 2021; Oguz et al. ˘ , 2021). We adopt similar techniques to (1) and (2) for ColBERTv2’s multivector representations (see §3.2). Question PassageQuestion Encoder Passage Encoder MaxSimMaxSimMaxSimscoreOffline IndexingFigure 1: The late interaction architecture, given a query and a passage. Diagram from Khattab et al. (2021b) with permission. 2.4 Out-of-Domain Evaluation in IR Recent progress in retrieval has mostly focused on large-data evaluation, where many tens of thousands of annotated training queries are associated with the test domain, as in MS MARCO or Natural Questions (Kwiatkowski et al., 2019). In these benchmarks, queries tend to reflect high-popularity topics like movies and athletes in Wikipedia. In practice, user-facing IR and QA applications often pertain to domain-specific corpora, for which little to no training data is available and whose topics are under-represented in large public collections. This out-of-domain regime has received recent attention with the BEIR (Thakur et al., 2021) benchmark. BEIR combines several existing datasets into a heterogeneous suite for “zero-shot IR” tasks, spanning bio-medical, financial, and scientific domains. While the BEIR datasets provide a useful testbed, many capture broad semantic relatedness tasks—like citations, counter arguments, or duplicate questions–instead of natural search tasks, or else they focus on high-popularity entities like those in Wikipedia. In §4, we introduce LoTTE, a new dataset for out-of-domain retrieval, exhibiting natural search queries over long-tail topics. 3 ColBERTv2 We now introduce ColBERTv2, which improves the quality of multi-vector retrieval models (§3.2) while reducing their space footprint (§3.3). 3.1 Modeling ColBERTv2 adopts the late interaction architecture of ColBERT, depicted in Figure 1. Queries and passages are independently encoded with BERT (Devlin et al., 2019), and the output embeddings encoding each token are projected to a lower dimension. During offline indexing, every passage d in the corpus is encoded into a set of vectors, and these vectors are stored. At search time, the query q is encoded into a multi-vector representation, and its similarity to a passage d is computed as the summation of query-side “MaxSim” operations, namely, the largest cosine similarity between each query token embedding and all passage token embeddings: Sq,d = X N i=1 M max j=1 Qi · DT j (1) where Q is an matrix encoding the query with N vectors and D encodes the passage with M vectors. The intuition of this architecture is to align each query token with the most contextually relevant passage token, quantify these matches, and combine the partial scores across the query. We refer to Khattab and Zaharia (2020) for a more detailed treatment of late interaction. 3.2 Supervision Training a neural retriever typically requires positive and negative passages for each query in the training set. Khattab and Zaharia (2020) train ColBERT using the official hq, d+, d−i triples of MS MARCO. For each query, a positive d + is human-annotated, and each negative d − is sampled from unannotated BM25-retrieved passages. Subsequent work has identified several weaknesses in this standard supervision approach (see §2.3). Our goal is to adopt a simple, uniform supervision scheme that selects challenging negatives and avoids rewarding false positives or penalizing false negatives. To this end, we start with a ColBERT model trained with triples as in Khattab et al. (2021b), using this to index the training passages with ColBERTv2 compression. For each training query, we retrieve the top-k passages. We feed each of those query–passage pairs into a cross-encoder reranker. We use a 22M-parameter MiniLM (Wang et al., 2020) crossencoder trained with distillation by Thakur et al. (2021).2 This small model has been shown to exhibit very strong performance while being relatively efficient for inference, making it suitable for distillation. We then collect w-way tuples consisting of a query, a highly-ranked passage (or labeled positive), and one or more lower-ranked passages. In this work, we use w = 64 passages per example. Like RocketQAv2 (Ren et al., 2021b), we use a 2 https://huggingface.co/cross-encoder/ ms-marco-MiniLM-L-6-v2 KL-Divergence loss to distill the cross-encoder’s scores into the ColBERT architecture. We use KLDivergence as ColBERT produces scores (i.e., the sum of cosine similarities) with a restricted scale, which may not align directly with the output scores of the cross-encoder. We also employ in-batch negatives per GPU, where a cross-entropy loss is applied to the positive score of each query against all passages corresponding to other queries in the same batch. We repeat this procedure once to refresh the index and thus the sampled negatives. Denoised training with hard negatives has been positioned in recent work as ways to bridge the gap between single-vector and interaction-based models, including late interaction architectures like ColBERT. Our results in §5 reveal that such supervision can improve multi-vector models dramatically, resulting in state-of-the-art retrieval quality. 3.3 Representation We hypothesize that the ColBERT vectors cluster into regions that capture highly-specific token semantics. We test this hypothesis in Appendix A, where evidence suggests that vectors corresponding to each sense of a word cluster closely, with only minor variation due to context. We exploit this regularity with a residual representation that dramatically reduces the space footprint of late interaction models, completely off-the-shelf without architectural or training changes. Given a set of centroids C, ColBERTv2 encodes each vector v as the index of its closest centroid Ct and a quantized vector r˜ that approximates the residual r = v − Ct . At search time, we use the centroid index t and residual r˜ recover an approximate v˜ = Ct + ˜r. To encode r˜, we quantize every dimension of r into one or two bits. In principle, our b-bit encoding of n-dimensional vectors needs dlog |C|e + bn bits per vector. In practice, with n = 128, we use four bytes to capture up to 2 32 centroids and 16 or 32 bytes (for b = 1 or b = 2) to encode the residual. This total of 20 or 36 bytes per vector contrasts with ColBERT’s use of 256-byte vector encodings at 16-bit precision. While many alternatives can be explored for compression, we find that this simple encoding largely preserves model quality, while considerably lowering storage costs against typical 32- or 16-bit precision used by existing late interaction systems. This centroid-based encoding can be considered a natural extension of product quantization to multi- vector representations. Product quantization (Gray, 1984; Jegou et al., 2010) compresses a single vector by splitting it into small sub-vectors and encoding each of them using an ID within a codebook. In our approach, each representation is already a matrix that is naturally divided into a number of small vectors (one per token). We encode each vector using its nearest centroid plus a residual. Refer to Appendix B for tests of the impact of compression on retrieval quality and a comparison with a baseline compression method for ColBERT akin to BPR (Yamada et al., 2021b). 3.4 Indexing Given a corpus of passages, the indexing stage precomputes all passage embeddings and organizes their representations to support fast nearestneighbor search. ColBERTv2 divides indexing into three stages, described below. Centroid Selection. In the first stage, ColBERTv2 selects a set of cluster centroids C. These are embeddings that ColBERTv2 uses to support residual encoding (§3.3) and also for nearestneighbor search (§3.5). Standardly, we find that setting |C| proportionally to the square root of nembeddings in the corpus works well empirically.3 Khattab and Zaharia (2020) only clustered the vectors after computing the representations of all passages, but doing so requires storing them uncompressed. To reduce memory consumption, we apply k-means clustering to the embeddings produced by invoking our BERT encoder over only a sample of all passages, proportional to the square root of the collection size, an approach we found to perform well in practice. Passage Encoding. Having selected the centroids, we encode every passage in the corpus. This entails invoking the BERT encoder and compressing the output embeddings as described in §3.3, assigning each embedding to the nearest centroid and computing a quantized residual. Once a chunk of passages is encoded, the compressed representations are saved to disk. Index Inversion. To support fast nearestneighbor search, we group the embedding IDs that correspond to each centroid together, and save this inverted list to disk. At search time, this allows us to quickly find token-level embeddings similar to those in a query. 3We round down to the nearest power of two larger than 16 × √nembeddings, inspired by FAISS (Johnson et al., 2019). 3.5 Retrieval Given a query representation Q, retrieval starts with candidate generation. For every vector Qi in the query, the nearest nprobe ≥ 1 centroids are found. Using the inverted list, ColBERTv2 identifies the passage embeddings close to these centroids, decompresses them, and computes their cosine similarity with every query vector. The scores are then grouped by passage ID for each query vector, and scores corresponding to the same passage are maxreduced. This allows ColBERTv2 to conduct an approximate “MaxSim” operation per query vector. This computes a lower-bound on the true MaxSim (§3.1) using the embeddings identified via the inverted list, which resembles the approximation explored for scoring by Macdonald and Tonellotto (2021) but is applied for candidate generation. These lower bounds are summed across the query tokens, and the top-scoring ncandidate candidate passages based on these approximate scores are selected for ranking, which loads the complete set of embeddings of each passage, and conducts the same scoring function using all embeddings per document following Equation 1. The result passages are then sorted by score and returned. 4 LoTTE: Long-Tail, Cross-Domain Retrieval Evaluation We introduce LoTTE (pronounced latte), a new dataset for Long-Tail Topic-stratified Evaluation for IR. To complement the out-of-domain tests of BEIR (Thakur et al., 2021), as motivated in §2.4, LoTTE focuses on natural user queries that pertain to long-tail topics, ones that might not be covered by an entity-centric knowledge base like Wikipedia. LoTTE consists of 12 test sets, each with 500–2000 queries and 100k–2M passages. The test sets are explicitly divided by topic, and each test set is accompanied by a validation set of related but disjoint queries and passages. We elect to make the passage texts disjoint to encourage more realistic out-of-domain transfer tests, allowing for minimal development on related but distinct topics. The test (and dev) sets include a “pooled” setting. In the pooled setting, the passages and queries are aggregated across all test (or dev) topics to evaluate out-of-domain retrieval across a larger and more diverse corpus. Table 1 outlines the composition of LoTTE. We derive the topics and passage corpora from the answer posts across various StackExchange fo- Topic Question Set Dev Test # Questions # Passages Subtopics # Questions # Passages Subtopics Writing Search 497 277k ESL, Linguistics, Worldbuilding 1071 200k English Forum 2003 2000 Recreation Search 563 263k Sci-Fi, RPGs, Photography 924 167k Gaming, Forum 2002 2002 Anime, Movies Science Search 538 344k Chemistry, Statistics, Academia 617 1.694M Math, Forum 2013 2017 Physics, Biology Technology Search 916 1.276M Web Apps, Ubuntu, SysAdmin 596 639k Apple, Android, Forum 2003 2004 UNIX, Security Lifestyle Search 417 269k DIY, Music, Bicycles, Car Maintenance 661 119k Cooking, Forum 2076 2002 Sports, Travel Pooled Search 2931 2.4M All of the above 3869 2.8M All of the above Forum 10097 10025 Table 1: Composition of LoTTE showing topics, question sets, and a sample of corresponding subtopics. Search Queries are taken from GooAQ, while Forum Queries are taken directly from the StackExchange archive. The pooled datasets combine the questions and passages from each of the subtopics. rums. StackExchange is a set of question-andanswer communities that target individual topics (e.g., “physics” or “bicycling”). We gather forums from five overarching domains: writing, recreation, science, technology, and lifestyle. To evaluate retrievers, we collect Search and Forum queries, each of which is associated with one or more target answer posts in its corpus. Example queries, and short snippets from posts that answer them in the corpora, are shown in Table 2. Search Queries. We collect search queries from GooAQ (Khashabi et al., 2021), a recent dataset of Google search-autocomplete queries and their answer boxes, which we filter for queries whose answers link to a specific StackExchange post. As Khashabi et al. (2021) hypothesize, Google Search likely maps these natural queries to their answers by relying on a wide variety of signals for relevance, including expert annotations, user clicks, and hyperlinks as well as specialized QA components for various question types with access to the post title and question body. Using those annotations as ground truth, we evaluate the models on their capacity for retrieval using only free text of the answer posts (i.e., no hyperlinks or user clicks, question title or body, etc.), posing a significant challenge for IR and NLP systems trained only on public datasets. Forum Queries. We collect the forum queries by extracting post titles from the StackExchange communities to use as queries and collect their corresponding answer posts as targets. We select questions in order of their popularity and sample questions according to the proportional contribution of individual communities within each topic. Q: what is the difference between root and stem in linguistics? A: A root is the form to which derivational affixes are added to form a stem. A stem is the form to which inflectional affixes are added to form a word. Q: are there any airbenders left? A: the Fire Nation had wiped out all Airbenders while Aang was frozen. Tenzin and his 3 children are the only Airbenders left in Korra’s time. Q: Why are there two Hydrogen atoms on some periodic tables? A: some periodic tables show hydrogen in both places to emphasize that hydrogen isn’t really a member of the first group or the seventh group. Q: How can cache be that fast? A: the cache memory sits right next to the CPU on the same die (chip), it is made using SRAM which is much, much faster than the DRAM. Table 2: Examples of queries and shortened snippets of answer passages from LoTTE. The first two examples show “search” queries, whereas the last two are “forum” queries. Snippets are shortened for presentation. These queries tend to have a wider variety than the “search” queries, while the search queries may exhibit more natural patterns. Table 3 compares a random samples of search and forum queries. It can be seen that search queries tend to be brief, knowledge-based questions with direct answers, whereas forum queries tend to reflect more openended questions. Both query sets target topics that exceed the scope of a general-purpose knowledge repository such as Wikipedia. For search as well as forum queries, the resulting evaluation set consists of a query and a target set of StackExchange answer posts (in particular, the answer posts from the target StackExchange page). Similar to evaluation in the Open-QA literature (Karpukhin et al., 2020; Khattab et al., Q: what is xerror in rpart? Q: is sub question one word? Q: how to open a garage door without making noise? Q: is docx and dotx the same? Q: are upvotes and downvotes anonymous? Q: what is the difference between descriptive essay and narrative essay? Q: how to change default user profile in chrome? Q: does autohotkey need to be installed? Q: how do you tag someone on facebook with a youtube video? Q: has mjolnir ever been broken? Q: Snoopy can balance on an edge atop his doghouse. Is any reason given for this? Q: How many Ents were at the Entmoot? Q: What does a hexagonal sun tell us about the camera lens/sensor? Q: Should I simply ignore it if authors assume that Im male in their response to my review of their article? Q: Why is the 2s orbital lower in energy than the 2p orbital when the electrons in 2s are usually farther from the nucleus? Q: Are there reasons to use colour filters with digital cameras? Q: How does the current know how much to flow, before having seen the resistor? Q: What is the difference between Fact and Truth? Q: hAs a DM, how can I handle my Druid spying on everything with Wild shape as a spider? Q: What does 1x1 convolution mean in a neural network? Table 3: Comparison of a random sample of search queries (top) vs. forum queries (bottom). 2021b), we evaluate retrieval quality by computing the success@5 (S@5) metric. Specifically, we award a point to the system for each query where it finds an accepted or upvoted (score ≥ 1) answer from the target page in the top-5 hits. Appendix D reports on the breakdown of constituent communities per topic, the construction procedure of LoTTE as well as licensing considerations, and relevant statistics. Figures 5 and 6 quantitatively compare the search and forum queries. 5 Evaluation We now evaluate ColBERTv2 on passage retrieval tasks, testing its quality within the training domain (§5.1) as well as outside the training domain in zero-shot settings (§5.2). Unless otherwise stated, we compress ColBERTv2 embeddings to b = 2 bits per dimension in our evaluation. 5.1 In-Domain Retrieval Quality Similar to related work, we train for IR tasks on MS MARCO Passage Ranking (Nguyen et al., 2016). Within the training domain, our development-set results are shown in Table 4, comparing ColBERTv2 with vanilla ColBERT as well as state-of-the-art single-vector systems. While ColBERT outperforms single-vector systems like RepBERT, ANCE, and even TAS-B, improvements in supervision such as distillation from cross-encoders enable systems like SPLADEv2, Method Official Dev (7k) Local Eval (5k) MRR@10 R@50 R@1k MRR@10 R@50 R@1k Models without Distillation or Special Pretraining RepBERT 30.4 - 94.3 - - - DPR 31.1 - 95.2 - - - ANCE 33.0 - 95.9 - - - LTRe 34.1 - 96.2 - - - ColBERT 36.0 82.9 96.8 36.7 - - Models with Distillation or Special Pretraining TAS-B 34.7 - 97.8 - - - SPLADEv2 36.8 - 97.9 37.9 84.9 98.0 PAIR 37.9 86.4 98.2 - - - coCondenser 38.2 - 98.4 - - - RocketQAv2 38.8 86.2 98.1 39.8 85.8 97.9 ColBERTv2 39.7 86.8 98.4 40.8 86.3 98.3 Table 4: In-domain performance on the development set of MS MARCO Passage Ranking as well the “Local Eval” test set described by Khattab and Zaharia (2020). Dev-set results for baseline systems are from their respective papers: Zhan et al. (2020b), Xiong et al. (2020) for DPR and ANCE, Zhan et al. (2020a), Khattab and Zaharia (2020), Hofstätter et al. (2021), Gao and Callan (2021), Ren et al. (2021a), Formal et al. (2021a), and Ren et al. (2021b). PAIR, and RocketQAv2 to achieve higher quality than vanilla ColBERT. These supervision gains challenge the value of fine-grained late interaction, and it is not inherently clear whether the stronger inductive biases of ColBERT-like models permit it to accept similar gains under distillation, especially when using compressed representations. Despite this, we find that with denoised supervision and residual compression, ColBERTv2 achieves the highest quality across all systems. As we discuss in §5.3, it exhibits space footprint competitive with these single-vector models and much lower than vanilla ColBERT. Besides the official dev set, we evaluated ColBERTv2, SPLADEv2, and RocketQAv2 on the “Local Eval” test set described by Khattab and Zaharia (2020) for MS MARCO, which consists of 5000 queries disjoint with the training and the official dev sets. These queries are obtained from labeled 50k queries that are provided in the official MS MARCO Passage Ranking task as additional validation data.4 On this test set, ColBERTv2 obtains 40.8% MRR@10, considerably outperforming the baselines, including RocketQAv2 which makes use of document titles in addition to the passage text unlike the other systems. 4These are sampled from delta between qrels.dev.tsv and qrels.dev.small.tsv on https://microsoft. github.io/msmarco/Datasets. We refer to Khattab and Zaharia (2020) for details. All our query IDs will be made public to aid reproducibility. Corpus Models without Distillation Models with Distillation ColBERT DPR-M ANCE MoDIR TAS-B RocketQAv2 SPLADEv2 ColBERTv2 BEIR Search Tasks (nDCG@10) DBPedia 39.2 23.6 28.1 28.4 38.4 35.6 43.5 44.6 FiQA 31.7 27.5 29.5 29.6 30.0 30.2 33.6 35.6 NQ 52.4 39.8 44.6 44.2 46.3 50.5 52.1 56.2 HotpotQA 59.3 37.1 45.6 46.2 58.4 53.3 68.4 66.7 NFCorpus 30.5 20.8 23.7 24.4 31.9 29.3 33.4 33.8 T-COVID 67.7 56.1 65.4 67.6 48.1 67.5 71.0 73.8 Touché (v2) - - - - - 24.7 27.2 26.3 BEIR Semantic Relatedness Tasks (nDCG@10) ArguAna 23.3 41.4 41.5 41.8 42.7 45.1 47.9 46.3 C-FEVER 18.4 17.6 19.8 20.6 22.8 18.0 23.5 17.6 FEVER 77.1 58.9 66.9 68.0 70.0 67.6 78.6 78.5 Quora 85.4 84.2 85.2 85.6 83.5 74.9 83.8 85.2 SCIDOCS 14.5 10.8 12.2 12.4 14.9 13.1 15.8 15.4 SciFact 67.1 47.8 50.7 50.2 64.3 56.8 69.3 69.3 (a) Corpus ColBERT BM25 ANCE RocketQAv2 SPLADEv2 ColBERTv2 OOD Wikipedia Open QA (Success@5) NQ-dev 65.7 44.6 - - 65.6 68.9 TQ-dev 72.6 67.6 - - 74.7 76.7 SQuAD-dev 60.0 50.6 - - 60.4 65.0 LoTTE Search Test Queries (Success@5) Writing 74.7 60.3 74.4 78.0 77.1 80.1 Recreation 68.5 56.5 64.7 72.1 69.0 72.3 Science 53.6 32.7 53.6 55.3 55.4 56.7 Technology 61.9 41.8 59.6 63.4 62.4 66.1 Lifestyle 80.2 63.8 82.3 82.1 82.3 84.7 Pooled 67.3 48.3 66.4 69.8 68.9 71.6 LoTTE Forum Test Queries (Success@5) Writing 71.0 64.0 68.8 71.5 73.0 76.3 Recreation 65.6 55.4 63.8 65.7 67.1 70.8 Science 41.8 37.1 36.5 38.0 43.7 46.1 Technology 48.5 39.4 46.8 47.3 50.8 53.6 Lifestyle 73.0 60.6 73.1 73.7 74.0 76.9 Pooled 58.2 47.2 55.7 57.7 60.1 63.4 (b) Table 5: Zero-shot evaluation results. Sub-table (a) reports results on BEIR and sub-table (b) reports results on the Wikipedia Open QA and the test sets of the LoTTE benchmark. On BEIR, we test ColBERTv2 and RocketQAv2 and copy the results for ANCE, TAS-B, and ColBERT from Thakur et al. (2021), for MoDIR and DPRMSMARCO (DPR-M) from Xin et al. (2021), and for SPLADEv2 from Formal et al. (2021a). 5.2 Out-of-Domain Retrieval Quality Next, we evaluate ColBERTv2 outside the training domain using BEIR (Thakur et al., 2021), Wikipedia Open QA retrieval as in Khattab et al. (2021b), and LoTTE. We compare against a wide range of recent and state-of-the-art retrieval systems from the literature. BEIR. We start with BEIR, reporting the quality of models that do not incorporate distillation from cross-encoders, namely, ColBERT (Khattab and Zaharia, 2020), DPR-MARCO (Xin et al., 2021), ANCE (Xiong et al., 2020), and MoDIR (Xin et al., 2021), as well as models that do utilize distillation, namely, TAS-B (Hofstätter et al., 2021), SPLADEv2 (Formal et al., 2021a), and also RocketQAv2, which we test ourselves using the official checkpoint trained on MS MARCO. We divide the table into “search” (i.e., natural queries and questions) and “semantic relatednes” (e.g., citationrelatedness and claim verification) tasks to reflect the nature of queries in each dataset.5 Table 5a reports results with the official nDCG@10 metric. Among the models with5 Following Formal et al. (2021a), we conduct our evaluationg using the publicly-available datasets in BEIR. Refer to §E for details. out distillation, we see that the vanilla ColBERT model outperforms the single-vector systems DPR, ANCE, and MoDIR across all but three tasks. ColBERT often outpaces all three systems by large margins and, in fact, outperforms the TAS-B model, which utilizes distillation, on most datasets. Shifting our attention to models with distillation, we see a similar pattern: while distillation-based models are generally stronger than their vanilla counterparts, the models that decompose scoring into termlevel interactions, ColBERTv2 and SPLADEv2, are almost always the strongest. Looking more closely into the comparison between SPLADEv2 and ColBERTv2, we see that ColBERTv2 has an advantage on six benchmarks and ties SPLADEv2 on two, with the largest improvements attained on NQ, TREC-COVID, and FiQA-2018, all of which feature natural search queries. On the other hand, SPLADEv2 has the lead on five benchmarks, displaying the largest gains on Climate-FEVER (C-FEVER) and HotPotQA. In C-FEVER, the input queries are sentences making climate-related claims and, as a result, do not reflect the typical characteristics of search queries. In HotPotQA, queries are written by crowdworkers who have access to the target pas- sages. This is known to lead to artificial lexical bias (Lee et al., 2019), where crowdworkers copy terms from the passages into their questions as in the Open-SQuAD benchmark. Wikipedia Open QA. As a further test of outof-domain generalization, we evaluate the MS MARCO-trained ColBERTv2, SPLADEv2, and vanilla ColBERT on retrieval for open-domain question answering, similar to the out-of-domain setting of Khattab et al. (2021b). We report Success@5 (sometimes referred to as Recall@5), which is the percentage of questions whose short answer string overlaps with one or more of the top-5 passages. For the queries, we use the development set questions of the open-domain versions (Lee et al., 2019; Karpukhin et al., 2020) of Natural Questions (NQ; Kwiatkowski et al. 2019), TriviaQA (TQ; Joshi et al. 2017), and SQuAD (Rajpurkar et al., 2016) datasets in Table 5b. As a baseline, we include the BM25 (Robertson et al., 1995) results using the Anserini (Yang et al., 2018a) toolkit. We observe that ColBERTv2 outperforms BM25, vanilla ColBERT, and SPLADEv2 across the three query sets, with improvements of up to 4.6 points over SPLADEv2. LoTTE. Next, we analyze performance on the LoTTE test benchmark, which focuses on natural queries over long-tail topics and exhibits a different annotation pattern to the datasets in the previous OOD evaluations. In particular, LoTTE uses automatic Google rankings (for the “search” queries) and organic StackExchange question–answer pairs (for “forum” queries), complimenting the poolingbased annotation of datasets like TREC-COVID (in BEIR) and the answer overlap metrics of Open-QA retrieval. We report Success@5 for each corpus on both search queries and forum queries. Overall, we see that ANCE and vanilla ColBERT outperform BM25 on all topics, and that the three methods using distillation are generally the strongest. Similar to the Wikipedia-OpenQA results, we find that ColBERTv2 outperforms the baselines across all topics for both query types, improving upon SPLADEv2 and RocketQAv2 by up to 3.7 and 8.1 points, respectively. Considering the baselines, we observe that while RocketQAv2 tends to have a slight advantage over SPLADEv2 on the “search” queries, SPLADEv2 is considerably more effective on the “forum” tests. We hypothesize that the search queries, obtained from Google (through GooAQ) are more similar to MS MARCO than the forum queries and, as a result, the latter stresses generalization more heavily, rewarding term-decomposed models like SPLADEv2 and ColBERTv2. 5.3 Efficiency ColBERTv2’s residual compression approach significantly reduces index sizes compared to vanilla ColBERT. Whereas ColBERT requires 154 GiB to store the index for MS MARCO, ColBERTv2 only requires 16 GiB or 25 GiB when compressing embeddings to 1 or 2 bit(s) per dimension, respectively, resulting in compression ratios of 6–10×. This storage figure includes 4.5 GiB for storing the inverted list. This matches the storage for a typical singlevector model on MS MARCO, with 4-byte lossless floating-point storage for one 768-dimensional vector for each of the 9M passages amounting to a little over 25 GiBs. In practice, the storage for a singlevector model could be even larger when using a nearest-neighbor index like HNSW for fast search. Conversely, single-vector representations could be themselves compressed very aggressively (Zhan et al., 2021a, 2022), though often exacerbating the loss in quality relative to late interaction methods like ColBERTv2. We discuss the impact of our compression method on search quality in Appendix B and present query latency results on the order of 50– 250 milliseconds per query in Appendix C. 6 Conclusion We introduced ColBERTv2, a retriever that advances the quality and space efficiency of multivector representations. We hypothesized that cluster centroids capture context-aware semantics of the token-level representations and proposed a residual representation that leverages these patterns to dramatically reduce the footprint of multi-vector systems off-the-shelf. We then explored improved supervision for multi-vector retrieval and found that their quality improves considerably upon distillation from a cross-encoder system. The proposed ColBERTv2 considerably outperforms existing retrievers in within-domain and out-of-domain evaluations, which we conducted extensively across 28 datasets, establishing state-of-the-art quality while exhibiting competitive space footprint. Acknowledgements This research was supported in part by affiliate members and other supporters of the Stanford DAWN project—Ant Financial, Facebook, Google, and VMware—as well as Cisco, SAP, Virtusa, and the NSF under CAREER grant CNS-1651570. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. Broader Impact & Ethical Considerations This work is primarily an effort toward retrieval models that generalize better while performing reasonably efficiently in terms of space consumption. Strong out-of-the-box generalization to small domain-specific applications can serve many users in practice, particularly where training data is not available. Moreover, retrieval holds significant promise for many downstream NLP tasks, as it can help make language models smaller and thus more efficient (i.e., by decoupling knowledge from computation), more transparent (i.e., by allowing users to check the sources the model relied on when making a claim or prediction), and easier to update (i.e., by allowing developers to replace or add documents to the corpus without retraining the model) (Guu et al., 2020; Borgeaud et al., 2021; Khattab et al., 2021a). Nonetheless, such work poses risks in terms of misuse, particularly toward misinformation, as retrieval can surface results that are relevant yet inaccurate, depending on the contents of a corpus. Moreover, generalization from training on a large-scale dataset can propagate the biases of that dataset well beyond its typical reach to new domains and applications. While our contributions have made ColBERT’s late interaction more efficient at storage costs, largescale distillation with hard negatives increases system complexity and accordingly increases training cost, when compared with the straightforward training paradigm of the original ColBERT model. While ColBERTv2 is efficient in terms of latency and storage at inference time, we suspect that under extreme resource constraints, simpler model designs like SPLADEv2 or RocketQAv2 could lend themselves to easier-to-optimize environments. We leave low-level systems optimizations of all systems to future work. Another worthwhile dimension for future exploration of tradeoffs is reranking architectures over various systems with cross-encoders, which are known to be expensive yet precise due to their highly expressive capacity. Research Limitations While we evaluate ColBERTv2 on a wide range of tests, all of our benchmarks are in English and, in line with related work, our out-of-domain tests evaluate models that are trained on MS MARCO. We expect our approach to work effectively for other languages and when all models are trained using other, smaller training set (e.g., NaturalQuestions), but we leave such tests to future work. We have observed consistent gains for ColBERTv2 against existing state-of-the-art systems across many diverse settings. Despite this, almost all IR datasets contain false negatives (i.e., relevant but unlabeled passages) and thus some caution is needed in interpreting any individual result. Nonetheless, we intentionally sought out benchmarks with dissimilar annotation biases: for instance, TREC-COVID (in BEIR) annotates the pool of documents retrieved by the systems submitted at the time of the competition, LoTTE uses automatic Google rankings (for “search” queries) and StackExchange question–answer pairs (for “forum” queries), and the Open-QA tests rely on passageanswer overlap for factoid questions. ColBERTv2 performed well in all of these settings. We discuss other issues pertinent to LoTTE in Appendix §D. We have compared with a wide range of strong baselines—including sparse retrieval and singlevector models—and found reliable patterns across tests. However, we caution that empirical trends can change as innovations are introduced to each of these families of models and that it can be difficult to ensure exact apple-to-apple comparisons across families of models, since each of them calls for different sophisticated tuning strategies. We thus primarily used results and models from the rich recent literature on these problems, with models like RocketQAv2 and SPLADEv2. On the representational side, we focus on reducing the storage cost using residual compression, achieving strong gains in reducing footprint while largely preserving quality. Nonetheless, we have not exhausted the space of more sophisticated optimizations possible, and we would expect more sophisticated forms of residual compression and composing our approach with dropping tokens (Zhou and Devlin, 2021) to open up possibilities for further reductions in space footprint.""

question:Ok, great. Well done. Now, summarise the following paper. Again, provide a deep understanding: ""RAPTOR: Recursive Abstractive Processing for Tree-Organized Retrieval Parth Sarthi, Salman Abdullah, Aditi Tuli, Shubh Khanna, Anna Goldie, Christopher D. Manning Stanford University <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS> Abstract Retrieval-augmented language models can better adapt to changes in world state and incorporate long-tail knowledge. However, most existing methods retrieve only short contiguous chunks from a retrieval corpus, limiting holistic understanding of the overall document context. We introduce the novel approach of recursively embedding, clustering, and summarizing chunks of text, constructing a tree with differing levels of summarization from the bottom up. At inference time, our RAPTOR model retrieves from this tree, integrating information across lengthy documents at different levels of abstraction. Controlled experiments show that retrieval with recursive summaries offers significant improvements over traditional retrieval-augmented LMs on several tasks. On question-answering tasks that involve complex, multi-step reasoning, we show state-of-the-art results; for example, by coupling RAPTOR retrieval with the use of GPT-4, we can improve the best performance on the QuALITY benchmark by 20% in absolute accuracy. 1Introduction Large Language Models (LLMs) have emerged as transformative tools showing impressive performance on many tasks. With the growing size of LLMs, they can serve standalone as very effective knowledge stores, with facts encoded within their parameters (Petroni et al., 2019; Jiang et al., 2020; Talmor et al., 2020; Rae et al., 2021; Hoffmann et al., 2022; Chowdhery et al., 2022; Bubeck et al., 2023; Kandpal et al., 2023) and models can be further improved with fine-tuning on downstream tasks (Roberts et al., 2020). Nevertheless, even a large model does not contain sufficient domain-specific knowledge for particular tasks and the world continues to change, invalidating facts in the LLM. Updating the knowledge of these models through additional fine-tuning or editing is difficult, particularly when dealing with vast text corpora (Lewis et al., 2020; Mitchell et al., 2022). An alternative approach, pioneered in open domain question answering systems (Chen et al., 2017; Yu et al., 2018), is to index large quantities of text, after splitting it into chunks (paragraphs), in a separate information retrieval system. Retrieved information is then presented to the LLM along with the question as context (“retrieval augmentation”, Lewis et al., 2020; Izacard et al., 2022; Min et al., 2023; Ram et al., 2023), making it easy to provide a system with current knowledge particular to some domain and enabling easy interpretability and provenance tracking, whereas the parametric knowledge of LLMs is opaque and difficult to trace back to its source (Akyurek et al., 2022). Refer to caption Figure 1:Tree construction process: RAPTOR recursively clusters chunks of text based on their vector embeddings and generates text summaries of those clusters, constructing a tree from the bottom up. Nodes clustered together are siblings; a parent node contains the text summary of that cluster. Nevertheless, existing retrieval-augmented approaches also have flaws. The one we tackle is that most existing methods retrieve only a few short, contiguous text chunks, which limits their ability to represent and leverage large-scale discourse structure. This is particularly relevant for thematic questions that require integrating knowledge from multiple parts of a text, such as understanding an entire book, as in the NarrativeQA dataset (Kočiskỳ et al., 2018). Consider the fairy tale of Cinderella, and the question “How did Cinderella reach her happy ending?”. The top- � retrieved short contiguous texts will not contain enough context to answer the question. To address this, we design an indexing and retrieval system that uses a tree structure to capture both high-level and low-level details about a text. As shown in Figure 1, our system, RAPTOR, clusters chunks of text, generates text summaries of those clusters, and then repeats, generating a tree from the bottom up. This structure enables RAPTOR to load into an LLM’s context chunks representing the text at different levels so that it can effectively and efficiently answer questions at different levels. Our main contribution is the idea of using text summarization to allow retrieval augmentation of context at different scales, and to show its effectiveness in experiments on collections of long documents. Controlled experiments with three language models (UnifiedQA (Khashabi et al., 2020), GPT-3 (Brown et al., 2020) and GPT-4 (OpenAI, 2023)) show that RAPTOR outperforms current retrieval augmentation. Moreover, RAPTOR coupled with GPT-4, and sometimes even with UnifiedQA, gives new state-of-the-art results on three QA tasks: free text response questions on books and movies (NarrativeQA, Kočiskỳ et al. 2018), full-text NLP papers (QASPER, Dasigi et al. 2021), and multiple-choice questions based on medium-length passages (QuALITY, Pang et al. 2022).1 2Related Work Why Retrieval? Recent advances in hardware and algorithms have indeed expanded the context lengths that models can handle, leading to questions about the need for retrieval systems (Dai et al., 2019; Dao et al., 2022; Liu et al., 2023). However, as Liu et al. (2023) and Sun et al. (2021) have noted, models tend to underutilize long-range context and see diminishing performance as context length increases, especially when pertinent information is embedded within a lengthy context. Moreover, practically, use of long contexts is expensive and slow. This suggests that selecting the most relevant information for knowledge-intensive tasks is still crucial. Retrieval Methods Retrieval-augmented language models (RALMs) have seen improvements in various components: the retriever, the reader, and end-to-end system training. Retrieval methods have transitioned from traditional term-based techniques like TF-IDF (Spärck Jones, 1972) and BM25 (Robertson et al., 1995; Roberts et al., 2020) to deep learning–based strategies (Karpukhin et al., 2020; Khattab & Zaharia, 2020; Sachan et al., 2023). Some recent work proposes using large language models as retrievers due to their ability to memorize extensive knowledge (Yu et al., 2022; Sun et al., 2022). Research on the reader component includes Fusion-in-Decoder (FiD) (Izacard & Grave, 2022), which employs both DPR and BM25 for retrieval and processes passages independently in the encoder and RETRO (Borgeaud et al., 2022; Wang et al., 2023), which utilizes cross-chunked attention and chunkwise retrieval to generate text grounded on retrieved context. End-to-end system training work includes Atlas (Izacard et al., 2022), which fine-tunes an encoder-decoder model in conjunction with the retriever; REALM (Guu et al., 2020), a bidirectional, masked LM fine-tuned for open-domain question answering; and RAG (Retrieval-Augmented Generation) (Lewis et al., 2020), which integrates pre-trained sequence-to-sequence models with a neural retriever. Min et al. (2021) introduced Joint Passage Retrieval (JPR) model which uses a tree-decoding algorithm to handle passage diversity and relevance in multi-answer retrieval. Dense Hierarchical Retrieval (DHR) and Hybrid Hierarchical Retrieval (HHR) represent advancements in retrieval accuracy by combining document and passage level retrievals and integrating sparse and dense retrieval methods, respectively (Liu et al., 2021; Arivazhagan et al., 2023). Despite a diversity in methods, the retrieving components of models predominantly rely on standard approaches, i.e., chunking corpora and encoding with BERT-based retrievers. Although this approach is widely adopted, Nair et al. (2023) highlights a potential shortcoming: contiguous segmentation might not capture the complete semantic depth of the text. Reading extracted snippets from technical or scientific documents may lack important context making them difficult to read or even misleading. (Cohan & Goharian, 2017; Newman et al., 2023; Zhang et al., 2023). Recursive summarization as Context Summarization techniques provide a condensed view of documents, enabling more focused engagement with the content (Angelidis & Lapata, 2018). The summarization/snippet model by Gao et al. (2023) uses summarizations and snippets of passages, which improves correctness on most datasets but can sometimes be a lossy means of compression. The recursive-abstractive summarization model by Wu et al. (2021) employs task decomposition to summarize smaller text chunks, which are later integrated to form summaries of larger sections. While this method is effective for capturing broader themes, it can miss granular details. LlamaIndex (Liu, 2022) mitigates this issue by similarly summarizing adjacent text chunks but also retaining intermediate nodes thus storing varying levels of detail, keeping granular details. However, both methods, due to their reliance on adjacency for grouping or summarizing adjacent nodes, may still overlook distant interdependencies within the text, which we can find and group with RAPTOR. 3Methods Overview of RAPTOR Building on the idea that long texts often present subtopics and hierarchical structures (Cao & Wang, 2022; Dong et al., 2023b), RAPTOR addresses the issue of semantic depth and connection in reading by building a recursive tree structure that balances broader thematic comprehension with granular details and which allows nodes to be grouped based on semantic similarity not just order in the text. Construction of the RAPTOR tree begins with segmenting the retrieval corpus into short, contiguous texts of length 100, similar to traditional retrieval augmentation techniques. If a sentence exceeds the 100-token limit, we move the entire sentence to the next chunk, rather than cutting it mid-sentence. This preserves the contextual and semantic coherence of the text within each chunk. These texts are then embedded using SBERT, a BERT-based encoder (multi-qa-mpnet-base-cos-v1) (Reimers & Gurevych, 2019). The chunks and their corresponding SBERT embeddings form the leaf nodes of our tree structure. To group similar text chunks, we employ a clustering algorithm. Once clustered, a Language Model is used to summarize the grouped texts. These summarized texts are then re-embedded, and the cycle of embedding, clustering, and summarization continues until further clustering becomes infeasible, resulting in a structured, multi-layered tree representation of the original documents. An important aspect of RAPTOR is its computational efficiency. The system scales linearly in terms of both build time and token expenditure, making it suitable for processing large and complex corpora. For a comprehensive discussion on RAPTOR’s scalability, please refer to the Appendix A. For querying within this tree, we introduce two distinct strategies: tree traversal and collapsed tree. The tree traversal method traverses the tree layer-by-layer, pruning and selecting the most relevant nodes at each level. The collapsed tree method evaluates nodes collectively across all layers to find the most relevant ones. Clustering Algorithm Clustering plays a key role in building the RAPTOR tree, organizing text segments into cohesive groups. This step groups related content together, which helps the subsequent retrieval process. One of the unique aspects of our clustering approach is the use of soft clustering, where nodes can belong to multiple clusters without requiring a fixed number of clusters. This flexibility is essential because individual text segments often contain information relevant to various topics, thereby warranting their inclusion in multiple summaries. Our clustering algorithm is based on Gaussian Mixture Models (GMMs), an approach that offers both flexibility and a probabilistic framework. GMMs assume that data points are generated from a mixture of several Gaussian distributions. Given a set of � text segments, each represented as a � -dimensional dense vector embedding, the likelihood of a text vector, 𝐱 , given its membership in the � � ⁢ ℎ Gaussian distribution, is denoted by � ⁢ ( 𝐱 | � ) = 𝒩 ⁢ ( 𝐱 ; � � , 𝚺 � ) . The overall probability distribution is a weighted combination � ⁢ ( 𝐱 ) = ∑ � = 1 � � � ⁢ 𝒩 ⁢ ( 𝐱 ; � � , 𝚺 � ) , where � � signifies the mixture weight for the � th Gaussian distribution. The high dimensionality of vector embeddings presents a challenge for traditional GMMs, as distance metrics may behave poorly when used to measure similarity in high-dimensional spaces (Aggarwal et al., 2001). To mitigate this, we employ Uniform Manifold Approximation and Projection (UMAP), a manifold learning technique for dimensionality reduction (McInnes et al., 2018). The number of nearest neighbors parameter, � ⁢ _ ⁢ � ⁢ � ⁢ � ⁢ � ⁢ ℎ ⁢ � ⁢ � ⁢ � ⁢ � , in UMAP determines the balance between the preservation of local and global structures. Our algorithm varies � ⁢ _ ⁢ � ⁢ � ⁢ � ⁢ � ⁢ ℎ ⁢ � ⁢ � ⁢ � ⁢ � to create a hierarchical clustering structure: it first identifies global clusters and then performs local clustering within these global clusters. This two-step clustering process captures a broad spectrum of relationships among the text data, from broad themes to specific details. Should a local cluster’s combined context ever exceed the summarization model’s token threshold, our algorithm recursively applies clustering within the cluster, ensuring that the context remains within the token threshold. To determine the optimal number of clusters, we employ the Bayesian Information Criterion (BIC) for model selection. BIC not only penalizes model complexity but also rewards goodness of fit (Schwarz, 1978). The BIC for a given GMM is � ⁢ � ⁢ � = ln ⁡ ( � ) ⁢ � − 2 ⁢ ln ⁡ ( � ^ ) , where � is the number of text segments (or data points), � is the number of model parameters, and � ^ is the maximized value of the likelihood function of the model. In the context of GMM, the number of parameters � is a function of the dimensionality of the input vectors and the number of clusters. With the optimal number of clusters determined by BIC, the Expectation-Maximization algorithm is then used to estimate the GMM parameters, namely the means, covariances, and mixture weights. While the Gaussian assumption in GMMs may not perfectly align with the nature of text data, which often exhibits a sparse and skewed distribution, our empirical observations suggest that it offers an effective model for our purpose. We run an ablation comparing GMM Clustering with summarizing contiguous chunks and provide details in Appendix B. Model-Based Summarization After clustering the nodes using Gaussian Mixture Models, the nodes in each cluster are sent to a language model for summarization. This step allows the model to transform large chunks of text into concise, coherent summaries of the selected nodes. For our experiments, we use gpt-3.5-turbo to generate the summaries. The summarization step condenses the potentially large volume of retrieved information into a manageable size. We provide statistics on the compression due to the summarization in Appendix C and the prompt used for summarization in Appendix D. While the summarization model generally produces reliable summaries, a focused annotation study revealed that about 4% of the summaries contained minor hallucinations. These did not propagate to parent nodes and had no discernible impact on question-answering tasks. For an in-depth analysis of hallucinations, refer to the appendix E. Refer to caption Figure 2:Illustration of the tree traversal and collapsed tree retrieval mechanisms. Tree traversal starts at the root level of the tree and retrieves the top- � (here, top- 1 ) node(s) based on cosine similarity to the query vector. At each level, it retrieves the top- � node(s) from the child nodes of the previous layer’s top- � . Collapsed tree collapses the tree into a single layer and retrieves nodes until a threshold number of tokens is reached, based on cosine similarity to the query vector. The nodes on which cosine similarity search is performed are highlighted in both illustrations. Querying In this section, we elaborate on the two querying mechanisms employed by RAPTOR: tree traversal and collapsed tree. These methods offer unique ways of traversing the multi-layered RAPTOR tree to retrieve relevant information, each with its own advantages and trade-offs. We provide the pseudocode of both methods in Appendix F. Note that we embed all nodes using SBERT. The tree traversal method first selects the top-k most relevant root nodes based on their cosine similarity to the query embedding. The children of these selected nodes are considered at the next layer and the top-k nodes are selected from this pool again based on their cosine similarity to the query vector. This process is repeated until we reach the leaf nodes. Finally, the text from all selected nodes is concatenated to form the retrieved context. The algorithm’s steps are outlined below: 1. Start at the root layer of the RAPTOR tree. Compute the cosine similarity between the query embedding and the embeddings of all nodes present at this initial layer. 2. Choose the top- � nodes based on the highest cosine similarity scores, forming the set � 1 . 3. Proceed to the child nodes of the elements in set � 1 . Compute the cosine similarity between the query vector and the vector embeddings of these child nodes. 4. Select the top � child nodes with the highest cosine similarity scores to the query, forming the set � 2 . 5. Continue this process recursively for � layers, producing sets � 1 , � 2 , … , � � . 6. Concatenate sets � 1 through � � to assemble the relevant context to the query. By adjusting the depth � and the number of nodes � selected at each layer, the tree traversal method offers control over the specificity and breadth of the information retrieved. The algorithm starts with a broad outlook by considering the top layers of the tree and progressively focuses on finer details as it descends through the lower layers. The collapsed tree approach offers a simpler way to search for relevant information by considering all nodes in the tree simultaneously, as depicted in Figure 2. Instead of going layer-by-layer, this method flattens the multi-layered tree into a single layer, essentially bringing all the nodes onto the same level for comparison. The steps for this method are outlined below: 1. First, collapse the entire RAPTOR tree into a single layer. This new set of nodes, denoted as � , contains nodes from every layer of the original tree. 2. Next, calculate the cosine similarity between the query embedding and the embeddings of all nodes present in the collapsed set � . 3. Finally, pick the top- � nodes that have the highest cosine similarity scores with the query. Keep adding nodes to the result set until you reach a predefined maximum number of tokens, ensuring you don’t exceed the model’s input limitations. We tested both approaches on 20 stories from the QASPER dataset. Figure 3 shows the performance of tree traversal with different top- sizes and collapsed tree with different maximum token numbers. The collapsed tree approach consistently performs better. We believe collapsed tree retrieval is better due to offering greater flexibility than tree traversal; i.e., by searching through all the nodes simultaneously, it retrieves information that is at the correct level of granularity for a given question. In comparison, while using tree traversal with the same values of � and � , the ratio of nodes from each level of the tree will be constant. So, the ratio of higher-order thematic information to granular details will remain the same regardless of the question. One drawback, however, of the collapsed tree approach is that it requires cosine similarity search to be performed on all nodes in the tree. However, this can be made more efficient with fast � -nearest neighbor libraries such as FAISS (Johnson et al., 2019). Refer to caption Figure 3:Comparison of querying methods. Results on 20 stories from the QASPER dataset using tree traversal with different top-k values, and collapsed tree with different context lengths. Collapsed tree with 2000 tokens produces the best results, so we use this querying strategy for our main results. Overall, given the collapsed tree approach’s greater flexibility and its superior performance on the subset of the QASPER dataset, this is the querying approach with which we proceed. Specifically, we use the collapsed tree with 2000 maximum tokens, which approximately equates to retrieving the top-20 nodes. Using a token-based approach ensures the context does not exceed model context constraints as token counts can vary across nodes. For experiments with the UnifiedQA model, we provide 400 tokens of context, as UnifiedQA has a max context length of 512 tokens. We provide the same amount of tokens of context to RAPTOR and to the baselines. Qualitative Study We conduct a qualitative analysis to understand the benefits of RAPTOR’s retrieval process compared to Dense Passage Retrieval (DPR) methods. Our study focuses on thematic, multi-hop questions using a 1500-word Cinderella fairytale. As illustrated in Figure 4, RAPTOR’s tree-based retrieval allows it to choose nodes from different tree layers, matching the question’s detail level. This approach often yields more relevant and comprehensive information for downstream tasks than DPR. For a detailed discussion and examples, including the text retrieved by both RAPTOR and DPR for specific questions, please refer to the appendix G. 4Experiments Datasets We measure RAPTOR’s performance across three question-answering datasets: NarrativeQA, QASPER, and QuALITY. NarrativeQA is a dataset that comprises question-answer pairs based on the full texts of books and movie transcripts, totaling 1,572 documents (Kočiskỳ et al., 2018; Wu et al., 2021). The NarrativeQA-Story task requires a comprehensive understanding of the entire narrative in order to accurately answer its questions, thus testing the model’s ability to comprehend longer texts in the literary domain. We measure performance on this dataset using the standard BLEU (B-1, B-4), ROUGE (R-L), and METEOR (M) metrics. Please see appendix H for more details on the NarrativeQA evaluation script used in our experiments. The QASPER dataset includes 5,049 questions across 1,585 NLP papers, with each question probing for information embedded within the full text (Dasigi et al., 2021). The answer types in QASPER are categorized as Answerable/Unanswerable, Yes/No, Abstractive, and Extractive. Accuracy is measured using standard F1. Lastly, the QuALITY dataset consists of multiple-choice questions, each accompanied by context passages averaging approximately 5,000 tokens in length (Pang et al., 2022). This dataset calls for reasoning over the entire document for QA tasks, enabling us to measure the performance of our retrieval system on medium-length documents. The dataset includes a challenging subset, QuALITY-HARD, which contains questions that a majority of human annotators answered incorrectly in a speed-setting. We report accuracies for both the entire test set and the HARD subset. Refer to caption Figure 4:Querying Process: Illustration of how RAPTOR retrieves information for two questions about the Cinderella story: “What is the central theme of the story?” and “How did Cinderella find a happy ending?”. Highlighted nodes indicate RAPTOR’s selections, while arrows point to DPR’s leaf nodes. Notably, RAPTOR’s context often encompasses the information retrieved by DPR, either directly or within higher-layer summaries. Controlled Baseline Comparisons We first present controlled comparisons using the UnifiedQA 3B as the reader, with SBERT (Reimers & Gurevych, 2019), BM25 (Robertson et al., 1995; 2009), and DPR (Karpukhin et al., 2020) as the embedding models with and without the RAPTOR tree structure, on three datasets: QASPER, NarrativeQA, and QuALITY. As shown in Tables 1 and 2, our results demonstrate that RAPTOR, when combined with any retriever, consistently outperforms the respective retriever across all datasets. 2 Since RAPTOR with SBERT has the best performance, we use it in all subsequent experiments. We now compare RAPTOR with BM25 and DPR, using three different LLMs: GPT-3, GPT-4, and UnifiedQA. As shown in Table 3, RAPTOR consistently outperforms BM25 and DPR across all three Language Models on the QASPER dataset. RAPTOR’s F-1 Match scores are 53.1%, 55.7%, and 36.6% when using GPT-3, GPT-4, and UnifiedQA, respectively. These scores surpass DPR by margins of 1.8, 2.7, and 4.5 points, and outdo BM25 by 6.5, 5.5, and 10.2 points across the respective LLMs. QASPER requires synthesizing information within NLP papers, so it is unsurprising that RAPTOR’s higher-level summary nodes would allow it to outperform methods that can only extract the top- � most similar raw chunks of text, which may not contain the correct response in isolation. Table 1:NarrativeQA Performance With + Without RAPTOR: Performance comparison of various retrieval methods (SBERT, BM25, DPR) with and without RAPTOR on the NarrativeQA dataset, using UnifiedQA-3B as the language model. RAPTOR outperforms baselines of each respective retrieval method. Model ROUGE BLEU-1 BLEU-4 METEOR SBERT with RAPTOR 30.87% 23.50% 6.42% 19.20% SBERT without RAPTOR 29.26% 22.56% 5.95% 18.15% BM25 with RAPTOR 27.93% 21.17% 5.70% 17.03% BM25 without RAPTOR 23.52% 17.73% 4.65% 13.98% DPR with RAPTOR 30.94% 23.51% 6.45% 19.05% DPR without RAPTOR 29.56% 22.84% 6.12% 18.44% Likewise, in the QuALITY dataset as shown in Table 5, RAPTOR achieves an accuracy of 62.4%, which is a 2% and 5.1% improvement over DPR and BM25. Similar trends are observed when UnifiedQA is employed, with RAPTOR outperforming DPR and BM25 by 2.7% and 6.7%, respectively. Finally, in the NarrativeQA dataset, as presented in Table 6, RAPTOR excels across multiple metrics. For ROUGE-L, it surpasses BM25 and DPR by 7.3 and 2.7 points, respectively. In other metrics like BLEU-1, BLEU-4, and METEOR, RAPTOR outperforms BM25 and DPR by margins ranging from 1.7 to 5.8 and 0.7 to 2.1 points, respectively. Table 2:QuALITY and QASPER Performance With + Without RAPTOR: Performance comparison across the QuALITY and QASPER datasets of various retrieval methods (SBERT, BM25, DPR) with and without RAPTOR. UnifiedQA-3B is used as the language model. RAPTOR outperforms baselines of each respective retrieval method for both datasets. Model Accuracy (QuALITY) Answer F1 (QASPER) SBERT with RAPTOR 56.6% 36.70% SBERT without RAPTOR 54.9% 36.23% BM25 with RAPTOR 52.1% 27.00% BM25 without RAPTOR 49.9% 26.47% DPR with RAPTOR 54.7% 32.23% DPR without RAPTOR 53.1% 31.70% Table 3:Controlled comparison of F-1 scores on the QASPER dataset, using three different language models (GPT-3, GPT-4, UnifiedQA 3B) and various retrieval methods. The column ”Title + Abstract” reflects performance when only the title and abstract of the papers are used for context. RAPTOR outperforms the established baselines BM25 and DPR across all tested language models. Specifically, RAPTOR’s F-1 scores are at least 1.8% points higher than DPR and at least 5.3% points higher than BM25. Retriever GPT-3 F-1 Match GPT-4 F-1 Match UnifiedQA F-1 Match Title + Abstract 25.2 22.2 17.5 BM25 46.6 50.2 26.4 DPR 51.3 53.0 32.1 RAPTOR 53.1 55.7 36.6 Table 4:Comparison of accuracies on the QuALITY dev dataset for two different language models (GPT-3, UnifiedQA 3B) using various retrieval methods. RAPTOR outperforms the baselines of BM25 and DPR by at least 2.0% in accuracy. Table 5:Results on F-1 Match scores of various models on the QASPER dataset. Model GPT-3 Acc. UnifiedQA Acc. BM25 57.3 49.9 DPR 60.4 53.9 RAPTOR 62.4 56.6 Model F-1 Match LongT5 XL (Guo et al., 2022) 53.1 CoLT5 XL (Ainslie et al., 2023) 53.9 RAPTOR + GPT-4 55.7 Table 5:Results on F-1 Match scores of various models on the QASPER dataset. Comparison to State-of-the-art Systems Building upon our controlled comparisons, we examine RAPTOR’s performance relative to other state-of-the-art models. As shown in Table 5, RAPTOR with GPT-4 sets a new benchmark on QASPER, with a 55.7% F-1 score, surpassing the CoLT5 XL’s score of 53.9%. In the QuALITY dataset, as shown in Table 7, RAPTOR paired with GPT-4 sets a new state-of-the-art with an accuracy of 82.6%, surpassing the previous best result of 62.3%. In particular, it outperforms CoLISA by 21.5% on QuALITY-HARD, which represents questions that humans took unusually long to correctly answer, requiring rereading parts of the text, difficult reasoning, or both. For the NarrativeQA dataset, as represented in Table 6, RAPTOR paired with UnifiedQA sets a new state-of-the-art METEOR score. When compared to the recursively summarizing model by Wu et al. (2021), which also employs UnifiedQA, RAPTOR outperforms it on all metrics. While Wu et al. (2021) rely solely on the summary in the top root node of the tree structure, RAPTOR benefits from its intermediate layers and clustering approaches, which allows it to capture a range of information, from general themes to specific details, contributing to its overall strong performance. Table 6:Performance comparison on the NarrativeQA dataset across multiple models, focusing on four metrics: ROUGE-L, BLEU-1, BLEU-4, and METEOR. RAPTOR, when paired with UnifiedQA 3B, not only surpasses retrieval methods like BM25 and DPR but also sets a new state-of-the-art in the METEOR metric. Model ROUGE-L BLEU-1 BLEU-4 METEOR BiDAF (Kočiskỳ et al., 2018) 6.2 5.7 0.3 3.7 BM25 + BERT (Mou et al., 2020) 15.5 14.5 1.4 5.0 Recursively Summarizing Books (Wu et al., 2021) 21.6 22.3 4.2 10.6 Retriever + Reader (Izacard & Grave, 2022) 32.0 35.3 7.5 11.1 RAPTOR + UnifiedQA 30.8 23.5 6.4 19.1 Table 7:Accuracies of the QuALITY dataset on both the overall test set and the more challenging hard subset. GPT-4 with RAPTOR sets a new state-of-the-art. Model Accuracy Test Set Hard Subset Longformer-base (Beltagy et al., 2020) 39.5 35.3 DPR and DeBERTaV3-large (Pang et al., 2022) 55.4 46.1 CoLISA (DeBERTaV3-large) (Dong et al., 2023a) 62.3 54.7 RAPTOR + GPT-4 82.6 76.2 4.1Contribution of the tree structure Table 8:Performance of RAPTOR when querying different tree layers for Story 1 from the QuALITY dataset. Columns represent different starting points (highest layer) and rows represent different numbers of layers queried. Layers Queried / Start Layer Layer 0 (Leaf Nodes) Layer 1 Layer 2 1 layer 57.9 57.8 57.9 2 layers - 52.6 63.15 3 layers - - 73.68 We examine the contribution of each layer of nodes to RAPTOR’s retrieval capabilities. We hypothesized that upper nodes play a crucial role in handling thematic or multi-hop queries requiring a broader understanding of the text. We validated this hypothesis both quantitatively and qualitatively. We present qualitative analysis in appendix G. To quantitatively understand the contribution of the upper-level nodes, we used stories from the QuALITY dataset. The RAPTOR tree is built for each of these stories, as described in Section 3. However, during retrieval, we limit the search to different subsets of layers. For example, we exclusively retrieve from the leaf nodes and each upper layer, as well as from different contiguous subsets of the layers. We show findings specific to one story in Table 8, revealing that a full-tree search, utilizing all layers, outperformed retrieval strategies that focused only on specific layers. These findings highlight the importance of the full tree structure in RAPTOR. By providing both the original text and higher-level summaries for retrieval, RAPTOR can effectively handle a wider range of questions, from higher-order thematic queries to detail-oriented questions. Detailed results for additional stories and an ablation study on layer contributions can be found in Appendix I. 5Conclusion In this paper, we have presented RAPTOR, a novel tree-based retrieval system that augments the parametric knowledge of large language models with contextual information at various levels of abstraction. By employing recursive clustering and summarization techniques, RAPTOR creates a hierarchical tree structure that is capable of synthesizing information across various sections of the retrieval corpora. During the query phase, RAPTOR leverages this tree structure for more effective retrieval. Our controlled experiments demonstrated that RAPTOR not only outperforms traditional retrieval methods but also sets new performance benchmarks on several question-answering tasks. 6Reproducibility Statement Language Models for QA and Summarization Four language models are used in our RAPTOR experiments: GPT-3 and GPT-4 for QA tasks, and GPT-3.5-turbo for summarization. The gpt-3, gpt-4, and gpt-3.5-turbo models can be accessed via API calls (OpenAI API). UnifiedQA, which is used for QA tasks, is publicly available at Hugging Face. Evaluation Datasets The three evaluation datasets used in our experiments—QuALITY, QASPER, and NarrativeQA—are all publicly accessible. These datasets ensure that the retrieval and QA tests conducted in this study can be replicated. Source Code The source code for RAPTOR will be publicly available here.""

question:Ok, great. Well done. Now, according to both papers and their summaries, which method would be better (more accurate) for me to use. I want to perform deep offline analysis of unstructured data concerning the intangible value of businesses for the quantitative finance industry.

question:"Incorporating a layered approach, where RAPTOR’s hierarchical, thematic insights are combined with ColBERTv2’s efficient retrieval capabilities, might offer a comprehensive solution if feasible. This could leverage ColBERTv2’s efficiency and effectiveness in retrieval across domains and RAPTOR’s strength in providing deep, hierarchical insights into complex, unstructured texts." How would this work? What would be the process? Wouldn't the two methods get in each others way? Also, the computational comlpexity (speed, latency and cost) would be much higher, right?