Code Large Language Models (Code LLMs) have excelled at tasks like code completion but often miss deeper semantics such as execution effects and dynamic states. This paper aims to bridge the gap between Code LLMs' reliance on static text data and the need for thorough semantic understanding for complex tasks like debugging and program repair.
We introduce a novel strategy to train Code LLMs with comprehensive semantics, encompassing high-level functional descriptions, local execution effects of individual statements, and overall input/output behavior, thereby linking static code text with dynamic execution states.
We begin by collecting , a clean code corpus of fully executable samples with functional descriptions and execution tracing.
We propose training Code LLMs to write code and represent and reason about execution behaviors using natural language, mimicking human verbal debugging. This approach led to the development of , a Code LLM with only 6.7B parameters, which shows competitive performance with GPT-3.5-turbo on code generation and execution reasoning tasks. achieves 81.1% on HumanEval (GPT-3.5-turbo: 76.8%) and 54.5% on CRUXEval-I (GPT-3.5-turbo: 50.3%).
We also study the effectiveness of 's monologue-style execution reasoning compared to concrete scratchpad reasoning, showing that our approach integrates semantics from multiple dimensions more smoothly. Finally, we demonstrate the potential of applying learned semantics to improve Code LLMs' debugging and self-refining capabilities.

§ INTRODUCTION

Recent advancements in code language models (Code LLMs) [1, 2, 3, 4, 5] have revolutionized the field of programming [6, 7, 8]. These models, trained primarily on vast corpora of programming-related text such as source code and docstrings [9], excel at automating tasks like code generation.

Unfortunately, the reliance on static text data limits the ability of existing Code LLMs to understand what the programs are actually doing, especially to reason about the deeper semantics intrinsic to code execution.
The lack of semantic understanding unsurprisingly often leads to poor performance in debugging and repairing errors in generated code [10]. Code LLMs struggle with reasoning about program semantics in both static and dynamic settings. In a static setting, the challenge lies in understanding the intended behavior of the code without running it, requiring deep comprehension of code syntax and static semantic properties (e.g., program dependency graph, etc.) [11, 12]. A dynamic setting involves observing and interpreting the code's behavior during execution, including tracking variable changes, identifying runtime errors, and detecting performance issues [13].
Even when the execution traces are exposed to the model, [13] observed that Code LLMs could not effectively interact with the real executions, struggling to leverage the dynamic execution traces for debugging.

Fifty years ago, Terry Winograd envisioned the future AI programmer: “The key to future programming lies in systems which understand what they are doing [14]".
In this paper, we explore constructing such a programming system, backed up by language models, not only to write programs but also to
understand what they are doing (a.k.a., semantics).
Our key insight is that Code LLMs should mimic how pragmatic human developers work: starting with general specifications, breaking them down into sub-tasks, implementing code line by line while reasoning about the effects of each line, and checking overall correctness by examining execution effects [15].
To achieve this, we introduce a novel strategy to train Code LLMs with comprehensive program semantics.

First, we incorporate different modalities of program semantics in our reasoning: (i) High-Level Functional Descriptions: We train Code LLMs to understand high-level functional descriptions while generating code from natural language. This involves teaching models to grasp a program's purpose and constraints, akin to how a human developer outlines software high-level approximate semantics; (ii) Local Effect of Individual Code Statements: We train Code LLMs to understand the local impact of individual code statements, recognizing how each line affects variables, control flow, and memory usage. By grasping these effects, models can better predict code execution semantics. We train the model to learn both abstract and concrete semantics, teaching it the general purpose of a statement and illustrating it with concrete examples; and (iii) Overall Execution Behavior: We further train the model to learn the overall operational semantics of code by learning input/output behavior.

We train , a novel semantic-aware Code LLM, to learn from different semantic modalities. We propose a unique strategy called Monologue Reasoning to align static source code with these program semantics, helping models correlate written code with its runtime behavior. To train the model, we also curate an execution-aware Python dataset, .

Curating Executable Code Dataset First, we collect , a synthetic dataset capturing comprehensive program semantics with executable code samples and unit tests. Inspired by existing datasets [16, 17], we use a powerful LLM to synthesize NL-to-code pairs. To ensure quality, includes only executable samples. It also generates unit tests and detailed execution traces, recording program states after each statement. From , we further construct a debugging dataset, -R. -R includes buggy code snippets generated by Code LLMs, corresponding error logs and faulty traces, as well as debugging rationales and refine plans [13] leading to patches. By fine-tuning Code LLMs on -R, we aim to develop programming assistants that debug and patch faulty code in a human-like manner, advancing the capabilities of current Code LLMs in iterative programming.

