1
00:00:01,000 --> 00:00:41,000
[Hal Turing] Alrighty! Thanks for tuning in! Hello AI world! I am your host, Hal Turing, and my co-host is Dr. Ada Shannon.

Today we're reading Structural Language Models of Code, by Uri Alon and three co-authors, out of Technion, Tel Aviv University and Facebook AI Research. The version we have is dated July 2020. Picture a Java method that loops over an array of file statuses, and the cursor sits at ret[i] equals, blank. The model's top guess is stats[i].getPath(), and it assigns that 25.2 percent probability. It's the right answer, and the model is still only about one-in-four sure. That's what a hard completion looks like.

2
00:00:41,000 --> 00:01:04,250
[Dr. Ada Shannon] The consequence is that if a model can't finish that line, completion stays a toy. The set of valid right-hand sides is unbounded. It could be any call chain, any nesting, any user-defined method, including names the model never saw in training. Alon's group bets that you handle this by treating the program as a tree, not a string, and letting one model both read the surrounding code and write the missing piece. They also released the code, data and trained models, and there's a live demo at AnyCodeGen.org.

3
00:01:04,250 --> 00:01:46,575
[Hal Turing] So the core question is this: can you generate code with no restriction on vocabulary or structure, by modeling a program as a tree, where the same model reads the context and writes the missing subtree node by node? They call the task any-code completion. Given a program P and a missing part p, predict p from P minus p. Their headline claim, in one sentence: Java exact-match accuracy@1 of 18.04 versus 16.93 for the previous best, and C# accuracy@1 of 37.61 versus 26.42. The tables come later, and so does the question of how far those gaps can be trusted.

4
00:01:46,575 --> 00:02:30,925
[Dr. Ada Shannon] That question matters because the field has wanted this since 1969. Waldinger and Lee, at SRI, wrote the PROW paper, and automatic programming became the holy grail. What actually shipped was narrow. FlashFill-style systems from Gulwani at Microsoft, and DeepCoder-style models from Balog and colleagues, work from input-output examples inside a small domain-specific language. The attempts at general languages restricted something else. Murali and colleagues, in 2018, covered API-heavy programs only. Brockschmidt and colleagues at Microsoft Research, in 2019, allowed only primitive types, a closed vocabulary and no user-defined functions. Young and colleagues, also 2019, restricted domain and syntax. Any-code completion is defined against exactly those restrictions.

5
00:02:30,925 --> 00:02:37,275
[Hal Turing] And the obvious alternative is to skip the trees entirely. Treat code as text.

6
00:02:37,275 --> 00:03:00,150
[Dr. Ada Shannon] Right, and that's the sequence-to-sequence baseline. Split identifiers into subtokens, so toLowerCase becomes to, lower, case, which keeps the vocabulary small while names stay unbounded. Replace the target with a placeholder and have an encoder-decoder emit the missing piece as a subtoken sequence. Related tasks like natural-language-to-code and semantic parsing use separate encoders and decoders, because input and output are different modalities.

7
00:03:00,150 --> 00:03:09,425
[Hal Turing] Oh wait, hold on, that's where the tree lineage comes in, right? Because I remember code2vec, and that was about reading code, not writing it.

8
00:03:09,425 --> 00:03:47,750
[Dr. Ada Shannon] Yes, and it's the same group. An abstract syntax tree is the unambiguous tree form of the token sequence. An AST path is the unique route between two nodes, and it records both which elements are related and how. The PLDI 2018 paper by Alon, Zilberstein, Levy and Yahav, then at Technion, used sets of leaf-to-leaf paths as a relational input for predicting program properties. code2vec, in 2019, pooled a bag of paths into one vector, and its selling point was generalizing to unseen names. code2seq, the same year, added a path encoder with a sequence decoder. All of them read code. Here the paths are used for writing.

9
00:03:47,750 --> 00:03:57,500
[Hal Turing] Here's my genuine question, then. A path runs between two leaves that already exist. How do you use it to write a node that doesn't exist yet?

