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

Simeng SunarXiv 2025 · DOI · arXiv

Abstract

Transformers have revolutionized natural language processing, yet their ability to perform systematic algorithmic reasoning remains a subject of intense scrutiny. This study investigates Program Trace Generation (PTG)—the task of executing code step-by-step to produce an intermediate state log. We demonstrate that while Transformers can master specific program distributions, they struggle with "contextual flexibility," failing to generalize when programs become longer or execution traces extend beyond training lengths. We evaluate various architectural modifications, finding that specific inductive biases like NaPE (a hybrid of NoPE and ALiBi) and 1D convolutions can mitigate some of these failures.

Introduction

Program Trace Generation (PTG) requires a model to take a program and its inputs and output a complete, step-by-step execution trace. This task is a rigorous test of a model's ability to maintain procedural correctness over time. Unlike standard algorithmic tasks where complexity is tied to input size, PTG separates the "algorithm" (the code) from the "data" (the inputs), allowing for a granular analysis of how Transformers handle sequential logic. The core question is whether a Transformer can maintain "procedural correctness" as programs grow in length, complexity, or execution time.

Example of a synthetic program and its corresponding step-by-step execution trace used in the PTG task.

Methodology

The researchers trained small Transformers (~154M parameters) on a synthetic benchmark based on L0-Bench. The programs included assignments, arithmetic, loops, and list operations. To improve generalization, several architectural variants were tested, including:

  • Alternative Position Encodings: RoPE, NoPE, ALiBi, and the hybrid NaPE (mixing NoPE and ALiBi heads).
  • Softmax Replacements: STB (stick-breaking attention) and $\alpha$-entmax (sparse attention).
  • Structural Changes: Canon (adding short 1D convolutions) and SWAN (a hybrid of sliding window and global attention).

Models were trained for 20k steps to reach near-perfect in-distribution (ID) performance before being tested on out-of-distribution (OOD) scenarios involving longer programs, longer traces, more variables, and longer lists.

Results and Discussion

The primary finding is a significant "Generalization Gap." Models that achieve near-perfect accuracy on in-distribution programs often fail when faced with OOD scenarios. The researchers measured whole-trace accuracy, where a single mistake in a long sequence results in a total failure.

Accuracy across different evaluation splits (ID and OOD) as training progresses. While ID performance reaches near 100%, OOD tasks like Longer Trace and Longer Programs show significantly lower plateaus, exposing the generalization gap.

As shown in the experimental results, while ID performance reaches 100% rapidly, OOD tasks like "Longer Trace" and "Longer Programs" show much lower plateaus for the baseline models. However, specific architectural choices proved beneficial:

Model ID (Mid) Longer Traces (Extensive) Longer Programs
NoPE (Baseline) 99.0% 14.2% 46.5%
NaPE 98.3% 93.5% 57.4%
NoPE + Canon 100.0% 35.3% 64.8%

NaPE was a standout performer, maintaining over 90% accuracy on longer execution traces, whereas most other models dropped below 40%. Additionally, Canon (1D convolutions) significantly improved performance on longer programs, suggesting it helps the model track the "instruction memory" of the code. Conversely, standard RoPE struggled with longer lists, suggesting that standard positional embeddings are a bottleneck for handling larger data structures.

Conclusion

Transformers face fundamental challenges in maintaining global state and procedural logic over extended sequences. While architectural tweaks like NaPE and Canon offer promising improvements for specific types of generalization, the "contextual flexibility" required for robust program execution remains an open challenge. Future work will explore if larger models or different architectures, such as Mixture-of-Experts, can bridge this generalization gap in more complex, nested logic settings.

Summary updated

Abstract

We study Transformers on the task \emph{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.
BibTeX
@misc{sun2025empirical,
  author = {Simeng Sun},
  title = {{An empirical study on the limitation of Transformers in program trace generation}},
  year = {2025},
  eprint = {2509.25073},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.25073},
}
Figure