acceptodds
Under review as a conference paper at ICLR 2027

Representation Sensitivity in Symbolic Execution by Large Language Models

Abstract

Large language models can execute symbolic procedures yet remain sensitive to how those procedures are represented. We study this gap using 256 deterministic table-execution programs with exact gold states. In the primary intervention, programs, table values, initial states, and decoding settings are fixed; only the names of row and column roles change. On gpt-oss-120b, replacing overlapping A/B role labels with disjoint P/Q labels raises accuracy from 82.4–86.7% to 98.0–98.8% across three sampling seeds. The direction persists under reversed condition order and across tested Qwen configurations. A subsequent 2×2 experiment crosses A/B versus W/X role labels with A–D versus W–Z value alphabets, preserving computations under a consistent symbol renaming. Across two sampling seeds, the preferred label pair reverses with the value alphabet: overlapping labels produce more errors within both alphabets. Mean within-alphabet overlap penalties are 7.81 and 10.94 percentage points, with paired bootstrap 95% intervals of [3.91, 11.72] and [7.03, 14.84]. All primary and crossed responses terminate naturally and are syntactically valid. A selected 12-root diagnostic cohort localizes the first visible error in ten failing traces to table-cell lookups. These results establish representation sensitivity and a replicated label–alphabet interaction in the tested setting, while leaving internal mechanisms unresolved. They motivate evaluating representation robustness alongside nominal symbolic-execution accuracy.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
large language models, symbolic reasoning, representation robustness, symbolic execution, LLM evaluation, reasoning reliability

Reviews

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

The paper studies whether LLM execution of a fully specified symbolic procedure stays the same when the representation changes but the semantics do not. The authors build EXACTBENCH-RENDER, and a deterministic oracle and a strict parser grade every answer. The primary experiment compares overlapping row/column role labels (A/B) with disjoint labels (P/Q), while keeping the underlying program semantics, lookup tables, initial states, and decoding parameters unchanged. The paper concludes that symbolic-execution reliability depends not only on the underlying computation but also on its textual representation, motivating representation-robustness evaluation alongside conventional accuracy measurements.

Critical strengths
  1. Good writing and logic chain, figures show the clear results.
  2. The paper's main strength is its carefully controlled paired experimental design. By changing only the row/column role labels while preserving program semantics, table contents, initial states, and gold outputs.
  3. It moves beyond demonstrating that one particular label pair performs better than another and reveals a replicated interaction between role labels and value symbols.
Critical weaknesses
  1. In the crossed design, a pure overlap account predicts that A/B labels improve when the values move to W–Z. They do not: A/B on A–D (overlap) gives 12.5%/14.1%, while A/B on W–Z (disjoint) gives 13.3%/13.3%.
  2. In a 2×2 design, the “overlap” contrast is aliased with the label×alphabet interaction.
Questions for authors
  1. Have the authors evaluated the representation intervention on independently generated programs that do not inherit the dynamic-parent selection procedure?
  2. Does the effect persist in a realistic serialisation where field names collide with values or at higher reasoning effort?
  3. Could directly estimate run-to-run variance directly, for example with five or more repeated runs of LEGACY and P/Q under one configuration?
Reviewer_WujgOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper uses symbolic procedures execution to measure LLM sensitivity to specific symbols in program definition. The authors build a synthetic small table-lookup programs (that have deterministic, easy to calculate answers) - then change only the labels printed on the table axes, comparing labels that reuse the same letters as the table values against labels that don’t. Overlapping labels seem to make models less reliable - shown on 2 sets of symbols (A/B, W/X).

Critical strengths
  • An exact and very focused intervention - allowing in principle for a high-fidelty experiment to isolate the effect.

  • Honest representation of the discovery process - notably including the failed attempts with Gemma and Mistral.

Critical weaknesses
  • Narrow evidential base. The 256 were generated once, and filtered, then used throught all experiments. Only 1 reasoning level was used. only 2 model families. No charaacterization regarding the interinsic noise of the performance - regardless of labeling. The models which were tested and discarded due to high performance - why not just generate longer programs? Or larger lookup tables? This would strenghen your claims on the 2 measured families as well.

  • The main point of the paper, the symbol “overlap” as the source of failures, is still not proven very well. Specifically Fig 2 in Appendix B shows that A/B doesn't change performance between A-D and W-Z values. The idea that W-Z values are inherently harder to understand + same symbol labeling reduces performance + the effects cancel each other almost perfectly - requires much stronger evidence.

Questions for authors
  • Why do you define SWITCH if its not used? Sounds like needless noise? What is the goal of Hold for that matter?

  • Why is the A/B called legacy?

  • Appendix B fig 2 shows that A/B labels are not sensitive to the values used? But W/X are very sensitive?

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

