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.
The process involves three main steps:
- 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."
- 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$$
- 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.
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