TL;DR
The authors introduce NPM (NonParametric Masked Language Model), the first language model that completely replaces the traditional vocabulary softmax layer with a fully nonparametric retrieval distribution over phrases in a reference corpus. By filling in [MASK] tokens purely via text retrieval, NPM achieves massive parameter efficiency, outperforming parametric models up to 500x its size on zero-shot tasks, particularly when handling rare words, facts, and out-of-vocabulary scripts.
What Problem Does This Paper Address?
Traditional language models (LMs) predict tokens by computing a softmax over a fixed, finite vocabulary. This design introduces a major "softmax bottleneck": it forces a low-rank approximation on a high-rank output space, making it incredibly difficult for models to predict rare words, specialized entities, or morphologically rich phrases (e.g., "Thessaloniki"). Furthermore, parametric models struggle to update their internal knowledge base without expensive retraining or fine-tuning, often failing on long-tail or temporally shifting facts.
While "retrieve-and-generate" architectures mitigate this by appending retrieved context to the prompt, their final prediction layer still relies on a fixed parametric vocabulary softmax. NPM addresses this core limitation by making the prediction space entirely nonparametric and unbounded.
Methods
NPM consists of a dense encoder and a reference text corpus $\mathcal{C}$. Instead of predicting a token ID, NPM maps the masked query and all phrases in the reference corpus into the same dense vector space.
1. Inference via Dual-Vector Retrieval
To predict an arbitrary-length phrase without an autoregressive decoder, NPM represents a masked span using two special tokens: [MASKs] (start) and [MASKe] (end).
- The query is encoded to produce two vectors: $q^{\text{start}}$ and $q^{\text{end}}$.
- NPM performs a fast $k$-nearest neighbor ($k$-NN) search over the reference corpus to independently find candidate start tokens ($c_i$) and end tokens ($c_j$).
- It then aggregates the similarity scores to predict the most likely $n$-gram phrase to fill the mask.
2. Contrastive Training
Training a fully nonparametric model from scratch is challenging because full-corpus retrieval during every training step is computationally prohibitive. The authors solve this using an in-batch approximation:
- Span Masking: They mask consecutive token spans, but only if those spans co-occur in other sequences within the same batch, guaranteeing the existence of "in-batch positives."
- Objective: They optimize a phrase-level contrastive learning objective, forcing the
[MASKs]and[MASKe]vectors to be close to the true start and end tokens of the phrase found elsewhere in the batch, while pushing them away from negative tokens.
Datasets
- Training Data: A massive 13-billion-token compilation of English Wikipedia (August 2019) and the English portion of CC-News (February 2019).
- Closed-set Evaluation: 9 standard text classification and sentiment datasets (including AGNews, Yahoo, SST-2, Subj, MR, RT, CR, Amz, and RTE).
- Open-set Evaluation: Knowledge-intensive benchmarks including LAMA (T-REx and Google-RE), KAMEL, Natural Questions (NQ), and TriviaQA (TQA).
- Temporal & Cross-Lingual Benchmarks: TempLAMA (for tracking factual updates between 2019 and 2022) and a newly curated Entity Translation task spanning 15 non-Latin languages (e.g., Arabic, Korean, Greek, Japanese).
Key Insights and Ideas
- Unbounded Output Space: Because NPM predicts by pointing to phrases in a corpus rather than selecting from a vocabulary matrix, its vocabulary is effectively infinite. It can seamlessly output words or characters it has never explicitly seen during training, provided they exist in the test-time reference corpus.
- Implicit Word Sense Disambiguation: Parametric models often conflate different meanings of the same word. NPM leverages contextualized phrase representations, meaning the vector for "cheap" (inexpensive) naturally maps to a different neighborhood than "cheap" (poor quality), leading to superior context matching.
- Zero-Shot Knowledge Updating: To update the model's knowledge base, you do not need to alter a single parameter. You simply swap or append the reference corpus (e.g., replacing 2019 Wikipedia with 2022 Wikipedia), allowing the model to immediately adapt to new real-world facts.
Key Results
- Parameter Efficiency: On zero-shot closed-set classification tasks, the 354M-parameter NPM outperformed much larger parametric models, including the 175B-parameter GPT-3 (achieving an average accuracy of 76.4% vs. GPT-3's 60.2%).
- Open-Set Knowledge Tasks: NPM consistently outperformed retrieve-and-generate baselines. On LAMA T-REx, NPM scored 34.5% Exact Match (EM), outperforming a BM25 + GPT-3 combo (32.0%) and raw GPT-3 (25.7%).
- Rare Entity Robustness: The authors broke down performance by the number of Byte-Pair Encoding (BPE) splits (a proxy for word rarity). As the number of splits increased (meaning the word was rarer), NPM's performance advantage over GPT-3 widened significantly.
- Cross-Lingual Transfer: Despite being trained only on English text, NPM excelled at translating English entities into non-Latin scripts (e.g., Korean characters), outperforming monolingual baselines and approaching the performance of massive, explicitly multilingual models like mT5.
Limitations and Future Work
- Memory Footprint: While NPM saves GPU compute during training, it shifts the burden to storage. Indexing the full English Wikipedia requires roughly 70GB of RAM and 1.4TB of disk space for token embeddings.
- Inference Speed: Performing dense $k$-NN lookups makes inference slower than standard parametric models of equivalent size, though it remains competitive with ultra-large models like GPT-3.
- Generation Constraints: NPM is fundamentally an encoder-only masked language model designed for fill-in-the-blank tasks. Extending it to handle open-ended, autoregressive text generation remains an open challenge for future work.
Summary updated