PaperlayerView exact revision on arXiv

Source-linked AI summary

IncDSI: Incrementally Updatable Document Retrieval

Varsha Kishore, Chao Wan, Justin Lovelace, Yoav Artzi, Kilian Q. Weinberger

arXiv:2307.10323v2cs.IRcs.CLcs.LG

TL;DR

Differentiable search indexes are difficult to update with new documents, even though dynamic corpora need timely indexing. IncDSI adds documents by optimizing their representations while holding the rest of the system fixed, achieving comparable performance to retraining with updates in about 50 milliseconds per document.

  • Problem

    Adding documents to a DSI is difficult because training on new documents risks forgetting existing ones, while periodic retraining is costly and real-time extension has remained open.

    Source: §1 · p. 1

  • Method

    IncDSI adds a document by optimizing a new document representation under constraints while keeping the rest of the retrieval system fixed.

    Source: §4.2 · p. 5, §8 · p. 9

  • Results

    IncDSI retains retrieval performance on old documents and achieves comparable performance on new documents to retraining, while indexing each document in about 50 milliseconds.

    Source: §1 · p. 2

  • Takeaways & Limitations

    IncDSI offers a way to index documents in real time and can potentially reduce how often resource-intensive retraining is required.

    Source: §6 · p. 8

    As more documents are added, performance on the original set degrades slightly, so the model eventually needs retraining.

    Source: §7 · p. 9

Abstract

from arXiv · show

Differentiable Search Index is a recently proposed paradigm for document retrieval, that encodes information about a corpus of documents within the parameters of a neural network and directly maps queries to corresponding documents. These models have achieved state-of-the-art performances for document retrieval across many benchmarks. These kinds of models have a significant limitation: it is not easy to add new documents after a model is trained. We propose IncDSI, a method to add documents in real time (about 20-50ms per document), without retraining the model on the entire dataset (or even parts thereof). Instead we formulate the addition of documents as a constrained optimization problem that makes minimal changes to the network parameters. Although orders of magnitude faster, our approach is competitive with re-training the model on the whole dataset and enables the development of document retrieval systems that can be updated with new information in real-time. Our code for IncDSI is available at https://github.com/varshakishore/IncDSI.

1. Introduction

Document retrieval systems need to incorporate new documents as dynamic collections grow. IncDSI addresses the difficulty of updating differentiable search indexes without retraining, using constrained optimization and achieving comparable retrieval performance with updates in about 50 milliseconds per document.

1. Introduction

  • DSI encodes a document collection in neural-network parameters and maps queries directly to document IDs, but adding documents risks forgetting and retraining is costly.By contrast, dual encoders can add documents by encoding them and including their vectors in nearest-neighbor search.Source: §1 · p. 1
  • The target setting is a dynamic corpus where newly uploaded documents should become available as soon as possible, ideally in real time.Although DSI can be retrained periodically, real-time extension had remained an open problem.Source: §1 · p. 1
  • IncDSI formulates adding documents as constrained optimization over document representations, extending the number of classes without retraining.It treats document vectors as independent from the query encoder, so adding one does not change existing document vectors or require broader encoder updates.Source: §1 · pp. 1–2
  • IncDSI retains retrieval performance on old documents and achieves comparable performance on new documents to retraining, while adding a document in about 50 milliseconds.The approach is evaluated while incrementally adding up to 10k documents.Source: §1 · p. 2

2. Related work

Related work covers sparse and dense retrieval, end-to-end differentiable search indexing, query-generation methods, and approaches to mitigating forgetting during continual learning.

Sparse and Dense retrieval

  • Dense retrieval uses neural networks to learn low-dimensional query and document representations, typically retrieving with approximate nearest-neighbor search.Earlier sparse methods are described as simple and effective but often unable to capture rich semantic connections.Source: §2 · p. 2

End-to-end Retrieval

  • DSI combines indexing and retrieval end to end, learning document IDs from text and mapping queries to IDs by generation or classification.Other DSI work improves performance with generated queries, decoder changes, or keyword- and semantic-based document IDs.Source: §2 · pp. 2–3

Query Generation in document retrieval

  • Generated queries can improve document indexing and retrieval, including settings where human queries are unavailable.Prior work uses generated queries alongside document tokens or generates synthetic queries from document-query examples.Source: §2 · p. 3

