PaperlayerView exact revision on arXiv

Source-linked AI summary

Structured Chain-of-Thought Prompting for Code Generation

Jia Li, Ge Li, Yongmin Li, Zhi Jin

arXiv:2305.06599v3cs.SEcs.CL

TL;DR

CoT prompting offers limited accuracy gains for code generation because it uses natural-language reasoning for a structured output. The paper proposes SCoT prompting, which builds intermediate reasoning from program structures before generating code, and reports improved benchmark accuracy, developer preference, and robustness to examples.

  • Problem

    CoT prompting is designed for natural-language generation and brings only slight improvements to code-generation accuracy.

  • Method

    SCoT prompting first asks LLMs to generate intermediate reasoning using sequence, branch, and loop structures, then generates code from that SCoT.

  • Results

    SCoT prompting significantly outperforms CoT prompting across three benchmarks in Pass@k and human evaluation, with up to 13.79% higher Pass@1.

  • Takeaways & Limitations

    SCoT prompting produces stable improvements, is robust to examples, and is effective across different LLMs and programming languages.

  • Takeaways & Limitations

    Benchmark data leakage remains possible because existing LLMs may have been trained on experimental benchmarks, although relative comparisons within each base model are considered credible.

Abstract

from arXiv · show

Large Language Models (LLMs) (e.g., ChatGPT) have shown impressive performance in code generation. LLMs take prompts as inputs, and Chain-of-Thought (CoT) prompting is the state-of-the-art prompting technique. CoT prompting asks LLMs first to generate CoTs (i.e., intermediate natural language reasoning steps) and then output the code. However, CoT prompting is designed for natural language generation and has low accuracy in code generation. In this paper, we propose Structured CoTs (SCoTs) and present a novel prompting technique for code generation, named SCoT prompting. Our motivation is source code contains rich structural information and any code can be composed of three program structures (i.e., sequence, branch, and loop structures). Intuitively, structured intermediate reasoning steps make for structured source code. Thus, we ask LLMs to use program structures to build CoTs, obtaining SCoTs. Then, LLMs generate the final code based on SCoTs. Compared to CoT prompting, SCoT prompting explicitly constrains LLMs to think about how to solve requirements from the view of source code and further the performance of LLMs in code generation. We apply SCoT prompting to two LLMs (i.e., ChatGPT and Codex) and evaluate it on three benchmarks (i.e., HumanEval, MBPP, and MBCPP). (1) SCoT prompting outperforms the state-of-the-art baseline - CoT prompting by up to 13.79% in Pass@1. (2) Human evaluation shows human developers prefer programs from SCoT prompting. (3) SCoT prompting is robust to examples and achieves substantial improvements.

1 INTRODUCTION

Code-generation prompting remains an open question because standard CoT prompting yields only slight improvements. SCoT prompting addresses this by structuring intermediate reasoning around program structures before code generation, and experiments report higher accuracy and broader robustness.

  • Motivation: Prompting technique remains an open question because code-generation performance heavily relies on the prompt.LLMs take prompts containing examples and a new requirement, then generate a program from them.
  • Proposed approach: SCoT uses sequence, branch, and loop structures to construct intermediate reasoning steps for structured code generation.The approach is motivated by source code’s rich structural information and by the decomposition of programs into these three structures.
  • Proposed approach: SCoT prompting asks LLMs to generate a structured CoT first and implement the final code afterward, explicitly constraining reasoning from a programming-language perspective.The paper presents this as a prompting technique intended to improve code-generation accuracy.
  • Evaluation: 13.79% is the largest reported Pass@1 improvement over CoT, with gains of up to 12.31% on MBPP and 6.63% on MBCPP.The evaluation covers ChatGPT and Codex on HumanEval, MBPP, and MBCPP, using unit tests and Pass@k.
  • Evaluation: Human developers prefer SCoT-generated programs, while improvements remain effective across LLMs and programming languages and do not depend on specific examples or writing styles.The reported model-specific gains reach up to 13.79% for ChatGPT and 13.77% for Codex in Pass@1.

