ReTrace compiles an LLM agent's logged reasoning into a planner-free workflow — 1.3s per task instead of 170s, at a 3-point completion cost
Amazon and Columbia distill logged agent reasoning into deterministic workflows — code, not an LLM, picks the next step. 1.3s vs 170s per task, 24% lower cost, at a 3-point completion gap.
Amazon and Columbia's ReTrace compiles a natural-language SOP plus a handful of logged agent runs into a deterministic workflow: code, not an LLM, picks the next step at runtime. On τ²-Bench it runs 1.3s per task instead of the agent's 170s (~130× faster) at 75.8% task success vs 80.6%; on 79 production procedures it reaches 93.8% completion vs 96.8% at 24% lower cost per task (abstract).
What shipped
ReTrace (arXiv:2611.14492, submitted 10 Nov 2026) is a three-stage pipeline that compiles an SOP and k logged agent traces into a reusable workflow. Its core move: treat the agent's free-text reasoning as a recoverable condition column that tool-call logs lack. A trace step is (reasoning, tool, inputs, result); the reasoning states why the tool was called, and ReTrace mines it.
Extraction. For each step, an LLM extracts a record with the condition under which the action applies, the intended action, the tool, its typed inputs, and the source of each input (task input, earlier result, or constant). The condition may only use information available before the action — "airplane mode is on" can justify turning it off, but the result of turning it off cannot. Case-specific values like a customer ID become variables filled per task. Alternative actions the reasoning mentions but the agent didn't take are kept.
Aggregation. An LLM summarizes each trace against the SOP, then a merge step combines the summaries: unify repeated steps, work out how earlier results feed later inputs, check the reasoning against the recorded calls and outcomes, and resolve disagreements using the SOP. The output is an Intermediate Representation — a completion check plus an ordered list of guard–action rules (a decision list). Each rule cites the trace steps or SOP statements that support it, and alternatives no logged run executed are marked unwitnessed.
Synthesis. An LLM compiles the rule document into executable code. Only this last stage depends on the platform: the same pipeline yields Python for the public benchmarks and typed workflow graphs for Amazon's internal enterprise platform. Pre-deployment checks require the code to load, import only approved libraries, and make no planning calls when re-run on training inputs; among valid candidates, ReTrace keeps the one that reproduces the most logged steps. At runtime the workflow checks completion, runs the first rule whose guard holds, appends the result, and loops — it never asks a model what to do next. Individual tools may still call a model (e.g., to classify a document); only step selection is model-free.
The compaction is the point. With 16 traces the code generator reads a 24.5k-token rule document instead of 101.4k tokens of raw traces; beyond 8 traces the paper switches to incremental merging that keeps the IR near 10k tokens at k=16. That matters because feeding the generator raw traces backfires: on τ²-Bench, build success collapses from 100% at 16 traces to 31% at 32, and on the internal dataset 9 raw traces drop completion below zero-shot.

Why it matters
Of 5,115 automations customers created on Amazon's enterprise platform between April and June 2026, 91.8% were agents that plan at runtime — yet seven of the ten most executed were fixed workflows. For agents using three to five tools, choosing the next step took 37–43% of execution time, on top of token cost. The paper estimates construction is recovered after about 75 executions, and those seven workflows each ran 297k–528k times in three months.
The results across the three evaluations:
- Production (79 procedures): ReTrace 93.8% completion vs agent 96.8%, at 24% lower cost per task ($0.096 vs $0.127). Median time dropped 68s → 37s.
- τ²-Bench (telecom domain): ReTrace 75.8% task success vs agent 80.6%, with zero model calls at runtime and 1.3s vs 170s per task. Zero-shot generation from the SOP alone scored 38.8%, so ReTrace's 37-point lead over zero-shot is the statistically significant result.
- SOP-Bench (8 procedures): unrepaired ReTrace trails few-shot generation (80.6% vs 83.6%), but repair lifts it to 87.8% vs the agent's 85.5%, at 0.40s vs 46.6s per task.
Repair is a separate post-construction step that uses training failures. Each round runs the workflow on training inputs and revises the code from the failures — the rule document stays fixed — with test inputs evaluated only after the last round. Three rounds lift k=2 workflows on τ²-Bench from 66.7% to 81.2% (effectively reaching the agent's 80.6%), and zero-shot workflows from 38.8% to 60.6%.

The paper's cleanest experiment is the reasoning ablation: holding the pipeline and tool calls fixed, stripping the reasoning costs 6.2 points on τ²-Bench and 8.8 points of completion on Internal, while gaining 1.7 points on SOP-Bench. Unwitnessed branches citing reasoning fell from 44 to 3 without it. The reasoning lets ReTrace cover branches no logged run actually executed — the airplane-mode branch that justifies a no-data path.
Caveats
Everything here is vendor-reported. The paper is an Amazon–Columbia preprint submitted 10 Nov 2026 with no peer review, and no code or project page is linked from the arXiv page — none of the numbers can be independently reproduced. Treat them as self-reported.
- Completion is platform-reported, not an independent audit. On the 20 of 79 procedures involving web automation, some agent runs the platform marked complete had no successful web call, so completion flags can overstate success.
- The headline τ²-Bench comparison is not statistically solid. The confidence interval is wide (roughly 20 points either way), so parity with the agent is "not established" — only the zero-shot lead and the Low-complexity Internal gain are significant.
- Repair leaks labels. It uses labeled training failures, so repaired vs unrepaired is not like-for-like.
- Verification doesn't prove correctness. The consistency checks track evidence and omissions; they don't verify a condition is true or a task is correct. Agent explanations can be mistaken or fail to reflect the real reason for an action.
- It only pays if the SOP is stable. Every SOP or tool change means a rebuild, and a workflow that hits no matching guard silently stops incomplete rather than recovering. Commentator Georgi Gospodinov flags procedure drift as an unaddressed operational risk.
- Condition recovery degrades with complexity. On Internal, completion falls monotonically from 96.3% (Low complexity) to 89.2% (High).
- No controlled head-to-head against the closest prior art (ASI), and the "Sonnet 4.6" agent attribution appears only in secondary coverage, not in the paper sections I could read.
The honest takeaway: ReTrace gives up a few points of completion to buy a ~130× latency cut and a 24% cost reduction — a good deal for high-volume, stable procedures, and a bad one for anything where inputs need free-text judgment at every step or the SOP changes often.