acceptodds
Under review as a conference paper at ICLR 2027

Do LLMs Understand Program Semantics?

Abstract

LLMs are remarkably good at writing code. But do they understand what code means—i.e., its semantics—or are they just exploiting syntactic patterns? We introduce a family of benchmarks that isolates reasoning about program semantics. Each task provides three of four components—a program, its inputs, its outputs, and a semantic interpretation—and asks the model to infer the fourth. All problems share a fixed (syntactic) language: programs are drawn from the same grammar, but are equipped with multiple semantic interpretations. This approach isolates semantic reasoning because models cannot rely on syntactic differences to distinguish behaviors. We construct these tasks via an automated procedure that samples programs, interpretations, and behaviors, and filters out degenerate cases to ensure non-trivial dependence on both inputs and semantics. Across a range of models and task types, we find that performance varies significantly between models, and falls off as the language’s semantics get more difficult—revealing a gap between coding ability and semantic understanding. Moreover, performance on our benchmarks correlates with success on program synthesis, suggesting that this gap reflects a limitation that transfers to practical settings.

Primary area:
datasets and benchmarks
Keywords:
large language models, program semantics, program synthesis, benchmarking

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_GSBpOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates whether LLMs genuinely reason about program semantics rather than relying on syntactic patterns. The authors introduce a benchmark framework that holds program syntax fixed while varying the semantic interpretations of individual statements. The authors develop an automated generation pipeline with controllable complexity and evaluate six LLMs across different semantic expression sizes, program structures, and input representations.

Critical strengths
  1. The varying semantics design provides a principled way to reduce reliance on memorized associations between program syntax and behavior. Evaluating four complementary tasks offers a broader perspective on semantic reasoning than conventional code execution or generation benchmarks.

  2. The automated generation pipeline supports controlled variation in semantic expression size and program structure.

  3. The evaluation covers 500 generated languages and the observed performance degradation with increasing expression size provides useful evidence about the limitations of current models.

Critical weaknesses
  1. Semantic understanding is not sufficiently disentangled from computational complexity. The central claim is that increasing semantic expression size reveals limitations in semantic understanding. However, the generated expressions consist primarily of register references and addition/subtraction operations. For loop-free programs, these expressions can be reduced to linear transformations over registers.

  2. Important experimental confounders are insufficiently controlled. The evaluated models have substantially different reasoning configurations, and GPT-5.1 is explicitly evaluated without reasoning enabled. The comparison between loop-free and loop-containing programs also uses different sampled language sets rather than clearly matched instances, making it difficult to isolate the effect of loops.

  3. The validity of the inverse tasks requires further investigation. Unlike output prediction, input prediction, semantic completion, and program synthesis can admit multiple valid solutions. In particular, predicting a missing semantic rule from only five input-output examples may be highly underdetermined.

  4. The claimed connection to practical program synthesis is not sufficiently established. Although Section 5 reports broadly consistent model-level performance trends on generated tasks and existing SemGuS synthesis benchmarks, the analysis lacks quantitative correlation measurements or controls for general model capability. Notably, o3 performs best on the generated benchmark, whereas GPT-5 solves more external synthesis benchmarks (206 versus 190).

  5. Limited generalizability and differentiation from prior work. The benchmark focuses on a relatively restricted family of synthetic register-based languages, primarily involving arithmetic operations and simple loops. Whether the conclusions generalize to more realistic semantic constructs, such as branching, recursion, mutable memory, and complex data structures, remains unclear.

Questions for authors
  1. Can the authors demonstrate that the benchmark measures semantic understanding rather than arithmetic or computational complexity?

  2. How sensitive are the results to reasoning budgets and model configurations?

  3. How is semantic ambiguity handled in the inverse prediction tasks? In particular, how frequently do multiple substantially different semantic completions satisfy the five provided input-output examples?

  4. Can the authors provide stronger evidence that benchmark performance predicts practical program synthesis ability?

  5. Can the effects of loops and semantic complexity be isolated through matched experiments?

1 comment

We thank the reviewer for their comments.

  1. Semantic understanding vs. arithmetic/computational complexity?

We use arithmetic/computational complexity as a proxy for semantic complexity. In turn, this increasing semantic complexity makes it more difficult to understand the semantics. In our setting, we measure semantic understanding observationally - that is, if the model can successfully complete the tasks we ask.

  1. Sensitivity to model configurations?

We only evaluate the model’s default, out-of-the-box configuration. Varying model configurations would be an interesting future ablation study.

  1. Semantic ambiguity

