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.
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:
- 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).
- 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.
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