Prompt optimization with textual gradients (ProTeGi): a complete guide

You know that loop where you tweak a prompt, run it, squint at the failures, and tweak again? ProTeGi hands that loop to an LLM. It reads your prompt's mistakes, writes a plain-English critique of what went wrong (the "gradient"), then rewrites the prompt to fix it, over and over, like gradient descent except every step happens in words instead of numbers.

The technique comes from Pryzant et al. (2023), "Automatic Prompt Optimization with 'Gradient Descent' and Beam Search," presented at EMNLP 2023 in Singapore. The headline: up to 31% accuracy improvement over the starting prompt across their classification benchmarks. The authors later renamed it Automatic Prompt Optimization (APO), so you'll see both names for the same method.

See it work

Say you're classifying support tickets as bug or feature_request. You start with the obvious prompt and it stumbles on tickets that describe a bug but politely ask for it to be fixed.

Initial prompt:
"Classify this ticket as 'bug' or 'feature_request'. Output only the label."

Error case:
Input:      "Would love it if the export button stopped crashing on big files."
Predicted:  feature_request
Correct:    bug

--- ProTeGi reads the failure and writes a textual gradient ---

Gradient: "The prompt doesn't tell the model that polite, request-shaped
language can still describe broken behavior. It treats 'would love it if'
as a feature signal and ignores 'crashing'."

--- ProTeGi edits the prompt in the opposite direction of that gradient ---

Optimized prompt:
"Classify this ticket as 'bug' or 'feature_request'. A ticket is a 'bug'
if it describes existing behavior that is broken or crashing, even when
phrased as a polite request. It is a 'feature_request' only if it asks
for new behavior that does not exist yet. Output only the label."

Same model, same task, but the prompt now carries the decision rule the model kept missing. That edit was written by an LLM, not you, from one failed example.

The mental model

Think of prompt tuning as walking downhill on a foggy hillside, where lower ground means fewer errors. Numerical gradient descent reads the slope under your feet and steps the other way. ProTeGi can't feel a numeric slope, so it asks a guide who can see a little: "which way is wrong?" The critique is the direction; the rewrite is the step.

ProTeGi replaces the math θ_new = θ_old - α·∇L with words: prompt_new = Edit(prompt_old, opposite_of(critique)). The LLM is both the thing being optimized and the optimizer.

That's the whole trick. The model that runs your task is also the model that diagnoses why the task failed and patches the instructions.

How it works

ProTeGi runs an iterative loop. Each round evaluates the current prompt on a batch, turns its mistakes into critiques, edits the prompt, then keeps only the best candidates for the next round.

1. Initialize. Start from a human prompt or a simple task description, a labeled training set, a beam width, and a stopping rule.
2. Evaluate a batch. Sample a minibatch, run the current prompt, compare predictions to ground truth, and keep the error cases.
3. Generate textual gradients. For each error, ask the LLM what about the prompt caused this specific failure, in one or two sentences.
4. Aggregate. Collect the gradients from several errors and optionally summarize them into one coherent critique.
5. Edit the prompt. Feed the critique back and ask the LLM to rewrite the prompt to fix it while preserving intent. This is the descent step.
6. Expand candidates. For each beam prompt, generate several edits from different errors, plus a couple of paraphrases as Monte Carlo samples for diversity.
7. Select. Use a bandit algorithm, specifically Upper Confidence Bound (UCB), to spend evaluation budget on the most promising candidates and keep the top-k.
8. Iterate. Repeat until you hit the iteration cap, plateau, or budget. Iterations usually run 3 to 10, with diminishing returns past about 5.

The canonical loop is short once the LLM does the heavy lifting:

def protegi_optimize(initial_prompt, train_data, iterations=5, beam_width=4):
    beam = [initial_prompt]
    for _ in range(iterations):
        candidates = []
        for prompt in beam:
            errors = evaluate(prompt, sample_batch(train_data))   # step 2
            gradients = [generate_gradient(prompt, e) for e in errors[:3]]  # step 3
            for g in gradients:
                candidates.append(edit_prompt(prompt, g))         # step 5
        beam = select_top_k(candidates, k=beam_width, data=train_data)  # UCB select
        if no_improvement(beam, threshold=0.01):
            break
    return best_prompt(beam, train_data)

The two LLM calls that make it tick are the gradient and the edit. Both are just prompts:

GRADIENT PROMPT
"The following prompt was used: {current_prompt}
 On input '{input}' the model predicted '{prediction}' but the correct
 answer was '{ground_truth}'. In 1-2 sentences, what flaw in the prompt
 caused this error?"

