Source-linked AI summary
Emergent Representations of Program Semantics in Language Models Trained on Programs
Charles Jin, Martin Rinard
TL;DR
Whether language models trained on next-token prediction capture semantics beyond surface correlations remains an open question. This paper trains on input-output specifications followed by programs and probes hidden states; the results indicate representations of program semantics emerge alongside correct synthesis.
Problem
Whether current language models capture semantics of the text they consume and generate, rather than relying on surface statistical correlations, remains an open question.
Source: §1 · p. 1Method
The authors train a language model on input-output examples followed by programs, probe hidden states for intermediate execution states, and use alternative-semantics interventions to test whether the probe learns semantics from a syntactic record.
Source: §1 · pp. 1–2, §4 · p. 6Results
Takeaways & Limitations
Semantic probing interventions distinguish semantic information intrinsic to model representations from a probe’s ability to derive semantics from syntactic information.
Source: §6 · p. 9The studied programs are straight-line programs with no control flow, so each operation produces exactly one traced program state.
Source: §2.2 · p. 3
Abstract
from arXiv · showhide
We present evidence that language models (LMs) of code can learn to represent the formal semantics of programs, despite being trained only to perform next-token prediction. Specifically, we train a Transformer model on a synthetic corpus of programs written in a domain-specific language for navigating 2D grid world environments. Each program in the corpus is preceded by a (partial) specification in the form of several input-output grid world states. Despite providing no further inductive biases, we find that a probing classifier is able to extract increasingly accurate representations of the unobserved, intermediate grid world states from the LM hidden states over the course of training, suggesting the LM acquires an emergent ability to interpret programs in the formal sense. We also develop a novel interventional baseline that enables us to disambiguate what is represented by the LM as opposed to learned by the probe. We anticipate that this technique may be generally applicable to a broad range of semantic probing experiments. In summary, this paper does not propose any new techniques for training LMs of code, but develops an experimental framework for and provides insights into the acquisition and representation of formal semantics in statistical models of code. Our code is available at https://github.com/charlesjin/emergent-semantics.
1. Introduction
The introduction asks whether next-token-trained code LMs model program semantics, then uses synthesis and semantic probing to test that hypothesis. It reports emerging intermediate-state representations and an intervention aimed at separating LM-carried semantics from semantics learned by the probe.
1. Introduction
- The tested Main Hypothesis holds that next-token-only code LMs do not model formal semantics, amid a broader account of language modeling based on surface statistical correlations.The paper investigates whether code LMs capture semantics of the text they consume and generate.Source: §1 · p. 1
- The study frames synthesis as generating programs from partial input-output specifications and probes LM hidden states for states along execution traces.The probe targets intermediate states specified by the program’s small-step operational semantics.Source: §1 · p. 1
- Training examples interleave five executed input-output pairs before their reference program; testing supplies unseen specifications for greedy program decoding.The experimental overview describes the training and test sequence.Source: Figure 1 · p. 2
- Probe-accessible abstract semantics of intermediate states and predictions of future states emerge alongside the LM’s ability to generate correct programs.The paper reports that these semantic representations emerge in lockstep with correct-program generation.Source: §1 · pp. 1–2
- Alternative-semantics probes achieve lower accuracies, supporting the interpretation that semantic information resides in LM states rather than being supplied by the probe.The reported evidence is consistent with states aligned to the original semantics and inconsistent with a purely syntactic-record account.Source: §1 · p. 2
2. Background and setting
The setup treats program traces as a model of meaning and studies next-token program synthesis in Karel. Training ends with a distinct phase of rapidly increasing semantic correctness.
2.1. Program tracing as meaning
- Program meaning is modeled as traces: sequences of intermediate states for an input, with abstract interpretation linking concrete and abstract states.Tracing is also linked to explaining code and localizing reasoning errors.Source: §2.1 · pp. 2–3
2.2. Language modeling task and training
- A 350M-parameter CodeGen Transformer learns next-token prediction from 500,000 Karel programs paired with five input-output worlds, with traces withheld.The five-operation subset has no control flow, so each operation yields one trace state.Source: §2.2 · p. 3
2.3. Results
- 92.4% generative accuracy at training’s end; accuracy rises rapidly in the final semantics-acquisition phase, after syntax acquisition increases output diversity.Accuracy stays near 10% during babbling, rises from 10% to 25% in the middle phase, then climbs from 25% to over 90%.Source: §2.3 · pp. 3–4, Figure 2 · p. 4
- Despite increasingly correct generations, a persistent perplexity gap suggests the LM underfits reference program tokens, so accuracy gains are not solely surface-distribution fit.The authors note that greedy decoding naturally lowers generated-program perplexity relative to reference-program perplexity.Source: §2.3 · p. 4
3. Emerging representations of semantics
The section tests whether language-model hidden states track program meaning by aligning generated-program states with executed program states. Probes recover abstract semantics that emerge during training.
3.1. Probing for representations of the program trace
- Every 4,000 training steps, the LM generates programs from input-output specifications while the corresponding program states are recorded across five specified inputs.The aligned hidden-state and program-state traces are averaged across the LM layer dimension before probe training.Source: §3.1 · p. 4
- Probes predict robot direction, position offset, and obstacle-facing status from model states; their geometric-mean test accuracy measures semantic content as abstract interpretation.The abstract-state features are an abstraction of the full program state, and tracing them is formally equivalent to performing an abstract interpretation.Source: §3.1 · pp. 4–5
3.2. Results
- Because training programs have length six or more, the authors also test retrieval explanations using shorter programs, where the LM must infer rather than retrieve semantics.This is presented as an additional hypothesis evaluated alongside the main results.Source: §3.2 · p. 5
- At two states ahead, the 2-layer MLP probe has greater absolute accuracy than the current-state-copy baseline, whose accuracy degrades faster across future states.This suggests the LM encodes information about what it intends to generate ahead of time.Source: Table 1 · p. 6, §3.2 · p. 6
- During semantics acquisition, all three probes' semantic content steadily increases; generative accuracy correlates with it (R2 = 0.904, 0.886, 0.821; p < 0.001).The correlations are for the linear, 1-layer MLP, and 2-layer MLP probes, respectively.Source: §3.2 · pp. 5–6
- For a 1-layer MLP, semantic content for states one and two steps ahead reaches a minimum during syntax acquisition, then rises and correlates with generative accuracy.The correlations are R2 = 0.878 and 0.874 (p < .001) for one and two abstract states ahead, respectively.Source: §3.2 · p. 6
4. Semantic probing interventions
The section tests whether semantic information is represented in the LM or learned by the probe, using interventions that change program semantics while preserving syntax. Alternative-semantics probes show significantly degraded semantic content, supporting the conclusion that LM states encode more than a syntactic record.
4.1. Intervening on semantics
- The intervention re-executes the same program tokens under alternative operation semantics and trains a new probe on the resulting states using the original LM states.If LM states contain only syntax, the alternative probe should recover the alternative semantics equally well and leave semantic content unchanged.Source: §4 · p. 6, §4.1 · p. 8
4.2. Results
- In all five cases, alternative-semantics probes show significantly degraded semantic content versus original semantics, supporting rejection of the syntactic record hypothesis.The authors conclude that a statistically significant portion of the observed semantic content cannot be explained by the probe learning semantics.Source: Table 2 · p. 7, §4.2 · p. 8
4.1. Intervening on semantics
- A valid control changes only individual operations’ semantics and preserves program syntax, so a significant drop in alternative semantic content counts against the syntactic record hypothesis.Under the syntactic record hypothesis, an alternative probe should interpret the unchanged record through an analogous procedure.Source: §4.1 · p. 8
4.2. Results
- Flip semantics retain a close relation to the original, while adversarial semantics change each operator’s meaning; the authors report lower semantic content for adversarial than flip, consistent with more difficult remapping.During the babbling phase, the original-over-flip excess disappears post-intervention, controlling for a probe’s ability to learn semantics.Source: §4.1 · p. 6, §4.2 · p. 8, Figure 7 · p. 8
5. Related work
The paper situates its work among studies of LM behavior, interpretability, program grounding, and probing. It contrasts its internal-state analysis and semantic intervention control with prior approaches to external evaluation and probe controls.
LMs, semantics, and interpretability
- Unlike work probing pretrained models or fine-tuned situation descriptions, this study trains an LM from scratch to examine how semantic representations emerge over training.The authors also distinguish their intervention method from work editing Othello representations and studying subsequent generations.Source: §5 · p. 9
Grounding programs from text
- Prior work establishes program-grounding questions and argues that meaning from unit tests may require human-equipped interpretation, while this paper reports empirical evidence from next-token training.Merrill et al. prove that some program semantics cannot be learned from text under assumptions the authors say do not hold in their setting.Source: §5 · p. 9
Program synthesis with LMs
- Program-synthesis studies have noted that BLEU against a reference solution poorly predicts LM competency, complementing this paper’s results concerning training-corpus perplexity.Source: §5 · p. 9
Probing
- Because random-feature control tasks disrupt program syntax, the paper introduces semantic interventions that change operation meanings while preserving program structure.The authors present the framework as applicable to future interpretability studies of meaning, beyond syntactic structure.Source: §5 · p. 9
6. Conclusion
The paper concludes that next-token training can yield LM representations of program formal semantics in its studied setting. It presents semantic probing interventions as a way to distinguish represented information from what a probe learns.
6. Conclusion
- The authors report empirical evidence that next-token-trained code LMs acquire formal program semantics, with later training showing a strong linear correlation between emerging semantic representations and synthesis accuracy on unseen specifications.They describe three distinct training phases and report representations of future semantics, suggesting a notion of intent during generation.Source: §6 · p. 9
- Semantic probing interventions distinguish semantic information intrinsic to LM representations from a probe’s ability to derive semantics from purely syntactic information.This framework supports evaluating nonlinear probes, which the authors say may otherwise be more prone to false positives because of their greater task-learning capacity.Source: §6 · p. 9
- The authors propose their techniques and insights as a principled foundation for future studies of LM capabilities and limitations.Source: §6 · p. 9
Impact statement
The impact statement identifies no societal consequences requiring specific emphasis and reports that the research code is publicly available.
Impact statement
- The authors state that they do not identify any potential societal consequences requiring specific highlighting.Source: Impact statement · p. 10
- The authors open-source code for generating training data, training the LM, and conducting probing experiments.Source: Impact statement · p. 10
A.1. Karel grammar specification
The appendix specifies a Karel grammar without loops or conditionals, describes the LM and probe training setup, and examines adversarial-semantic results. The adversarial comparison shows noisy excess semantic content during the babbling phase and a pattern consistent with a shared mapping from original to adversarial states.
A.1. Karel grammar specification
- The grammar removes loops and conditionals and uses five actions: move, turn right, turn left, pick a marker, and put a marker.The action set is specified as move(), turnRight(), turnLeft(), pickMarker(), and putMarker().Source: §A.1 · p. 16
A.2. Language model and probe details
- The LM is a 350M-parameter CodeGen model trained for 2.5 billion tokens, while probes use a linear layer or stacked linear, batch-normalization, and ReLU layers.The LM uses Adam with a 5e-5 learning rate; probes are trained on 100,000 aligned training traces.Source: §A.2 · p. 16
B.1. Plots for adversarial semantics
- Adversarial excess semantic content is noisy and often negative during the babbling phase, then remains largely constant across current and future states late in training.The authors attribute the babbling-phase noise to a weaker relationship between adversarial and original semantics, and the later pattern is consistent with probes learning the same map from original to adversarial states.Source: §B.1 · pp. 16–17
B.2. Generated programs become shorter than reference programs over training
Generated programs become shorter than their references while becoming more correct over the latter half of training. In a separate comparison, the LM’s states show greater semantic content for greedy-decoded programs than for reference programs by the end of training.
B.2. Generated programs become shorter than reference programs over training
- Generated programs are shorter than references sampled from the training distribution, yet their correctness continues to improve during the second half of training.The references have lengths 6 to 10 inclusive; greedy decoding can partly explain the shorter outputs.Source: §B.2 · p. 17
- The authors present the connection between syntactic divergence and semantic properties of LM generation and training data as a contribution not previously reported to their knowledge.They relate this observation to prior work on surface-statistical differences between LM outputs and training corpora (Meister & Cotterell, 2021; LeBrun et al., 2022).Source: §B.2 · p. 17
B.3. Semantic content of reference programs
- By the end of training, greedy-decoded programs have higher semantic content than reference programs, especially for present and future states.The authors explain that future states are partly random because generated programs follow a random sampling procedure, limiting how informative LM representations can be.Source: §B.3 · p. 18, Figure 11 · p. 18
- The gap between semantic content for reference and generated programs grows with generative accuracy, while a general increase in greedy-decoding preference is conjectured and decoding-strategy effects remain for future study.The authors leave a more detailed exploration of how decoding strategies affect internal-state coherence to future work.Source: §B.3 · p. 18
B.4. Semantics are inferred, not retrieved
The results indicate that semantic content cannot be fully explained by retrieval of previously seen program states. Retrieval effects vary by feature and probe depth, while the evidence supports retrieval coexisting with semantic representations.
B.4. Semantics are inferred, not retrieved
- Probes achieve non-trivial accuracy on unseen program states from programs of length 5 or less, supporting generalization beyond retrieval of training states.Training programs have length 6 or greater, so the first five entries in test traces cannot be retrieved from corresponding training states.Source: §B.4 · pp. 18, 20, Table 3 · p. 19
- Retrieval appears more pronounced for the simpler direction feature, while robot-position accuracy declines with depth, consistent with compounding execution errors.Deeper probes are less sensitive to retrieval across all three features, suggesting retrieval is represented more shallowly and matters less once probes extract deeper semantics.Source: §B.4 · p. 20
- Excess semantic content over flip and adversarial semantics starts near zero mid-training and becomes positive by the end across depths; retrieval nevertheless coexists with semantic representations.For flip semantics, excess content rises with depth from 1 to 5 and then decreases beyond depth 5, a pattern the authors contrast with reliance on retrieved states.Source: Figure 12 · p. 19, §B.4 · p. 20
B.5. Interpreting programs without outputs
In the input-only setting, the LM is prompted with inputs and reference program tokens while outputs are replaced by empty grids. The results show degraded semantic content but retain evidence of program interpretation, and selected regression plots support linear relationships with generative accuracy.
B.5. Interpreting programs without outputs
- Input-only probes show significantly degraded original-state semantic content relative to Table 2, especially for future states, with little performance separation among probe depths.The authors attribute the future-state difficulty partly to randomness; semantic content is maximized one abstract state into the past across settings.Source: §B.5 · pp. 20, 22, Table 4 · p. 21
- Even without specification outputs, the LM retains evidence of program interpretation, and original-versus-adversarial semantic content is significantly correlated across all three probes and five abstract states.The interventional baseline supports alignment of LM representations with original semantics rather than semantics learned by the probe.Source: Table 4 · p. 21, §B.5 · p. 22
- For the linear probe, excess original-over-flip semantic content correlates significantly with generative accuracy, but this effect disappears for deeper probes.The authors note that flip semantics is a strong baseline because it can often be inferred by reflecting the robot across an axis.Source: §B.5 · p. 22
- On input-only traces, almost every unseen feature and overall abstract state has greater semantic content for original than alternative semantics, arguing against retrieval as the full explanation.The comparison uses a linear probe one abstract state into the past; Table 5 separates excess semantic content by depth and feature.Source: §B.5 · p. 22, Table 5 · p. 22
B.6. Selected regression and residual plots
- Regression and residual plots for current-state semantic content measured by a linear classifier confirm linear relationships with generative accuracy, including cases not shown.Figures 14 and 15 show selected plots from Tables 2 and 4, respectively.Source: §B.6 · p. 22, Figure 14 · p. 24, Figure 15 · p. 25