💬 NLP

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

PROTEA is a unified interface for offline, test-driven refinement of multi-agent LLM workflows that localizes bottlenecks through graph-based scoring and backward evaluation, enabling developers to iteratively edit and validate prompt revisions to significantly improve system performance.

Original authors: Kazuki Kawamura, Satoshi Waki, Kei Tateno

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Kazuki Kawamura, Satoshi Waki, Kei Tateno

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the director of a play where the cast consists entirely of AI robots. Each robot has a specific job: one reads the script, another checks the facts, a third writes the dialogue, and a fourth delivers the final performance. This is what developers call a "multi-agent LLM workflow."

Usually, these robot teams work better than a single robot trying to do everything at once. But here's the problem: if the final performance is bad, it's a nightmare to figure out which robot messed up. Did the fact-checker get the wrong info? Did the writer misunderstand the tone? Or did the final actor just stumble?

Currently, developers have to watch hours of video (the "trace") of the whole play, guessing where the error started. It's like trying to find a single typo in a 500-page book by reading every word again.

Enter PROTEA.

Think of PROTEA as a smart, interactive "rehearsal room" with a magic spotlight. It helps developers debug and improve these robot teams without having to watch the whole movie again and again.

Here is how it works, using simple analogies:

1. The Magic Spotlight (Node-Level Diagnosis)

Instead of looking at the whole play, PROTEA puts a traffic light on every single robot's station.

🟢 Green: This robot did its job perfectly.
🟡 Yellow: This robot was okay, but maybe a little sloppy.
🔴 Red: This robot messed up.

When the final answer is wrong, PROTEA doesn't just say "The play failed." It instantly highlights the Red robot and says, "Hey, look here! This robot gave the next robot the wrong information." It saves the developer from searching through the whole script.

2. The "Reverse Engineer" (Backward Inference)

Sometimes, developers only know what the final answer should be (e.g., "The play must end with a happy laugh"), but they don't have a specific script for what the middle robots should say.

PROTEA uses a trick called Backward Inference. Imagine you know the destination of a road trip but not the turns along the way. PROTEA works backward from the "Happy Laugh" to ask: "For the final robot to laugh, what did the writer robot need to say? And for the writer to say that, what did the fact-checker need to provide?"

It generates a "ghost script" for the middle steps based on the final goal. Then, it compares what the robots actually said against this "ghost script" to find the weak links.

3. The "Edit Button" (Prompt Refinement)

Once PROTEA finds the Red robot, it doesn't just point at it; it offers a suggested fix.

It shows the robot's current instructions (the "Prompt").
It suggests a new, improved version of those instructions.
It shows a "Before vs. After" comparison, like a photo editing tool showing the original and the edited version side-by-side.

The developer can accept the suggestion, tweak it, or ignore it.

4. The "Instant Replay" (Automatic Rerun)

The best part? As soon as the developer hits "Save," PROTEA instantly re-runs the whole play with the new instructions. It then shows a graph of the scores: "See? Before, the score was 64%. After your edit, it's now 84%!"

This creates a fast loop: Find the problem → Suggest a fix → Test it → See the result. No more waiting days to see if a change worked.

What Did They Actually Achieve?

The paper tested this system in two real-world scenarios (though they kept the specific company names secret):

Document Inspection: A system that checks documents for strict rules. PROTEA helped improve its accuracy from 64.3% to 83.9%.
Recommendation System: A chatbot that suggests items (like movies or products). PROTEA helped it get the right recommendation into the top 5 list more often, improving a score from 0.30 to 0.38.

They also tested it on a group of six experienced AI developers. These developers loved the system because it stopped them from staring at endless logs and let them focus on fixing the specific robot that was causing the trouble.

The Bottom Line

PROTEA is a tool that turns the confusing, messy job of debugging a team of AI robots into a clean, visual process. It acts like a coach with a highlight reel, showing you exactly which player dropped the ball and giving you a playbook to fix it, all in one place.

Technical Summary: PROTEA

Problem Statement
Multi-agent Large Language Model (LLM) workflows, which compose multiple role-specific LLM calls into a directed acyclic graph (DAG), often outperform single-prompt baselines. However, refining these systems is a complex, systems-level debugging task. Failures in the final output often stem from subtle errors in intermediate node outputs that propagate downstream. Current evaluation tools (e.g., AgentBench, OpenAI Evals, RAGAs) typically focus on end-to-end success metrics or component-level evaluation (like retrieval relevance) but lack graph-aware diagnosis. Consequently, developers must manually inspect long execution traces to infer which node to modify and how to revise its prompt. Furthermore, in realistic production settings, teams often possess labels only for the terminal output, making the creation of reference outputs for every intermediate node costly and impractical.

