Stolen Probability: A Structural Weakness of Neural Language Models

David Demeter, Gregory Kimmel, Doug Downey

TL;DR

Standard neural language models suffer from a fundamental geometric flaw called the stolen probability effect, which prevents words located on the interior of the embedding space's convex hull from ever receiving high probability scores. This structural weakness means these models mathematically cannot predict certain infrequent words with high confidence, even in highly predictable contexts.

What Problem Does This Paper Address?

Most Neural Network Language Models (NNLMs) predict the next word by taking the dot product of a context-driven prediction vector ($h_t$) and all word embedding vectors ($x_i$), passing the results through a softmax function.

The authors reveal a hidden limitation in this ubiquitous setup: the geometry of the dot-product softmax strictly bounds the maximum probability of any word whose embedding vector falls inside the convex hull of the vocabulary. Even if a sequence perfectly points to an interior word (for example, the word "America" completing the phrase "the United States of America"), the model is structurally incapable of assigning it a high probability. Instead, that probability is effectively "stolen" by the words located on the outer hull of the embedding space.

Figure 1: Numerical Illustration of the Stolen Proba- bility Effect. Panels (i) and (ii) show the embedding of four words in a 2D embedding space. Word A is on the convex hull in panel (i), and interior to the convex hull in panel (ii). Panels (iii) and (iv) show the probability that would be assigned by the dot-product softmax to A for a range of prediction points ht in the x, y plane. When word A is on the convex hull, it can achieve nearly 100% probability for an ht prediction point in the far lower-left quadrant (see panel (iii)). When word A is interior to the convex hull, its maximum proba- bility is bounded by any word on the convex hull (see panel (iv)).

Methods

  • Theoretical Proof: The authors mathematically demonstrate that for any interior word vector, as the magnitude of the prediction vector grows to maximize confidence, its probability under a dot-product softmax asymptotically approaches zero.
  • Approximate Detection Algorithm: Finding an exact convex hull in high-dimensional spaces (e.g., over 10 dimensions) is computationally intractable using standard methods like Quickhull. The authors developed a high-precision, low-recall approximation algorithm that discretizes the angular space of an $n$-sphere to systematically identify and classify interior words.
  • Model Evaluation: The authors evaluated the effect on two popular architectures—AWD-LSTM and the Mixture of Softmaxes (MoS) model—across various dimensionalities ($d \in \{50, 100, 200\}$).
  • Targeted Ensembling: To mitigate the effect, they built a hybrid model that combines an NNLM with a traditional smoothed trigram model. Because $n$-gram models rely on count statistics rather than dot-product geometry, they do not suffer from the stolen probability limitation.

Datasets

The models were trained and evaluated on the standard Wikitext-2 corpus. While no new datasets were introduced, the authors used their detection algorithm to partition the Wikitext-2 vocabulary into distinct "interior" and "non-interior" word sets for analysis.

Key Insights and Ideas

  • Geometry Binds Expressiveness: The stolen probability effect is a consequence of the spatial arrangement of word embeddings rather than the dimensionality of the space or matrix rank. This makes it distinct from the well-known "softmax bottleneck."
  • Infrequent Words Suffer Most: Words that appear infrequently in the training data naturally tend to have smaller embedding norms. This pulls them toward the center of the embedding space, inadvertently trapping them inside the convex hull.
  • Bias Terms Are Not a Cure: Word-specific bias terms only shift logits by a constant factor. They can adjust the severity of the effect but cannot alter the underlying geometric boundaries that cause probability bounding.

Key Results

  • The Probability Gap: As shown in the maximum probability rankings, NNLMs severely struggle to assign high probabilities to interior words, whereas traditional trigram models easily capture their true statistical likelihood.
Figure 2: Maximum Probability of Top 500 Inte- rior and Non-Interior Words. The MoS model with d = 100 struggles to assign high probability to interior words, while trigrams were able to capture more accu- rate statistics. This behavior is absent for non-interior words.
  • Ensemble Rescue: Incorporating a trigram model dramatically improved performance for interior words. For an MoS model ($d=100$), the targeted ensemble dropped the training perplexity of interior words from 700.0 to 157.2 and test perplexity from 645.6 to 306.7.
  • Geometric vs. Norm-Based Effects: While interior words generally have smaller embedding norms, the scatter plot of maximum probability vs. embedding norm confirms that the limitation is strictly geometric: non-interior words with similarly small norms face no such probability ceiling.
Scatter plot demonstrating that interior words are bounded to low maximum probabilities regardless of their embedding norm.

Limitations and Future Work

  • Approximate Detection: The proposed detection algorithm favors precision over recall (achieving ~100% precision but only 68% recall in low-dimensional tests). This means many interior words likely went undetected in higher dimensions.
  • Vocabulary Scale: Wikitext-2 has a relatively small vocabulary. The authors note that larger vocabularies might introduce more interior words, potentially shifting or worsening the impact of the stolen probability effect.
  • Architectural Alternatives: While ensembling with $n$-grams mitigates the issue, the ultimate solution requires designing alternative neural network output layers that completely bypass the structural limitations of the dot-product softmax.

Summary updated

Abstract

Neural Network Language Models (NNLMs) generate probability distributions by applying a softmax function to a distance metric formed by taking the dot product of a prediction vector with all word vectors in a high-dimensional embedding space. The dot-product distance metric forms part of the inductive bias of NNLMs. Although NNLMs optimize well with this inductive bias, we show that this results in a sub-optimal ordering of the embedding space that structurally impoverishes some words at the expense of others when assigning probability. We present numerical, theoretical and empirical analyses showing that words on the interior of the convex hull in the embedding space have their probability bounded by the probabilities of the words on the hull.
BibTeX
@inproceedings{demeter2020stolen,
  author = {David Demeter and Gregory Kimmel and Doug Downey},
  title = {{Stolen Probability: A Structural Weakness of Neural Language Models}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2020},
  doi = {10.18653/v1/2020.acl-main.198},
}
Figure