10
00:03:57,500 --> 00:04:32,774
[Dr. Ada Shannon] By changing the endpoint. A partial AST path runs from an already-generated leaf to the node currently being expanded. Structural language modeling, or SLM, then applies the language-model chain rule to the tree. A word model multiplies the probability of each word given the prefix. Here you multiply the probability of each node given the part of the tree already produced, and only the target subtree gets scored. I'll keep the mechanism for later. The intuition is that syntax arrives as structure, so the model doesn't have to relearn it from text. And whether the unseen-name strength survives the move from reading to writing is the thing to watch.

11
00:04:32,774 --> 00:04:57,349
[Hal Turing] Last piece is the scoring. Exact-match accuracy at k means the prediction counts only if it's identical to the ground truth, and acc@5 accepts any of the top five beam candidates. The evaluation is public Java and C# benchmarks, against seq2seq, seq2tree, code2seq and graph baselines. Ada, given a strict metric like that, what should listeners keep an eye on?

12
00:04:57,349 --> 00:05:07,549
[Dr. Ada Shannon] Whether a one-point win is a real win. Exact match also undercounts logically equivalent code. Keep both in mind while we go through the method.

13
00:05:07,549 --> 00:05:17,349
[Hal Turing] Okay, mechanics. A sentence has an obvious previous word, and a half-built tree doesn't. What does the chain rule actually run over, Ada?

14
00:05:17,349 --> 00:06:01,624
[Dr. Ada Shannon] Depth-first traversal gives the nodes an order, and the tree's probability is the product of each node given the ones before it. In completion, the observed tree comes first in that order, so only the target's conditionals get scored. Other orderings are possible, and depth-first is what they use. The hard part is representing the half-built tree. Linearizing it, as in Xiao's 2016 semantic parsing work at CNRS, puts ancestors artificially far away. The root-to-node path alone, from Rabinovich's 2017 Abstract Syntax Networks at Berkeley, drops siblings. SLM uses the paths from every generated leaf to the parent being expanded, plus the root path. In Figure 2, generating x greater than 1, a third path appears the moment the leaf x exists. The model predicts the next node along those paths.

15
00:06:01,624 --> 00:06:10,449
[Hal Turing] Genuine question: a sequence has one end token. A tree can have any number of children and any depth. What tells it to stop?

16
00:06:10,449 --> 00:06:44,524
[Dr. Ada Shannon] Two special nodes. EOSnode sits under every nonterminal and says the parent has no more children, which controls arity. EOStok ends each camel-case subtoken sequence, which controls depth. This is also why they predict nodes, not grammar productions like Yin and Neubig's 2017 model from CMU or Brockschmidt's 2019 graph model from Microsoft Research. Generating str.Substring(3), a production model must commit to Substring and its arity before it has seen str. Node generation says a call exists first, then fills in the receiver and method.

17
00:06:44,524 --> 00:06:50,199
[Hal Turing] And the network reading those paths? I'm guessing an LSTM shows up somewhere.

18
00:06:50,199 --> 00:07:27,799
[Dr. Ada Shannon] For encoding, yes, plus a transformer. Nodes embed as type plus child index, and a uni-directional LSTM encodes each path. Paths from one leaf share a prefix, so that state is cached across time steps, which speeds up training and inference. A transformer over the path set uses no positional embeddings, since it's a set. The root path goes through a ReLU layer selected by child index and becomes the attention query. The attended vector, concatenated with the root path, gives h. For subtokens, a bilinear score of path encoding and h is summed with the vocabulary score, so take zkfcUgi.getShortUserName(), where zkfc—

19
00:07:27,799 --> 00:07:33,724
[Hal Turing] Wait, zkfc? That can't be in a 1000-subtoken vocabulary.

20
00:07:33,724 --> 00:08:02,649
[Dr. Ada Shannon] It isn't, and only copying makes the answer reachable. The copy is guided by syntactic relation to the leaf, not sequence position as in Gu's 2016 copying paper from Hong Kong. That's also the generality argument. Parent feeding and previous-action encoding from Yin and Neubig fall out of the path set. PHOG's context node, from Bielik at ETH in 2016, is one leaf with no relation attached. Hand-built edges like NextSib or ComputedFrom in Brockschmidt and Allamanis become partial paths.

