Skip to content

Meta-Prompt Optimization for LLM-Based Sequential Decision Making

Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Reasoning
Keywords: Prompt Optimization, Sequential Decision Making, Adversarial Bandits, Exponential Weights, In-Context Learning

TL;DR

To resolve the failure of traditional prompt optimization caused by non-stationary rewards during LLM agent interactions, this paper proposes EXPO (grounded in adversarial bandits) and its exemplar selection extension EXPO-ES, which dynamically optimize task descriptions, meta-instructions, and exemplar sequences to significantly accelerate convergence and reduce regret.

Background & Motivation

Large language models (LLMs) have emerged as powerful autonomous agents for complex sequential decision-making tasks, including multi-armed bandits (MAB), Bayesian optimization (BO), and reinforcement learning (RL). In existing agent frameworks (such as OPRO and LLM-based MAB), the agent is prompted at each time step using a structured meta-prompt containing a task description, a meta-instruction specifying how to choose the next action, and a sequence of historical interaction exemplars. However, virtually all previous literature relies on fixed, manually designed meta-prompts throughout the entire sequential decision-making trajectory. Extensive prompt engineering literature indicates that LLM behavior is acutely sensitive to prompt phrasing, and handcrafted instructions often suffer from subtle semantic misinterpretations—such as misunderstanding descending score ordering as decreasing quality—severely handicapping agent capabilities.

The fundamental technical barrier preventing the direct application of existing automated prompt optimization methods is the intrinsic non-stationarity of observed rewards in sequential decision making. In standard prompt optimization scenarios, prompt quality is assessed against a fixed, stationary benchmark dataset where the reward distribution remains constant across iterations. In contrast, an LLM agent interacting with an environment experiences continuous state transitions and context evolution: in BO and MAB, candidate solutions discovered in later stages yield systematically higher rewards than early explorations, while in RL the rewards are directly conditioned on time-varying environmental states. Consequently, identical meta-prompts receive dynamically shifting reward signals across different iterations, completely violating the stationary reward distribution assumption underpinning stochastic bandit and evolutionary prompt optimizers such as INSTINCT, PromptBreeder, and MIPRO.

To resolve this core tension, the authors draw inspirations from adversarial bandits, a theoretical framework specifically developed to handle arbitrary, non-stationary, and adversarial reward feedback across time. Rather than assuming static rewards, adversarial bandit algorithms optimize the cumulative performance to compete against the best single decision arm in hindsight. Core idea: formulate meta-prompt selection in sequential decision making as an adversarial multi-armed bandit problem, proposing an exponential-weight optimization framework (EXPO) with neural surrogate score estimation, coupled with an exemplar sequence optimization extension (EXPO-ES) featuring historical model ensembling and cyclical permutation to conquer reward non-stationarity.

Method

Overall Architecture

The paper introduces EXPO (Algo. 1) for optimizing task descriptions and meta-instructions, along with its extension EXPO-ES (Algo. 2) for joint exemplar sequence optimization. In the offline stage, a frontier LLM (e.g., GPT-4) paraphrases an initial task description \(D_0\) and meta-instruction \(I_0\) into \(k_1\) and \(k_2\) variants respectively, forming a discrete combinatorial domain of \(k = k_1 \times k_2\) arms whose pre-trained text embeddings are pre-computed and cached. At each online decision iteration, the algorithm samples a candidate task description and meta-instruction pair from an exponential-weight probability distribution constructed from surrogate neural network cumulative estimates, compiles the meta-prompt with selected exemplars, executes mixed-temperature batch action queries in the environment, and records the deterministic evaluation feedback. Finally, an online multi-layer perceptron (MLP) surrogate is updated via mean squared error to re-estimate the scores of all candidate arms and refresh the exponential sampling distribution.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Offline Domain Construction<br/>GPT-4 paraphrasing generates k1×k2 candidate arms"] --> B["Exponential-Weight Arm Sampling<br/>Numerically stabilized probability distribution Pt"]
    B --> C["Mixed-Temperature Action Selection<br/>T=1 diverse exploration + T=0 deterministic evaluation"]
    C --> D["Temporal Embedding Surrogate Modeling<br/>Lightweight MLP predicting scores via MSE loss"]
    D --> E["Dynamic Exemplar Sequence Optimization EXPO-ES<br/>Historical parameter ensemble + cyclical permutation"]
    E -->|Cumulative score update & environment state transition| B

Key Designs

