# Code Simulation Challenges for Large Language Models

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 78 references that are in the map.
- First posted on arXiv 17 Jan 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [BLOOM: A 176B-Parameter Open-Access Multilingual Language Model](https://mlsanity.com/paper/2211.05100/) (2022)
- [Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?](https://mlsanity.com/paper/2202.12837/) (2022)
- [Code as Policies: Language Model Programs for Embodied Control](https://mlsanity.com/paper/2209.07753/) (2022)
- [Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting](https://mlsanity.com/paper/2305.04388/) (2023)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [The Reversal Curse: LLMs trained on "A is B" fail to learn "B is A"](https://mlsanity.com/paper/2309.12288/) (2023)
- [Large Language Models for Software Engineering: A Systematic Literature Review](https://mlsanity.com/paper/2308.10620/) (2023)
- [Detecting Pretraining Data from Large Language Models](https://mlsanity.com/paper/2310.16789/) (2023)
- [Who's Harry Potter? Approximate Unlearning in LLMs](https://mlsanity.com/paper/2310.02238/) (2023)
- [Learning Deep Transformer Models for Machine Translation](https://mlsanity.com/paper/1906.01787/) (2019)
- [Mathematical Capabilities of ChatGPT](https://mlsanity.com/paper/2301.13867/) (2023)
- [Emergent Analogical Reasoning in Large Language Models](https://mlsanity.com/paper/2212.09196/) (2022)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [Machine Theory of Mind](https://mlsanity.com/paper/1802.07740/) (2018)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solve](https://mlsanity.com/paper/2309.13638/) (2023)

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

- [The Landscape of Agentic Reinforcement Learning for LLMs: A Survey](https://mlsanity.com/paper/2509.02547/) (2025)
- [Reasoning Runtime Behavior of a Program with LLM: How Far Are We?](https://mlsanity.com/paper/2403.16437/) (2024)
- [Graph-enhanced Large Language Models in Asynchronous Plan Reasoning](https://mlsanity.com/paper/2402.02805/) (2024)
- [EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking](https://mlsanity.com/paper/2502.12466/) (2025)
- [CodeARC: Benchmarking Reasoning Capabilities of LLM Agents for Inductive Program Synthesis](https://mlsanity.com/paper/2503.23145/) (2025)
- [A Tool for In-depth Analysis of Code Execution Reasoning of Large Language Models](https://mlsanity.com/paper/2501.18482/) (2025)
- [Code Simulation as a Proxy for High-order Tasks in Large Language Models](https://mlsanity.com/paper/2502.03568/) (2025)
- [L0-Reasoning Bench: Evaluating Procedural Correctness in Language Models via Simple Program Execution](https://mlsanity.com/paper/2503.22832/) (2025)
- [Can LLMs Reason Structurally? Benchmarking via the Lens of Data Structures](https://mlsanity.com/paper/2505.24069/) (2025)
- [Demystifying Errors in LLM Reasoning Traces: An Empirical Study of Code Execution Simulation](https://mlsanity.com/paper/2512.00215/) (2025)
- [Can Language Models Pretend Solvers? Logic Code Simulation with LLMs](https://mlsanity.com/paper/2403.16097/) (2024)
- [LogicIF: Towards Complex Logic Instruction Following](https://mlsanity.com/paper/2508.09125/) (2025)
- [Computational Reasoning of Large Language Models](https://mlsanity.com/paper/2504.20771/) (2025)
- [Can Large Language Models Generalize Procedures Across Representations?](https://mlsanity.com/paper/2602.03542/) (2026)
- [Evaluating Exact Output and Checkpoint-State Prediction in Real Programs](https://mlsanity.com/paper/2610.11889/) (2026)

## Abstract (arXiv)

Many reasoning, planning, and problem-solving tasks share an intrinsic algorithmic nature: correctly simulating each step is a sufficient condition to solve them correctly. This work studies to what extent Large Language Models (LLMs) can simulate coding and algorithmic tasks to provide insights into general capabilities in such algorithmic reasoning tasks. We introduce benchmarks for straight-line programs, code that contains critical paths, and approximate and redundant instructions. We further assess the simulation capabilities of LLMs with sorting algorithms and nested loops and show that a routine's computational complexity directly affects an LLM's ability to simulate its execution. While the most powerful LLMs exhibit relatively strong simulation capabilities, the process is fragile, seems to rely heavily on pattern recognition, and is affected by memorisation. We propose a novel off-the-shelf prompting method, Chain of Simulation (CoSm), which instructs LLMs to simulate code execution line by line/follow the computation pattern of compilers. CoSm efficiently helps LLMs reduce memorisation and shallow pattern recognition while improving simulation performance. We consider the success of CoSm in code simulation to be inspirational for other general routine simulation reasoning tasks.