PaperlayerView exact revision on arXiv

Source-linked AI summary

What I cannot execute, I do not understand: Training and Evaluating LLMs on Program Execution Traces

Jordi Armengol-Estapé, Quentin Carbonneaux, Tianjun Zhang, Aram H. Markosyan, Volker Seeker, Chris Cummins, Melanie Kambadur, Michael F. P. O'Boyle, Sida Wang, Gabriel Synnaeve, Hugh James Leather

arXiv:2503.05703v1cs.LGcs.AIcs.PL

TL;DR

Code datasets typically treat code as static strings and rarely use information about program execution. Execution Tuning trains models on program traces without manual test annotations; trace-trained models outperform direct prediction on CruxEval, and dynamic scratchpads succeed on executions up to 14k steps.

  • Problem

    Code datasets typically treat programs as static strings and rarely exploit execution information, leaving questions about trace-data scale, granularity, long executions, scratchpad design, and downstream effects open.

    Source: §1 · pp. 1–2

  • Method

    Execution Tuning models real-world program traces without manual test annotations and compares direct, line-level, and instruction-level representations with several scratchpad strategies.

    Source: §1 · p. 2, §2.2 · p. 4

  • Results

    Trace-trained models outperform direct-output models on CruxEval, and dynamic scratchpads succeed on executions up to 14k steps.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Automatically generated inputs scale trace modeling, which generalizes to output-prediction benchmarks; dynamic scratchpads excel on very long executions.

    Source: §6 · p. 10

    Most CruxEval errors involve string indexing or basic string manipulation, with arbitrary-string indexing difficult because of tokenization artifacts.

    Source: §3.2 · p. 7

Abstract

from arXiv · show

Code generation and understanding are critical capabilities for large language models (LLMs). Thus, most LLMs are pretrained and fine-tuned on code data. However, these datasets typically treat code as static strings and rarely exploit the dynamic information about their execution. Building upon previous work on trace modeling, we study Execution Tuning (E.T.), a training procedure in which we explicitly model real-world program execution traces without requiring manual test annotations. We train and evaluate models on different execution trace granularities (line and instruction-level) and strategies on the task of output prediction, obtaining around 80% accuracy on CruxEval and MBPP, and showing the advantages of dynamic scratchpads (i.e., self-contained intermediate computations updated by the model rather than accumulated as a history of past computations) on long executions (up to 14k steps). Finally, we discuss E.T.'s practical applications.

1 INTRODUCTION

Code datasets usually treat programs as static strings and rarely use execution information, despite code’s executable nature. The paper introduces Execution Tuning to model program traces at multiple granularities and compares scratchpad strategies, including dynamic scratchpads, for output prediction.

1 INTRODUCTION

  • Code datasets typically treat programs as static strings and rarely exploit execution information, leaving code-execution reasoning underrepresented.The introduction identifies whether and how trace modeling affects downstream code generation as an open question.Source: §1 · pp. 1–2
  • Execution Tuning models real-world program traces without manual test annotations, using automatically generated inputs for about 300k Python functions.The approach studies direct-output, line-level, and bytecode-instruction-level representations.Source: §1 · p. 2
  • The study compares regular and compact scratchpads with dynamic scratchpads, which update one self-contained representation of the current program state rather than accumulating execution history.The introduction frames trace-data scale, granularity, long executions, scratchpad design, and downstream code generation as open questions.Source: §1 · pp. 1–2
  • Trace-trained models outperform direct-output models on CruxEval, while dynamic scratchpads succeed on executions up to 14k steps and can reduce required intermediate steps from 14k to 1.5k.The paper also reports greater disparity between tracing strategies on MBPP functions with nested loops.Source: §1 · p. 2

2 EXECUTION TUNING

Execution Tuning collects executable Python functions, traces their runs, and converts those traces into model-training examples. It varies trace granularity and scratchpad representation, including a dynamic state that can be updated or advanced across multiple steps.

