# An empirical study on the limitation of Transformers in program trace generation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 17 references that are in the map.
- First posted on arXiv 29 Sep 2025.

## Builds on (most cited first, 15 of 15)

- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [The Impact of Positional Encoding on Length Generalization in Transformers](https://mlsanity.com/paper/2305.19466/) (2023)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Learning to Execute](https://mlsanity.com/paper/1410.4615/) (2014)
- [Physics of Language Models: Part 1, Learning Hierarchical Language Structures](https://mlsanity.com/paper/2305.13673/) (2023)
- [Exposing Attention Glitches with Flip-Flop Language Modeling](https://mlsanity.com/paper/2306.00946/) (2023)
- [Forgetting Transformer: Softmax Attention with a Forget Gate](https://mlsanity.com/paper/2503.02130/) (2025)
- [Length Generalization of Causal Transformers without Position Encoding](https://mlsanity.com/paper/2404.12224/) (2024)
- [PaTH Attention: Position Encoding via Accumulating Householder Transformations](https://mlsanity.com/paper/2505.16381/) (2025)
- [Long-Context Generalization with Sparse Attention](https://mlsanity.com/paper/2506.16640/) (2025)
- [SWAN-GPT: An Efficient and Scalable Approach for Long-Context Language Modeling](https://mlsanity.com/paper/2504.08719/) (2025)
- [Scaling Stick-Breaking Attention: An Efficient Implementation and In-depth Study](https://mlsanity.com/paper/2410.17980/) (2024)
- [L0-Reasoning Bench: Evaluating Procedural Correctness in Language Models via Simple Program Execution](https://mlsanity.com/paper/2503.22832/) (2025)

## Abstract (arXiv)

We study Transformers on the task program trace generation (PTG), where models produce step-by-step execution traces for synthetic programs. Unlike existing algorithmic problems, PTG externalizes reasoning through long traces where each step is trivial. We train small Transformers with diverse modifications, including alternative position encodings, softmax replacements, hybrid model, and short convolutions. While these models achieve strong in-distribution accuracy, they exhibit systematic failures when generalizing to various factors (e.g., program length, trace steps), though some designs significantly improve generalization.