Nonparametric Masked Language Modeling

Sewon Min, Weijia Shi, Mike Lewis, Xilun Chen, Wen-tau Yih, Hannaneh Hajishirzi, Luke Zettlemoyer

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.
An illustration of NPM inference using start and end vectors to retrieve phrases from a reference corpus.

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

Abstract

Existing language models (LMs) predict tokens with a softmax over a finite vocabulary, which can make it difficult to predict rare tokens or phrases. We introduce NPM, the first nonparametric masked language model that replaces this softmax with a nonparametric distribution over every phrase in a reference corpus. NPM fills in the [MASK] solely from retrieving a token from a text corpus. We show that NPM can be efficiently trained with a contrastive objective and an in-batch approximation to full corpus retrieval. Zero-shot evaluation on 16 tasks including classification, fact probing and question answering demonstrates that NPM outperforms significantly larger parametric models, either with or without a retrieve-and-generate approach. It is particularly better at dealing with rare patterns (word senses or facts) and predicting rare or nearly unseen words (e.g., non-Latin script). We release the model and code at github.com/facebookresearch/NPM.
BibTeX
@inproceedings{min2023nonparametric,
  author = {Sewon Min and Weijia Shi and Mike Lewis and Xilun Chen and Wen-tau Yih and Hannaneh Hajishirzi and Luke Zettlemoyer},
  title = {{Nonparametric Masked Language Modeling}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2023},
  doi = {10.18653/v1/2023.findings-acl.132},
}
Figure