Replay-Based Eval Workflow for Agent Prompt Changes

A prompt change that ships without being replayed against real production traces is not an engineering decision. It's a bet, and the team making it usually has no idea what odds it's actually facing. Replay-based evaluation fixes this by giving teams a repeatable process: rewind a recorded failure, apply the candidate prompt, re-run it, and measure whether the outcome actually changes before any of it touches a live user.

The failure mode this guards against is familiar to anyone who has shipped an agent to production. A team edits a system prompt on a Friday afternoon, the change looks cleaner, the manual test passes, and it goes out. By Monday, support escalations are up 14%, and nobody on the team can say which user segment got hit or why. There's no offline regression suite to check against, no quality signal sitting on top of the traces that would have caught it, just a dashboard tracking token counts and latency, both of which looked perfectly fine the whole time.

That's the structural problem, not an oversight. Most observability stacks were built to answer "is it fast and is it cheap," not "is it right." Semantic quality, whether the agent's output actually satisfies the task, is a blind spot by design. Agent systems make this worse than single-call LLM apps ever did: errors compound across a chain of steps, the same input can trigger a different sequence of tool calls on two separate runs, and an output can look completely reasonable while being wrong in a way that only shows up three steps downstream. A single passing manual test proves almost nothing under those conditions, because non-determinism means you're not looking at "the" behavior of the system, you're looking at one draw from a distribution of behaviors. Validating a prompt change means validating it against that distribution, not against a handpicked example that happened to go well in a demo.

When the tooling is stripped away, the implicit claim behind every unreplayed prompt edit is: "this is an improvement." Without evidence pulled from actual production traces, that's not a claim, it's a guess dressed up in engineering language.

Where agent prompt failures originate, and why observing the final output doesn't tell you

Agent failures live inside long execution trajectories, and the step that finally produces the bad outcome is rarely the step where things went wrong. A tool call that deletes the wrong record, for instance, is usually the downstream consequence of a decision made several steps earlier: a misread instruction, an ambiguous handoff, a piece of context that got dropped. Looking only at the final output and asking "what happened here" skips over the actual causal chain.

Attribution turns out to be genuinely hard to automate, too. On the Who&When benchmark, which measures how accurately an LLM judge can pinpoint the specific step that caused a multi-agent failure, state-of-the-art step-level accuracy is around 14%, per arXiv:2606.08275. That's not a rounding error; it's a system that's wrong the overwhelming majority of the time when asked to point at the culprit step. The MAST failure taxonomy, validated across more than 1,600 execution traces, sorts these failures into fourteen distinct modes rolling up into three root categories: system design issues, inter-agent misalignment, and task verification gaps. A report from augmentcode.com found that multi-agent systems fail in production somewhere between 41% and 86.7% of the time depending on task complexity, and specification ambiguity paired with unstructured coordination accounts for 79% of those breakdowns.

Attribution errors compound the problem in a subtler way. A two-year postmortem conducted by a major retailer found a persistent attribution error rate of roughly 10%, where the diagnostic model blamed a technology simply because it appeared somewhere in the incident thread, not because it caused anything. The tool was a bystander, and the model treated it as a suspect.

The implication for prompt work is direct: if a team can't reliably say where in the trajectory a failure originated, it can't know whether editing the prompt fixes the actual cause, or just happens to change the surface behavior on one lucky trace. This is precisely the gap replay closes. Replay confirms which layer, prompt, tool, workflow, or memory, actually caused the failure, not merely that a run failed, something everyone already knew. It's isolating which layer, prompt, tool, workflow, or memory, actually caused the failure, so the fix lands where it needs to.

What "replay" means in the context of agent traces

Replay has a specific, narrow meaning here. It means rewinding a recorded production trace to a chosen point, substituting a candidate change (say, a new system prompt), and re-executing the trajectory forward from that point under the same inputs and the same stochastic policy the original run used.