Any predicted component (inputs, semantics, program) that produces the required output is counted as correct. Our benchmarks are generated with a single canonical example, but we expect that the LLM might (correctly) generate one of many correct solutions. Because our semantics meta-language is integer arithmetic including both addition and subtraction, there are, in general, an unbounded number of semantic completions that produce the correct answer. (In essence, it is program synthesis sub-problem.)

  1. Practical program synthesis ability?

Our setting is in formal, SMT-based semantics, so SemGuS problems represent a real, pre-existing set of synthesis benchmarks that fits within our setting.

  1. Loops, semantic complexity, and matched experiments?

Note that our loop and non-loop experiments are already matched. Both experiments are generated from identical sets of initial parameters, with the exception of whether or not loops are emitted.

Reviewer_y2ctOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents a benchmark for evaluating LLMs’ reasoning about program semantics. Each instance consists of four components (program, inputs, outputs, semantic) and asks the model to infer one component given the other three. The benchmark keeps the program grammar fixed while varying the semantics to test whether models can follow explicitly provided language definitions. The results show performance differences across models, also we can see a decline in accuracy as the expressions defining semantics become larger.

Critical strengths
  1. The benchmark generator is sound. It produces new instances with configurable difficulty and checks answers deterministically. The dataflow construction and filtering procedures also help reduce trivial examples and irrelevant computations.
  2. The evaluation is comprehensive and produce explainable results. The experiments in this paper covers different task types, expression sizes, loop constructs, and input formats
Critical weaknesses
  1. The novelty is limited. As I understand it, this paper does not clearly test a new capability, but rather a specific subset of existing capabilities. Such semantic reasoning is already involved in general code generation tasks, where generated code must satisfy the intended behavior. Many papers (such as [1], SemCoder, CRUXEval, and EquiBench) also investigate similar capabilities, although their task formats may differ.
  2. The evaluation includes only six older OpenAI models from 2025. Some already achieve near-perfect accuracy (even for large expression size has 60+) in the C-like format, which raises the question of whether state-of-the-art models (like GPT-6-Astra) is already saturated on this benchmark.
  3. The coverage is limited. The benchmark only considers simple loops. It does not cover more complex control-flow features, especially like conditional branches and memory operations.

[1] Can Large Language Models Reason about Program Invariants? — Kexin Pei et al., ICML 2023

Questions for authors
  1. What evidence shows that this benchmark reveals semantic reasoning failures or distinguishes model capabilities that differs from the previous work mentioned, given that program used in this work are actually simpler?
  2. Can the author report on SOTA models from different model providers? Also please try testing on some simple agents. Direct model input/output does not reveal the whole picture of its reasoning ability.
1 comment

We thank the reviewer for their comments.

  1. Distinguishing model capabilities differerent from the previous work mentioned

The key differentiator from the listed works is that our method removes clues to the program’s semantics from the program’s syntax. So, while our programs are certainly simpler, the program’s language (i.e., semantic interpretation) is complex and is all but guaranteed (by the random sampling of the semantics) to not be a language that the model has seen in its training data.

For example, Pei et al. evaluates Java programs - but do the models perform well because they “understand” the Java code, or simply because they were trained on a corpus of Java programs and are matching on the specific Java syntax? Our work is designed to remove the possibility of this syntactic matching by generating fresh semantics with a minimal syntax, letting us tease apart this gap.

We keep our target languages focused for ease of random sampling. Conditional branches are a sub-class of loops (i.e., a loop iterated zero or one times). Memory operations (corresponding to the theory of Arrays in our SMT-based setting) would be interesting to explore, but the existing SemGuS tooling we use does not yet support this theory.

  1. Other model providers and agents

Unfortunately, we only have access to models that run in batch mode in Microsoft Foundry. Only a subset of OpenAI models are available on this platform for batch mode. Evaluating more models from more vendors would certainly be an interesting extension; however, the core of this work is evaluating the benchmarks themselves as useful differentiators, not necessarily cataloging the performance of all models on those benchmarks.

We intentionally do not include agents. Agent harnesses are known to drastically improve performance, e.g. in tools like Claude Code or Codex. Our focus is just the capabilities of the models themselves, unentangled from the separate engineering of the agent harnesses. Comparing the models themselves to different agent harnesses would be an interesting future extension.

Reviewer_u1JTOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper asks whether LLMs understand program semantics and proposes a procedurally generated benchmark to test it. The syntax is fixed (sequences of statement labels over four registers), and each label’s meaning is a randomly sampled +/- assignment expression, optionally combined with a simple counted loop. Each instance has four components (semantics, program, input, output); the model is given three and must infer the fourth, and answers are checked automatically. Six OpenAI models are evaluated with answer-only prompts. Strong reasoning models do reasonably well, non-reasoning models score near zero, and accuracy drops as expression size grows. The authors also report that model rankings on 277 name-obfuscated SemGuS synthesis problems mirror the benchmark rankings and argue that the benchmark transfers to practical settings.

