Bringing Structure to Naturalness: On the Naturalness of ASTs
Profir-Petru Pârțachi, Mahito Sugiyama · 2025
Read Bringing Structure to Naturalness: On the Naturalness of ASTs by Profir-Petru Pârțachi, Mahito Sugiyama (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-08234.txt.
Introduction
Programmers have long noticed that source code feels predictable, almost like a language with habits. Profir-Petru Pârțachi and Mahito Sugiyama ask whether that predictability survives when code is viewed as structure rather than text. They name this the Structured Naturalness Hypothesis: the trees that parsers build from code, called abstract syntax trees, should also follow learnable statistical patterns.
Testing tree based language models against classic word sequence models, they found mixed news. For Ruby, tree models matched the text models while sidestepping a known token problem. For Java and Python they did worse, suggesting that helping a downstream task does not always mean modeling the language better. The team also showed the naturalness signal can power just in time defect prediction at near state of the art levels, with no hand built features.
Catalog record
| CREATOR | Profir-Petru Pârțachi, Mahito Sugiyama |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-08234
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bringing Structure to Naturalness: On the Naturalness of ASTs Profir-Petru Pârțachi, Mahito Sugiyama Abstract Source code comes in different shapes and forms. Previous research has already shown code to be more predictable than natural language as well as highlighted its statistical predictability at the token level: source code can be natural. More recently, the structure of code — control flow, syntax graphs, abstract syntax trees etc. — has been successfully used to improve the state-of-the-art on numerous tasks: code suggestion, code summarisation, method naming etc. This body of work implicitly assumes that structured representations of code are similarly statistically predictable, i.e. that a structured view of code is also natural. We consider that this view should be made explicit and propose directly studying the Structured Naturalness Hypothesis. Beyond just naming existing research that assumes this hypothesis and formulating it, we also provide evidence in the case of trees: TreeLSTM models over ASTs for some languages, such as Ruby, are competitive with n n -gram models while handling the syntax token issue highlighted by previous research ‘for free’. For other languages, such as Java or Python, we find tree models to perform worse, suggesting that downstream task improvement is uncorrelated to the language modelling task. Further, we show how such naturalness signals can be employed for near state-of-the-art results on just-in-time defect prediction while forgoing manual feature engineering work. Bringing Structure to Naturalness: On the Naturalness of ASTs 1 Introduction Source code is highly repetitive; despite the flexibility that programming languages offer, developers tend to converge to similar constructions which lend to its statistical predictability [ 1 ] . In the seminal work on source-code naturalness , Hindle et al. [ 1 ] show that this predictability, which represents naturalness, lends itself well to statistical language models. This property of source-code has been successfully exploited for many tasks such as code synthesis [ 2 , 3 ] , code completion [ 4 , 5 ] , identifier or method name suggestion [ 6 , 7 ] , defect prediction [ 8 ] etc. Allamanis et al. provide a more complete overview in their survey [ 9 ] . More recently, Rahman et al. [ 10 ] show that much of this predictability is due to syntax tokens and removing these, akin to removing stop-words, makes code less predictable than previously claimed. In addition to this, Rahman et al. consider a graph view that is obtained from a program-dependency graph which does not have to contend with syntax tokens by mining (2,3,4)-hop sub-graphs. They show that this view is more predictable than a token view; however, they stop short of formulating structured naturalness or studying other structures more extensively. Recent work has started exploiting structure, not necessarily restricted to the view presented by Rahman et al. , either as additional signal [ 11 , 12 , 13 , 14 ] , or to overcome limitations of existing methods: such as overcoming vanishing gradients in neural models using a graph structure superimposed on the tokens [ 15 ] by providing shorter paths for information to propagate along. While it seems intuitive that naturalness should extend from the unstructured token domain into structures that we obtain, which we refer to as structured naturalness , either via parsing, such as abstract syntax trees (ASTs), or by static or dynamic analysis, such as control-flow graphs, data-flow graphs, call graphs etc. , this assumption has not been studied directly. Further, it is an open question if such tasks help with the language modelling task or specifically the downstream tasks for which such views are employed. We propose that the structured naturalness hypothesis should be the primary subject of study rather than an unstated assumption as the current body of literature would have it. By better knowing the nature of the statistical regularities induced in structured views of code from the underlying naturalness of the source code itself, we can better tune statistical approaches that seek to use it either as an aid or directly as a signal. We also wish to explore if the structure is task-specific, and if it should be considered as a prior or inductive bias. Rahman et al. has placed the first stones towards the study of structured naturalness by looking at a mined sub-graph view of code; however, that mimics n -grams too closely and misses the more fundamental nature of structured naturalness by casting it too close to the token-level view. In this work, we propose, first of all, to formulate the hypothesis and, then, to study the naturalness of ASTs directly to demonstrate the promises of structured naturalness. Existing work already makes use of tree structures for code [ 11 , 12 , 13 , 15 ] , hence we aim to retroactively provide empirical evidence for why such language models should work. Instead of following too closely the original Hindle et al. [ 1 ] naturalness work and restricting ourselves to a n -gram analogue, as there is no canonical language model, we instead consider TreeLSTM with masked token prediction as the training task. Our choice of using ASTs is both pragmatic — it allows us to use existing parsers — and as a representative structure that we expect to exhibit structured naturalness that has not been previously studied as a first-class citizen of such research. We find mixed results across the languages, suggesting that perhaps downstream tasks benefit from the structure as a side-channel rather than enhanced language modelling directly. To explore if structure helps downstream tasks specifically, rather than by improving language understanding, we explore if the statistical signal can be employed by a simple classification pipeline trained to perform just-in-time defect prediction. We find that even a simple pipeline can reach near state-of-the-art results on JIT defect prediction with no manual input for feature selection. Structured naturalness holds promises beyond the domain of programming languages: going from the naturalness of tokens to that of parses can extend to natural languages. We can already see the idea of employing graph structures for summarisation in work from Allamanis et al. [ 15 ] . They endow an English sentence with either entity recognition-based graphs or dependency parse graphs to avoid vanishing gradient issues. While they use this construction for pragmatic reasons, this still leaves the door open to questions about the regularities of such parses or graphs, hence their structured naturalness. Further, there are open questions about representations that can be antagonistic towards pre-training tasks (masked token prediction) while being synergistic to downstream tasks 1 1 1 We make our experimentation code available here: https://drive.proton.me/urls/07K7T7ABEW#kk74oCX54fUk . To summarise, we: • propose to extend the naturalness hypothesis to structured representations of code: both from parses, such as ASTs, and from analysis, such as control-flow graphs, call graphs etc. • study the naturalness of AST trees, providing empirical evidence to justify why such models should succeed at source-code prediction tasks or, indeed, why they do not. • demonstrate near state-of-the-art results for just-in-time prediction without requiring manual feature engineering work to show how regularities from ASTs can help downstream tasks. 2 Structured Naturalness Figure 1: Log-Log plot of AST Labels (inner nodes) against their rank by frequency in the corpus.