2 EXECUTION TUNING

  • E.T.’s pipeline turns executable Python functions and generated inputs into structured traces, then trains models using different trace representations.The tracer-generated dataset follows input generation and test-quality filtering.Source: Figure 2 · p. 3, §2.1 · p. 3

2.1 TRACES COLLECTION

  • Automatically generated inputs yield about 300k executable functions and more than 1.5M executions, without manually written unit tests.Inputs come from LLM-generated tests and fuzzing, with runtime-error cases discarded and test quality filtered using coverage and similarity.Source: §2.1 · p. 3
  • The custom tracer captures Python call, return, line, and opcode events, plus globals, stack state, and instruction-level changes.It steps into user-defined auxiliary functions, excludes imported-module functions, and ignores C events to avoid source-inaccessible trace noise.Source: §2.1 · p. 3

2.2 TRACES REPRESENTATION

  • The study compares direct output prediction with line-level states and instruction-level bytecode states, which also expose the stack to the model.Python repr is used to represent objects; source code appears as inline comments at the first opcode for its line.Source: §2.2 · p. 4
  • Dynamic scratchpads update one self-contained state and can train the model to predict a state after N steps, unlike history-accumulating scratchpads.Because execution history no longer carries implicit information, iterator states are explicitly encoded using stack-derived iteration counts.Source: §2.2 · p. 4

3 OUTPUT PREDICTION RESULTS

The section evaluates output prediction as a proxy for code reasoning on CruxEval, nested-loop MBPP, and long algorithmic executions. Trace-trained models outperform direct output prediction, while dynamic scratchpads show advantages on long executions.

3.1 INDIVIDUAL STATE PREDICTIONS ON CRUXEVAL

  • Dynamic scratchpads achieve 99.5% line-level and 99.9% instruction-level control-flow accuracy; multi-step prediction remains feasible, though variables and returns become harder.For Line-N, accuracy and confidence decline as the prediction horizon grows, without sharp performance drops.Source: §3.1 · pp. 5–6
  • On individual CruxEval states, instruction-level models reach 98.8% full-state accuracy, versus 96.3% for line-level dynamic scratchpads and 86.4% for Scratchpad.Prompted Llama reaches 10.6% full-state accuracy with Line-1.Source: Table 1 · p. 5, §3.1 · p. 6

3.2 CRUXEVAL OUTPUT PREDICTION

  • Trace-trained models outperform direct output-prediction fine-tuning on CruxEval, reaching up to almost 80% accuracy.Aggregating trace predictions can lower accuracy because a single error in a multi-step execution can produce a wrong output.Source: Table 2 · p. 6, §3.2 · p. 7
  • On CruxEval’s short executions, compact and full scratchpads outperform dynamic scratchpads; indexing and basic string manipulation account for many errors.Dynamic scratchpads lag line-level Scratchpad by about 5% on output prediction, mainly due to string indexing.Source: §3.2 · p. 7
  • Selecting the most confident multi-step prediction yields reasonable CruxEval accuracy with fewer steps; Line-n averages 35% of Line-1’s steps for correct predictions.The most confident horizon is not always the immediate next step.Source: §3.2 · p. 7

3.3 MBPP

  • On the nested-loop MBPP subset, instruction-based models perform considerably better than on CruxEval, and stepping into auxiliary functions raises compact-scratchpad accuracy from 77.4% to 80.6%.The selected executions average about seven times as many executed lines as CruxEval.Source: §3.3 · p. 7, Table 3 · p. 8

3.4 LONG EXECUTIONS

  • On Collatz, Line-n matches Line-1 accuracy with 39% of its steps; on Fibonacci at n = 103, it reduces steps from 414 to 160.These tasks test executions longer than those typically found in CruxEval and MBPP.Source: §3.4 · pp. 8–9
  • For the 4-bit binary counter at n = 3038, Line-1 chains 14,055 correct predictions, while confidence-based Line-n path selection is unreliable.With Dijkstra search, Line-n predictions would reach perfect accuracy using 17% of Line-1’s average steps.Source: §3.4 · pp. 8–9, Table 4 · p. 8

4 DOWNSTREAM EFFECTS

