PaperlayerView exact revision on arXiv

Source-linked AI summary

When Do Program-of-Thoughts Work for Reasoning?

Zhen Bi, Ningyu Zhang, Yinuo Jiang, Shumin Deng, Guozhou Zheng, Huajun Chen

arXiv:2308.15452v6cs.CLcs.AIcs.LGcs.SE

TL;DR

The relationship between code data and LLM reasoning improvement remains understudied, despite program-of-thought prompting using code for complex reasoning. The paper introduces CIRS to assess code's structural and logical complexity and applies complexity-guided synthesis and stratification to mathematical reasoning and code generation. It finds that optimal-complexity code is most effective for reasoning and reports favorable results across the two tasks.

  • Problem

    The relationship between code data and improved LLM reasoning remains understudied, despite program-of-thought prompting using code for complex reasoning.

    Source: §1 · p. 1

  • Method

    CIRS assesses code's structural and logical complexity, and an auto-synthesizing and stratifying algorithm is applied to mathematical-reasoning instruction generation and code-data filtering for code generation.

    Source: §1 · pp. 1–2

  • Results

    Optimal-complexity code is most effective for program-of-thought reasoning, and the proposed approach reports favorable results in mathematical reasoning and effectiveness for code generation.

    Source: §1 · p. 2, §8 · p. 8

  • Takeaways & Limitations

    Code with local structure and coherent knowledge circuitry is learnable at an optimal complexity level, whereas overly complex structure and logic are difficult for LLMs to learn.

    Source: §8 · pp. 7–8

    Current LLMs' understanding of complex knowledge is limited, and performance tends to decrease when data complexity is extremely high.

    Source: §5.2 · p. 4

Abstract

from arXiv · show

In the realm of embodied artificial intelligence, the reasoning capabilities of Large Language Models (LLMs) play a pivotal role. Although there are effective methods like program-of-thought prompting for LLMs which uses programming language to tackle complex reasoning tasks, the specific impact of code data on the improvement of reasoning capabilities remains under-explored. To address this gap, we propose complexity-impacted reasoning score (CIRS), which combines structural and logical attributes, to measure the correlation between code and reasoning abilities. Specifically, we use the abstract syntax tree to encode the structural information and calculate logical complexity by considering the difficulty and the cyclomatic complexity. Through an empirical analysis, we find not all code data of complexity can be learned or understood by LLMs. Optimal level of complexity is critical to the improvement of reasoning abilities by program-aided prompting. Then we design an auto-synthesizing and stratifying algorithm, and apply it to instruction generation for mathematical reasoning and code data filtering for code generation tasks. Extensive results demonstrates the effectiveness of our proposed approach. Code will be integrated into the EasyInstruct framework at https://github.com/zjunlp/EasyInstruct.

1 Introduction

The paper asks when code used in program-of-thought prompting improves LLM reasoning, and proposes measuring code complexity across structural and logical dimensions. It reports that code at an optimal complexity level is learnable and supports reasoning gains, then applies its synthesis and stratification algorithm to mathematical reasoning and code generation.

1 Introduction

  • The paper asks when program-of-thought prompting improves reasoning, noting that code-based prompting breaks complex problems into executable steps while the code–reasoning relationship remains understudied.It contrasts this approach with chain-of-thought prompting.Source: §1 · p. 1
  • CIRS measures the relationship between code reasoning steps and LLM reasoning capacity using structural and logical attributes.Its structural score uses AST node count, node type, and depth; its logical score integrates code difficulty and cyclomatic complexity.Source: §1 · pp. 1–2
  • Only code with an optimal level of structural and logical complexity contributes to effective reasoning enhancement; simpler code lacks knowledge and more intricate code can be too difficult to learn.The analysis also reports that current LLMs have limited understanding of symbolic knowledge such as code.Source: §1 · p. 2
  • The auto-synthesizing and stratifying algorithm generates and filters data for mathematical-reasoning instruction generation and code-generation tasks, with favorable reported results.The authors describe extensive results as demonstrating the approach's effectiveness.Source: §1 · p. 2

2 Background

