Capturing Structural Locality in Non-parametric Language Models
Authors: Frank F. Xu
Junxian He
Graham Neubig
Vincent Josua Hellendoorn
Venue: ICLR 2022 Poster (2022)

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.


Published as a conference paper at ICLR 2022
CAPTURING STRUCTURAL LOCALITY IN NON-PARAMETRIC LANGUAGE MODELS
Frank F. Xu, Junxian He, Graham Neubig, Vincent J. Hellendoorn School Computer Science Carnegie Mellon University (fangzhex, junnzaen g (calbiig)ecseeeo @cs. cmu. edu, vhellendoornécmu.o
ABSTRACT
Structural locality is a ubiquitous feature of real-world datasets, wherein data points 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 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 grasp the locality structure.
INTRODUCTION
Language models (LMs) predict probability distribution over sequences, and are most widely studied to model and generate natural languages (Bengio et al., 2203) Merity et al.) [2018] Baevski] & Auli 2018 Brown et al.] 2020). Advances in I.Ms benefit many natural language processing downstream tasks, such as machine translation (Bahdanau al. 2015), dialog systems (Sordoni et al., 2015), question answering Yang et al. [2019] Raffel et al. 2019). and general representation learning for natural language (Devlin et al. 20188] Liu et al. 2019). Recently, LMs have also been adopted to model sequences other than text, such source code written in programming language (Hindle et al., 2016 Hellendoorn Devanbu 2017 Alon et al. 2020 Karampatsis et al,, 2020), which can enable useful downstream tasks like code completion (Raychev et 2014).
Most current neural LMs are based on parametric neural networks, using RNN Miikolov et al. 2010) Transformer /Vaswani al. 2017) architectures. These models make predictions solely using a fixed set of neural network parameters. Recently, more and more neural LMs also incorporate non-parametric components (Grave et al. 2017 Guu al. 2018 He et al. 2020 Khandelwal et al.) 2020), which usually first select examples from an external source and then reference them during the prediction. For example, Khandelwal et al. (220)) model the token-level probability by interpolating the parametric LM probability with a probability obtained from the nearest context-token pairs in an external datastore. Using such non- parammemetricc components in LMs is beneficial because the model no longer needs to memorize everything about the language in its parameters.
For such non-pant maraamamttric LMs, one important concept a distance metric between the current context and other contexts in the datastore. One example of such metric is the l distance between context vectors calculated by the parametric model (Khandelwal et al., 2020). This distance can be used in both retrieval and probability calculation; items in the datastore that are less distant from the current context are more likely to be retrieved and have a higher influence on the final probability. However, given that non parammemtii datastores disparate sources, calculating a metric that accurately reflects semantic similarities non-trivial; as demonstrate in experiments, there is much room for improvement in current practice.
typically very large, containing myriad of contexts from

---