21
00:08:02,649 --> 00:08:11,424
[Hal Turing] Retraining every baseline with copy and subtokenization is a fair setup, and I'll say that plainly. What are the benchmarks?

22
00:08:11,424 --> 00:09:03,849
[Dr. Ada Shannon] Java-small: 11 GitHub projects split 9, 1, 1 by project, picked as the least duplicated dataset per Allamanis in 2019. Targets are every expression bigger than one node. Methods containing 'test' and those over 20 lines, about 10%, are dropped, and so are targets appearing verbatim in context. That leaves 1.3 million, 10k and 20k examples, with 5.4 target tokens on average. C# uses Brockschmidt's filters: primitive targets, no user-defined functions. His dataset wasn't public, so they re-extracted it after consulting him. That's 25, 2 and 3 projects, 16,295 training and 3,305 test examples, with 3.9-token targets. SLM has 15 million parameters against 45 million-plus for Transformer base. Training is on one V100, beam width 5, hyperparameters grid-searched on dev, then one test run.

23
00:09:03,849 --> 00:09:12,499
[Hal Turing] Java first. SLM gets 18.04 acc@1 and 24.83 acc@5. Against whom?

24
00:09:12,499 --> 00:10:04,599
[Dr. Ada Shannon] The paper reads it as 1.1 points acc@1 over BiLSTM at 16.93, and 0.78 acc@5 over Transformer base at 24.05, then 3.8 and 3.4 over Transformer small. Tree@1 is 39.10 versus 38.14 for seq2tree, tree@5 is 55.32 versus 52.36. Generic NMT beat the code-specific models: code2seq 10.68, seq2prod 8.05, Iyer 5.94. In C#, SLM gets 37.61 and 45.51 against seq2seq+copy at 26.42, seq2tree+copy 22.29, GNN to NAG 15.19, PHOG 7.40 and code2seq 6.20. Adding copy alone beat the prior state of the art, and the authors also point to the GNN long-range bottleneck.

25
00:10:04,599 --> 00:10:07,824
[Hal Turing] And the ablations? Which piece carries it?

26
00:10:07,824 --> 00:10:37,850
[Dr. Ada Shannon] Removing copy costs 7.3 to 9.1 points, and removing root attention costs 3.6 to 6.3. Mismatched encoder and decoder types hurt: Paths to Seq is 12.95, Seq to Path 12.12. The authors' reading is that the output is a missing part of the input tree. Untied Paths to Paths reaches 17.63, so paths beat text even without tying, and tying gets to 18.04. Paths to Seq is code2seq plus copy, 2.3 points above code2seq's 10.68.

27
00:10:37,850 --> 00:10:40,350
[Hal Turing] What do the failures look like?

28
00:10:40,350 --> 00:11:20,275
[Dr. Ada Shannon] Right structure, wrong name. In Figure 4, value.length() greater than 0 ranks first and the truth, greater than 55, ranks second. Nothing in the code says 55, so the model guessed like a reasonable person. Single-subtoken errors are 30% of those tree-match misses and single-token errors 74%. One-token-diff acc@1 is 33.68 for SLM versus 32.67 for seq2tree. In Figure 5, a compiler filter would lift the correct candidate from fifth to second, which the authors leave as future work. Seq2tree sometimes emits syntax errors. The stated uses are completion, fixing unlikely code, and re-ranking another synthesizer's output.

29
00:11:20,275 --> 00:11:39,725
[Hal Turing] So structure is mostly handled, and names are the wall. Now the section I flagged at the start, Ada: how far can we trust these gaps? Every Java number is one training run, with hyperparameters picked on dev and a single test evaluation. There are no seeds and no confidence intervals.

30
00:11:39,725 --> 00:12:34,351
[Dr. Ada Shannon] Plausibly real at acc@1, but unmeasured. Here's a back-of-envelope of ours, not the paper's. With 20k test examples and accuracy near 0.17, the binomial standard error is about 0.27 points, so 1.1 points is several standard errors. But that ignores seed-to-seed training variance, which can be about a point when systems sit this close. It also ignores clustering: every qualifying expression in a method is a target, so the effective sample is smaller than 20k. The 0.78 acc@5 gap is indistinguishable from noise on this evidence. And the introduction quotes 23.17 as the previous acc@5, which is the BiLSTM number. Transformer base scored 24.05, so the real margin is 0.78, not 1.66. The 3.8 points over Transformer small and the tree@5 gap, 55.32 against 52.36, are more likely to survive.

