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.
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.
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