Published as a conference paper at ICLR 2022
Contetrreonntst
Target
Distance
Calegaay Section
Modilfed Distance
Obama awerded the
Nobel
Robel
3
Politics Awards
Hobel
15
Judes Pearl received his
Ba Bachelor
Bachelor
22
CS
Early Life)
Bachelor
50
Judos Pearl received the Terence Tao won the
Turiing Fields
Puring
20
CS
Awards
Turing
5
Fields
10
Math
Awards
Pields
22.
query (()(
Normaline
Aggngate
Currenk Conteed G
Wrr
Current Locality
Gooftxay Einton
awarded the
Awardss
PRNN (welc)
An example of incorporating structural locality in the computation flow of (we(ee))))) The current context o is used to calculate distance d to contexts in the datastore (c,w). Dashed boxes and lines represent components proposed in our work, which leverage structural information ( (non-local, local) to allow for more accurate modified distances (lower is more similar).
Figure 1:
In this paper, we argue that the relevance of contexts may be correlated with not only contextual distance, but also structural characteristics of the underlying data. Specifically, take advantage of a property we dub structural locality, the propensity of text to be divided into local groups sharing common hierarchical attributes. This property is ubiquitous across many kinds of texts and can provide additional information on how closely related two different examples are to each other. Throughout this paper, we will provide two case-studies of this phenomenon. First, in the domain of programs written in source code, if two source files originate from the same project, they are more likely to be related than files from other projects, and even more so if they are from the exact same package (Hellendoorn & Devanbu (017). Second, in natural language, two sections of Wikipedia text may be more related they fall within the same topical domain, are from similarly titled sections, or even are from the same article (as in Figure [].. Notably this locality often manifests itself at different levels, such as the levels of "project", "subdirectory". and "file" cited above for source code.
In this paper, we hypothesize that by using multiple levels of structural locality, we can better calibrate the distance metrics used to retrieve examples from non- non-parametric datastores, thereby improving LM performance. Specifically, we propose simple-yet-ee yefffeectteffecttve approach that can easily be applicd to non non-parametric LMs: we use different levels of structural locality to define functions that modify the contextual distance metrics used by the non-parametric module.
Java programming language source code, and natural language Wikipedia articles, achieving noticeable LM performance gains in both by adding just 5 & 7 parameters respectively. Moreover, we perform an in-depth analysis showing how the traditionally used contextual similarity metrics alone are not enough to grasp the locality structure, providing evidence for why adding the locality features is indeed useful. We also compare programming languages and natural languages highlight several interesting differences in terms of how, and how much, the locality helps improve LM performance.
We evaluate our method on two drastically different domains:
2 NON-PARAMETRIC LANGUAGE MODELS
Given linguistic context consisting of sequence of tokens q. (wi,-..W(-1) autoregressive parametric LMS estimate p(wy|ct f). the probability distribution over the next token wy- Such parametric LMs store information regarding the language being modeled in the parameters 0. The size of 0 is fixed in advance based on the hyperparameters of the model architecture, in recent years typically neural network (Grave et al. 2016 Baevski & Auli 2018 Dai et al. 2019 Brown et al. 2020). In contrast, architecture, but also by the underlying data used to train the model. While non non-parametric LMs using Bayesian statisties have existed for some time (Wood et al. 2011 Shareghi et al.) 2017 He al. 2020), they have recently seen increased prevalence through the introduction of neural L.Ms that retrieve relevant examples from external datastore (Hashimoto et al. [0188] Guu et al., 2018). In particular, we focus on kNN-LMs (Khandelwal et al.) (002)). a variety of such models that uses a nearest neighbor retrieval mechanism to augment pre-trained parametric LM, achieving impressive results without any additional training.
parametrii LM number of parameters is not determined by just the model
Neural network- based LMs usually map the context a fixed-length vector representation, with trained function f (c). In kNN-LMs, the non-parametri component consists of a collection (D) of contexts for the KNN to retrieve from. Denoting these contexts and their corresponding next token as
2

---

Published as a conference paper at ICLR 2022
Table Locality features designed for each data type according to domain knowledge.
Locality
Wikipedia text
Java projects
lo
different article category, different section title
different project
same article category, different section title
same project, different subdirectory same subdirectory
12
same section title, different article category
ls
same section title, same article category
(ci, w;) E DD we create datastore (K, V) ((ki, v:)}, which contains key-value pairs:
(K. = {(f (c)) wx) (G,, m04) D}
During inference, the parametric component of the LM generates the output distribution over next tokens PL.M (w, (4; () and the corresponding context representation f(x)). given the test input context Ct. Then the non-parametric component of the LM queries the datastore with f fcx) representation to retrieve its k-nearest neighbors. .N' according to distance function d(-,)) -). We can then compute probability distribution over these neighbors using the softmax of their negative distances. The model aggregates the probability mass for each vocabulary item across all its occurrences in the retrieved targets. This distribution is then interpolated with the parametric LM distribution PLM to produce the final KNN-LM distribution:
PANN(WelC))
Σ 1w exp(-d(ks,,))) f(a)))
p(welo;; 0) (weln( + A)PLM cx;
(3)
In our experiments, we follow Khandelwal al. (2020) in setting the interpolation factor À to 0.25.
3 DEFINING STRUCTURAL LOCALITY
We define structural locality categorical feature calculated between pair of contexts (c,, Cj) in a collection of data, that describes whether the pair share some common, potentially hierarchical, attributes (e.g., the section title of a Wikipedia article section, or the directory path of source code file). For each domain, a set of hierarchical attributes (lg. 41, ..., 4 can be defined based on prior knowledge of the domain. We denote (4 cÿ) E {0, 1} the boolean locality feature value for the context pair, representing whether 6; and Cj share the same hierarchical attributes 42. Here, lo is reserved for "no locality",, in we set constraint that Σx k 4x (C;, Cj) 1, as new features can be introduced by conjunction and negation of the attributes if needed.
the pair shares none of the attributes. Without loss of generality,
Specific Instantiations. We instantiate these features our case studies of Wikipedia text and Java source code, as summarized in Table
In Wikipedia, for every context cj we define four mutually exclusive hierarchical attributes, la- We calculate these features based on the Wikipedia article and section titles, using simple pattern matching. We then link each article to set of categories (one article may belong to multiple categories) using the knowledge graph WikiData by aggregating all the category entities involving two properties: P31 (instance of) and P279 (subclass of). The criterion for "same section title" is exact string match (Hayashi et al. 2020). If there is at least one common category between the sets of categories for two articles, the pair assigned the "same article category""
For Java source code, we define 3 mutually exclusive attributes, to 12 based on the location of the code. For each source file, we use the full file path to obtain the two attributes: project name and sub-directory path The criterion for both "same project" and "same subdirectory" is exact string match. Note that these features are strictly hierarchical, hence only two features are used to capture specific locality here.
An Aside: Connections to Domain Adaptation. Domain adaptation typically refers to reusing existing information about a given problem (e.g., data or model) to solve a task a new domain.
https::// wikidata org/
Forr example, full ..o/rnualll httpp//aa......///a///////////// Journal. and sub-directory src//main//jwww/jjuraaa///// for package journal. io. ipi.
java has project
3

---

Published as a conference paper at ICLR 2022
Domain adaptation for neural models generally focuses on fine-tuning models in-domain data (Sen nrich et al. 2016, Chu et al. (017)) or making direct modifications to the model to consider domain information (Britz et al. (217)) latent topic features (Khudanpur & Wu 2000 Mikolov & Zweig 2012, Wang & Cho 2016). Most of these methods do not natively support new test-time contexts that seen training time. In comparison, one immediate advantage of non- con-parametric LMs is the
ability to adapt to different domains at test time without re-training (Merity et al., 2016 Grave et al. 2016 20177 Khandelwal al. 2020). For example, some adaptive LMs (Grave et al. 2016] 2017)
make use of the previous hidden states of test documents dynamically during inference. Similarly, our proposed locality features do not require re-training on the training set.
Note that within the scope of this paper, although connected, the proposed structural locality is different concept from domain. We consider domains as higher-level classifications describing the text where one example helongs to one domain label; e.g., a section about Kim Kardashian's 's early life belongs to a category texts describing celebrities. One the other hand, with the structural locality, a user could define multiple levels of locality: to that same section, we can assign not only the domain label, but also, the section title "Early Life". The lightweight nature of our model combined with non-parametric LMs also makes adding more levels of features straightforward, as the features only need to be calculated for the top nearest neighbors, and the number parameters that need tuning in our proposed method (Section 5 is only about twice the number of locality features.
STRUCTURAL LOCALITY AND NEAREST NEIGHBORS
In this section, we examine the relationship between distances derived from neural LM features d(f(c), f(c)), structural locality features [(,, ct). and the accuracy of the next-word prediction w;- Specifically, the underlying assumption of the KNN-LM is that less distant contexts will be more likely to accurately predict the next word Wy, We would like to test whether this correlation between distance di-) holds uniformly across different locality levels I(-). if locality provides additional information indicative of whether a particular context is useful for predicting wi beyond just that provided by the neural representations.
Data. We use two different corpora from different domains to examine this question.
WIKITEXT- 1 0zF] is a standard language modeling benchmark (Merity et al. 2016) consisting of natural language text from English Wikipedia. It contains a 250K token, word-level vocabulary, with 103M tokens in the training set and 250K tokens in both the validation and test sets.
JAVA GITHIUE is programming language corpus containing Java source code from Github (Allama nis & Sutton 2013) that is widely used in source code modeling (Hellendoorn & Devanbu 2017] Karampatsis al. 2020). It contains 1.44B tokens from 13,362 projects in the training split, 3.83M tokens from 36 projects in the validation split and 5.33M tokens from 38 projects in the test split. The splits are separated by whole projects. The dataset is tokenized with byte-pair encoding (Sennrich
ct al. 2015) using the vocabulary from Karampatsis et al. (2020) with 2,000 subtokens.
Base Model. As the neural model used to calculate context features, we follow Khandelwal et al. (2020)) train an LM with the exact architecture and optimization described by Baevski & Auli 20188: : a decoder-only Transformer (Vaswani et al. 2017). with 1024 dimensional hidden states the WIKITEXT- 103 dataset and 5 122 for JAVA GITHUB. We set the number of retrieved nearest neighbors to be analyzed to 1024, and the distance metric to l following the default.
To capture the effect of our proposed locality features, the datastore should ideally be both closely related to the test examples, sufficiently large to ensure precise kNN retrieval performance for a wide range of contexts, and not too sparse in terms of the prevalence of locality features.
Datastore.
For WIKITEXT-ION 103, we include the training set, as well as the validation/test set (excluding the text currently being evaluated) in the datastore. For the JAVA GITHUB, due to the relatively large size of the validation/test set, and the unwieldy size of the training set, we include only the validation/test set (also excluding the current file).
httpss///ennddoor//reeeao////sss http:://giihub..ccmuurvaaaiii//i
4

---