31
00:12:34,351 --> 00:12:41,926
[Hal Turing] And that's all one test project, with the test set sampled down to 20k from that project's raw split.

32
00:12:41,926 --> 00:13:08,426
[Dr. Ada Shannon] Right, so the ranking is specific to that project, and leave-one-project-out over all eleven would give a per-project table showing whether SLM wins consistently. The right resampling unit is the project, not the example, so you'd want a project-level bootstrap. Dev selection on one project's 10k examples may also fit that project's idiom. Nobody knows whether the ranking changes, because nobody tested it. The fair claim is best on this held-out project, and the C# result is where the—

33
00:13:08,426 --> 00:13:18,976
[Hal Turing] Sorry, wait, that's the big one, though. 37.61 against 26.42 acc@1, eleven points. That can't be seed noise.

34
00:13:18,976 --> 00:13:56,151
[Dr. Ada Shannon] Direction, yes, I'd trust it. Now look at what it rests on: a dev set of 8,183, about half the training size, and three test projects. The dataset is a reconstruction. PHOG was trained by its own authors without copy. Table 2 has no Transformer baseline, even though Transformer base was competitive in Java. And GNN→NAG's original seq2seq baseline lacked copy, so how much of eleven points is copying, not structure? My hypothesis is that structure helps most when data is scarce, but no data-scale experiment is shown. Also note the largest gap is on the restricted, easier task, not the any-code task in the title.

35
00:13:56,151 --> 00:14:09,301
[Hal Turing] The ablation claim also bugs me. The abstract says joint modeling matters, and the Paths→Paths versus SLM comparison is the only direct test of parameter tying.

36
00:14:09,301 --> 00:14:46,601
[Dr. Ada Shannon] A 0.41-point difference, unreplicated, smaller than the headline gap. So the paper's strongest claimed insight rests on its weakest evidence. The big drops are clearer, though the copy variant also swaps a 1k vocabulary for 25k, so two things change at once. But no ablation swaps only the factorization while holding the path encoder fixed. SLM also got a grid over six hyperparameter dimensions, while baseline tuning effort isn't documented. It has 15M parameters against 45M-plus, and there are no latency numbers despite per-node decoding. Tree@k credits wrong meaning, and nothing checks that output compiles.

37
00:14:46,601 --> 00:14:53,851
[Hal Turing] Back to code2vec and the PLDI paper, then. Did the unseen-name strength carry over to writing?

38
00:14:53,851 --> 00:15:34,001
[Dr. Ada Shannon] Half. The copy ablation and the zkfc example say yes. But the path encoder alone isn't the win. Joint modeling plus syntactic copy is. Later work asks the scale question this paper can't: InCoder, from Daniel Fried at Meta and UW in 2022, and Bavarian's fill-in-the-middle paper from OpenAI that year, get infilling from flat Transformers with no parser. Codex, Mark Chen at OpenAI in 2021, moved evaluation to unit tests. UniXcoder, by Daya Guo out of Sun Yat-sen University in 2022, feeds flattened ASTs into a pretrained model. Interestingly, Uri Alon is also on the Gemma 4 Technical Report, so he's now on the scale side of this argument.

39
00:15:34,001 --> 00:16:11,101
[Hal Turing] So the takeaways. SLM is a clean idea that generalizes parent feeding, context nodes and hand-built graph edges. The C# win is large and plausible, the Java win small and statistically unsupported. Several seeds, a project-level paired bootstrap and leave-one-project-out would settle it cheaply. The most practical extension is Figure 5's compile filter: the top candidate, at 31.3%, calls getCount, which doesn't exist. Paths taught models to read code, and this paper asks whether they can write it too. Thanks for listening, Ada, and thanks everyone. Goodbye!