The background describes code language models' use across reasoning and other tasks, and presents code-format chain-of-thought as an intermediate representation for multi-step problem solving.

2 Background

  • Code language models are used for tasks including commonsense and mathematical reasoning, and training on code data may foster reasoning as well as code understanding.The passage also reports that Codex outperforms GPT-3 on arithmetic reasoning and structural prediction despite equal parameter counts.Source: §2 · p. 2
  • Program-of-thought formalizes multi-step reasoning as code-format chain-of-thought and aims to maximize the likelihood of the answer given the question.Generated code serves as an intermediate step for solving the problem.Source: §2 · p. 2

3 Complexity-Impacted Reasoning Score

CIRS measures code-rationale complexity as the product of structural and logical complexity. Its structural component uses AST features, while its logical component integrates difficulty and cyclomatic complexity.

3 Complexity-Impacted Reasoning Score

  • CIRS defines a code rationale’s complexity-impacted reasoning score as the product of structural complexity and logical complexity.The score is intended to measure the relationship between code reasoning steps and their impact on LLM reasoning capacities.Source: §3 · p. 2
  • Structural complexity uses AST node count, node types, and tree depth, then normalizes, mean-pools, and sigmoid-transforms those features.The transformation maps the aggregate score to the range 0 to 1.Source: §3 · p. 2
  • Figure 2 outlines a pipeline that analyzes complexity distributions, splits data into three subsets, tests model parameters, and evaluates filtered data.The final evaluation uses data selected for the most effective complexity.Source: Figure 2 · p. 3
  • Logical complexity integrates problem-solving difficulty with cyclomatic complexity to account for operators, operands, and control flow.Difficulty uses operator and operand counts; cyclomatic complexity represents code control flow.Source: §3 · p. 3

4 Experimental settings

The experiments evaluate mathematical reasoning under zero- and few-shot settings and compare model performance across selected benchmarks. A separate trained-model evaluation includes both in-distribution and out-of-distribution tasks.

4 Experimental settings

  • Evaluation uses zero-shot and three-shot settings, counting an answer as correct only when the code executor returns the correct answer.Few-shot prompts contain three in-context examples with rationales.Source: §4 · p. 3
  • The zero-shot benchmark uses 500 randomly selected test instances each from AsDiv, GSM8K, MultiArith, and SVAMP, with gpt-3.5-turbo evaluated by accuracy.Source: §4 · p. 3
  • The trained LLaMA-7B evaluation compares Vicuna and Falcon and tests out-of-distribution MATH level-1 problems and selected BigBench-Hard tasks.The BigBench-Hard tasks cover algorithmic and multi-step arithmetic reasoning.Source: §4 · p. 4

5 Empirical Analysis

The empirical analysis finds that mid-range code complexity performs best for reasoning, while model scale and the form of the rationale also matter. It examines synthesized data across complexity levels, the characteristics of those levels, and whether the observed effects depend on data frequency.

5.1 Data synthesizing

  • The analysis synthesizes over 60,000 code samples from five mathematical-reasoning datasets and partitions generated data into low-, medium-, and high-CIRS subsets.Approximately 10,000 samples are generated from each seed dataset; 1,700 instances per complexity subset are used for model comparisons.Source: §5.1 · p. 4, §5.2 · p. 4

5.2 Impacts of different complexity score

  • Mid-range code complexity yields the best reasoning performance across four datasets; overly simple code offers little effect, while highly complex code may be difficult to learn.The study also reports that increasing complexity can make logical semantics and nested structures harder for LLMs to comprehend.Source: §5.2 · p. 4
  • As models grow from 7B to 65B parameters, reasoning effectiveness improves, and most fine-tuned 65B models approach GPT-3.5-turbo results.Differences across complexity levels are minimal for sufficiently large models.Source: §5.2 · p. 4
  • The authors report limits in current LLMs’ understanding of complex symbolic knowledge and argue that reasoning beyond mathematics requires more powerful external tools.They also identify limited understanding of complex knowledge in decoder-only architectures as a constraint.Source: §5.2 · pp. 4–5