In the Java source code domain (Figure 26). we generally observe that the retrieval accuracy is much higher than that in the Wikipedia domain, suggesting that the kNN is doing a better job retrieving relevant contexts. This is largely due to higher repetitiveness of source code (Hindle et al. 2016); as we show later, the base Transformer model also performs much better here than on natural language text (Section 6.2). We also observe more pronounced locality effect here: at the same distances close to and at the same rank, neighbors that are local to the current context have far higher accuracy, can Published as a conference paper at ICLR 2022
2.9
9.6
0.5
-100
0.7
-105
same Gatgerry
category
0.5
catngory
Nap Disance
0.5
-113
-1200
0.4-
125
0.3-
-13.
9.2
0.2
-135
0.3
-15.0
-12.5
-10.0
-75
-50
-25
0.0
50
1.00
150
200
0
50
100 Rank.
150
200
Nog. Bizance
Pank
(a) WIKITEXT- 103
1.0
-50
2.90
Incllty
3.9
-120
project
2.65
-130
0.80
0.75
Berg
-250
3.6
0.70
-300
0.65
-350
0.5
400
-200
-200
-100
0
30
1.00
150
200
50
120
150
200
Keg. Distance
Renc
Park
(b) JAVA GITHUB
Figure 2: The relationship between nearest neighbor rank, negative distance, and the retrieval accuracy. grouped by different locality levels. Only top 200 nearest neighbors are shown for clarity. Negative distance on x-axis represents the upper bound of the bin.
Analysis. Consider & nearest neighbor contexts Ni fcrlr L...k) retrieved for any test context op in the test set C, ordered by the ascending distance: Vr d(cr, ot) < d(cr41, ct). We define r E [1, k] as the "rank" for the retrieved context c.- To study the quality of the retrieved contexts, we calculate the number of correctly retrieved tokens, defined as # #w, = Wigu } across C.
We plot in Figure from left to right: (1) Negative distances (-d(er,c))le E NN, E C} grouped into bins, the retrieval accuracy of the bin avg(# (w., wema))). (2) Rank vs. the retrieval accuracy at rank r, avg(# [ww, w)) (3) Rank
the average negative distance aog(-d(c,, ct)) at rank r. All of the plots are grouped by different locality levels lo to In
Naturally, the lost sub-figures reflect that the lower the (negative) distance, the lower the accuracy on both datasets. Yet, interesting, the Wikipedia domain (Figure 2ap, the negative distance gets close to (perfect match). the retrieval accuracy for the next word does not always increase; the accuracy values in this range have very high variance and all 4 levels of locality show clear trend. This partly indicates that context-basee distance is imperfect, regardless of locality. Even so, slightly lower distances, the trends stabilize and largely show a consistent picture: more specific locality features, especially those involving the same category (1,8)))) yield better predictions than the locality-insensitie component for identical distances. This is especially significant at higher ranked retrievals (middle sub-figure), where contexts that share the same section title and the same article category are substantially more likely to share the same completion. This suggests that the proposed locality features are not fully represented by, or correlated with the original distance metric, and thus implies that there room for improvement by incorporating these features.
indicating usefulness of locality features in the source code domain well. However,
5

---

