LLM Prompt Duel Optimizer: Efficient Label-Free Prompt Optimization

AI summary

Overview

Research area: Automatic prompt optimization (APO) for large language models, specifically label-free optimization using LLM-as-judge pairwise preference feedback, framed as a dueling-bandit problem.

Technical level: Intermediate. The paper assumes familiarity with LLMs, prompt engineering, and basic bandit/exploration concepts, but its core idea is explained in accessible terms.

Scope: The paper proposes and empirically evaluates the Prompt Duel Optimizer (PDO), a method that selects strong prompts from LLM-judge pairwise comparisons under a fixed judge-call budget, tested on 16 BIG-bench Hard tasks and four MS MARCO question-answering tasks.

What This Paper Is About

Most automatic prompt optimization methods need ground-truth labels or gold references to score candidate prompts on a validation set, which is slow and expensive to obtain in real deployments. The authors ask whether prompts can be optimized without any label references, using instead an LLM judge that compares two prompts' outputs on the same input and says which it prefers. The goal is to identify high-quality prompts under a limited comparison budget, since exhaustive pairwise evaluation scales as O(n|P|²) and each comparison costs an API call.

Key Contributions

1. The authors formalize label-free prompt optimization with LLM-judged pairwise comparisons as a dueling-bandit problem, with prompt selection targeting the Condorcet winner (or the Copeland winner when none exists).
2. They propose PDO, which combines Double Thompson Sampling (D-TS) for sample-efficient prompt selection with a top-performer guided mutation-and-prune strategy that expands the candidate pool while discarding weak prompts.
3. They show empirically on BIG-bench Hard and MS MARCO that PDO outperforms label-free baselines under fixed judge budgets, and they analyze quality–cost trade-offs through judge-budget and wall-clock runtime comparisons.
4. They analyze judge noise and potential circularity, and show that PDO's gains persist under alternative judge families and under a small-scale human agreement check.

Main Findings

• Multiple-choice performance: Using only preference signals from the LLM judge and selecting the winner by Copeland score, PDO achieves the highest evaluation accuracy on 13/16 BIG-bench Hard tasks. Notable gains include Tracking-7 (0.641 vs. 0.543, +9.8pp) and Web of Lies (0.942 vs. 0.861, +8.1pp).
• Open-ended QA performance: On four MS MARCO tasks (Description, Entity, Numeric, Location), PDO with D-TS achieves the highest scores and converges faster than RUCB and uniform Random sampling, surpassing the SPO baseline within a few rounds (50 duels per round, averaged over 30 independent runs, starting from a pool of |P| = 50 instructions).
• Judge reliability varies by task: With Llama-3.3-70B as the preference judge, selection accuracy on instances where the two candidate answers differ is 0.59 on Geometric, 0.89 on Tracking-7, and 0.85 on Web of Lies. Substituting Claude-4.5-Sonnet raises these to 0.87, 0.98, and 0.99 respectively.
• Noisy judging tracks performance gaps: Geometric shows a discrepancy of 11.4 percentage points between label-free Copeland selection and development-set-accuracy selection, and its Copeland leader stays around ranks 6–8 across rounds, whereas Tracking-7 steadily improves to rank 2 and Web of Lies approaches rank ≈ 2.5; an oracle judge converges to the best prompt by round 4.
• Gains are not judge circularity: Cross-family re-scoring of 10 PDO prompts and 10 SPO prompts on MS MARCO Description gives PDO higher scores under every judge: Llama 3.3 (4.68 ± 0.06 vs. 4.50 ± 0.07, Δ0.18), Mistral-Large (4.61 ± 0.07 vs. 4.49 ± 0.07, Δ0.12), GPT-4o (4.60 ± 0.06 vs. 4.41 ± 0.06, Δ0.19), Claude 3.5 Sonnet (4.45 ± 0.08 vs. 4.25 ± 0.08, Δ0.20), and Claude 4.5 Sonnet (4.58 ± 0.06 vs. 4.49 ± 0.06, Δ0.09).
• Mutation helps: On Web of Lies and Tracking-7, mutation yields consistently higher accuracy after round 10 than a fixed pool; across all 16 BBH tasks, 8 of 16 show statistically significant gains under mutation, and mutation never underperformed the non-mutation baseline.
• Pairwise beats pointwise: Preference judgement outperforms pointwise 1–5 scoring on the same fixed pool of 50 MS MARCO candidates in 7 of 8 model–task combinations across two judge models.
• Runtime cost: On MS MARCO, PDO early-stopped at 10 rounds takes 4.39, 3.39, 3.83, and 3.10 minutes across Description, Entity, Numeric, and Location, versus SPO at its default 20 rounds with 6.78, 6.74, 6.17, and 7.45 minutes. SPO is faster per run because it compares only two prompts per round and immediately eliminates the loser, but the authors attribute its weaker performance to the absence of an explicit exploration–exploitation strategy.
• Posterior sampling wins among exploration strategies: In the round-5/10/15 comparison on MS MARCO, D-TS is best in most (round, task) cells, Self-Sparring is competitive and is top on Entity at every reported round, RMED falls between the Thompson-sampling methods and the UCB-style baselines, and Random performs worst overall.
• Human agreement: On 20 MS MARCO examples (5 from each of the four tasks) where PDO and SPO outputs received different Llama 3.3 scores, 10 blinded non-author raters produced a mean alignment ratio of 0.87 with the Llama judge.