It helps to be equally clear about what replay is. It is not re-running the agent live against a fresh batch of synthetic inputs, since those inputs, however well-crafted, don't reflect the actual distribution of failures that happened in production. It is not a live A/B test either, because that approach validates the change by exposing real users to it, which is exactly the risk replay is meant to avoid. And it is not an LLM judge scoring a static output snapshot after the fact. That measures correlation between an output and a rubric. It says nothing about the causal effect of the specific change under test.

Causal Agent Replay, described in arXiv:2606.08275 (June 2026), formalizes this idea by modeling an agent run as a structural causal model, applying what's called a do-operation to a specific step, then re-executing forward and measuring the shift in the resulting outcome distribution. The design detail that matters most: the replay uses the same stochastic policy as the original run. That's what keeps the comparison fair. Without it, a team measuring a "difference" might just be measuring the effect of a different random seed or a different runtime environment, not the effect of the prompt edit itself.

Cost is a real constraint here. Exhaustive replay across every candidate event in a trajectory scales linearly with trace length, which gets expensive fast on long trajectories. Budget-bounded techniques, Monte Carlo Shapley estimation among them, exist to approximate the full replay without paying for it in full.

There's also a meaningful distinction between closed-loop recovery and decoupled self-correction. Closed-loop recovery is grounded in an attributed root cause: it knows which step to fix and applies the correction there. Decoupled self-correction just asks the model to try again without that grounding. On the GAIA benchmark, closed-loop recovery repaired more than twice as many failed tasks in a single rerun compared to decoupled self-correction baselines. Attribution before intervention is the mechanism underneath that result, and it is the same mechanism that makes replay-based evaluation work at all.

Step 1: Collect and triage the production traces your prompt change needs to answer for

The eval set has to come from production. Synthetic inputs, however carefully constructed, don't reproduce the actual failure distribution: prompt ambiguity that appears only under a specific phrasing, tool schema drift introduced after an API update, workflow loops that trigger only on certain input lengths. Real traces surface all of it because it already happened.

Trace capture needs to cover the full session, not just the final LLM call, since agent failures live in multi-step causal chains rather than in any single call taken in isolation. That means step-level spans for model calls, tool calls, memory reads and writes, and handoffs between agents. OpenTelemetry's GenAI semantic conventions are becoming the standard here, now maintained in their own dedicated repository (open-telemetry/semantic-conventions-genai) as of version 1.41, covering agent, workflow, tool, and model spans. All of the gen_ai.* attributes still carry a Development stability badge, meaning attribute names can shift without a major version bump. Only non-GenAI-specific attributes, like error.type, have reached Stable. Teams building on this convention should expect some churn.

Triage from there. Pull traces where the run failed a quality metric or triggered an escalation. Pull traces where the failure looks, on inspection, like it's plausibly a prompt-layer issue rather than a tool schema error, stale memory, or an infrastructure hiccup. And spread the selection across difficulty tiers: easy regressions that should never happen again, medium cases with genuine ambiguity, and the hard adversarial cases that actually surfaced through a support ticket.

Don't skip the successful traces either. They're the non-regression baseline, and a prompt change that fixes ten failures while quietly breaking five things that used to work is not a net improvement, no matter how good it looks against the failure set alone.

Engineering attention tends to gravitate toward the tail: the bottom slice of prompts where the model fails repeatedly. Those failures carry more diagnostic value than average-case examples. That's the right instinct. Those traces carry more diagnostic value than any number of average-case examples, and they're the ones most worth spending replay budget on.

Once the trace set is assembled, lock it down. Version it exactly like code, same traces, same metric configs, same gold answers, so that if a regression shows up later, the team can trace it back to an exact commit rather than arguing about what the eval set even was at the time.

Step 2: Attribute the failure to the prompt layer before touching the prompt

Before writing a single word of a new prompt, confirm the failure actually belongs to the prompt layer. It's tempting to skip this step. Don't. A failure that looks like a prompt problem on the surface is, often enough, a tool schema mismatch or a memory staleness issue wearing a prompt-shaped disguise.

