Skip to content

PROTEA: Offline Evaluation and Iterative Refinement for Multi-Agent LLM Workflows

🕒 Published (v1): 2026-05-18 08:22 UTC · Source: Arxiv · Venue: ACL 2026 · link

Why this paper was selected

ACL; offline evaluation and iterative refinement pipeline for multi-agent LLM workflows

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

PROTEA is an offline, test-driven debugging and refinement interface for multi-agent LLM workflow DAGs. It localizes bottleneck nodes via LLM-as-a-judge rubric scoring, generates intermediate node-level expectations backward from final-answer references, and proposes editable prompt revisions that are automatically re-evaluated within the same interface. In two production-adjacent case studies, it raised document-inspection accuracy from 64.3% to 83.9% and recommendation Hit@5 from 0.30 to 0.38.

Problem

Multi-agent LLM workflows (DAGs of role-specific LLM calls) are hard to debug because failures propagate silently from upstream nodes and existing evaluation frameworks—OpenAI Evals, lm-evaluation-harness, DeepEval, LangSmith, RAGAs—measure end-to-end or component-level outcomes but do not automatically localize which node caused failure or propose which prompt to change. Developers must manually read long traces, infer fault attribution, edit prompts in separate tools, and manually compare before/after runs.

Method

PROTEA represents workflows as DAGs \(G = (V, E)\) where each node \(v\) has instruction \(I_v\), optional output format \(S_v\), and observed output \(y_v\).

Backward Node Evaluation. When only a final-answer reference \(y^{\star}_\text{final}\) is available, a reference-generation LLM \(M_\text{gen}\) synthesizes a candidate expectation \(\hat{y}_v\) for each intermediate node by conditioning on \(I_v\), \(S_v\), downstream children's requirements, and \(y^{\star}_\text{final}\), traversed in reverse topological order.

Rubric-based scoring. An evaluator \(M_\text{eval}\) scores each node output against its reference on per-criterion dimensions \(d\), producing scores \(\sigma_d(v) \in [0,1]\) and an overall weighted score \(s(v) \in [0,1]\), mapped to PASS/WARN/FAIL with default thresholds 0.8 / 0.55.

Prompt refinement. For a developer-selected node, a prompt-revision LLM \(M_\text{opt}\) proposes a rewritten instruction \(I_v'\) conditioned on \(I_v\), the evaluator rationale, and an improvement suggestion. The interface presents this as an editable before/after diff. PROTEA then reruns the full workflow and re-evaluates automatically. An AUTO LOOP mode repeats the evaluate→revise→re-evaluate cycle for a fixed number of iterations, retaining revisions only when repeated offline checks show improvement.

Key Contributions

  • Backward node evaluation: derives intermediate node-level expectations from final-answer references only, eliminating the need to manually label every node's expected output.
  • Graph-overlaid diagnosis: PASS/WARN/FAIL states with rationales are displayed directly on the workflow graph, sorted FAIL→WARN→PASS by score within each tier.
  • Editable before/after prompt revision: proposals are grounded in evaluator rationale and presented as diffs; developers can accept, modify, or discard without tool switching.
  • Automatic re-evaluation loop: after prompt acceptance, PROTEA reruns the full offline suite and shows score trajectories and per-iteration history for rollback.
  • AUTO LOOP mode: fully automated iterate→revise→re-evaluate for a fixed number of steps with stability checks before retaining revisions.

Results

Production-adjacent case studies (developer-in-the-loop): - Case A (enterprise document inspection, \(N=5\) nodes): accuracy 64.3% → 83.9% - Case B (conversational recommendation, \(N=6\) nodes): Hit@5 0.30 → 0.38

Automatic iteration stress test (AUTO LOOP, 3 iterations, 5 minimal-prompt workflows): - 4/5 workflows exceeded the no-rewrite baseline - 3/5 achieved gains > 0.3 score units - Largest gain: course-scheduling workflow 0.186 → 0.800 (+0.614) - No improvement: word-problem workflow (0.000 → 0.000), attributed to near-binary exact-match scoring providing no graded gradient signal - No-rewrite baseline used as control: same workflow run 3× without prompt revision to isolate score variation from stochastic sampling

Formative user study: 6 experienced LLM developers; qualitative endorsement of graph-level localization, per-node rationales, and editable before/after comparison; no quantitative usability metrics reported.

Limitations

  • Designed for fixed DAG topologies; cyclic workflows, supervisor-based coordination, and long-running interactive agents are not yet supported.
  • Rubric-based LLM-as-a-judge evaluation is sensitive to evaluator calibration; near-binary scoring criteria (e.g., exact numeric correctness) provide insufficient gradient signal for AUTO LOOP.
  • Backward-inferred expectations are candidates, not ground truth; their quality depends on the reference-generation LLM and may degrade for nodes far from the final output.
  • All evaluations are small-scale (two internal workflows, five stress-test workflows, six user-study participants); no controlled comparison of time-to-fix or regression rates vs. manual iteration.
  • No support yet for architectural edits (adding/removing nodes, rewiring edges) or cost-aware prompt compression.
  • Integration with existing CI pipelines, graph importers, and team versioning workflows is identified as a gap but not yet implemented.

Relevance to Harnesses / Meta-Harnesses

PROTEA is directly a meta-harness: it wraps arbitrary multi-agent LLM workflow DAGs with a unified evaluation-and-refinement control loop, exactly the pattern of a harness that orchestrates other agents and toolchains. Its backward node evaluation and rubric scoring constitute a configurable judge layer that can be applied to any DAG imported from LangGraph or defined manually—analogous to how meta-harnesses wrap arbitrary task pipelines with measurement and iteration logic. The AUTO LOOP mode implements an automated self-improvement loop over the harness itself, foreshadowing meta-harnesses that optimize their own component agents without human intervention. The design tension it identifies—end-to-end labels vs. per-node supervision—is a core challenge in any harness that must evaluate intermediate agent outputs without exhaustively labeling every step.