NExT: Teaching Large Language Models to Reason about Code Execution

Overview

• Large language models (LLMs) are typically trained on the surface textual form of programs, which may lack a semantic understanding of how programs execute at run-time.
• The paper proposes NExT, a method to teach LLMs to inspect the execution traces of programs (variable states of executed lines) and reason about their run-time behavior through chain-of-thought (CoT) rationales.
• NExT uses self-training to bootstrap a synthetic training set of execution-aware rationales that lead to correct task solutions (e.g., fixed programs) without laborious manual annotation.

Plain English Explanation

Developers often have a strong intuition for how code will execute, allowing them to mentally simulate the program's behavior and use this understanding to debug and fix issues. However, large language models that are trained to understand and generate code may not naturally develop this semantic understanding of program execution.

To address this, the researchers developed a method called NExT that aims to teach LLMs to reason about the runtime behavior of programs. NExT does this by exposing the models to "execution traces" - detailed information about how variables change as the program runs. With this additional information, the models can learn to explain their thought processes in a step-by-step "chain-of-thought" when solving tasks like program repair.

The key innovation in NExT is that it uses a self-training approach to automatically generate these execution-aware explanations, rather than relying on costly manual annotation. By learning from these synthetic training examples, the LLMs can develop a more nuanced understanding of how programs execute and apply that knowledge to tasks like fixing broken code.

Technical Explanation

The paper proposes NExT, a method to teach large language models (LLMs) to reason about the runtime behavior of programs. NExT does this by exposing the models to "execution traces" - detailed information about how variables change as the program runs.

The core idea is to use self-training to bootstrap a synthetic training set of execution-aware rationales that lead to correct task solutions (e.g., fixed programs). This avoids the need for laborious manual annotation of such rationales.

Specifically, NExT works as follows:

1. Train an initial LLM on code and its textual form alone, without execution traces.
2. Use this initial model to generate candidate solutions (e.g., program fixes) for a set of training tasks.
3. For each candidate solution, generate an execution trace and use it to construct a chain-of-thought (CoT) rationale explaining how the solution was derived.
4. Fine-tune the initial LLM on this synthetic dataset of code, execution traces, and CoT rationales.

The paper evaluates NExT on program repair tasks from MBPP and HumanEval. Experiments show that NExT improves the fix rate of a PaLM 2 model by 26.1% and 14.3% absolute, respectively, with significantly improved rationale quality as verified by automated metrics and human raters.

Importantly, the paper also demonstrates that NExT can generalize to scenarios where program traces are absent at test-time, suggesting the models have developed a more semantic understanding of program execution.

Critical Analysis

The NExT approach represents an innovative step towards teaching large language models to reason about the runtime behavior of programs, rather than just their surface textual form. This is an important capability, as it aligns with how human developers often approach programming tasks.

That said, the paper acknowledges several limitations and areas for further research:

• The synthetic training data generated by NExT, while effective, may not fully capture the nuances of real-world program execution. Exploring ways to incorporate actual execution traces could further improve the models' understanding.
• The evaluation is limited to program repair tasks; extending NExT to a broader range of programming activities, such as code generation or program synthesis, would further demonstrate its generalizability.
• The paper does not explore how NExT's execution-aware reasoning could be combined with other techniques, such as program sketching or pseudocode execution, to create more powerful programming assistants.
• The performance improvements, while significant, still leave room for further advancements in program understanding and reasoning capabilities of large language models.

Overall, the NExT approach is a valuable contribution to the ongoing efforts to imbue LLMs with more robust and semantic understanding of code, as demonstrated by the GoEx project and others. Continued research in this direction has the potential to unlock new frontiers in human-AI collaboration for software development.

Conclusion

The paper proposes NExT, a method to teach large language models to reason about the runtime behavior of programs, rather than just their surface textual form. By exposing the models to execution traces and using self-training to generate execution-aware rationales, NExT enables LLMs to develop a more semantic understanding of how code behaves at runtime.

Experiments on program repair tasks show that NExT can significantly improve the performance and explainability of LLMs in these domains. While the approach has limitations and areas for further research, it represents an important step towards bridging the gap between how human developers and language models reason about code, with potential implications for a wide range of programming-related applications.