# Generalization Properties of Retrieval-based Models

arXiv: https://arxiv.org/abs/2210.02617 · HTML: https://mlsanity.com/paper/2210.02617/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 61 references that are in the map.
- First posted on arXiv 6 Oct 2022.

## Builds on (most cited first, 29 of 29)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Bootstrap your own latent: A new approach to self-supervised Learning](https://mlsanity.com/paper/2006.07733/) (2020)
- [Scaling Up Visual and Vision-Language Representation Learning With Noisy Text Supervision](https://mlsanity.com/paper/2102.05918/) (2021)
- [Searching for MobileNetV3](https://mlsanity.com/paper/1905.02244/) (2019)
- [What Makes Good In-Context Examples for GPT-3?](https://mlsanity.com/paper/2101.06804/) (2021)
- [Scaling Vision Transformers](https://mlsanity.com/paper/2106.04560/) (2021)
- [Atlas: Few-shot Learning with Retrieval Augmented Language Models](https://mlsanity.com/paper/2208.03299/) (2022)
- [Large-Scale Long-Tailed Recognition in an Open World](https://mlsanity.com/paper/1904.05160/) (2019)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Universal Sentence Encoder](https://mlsanity.com/paper/1803.11175/) (2018)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [Adaptive Gradient-Based Meta-Learning Methods](https://mlsanity.com/paper/1906.02717/) (2019)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [Neural Episodic Control](https://mlsanity.com/paper/1703.01988/) (2017)
- [Case-based Reasoning for Natural Language Queries over Knowledge Bases](https://mlsanity.com/paper/2104.08762/) (2021)
- [Retrieval Augmented Classification for Long-Tail Visual Recognition](https://mlsanity.com/paper/2202.11233/) (2022)
- [Model-Free Episodic Control](https://mlsanity.com/paper/1606.04460/) (2016)
- [Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theory](https://mlsanity.com/paper/1711.01244/) (2017)
- [A PAC-Bayesian bound for Lifelong Learning](https://mlsanity.com/paper/1311.2838/) (2013)
- [Provable Guarantees for Gradient-Based Meta-Learning](https://mlsanity.com/paper/1902.10644/) (2019)
- [Training Data is More Valuable than You Think: A Simple and Effective Method by Retrieving from Training Data](https://mlsanity.com/paper/2203.08773/) (2022)
- [A Generalization Error Bound for Multi-class Domain Generalization](https://mlsanity.com/paper/1905.10392/) (2019)
- [Hypothesis Set Stability and Generalization](https://mlsanity.com/paper/1904.04755/) (2019)
- [Rapid Task-Solving in Novel Environments](https://mlsanity.com/paper/2006.03662/) (2020)
- [Matching-CNN Meets KNN: Quasi-Parametric Human Parsing](https://mlsanity.com/paper/1504.01220/) (2015)

## Built on by (most cited first, 5 of 5)

- [Transformers as Algorithms: Generalization and Stability in In-context Learning](https://mlsanity.com/paper/2301.07067/) (2023)
- [Improving Image Recognition by Retrieving from Web-Scale Image-Text Data](https://mlsanity.com/paper/2304.05173/) (2023)
- [KNN-LM Does Not Improve Open-ended Text Generation](https://mlsanity.com/paper/2305.14625/) (2023)
- [Retrieved Sequence Augmentation for Protein Representation Learning](https://mlsanity.com/paper/2302.12563/) (2023)
- [Schema-aware Reference as Prompt Improves Data-Efficient Knowledge Graph Construction](https://mlsanity.com/paper/2210.10709/) (2022)

## Abstract (arXiv)

Many modern high-performing machine learning models such as GPT-3 primarily rely on scaling up models, e.g., transformer networks. Simultaneously, a parallel line of work aims to improve the model performance by augmenting an input instance with other (labeled) instances during inference. Examples of such augmentations include task-specific prompts and similar examples retrieved from the training data by a nonparametric component. Remarkably, retrieval-based methods have enjoyed success on a wide range of problems, ranging from standard natural language processing and vision tasks to protein folding, as demonstrated by many recent efforts, including WebGPT and AlphaFold. Despite growing literature showcasing the promise of these models, the theoretical underpinning for such models remains underexplored. In this paper, we present a formal treatment of retrieval-based models to characterize their generalization ability. In particular, we focus on two classes of retrieval-based classification approaches: First, we analyze a local learning framework that employs an explicit local empirical risk minimization based on retrieved examples for each input instance. Interestingly, we show that breaking down the underlying learning task into local sub-tasks enables the model to employ a low complexity parametric component to ensure good overall accuracy. The second class of retrieval-based approaches we explore learns a global model using kernel methods to directly map an input instance and retrieved examples to a prediction, without explicitly solving a local learning task.