2 METHODOLOGY

SCoT represents intermediate reasoning with nested program structures and input-output information, then uses a two-prompt process to generate and implement that reasoning. The method also includes mechanisms for checking and correcting noisy intermediate steps.

  • Structured Chain-of-Thought: SCoT denotes intermediate reasoning steps constructed from sequence, branch, and loop structures before final code generation.The methodology presents SCoT and SCoT prompting as separate but connected components.
  • Structured Chain-of-Thought: Sequence steps remain at one level, branches condition actions, and loops repeat steps until specified conditions are unmet.Branch formats include if, if-else, and if-elif-else; loop formats include for and while.
  • Structured Chain-of-Thought: Different program structures may be nested, allowing SCoT to represent more complex solving processes.Examples show SCoT flexibly combining various structures.
  • Structured Chain-of-Thought: The input-output structure records parameters and types to clarify program entry, exit, and the subsequent solving process.It complements the three basic program structures.
  • SCoT prompting: SCoT prompting uses one prompt to generate a SCoT from requirement–SCoT examples and a second prompt to generate code from the requirement and SCoT.The second prompt treats SCoT as a soft template and uses requirement–SCoT–code examples.
  • Error handling: The method asks LLMs to double-check SCoTs and supports human correction before code generation to reduce error accumulation.The two-step pipeline also provides an opportunity to inspect where the SCoT goes wrong.
  • Implementation: SCoT prompting is designed to avoid dependence on a specific LLM and uses manually written SCoTs for a small set of example seeds.The default setup uses three examples, with templates and examples available in the replication package.

3 STUDY DESIGN

The study evaluates SCoT prompting against established prompting baselines across two LLMs and three code-generation benchmarks. It measures accuracy, developer preferences, robustness to examples, and the contributions of program structures using controlled sampling and Pass@k.

  • Research Questions: The research questions assess accuracy, developer preferences, robustness to examples, and the contributions of individual program structures.Developer evaluation covers correctness, code smell, and maintainability; robustness varies example seeds and writing styles; structure contributions are tested by removing structures individually.
  • Datasets: Evaluation covers HumanEval and MBPP in Python and MBCPP in C++ using original dataset splits and test-data performance.HumanEval contains 164 hand-written Python programming problems, and MBPP examples are reused for HumanEval prompts because HumanEval lacks training data.
  • Evaluation Metrics: Pass@k measures the percentage of requirements solved by at least one of k generated programs, with higher values indicating better performance.The experiments use k values of 1, 3, and 5 and employ the unbiased Pass@k estimator with n=20 generated programs per requirement.
  • Comparison Baselines: The study compares SCoT prompting with zero-shot, few-shot, and CoT prompting baselines.All approaches use the same number of examples and example seeds for fairness.
  • Implementation Details: Each baseline and SCoT configuration generates 20 programs per requirement under matched sampling budgets.SCoT first samples 20 SCoTs and then generates one program per SCoT; its total generation length matches CoT prompting.

4 RESULTS AND ANALYSIS

Across three benchmarks, SCoT prompting improves code-generation accuracy over baselines, and developers rate its programs more highly. The approach remains effective across example seeds and writing styles, while program structures contribute to its performance.

  • Accuracy results: SCoT prompting improves Pass@1 over few-shot prompting by up to 16.05% in HumanEval, 17.45% in MBPP, and 9.56% in MBCPP.
  • Accuracy results: 13.79%, 12.31%, and 6.63% are SCoT prompting’s maximum Pass@1 improvements over CoT prompting on HumanEval, MBPP, and MBCPP, respectively.
  • Human evaluation: 15.27%, 10.66%, and 15.90% are SCoT prompting’s relative improvements over CoT prompting in correctness, code smell, and maintainability.
  • Robustness to examples: SCoT prompting substantially outperforms CoT prompting across different example seeds and annotators’ writing styles, despite slight performance variances.
  • Program-structure contributions: Removing the three basic structures causes an obvious performance drop, while removing the input-output structure decreases performance slightly.
  • Program-structure contributions: The input-output structure improves ChatGPT by up to 6.37% in Pass@1, and the three basic structures improve it by up to 12.73%.