1. Exponential-Weight Randomized Meta-Prompt Selection: Non-Stationary Reward Handling and Numerical Stabilization Traditional prompt optimization methods based on greedy or stochastic exploration converge prematurely to locally suboptimal prompts, as early low scores permanently bias cumulative empirical averages. Guided by the classical EXP3 adversarial bandit framework, EXPO treats each combinatorial meta-prompt \((D_i, I_i)\) as an arm \(i \in \{1, \dots, k\}\). Because evaluating all \(k\) candidate prompts in the actual environment at every iteration is computationally prohibitive, EXPO leverages a neural network surrogate to predict instantaneous scores for all arms, maintaining a cumulative predicted score \(\hat{s}_i^{(t+1)} = \hat{s}_i^{(t)} + \mathcal{M}(g(D_i) \oplus g(I_i); \theta_{t+1})\). To eliminate floating-point overflow during exponentiation, a dynamic per-iteration translation constant \(C(t) = \max_j S_j^{(t)}\) is subtracted before computing softmax probabilities: $\(P_t[i] = \frac{\exp\left(\eta (\hat{s}_i^{(t+1)} - C(t))\right)}{\sum_{j=1}^k \exp\left(\eta (\hat{s}_j^{(t+1)} - C(t))\right)}\)$ The paper provides a formal equivalence proof showing that subtracting \(C(t)\) preserves the exact probability distribution. The learning rate \(\eta\) explicitly calibrates exploration versus exploitation: the inherent sampling entropy guarantees continuous exploratory pressure across the prompt space, while exponential scaling ensures that high-performing arms receive dominating selection mass.

2. Mixed-Temperature Batch Action Selection and Surrogate Evaluation: Decoupling Exploration from Feedback Reliability Prompt update reliability in sequential tasks depends entirely on the fidelity of scalar feedback received from the environment. Single-sample decoding with high temperature injects severe reward variance, whereas greedy decoding collapses the exploration breadth needed for hard global optimization tasks. To reconcile this dilemma, EXPO executes a batch of 8 action queries under the current meta-prompt \(Q_t\): 7 inferences are executed with high temperature \(T=1\) to explore diverse candidate solutions (such as regression parameters or TSP tours), while the 8th inference is strictly decoded with temperature \(T=0\). The scalar evaluation score \(s_t = \xi(x_t)\) of this deterministic 8th action is designated as the clean, noiseless surrogate training label. The state pair \((g(D_t) \oplus g(I_t), s_t)\) is appended to history \(S_{t+1}\) to train the MLP surrogate, ensuring the proxy model fits real prompt efficacy rather than sampling noise.

3. EXPO-ES Exemplar Sequence Optimization: Historical Parameter Ensembling and Cyclical Positional De-Biasing In-context learning is sensitive not only to exemplar demonstration quality but also to presentation order. Because the pool of available exemplars continuously grows with each environmental iteration, the domain of candidate exemplar sequences dynamically shifts over time. EXPO-ES tackles this non-stationary, open-domain setting by maintaining a historical archive of trained surrogate network parameters \(\Theta_{\text{history}} = \{\theta_1^{ES}, \dots, \theta_{t+1}^{ES}\}\). In each round, \(k_{ES}\) candidate ordered sequences of length \(L\) are sampled, and their cumulative scores are computed across the entire parameter ensemble: $\(\hat{s}_j^{(\text{final})} = \sum_{\theta^{ES} \in \Theta_{\text{history}}} \mathcal{M}_{ES}(g(E_j^{t+1}); \theta^{ES})\)$ For structured tasks like MAB where interaction summaries follow a fixed set of actions/buttons, EXPO-ES deploys an elegant cyclical permutation scheme: candidate sequences are constructed by cyclically shifting button order across \(K\) rotations. This guarantees that every action occupies every positional rank uniformly, systematically neutralizing LLM positional bias without requiring parameter history storage.

Loss & Training

