When Do Program-of-Thoughts Work for Reasoning?

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

Introduction

Large Language Models (LLMs) have demonstrated significant potential in solving complex problems through Program-of-Thought (PoT) prompting. Unlike the traditional Chain-of-Thought (CoT) approach, which relies on natural language explanations, PoT requires models to generate executable code to derive solutions. This shift leverages the inherent structure and logic of programming languages to improve reasoning accuracy.

Conceptual overview of mapping code solutions to logic and structure for complexity analysis.

However, the effectiveness of PoT is not uniform across all types of code. This research investigates the relationship between the structural and logical attributes of code and the resulting improvement in LLM reasoning. The authors identify a "Goldilocks zone": models perform best when trained on code of moderate complexity—data that is too simple lacks informative signal, while data that is too complex exceeds the model's current capacity.

The Complexity-Impacted Reasoning Score (CIRS)

To quantify this relationship, the authors introduce the Complexity-Impacted Reasoning Score (CIRS). This metric evaluates code rationales across two primary dimensions:

  1. Structural Complexity ($Score_{SC}$): Analyzed via an Abstract Syntax Tree (AST), this measures the physical architecture of the code, including node count (size), node types (diversity of operations like loops or conditionals), and tree depth (nesting levels).
  2. Logical Complexity ($Score_{LC}$): Derived from software engineering principles, this combines Halstead Complexity (difficulty based on unique operators and operands) and McCabe’s Cyclomatic Complexity (the number of linearly independent paths through the code's control flow).

Methodology: Synthesis and Stratification

The researchers developed an automated pipeline to test their hypotheses. Starting with "seed" datasets like GSM8K and AQuA, they used an LLM to synthesize new problems and corresponding PoT solutions. These were then stratified into "low," "medium," and "high" complexity buckets using the CIRS metric for controlled training.

The full pipeline: from data synthesis and CIRS-based stratification to model training and evaluation.

Key Insights

  • The "Goldilocks" Principle: Reasoning performance follows a bell-shaped curve relative to complexity. Training on "mid-range" complexity data is most effective.
  • Code vs. Text: Training on code rationales consistently outperforms training on natural language rationales. Code's formal structure explicitly captures logical semantics that natural language often obscures.
  • Scaling and Complexity: While larger models (up to 65B parameters) handle higher complexity better than smaller ones, all models eventually encounter a complexity ceiling where performance degrades.

Results

A LLaMA-7B model fine-tuned on CIRS-guided medium-complexity data (CIRS-LLaMA) showed remarkable gains:

  • MultiArith Accuracy: Achieved 97.2%, rivaling much larger models and approaching GPT-3.5-turbo performance levels.
  • Generalization: Outperformed baselines like Vicuna and Falcon on both in-distribution and out-of-distribution tasks (e.g., MATH Level-1).
  • Code Filtering: Applying CIRS to filter the Code Alpaca dataset for optimal complexity improved code generation accuracy from 50.0% to 55.0%.

Conclusion

This work provides a systematic framework for understanding and optimizing PoT-based reasoning. By focusing on the "Goldilocks zone" of complexity, researchers can more effectively train LLMs for logical tasks. Future work will explore extending these metrics to commonsense reasoning and reducing the dependency on external code interpreters.

Summary updated

Abstract

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.
BibTeX
@misc{bi2023when,
  author = {Zhen Bi and Ningyu Zhang and Yinuo Jiang and Shumin Deng and Guozhou Zheng and Huajun Chen},
  title = {{When Do Program-of-Thoughts Work for Reasoning?}},
  year = {2023},
  eprint = {2308.15452},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2308.15452},
}
Figure