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$).
- 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."
- Learn the Correction: A small validation set is used to learn the $w$ and $b$ parameters, requiring only 5-7 parameters in total.
- 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).
- 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