A rough taxonomy helps here. Prompt-layer failures look like instruction ambiguity, missing context framing, role confusion, or an output format the model wasn't actually told to follow. Tool-layer failures include schema drift, wrong or missing parameters, or a tool getting called at the wrong point in the sequence. Workflow-layer failures are skipped steps, misordered operations, premature termination, or an outright infinite loop. And memory-layer failures are about context going stale: research quantifies roughly 2% context retention loss per step, which compounds fast enough that after five cycles, less than 60% of the original context remains reliably accessible.

There are concrete ways to test which layer is at fault. Replay the trace with the original prompt intact but a corrected tool schema; if the failure disappears, the tool was the cause all along. Check whether the failure originates early in the trajectory and then propagates forward, a sign of specification ambiguity, or whether it appears suddenly at the action step itself, which points more toward a verification gap. Research presented at ICSE 2025 found that incorporating code-level knowledge into root cause localization improved accuracy by 28.3% over the prior leading methods, a reminder that structural trace inspection consistently beats a surface read of the final output.

Only move to editing the prompt once the attribution actually points there. Fixing the visible symptom without confirming the cause is exactly what decoupled self-correction gets wrong, and it's the trap this whole workflow exists to avoid.

Step 3: Write and scope the prompt variant with the failure traces in view

Write the variant to match what the traces actually show, not what feels intuitively like it should work. A prompt edit made on a hunch, without trace evidence backing it, is the same guesswork the entire replay workflow was built to eliminate. It just happens later in the process.

Scope matters as much as content. Change one thing at a time. Editing wording, role framing, and output format all in the same pass makes it impossible to know afterward which change actually moved the metric, and teams end up re-litigating the same edit weeks later because nobody can isolate what worked. Use explicit delimiters and a consistent structure across variants, so the thing under test stays isolated rather than getting confounded by an unrelated formatting change.

The traces themselves tend to surface a handful of recurring failure patterns. Specification ambiguity, role confusion, an underspecified output format, and missing context framing are prompt-layer problems that call for clearer role statements and more explicit output structure. Instruction drift across long trajectories, where the model loses the thread of its own intent over many steps, calls for step-anchoring instructions or procedural checkpoints rather than trusting the model to hold onto intent unassisted. Operational procedure failures, skipped steps, steps done out of order, premature termination, get fixed by externalizing the procedure as an explicit checklist rather than leaving it implicit in a paragraph of prose.

There's a related, prompt-adjacent lever: packaging recurring procedures into reusable artifacts, sometimes called skills, shifts the agent from improvising each step fresh to assembling a task from pre-validated components. That's the right move specifically when the trace shows repeated process-level instability, not a single wording problem in one prompt.

Automated prompt optimization tools, DSPy, ProTeGi, Bayesian search methods, can search a space of wordings against a target metric, and they're genuinely useful for tuning phrasing within a structure that's already been decided. What they optimize is phrasing within a structure that's already been decided, not the underlying architecture of tools, orchestration, or memory. They complement attribution-first editing. They don't replace it.

Step 4: Score the variant against the trace set before replay

Run a panel of metrics, not one number. A single aggregate score can climb while a specific, important failure mode quietly gets worse, and a team that only checks the top-line score won't notice until it's already in production.

Start with deterministic checks: output format validity, schema compliance, length constraints. These are cheap, fast, and they gate everything downstream, since there's no point spending judge-model tokens scoring an output that's structurally broken before it even gets to the semantic question. LLM-as-judge scoring comes next, for faithfulness, task adherence, and instruction following, and the judge should be a different or stronger model than the one under test. Self-preference bias, where a model rates its own outputs more favorably, is a documented risk, and running the judge and the test model as the same model invites exactly that distortion. Calibrate the judge against a small human-labeled sample drawn from the same trace population before trusting its scores at scale; a judge is a model too, with its own blind spots.