Preventing forgetting

  • Continual-learning approaches address catastrophic forgetting through replaying old examples and optimizing flatter loss basins (Chaudhry et al., 2019; Foret et al., 2020).The cited work reports that repeating even a small part of old training data can reduce forgetting to some extent.Source: §2 · p. 3

3. Problem Setup and Notation

IncDSI begins with a retrieval model trained on an initial document set, then updates it as additional documents arrive in a stream.

3. Problem Setup and Notation

  • The setup first trains a retrieval model M_0 on an initial set of documents D_0, using associated queries for training.The queries may be user queries or generated queries, treated the same way.Source: §3 · p. 3
  • Additional documents arrive in a streaming fashion, and the model is updated as each new document becomes available.The passage denotes the new documents as D′ and the model after t additions as M_t.Source: §3 · p. 3
  • Each new document has associated queries, which may be user queries or queries produced by a query-generation model.Both query sources are used in the same manner.Source: §3 · p. 3

4. IncDSI

IncDSI adds documents to a classification-based DSI model by optimizing a new document vector. It aims to retrieve queries for the new document without disrupting retrieval for existing documents, and applies the procedure sequentially for further additions.

4.1. Document Retrieval Model

  • The initial model uses a BERT-based DSI classification setup trained to map queries to document IDs.The model is trained with cross-entropy loss; the classification layer represents document classes.Source: §4.1 · pp. 3–4

4.2. Incremental Addition

  • IncDSI adds a document by optimizing one new class vector against its associated queries while keeping existing document vectors fixed.The new vector is appended to the classification layer as an additional document class.Source: §4.2 · p. 4, Figure 2 · p. 4
  • Cached queries for original documents provide constraints that preserve their retrieval, while a squared-hinge loss encourages correct retrieval of the new document.The constraints discourage the new vector from outranking the original document for its representative query embeddings.Source: §4.2 · p. 5
  • The objective balances retrieving new-document queries against preserving original-document performance, with a separate L2 regularization weight.L-BFGS optimizes the new vector for at most 30 iterations, with early termination when the update norm is below 10^-3.Source: §4.2 · p. 5
  • After each addition, the updated document and representative-query matrices are used to repeat the optimization for subsequent documents.This supports adding a stream of documents sequentially.Source: §4.2 · pp. 5–6

5. Experiments

The experiments use Natural Questions 320K and MS MARCO with separate initial, streaming-addition, and tuning document sets. They evaluate retrieval on original and new documents and tune IncDSI’s hyperparameters using validation performance.

Datasets

  • Experiments use NQ320K and MS MARCO, splitting documents into 90% initial, 9% new, and 1% tuning sets.The datasets contain query-document pairs, including natural-language questions and associated Wikipedia articles or web pages.Source: §5 · p. 6

Metrics

  • Evaluation measures Hits@1, Hits@5, Hits@10, and MRR@10 on queries for both original and newly added documents, plus document-addition time..Source: §5 · p. 7

Hyperparameter tuning

  • IncDSI’s four hyperparameters are tuned over 50 Ax trials using a weighted harmonic mean of validation MRR@10 for original and tuning documents.The authors set β = 5 to emphasize preserving retrieval performance for original documents.Source: §5 · p. 7

6. Results and Discussions.

IncDSI adds documents to trained retrieval models rapidly while retaining retrieval quality on existing documents and achieving performance on new documents comparable to retraining. Results also show trade-offs across original and new documents as the tuning weight and query choices change.

