- 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
-
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.
-
The automated generation pipeline supports controlled variation in semantic expression size and program structure.
-
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
-
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.
-
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.
-
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.
-
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).
-
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
-
Can the authors demonstrate that the benchmark measures semantic understanding rather than arithmetic or computational complexity?
-
How sensitive are the results to reasoning budgets and model configurations?
-
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?
-
Can the authors provide stronger evidence that benchmark performance predicts practical program synthesis ability?
-
Can the effects of loops and semantic complexity be isolated through matched experiments?
We thank the reviewer for their comments.
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.
We only evaluate the model’s default, out-of-the-box configuration. Varying model configurations would be an interesting future ablation study.
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.)
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.
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.