Capturing Structural Locality in Non-parametric Language Models

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

Introduction

Standard parametric language models, such as GPT or BERT, encode knowledge within fixed neural weights. In contrast, non-parametric models like kNN-LM augment these weights with an external datastore of context-token pairs. During inference, the model retrieves the most similar contexts to the current input and uses their associated tokens to refine predictions.

However, traditional retrieval relies on simple geometric distance (e.g., $l^2$ distance) between vector representations. This approach often overlooks the structural locality inherent in data—the hierarchical organization such as files within a project or sections within an article. This paper proposes a lightweight method to incorporate these structural relationships, significantly improving retrieval accuracy with minimal overhead.

Methods: Incorporating Locality

The authors introduce a modified retrieval process that adjusts the raw distance $d$ based on the "locality" of a retrieved example.

Overview of the kNN-LM retrieval process with locality-based distance modification.

The process involves three main steps:

  1. Defining Locality Levels: Discrete levels are defined based on domain structure. For Wikipedia, levels include "same section and category" or "same category, different section." For Java code, levels include "same subdirectory" or "same project."
  2. Learned Scaling: For each locality level $n$, the model learns a weight ($w_n$) and a bias ($b_n$). The modified distance $g$ is computed as: $$g = w_n \cdot d + b_n$$
  3. Optimization: These few parameters (typically 5–7) are tuned on a small validation set to minimize negative log-likelihood. This allows the model to learn the relative importance of local versus non-local neighbors without retraining the underlying Transformer.

Datasets

The method was evaluated on two distinct domains to prove its versatility:

  • WIKITEXT-103: A standard natural language benchmark of English Wikipedia articles (103M tokens).
  • JAVA GITHUB: A large-scale programming corpus (1.44B tokens) from over 13,000 projects, where structural hierarchy is strictly defined by directory structures.

Key Insights and Results

A central finding is that geometric proximity in vector space does not always equate to semantic relevance. Even when a non-local example is "closer" in vector space, a local example often provides a better prediction.

Relationship between negative distance, rank, and locality levels in the Wikipedia dataset.

As shown in Figure 3, examples with higher structural locality (e.g., "same section, same category") tend to have higher negative distances (smaller raw distances) for a given rank compared to those with "no locality." The proposed method learns to prioritize these local neighbors further.

Performance Gains

The inclusion of locality features yielded consistent improvements across both domains:

  • WIKITEXT-103: Perplexity decreased from 19.94 to 19.16, and Top-1 accuracy improved from 41.3% to 43.2%.
  • JAVA GITHUB: Perplexity dropped from 2.18 to 2.13, representing a 4.91% relative error reduction in Top-1 accuracy.
  • Interpretability: The learned parameters confirmed that the model effectively "discounts" the distance of local neighbors, moving them higher in the retrieval ranking.

Conclusion and Future Work

This research demonstrates that respecting the natural organization of data can significantly boost the performance of non-parametric language models. The approach is highly efficient, requiring only a handful of additional parameters and no retraining of the base model.

While the current method requires manual definition of locality levels, future work could explore "latent locality," where the model automatically discovers hierarchical structures. Additionally, this framework could be extended to other structured domains, such as scientific literature or technical documentation.

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 improved 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 J. 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