The surrogate neural networks take frozen embeddings generated by OpenAI's text-embedding-3-large (dimension 3072) as input. For joint optimization of task descriptions and meta-instructions (LR and TSP), the concatenated embedding vector has dimension 6144 and feeds into an MLP with a single hidden layer of width 1536. For single-component instruction optimization or exemplar sequence scoring, the embedding dimension is 3072 with a hidden layer width of 512. The network parameter vector \(\theta\) is updated online using the Mean Squared Error (MSE) objective: $\(\mathcal{L}_{\text{MSE}}(\theta) = \frac{1}{|S_{t+1}|} \sum_{i=1}^{|S_{t+1}|} \left( \mathcal{M}(\mathbf{z}_i; \theta) - s_i \right)^2\)$ Optimized via Adam, the learning rate hyper-parameter for arm selection is set to \(\eta_{\text{desc}}=100\) for LR and TSP, \(\eta_{\text{meta-inst}}=50\) for instruction optimization, and \(\eta_{\text{desc}}=10\) for MAB. For exemplar selection, \(\eta_{\text{exemplar}}\) is set to 25 in continuous domains and 10 in MAB. Ablation experiments demonstrate that concatenating exemplar embeddings directly into the main surrogate input increases dimensionality to 9216, causing severe surrogate degradation; decoupling macro-prompt optimization from exemplar sequencing is crucial for empirical convergence.

Key Experimental Results

Main Results

Empirical evaluations were conducted across continuous parameter search (Linear Regression LR), discrete combinatorial routing (Traveling Salesman Problem TSP), prompt self-improvement (GSM8K), and Multi-Armed Bandits (MAB), utilizing GPT-3.5-Turbo, GPT-4-Turbo, and Qwen-2.5-7B-Instruct.

Task Setting Evaluation Metric (Lower / Higher is Better) Baseline OPRO Enhanced OPRO EXPO (Ours) EXPO-ES (Ours) Advantage / Convergence Highlights
LR (\(w=2, b=30\)) Regression MSE (\(\downarrow\)) ~170 (50 iters) ~130 (50 iters) ~20 < 5 Error reduced by an order of magnitude, >3× speedup
LR (\(w=36, b=-1\)) Regression MSE (\(\downarrow\)) ~250 (50 iters) ~210 (50 iters) ~40 ~10 Escapes deceptive local minima, 95% error drop
TSP (10 Nodes) Optimality Gap (\(\downarrow\)) 25.4% 18.2% 0.8% 0.8% Reaches near-optimal tour, sub-1% gap
TSP (15 Nodes) Optimality Gap (\(\downarrow\)) 48.6% 37.1% 12.5% 12.3% 74.3% relative reduction over standard OPRO
TSP (20 Nodes) Optimality Gap (\(\downarrow\)) 118.2% 94.5% 42.1% 41.8% Drastically cuts tour distance on complex graphs
GSM8K Instruction Opt. Test Accuracy (\(\uparrow\)) 75.8% — 84.6% 88.2% +12.4% absolute accuracy boost over baseline
MAB BSSND (Easy) Cumulative Regret (\(\downarrow\)) 8.8 (Original) — 3.2 2.6 Substantially eliminates exploration freezing
MAB BSSCD (Hard) Cumulative Regret (\(\downarrow\)) 9.4 (Original) — 4.8 3.8 Dynamic balance cuts cumulative regret by >55%

In terms of runtime efficiency on the Linear Regression task (\(w=2, b=30\)), the wall-clock time required to achieve target MSE thresholds is detailed below:

Method Time (s) to MSE \(\le 100\) Time (s) to MSE \(\le 50\) Time (s) to MSE \(\le 25\) Time (s) to MSE \(\le 10\) Total Runtime (s)
OPRO 64.1 170.1 Failed (NA) Failed (NA) 731.4 (300 iters)
EXPO (Ours) 94.5 207.4 263.1 350.8 1645.6

Ablation Study

Ablation experiments evaluate the necessity of joint component optimization, validate adversarial modeling against general prompt optimizers, and investigate sensitivity to exploration parameter \(\eta\).

Configuration / Baseline LR (\(w=2, b=30\)) MSE LR (\(w=36, b=-1\)) MSE TSP (20 Nodes) Gap (%) Key Insight & Mechanism
OPRO (Enhanced Baseline) 132.5 212.0 94.5% Fixed manual prompt traps agent in suboptimal plateaus
MIPRO (General Optimizer) 165.2 240.1 — Fails under non-stationary sequential reward observations
PromptBreeder (Evolutionary) 148.0 225.4 — Random mutation lacks sample-efficient adaptive feedback
INSTINCT (Stochastic MAB) 115.0 175.2 78.4% Static reward assumption causes heavy early reward dragging
EXPO (Task-Description Only) 68.4 112.3 64.2% Lacks fine-grained output format and constraint tuning
EXPO (Meta-Instruction Only) 52.1 95.6 58.7% Misses adaptive grounding of objective context
EXPO (Joint \(D + I\)) 21.3 42.5 42.1% Synergistic co-evolution yields superior prompt efficacy
EXPO (\(\eta=10\), High Explore) 38.6 65.2 41.5% Promotes escaping local optima in hard 20-node TSP
EXPO (\(\eta=1000\), Low Explore) 18.2 39.1 58.6% Rapid convergence on easy tasks; premature lock-in on hard tasks