6. Results and Discussions.

  • On NQ320K, IncDSI indexes 1,000 documents in roughly 16 seconds at H@1 62.0, while DSI-Scratch takes 2hr17m for H@1 63.4; on MS MARCO, new-document H@1 is 61.0 versus at most 51.8 for baselines.The reported DSI-Scratch indexing time is over 513× longer.Source: §6 · p. 8
  • For NQ320K additions of at least 100 documents, IncDSI achieves new-document H@1 greater than 61.0 while DPR never exceeds 48.0, with similar millisecond-scale indexing speed.The paper attributes this performance difference to optimizing document representations directly rather than relying on a parametric encoder.Source: §6 · p. 8
  • During incremental indexing, original-document H@10 remains nearly constant, while Hits@1 degrades slowly over time.Figure 4 plots retrieval performance for original and new documents as document counts increase, averaging IncDSI over 10 random orderings.Source: §6 · p. 8, Figure 4 · p. 8
  • IncDSI yields performance close to retraining for near-real-time additions, but is not presented as a replacement for retraining when many documents must be added.The authors suggest it could reduce how often resource-intensive retraining is required.Source: §6 · p. 8
  • Using only generated queries to add 1,000 NQ320K documents yields performance comparable to baselines, while adding natural queries provides significant gains.The authors suggest the gains may reflect the greater structural and content diversity of natural queries.Source: §6 · p. 8
  • Increasing β monotonically improves retrieval on original documents at the expense of new-document performance; the authors select β = 5 as a balance.Other β values may be preferable depending on the application.Source: §6 · p. 9
  • On NQ320K, IncDSI is not sensitive to the number of generated queries, though other datasets may benefit from more queries.The paper says more generated queries produce a more robust document-class representation that leads to better generalization.Source: §6 · p. 9
  • Standard and squared hinge losses achieve similar performance, but the squared hinge loss is almost 3.3× faster.The authors use the squared hinge loss in IncDSI.Source: §6 · p. 9

7. Limitations and Future work

IncDSI has limits as the corpus grows: performance on the original documents gradually degrades, and the method relies on a frozen query encoder trained on the initial documents. The work considers adding documents, while leaving document editing for future study.

7. Limitations and Future work

  • As more documents are added, performance on the original set degrades slightly, and eventually the model must be retrained.Alternative optimization objectives might preserve performance longer.Source: §7 · p. 9
  • New-query embeddings rely on a frozen query encoder trained on initial documents to generalize effectively.The authors suggest exploring pretraining or other ways to improve generalizability.Source: §7 · p. 9
  • The study considers adding documents; editing existing documents is proposed through new constraints but left for future work.The proposed editing approach would optimize the corresponding document vector.Source: §7 · p. 9

8. Conclusion

IncDSI adds documents to a trained DSI model in roughly 50 milliseconds by optimizing document representations while holding the rest of the system fixed. The appendix describes dataset handling and evaluation for the new documents.

8. Conclusion

  • Roughly 50 milliseconds per document, IncDSI uses constrained optimization of the document representation while keeping the rest of the system fixed, with performance comparable to retraining.The method extends the number of document classes without retraining.Source: §8 · p. 9

A. Datasets.

  • NQ320K documents are deduplicated by title, avoiding separate IDs for versions that differ only in minor edits.The passage contrasts this with URL-based deduplication, which can retain such versions separately.Source: A. Datasets · p. 12
  • Generated training queries are sampled from different 512-token document sections to encourage diversity.The queries are produced with docTTTTTquery.Source: A. Datasets · p. 12
  • After adding documents, accuracy is evaluated using validation or test queries corresponding to the newly added documents.Source: A. Datasets · p. 12

B. Training with and without Document Text

The experiments compare training with queries alone against training with queries plus the first 32 document tokens; the authors choose queries alone for simplicity.

B. Training with and without Document Text

C. Results on NQ320K

On NQ320K, IncDSI achieves Hits@1 and Hits@10 comparable to DSI-Scratch and DSI-DPR while taking much less time to add documents. DPR performs substantially worse, and adding documents with DPR requires no additional training.

C. Results on NQ320K

  • DPR performs much worse because it uses a frozen model trained on the initial data to encode new documents and queries.DPR requires no additional training when new documents are added, so its addition time is not shown.Source: C. Results on NQ320K · pp. 12–13
  • IncDSI's Hits@1 and Hits@10 are comparable to DSI-Scratch and DSI-DPR, while its document-addition time is much shorter.Source: C. Results on NQ320K · p. 12, Table 7 · p. 13

D. Results on MS MARCO

On MS MARCO, IncDSI outperforms trained baselines, especially on new-document performance. The dataset is harder than NQ320K, and its table reports Hits@k and document-addition time.

D. Results on MS MARCO

Related papers

Loading 2307.10323v2…