Learning Program Semantics To learn program semantics, we propose monologue reasoning, where Code LLMs articulate code execution step-by-step, inspired by rubber duck debugging [15]. This includes: (i) forward monologue: uses source code and inputs to verbally simulate execution, explaining each line's impact, executed lines, variable changes, and final output, and (ii) backward monologue: given the final output, reasons about possible previous states abstractly, capturing essential characteristics without precise enumeration.
This abstract reasoning is crucial for understanding complex operations like sorting or aggregation, where the previous state cannot be uniquely determined. Overall, monologue reasoning equips Code LLMs with a human-like understanding of control flow, state transitions, and complex operations, bridging the gap between static code analysis and dynamic execution reasoning.

We show that, by training on this approach,  can generate, reason about execution, debug and refine code in a more intuitive and effective manner, pushing the boundaries of what current Code LLMs can achieve in different software engineering tasks.

Performance of
, while having only 6.7B parameters, exhibits exceptional performance in code generation and execution reasoning tasks, surpassing larger models like GPT-3.5-turbo and various open-source models. For code generation, variants achieve a pass@1 of 81.1% on HumanEval, significantly outperforming GPT-3.5-turbo's 76.8%, and leads with 79.9% on MBPP. For execution reasoning, variants score 54.5% and 56.6% on CRUXEval-I and CRUXEval-O, respectively, showcasing its superior understanding of program executions. The innovative monologue reasoning technique, where the model verbalizes step-by-step code execution, greatly enhances execution reasoning, outperforming existing trace reasoning formats like scratchpad [2] and NeXT [13]. The monologue reasoning approach also allows to flexibly handle abstract semantics and non-deterministic program states, which existing methods struggle with. Additionally, excels in debugging and self-refinement, improving code generation accuracy iteratively by leveraging execution traces and debugging by itself.

Our main contribution is the development of , a semantic-aware Code LM designed to enhance understanding and reasoning about program semantics. We introduce Monologue Reasoning, a novel execution learning approach that aligns static source code with its runtime behavior through detailed verbal descriptions of code execution. To expose comprehensive program semantics at different levels, we curate , a collection of executable code samples with functional descriptions and execution traces. demonstrates superior performance in code generation and execution reasoning tasks, surpassing larger open-source models. also excels in debugging and self-refinement by leveraging knowledge from its semantic-aware training. Our work highlights the potential of integrating deep semantic understanding into Code LMs to improve their effectiveness in complex programming tasks.
We will publicly release our dataset and model.

§ PROGRAM SEMANTICS

training strategy with different modalities of program semantics. We specify the overall objective of a task, such as “retrieves potential energies of atoms and performs sorting", constraints that the implementation should follow, such as “takes a list of float numbers as input and returns a list of integer-based indices" (See green box), and expected input/output with test cases, such as “Given [10.5, 8.2, 10.5, 7.1, 8.2], return [3, 1, 0]" (See blue box). We further annotate the program with forward and backward monologues, as shown in the blue and yellow boxes. learns from all the information to generate code and predict execution.

Program semantics refers to the meaning or behavior of a computer program, describing what it does when it runs, including input processing, computations, and output [18, 19]. Understanding program semantics is crucial for ensuring programs behave correctly and meet their intended purpose.

Program semantics can be represented in various modalities. A high-level description outlines a program's intended functionality, while fine-grained semantics detail the actions and side effects of each line of code, including data manipulation and state changes. This detailed understanding helps developers write better code and aids in code reviewing, debugging, and team communication, known as rubber duck debugging [15].
Fine-grained semantics can be concrete or abstract. Concrete semantics (e.g., program traces) capture actual execution effects, while abstract semantics focus on key input-output relationships and overall program effects, abstracting away lower-level details [20, 21]. To this end, following the existing literature on program semantics [18, 19], we curate the following semantic information corresponding to each source code.

Approximate Semantics describes the overall objectives of a program, often articulated through docstrings or documentation [22, 23].
These Natural Language descriptions provide an overview of the program's goals and anticipated results, ensuring that the implementation aligns with the intended high-level functionalities (See the green box in Figure <ref>).

Operational Semantics describe how the individual steps in a source code execute [24, 18, 19]. It focuses on describing the concrete execution of a program in a step-by-step manner, detailing how each action transforms the program's state. This approach is particularly useful for reasoning about the dynamic behavior of programming languages (See the middle yellow box in Figure <ref>).

Abstract Semantics is a way to describe program behavior at a higher level of abstraction [25, 26, 20, 21]. Unlike concrete semantics, which provides detailed descriptions of the program's execution on specific inputs, abstract semantics focuses on the essential aspects of program behavior while ignoring low-level details. This approach is particularly useful for reasoning about program properties (See the extreme right box in Figure <ref>, where the traces log the impact of each statement on variable types and range of values rather than a concrete value.).

§ : SEMANTIC-AWARE TRAINING DATASET