The paper builds a synthetic task (EXACTBENCH-RENDER) where an LLM has to run a short program by hand using three 4x4 lookup tables over {A,B,C,D}, three registers and a mode bit, and output the final state which is checked exactly against an oracle. Only the axis labels around the tables change b/w conditions... LEGACY writes rows as "A=A, A=B, ..." and columns as "B=A, B=B, ..." so the label names are also values, and P/Q writes "P=A, ..." and "Q=A, ...". On the same 256 programs, gpt-oss-120b at low effort has 13.3 to 17.6% error with LEGACY vs 1.2 to 2.0% with P/Q over 3 seeds (one with reversed run order), and Qwen3.8-27B (Q4/Q8) shows the same direction with a smaller gap (6.3 to 7.8% vs 0.8 to 2.7%). A 2x2 follow up on gpt-oss crosses A/B vs W/X labels with A-D vs W-Z values and finds the overlapping pair is worse in both alphabets (mean overlap effect 7.81% and 10.94% over 2 seeds). Paper also has a small trace study on 12 selected programs where all 10 LEGACY failures start with a wrong table cell value.

Critical strengths

1- Clear paired setup... inside each pair the tables, program, start state, gold state and sampling settings are the same, and all primary and crossed answers finish normally and parse. Gap may not come from truncation, parser bugs or fuzzy scoring, which is the problem Hua et al. (2025) raise for prompt sensitivity work.

2- The crossed label/alphabet test is well designed (all 4 conditions run together for each program with balanced orders, 2 seeds) and shows the label effect depends on the value alphabet.. W/X is better than A/B on A-D values and worse on W-Z values in both seeds. Authors also report the failed Mistral/Gemma pilots and how the effect was first found (adaptive discovery on Qwen seed 17). This is good and and makes the claims easier to check.

Critical weaknesses

1- Many findings are already known in literature.. so its hard for me to find the new knowledge after reading the paper. That format and naming changes which keep the meaning can still move LLM accuracy is well known (Sclar et al. 2024, Mizrahi et al. 2024, Narin 2024). For execution style tasks, Orvalho & Kwiatkowska (arXiv 2505.10443) show predictions change under variable renaming on CRUXEval and LiveCodeBench, and Spiess et al. report GPT-5.2 going from 99.24% to 75.75% on CRUXEval after renaming. Errors from using one symbol as both a name and a value are also close to work on interference and binding.. proactive interference in key-value tracking, binding IDs, variable binding in symbolic program and sporadic lookup errors in flip-flop tasks. None of these are discussed/mentioned in the paper. Also the LEGACY prompt never says what "A=" and "B=" in the headers mean (the contract in App. A only says "use x as the ROW label and y as the COLUMN label"), so the model has to guess the notation, and the paper agrees its not "a realistic table format". So the finding is mostly "an undefined header notation where names equal values gives more lookup errors in one synthetic task", and the agent interface motivation (Sec 2.2, Sec 7) is not tested on JSON, CSV or tool outputs. Please clarify.

2- The evidence is very narrowed. 1 task, the same 256 programs for every seed and model, 2 model families (both run locally via llama.cpp, Qwen only quantized) and only low reasoning effort, even though both models have higher levels (medium/high for gpt-oss, medium/xhigh for Qwen3.8). LEGACY answers are already 1.5x longer (536 vs 356 tokens), so the model is working harder on them and more reasoning may fix most of the gap. "Replication across seeds" is just resampling the same prompts at T = 1.0.. new programs from a new generator seed would be a real replication but its not done in the paper. Also the main LEGACY and P/Q runs were separate batches, and the exact same LEGACY prompt gave 45 vs 36 errors in two runs with the same seed. For Qwen the gaps are 3.5 to 5.9%, which is about this size. Pl clarify..

Questions for authors

1- Please clarify all the novelties/new findings compared to the papers above - a clear distinguish b/w what was already known and whats specific/new to your paper.

2- Can you run LEGACY vs P/Q on gpt-oss-120b at medium and high effort (and Qwen3.8 at medium/xhigh), on a new set of programs from a new generator seed, with both formats run together for each program? ANd does the gap stay?

3- If you add one sentence that defines the headers (row "A=v" means x = v, column "B=v" means y = v), does the gap fix?

4- [Only if possible in the given time frame as I understand authors can have cost issues or timing issues and this does not affect my overall score recommendation] Can you add more models (one or two API reasoning models, another open model, Qwen3.8 with thinking off), and test one realistic format like a CSV/markdown table or JSON where a key name equals a cell value?

5- Can you take several samples per program (like 10), report greedy decoding too, and fit a model with a program level random effect? Is the gap driven by a few programs (at least 7 failed LEGACY in all 3 gpt-oss seeds)?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.