Technical Summary: Prompting Policies for Multi-step Reasoning and Tool-Use in Black-box LLMs with Iterative Distillation of Experience

1. Problem Statement

The paper addresses the "fine-tuning bottleneck" inherent in the modern landscape of Large Language Models (LLMs). As the industry shifts toward proprietary, "black-box" models (e.g., Gemini-Pro, GPT-5) accessible only via API, traditional transfer learning techniques like full parameter updates or Parameter-Efficient Fine-Tuning (PEFT) such as LoRA are rendered impossible due to the lack of access to model weights, gradients, or internal computation graphs.

Consequently, task adaptation relies on In-Context Learning (ICL) and prompt engineering. However, manual prompt engineering is heuristic and fragile; LLMs are highly sensitive to "semantic noise," where minor perturbations in phrasing or example ordering can cause significant performance fluctuations. While Automated Prompt Optimization (APO) methods exist, many rely on evolutionary algorithms or LLM-based reflections that treat optimization as heuristic generation rather than a structured policy. These methods often struggle with complex, multi-step reasoning trajectories and lack the sample efficiency required for robust deployment.

2. Methodology

The authors propose a Reinforcement Learning (RL) framework that trains a learned "Prompter Policy" to optimize prompts for a larger, frozen "Worker" LLM. The core innovation lies in decoupling the control logic (the prompter) from the execution logic (the worker) and utilizing an Iterative Distillation of Experience.

2.1 Dual-Agent Architecture

• Prompter Agent ($\pi_\theta$): A smaller, efficient LLM (e.g., 2–10 billion parameters) that acts as the trainable policy. It generates task instructions (prompts) based on the task context and a history of past experiences. Gradients are computed exclusively for this model.
• Frozen Worker Agent ($\pi_{LLM}$): A large, frozen reasoning engine (e.g., 1 trillion parameters) that executes the instructions generated by the Prompter. It serves as the environment and provides the output.

2.2 The Objective

The goal is to learn parameters $\theta$ for the prompter policy $\pi_\theta$ that maximize the expected reward $R(p, x, y)$ over a dataset $D$, while minimizing deviation from a reference policy $\pi_{ref}$ via a KL-divergence penalty:
$$J(\theta) = \mathbb{E}_{(x,y) \sim D, p \sim \pi_\theta(\cdot|c,H)} [R(p, x, y) - \alpha D_{KL}(\pi_\theta \parallel \pi_{ref})]$$
The framework supports both Fixed Prompt Optimization (learning a single static prompt) and Dynamic Prompt Optimization (learning a meta-policy that adapts to specific task contexts).

2.3 Contrastive Experience Buffer

To address the sparsity of scalar rewards (correct/incorrect) and the computational cost of multi-turn self-reflection, the authors introduce a Contrastive Experience Buffer.

• Mechanism: The buffer stores trajectories of $(prompt, critique, reward)$. Critiques are dense textual descriptions of discrepancies between the Worker's output and the ground truth, generated by an external feedback model.
• Amortization: Instead of performing multi-turn reflection during inference, the prompter is conditioned on a sampled history $H$ from the buffer during training. This allows the policy to "distill" complex, multi-turn reasoning and correction patterns into its weights.
• Update Strategy: Prompts are added to the buffer if their reward meets a threshold relative to the batch maximum ($r \ge r_{max} - \epsilon$), ensuring a diverse yet high-performing history.

3. Key Contributions

1. Dual-Agent Distillation with Memory: A framework where strategic steering is distilled into an efficient, memory-augmented Prompter policy. This enables the model to learn from experience, effectively compressing complex reasoning trajectories into a streamlined policy.
2. Contrastive Experience Buffer: A high-bandwidth feedback mechanism coupling scalar rewards with dense textual critiques. The authors provide a formal characterization showing how this amortizes multi-turn self-reflection loops into single-shot policy weights, achieving up to 2.4× faster convergence compared to scalar-only baselines.
3. Discovery of Algorithmic Heuristics: Qualitative analysis reveals that the learned policy evolves to discover specialized strategies, such as "Ground Truth Anchoring" (distrusting provided traces in favor of raw input) and "Atomic Sequencing" for tool calls, rather than relying on abstract guidance.
4. Empirical Validation: The approach is validated on the Big Bench Extra Hard (BBEH) suite for logic-intensive reasoning and the $\tau$-bench for agentic tool-use workflows.

4. Experimental Results

The experiments utilize Gemini 2.5 Flash as the frozen Worker and Gemini 2.5 Flash-lite as the trainable Prompter.

4.1 Reasoning Tasks (BBEH)

The Prompter Policy with Experience Buffer significantly outperformed both zero-shot baselines and the state-of-the-art evolutionary baseline, GEPA.

• Dyck Languages: Improved from 63.33% (Baseline) to 91.25% (Prompter Policy), a gain of +27.92% over GEPA.
• Web of Lies: Improved from 52.50% (Baseline) to 90.12%, a gain of +37.62% over GEPA.
• Disambiguation QA: Improved from 57.08% to 65.41%.

4.2 Tool-Use Tasks ($\tau$-Bench)

The policy demonstrated substantial gains in multi-step tool-use scenarios (Retail and Airline domains).

• Retail: Achieved 91.30% success rate (vs. 73.91% baseline).
• Airline: Achieved 83.33% success rate (vs. 65.27% baseline).
• The RL-tuned prompts outperformed GEPA by replacing abstract guidance with concrete, procedural workflows (e.g., explicit batching of tool calls, strict state verification).

4.3 Cross-Model Generalization

The policy trained on the Flash model showed forward compatibility, successfully steering the larger Gemini Pro model to an 80% success rate on Dyck Languages (a +7.5% gain over its zero-shot baseline). Conversely, it bridged the gap between models, allowing the mid-tier Flash model (91% with optimized prompt) to outperform the larger Pro model (72.5% with zero-shot prompting).

5. Significance and Claims

The paper claims that the proposed RL framework with iterative distillation of experience represents a significant advancement in interacting with black-box LLMs. By treating prompt generation as a Markov Decision Process and utilizing a contrastive experience buffer, the approach:

• Overcomes the Fine-Tuning Bottleneck: It enables the optimization of task-specific strategies without accessing model weights.
• Improves Sample Efficiency: The integration of dense textual critiques into the reward signal allows for faster convergence and better performance than evolutionary baselines or scalar-only RL.
• Enables Structural Evolution: The policy does not just find a "better" prompt; it discovers specialized algorithmic heuristics (e.g., independent stack simulation, anchor-and-chain deduction) that fundamentally change how the worker model approaches the task.
• Offers Cost-Benefit Advantages: The framework allows smaller, cheaper models to achieve performance levels comparable to or exceeding larger, zero-shot models through learned instructional steering.

The authors acknowledge limitations, noting that the policy was trained on a limited set of tasks and that its capacity for zero-shot transfer to entirely unseen tasks without buffer initialization remains a challenge for future study. They also suggest future work in sophisticated buffer management and personalized prompt generation based on user state representations.