Capturing program semantics requires executing source code with unit tests. Real-world datasets are challenging due to diverse configurations, lack of unit tests, and limited documentation [27]. Thus, we use a synthetic dataset to capture program semantics.
Here, we detail the process of gathering high-quality data for learning multi-modal code semantics. Building on WizardCoder and MagiCoder [16, 17], we first synthesize NL to Code pairs. Then, we use the Python interpreter to filter out defective samples, ensuring comprehensive semantic coverage. This method significantly improves the fine-tuned model's performance (see Section <ref>).
See Appendix <ref> for more details and analysis, including Figure <ref> which depicts the data collection procedure.

§.§ Synthesizing Executable Code

Synthesizing instructional data (NL to code) with existing LLMs is common for obtaining large datasets for instruction tuning CodeLLMs [16, 17]. However, current methods do not guarantee the quality of generated code.
For instance, out of 43.1k Python solutions from [16], about 11.6k (26.9%) are inexecutable despite instructions to produce "correct" and "self-contained" code (Table <ref> in Appendix <ref> shows the top 10 error types).
To build , we train it with high-quality, parsable, and executable data, as good data leads to better generation [28, 29]. We improve the OSS-Instruct data generation process [16], which prompts an LLM to create a programming task and solution inspired by a seed snippet. Instead of randomly sampling lines from existing programs, we parse them into ASTs and sample subtrees to obtain parsable seeds. We execute the generated code, retaining only successfully executed samples, and use the generator model's debugging capability to retry until the code runs correctly. With the low-cost supervision from the Python interpreter, we build a higher-quality instruction tuning dataset for semantic-aware model training. Step I of Figure <ref> in Appendix <ref> summarizes this process.
Table <ref> in Appendix <ref> compares our with OSS-Instruct in details.

§.§ Traced Dataset with Operational Semantics

We select a subset of to construct data to learn the execution reasoning (See Step-II of Figure <ref> in Appendix <ref>).

Data Selection We apply the following filtering criteria to select programs with clean, easy-to-learn execution traces from our executable dataset:
(i) Only programs without external resource interactions (e.g., keyboard input, file system changes) are included, as our trace representation only captures variable state changes.
(ii) Programs are limited to those using Python built-in types for easy text representation of variable values.
(iii) Only single-function programs are collected to focus on variable changes without complex inter-procedure effects.
(iv) Programs must have no randomness, ensuring predictable behavior.

Input Generation Our executable dataset typically has one or two example inputs per program. To model operational semantics accurately and avoid bias, we need a diverse input set to expose different execution traces. We expand the input set using type-aware mutation and LLM-based input generation, similar to [30] as detailed in Appendix <ref>.

§.§ -R: Training Code LLMs to Debug and Self-refine

We construct a debugging dataset, -R, to train Code LLMs for debugging and self-refinement, aiming to improve their iterative programming capabilities. To create buggy samples, we prompt a 7B Code LLM to solve problems in , execute the predictions with unit tests, and use differential testing [31] to compare against the ground-truth. Solutions differing from the ground truth are saved as buggy code. We collect execution traces from buggy programs and their input sets, recording program states after each statement execution. Following NeXT [13], we track changed variables and execution order, maintaining the first, second, and last states if a line is executed more than three times. Similar to NeXT, we prompt the LLM to analyze buggy programs with their faulty traces and generate patches. -R includes only those rationales that lead to correct patches, verified by differential testing against the ground truth.

§ : LEARNING COMPREHENSIVE SEMANTICS

§.§ Natural Language to Code

We train to translate high-level functional descriptions into executable code, known as the natural language to code task [16, 17]. Using samples, we provide well-defined problem descriptions that specify (1) the task's overall objective, (2) implementation constraints, and (3) expected outcomes with test cases. These descriptions give a holistic view of the task, forming the basis for the model’s understanding.  Figure <ref> shows an example.

§.§ Monologue Reasoning for Execution

We train to understand execution through monologue reasoning, describing state changes line by line. Inspired by rubber duck debugging, this approach explains algorithmic purposes and state changes more smoothly than structured formats like Scratchpad, and avoids misleading chains of thought. We detail the rules and their effectiveness in Section <ref>. Our approach captures both operational and abstract semantics in forward and backward directions, as defined in Section <ref>.

§.§.§ Forward Monologue

During the forward monologue, we provide with the source code and input, and it learns to reason about the operational semantics by verbally simulating the execution step by step. Figure <ref>, blue box, summarize this process.

Execution Coverage
To ensure comprehensive understanding, covers each line of code, explicitly mentioning whether it is executed, regardless of variable changes. This approach identifies executed code parts in different scenarios, contributing to a thorough control flow understanding and enforcing a detailed code walkthrough, similar to a developer's debugging process.

