Evolutionary Pre-Prompt Optimization for Mathematical Reasoning

Technical Summary: Evolutionary Pre-Prompt Optimization for Mathematical Reasoning

Problem Statement
Large Language Models (LLMs) have demonstrated remarkable proficiency in few-shot learning, particularly when combined with Chain-of-Thought (CoT) prompting, which guides models to articulate intermediate reasoning steps. However, the performance of CoT prompting is highly sensitive to the selection and structure of the few-shot examples provided in the pre-prompt. While manual prompt engineering is common, it is often suboptimal and labor-intensive. Furthermore, existing automated methods often rely on per-example optimization or fine-grained gradient-based updates, which can be computationally expensive and prone to overfitting, especially given the limited size of reasoning benchmarks (e.g., GSM8k, MathQA) which are often insufficient for traditional fine-tuning. The core challenge addressed is how to systematically select a fixed, concise set of few-shot CoT examples that maximizes LLM performance on a specific downstream mathematical reasoning task without overfitting to the training data.

Methodology: Evolutionary Pre-Prompt Optimization (EPPO)
The authors propose Evolutionary Pre-Prompt Optimization (EPPO), a comparison-based evolutionary framework designed to optimize fixed few-shot pre-prompts at the task level.

• Formulation: The problem is framed as a combinatorial optimization task. A demonstration set $D$ (containing prompt-solution pairs) serves as a lookup table. The goal is to find a small subset of indices (a "few-shot pre-prompt") from $D$ that, when used as a static pre-prompt for all queries, maximizes the model's accuracy on a training set $T$.
• Optimization Algorithm: EPPO utilizes black-box evolutionary algorithms (e.g., Discrete (1+1)-ES, LogNormal, DoubleFastGA) implemented via the Nevergrad library. Crucially, the optimization is comparison-based. Instead of receiving absolute performance scores (which would require fine-grained feedback), the optimizer only receives the index of the best-performing candidate among a batch of $\kappa$ candidates in each iteration. This "ask-and-tell" paradigm relies on coarse feedback (ranking) rather than gradient information.
• Data Strategy: To manage computational costs, the authors employ a subsampling strategy to create demonstration sets. They also utilize a confidence-based subsampling method (using LLaMA2-70B response uncertainty) to ensure the demonstration set covers a diverse range of example difficulties.
• Generalization Analysis: The paper provides an information-theoretic analysis of the generalization risk. Because EPPO relies on limited feedback (comparisons) and a finite optimization budget, the authors derive bounds showing that the risk of overfitting is controlled and depends on the feedback granularity and budget, rather than the size of the ambient prompt space or the model's internal complexity. This contrasts with gradient-based methods that access fine-grained data and are more susceptible to overfitting in low-data regimes.

Key Contributions

1. Framework Introduction: The introduction of EPPO, a principled combinatorial optimization approach for selecting static few-shot CoT pre-prompts.
2. Empirical Superiority: Demonstration that controlled, exploitative evolutionary search outperforms brute-force selection, random search, and classical fine-tuning in low-data regimes, while reducing overfitting.
3. Performance Gains: Achievement of significant improvements (exceeding 10 absolute points in exact match scores) on benchmarks like GSM8k and MathQA using LLaMA2 models. These gains are robust across different decoding strategies and additive when combined with Self-Consistency (SC).
4. Mechanistic Insights: Analysis revealing that optimized pre-prompts induce more consistent and structured reasoning traces. The paper finds that prompt quality (specifically the selection of examples) is more critical than prompt length, and that larger few-shot sizes (e.g., 8-shot) can lead to overfitting in downsampled scenarios, whereas smaller sizes (e.g., 4-shot) often yield better generalization.
5. Theoretical Bounds: Derivation of generalization bounds for evolutionary few-shot optimization that characterize the effects of data size, population parallelism, and optimization budget, offering theoretical guarantees unavailable for gradient-based fine-tuning.

Experimental Results

• Benchmarks: The method was evaluated on GSM8k, SVAMP, MathQA, and MATH using LLaMA2-7B and LLaMA2-70B.
• Performance: EPPO consistently outperformed baselines (standard CoT, Long CoT, and Resprompt). On GSM8k with LLaMA2-70B, EPPO (4-shot) achieved 68.2% accuracy compared to 56.8% for standard CoT. Similar gains were observed on MathQA and MATH.
• Transferability:
  • Task Transfer: Pre-prompts optimized on GSM8k successfully transferred to SVAMP (which lacks a training set), improving performance over baselines.
  • Model Transfer: Prompts optimized for the larger 70B model transferred effectively to the 7B model, but the reverse (7B to 70B) was less effective, though still better than baselines.
• Overfitting Dynamics: Experiments showed that increasing the number of shots (e.g., from 4 to 8) in a downsampled training setting led to overfitting (higher training accuracy but lower test accuracy). However, using the full training set mitigated this issue.
• Efficiency: EPPO requires significantly less computational resources and memory than backpropagation-based fine-tuning, as it does not involve a backward pass.

Significance and Claims
The paper claims that EPPO offers a robust, efficient, and theoretically grounded alternative to both manual prompt engineering and gradient-based fine-tuning for mathematical reasoning tasks. By leveraging comparison-based evolutionary optimization, the method effectively navigates the prompt selection space while maintaining strong generalization guarantees in data-scarce environments. The authors emphasize that the success of EPPO stems not merely from finding "better" examples, but from finding a concise set of examples that induce more consistent reasoning patterns in the LLM. The work suggests that the key to effective CoT reasoning lies in the strategic selection of prompt content rather than simply increasing prompt length or relying on complex, per-example retrieval mechanisms. Furthermore, the paper posits that EPPO's additive compatibility with Self-Consistency and other bootstrapping methods makes it a versatile component for enhancing LLM reasoning capabilities.