Published as a conference paper at ICLR 2022
from the (right-most) plot of rank versus the negative distance, the average distances of the neighbors with higher locality levels are also significantly smaller than the distance of those without locality, This suggests that the distance in the Java source code domain already correlates well with the level of locality, which may render incorporating locality features less beneficial. We study the precise benefit under instantiation of this model next.
5 INCORPORATING STRUCTURAL LOCALITY IN NON-PARAMETRIG LMS
Now that we have demonstrated that locality is additionally indicative of next-word prediction accuracy beyond context distance, we propose a method to incorporate this information into the non- parametric retrieval module. In the case of KNN-LMs (Section D. recall that PŁNN is calculated based on the softmax of the negative distance -d(((c))) [c+)). Assuming locality features {lo, 4,, (n for each pair (C;, 6q) consisting the retrieved nearest neighbor and the current inference context ct. we modify the formulation of PKNN (Equation 3)
to consider these features as below:
(w, cas {0n})
Σ PKN
Twi=,, exp(- cz (0,)))
(4)
O(ki, cz; (0x}) = 9n (d(ks,, [(e)); (c) =1
(5)
where 9a (d((:,)): 0%)) is a learnable function of the distance of the nearest neighbors, with parameter 8n for each type of locality feature L,, One can view function 9()) as "modified" distance for nearest neighbors after taking locality information into consideration. In our experiments, we adopt a linear form of g()):
(6) We omit the bias for 9v(-) by setting by = to remove free parameter from the model and potentially make optimization easier 0 To learn these functions, a user needs to provide just a small sample of annotated data in the same domain, as there are only 2n + 1 parameters to optimize. In our experiments, we use the validation split for optimization. The parameters are trained to minimize the negative log- log-liielihood of the kNN prediction of the gold token:
In. (d(, wn. bw.) = w.,d(--) b,
arg min log PLNN (w,, (0.)
uizata Oe (0.))
To optimize the parameters, we use the Adam (Kingma & Ba 2014) optimizer with a learning rate of 0.0001 on the validation set for 200 epochs. It converges within 20 minutes for both datasets.
6 How DOES STRUCTURAL LOCALITY IMPROVE LANGUAGE MODELING?
6.1 EXPERIMENTAL SETUP
Baselines. Since we base our model on kNN-LMs, this model will be our most directly comparable baseline. We also compare our model to the underlying parametric LM (Baevski & Auli (018). without the kNN module. For the JAVA GITHUB dataset, we additionally compare to the recent state-of-the-ar model from Karampatsis al. (2020) on code language modeling, which uses BPE and LSTMs. In all experiments, the maximum number of tokens per input sample is 3,072.
Evaluation. We evaluate the performance of the LM with the standard perplexity metric and token prediction top-k accuracy on the held-out data] The top-k accuracy is calculated by checking the ground truth token is among the predicted top-k list. This metric, primarily for & E {1,5} (with more & values in Appendix (A.)). is commonly used to evaluate predictive models of source code (Hindle et al. 2016). In order to more easily incorporate and analyze the locality features, and also following Karampatsis et al. (2020), we split the evaluation dataset into independent test examples to evaluate, where each of the example is an atomic unit in the locality hierarchy. For JAVA GITHIUB each test example is a source code file, and for WIKITEXT- 103, each example is an article section
We also experimented with an adaptive variant that conditioned the weights and biases (f ((w,). (bx,) on the current context representation f(()) parameterized by MLP. However, this did not result in significant improvement over directly optimizing w and b (Appendix A.3).
For JAVA GITHUB, the perplexity is calculated full tokens by aggregating the likelihood of subtokens. The accuracy calculated that all subtokens in full token have to he predicted correctly.
'Note that hecause predict WIKITEXT- 103 setioon-y--eectinn instead of article-by-articl the perplexity numbers reported here are somewhat worse than other works. Article-by-article calculation is not inherently

---

Published as a conference paper at ICLR 2022
Table 2: Perplexity and top-k token prediction accuracy results on two datasets. *Uses released pre-trained model, 'oo stochastic training, for all others stddev < 0.01 for 5 runs.
Rel. Gain
Top-1 Acc. (Rel. Err. Red.)
Top-5 Acc.
Dataset
Model
Dev PPI.
Test PPL.
(Rel. Err. Red.)
Transformer'
223.31
223.73
39.0%
(-)
64.0%
(-)
WIKITEXT
-103
+NNN2
120.21
19.994
16.0%
41.3%
(3.79%
66.8%
(7.91%) 1
+NNN + locality
19.51
19.16
3,9%
43.2% %
(3.29%)
68.0%
(3.56%)
BPF LSTM3
*5.27
JAVA GITHUB
Transformer
3.29
3.07
41.7%
75.6%
(-)
87.6%
(-)
+NNN
22.43
22.18
29.0%
83.9%
(34.0%)
96.0%
(67.9%)
+KNN + locality
2.37
2.13
2.3%
84.7 %
(4.91%)
96.6% %
(15.0%)
Baevski & Auli 2
Khandelwal ct al. (2020),
Karampatsis al. (2020)
6.2 RESULTS
The high-level results are shown in Table 2 At first glance, we can already see that the two datasets vary greatly in predictability. With a similar Transformer architecture, performance on JAVA GITHUB much better than on the WIKITEXT-I0S across the board, partly due to the rigid nature of programming language syntax. With Transformer model, we achieved strong sfate-of-the- art language model on Java code, with low perplexity and very high prediction accuracy (~75%).
By adding kNN module onto the Transformer- based LMs, perplexity and accuracy in both domains improves by a large margin. This is expected and in line with previous experiments on KNN- LMs (Khandelwal et al. 2020). The Wikipedia domain enjoys less relative improvement in perplexity (16%) than the Java source code domain (29%). This is particularly interesting, considering that the datastore used for WIKITEXT-I01 103 contains both the current held-out split and the training data (~ contexts), compared to that for JAVA GITHUB with only the current held-out split (~5M contexts). This reflects the fact that source code known to benefit strongly from project- and package-specific locality (Tu et al. 2014 Hellendoorn & revanbu,2017
Table 3: Learned parameters lo, (0,) for each locality level and a non-local level go-
Adding proposed locality features and finetuning the pa- rameters on the validation set improves the performance further on both datasets, albeit with a smaller relative gain. This confirms our hypothesis that incorporating locality into the non-parametric retrieval- We also see that locality features in the Wikipedia domain result in fairly consistent gains, while the Java source code domain sees especially strong accuracy improvements. This echoes our analysis of the source code corpus in Section 4 where we found that distance was generally strongly correlated with accuracy, but that locality was particularly informative at low distances. There, it may help discriminate between top-ranked completion candidates (as also shown later in Tab.
WIKITEXT- 103
JAVA GITHUB w
LMs is beneficial.
w
9o
1.233
0.022
91
1.246
-1.087
0.033
-3.627
1.288
-1.250
0.041
-5,920
93
1.285
-1.464
4. It is notable that despite the fact that the perplexity and accuracy on JAVA GITHUB are already very strong with the vanilla Transformer, we still see a noticeable relative error reduction of 4.9% by adding locality levels information.
We next study how locality features guide towards a "better" distance distribution among nearest neighbors. We plot the relationship between the nearest neighbor ranks and "modified" distance g(k,, in F Table the specific learned parameters for each level of g(:-). Evidently, the biases and weights vary accordingly with locality levels, as the model tries to "correct" the original distance by emphasizing more local contexts. Compared with the original negative distance -d(k; fc:)) depicted in Figure 2 the negative modified distance is more separated between the different locality levels on either dataset, showing the relative importance of different locality more clearly. We analyze several alternative approaches to parameterizing locality in Appendix A.3
For WIKITEXT- 1 103, comparing Figure Ba with Figure 2a we can see that with the original distance different localities cluster together, and the modified distance separates them much better. We can also
incompatible with our proposed method, but it would require additional implementation to use different locality features for different locations in the output. Hence, we used section-by-section calculation for expediency.
7

---

Published as a conference paper at ICLR 2022
localty
localty lsality
callegoyy, category
Mep dideece (Mood
came soct same Gatogory
Mep. Dittncce thootree
-14
-15
-16-
100 125
150
200
50
75
100
125
150
(a) WIKITEXT-108
(b) JAVA GITHUB
Figure 3: The relationship between nearest neighbor rank and the "modified" negative distance -9 guided by our proposed locality features, grouped by different locality levels. Similarly to Figure 2
only top 200 nearest neighbors are shown for clarity.
see that if two contexts have the same article category and the same section title, then their distance on average is the closest, closely followed by those sharing article categories only. On the other hand, contexts that only share section titles are not as closely related. This is intuitively reasonable; the education section for computer scientist and musician can be very different in content, even if sharing some commonalities, like the phrases used to describe courses, grades, school locations, etc. This also underscores the usefulness of explicit locality features in providing interpretable insights into the relevance of domain knowledge.
For JAVA GITHUB, comparing Figure 3b with Figure 2b we can see that the original distance is already more separated between different locality levels than that of WIKITEXT- 103, again suggesting better learned representations (in terms of locality sensitivity) for the Java domain. However, the model still benefits somewhat from the contexts that are under the same subdirectory (more so than just the same project), especially for top nearest neighbors: the gap for ranks higher than is more pronounced with the modified distance. This again verifies our hypothesis about the hierarchical nature of structural locality. deployed in a code editor, one could obtain representations of the files in the same sub-directory as the current file and use them, along with the proposed locality features, to bias auto-complete results.
also indicates potential practical applications - if this model were
Table 4 shows randomly sampled test context from each domain where PaNN for the gold token increases after using locality features. We can see that the nearest neighbor search using context representations performs reasonably well at capturing patterns and themed phrases, especially closer to the last token, finding two very similarly rated candidates. However, in both examples, the second retrieved candidate has wrong target token. Informed by locality features in the WIKITEXT- 103 example, a matching section and category for the first candidate - the more "local" context enjoys large boost in probability, while the non-local one's decreases slightly. We present additional examples in Appendix A.1 The JAVA example demonstrates the same effect; the second retrieved example shows resemblances in variable name and template structures, but the fact that the project focused on Google API rather than Twitter API makes the original retrieval undesirable.
7 CONCLUSION
In this paper, we propose a nove method of incorporating structural locality into non-parametric LMs that reference retrieved examples from a datastore. We evaluate this approach in both a natural language and programming language domain, and empirically explore the similarities and differences of how structural locality affects LMs in these settings. The improvement in perplexity and prediction
Previous work (Hellendoorn & Devanbu 2017) made the observation that source code files from the same GitHub repository or sub-directory tend to be relatively similar, but did not include empirical analysis of this effect. Rather, their observation was backed up by improved performance their n-gram language model with multiple tiered caches. Our work gives more fine-grad grained insights into this phenomenon, expands the applicability to neural models and new domains, and proposes a more generalized formulation for encoding multiple localities across multiple domains. See Appendix A.4 for detailed discussion of the connection to previous work and novelty.
8

---

Published as a conference paper at ICLR 2022
Table Examples from two domains where incorporating locality features (non-local, local) lead to significant increase in the cumulative PLNN for the gold token, with corresponding change in probability (normalized negative distance) for two nearest neighbors.
Test Target
Initial
A log PINN
Test Context
log PaNs
Seasonal forecasts; Category: Pacific typhoon season The forecast indicated the potential for 26.2 tropical storms, compared to the 10- and ye-r average of 27.8 and 26.3 storms, respectively. The following month, the group raised their..
Section:
forecast
-2.20
+0.89
Datastore
Orig. Log-Prob.
ALog-
Datastore Context
Target
Prob.
Seasonal forecasts; Category: Pacific typhoon season Their main reasons behind this is due to weaker trude force winds occurring many parts of basin, there would be an enhanced cyclonic vorticity over the northwestern part of the Pacific. On April 27, the GCACIC made their first...
Section:
forecast
-2.91
+1.25
Section: Earthquake; Category: earthquake Nickson Sioni from Simbo came on the (HF) radio and announced the arrival of a huge wave that had washed away several houses and come inland about 200m. This information was possed on by telephone the Hawaii-hased Pacific Tsunami Warning Center who then upgraded their ...
warning
-3.01
-0.31
Test
Initial
A log PANN
Test Context
Target
log PaNs
Directory: w...aadoidliviieer///mCCCnaaaaat java; Project: twitterdroid public static final String CONSUMER_SECRET "YOUR_CONSUMER__S" public static final String REQUEST_URE "http://wwN.
twitter
-2.03
+0.49
Datastore
Orig. Log-Prob.
ALog-
Datastore Context
Target
Prob.
Directory: ww.ffiitee/VviteerConneiiioonnni public static final String FRIENDS_ CIMELDDS_TIMLLIEEEUE
Project: twitterdroid
twitter
-1.99
+0.17
"http://apii httt:://pp.twiitter.... wtw.tttee../////taattttttteoeoee wtt./////tatuses///eeeoss
lerriiienndssiiiiiiiieeeeee xm1";
public static final String UPDATE_UR! = "http: //api.
Directory: hiipl//AcivityTeeplat..i.
Project: spring seriing-socill-eo google googleapis
-1.87
-0.09
private static final String ACTIVITIES. PUBLIC //attivities/public""
private static final String ACTIVITIES_ "https://ww..
accuracy across both domains show the effectiveness and ubiquity of such locality information. Besides language modeling, we also envision that the method can benefit other applications that could be enhanced using user-defined prior domain knowledge such as conditional generation or representation learning using retrieved information.
Linitations. Our method applies to settings where locality effects are present, there is sufficient data to build reliable datastore for each locality level, and that locality is not already meaningfully captured by the model. While this may not apply to every domain, these features are common: besides source code & Wikipedia, domains including books (features: authorship & dewey decimal system information), research papers (venue, research area), product manuals (kind, sections), and online discussions (time, topic) are all plausible candidates. The features our studied domains were selected based on availability and prior knowledge of the domain (c.g., for Java, Hellendoom & Devanbu (2017)) While they did provide measurable improvements and were natural to interpret, these may not be the optimal choice, and other options are worth investigating. It is also possible that LM improvements will eventually lead to learned context representations that almost perfectly capture the relevant locality information. However, we believe this to be unlikely: in many practical settings, there is some inherent ambiguity in partial contexts that cannot be solved with the surface text only. For instance, in Java source code files, it common declare package, which will obviously match perfectly based on the first few tokens (c.g., package org.) with many other contexts. Yet given the scoped nature of this declaration, locally retrieved continuations inherently far more useful.

---

Published as a conference paper at ICLR 2022
ACKNOW
We thank Uri Alon for the helpful discussions and thorough feedback. We also thank the reviewers for the helpful conversations during the revision period of the paper. This work was supported in part by the National Science Foundation under Grant #1815287, and a gift from Amazon AWS.
ETHICS STATEMENT
There are several ethical considerations regarding proposed method. First, while language models have a large variety of positive uses in generating natural language et 202T) or source code (Allamanis et al. 2018), there is also potential for dual For example, previous work has cited the potential to generate fake news (Zellers et al.) 2019) or undesirableedeffaattry content (Wallace) al., 2019). Our methodology improves the accuracy of language models, which has the potential to increase their applicability not only in positive use cases but also in ethically questionable scenarios. In order mitigate these risks, methods detect machine generated content may be employed. although these are not perfect remedies (Zellers et al. 2019).
Second, because our methodology explicitly references the training corpus in generation it may increase the likelihood of copying content more-or-less verbatim from the training text. This raises potential issues of copyright violation (Chen al. 2021) or privacy violation (Carlini et al. (021). However, at the same time, because non non-paraettric models increase traceability through direct references to the training corpus, it also provides tool identify the provenance of the original content, providing tool to identify such verhatim copying compared to standard parametric models.
Finally, there has been much recent interest in the energy and environmental impact of large language models (Strubell et al.) 2019). Due to the necessity to look up information in datastore, non- parametric models have additional computational overhead compared to parametric models. However, at the same time, noted by Khandelwal et al. (2020), non ao--aaametric models also provide tool for quickly adapting to new domains through the use of Nomain-specinn datastores, obviating the necessity for domain-specific fine-tuning. Our work takes this step further, allowing models to leverage locality of the datastores, potentially making this an even more attractive alternative for efficient adaptation.
REPRODUCIBILITY STATEMENT
The source code package containing a README document on how to reproduce the results and analysis and experiment scripts is available in the paper's supplementary material. The details about the dataset used, model hyper-parameters, and analysis performed are described in Section 4 and single machine with 48 core CPU and NVIDIA V100 32GB GPU. For WIKITEXT- 103 we use the pretrained model provided by (Khandelwal et al. 2020) for fair comparison. For JAVA GITHUB the Transformer model trained until it converges, requiring approximately days. The datastore size is about 5GB for JAVA GITHUB and 351 GB for WiKITEXT-103 103.
Section 6. I All experiments are conducted
REFERENCES
Miltiadis Allamanis and Charles Sutton. Mining source code repositories at massive scale using language modeling. In 2013 10th Working Conference on Mining Software Repositories (MSR), pp. 207-216. IEEE, 2013.
Miltiadis Allamanis, Earl Barr, Premkumar Devanbu, and Charles Sutton. A survey of machine learning for big code and naturalness. ACM Computing Surveys (CSUR), 51(4):1-37 2018.
Uri Alon, Roy Sadaka, Omer Levy, and Eran Yahav. Structural language models of code. In International Conference on Machine Learning, pp. 245-256. PMLR, 2020.
Alexei Baevski and Michael Auli. Adaptive input representations for neural language modeling. 2018
arXiv preprint /
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. I Proceedings ICLR, 2015.
10

---

Published as a conference paper at ICLR 2022
Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Jauvin. A neural probabilistic language model. Journal of machine learning research, 3(Fcb):1137-I11) 2003.
Denny Britz, Quoe Le, and Reid Pryzant. Effective domain mixing for neural machine translation. In Proceedings of the Second Conference Machine Translation, pp. 118-126, 2017.
Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 2020.
Nicholas Carlini, Florian Tramèr, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voos Katherine
Lee, Adam Roberts, Tom Brown, Dawn Song, Ülfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. In USENIX Security Symposium, 2021.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde, Jared Kaplan, Harri Edwards, Yura Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107. 107.03374, 2021.
Chenhui Chu, Raj Dabre, and Sadao Kurohashi. An empirical comparison of domain adaptation methods for neural machine translation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume Short Papers), pp. 385-391, 2017.
Zihang Dai, Zhilin Yang, Yiming Yang. Jaime G Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transformer-XL. XL: Attentive language models beyond fixed-length context. In Proceedings of ACL, 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT:
Pre-training of deep
bidirectional transformers for language understanding. arXiv preprint arXiv: /8 180.00000 2018.
Edouard Grave, Armand Joulin, and Nicolas Usunier. Improving neural language models with continuous cache. arXiv preprint arXiv: 0404224 2016.
Edouard Grave, Moustapha Cissé, and Armand Joulin. Unbounded cache model for online language modeling with open vocabulary. arXiv preprint 17 2017.
Kelvin Guu, Tatsunori B Hashimoto. Yonatan Oren, and Percy Liang. Generating sentences by editing prototypes. Transactions of the Association for Computational Linguistics, 6:437-450, 2018.
Tatsunori B Hashimoto, Kelvin Guu, Yonatan Oren, and Percy S Liang. A retrieve-and-edee framework for predicting structured outputs. Proceedings of NeurIPS, 2018
Hiroaki Hayashi, Zecong Hu, Chenyan Xiong, and Graham Neubig. Latent relation language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 791 1911-7918, 2020.
Junxian He, Taylor Berg- Kirg-Kiik,,,,,ck, and Graham Neubig. Learning sparse prototypes for text generation. arXiv preprint arXiv:2006.16336 2020.
Vincent Hellendoorn and Premkumar Devanbu. Are deep neural networks the best choice for modeling source code? In Proceedings of the 2017 I 11th Joint Meeting on Foundations of Software Engineering. pp. 763-773, 2017.
Abram Hindle, Earl T Barr, Mark Gabel, Zhendong Su, and Premkumar Devanbu. On the naturalness of software. Communications of the ACM, 122-111 2016.
Rafael-Michael Karampatsis, Hlib Babii, Romain Robbes, Charles Sutton, and Andrea Janes. Big code!= big vocabulary: Open-vocabulary models for source code. In 2020 IEEE/ACM 42nd International Conference on Software Engineering (ICSE), pp. 1073-1085. IEBE, 2020.
Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. Generalization through memorization: Nearest neighbor language models. In Proceedings of ICLR, 2020.
Sanjeev Khudanpur and Jun Wu. Maximum entropy techniques for exploiting syntactic, semantic and collocational dependencies in language modeling. Computer Speech & Language, 14(4):355-372, 2000.
11

---

Published as a conference paper at ICLR 2022
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Junyi Li, Tianyi Tang, Wayne Xin Zhao, and Ji-Rong Wen. Pretrained language models for text generation: A survey. arXiv preprint arXiv:210S.10311, 2021.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprini arXiv: 1692, 2019.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprini urXiv:/609007888 2016.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. In Proceedings of ICLR, 2018.
Tomas Mikolov and Geoffrey Zweig. Context dependent recurrent neural network language model. In 2012 IEEE Spoken Language Technology Workshop (SLT), pp. 234-239. IEEE, 2012.
Tomáš Mikolov, Martin Karafiát, Lukáš Burget, Jan Černocký, and Sanjeev Khudanpur. Recurrent neural network based language model. In Eleventh annual conference of the international speech communication association, 2010.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with unified text-to-text transformer. arXiv preprint 1r1iv: 10683, 2019.
Veselin Raychev, Martin Vechev, and Eran Yahav. Code completion with statistical language models. P Programming Language Design and
In Proceedings of the 35th ACM SIGPLAN Conference on Implementation, pp. 419-428, 2014.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. arXiv preprint arXiv:1508.07900 2015.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Controlling politeness in neural machine translation via side constraints. Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 35 40, 2016.
Ehsan Shareghi, Gholamreza Haffari, and Trevor Cohn. Compressed nonparametric language modelling. In IJCAI, pp. 2701-2707, 2017.
Alessandro Sordoni, Michel Galley, Michael Auli, Chris Brockett, Yangfeng Ji, Margaret Mitchell, Jian-Yun Nie, Jianfeng Gao, and Bill Dolan. neural network approach to context-sensitive generation of conversational responses. In Proceedings of NAACL, 2015.
Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning in nlp. arXiv preprint urXiv:1906.022: 2019.
Zhaopeng Tu, Zhendong Su, and Premkumar Devanbu. On the localness software. Proceedings of the 22nd ACM SIGSOFT International Symposium Foundations of Software Engineering, pp. 269-280, 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of NeurIPS, 2017.
Eric Wallace, Shi Feng, Nikhil Kandpal, Matt Gardner, and Sameer Singh. Universal adversarial triggers for attacking and analyzing nlp. arXiv preprint arXiv:1908.077 2019.
Tian Wang and Kyunghyun Cho. Larger-contex: language modelling with recurrent neural network. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1319-1329, 2016.
12

---

Published as a conference paper at ICLR 2022
Frank Wood, Jan Gasthaus, Cédric Archambeau, Lancelot James, and Yee Whye Teh. The sequence memoizer. Communications of the ACM, 54(2)911-98, 2011.
Zhilin Yang, Zihang Dai, Yiming Yang. Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. XLNet: Generalized autoregressive pretraining for language understanding. In Proceedings of NeurIPS, 2019.
Rowan Zellers, Ari Holtzman, Hannah Rashkin, Yonatan Bisk, Ali Farhadi, Franziska Roesner, and Yejin Choi. Defending against neural fake news. In Advances in Neural Information Processing Systems, pp. 9051-9062, 2019.
13

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1 ADDITIONAL EXAMPLES
We provide additional examples on WIKITEXT- 103 in T
Test
Initial log PaNs
A log PANN
Test Context
Target
Section: Design; Category: ship class In effort to outmatch the American New York class, planners called for ship armed with twelve 14-inch em) guns and faster than the knots (39 km/h; 24 mpht of their rivals. Vickers files show that the Japanese had access to the designs for double- and triple- gun turrets, yet opted for six double turrets over four triple nurrets. The final design designated A-64 by the IN-called for
displacement
-2.54
+1.09
Datastore Target
Orig. Log-Prob.
ALog Prob.
Datastore Context
Design; Category: ship class Both ships also given torpedo bulges improve their underwater protection and compensate for the weight of the additional armour. addition, their sterns were lengthened by 7.62 metres (25 ft). These changes increased their overall length to 2 1.3.8 metres (701 ft), their beam to 31.75 metres (104 2 in) and their draft 9.45 metres (31 ft). Their..
Section:
displacement
-3.25
+1.23
Section: History: Category: gun mount The British Admiralty ordered a protolype of Coles's patented design in 1859, which installed the ironclad floating buttery, HMS Trusty, for trials 1861, becoming the first warship to be fitted with a revolving gun uurret. Coles's 's aim was to create a
ship
-2.98
-0.24
Test Target
Initial log Paow
A
Test Context
log PNNN
Section: La Venta: Category: colossal statue When discovered was half- buried; its massive size meant that the discoverers were unable to excavate it completely. Matthew Stirling fully excavated the monument 1940, after clearing the thick vegetation that had covered it in the intervening years. Monument has been
moved
-2.97
+1.22
Datastore Target
Orig. Log-Prob.
ALgg Proh.
Datastore Context
San Lorenzo; Category: colossal statue The sculpture suffered some mutilation antiquity, with nine pits hollowed into the face and headdress. San Lorenzo Colossal Head 10 (also known as Lorenzo Monument 89) has been...
Section:
moved
4.18
+1.36
Section: San Lorenzo; Category: castle The excavations investigated the north of the fortress, searching for an entrance postulated by architect Eugene Viollet-le-Duc; but no such entrance was found. However, the excavation did reveal was that there castle to enable the use of guns. Typologically, structure has been
dated
-4.63
-0.11
addition to the north the
Table 5: Additional WIKITEXT- 1 103 examples where incorporating locality features (non-local, local) lead significant increase in the cumulative PLNN for the gold token, with corresponding change in probability (normalized negative distance) for two nearest neighbors.
A.2 ADDITIONAL RESULTS ON TOKEN PREDICTION ACCURACY
We show additional results on top-k (k 10, 20) accuracy and relative error reduction (RER) on two datasets in Table K
A.3 ALTERNATIVE FORMULATIONS TO LEARN PARAMETERS FOR LOCALITY FEATURES An alternative way to incorporate locality features into the model is an adaptive variant that conditions the weights and biases (fw,), (b.) in Equation 6) the current context representation f(a)
14

---

this in Published as a conference paper at ICLR 2022
Table 6: Additional token prediction top-k (k 10, 20) accuracy results and relative error reduction (RER) on two datasets.
Dataset
Model
Top-10
RER
Top-20
RER
Transformer
72.0%
78.9%
WIKITEXT- 103
+NNN
74.6%
9.29%
81.0%
9.98%
+NNN locality feat.
74.9%
1.30%
81.1 %
0.84%
Transformer
89.5%
90.8%
JAVA GITHUB
+NNN
97.3%
74.86%
98.2%
80.33%
+NNN locality feat.
97.9%
21.89%
98.6%
25.41%
Table 7: The perplexity results comparing alternative formulation using MLP to contextualize parameters for locality features on two datasets.
Dataset
Model
Dev PPL
Test
Transformer
23.31
23.73
+KNN
20.21
19.94
WIKITEXT- 103
+NNN + locality (MLP contextualized)
20.11
19.92
+KNN + locality (direct)
19.51
19.16
Transformer
3.29
3.07
+NNN
2.43
2.18
JAVA GITHUB
+NNN + locality (MLP contextualized)
2.47
2.20
+NNN + locality (direct)
2.37
2.13
parameterized by a MLP:
[Wo
Wn
b
bn MLP(f(ce)
(8)
In our experiments, used two-layer MLP with ReLU activations, with 64 hidden units and 0.3 dropout rate during training. The perplexity results compared with directly optimizing weights and biases (fw,), ), (b,, 1) are shown in Table 7
We find that contextualizing the parameters does not result in significant improvements over directly optimizing w and b, and sometimes makes the performance even worse. This is perhaps because the context vector space is very large (512-1024 dimensions) compared to the relatively few data points from the validation set used to train.
In Section 6.2] we discuss the effect of learned parameters for each locality level. Observing that the bias terms (b:) and weights (w:) vary according to the locality levels in the learned parameters and to study the weights of the non-local level wo. we freeze all weights except for non-local weights (wsyo) o) to and only optimize bias terms and the weight for the non-local level (wy). This is to exacerbate the effect of bias different locality levels. The learned parameters shown in Table g We see similar results where the bias terms vary aggressively to modify the "distance" with different levels of locality, and the weights for the non-local level are less than lowering the importance of those non-local retrieved candidates. It's worth mentioning that for JAVA GITHUB these learned biases much larger in amplitude than before, to compensate for the small scale weights learned before (only around 0.03). However, the perplexity results on both datasets are slightly worse than the full optimization setting that we use the main experiments (19.33 vs. 19.16 WIKITEXT- 103 and 2.15 vs. 2.13 in JAVA GITHUB).
A.4 CONNECTION WITH RELATED WORK AND NOVELTY
Previous work (Hellendoom Devanbu 2017) has made the observation that source code files from the same GitHub repository or sub-directory tend to be relatively similar, but did not include an empirical analysis of this effect. Rather, their observation was backed up by an improved performance of their n-gram language model with multiple tiered caches. Our work improves number of ways, including 1. directly examining the internal representations of a neural language model, 2. demonstrating that the internal representations do not sufficiently capture structural locality
15