Natural Execution Orders
To mimic natural code execution, follows the natural order of reasoning. For loops, it explains each iteration with specific values, addressing lines executed multiple times differently. This ensures an accurate, context-aware execution path, similar to how developers mentally simulate execution  behavior, helping to detect issues like infinite loops or incorrect condition handling.

Program State Transition Understanding each line's side effects is crucial for grasping program state evolution. The model is trained to indicate changes in variable values when a line is executed, enhancing its ability to simulate real execution effects. This focus on side effects helps capture dynamic semantics, providing granular, step-by-step explanations of state changes, thus improving debugging and refinement based on observed behavior.

Final Output Finally, the model predicts the program's final output after explaining the execution process, validating logic and correctness. This ensures it can explain intermediate steps and derive final results, mimicking a developer's comprehensive understanding, crucial for debugging.

§.§.§ Backward Monologue

While forward execution is mostly deterministic, the previous program state cannot always be determined from the current state, such as an unsorted list from its sorted version. Therefore, we design the backward monologue to be flexibly abstract (See Figure <ref>, yellow box).

Abstract Intermediate Constraints In our backward monologue reasoning, we use abstract intermediate constraints when previous program states can't be uniquely determined from the current state, such as after sorting or aggregation. We train the model to describe these constraints abstractly. For example, instead of listing exact elements, the model might describe a sorted list's () previous state as "a disordered list with two 10.5s, two 8.2s, and one 7.1." This abstraction captures essential characteristics and patterns, allowing the model to reason about multiple possible previous states. This approach enhances the model's flexibility and generalization, improving its ability to handle diverse and complex program reasoning tasks.

Concrete Input For a given output, the model learns to predict concrete input values that satisfy the input abstract constraints. This step bridges the gap between abstract reasoning and concrete execution. This ensures it understands patterns and can generate practical examples, enhancing its robustness for real-world tasks like debugging and testing. This dual capability mirrors how human developers reason about code.

§.§.§ Monologue Annotation Using LLM

To annotate the monologue required for training , we employ a method of rejection sampling [32, 33] through a large language model (, specifically). We leverage the power of LLM to automatically annotate numerous samples for training , while we have an execution-based golden standard to verify the quality of annotated monologues, ensuring they are informative and valuable, thereby enhancing 's ability to reason about program executions both forward and backward.

For forward monologue annotation, we feed code samples from our PyX dataset into an LLM, prompting it to generate a detailed, line-by-line explanation of state changes and logic, ending with a final output prediction. We then execute the code; if the actual output matches the LLM's prediction, we accept the monologue, ensuring it accurately reflects the program's execution. If the output does not match, the monologue is rejected. This method ensures the monologue is comprehensive and suitable for training . We follow the similar strategy for backward monologue annotation.

To enhance our monologue annotation process, we provide the LLM with few-shot examples when generating forward and backward monologues. These examples follow our defined rules, explicitly detailing execution lines, variable changes, and reasoning steps for forward monologues, and abstract constraints with specific examples for backward monologues. This guidance ensures the LLM adheres to our structured reasoning steps. We also use system instructions to ensure the LLM follows the procedures illustrated in the few-shot examples.

§.§ Joint Training with Comprehensive Semantics

is trained with the combined data of natural-language-to-code samples, forward monologues, and backward monologues, using the standard next-token prediction objective [34].
Our training has an emphasis on learning the program semantics, where the training loss is accumulated only by cross-entropy loss on code and monologue tokens together. We also include a task-specific prefix as part of the model input so that the model is better aware of which types of program semantics it should learn to capture and predict for the current sample. See Appendix <ref> for concrete prefixes.

§ EXPERIMENTS

Code Generation and Execution Reasoning
For code generation evaluation, we use EvalPlus [30], an extensive benchmark combining HumanEval [1] and MBPP [35], comprising 563 problems with numerous test cases and oracles. We input high-level descriptions into Code LLMs for zero-shot prompting and use greedy decoding during inference. For execution reasoning, we employ CRUXEval [36], featuring 800 Python functions and input-output pairs across two tasks: CRUXEval-I and CRUXEval-O. We evaluate in two settings: direct prediction and reasoning, using two-shot prompting for baselines and zero-shot for . Inference follows the benchmark's top-p sampling (p=0.95, temperature=0.2).

Debugging and Self-refine To improve debugging and self-refinement, we fine-tune and other Code LLMs on -R to generate debugging rationales and patches (Section <ref>). We then evaluate iterative programming capabilities in self-refinement/self-debugging [37, 38] setting—Models generate code, execute it, trace bugs, and refine their code based on the trace. Using EvalPlus [30], we perform five iterative refinements. Greedy decoding is used initially, followed by top-p sampling for diversity.