Key Findings

  • Adversarial Bandits Outperform Stochastic Optimizers Under Non-Stationarity: Standard prompt optimization baselines (INSTINCT, PromptBreeder, MIPRO) severely degrade in sequential decision making because environmental progression causes rewards to drift upward. Stochastic MAB algorithms compute unweighted historical averages that remain permanently depressed by initial exploration rounds, whereas EXPO's exponential-weight mechanism rapidly adapts to non-stationary feedback.
  • Task-Dependent Value of Exemplar Sequencing: EXPO-ES delivers major performance leaps in Linear Regression (MSE dropping from 21.3 to <5) and instruction generation (+3.6% accuracy), but offers negligible gains in TSP. In continuous regression, coordinate pairs directly communicate numerical curvature to the LLM, whereas in combinatorial graph routing, the LLM struggles to parse spatial graph heuristics from raw string traces, causing prompt instruction semantics to dominate.
  • Curse of Dimensionality in Surrogate Modeling: Direct concatenation of exemplar embeddings into the primary surrogate MLP input (Fig. 16) inflates feature dimensionality from 6144 to 9216, degrading generalization and yielding inferior performance compared to the standard decoupled architecture.

Highlights & Insights

  • Adversarial Bandit Formulation for Non-Stationary Agent Trajectories: Seamlessly ports EXP3 theory into the prompt engineering paradigm, overcoming the invalid stationary assumptions of prior work and establishing a rigorous mathematical foundation for agent prompt adaptation.
  • Diagnosing Semantic Misinterpretations in Prompting: Uncovers critical failure modes where LLMs confuse syntactic descending order of loss metrics with semantic quality rank, introducing prompt enhancements that eliminate counter-productive optimization trajectories.
  • Broad Transferability Across Agent Pipelines: The core principle of modeling time-varying prompt utility via lightweight surrogate feedback is directly applicable to code synthesis agents, multi-step tool-use agents, and interactive reinforcement learning environments.

Limitations & Future Work

  • Closed-Domain Rephrasing Bottleneck: Candidate task descriptions and meta-instructions are restricted to an initial \(k_1 \times k_2\) domain generated offline by GPT-4, lacking an open-ended mechanism to synthesize completely novel semantic concepts dynamically during runtime.
  • Inference Cost Overheads: Generating 8 batch queries per iteration alongside online neural network training roughly doubles total execution time relative to standard OPRO (1645.6s vs. 731.4s on LR).
  • Theoretical Assumptions in Open-Ended Deployments: Regret bounds derived from adversarial bandit theory assume bounded reward signals and fixed action sets, which may be violated in open-ended, multi-agent long-horizon ecosystems.
  • vs OPRO (Yang et al., 2024): OPRO employs static meta-prompts to drive LLMs as black-box optimizers, frequently stagnating due to semantic ambiguity; EXPO dynamically co-optimizes the meta-prompts themselves, unlocking substantially faster convergence and lower errors.
  • vs INSTINCT (Lin et al., 2024b): INSTINCT uses stochastic multi-armed bandits with neural surrogate estimation for prompt tuning on static datasets; EXPO introduces adversarial bandit principles to successfully master non-stationary sequential environments.
  • vs PromptBreeder (Fernando et al., 2023): PromptBreeder relies on self-referential evolutionary mutations that require immense sample budgets and struggle under non-stationary rewards; EXPO leverages pre-trained embeddings and exponential weighting for rapid online adaptation.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ Formulates prompt adaptation for LLM agents as an adversarial bandit problem, bridging non-stationary bandit theory with prompt optimization.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Extensive validation across continuous optimization, discrete graph routing, instruction meta-tuning, and stochastic bandits with thorough ablations.
  • Writing Quality: ⭐⭐⭐⭐⭐ Rigorous mathematical notation, intuitive conceptual illustrations, and transparent reporting of design choices and limitations.
  • Value: ⭐⭐⭐⭐⭐ Provides an effective, modular blueprint for enhancing sequential decision-making agents without internal model fine-tuning.