Capturing Structural Locality in Non-parametric Language Models

Frank F. Xu, Junxian He, Graham Neubig, Vincent Josua Hellendoorn

Introduction

While modern language models are exceptionally good at finding "what" is similar, they often ignore "where" that information comes from. Structural locality—such as project hierarchies in code or topical categories in Wikipedia—is a ubiquitous feature of real-world datasets. This paper introduces a simple, lightweight method to incorporate this structural locality into non-parametric language models, leading to significant gains in prediction accuracy with as few as five additional parameters.

The Limits of Contextual Similarity

Standard "parametric" language models (like GPT) store their knowledge entirely within their network weights. "Non-parametric" models, such as $k$NN-LM, take a different approach: they maintain a datastore of millions of text snippets. When predicting the next word, they look up the most similar contexts in this datastore and use them to inform the prediction.

Currently, these models rely entirely on contextual similarity, typically measured by the L2 distance between vector embeddings. However, embeddings are imperfect. For example, a code snippet from a completely different software project might look similar to your current work but use different naming conventions or libraries. Conversely, a snippet from the same file is highly likely to be relevant, even if the embedding distance is slightly larger. The authors argue that the hierarchical structure of data is a vital signal that current models are leaving on the table.

Incorporating Structural Locality

The authors propose a simple yet effective modification to the $k$NN-LM architecture. Instead of using the raw distance $d$ between a query and a retrieved neighbor, they compute a modified distance $g$:

$$g = w_n \cdot d + b_n$$

Here, $w_n$ and $b_n$ are learnable weights and biases specific to a locality level ($l_n$).

Illustration of how structural locality modifies retrieval distances.
  1. Define Locality Levels: For Java code, levels include "same subdirectory," "same project," or "different project." For Wikipedia, they use "same article/section" and "same category."
  2. Learn the Correction: A small validation set is used to learn the $w$ and $b$ parameters, requiring only 5-7 parameters in total.
  3. Adjust the Retrieval: During inference, the model "shrinks" the distance for local neighbors. This effectively trains the model to trust examples from the same project or article more than those from disparate sources.

Key Insights and Results

The researchers evaluated their approach on two distinct domains: WikiText-103 (103 million tokens from English Wikipedia) and JAVA GITHUB (1.44 billion tokens from over 13,000 GitHub projects).

Impact of locality on accuracy and distance across WikiText-103 and Java GitHub datasets.
  • The Repetitiveness of Code: The performance gains were significantly higher in source code than in natural language. Software projects are highly repetitive and follow strict internal logic; if a variable name is used once in a project, it is very likely to appear again in the same subdirectory. The Java dataset saw a 4.9% relative error reduction in Top-1 accuracy over the standard $k$NN-LM, with perplexity dropping from 2.18 to 2.13.
  • Correcting the Embedding Space: Contextual similarity metrics alone are not enough to grasp locality. By visualizing the modified distances, the authors showed that the model learns to aggressively prioritize local neighbors, effectively fixing instances where the neural embedding was ambiguous.
  • Interpretability: Unlike complex black-box attention mechanisms, this method provides clear insights. In Wikipedia, for instance, the model learned that sharing a "section title" is a much stronger signal of relevance than just sharing a broad "category." Wikipedia perplexity improved from 19.94 to 19.16 with almost zero computational overhead.
  • Efficiency: Because the method only modifies the final distance calculation of retrieved neighbors, it adds negligible latency to the model's inference time.

Limitations and Future Work

While highly effective, the method requires that the datastore includes metadata about the source of each snippet (e.g., file paths or article IDs). In "in-the-wild" datasets where this metadata is missing, the method cannot be applied. Furthermore, the current model uses fixed weights for locality. Experiments with "adaptive" weights that change based on the current context did not provide a significant boost, suggesting that the simple linear shift is surprisingly robust.

Future directions could expand this approach to other structured domains like legal documents (case hierarchies), medical records, or research papers (citation networks), where structural locality plays a similarly crucial role.

Summary updated

Abstract

Structural locality is a ubiquitous feature of real-world datasets, wherein data points are organized into local hierarchies. Some examples include topical clusters in text or project hierarchies in source code repositories. In this paper, we explore utilizing this structural locality within non-parametric language models, which generate sequences that reference retrieved examples from an external source. We propose a simple yet effective approach for adding locality information into such models by adding learned parameters that improve the likelihood of retrieving examples from local neighborhoods. Experiments on two different domains, Java source code and Wikipedia text, demonstrate that locality features improve model efficacy over models without access to these features, with interesting differences. We also perform an analysis of how and where locality features contribute to improving performance and why the traditionally used contextual similarity metrics alone are not enough to grasp the locality structure.
BibTeX
@inproceedings{xu2022capturing,
  author = {Frank F. Xu and Junxian He and Graham Neubig and Vincent Josua Hellendoorn},
  title = {{Capturing Structural Locality in Non-parametric Language Models}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=nnU3IUMJmN},
}
Figure