Adding Execution Tuning (E.T.) traces to supervised fine-tuning yields little coding-benchmark improvement, though the best-performing trace variant brings slight gains on HumanEval and MBPP and 1.2 points on GSM8K.

4 DOWNSTREAM EFFECTS

  • The SFT experiment uses Llama 3.1 8B, a code-only base mix, and evaluates HumanEval, MBPP, and GSM8K without traces at inference.Training ran for 7.5k steps with a global batch size of 1024 sequences of up to 8192 tokens.Source: §4 · p. 9
  • Direct I/O prediction improves Crux-I and Crux-O but not coding benchmarks, while forward execution fine-tuning worsens Crux-I and vice versa.The authors suggest these results indicate weaker-than-expected ties between forward and backward prediction.Source: §4 · p. 9
  • The best-performing trace variant, with 10% Compact Scratchpad, brings slight gains on HumanEval and MBPP and 1.2 points on GSM8K.Overall, the results indicate that merging E.T. with SFT data offers little coding improvement.Source: Table 5 · p. 9, §4 · p. 9

5 RELATED WORK

Related work spans neural program evaluation, scratchpads for intermediate computations, and execution-based approaches to code improvement. This study builds most closely on trace modeling and compact Python trace representations.

5 RELATED WORK

6 CONCLUSION

The conclusion reports that automatically generated inputs let Execution Tuning scale trace modeling and generalize to output-prediction benchmarks. Dynamic scratchpads excel on very long executions, but the study finds no conclusive downstream coding-benchmark improvements.

6 CONCLUSION

  • Automatically generated inputs scale trace modeling, and the resulting training data generalizes to output-prediction benchmarks.The authors report tracing executions on automatically generated inputs as the basis for scaling E.T.Source: §6 · p. 10
  • Finer trace granularity helps when execution steps can be further broken down, but not for CruxEval indexing.Source: §6 · p. 10
  • Dynamic scratchpads excel on very long executions, while compact scratchpads generally outperform the original scratchpad.Source: §6 · p. 10
  • The study finds no conclusive improvements on downstream coding benchmarks, where program-state understanding might not be critical.The authors suggest extending the work to other languages, pointer IDs, closures, and more challenging datasets with exceptions and dynamic trace granularities.Source: §6 · p. 10

A LONG EXECUTION FINE-GRAINED RESULTS

Fine-grained long-execution results cover Collatz, Fibonacci, and binary counter tasks, reporting final-result accuracy and steps needed.

A LONG EXECUTION FINE-GRAINED RESULTS

B ADDITIONAL INFORMATION ON LONG EXECUTIONS

The appendix provides implementations of algorithmic tasks used to study long executions and replaces function names with f when presenting them to models.

B.1 COLLATZ

The Collatz implementation counts iterations to reach 1, using a loop that continues while n exceeds 1.

  • The Collatz function returns the number of iterations needed to reach 1 in the sequence.Source: §B.1 · p. 16
  • It initializes steps to zero and loops while n > 1.Source: §B.1 · p. 16
  • One update divides n by 2 using integer division.Source: §B.1 · p. 16

B.2 BINARY COUNTER

The appendix describes a hand-implemented 4-bit binary counter and an iterative Fibonacci function.

B.2 BINARY COUNTER

  • The binary counter implements a 4-bit counter by hand.Source: §B.2 · p. 16
  • The counter initializes four Boolean state variables and iterates n times before returning their values.Source: §B.2 · pp. 16–17

B.3 ITERATIVE FIBONACCI

  • The iterative Fibonacci function returns 1 for n == 0 and initializes its previous-term values before looping from 2 through n.Source: §B.3 · p. 17
  • Each iteration adds the previous two terms, shifts those values forward, and the function returns the latest term.Source: §B.3 · p. 17

C INPUT PREDICTION RESULTS

Input-prediction results on reversed CruxEval are reported as strict lower bounds under exact-match evaluation, with individual trace evaluations shown in Table 7 and Figure 5.

Loading 2503.05703v1…