Methodology in Plain English

The researchers treat each candidate prompt as an "arm" in a dueling bandit, where the feedback is not a score but the outcome of a head-to-head comparison. Each round, PDO uses Double Thompson Sampling to pick two prompts to compare: it draws posterior samples of each prompt's probability of beating the others (modeled as Beta distributions over win counts), uses an optimistic Copeland score to narrow down which prompt is likely best, then restricts the second pick to opponents whose lower confidence bound is still at or below 0.5 — that is, opponents that have not been clearly beaten yet. This concentrates expensive judge calls on pairs where the answer is most informative.

Separately, every so often (at rounds 10 and 20 in the main experiments) PDO takes the current Copeland leader, generates a new variant of it through template edits, text-gradient guided changes, or LLM-assisted rewrites, prunes the lowest-scoring prompts, and adds the new candidate to the pool. This compensates for the fact that D-TS can only find the best prompt within a fixed pool.

Comparisons are made by an LLM judge. For multiple-choice tasks, the judge uses a dual-criterion approach: if two prompts give different answers, it favors the correct one; if they agree, it judges the quality of the reasoning. For open-ended tasks the judge scores accuracy, completeness, relevance, and clarity. Output order is randomized to reduce position bias.

Experiments use 16 BIG-bench Hard multiple-choice tasks with accuracy as the metric, and four MS MARCO open-ended QA tasks scored 1–5 by an LLM judge against the dataset's ground-truth answers. Data is split 50/50 into development and test sets, and results are averaged over 10 runs. Llama-3.3-70B-Instruct is used for prompt generation, preference judging, and final evaluation. The main hyperparameters are 20 initial prompts for BBH and 50 for MS MARCO, 30 rounds with 25 duels per round, and mutation at rounds 10 and 20 that keeps the top-3 Copeland prompts and generates 10 new ones while pruning the 10 lowest. (The D-TS parameter α is described as fixed, but its value is not shown in the available text.)

Why This Matters

This work matters because it removes the most expensive bottleneck in automatic prompt optimization: labeled validation data. It shows that LLM pairwise preferences alone can serve as a usable supervision signal for prompt search, and it brings principled exploration–exploitation trade-offs from the dueling-bandit literature into a practically motivated prompt-engineering pipeline.

Real-world applications include:

• Industrial text classification before labels exist: Practitioners who need a reasonably good prompt to start deployment before large human-labeled datasets are available.
• Search and retrieval QA: Optimizing instructions for open-ended answer generation, as demonstrated on MS MARCO description, entity, numeric, and location tasks.
• Reasoning-heavy multi-choice assistants: Improving instruction quality on BIG-bench Hard-style reasoning tasks such as tracking shuffled objects, logical deduction, and web-of-lies reasoning.
• Cost-tiered deployments: Using an expensive frontier model such as Claude-4.5 as the judge during optimization while deploying the resulting prompt on a lower-cost model such as Llama-3.3 that serves production traffic.

Industry relevance is direct: the method is designed around API budgets, and the authors report both a quality–cost trade-off (fewer expensive judge calls for better prompts) and wall-clock runtime comparisons against a greedy hill-climbing baseline. Code is released at https://github.com/meta-llama/prompt-ops.

Future Directions

• Extending label-free prompt optimization beyond single-turn settings to multi-turn interactions and prompt sets for agentic systems, which the authors name as a flexible extension of PDO.
• Improving alignment between LLM judges and true task objectives, since the algorithm optimizes for the judge's notion of quality and may favor stylistic patterns that align with the judge's preferences.
• Reducing judge noise on hard, domain-specific tasks: on BBH Geometric, Llama-3.3-70B selection accuracy was only marginally above chance (0.59), and stronger foundation models are more reliable but substantially more costly.
• Broader empirical coverage: the authors state they were unable to conduct wider experiments across a wider range of tasks, and they call for future work on better aligning judges with task objectives.

Target Audience

This paper is most useful to machine learning engineers and applied researchers who build LLM systems and need prompt optimization without labeled data, to researchers working on LLM-as-judge evaluation and preference-based learning, and to practitioners in industry settings where annotation budgets are limited. Readers with a background in bandit algorithms or prompt engineering will get the most out of the methodology sections, though the problem framing and empirical results are accessible to a broader technical audience.

Authors’ abstract

Large language models (LLMs) are highly sensitive to prompts, but most automatic prompt optimization (APO) methods assume access to ground-truth references (e.g., labeled validation data) that are costly to obtain. We propose the Prompt Duel Optimizer (PDO), a sample-efficient framework for label-free prompt optimization based on pairwise preference feedback from an LLM judge. PDO casts prompt selection as a dueling-bandit problem and combines (i) Double Thompson Sampling to prioritize informative comparisons under a fixed judge budget, with (ii) top-performer guided mutation to expand the candidate pool while pruning weak prompts. Experiments on BIG-bench Hard (BBH) and MS MARCO show that PDO consistently identifies stronger prompts than label-free baselines, while offering favorable quality--cost trade-offs under constrained comparison budgets.