Critical strengths

[S1] Fixing the syntax while varying the semantics is a clean way to rule out surface-syntax shortcuts and training-data contamination.

[S2] The generator is automated, controllable, and solver-verified, so even tasks with multiple valid answers are graded exactly.

[S3] Rendering the same instances in both SemGuS and C formats is a sensible control for unfamiliar notation.

Critical weaknesses

[W1] The inference setup invalidates the main conclusions. Prompts require answer-only output with no chain of thought. Non-reasoning models (gpt-4.1, gpt-4.1-mini, gpt-5.1 in non-reasoning mode) must therefore mentally trace 10–20 statements, each with up to 79-symbol expressions, and emit five exact integers. Their near-0% scores are expected under these conditions and say nothing about semantic understanding. Reasoning models do think internally, so the headline “two-tier” result most plausibly separates models with a scratchpad from those without, not models that understand semantics from those that do not. The justification of measuring “inherent capabilities” is inconsistent: internal CoT is treated as inherent, while elicited CoT is treated as an external technique. Reasoning budgets are not reported, even though most failures of the strong models are abstentions the authors attribute to truncation.

[W2] The benchmark measures arithmetic bookkeeping, not “program semantics.” With only + and −, every statement simplifies to a linear combination of registers, and every loop-free program computes y = a·x1 + b·x2. Increasing expression size mainly increases the work of algebraic simplification and tracking values. Predict Input then reduces to solving one linear equation. Predict Semantics appears not to constrain the size of the answer expression, so short guesses can satisfy the examples; this may explain why weak models reach about 20% on this task while scoring about 0% elsewhere. Core semantic phenomena such as control flow, scoping, aliasing, evaluation order, side effects, and state beyond a few integer registers are absent. In general, there is a huge gap between the synthetic tasks in this paper and real program semantics.

[W3] The claims far exceed the evidence. The title and abstract pose a broad question about understanding versus pattern matching, but the experiments cannot separate a lack of understanding from a lack of computation budget, as the authors concede in their limitations. The abstract claims “a gap between coding ability and semantic understanding,” yet coding ability is never measured. The choice of the four tasks rests on intuition and formal symmetry; there is no argument that they are sufficient or that each actually probes real coding semantics.

[W4] The transfer evidence is weak. The link to “practical settings” rests on six single-vendor models whose rankings agree across two tasks. With models falling into two clear tiers, this agreement is almost guaranteed and is compatible with general capability alone. No correlation statistic, per-instance analysis, or control for general coding ability is reported. The “realistic” tasks are small academic SemGuS problems whose names have been obfuscated, which makes them less realistic rather than more.

Questions for authors

No questions at this time.

1 comment

We thank the reviewer for their comments, and we make the following notes:

The two-tier structure of reasoning vs non-reasoning is certainly not unexpected. While a model’s internal reasoning is similar to an external chain-of-thought process, it is still a part of the model, baked in by the vendors, and it is important to consider it as out-of-the-box functionality. It is within these two tiers that differences between similarly-equipped models emerge - for example, the difference between o3 and gpt-5, or the similarity between gpt-5.1 (non-reasoning) and gpt-4.1-mini.

…there is a huge gap between the synthetic tasks in this paper and real program semantics.

Our focus is on formally specified semantics. While this does leave out many features found in existent programming language, it allows us to dramatically simplify the benchmark generation process while meeting our goals of separating the language’s syntax and semantics. In particular, despite their simplicity, our benchmarks do successfully differentiate model performance.

We suggest that, if a model can successfully simplify the program to a linear expression, that this does demonstrate understanding of the semantics. Admittedly, the Predict Semantics task is noisy from successful small-size guesses, but the results are still correlated with success on the other tasks. We will improve this framing.

It would be an interesting future work to extend to additional primitives in our semantics meta-language, and see if different models struggle more or less with different parts.

The abstract claims “a gap between coding ability and semantic understanding,”

Our usage of “coding ability” refers to syntactic understanding - from the syntax, all programs in our benchmark set are drawn from fixed syntax. The gap is that the model success drops as the semantic difficulty is raised, while the syntactic difficulty is fixed. We will clarify this point.

The “realistic” tasks are small academic SemGuS problems whose names have been obfuscated, which makes them less realistic rather than more.

Our setting is in formal, SMT-based semantics, so SemGuS problems represent a real, pre-existing set of synthesis benchmarks that fits within our setting. Obfuscating the names is essential; otherwise, the models will fall back on syntactic pattern-matching (e.g., assuming a production named + represents addition).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.