Models loads the 6.7B base version of DeepSeekCoder
as the initial checkpoint and continues to optimize it with the proposed program semantic training. Similar to Magicoder [16], we train two versions of , the base version and the more advanced -$S$. The base version is completely trained with , and the -$S$ combines with Evol-instruct [16], a decontaminated version of  [39], which contains numerous instruction data that has been shown to improve models' instruction-following capabilities [16]

Configuration and Empirically Settings

All variants are trained for 3 epochs on a server with eight NVIDIA RTX A6000 GPUs, using a learning rate of 5e-5 for program semantics training. For self-refinement fine-tuning, and baseline Code LLMs are trained for 2 epochs with a learning rate of 1e-5. We use a batch size of 512, a maximum context length of 2,048, and apply cosine learning rate decay.  is used as the LLM where required.

§ EVALUATION

§ RELATED WORK

Code LLMs and Training Data

Many open source Code LLMs, such as CodeGen [41], StarCoder [42, 5], Code Llama [4], and DeepSeek Coder [3], are proposed.
Specialized models [35, 1, 43] have also been developed for tasks like code generation, summarization, output prediction, and competitive programming following the success of GPT-3 [44].
These models are trained only on source code and related text, lacking execution context.
This limits their understanding of program semantics, leading to security issues and debugging failures. We aim to bridge this gap by training Code LMs on both static source code and dynamic execution traces. An orthogonal line of research curates synthetic instruction-following data to enhance Code LLM performance. Code Alpaca [45] has 20k instruction-response pairs, Evol-Instruct-Code [17] expands this to 80k pairs, and OSS-Instruct [16] includes 75k diverse pairs from the Stack dataset [9]. However, these datasets focus on natural-language-to-code tasks with little coverage of code execution and unverified solutions. To improve correctness, Zheng et al. [46] created a multi-turn conversation dataset with compiler error messages, and Wei et al. [47] incorporated execution by generating test cases and filtering invalid pairs. Yet, no dataset includes simulating and understanding execution traces. We aim to fill this gap (see Section <ref>).

Learning and Reasoning about Program Executions

Before LLMs,
[48, 49] predict simple program outputs using RNNs, GNNs, small transformers, and neural Turing machines. Austin et al. [35] fine-tuned LLMs for execution output prediction with minimal performance gains. Early models predicted final outputs without revealing execution traces. Nye et al. [2] introduced the Scratchpad method for intermediate results, and others [50, 51] fine-tuned UniXcoder [52] for execution traces but didn't evaluate for code generation tasks. We fine-tune a Code LLM to understand program semantics, excelling in code generation, output prediction, and input prediction (see Section <ref>).
Another approach uses execution feedback for debugging Code LLMs. Self-Debugging [37] shows that natural language explanations or unit test results help self-refinement, but execution traces reduce performance. LeTI [53] and CYCLE [38] fine-tune with execution feedback to improve performance, especially for smaller models. NeXT [13] generates debugging rationales to mitigate the negative impact of execution traces. Our work shows that a model trained on code generation, output prediction, and input prediction excels in understanding execution feedback and self-refinement (see Table <ref>).

§ CONCLUSION

We train to simultaneously learn different modalities of program semantics: Approximate Semantics via natural-language-to-code generation, Operational Semantics via output prediction, and Abstract Semantics by input prediction. We show that such semantics-oriented joint training cultivates a comprehensive understanding of program semantics — or -$S$ achieves SOTA performance, among all less-than-15B open-source models, in not only the code generation and execution prediction tasks themselves, but also downstream tasks that require deep knowledge of both natural language specifications and execution traces like debugging and self-refinement.

[1]
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba.
Evaluating large language models trained on code, 2021.

[2]
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena.
Show your work: Scratchpads for intermediate computation with language models, 2021.

[3]
Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Y. Wu, Y. K. Li, Fuli Luo, Yingfei Xiong, and Wenfeng Liang.
Deepseek-coder: When the large language model meets programming – the rise of code intelligence, 2024.

[4]
Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, Jérémy Rapin, Artyom Kozhevnikov, Ivan Evtimov, Joanna Bitton, Manish Bhatt, Cristian Canton Ferrer, Aaron Grattafiori, Wenhan Xiong, Alexandre Défossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve.
Code llama: Open foundation models for code, 2024.