Methodology: The PROTEA Framework
PROTEA is a unified, offline, test-driven interface designed for the iterative refinement of multi-agent LLM workflows. It operates on a fixed-suite iteration loop: executing the workflow, evaluating intermediate nodes, localizing bottlenecks, revising prompts, and re-evaluating. The system is built around three core mechanisms:

Backward Node Evaluation: To address the scarcity of intermediate references, PROTEA generates candidate node-level expectations from the final-answer reference and the graph context. Formally, starting from the final node's supervision signal ( $y^*_{final}$ ), the system uses a reference-generation step ( $M_{gen}$ ) to infer the required output for upstream nodes based on downstream requirements. This allows the system to evaluate intermediate nodes in reverse topological order, comparing observed outputs ( $y_v$ ) against these generated expectations ( $\hat{y}_v$ ) to produce scores and rationales.
Graph-Based Diagnosis: PROTEA overlays per-node states (PASS/WARN/FAIL) and evaluator rationales directly onto the workflow graph. Nodes are sorted by status and score, guiding developers to likely bottlenecks without requiring manual trace inspection.
Localized Prompt Refinement: For a selected node, PROTEA proposes targeted prompt revisions ( $I'_v$ ) based on the evaluator's rationale. These are presented as editable "before/after" comparisons. The system enforces constraints to preserve variable passing, output formats, and to prevent the leakage of test-specific content into prompts. Upon acceptance, the workflow is automatically rerun on the offline test suite to track score trajectories and verify improvements.

Key Contributions

Unified Interface for Iterative Refinement: PROTEA integrates execution, evaluation, diagnosis, and prompt editing into a single loop, reducing the manual effort required to translate evaluation evidence into fixes.
Backward Inference for Supervision: The system introduces a method to generate intermediate node expectations from final answers, enabling effective debugging even when intermediate ground truth is unavailable.
Developer-Centric Workflow: Unlike automatic optimization methods (e.g., DSPy, OPRO) that optimize against an objective function autonomously, PROTEA surfaces candidate bottlenecks and proposes inspectable revisions, allowing developers to adopt, edit, or revert changes in context.

Experimental Results
The authors evaluated PROTEA through two production-adjacent workflow studies, an automatic iteration stress test, and a formative user study with six experienced LLM developers.

Production-Adjacent Studies:
- Document Inspection: In a 5-node enterprise workflow, iterative refinement improved document-inspection accuracy from 64.3% to 83.9%.
- Conversational Recommendation: In a 6-node recommendation workflow, the Hit@5 metric improved from 0.30 to 0.38.
- In both cases, the system helped trace constraint propagation and reduced the need to read long traces end-to-end.
Automatic Iteration Stress Test:
- The system was tested on 11 independently generated workflows. In a subset of 5 workflows with minimal initial prompts, the "AUTO LOOP" mode (automated propose-retain cycle) achieved higher best scores than a no-rewrite baseline in 4 out of 5 cases.
- Notable gains included a jump from 0.186 to 0.800 in a course-scheduling workflow.
- Limitations were observed in tasks with near-binary criteria (e.g., exact-match word problems), where the lack of graded signals for intermediate reasoning hindered optimization.
User Study:
- Six experienced developers found value in graph-level localization, per-node rationales, and the ability to compare prompt revisions with automatic reruns.
- Participants identified future priorities including evaluator calibration, integration with existing toolchains (CI/CD), and versioning support.

Significance and Claims
The paper claims that PROTEA addresses a critical gap in the LLM engineering lifecycle: the difficulty of debugging complex, multi-agent systems where supervision is limited to final outputs. By combining backward inference with a developer-in-the-loop interface, PROTEA enables rapid, test-driven refinement without requiring exhaustive manual labeling of intermediate steps. The authors position the tool as complementary to automatic prompt optimization; while methods like DSPy optimize program behavior against an objective, PROTEA focuses on the developer workflow for concrete multi-agent graphs, surfacing specific, actionable bottlenecks and localized fixes. The results suggest that such an interface can significantly improve workflow performance (e.g., +19.6% accuracy in document inspection) while reducing the cognitive load associated with tracing errors through complex agent graphs.