EDIT PROMPT
"Current prompt: {current_prompt}
 This prompt has the following problem: {aggregated_gradient}
 Rewrite the prompt to fix this while preserving its core intent.
 Output only the new prompt."

Why it works

The gains aren't magic; they trace to a few factors the original work and follow-ups consistently point at. Ranked by how much they move the needle:

The deeper reason it beats random search: a critique gives direction. Instead of sampling arbitrary prompts, ProTeGi only edits toward the failure it just diagnosed, shrinking the search space to semantically nearby improvements. Edits also tend to be small, which acts like implicit regularization, so working parts of the prompt survive.

Where it shines

ProTeGi was built for tasks with a clear right answer and a metric to chase. The original paper evaluated four classification tasks with GPT-3.5 and GPT-4:

Against other prompt-optimization methods, it lands near the top on improvement while staying moderate on cost:

Beyond the benchmarks, it carries over to content moderation (up to 20% accuracy improvement on jailbreak detection, enough to push borderline prompts into production), information extraction and named entity recognition, code classification and error detection, plus query reformulation prompts inside RAG pipelines. In research settings it's been applied to clinical entity extraction, legal clause classification, and financial risk detection. Results tend to transfer across similar tasks within the same domain.

When to use it (and when not)

Reach for it when: the task has definable right answers, you have a labeled set but the prompt isn't good enough, manual iteration has hit diminishing returns, you need reproducible optimization, or you have many similar prompts to tune.

Skip it when: you're doing open-ended or creative generation with no clear metric, you need real-time adaptation (this takes minutes, not milliseconds), the prompt already works well, evaluation is purely subjective, or you lack reliable labeled data.

The sweet spot by the numbers: 30 to 300 labeled examples (below 20 or above 1000 is a poor fit) and current accuracy in the moderate 50 to 80% band (below 30% or above 95% is a poor fit).

Model fit. Quality scales with the model doing the gradients and edits:

When to escalate to something else:

Picking a variant:

Components and configuration

Six pieces do the work. The first five are required, the selector and beam manager are strongly recommended:

1. Initial prompt — a human prompt, a task description, or output from another generator. Affects convergence speed, not the final ceiling.
2. Training dataset — labeled input/output pairs. Minimum ~30, recommended 100 to 300, ideally covering edge cases.
3. Gradient generator — the LLM that reads (prompt, input, prediction, ground truth) and emits a critique.
4. Prompt editor — the LLM that applies a critique to produce a new prompt while keeping it coherent.
5. Evaluation function — a scalar score: accuracy, F1, precision, recall for classification; BLEU, ROUGE, exact match, or semantic similarity for generation.
6. Candidate selector + beam manager — UCB bandit selection over a beam of typically 3 to 8 candidates, so you don't pay to fully evaluate every weak edit.

The knobs you'll actually turn:

Tune for the scenario: high-stakes classification wants a wider beam (8 to 12) and a held-out validation set for final selection; low-data runs (below 50 examples) want beam width 2 to 3, cross-validation, and only 3 to 4 iterations to avoid overfitting; open-ended generation wants a semantic-similarity metric and more paraphrase variants.

Implementation and debugging

A practical workflow: collect 100 to 300 labeled examples with balanced classes, split 80/20 train/validation, write a clear initial prompt, record a baseline accuracy, run with defaults while watching the validation score for overfitting, then evaluate the winner on a held-out test set and A/B test it against the original before full rollout. Plan for periodic re-optimization as your data drifts.

The core mechanism is the gradient call. Here it is concretely, the function the loop leans on:

def generate_gradient(prompt, error, client):
    """Turn one error case into a textual gradient."""
    g = f"""You are analyzing why a prompt produced an incorrect output.
PROMPT: "{prompt}"
INPUT: "{error['input']}"
MODEL OUTPUT: "{error['prediction']}"
CORRECT ANSWER: "{error['ground_truth']}"
What flaw in the prompt caused this error? Give a concise critique
(2-3 sentences) naming the specific problem."""
    resp = client.chat.completions.create(
        model="gpt-4",
        messages=[{"role": "user", "content": g}],
        temperature=0.7,
    )
    return resp.choices[0].message.content.strip()

The edit call is the mirror image: same shape, but it takes the prompt plus the aggregated critique and returns a rewritten prompt with temperature around 0.7. Frameworks wrap this for you. DSPy expresses the gradient and editor as Signature classes and runs the whole thing through MIPROv2; LangChain and Haystack wrap the same two calls around their prompt-template and pipeline objects.

Do: start from a reasonable prompt (garbage in, garbage out), use diverse examples, keep a validation set to catch overfitting, log every intermediate prompt and score, eyeball the gradients for quality, and review the final prompt by hand before shipping.