[5]
Anton Lozhkov, Raymond Li, Loubna Ben Allal, Federico Cassano, Joel Lamy-Poirier, Nouamane Tazi, Ao Tang, Dmytro Pykhtar, Jiawei Liu, Yuxiang Wei, Tianyang Liu, Max Tian, Denis Kocetkov, Arthur Zucker, Younes Belkada, Zijian Wang, Qian Liu, Dmitry Abulkhanov, Indraneil Paul, Zhuang Li, Wen-Ding Li, Megan Risdal, Jia Li, Jian Zhu, Terry Yue Zhuo, Evgenii Zheltonozhskii, Nii Osae Osae Dade, Wenhao Yu, Lucas Krauß, Naman Jain, Yixuan Su, Xuanli He, Manan Dey, Edoardo Abati, Yekun Chai, Niklas Muennighoff, Xiangru Tang, Muhtasham Oblokulov, Christopher Akiki, Marc Marone, Chenghao Mou, Mayank Mishra, Alex Gu, Binyuan Hui, Tri Dao, Armel Zebaze, Olivier Dehaene, Nicolas Patry, Canwen Xu, Julian McAuley, Han Hu, Torsten Scholak, Sebastien Paquet, Jennifer Robinson, Carolyn Jane Anderson, Nicolas Chapados, Mostofa Patwary, Nima Tajbakhsh, Yacine Jernite, Carlos Muñoz Ferrandis, Lingming Zhang, Sean Hughes, Thomas Wolf, Arjun Guha, Leandro von Werra, and Harm de Vries.
Starcoder 2 and the stack v2: The next generation, 2024.

[6]
Github copilot: Your ai pair programmer.
<https://github.com/features/copilot>, 2021.

[7]
Amazon codewhisperer: Your ai-powered productivity tool for the ide and command line.
<https://aws.amazon.com/codewhisperer/>, 2022.

[8]
<https://chatgpt.com/>, 2022.

[9]
Denis Kocetkov, Raymond Li, Loubna Ben Allal, Jia Li, Chenghao Mou, Carlos Muñoz Ferrandis, Yacine Jernite, Margaret Mitchell, Sean Hughes, Thomas Wolf, et al.
The stack: 3 tb of permissively licensed source code.
arXiv preprint arXiv:2211.15533, 2022.

[10]
Alex Gu, Wen-Ding Li, Naman Jain, Theo X. Olausson, Celine Lee, Koushik Sen, and Armando Solar-Lezama.
The counterfeit conundrum: Can code language models grasp the nuances of their incorrect generations?, 2024.

[11]
Nathaniel Ayewah, William Pugh, David Hovemeyer, J. David Morgenthaler, and John Penix.
Using static analysis to find bugs.
IEEE Software, 25(5):22–29, 2008.

[12]
Brittany Johnson, Yoonki Song, Emerson Murphy-Hill, and Robert Bowdidge.
Why don't software developers use static analysis tools to find bugs?
In 2013 35th International Conference on Software Engineering (ICSE), pages 672–681, 2013.

[13]
Ansong Ni, Miltiadis Allamanis, Arman Cohan, Yinlin Deng, Kensen Shi, Charles Sutton, and Pengcheng Yin.
Next: Teaching large language models to reason about code execution, 2024.

[14]
Terry Winograd.
Breaking the complexity barrier again.
In Proceedings of the 1973 Meeting on Programming Languages and Information Retrieval, SIGPLAN '73, page 13–30, New York, NY, USA, 1973. Association for Computing Machinery.

[15]
Andrew Hunt and David Thomas.
The pragmatic programmer: from journeyman to master.
Addison-Wesley Longman Publishing Co., Inc., USA, 2000.

[16]
Yuxiang Wei, Zhe Wang, Jiawei Liu, Yifeng Ding, and Lingming Zhang.
Magicoder: Source code is all you need.
arXiv preprint arXiv:2312.02120, 2023.

[17]
Ziyang Luo, Can Xu, Pu Zhao, Qingfeng Sun, Xiubo Geng, Wenxiang Hu, Chongyang Tao, Jing Ma, Qingwei Lin, and Daxin Jiang.
Wizardcoder: Empowering code large language models with evol-instruct.
arXiv preprint arXiv:2306.08568, 2023.

[18]
Matthew Hennessy.
The semantics of programming languages: an elementary introduction using structural operational semantics.
John Wiley & Sons, Inc., 1990.

[19]
Glynn Winskel.
The formal semantics of programming languages: an introduction.
MIT press, 1993.

[20]
Carl A Gunter.
Semantics of programming languages: structures and techniques.
MIT press, 1992.

[21]
Joseph E Stoy.
Denotational semantics: the Scott-Strachey approach to programming language theory.
MIT press, 1981.

[22]
Steve McConnell.
Code complete.
Pearson Education, 2004.

[23]
David Thomas and Andrew Hunt.
The Pragmatic Programmer: your journey to mastery.
Addison-Wesley Professional, 2019.

[24]
Gordon D Plotkin.
A structural approach to operational semantics.
Aarhus university, 1981.

[25]
Flemming Nielson, Hanne R Nielson, and Chris Hankin.
Principles of program analysis.
springer, 2015.

[26]
Patrick Cousot and Radhia Cousot.
Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints.
In Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, pages 238–252, 1977.