5.3 The characteristics of different CIRS scores.

  • Low-CIRS samples are largely flat textual descriptions, while higher scores correspond to more programming structure and logic, with the highest scores associated with challenging math problems.The study describes the middle range as simple, direct programming with straightforward logical operations.Source: §5.3 · p. 5, Figure 4 · p. 5

5.4 Excluding the effect of the complexity distribution itself

  • CIRS-medium outputs show high accuracy across low-, medium-, and high-complexity test distributions, and the authors conclude that the effect is not explained by training-data frequency.In the reported distributions, CIRS-medium accuracy is 53.4, 46.1, and 47.3, respectively.Source: §5.4 · p. 6, Figure 5 · p. 6

5.5 Ablation analysis for textual rationales

  • Code-format solutions outperform textual rationales on all four evaluated datasets in the comparison using LLaMA-7B.The authors attribute the advantage to code's logical semantics and structure, as well as its executability by external interpreters.Source: §5.5 · p. 6

6 CIRS for Improving the Reasoning Ability

The section presents auto-synthesizing and stratifying to select code data by complexity, then applies it to mathematical instruction generation and code-data filtering. The reported results cover both mathematical reasoning and code generation.

6 CIRS for Improving the Reasoning Ability

  • The section applies the algorithm to instruction generation for mathematical reasoning and code-data filtering for code generation.For mathematical reasoning, the reported training set contains 40,000 samples targeting mid-range complexity.Source: §6 · p. 6, §6.2 · p. 6, §6.3 · p. 7

6.1 Auto-Synthesizing and Stratifying

  • The algorithm fills templates through APIs, computes CIRS thresholds, clusters synthesized data by complexity, and removes clusters outside the threshold set.It repeats cluster assignment and centroid updates until there are no further updates or the maximum iterations are reached.Source: §6.1 · p. 6

6.2 Usage1: CIRS-guided Instruction Generation

  • The CIRS-trained model outperforms Vicuna and Falcon in-distribution and performs best in zero-shot and few-shot out-of-distribution evaluation, with different comparisons on BigBench-Hard and MATH.The paper reports comparable effectiveness to ChatGPT on BigBench-Hard in zero-shot, but lower performance on MATH; it attributes the latter to limitations of code data itself.Source: §6.2 · pp. 6–7, Table 2 · p. 7

6.3 Usage2: CIRS-based Code Filtering

  • Code (CIRS)-LLaMA, trained on filtered Code Alpaca instructions, demonstrates effective performance on pure code-generation tasks.The filtered subset is described as containing higher-quality code instructions than the unfiltered training data.Source: §6.3 · p. 7, Table 3 · p. 7

7 Related Work

The related-work section surveys program-aided prompting and research on LLM reasoning. It positions this paper's focus on reasoning capabilities through code data as distinct from prior work.

Program-aided Prompting

  • Program-aided approaches use interpreters, intermediate programs, or code prompting for reasoning and related tasks.The cited work also includes neural-symbolic methods and code-based task formulations.Source: §7 · p. 7

Reasoning with Large Language Models

  • Prior LLM reasoning research spans capability analysis, fine-tuning, rationale generation, and complexity-based evaluation; the authors position code-data analysis as their distinction.The passage describes their work as the first to analyze LLM reasoning capabilities from code data.Source: §7 · p. 7

8 Discussion and Conclusion

The discussion identifies an optimal, learnable level of code complexity as most effective for reasoning and describes how structure and logic qualify that result. It also reports improved understanding of complex knowledge with larger models and outlines future task settings.

8 Discussion and Conclusion

  • Code data with an optimal level of complexity is most effective because it is learnable, while overly complex structure and logic are too difficult for LLMs.The conclusion also states that local structural properties and logical coherence or a degree of knowledge circuitry are important.Source: §8 · pp. 7–8
  • As language-model parameter counts increase, their understanding of complex knowledge also improves.Source: §8 · p. 8
  • The paper introduces CIRS to measure the relation between code reasoning steps and reasoning abilities, and identifies commonsense and logical reasoning as future scenarios.CIRS considers structural and logical code attributes; the paper describes AST-based structure and difficulty and cyclomatic complexity for logical complexity.Source: §8 · p. 8

Related papers

Loading 2308.15452v6…