Don't: use fewer than 30 examples, skip validation, run iterations forever without a convergence check, trust low-quality gradients, or expect optimization to rescue a fundamentally broken task definition.

When it misbehaves, the symptom usually points at the cause:

A clean comparison is how you prove it worked, run both prompts on held-out data and check the gap is real:

def compare(original, optimized, test_data, client, trials=5):
    import numpy as np
    from scipy.stats import ttest_ind
    a = [evaluate_prompt(original, test_data, client)[0] for _ in range(trials)]
    b = [evaluate_prompt(optimized, test_data, client)[0] for _ in range(trials)]
    t, p = ttest_ind(a, b)
    return {"original": np.mean(a), "optimized": np.mean(b),
            "significant": p < 0.05}

Stop optimizing when validation accuracy stalls for two consecutive iterations, you clear your target threshold, you exhaust the budget, or gradient quality visibly drops. Cover your test set with happy-path, edge, adversarial, and distribution-shift cases, not just easy examples.

Limitations

Some constraints are baked in and no amount of tuning removes them:

• Needs labeled data. No ground truth means no errors to learn from. Tasks without clear right answers can't be optimized this way.
• Only optimizes what you measure. Creativity, style, and nuance slip through standard metrics.
• First-order. It reacts to immediate per-iteration feedback, so it struggles with optimizations that need long-range, multi-step structure.
• Local optima. Like numerical gradient descent, it can settle into a prompt that's locally good but globally mediocre.
• Gradient-quality ceiling. If the model can't correctly diagnose a failure, it can't fix it. Effectiveness is bounded by the LLM's analytical skill.

Watch for the predictable failure modes: noisy labels make it optimize for noise (clean first), imbalanced data biases toward the majority class (balance or weight), small datasets overfit fast (fewer iterations, cross-validate), and genuinely ambiguous inputs make gradients conflict and oscillate (remove them or accept multi-label). Always keep a best-so-far fallback so a bad edit can't sink the run.

How it compares

ProTeGi sits in a family of automatic prompt optimizers. The useful distinctions:

APE is its one-shot predecessor (generate then select); GRIPS uses heuristic edit operations rather than gradient-guided ones; OPRO is trajectory-based rather than error-focused; TextGrad is a direct extension that optimizes any text variable, not just prompts. It also combines well: ProTeGi + RAG, + CoT, + RLHF, and + Constitutional AI are all promising hybrids, and the gradient idea transfers to few-shot example selection, system-prompt tuning, and LLM-as-judge evaluation prompts.

ProTeGi's "textual gradient" idea also kicked off a research line. TextGrad (2024), published in Nature, generalized gradients to any text variable and reported 78% to 92% accuracy improvement on GPT-3.5-turbo benchmarks, with applications from code debugging to molecular structure and radiotherapy planning. MAPO (2024) added momentum to escape oscillation and hit higher F1 with fewer API calls. PO2G (2024) uses both a positive and negative gradient and reaches 89% accuracy in 3 iterations versus ProTeGi's 6 for comparable performance.

Tools to start from: the authors' reference implementation lives in Microsoft's LMOps repo (github.com/microsoft/LMOps/tree/main/prompt_optimization), TextGrad is at textgrad.com, DSPy at dspy.ai, and the original paper is aclanthology.org/2023.emnlp-main.494. For deeper reading, the MAPO paper is arxiv.org/abs/2410.19499 and there's a broader APO survey at arxiv.org/abs/2502.16923.

Summary

• What: ProTeGi (also called APO) automates prompt tuning by simulating gradient descent in natural language, an LLM critiques its own failures and rewrites the prompt to fix them.
• Why: it replaces slow, subjective manual iteration with a systematic, reproducible loop, delivering up to 31% accuracy improvement over the starting prompt.
• How: evaluate on a batch, turn errors into textual gradients, edit the prompt in the opposite direction, expand candidates, and use UCB bandit selection over a beam, for 3 to 10 iterations.
• When: tasks with clear metrics and 30 to 300 labeled examples sitting at moderate (50 to 80%) accuracy, especially after manual tuning has plateaued.
• When not: open-ended generation, real-time needs, already-strong prompts, or subjective tasks without reliable labels.
• Where: classification, extraction, content moderation, code, and RAG query reformulation, with results that transfer across similar tasks in a domain.
• Which: prefer full beam search for quality, single-gradient for budget, MAPO for speed; escalate to APE, DSPy MIPRO, or fine-tuning when ProTeGi's assumptions don't hold.
• Cost and limits: roughly $2 to $10 and 5 to 30 minutes per task; bounded by label quality, metric coverage, gradient accuracy, and local optima, so keep a validation set and a human review gate.