[27]
Marcus J Min, Yangruibo Ding, Luca Buratti, Saurabh Pujar, Gail Kaiser, Suman Jana, and Baishakhi Ray.
Beyond accuracy: Evaluating self-consistency of code llms.
In The Twelfth International Conference on Learning Representations, 2023.

[28]
Suriya Gunasekar, Yi Zhang, Jyoti Aneja, Caio César Teodoro Mendes, Allie Del Giorno, Sivakanth Gopi, Mojan Javaheripi, Piero Kauffmann, Gustavo de Rosa, Olli Saarikivi, et al.
Textbooks are all you need.
arXiv preprint arXiv:2306.11644, 2023.

[29]
Yue Yu, Yuchen Zhuang, Jieyu Zhang, Yu Meng, Alexander J Ratner, Ranjay Krishna, Jiaming Shen, and Chao Zhang.
Large language model as attributed training data generator: A tale of diversity and bias.
Advances in Neural Information Processing Systems, 36, 2024.

[30]
Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and Lingming Zhang.
Is your code generated by chatgpt really correct? rigorous evaluation of large language models for code generation.
Advances in Neural Information Processing Systems, 36, 2024.

[31]
William M. McKeeman.
Differential testing for software.
Digit. Tech. J., 10:100–107, 1998.

[32]
George Casella, Christian P. Robert, and Martin T. Wells.
Generalized accept-reject sampling schemes.
Lecture Notes-Monograph Series, 45:342–347, 2004.

[33]
Radford M. Neal.
Slice sampling, 2000.

[34]
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.
Language models are unsupervised multitask learners.
OpenAI preprint, 2019.

[35]
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al.
Program synthesis with large language models.
ArXiv preprint, abs/2108.07732, 2021.

[36]
Alex Gu, Baptiste Rozière, Hugh Leather, Armando Solar-Lezama, Gabriel Synnaeve, and Sida I. Wang.
Cruxeval: A benchmark for code reasoning, understanding and execution.
arXiv preprint arXiv:2401.03065, 2024.

[37]
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou.
Teaching large language models to self-debug, 2023.

[38]
Yangruibo Ding, Marcus J. Min, Gail Kaiser, and Baishakhi Ray.
Cycle: Learning to self-refine the code generation, 2024.

[39]
The evolved code alpaca dataset.
<https://huggingface.co/datasets/theblackcat102/evol-codealpaca-v1>, 2023.

[40]
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou.
Chain-of-thought prompting elicits reasoning in large language models, 2023.

[41]
Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong.
Codegen: An open large language model for code with multi-turn program synthesis.
In International Conference on Learning Representations, pages 1–25, 2023.

[42]
Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, et al.
Starcoder: may the source be with you!
arXiv preprint arXiv:2305.06161, 2023.

[43]
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al.
Competition-level code generation with alphacode.
ArXiv preprint, abs/2203.07814, 2022.

[44]
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.
Language models are few-shot learners.
In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, pages 1–25, 2020.

[45]
Sahil Chaudhary.
Code alpaca: An instruction-following llama model for code generation.
<https://github.com/sahil280114/codealpaca>, 2023.

[46]
Tianyu Zheng, Ge Zhang, Tianhao Shen, Xueling Liu, Bill Yuchen Lin, Jie Fu, Wenhu Chen, and Xiang Yue.
Opencodeinterpreter: Integrating code generation with execution and refinement, 2024.

[47]
Yuxiang Wei, Federico Cassano, Jiawei Liu, Yifeng Ding, Naman Jain, Harm de Vries, Leandro von Werra, Arjun Guha, and Lingming Zhang.
Starcoder2-instruct: Fully transparent and permissive self-alignment for code generation, 2024.

[48]
Wojciech Zaremba and Ilya Sutskever.
Learning to execute, 2015.

[49]
Alex Graves, Greg Wayne, and Ivo Danihelka.
Neural turing machines, 2014.

[50]
Chenxiao Liu, Shuai Lu, Weizhu Chen, Daxin Jiang, Alexey Svyatkovskiy, Shengyu Fu, Neel Sundaresan, and Nan Duan.
Code execution with pre-trained language models, 2023.

[51]
Yangruibo Ding, Benjamin Steenhoek, Kexin Pei, Gail Kaiser, Wei Le, and Baishakhi Ray.
Traced: Execution-aware pre-training for source code.
In Proceedings of the 46th IEEE/ACM International Conference on Software Engineering, pages 1–12, 2024.

[52]
Daya Guo, Shuai Lu, Nan Duan, Yanlin Wang, Ming Zhou, and Jian Yin.
Unixcoder: Unified cross-modal pre-training for code representation.
arXiv preprint arXiv:2203.03850, 2022.

[53]
Xingyao Wang, Hao Peng, Reyhaneh Jabbarvand, and Heng Ji.
Leti: Learning to generate from textual interactions, 2024.