Score at three levels. End-to-end: did the task actually succeed on the failure traces? Trajectory-level: was the path efficient, or did the variant introduce extra tool calls and unnecessary loops even while technically succeeding? Component-level: did the prompt-layer score improve specifically, without dragging down tool-call correctness or reasoning quality elsewhere in the chain?

Run this scoring against the non-regression baseline traces too. A variant that fixes the failures while degrading the passing traces doesn't clear the bar, regardless of how good its improvement number looks in isolation.

Every score needs to trace back to something inspectable: token counts, the tool call sequence, the step-level reasoning that produced the answer. A numeric summary with nothing behind it is a black box, and black boxes don't survive a serious review.

Step 5: Replay the candidate prompt against the original failure traces and measure the outcome shift

This is where the actual test happens. For each failure trace in the set, rewind to the exact point where the prompt layer was invoked, substitute in the candidate prompt, and re-execute forward under the same stochastic policy and the same tool environment the original run used. Record the outcome across multiple replays of the same trace, not a single pass or fail, since the agent's non-determinism means one run tells you almost nothing about the true rate.

What matters is the shift: did the proportion of successful outcomes go up across the replayed set? Did the specific failure modes identified back in Step 2 actually shrink, or did the variant just change the shape of the failure without reducing its frequency?

The attribution work from Step 2 pays off directly here. Because the failure was already traced to the prompt layer, the replay applies the intervention at the point that actually matters, rather than patching the visible symptom several steps downstream. That's the exact distinction between closed-loop recovery and decoupled self-correction again, and it's why the fix lands on the cause instead of the surface.

Budget the replay carefully. Exhaustive replay of every candidate event scales linearly with trace length, and long trajectories make that expensive fast. Use the Step 2 attribution to bound the intervention space: replay from the attributed step forward.

The judge accuracy limitation resurfaces here too. Given that state-of-the-art LLM-judge step attribution accuracy is around 14% on benchmarks like Who&When, leaning on a judge to confirm whether the attributed step "looks like" the cause is a weak substitute for the structural question replay actually answers: did the trajectory succeed or not, under a fair, controlled comparison?

Document the results in the same versioned record as the trace set and the prompt variant. That record is the evidence a team reviews before shipping, and it's also the audit trail if the change causes trouble in production later.

Step 6: Gate the change with a non-regression check and a reviewable diff before merge

The gate needs explicit criteria. Replay success rate on the failure traces has to exceed the baseline rate the original prompt scored on those same traces. Replay success rate on the non-regression traces can't drop below a threshold the team has actually agreed on and written down in advance. What counts as acceptable degradation is a judgment call, but it has to be a made judgment, not an implicit one discovered after the fact. And the deterministic checks, schema compliance, output format, any policy constraints, still have to pass regardless of how good the semantic scores look.

The diff that goes to review should include more than the new prompt text. It should carry the trace set the variant was validated against, the full metric panel results, and the replay outcome distribution, all visible together. A prompt change with no evidence attached asks a reviewer to trust intuition. A prompt change with a reviewable diff asks a reviewer to check work, which is a fundamentally different, and more defensible, request.

Developers deserve changes they can actually audit. A prompt approved on replay evidence a reviewer can walk through is categorically different from an auto-fix that arrives as a black box, and that difference is exactly what builds durable confidence in the workflow over time, rather than a one-off sense of relief that this particular ship went fine.

Wire the gate into CI. Treat a failing replay result the same way a failing unit test gets treated: the change doesn't merge until it passes. That's what turns this from a good idea a team does when there's time into a process that actually runs every time, whether or not anyone remembers to ask for it.

When the gate fails, that's not a dead end, it's information. A failed gate usually means the attribution in Step 2 missed something, or the variant addressed the wrong failure mode entirely, and either way, the team now knows something concrete about the system that it didn't know before the attempt.