---

Published as a conference paper at ICLR 2022
Table 8: Learned parameters Go. } for each locality level and non-local level go. with fixed Wi>o = 1 during optimization.
WIKITEXT- 103
JAVA GITHUB
b
1.127
0.901
91
1,000
+0.385
1.000
-28. 286716
92
1.000
-0.475
1.000
-55.428
1.000
-0.726
features, 3. providing efficient ways to compensate for this disconnect, leading to improved language modeling performance, and 4. showing that this carries over to Wikipedia, which has not been previously examined in this way. As result, work both gives phenomenon and expands the applicability to neural models and new domains. In addition, our work proposes more generalized formulation for encoding multiple localities across multiple domains than the one proposed in Hellendoorn & Devanbu (2017), which treated locality as strictly nested (e.g. project + sub-directory + file). Our formulation in Eq. 5 can encode more general hierarchies, such as the lattice we used in the Wikipedia case:
fine-grained insights into this
same section & category
same section
same category
any section category
16


Reviews:
[{"review_id": "mUXNbudtnuu", "reviewer": "Reviewer_7oBt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- Authors propose a way to include structural locality into kNN-LM models\n- Authors demonstrate improvement on retrieval tasks for Wikipedia and Java source code domains\n\nWeaknesses:\n- It seems that the structural locality and its value are known and not new. The paper's contribution then is adding the structural locality to the non-parametric language models. The way to add structural locality is straightforward. It seems to me that this contribution is not significantly novel.\n- There is no comparison or discussion of other ways to add structural locality to LMs. It seems authors tried just a single approach that they present in the paper.\n- Using locality info in authors' experiments leads to minor improvement. This is not a significant weakness since there might be other tasks where locality will contribute more. However, it would have been interesting to see tasks or domains where improvement is more significant.\n\nBased on discussion with authors and clarifications provided in comments and paper itself, I have increased my score to \"marginally above acceptance threshold\".", "summary_of_the_paper": "Authors propose a way to use structural locality in language models. Authors demonstrate that the structural locality information improves results for two domains they experiment with. ", "summary_of_the_review": "In my opinion, the paper makes a minor contribution by proposing a straightforward way to add structural locality to kNN-LM models. The contribution is possibly useful, but not major. For tested tasks, structural locality information improves results but not significantly. I believe the paper is marginally below acceptance threshold.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Vi0ELPC09VJ", "reviewer": "Reviewer_gYwe", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "+ The paper is well written and easy to read\n+ What the paper is suggesting is simple, yet useful. The example depicted in Figure 1 describes their motivation as well as what they are doing effectively\n+The concept of structural locality as used in their paper is defined clearly\n+Results are compared with other state of the art models (Table 2)\n\n- The only weakness that I can identify is that the authors have used one dataset of each domain. Since there is minor improvement in the results, it is difficult to gain confidence that the results will indeed improve on other datasets as well\n\n\n\n\n", "summary_of_the_paper": "The authors propose an approach to complement context by adding 'locality' information in examples present in external stores of non-parametric language models. The locality information captures the hierarchical structure, and deems two contexts more similar (or having less distance) if they share common hierarchical structure/attributes. The authors conduct experiments on source code as well as natural language articles. They analyze the results to point out reasons for improvement, and also highlight differences between the domains.", "summary_of_the_review": "Same as above", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Hbl1CGnaSLa", "reviewer": "Reviewer_PnXs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work concerns itself about utilizing structural locality inherent in real-world datasets in improving the effectiveness of non-parametric language models. It makes a claim that a) structural locality is not implicitly fully captured by the distance metric used in non-parametric language models and further that b) explicitly plugging in structural locality into non-parametric language models can improve their effectiveness. It validates this claim first by doing analysis of two datasets with the help of custom locality functions and then by plugging in the locality functions into a non-parametric language model with the help of learnable parameters. \n\n\nPositives:\n\t1. Well stated hypothesis and analysis that shows that structural locality is not implicitly fully captured by the distance metric used in K-nearest neighbour non-parametric language model of Khandelwal et al.\n\t2. Locality features for two datasets - wikipedia and Java projects\n\t3. Incorporation of locality features in non-parametric language models using simple learnable functions of the distance metric\n\t4. Analysis that shows that incorporating locality features leads to improved distance distribution among nearest neighbours\n\nNegatives:\n\t1. Structural locality inherent in datasets need to be captured by a set of custom locality feature functions which requires prior knowledge of the domain of the datasets. \n\t2. Marginal improvements in results\n\t3. No detailed discussion of learned parameters presented in Table 3.\n\t\ta. It appears that w doesn't matter so much for all non l_0 features. So it would be interesting to set w to 1 for these features and learn only b and for l_0 learn w. \n\nIn Eqn 4. y should be w_t?\n\n", "summary_of_the_paper": "This work concerns itself about utilizing structural locality inherent in real-world datasets in improving the effectiveness of non-parametric language models. It makes a claim that a) structural locality is not implicitly fully captured by the distance metric used in non-parametric language models and further that b) explicitly plugging in structural locality into non-parametric language models can improve their effectiveness. It validates this claim first by doing analysis of two datasets with the help of custom locality functions and then by plugging in the locality functions into a non-parametric language model with the help of learnable parameters. \n", "summary_of_the_review": "The paper makes an interesting hypothesis and goes about validating the hypothesis. However, the improvements due to the proposed method are marginal.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DRBfjS5fO3G", "reviewer": "Reviewer_bn3A", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper models structural information into the non-parametric language models. While the results demonstrate that the method improves upon the existing methods, there are some weaknesses too.\n\nStrengths:\n1. The model or the loss function developed by the authors that incorporate structural information is novel. The authors have also clearly explained the model.\n2. Results demonstrate that the method improves upon existing methods.\n\nWeaknesses:\n1. While there are clear strengths, one weakness is that one may need to define structural properties in different types of datasets that one might use. For instance, it is clear that the model works for source codes and Wikipedia because associated structural information can be mined from the data. It is unclear how does the method generalise across different tasks and datasets, i.e., beyond two datasets. While the authors have addressed these limitations towards the end of the paper, the question is will the work be useful only to a small set of audience, or people from different domains can manually or automatically build such prior knowledge and incorporate it in this model. The key advantages are clear from the paper, this seems to be the weakness that is hard to defend. One possible way to improve the argument so that we could obtain Wikidata-type structure for most datasets is to exploit entity detection and linking including automatically learning their relation (vector) information in a completely unsupervised way. The authors must note that I am simply giving ideas on how to strongly defend this weakness of the model.\n2. In terms of experiments, these can be further improved by conducting some downstream application tasks. Can the model be useful for document classification tasks? Currently, it is very difficult to gauge the usefulness of the model through the limited experiments presented in the paper which mainly revolves around perplexity analysis and table 5 in the appendix has additional token prediction results.\n", "summary_of_the_paper": "The paper is about modelling structural locality in non-parametric language models. The key hypothesis is in modelling not only the co-occurrence characteristics but also structural characteristics such as locality. The paper explains the key claims via case studies conducted on source code data and Wikipedia datasets.\n\nThe model paradigm is based on non-parametric language models. A key difference between the non-parametric model and the parametric counterpart is that in the non-parametric model the model parameters are not only determined by the model architecture but also the underlying data.\n\nStructural locality, which is different from just co-occurrence counts, models the structural relationships between pairs of items, e.g., whether they belong to the same or different directory in the case of source code.\n\nThe optimisation model is presented in Equation 7 where the authors need a small sample set emanating from the same domain to train the model. The authors then conduct experiments to demonstrate that the method improves upon existing works. Both qualitative and quantitative experimental results are shown.", "summary_of_the_review": "Overall, the paper indeed has some merits. The paper can be made stronger by considering some comments mentioned above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers were in agreement but borderline.  The paper has a nice hypothesis and develops the work using two realistic datasets, Wikipedia and Code.  One reviewer was initially more negative but changed their views based on the authors improvements to the paper.
The idea is fairly simple, but does require modellers come up with the structural features.  There was discussion that more down-stream tasks are needed to highlight the approach.  Moreover, more datasets should be experimented with.  In all, experiments are good but improvement is easily done.
Decision: Accept (Poster)