mlsanityData to 14 Oct 2026

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

arXiv 2509.25073 ↗First posted 29 Sep 2025cs.CLcited by 0

Not on the map. Why?

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.

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

15 of 17 references.

References · 15

  1. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,703
  2. 2021Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolationcited by 1,103
  3. 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 327
  4. 2022Neural Networks and the Chomsky Hierarchycited by 217
  5. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  6. 2014Learning to Executecited by 106
  7. 2023Physics of Language Models: Part 1, Learning Hierarchical Language Structurescited by 83
  8. 2023Exposing Attention Glitches with Flip-Flop Language Modelingcited by 75
  9. 2025Forgetting Transformer: Softmax Attention with a Forget Gatecited by 53
  10. 2024Length Generalization of Causal Transformers without Position Encodingcited by 47
  11. 2025PaTH Attention: Position Encoding via Accumulating Householder Transformationscited by 34
  12. 2025Long-Context Generalization with Sparse Attentioncited by 21
3 more
  1. 2025SWAN-GPT: An Efficient and Scalable Approach for Long-Context Language Modelingcited by 19
  2. 2024Scaling Stick-Breaking Attention: An Efficient Implementation and In-depth Studycited by 13
  3. 2025L0-Reasoning Bench: Evaluating Procedural Correctness in Language Models via Simple Program Executioncited by 5

Built on by

Not cited yet.