[54]
(Accessed on 05/17/2024).

§ COMPARISON WITH LARGER OPEN-SOURCED MODELS AND CLOSED-SOURCE MODELS

§ CONTINUOUSLY REFINES CODE QUALITIES

We studied 's code generation accuracy at each step of refinement with varied temperatures. The results are plotted in Figure <ref>. We observed that is capable of continuously refining its own errors, and the increase does not stop when the temperature is high, which indicates the has strong debugging and self-refine capabilities and a high temperate better leverages such capabilities for iterative programming.

's performance of self-refinement at each time step with different sampling.

§ EXECUTABILITY ANALYSIS OF OSS-INSTRUCT

We execute all Python samples in OSS-Instruct [16] to analyze their executability. To get a more accurate result, we try to mitigate the  by installing the top 75 missing dependencies according to a pre-run result. Table <ref> shows the breakdown of the top 10 error types.

§ DETAILS ON

The whole data collection pipeline is shown in Figure <ref>. Here we also document more details about .

: Execution-aware Training Data Collection Strategy

Prompt for Data Synthesis

We follow the prompt in OSS-Instruct for data synthesis, but with two modifications: 1) For problem design, instruct the model to avoid interaction with external resources or requirement of
uncommon third-party libraries to increase the probability of getting executable code. 2) For giving solutions, instruct the model to show its thought process before writing code to produce more aligned natural language along with the code in the dataset. Table <ref> details our prompts with an example in .

Input Set Expansion
To enlarge the input set, we first initialize the input corpus with all known valid inputs. Then, for type-aware mutation, we alter known inputs based on type-specific heuristics. For LLM-based generation, we prompt the model with the function and several known inputs to generate more. We verify new inputs by executing them, retaining only those that execute successfully without exceptions. We alternate between type-aware mutation and LLM-based generation until reaching a predefined threshold, combining mutation's efficiency with LLM generation's robustness. The generated inputs and their outputs serve as unit tests for the NL-described task in future steps.

Coverage of Inputs Our input generation method only considers diversity in terms of variable values but does not try to fully exercise different execution paths in an executable code, like what the coverage-guided testing usually does. However, our dataset only consists of relatively short single-function programs that do not have complicated branches. We find that our generated inputs can achieve average branch coverage and average line coverage of 93%, 96% respectively, which shows that our approach is light-weight yet effective for the current setting.

Executability v.s. Parsability
Along with the generation of 34k executable data, we also get 13k samples that can only be parsed as valid ASTs but cannot be successfully executed. We include these parsable samples to form a 47k dataset, -Soft, and compare it against the fully executable one . Results in Table <ref> show that -Soft and have comparable results, and both of them outperform OSS-Instruct and its Python subset. Though -Soft sometimes slightly outperforms , full executability is required for comprehensive semantic coverage, so we use for the main evaluation.

Data De-duplication
We follow the data decontamination process of [16] and [54] to clean our dataset. To examine the similarity between our instruction tuning dataset and the testing benchmarks, we embed the problems and solutions of all samples in our dataset and all samples in HumanEval and MBPP with an OpenAI's embedding model (), and then compute cosine similarities between them. For each sample in our dataset, its similarity to a benchmark is computed as the maximum cosine similarity to any sample in the benchmark. We apply the same analysis to OSS-Instruct for comparison. Figure <ref> shows that the similarity between our dataset and the two benchmarks is on par with OSS-Instruct, where the majority has less than 0.5 cosine similarity, and we also find there is no sample with cosine similarity greater than 0.75. These results indicates that the performance improvement brought by our dataset is not from data leakage or benchmark data imitation.

Cosine similarities between and two popular benchmarks

Categories To study the effect of executability filtering, we categorize all samples in our dataset following [16] shown by Figure <ref>. Compared to OSS-Instruct, the categorical distribution shifts by an increase in algorithmic and data structure problems, data science and machine learning problems, and mathematical and computational problems, and a decrease in the remaining categories, which is expected since interactions with external resources commonly required in scenarios like database, web and UI design are not allowed in our execution environment.

The category distribution of

Data Statistics We perform decontamination on the , and monologue samples (we remove the samples that share the same input and output pair with CRUXEval). includes 34,639 natural language to code pairs. We generated 29,494 forward monologues and 20,990 backward monologues using rejection sampling. is trained with 85k samples, and -$S$ with 195k samples. -R contains 24,712 debugging samples, each with the original description, buggy code, faulty trace, debugging rationale, and final patch.

§ TASK-SPECIFIC PREFIX

We append task-specific prefixes to the training samples to guide the model to perform different types of semantic reasoning.

§ BASELINE TRACE FORMATS

We present the baseline traces formats as we discussed and compared in Section <ref>.