5 DISCUSSION

The discussion positions SCoT prompting as complementary to ranking methods and examines usability, validity threats, and experimental scope. It also reports that combining SCoT with CodeT continually improves ChatGPT’s MBPP performance.

  • 5.1 SCoT vs. Pseudocode: 26% of 100 manually reviewed SCoTs were very close to pseudocode, supporting their potential usability for understanding and maintaining generated programs.The authors note that SCoTs can be inserted into comments and help future maintenance.
  • 5.1 SCoT vs. Pseudocode: SCoT prompting separates solution exploration from standardized program implementation, unlike pseudocode’s more detailed implementation steps.The authors report that SCoT prompting substantially outperforms its pseudocode-based variant, SCoT-P, on three benchmarks.
  • 5.2 SCoT prompting vs. Rank Techniques: SCoT prompting and ranking techniques are complementary: SCoT generates programs, while ranking methods select among multiple outputs.Users can generate many programs with SCoT prompting and then apply ranking techniques to choose a final output.
  • 5.2 SCoT prompting vs. Rank Techniques: ChatGPT’s MBPP performance continually improves when CodeT and SCoT prompting are progressively added.The experiment is exploratory and uses ChatGPT as the base model.
  • 5.2 SCoT prompting vs. Rank Techniques: Ranking techniques require execution environments and test-case results, whereas SCoT prompting operates without execution results in general programming scenarios.The authors therefore consider direct comparisons between the approaches unfair because they use different resources and target different settings.
  • 5.3 Threats to Validity: The study identifies threats involving benchmark generalizability, the two-step pipeline, and possible data leakage from training corpora.The authors argue that ablations support program structures as the source of improvements and that relative comparisons remain credible despite possible leakage.

6 RELATED WORK

Related work covers source-code language models and prompting techniques, culminating in SCoT prompting, which introduces program structures into intermediate reasoning and outperforms CoT on three benchmarks.

  • Source-Code Language Models: Source-code LLMs are large neural networks pretrained on natural-language text and source code, spanning standard and instruction-tuned models.Standard models use next-token prediction, while instruction-tuned models are trained to follow user instructions.
  • Prompting Techniques: Prompting techniques generate code by supplying LLMs with task instructions, requirements, and sometimes requirement–code examples.The related work distinguishes zero-shot prompting from few-shot prompting by whether examples are included.
  • Prompting Techniques: CoT prompting generates intermediate natural-language reasoning steps before final code and has achieved state-of-the-art results in natural-language generation.The paper presents SCoT as a code-generation-specific development of this prompting paradigm.
  • Structured Chain-of-Thought Prompting: SCoT prompting explicitly introduces sequence, branch, and loop structures into intermediate reasoning steps before code generation.The paper reports that SCoT significantly outperforms CoT on HumanEval, MBPP, and MBCPP.

7 CONCLUSION AND FUTURE WORK

The paper concludes that SCoT prompting structures intermediate reasoning with program constructs and improves code-generation outcomes relative to CoT. Future work will investigate tree-based prompting using representations such as abstract syntax trees.

  • 7 CONCLUSION AND FUTURE WORK: CoT prompting remains a state-of-the-art code-generation approach but has low accuracy, motivating a structured alternative.CoT first produces natural-language reasoning steps and then outputs code.
  • 7 CONCLUSION AND FUTURE WORK: SCoT prompting generates structured intermediate reasoning with sequence, branch, and loop structures before producing code.Across three benchmarks, the paper reports improvements over CoT in Pass@k and human evaluation, with robustness to examples.
  • 7 CONCLUSION AND FUTURE WORK: Future work will explore tree-based prompting in which LLMs generate source-code representations such as abstract syntax trees.This extends the paper’s structural prompting idea beyond the three basic program structures.
Loading 2305.06599v3…