# LLMs Lean on Priors, Not Programming Language Semantics

arXiv: https://arxiv.org/abs/2510.03415 · HTML: https://mlsanity.com/paper/2510.03415/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 33 of its 74 references that are in the map.
- First posted on arXiv 3 Oct 2025.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 30 of 33)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [ImageNet-trained CNNs are biased towards texture; increasing shape bias improves accuracy and robustness](https://mlsanity.com/paper/1811.12231/) (2018)
- [Qwen2.5-Coder Technical Report](https://mlsanity.com/paper/2409.12186/) (2024)
- [Beyond Accuracy: Behavioral Testing of NLP models with CheckList](https://mlsanity.com/paper/2005.04118/) (2020)
- [Right for the Wrong Reasons: Diagnosing Syntactic Heuristics in Natural Language Inference](https://mlsanity.com/paper/1902.01007/) (2019)
- [BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions](https://mlsanity.com/paper/2406.15877/) (2024)
- [CodeGeeX: A Pre-Trained Model for Code Generation with Multilingual Benchmarking on HumanEval-X](https://mlsanity.com/paper/2303.17568/) (2023)
- [CRUXEval: A Benchmark for Code Reasoning, Understanding and Execution](https://mlsanity.com/paper/2401.03065/) (2024)
- [Stress Test Evaluation for Natural Language Inference](https://mlsanity.com/paper/1806.00692/) (2018)
- [CWM: An Open-Weights LLM for Research on Code Generation with World Models](https://mlsanity.com/paper/2510.02387/) (2025)
- [NExT: Teaching Large Language Models to Reason about Code Execution](https://mlsanity.com/paper/2404.14662/) (2024)
- [CodeI/O: Condensing Reasoning Patterns via Code Input-Output Prediction](https://mlsanity.com/paper/2502.07316/) (2025)
- [Reasoning Runtime Behavior of a Program with LLM: How Far Are We?](https://mlsanity.com/paper/2403.16437/) (2024)
- [Measuring The Impact Of Programming Language Distribution](https://mlsanity.com/paper/2302.01973/) (2023)
- [CRUXEval-X: A Benchmark for Multilingual Code Reasoning, Understanding and Execution](https://mlsanity.com/paper/2408.13001/) (2024)
- [Emergent Representations of Program Semantics in Language Models Trained on Programs](https://mlsanity.com/paper/2305.11169/) (2023)
- [TRACED: Execution-aware Pre-training for Source Code](https://mlsanity.com/paper/2306.07487/) (2023)
- [EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking](https://mlsanity.com/paper/2502.12466/) (2025)
- [Beyond Instruction Following: Evaluating Inferential Rule Following of Large Language Models](https://mlsanity.com/paper/2407.08440/) (2024)
- [EffiCoder: Enhancing Code Generation in Large Language Models through Efficiency-Aware Fine-tuning](https://mlsanity.com/paper/2410.10209/) (2024)
- [CodeARC: Benchmarking Reasoning Capabilities of LLM Agents for Inductive Program Synthesis](https://mlsanity.com/paper/2503.23145/) (2025)
- [Semantic Sensitivities and Inconsistent Predictions: Measuring the Fragility of NLI Models](https://mlsanity.com/paper/2401.14440/) (2024)
- [What can Large Language Models Capture about Code Functional Equivalence?](https://mlsanity.com/paper/2408.11081/) (2024)
- [Large Language Models as Code Executors: An Exploratory Study](https://mlsanity.com/paper/2410.06667/) (2024)
- [CoCoNUT: Structural Code Understanding does not fall out of a tree](https://mlsanity.com/paper/2501.16456/) (2025)
- [Evaluating the Generalization Capabilities of Large Language Models on Code Reasoning](https://mlsanity.com/paper/2504.05518/) (2025)

## Built on by (most cited first, 6 of 6)

- [Self-Execution Simulation Improves Coding Models](https://mlsanity.com/paper/2604.03253/) (2026)
- [CordisBench: Can Language Models Reason About Component Lifecycles in Dynamic Agent Harnesses?](https://mlsanity.com/paper/2609.01600/) (2026)
- [Predicting Program Exit Code with LLMs and Programming Language Semantics](https://mlsanity.com/paper/2609.00579/) (2026)
- [Retrofitting Code Using LLMs to Support Exceptional Behavior](https://mlsanity.com/paper/2609.10397/) (2026)
- [From Verification Failures to Reusable Guidance for Coding Agents](https://mlsanity.com/paper/2609.39022/) (2026)
- [Natural Code Transformation Confuses Agents in Vulnerability Analysis](https://mlsanity.com/paper/2610.14350/) (2026)

## Abstract (arXiv)

Recent work asks whether large language models (LLMs) condition their reasoning on explicit rules rather than statistical regularities from pretraining. Program execution provides a canonical instance: formal semantics define behavior through symbolic transition rules that can be systematically altered under distribution shift. We investigate whether LLMs can condition their reasoning on formal semantics through program execution and introduce PLSemanticsBench, pairing featherweight C programs with two semantic systems -- small-step operational semantics and K semantics -- and probing four capabilities: composing rules for final states, selecting rules when state is unmutated, sustaining such conditioning over long traces, and following supplied rules under novel semantics. To decouple semantic reasoning from syntactic familiarity, we redefine familiar operators to induce symbol-meaning conflict and introduce novel symbols defined only through the supplied rules, and stress-test models on Human-Written, LLM-Translated, and Fuzzer-Generated splits with increasing structural complexity. Across 11 frontier LLMs, strong final-state accuracy under standard semantics (up to 90%) drops sharply -- by as much as 40--60% points -- under semantic mutations and increasing structural complexity. Only a handful of models achieve non-zero long-horizon conditioning accuracy, and even the best systems reach just 35%. Together, these results suggest that contemporary LLMs often rely on pretrained lexical associations rather than systematically conditioning on supplied formal rules. PLSemanticsBench is publicly available at https://EngineeringSoftware.github.io/PLSemanticsBench.