Pay for the Fault, Not the Flow: Label-Free In-Flow Multi-Agent Workflow Optimization

AI summary

Overview

• Research area: Large language model (LLM) based multi-agent systems — specifically automatic construction and runtime repair of agent workflows.
• Technical level: Advanced.
• Scope: The paper introduces InFlowOp, a training-free framework that builds and repairs multi-agent workflows using a single label-free cost signal, and Braid, a benchmark of tasks designed to require multi-agent coordination beyond single-agent capability.

What This Paper Is About

When an LLM constructs a multi-agent workflow, it must decide how finely to split a task, which specialist agent takes each part, and when to create a new specialist — but whether any subtask actually succeeds is unknown until the workflow runs. Improving such a workflow has traditionally required a reference answer, a graded outcome, or a trained assessor, and the fix is usually applied to the whole workflow through re-execution, re-search, or retraining. The paper's goal is to price every one of these decisions with a single label-free cost that weighs how well an agent's competence meets a subtask's demand against how much that agent costs to run, and to use that same cost both while the workflow is being built and while it runs.

Key Contributions

1. Coalesce — cost-driven bidirectional workflow construction. A method (Alg. 3) that decomposes a task top-down into its finest atoms and then coalesces them bottom-up into subtasks, letting cost rather than a fixed template determine granularity and agent assignment. New agents are created only when no available agent clears a competence bar (C̄), triggering a coverage residual penalty (γ).
2. InFlowOp — optimization in flow, without supervision. A two-stage, training-free framework (Alg. 1) that detects faults during execution against contracts declared at construction time, pauses at the faulty subtask, corrects it via a cost-ordered ladder (Re-assign ≺ Re-decompose), and resumes only the affected closure — with no reference answer, graded outcome, or trained assessor.
3. Braid — a benchmark for reasoning over agent-interdependent divisions. A workflow-level benchmark whose tasks require multi-agent coordination beyond single-agent competence, built on 10 public datasets and spanning 19 evaluation-only arms across 8 domains, with two composition methods (distributed and anchored) and four quality-control criteria.
4. Evaluation across domains and backbones. Experiments over eight domains, six backbones, and four workflow constructors, plus ablations of the estimator, the cost matrix, the agent pool, and the evolving profile.

Main Findings

• Consistent gains across backbones. InFlowOp improves every backbone over both baselines. Accuracy on the five-domain subset (Table 1, averaged over 16 arms) runs from 20.81 (Qwen3.5-4B) and 25.13 (Qwen3.5-9B) to 27.01 (GPT-5-mini), 29.46 (GPT-5.4-mini), 38.52 (GPT-5.4), and 49.37 (GPT-5.6-luna).
• Gains over baselines. Over the single LLM baseline (1.74 for Qwen3.5-4B up to 28.25 for GPT-5.6-luna), the paper reports gains up to +21.90%; over the single agent baseline (13.66 for Qwen3.5-4B up to 41.99 for GPT-5.6-luna), the introduction and contribution list report gains from +7.15% to +11.97% under a matched turn budget, and the abstract reports up to +11.97% over single-agent baselines with +9.64% achieved through in-flow optimization. Section 5.2 states gains up to +21.90% over the single LLM baseline and up to +11.97% over the single agent baseline with a matched compute budget, and up to +9.64% over workflow baselines.
• Stability of the gain. What InFlowOp earns varies by ≤3.74% across the six backbones, whereas the single agent's gain over the single LLM ranges from +6.90% to +14.15%.
• A small backbone can beat larger ones. Under InFlowOp, Qwen3.5-4B reaches 20.81%, above the single-agent accuracy of Qwen3.5-9B (17.38), GPT-5-mini (16.33), and GPT-5.4-mini (17.49).
• Division alone is not the gain. A greedily built workflow reaches 15.49%, below the single agent's 17.38%, on Qwen3.5-9B (Table 2). Cost-decided division reverses this: Coalesce reaches 22.21% (+6.72% over greedy search, +4.83% over the single agent), in-flow tempering adds +1.59% (23.80), and scoring agents on the evolving profile adds +1.33% more (25.13, +7.75% over the single agent).
• Cost is better computed than judged. Replacing the rubric semantic estimator with a single-pass LLM estimator costs −3.27% on Qwen3.5-4B and −3.85% on Qwen3.5-9B, leaving Qwen3.5-9B below the 22.21% it reaches under Coalesce alone.
• A dynamic cost matrix helps. A matrix that updates as new agents are created outperforms a static one by +3.15% (Qwen3.5-4B) and +2.55% (Qwen3.5-9B).
• A dynamic pool raises the ceiling. Allowing new specialist agents beats settling for the closest available agent by +4.49% (Qwen3.5-4B) and +3.29% (Qwen3.5-9B).
• Profiles must remember success. A profile evolving within a run gains +2.54%, +1.33%, and +2.23% over the agent card alone on Qwen3.5-4B, Qwen3.5-9B, and GPT-5.4-mini; continuing across runs while keeping only successful entries adds +1.21%, +1.19%, and +1.30%. Applying all entries instead reaches 17.34%, 21.52%, and 26.53% — below the agent card alone on all three backbones.
• Global localization loses accuracy. Enabling a global pass beside the local one yields −1.63% on Qwen3.5-4B and −1.41% on Qwen3.5-9B, which is why in-flow optimization stays local in every other experiment.
• Domain variation. Gains are largest on charts, mathematics, and finance, and smallest on physics, where all methods stay ≤17.34% under any backbone.
• Table 1's Δ_acc column. The table lists Δ_acc values such as +19.07 (InFlowOp, Qwen3.5-4B) and +21.90 (InFlowOp, Qwen3.5-9B); the table caption does not state the reference point for Δ_acc.

Methodology in Plain English

The framework replaces hand-chosen workflow structure with one measurable quantity: cost. Every agent is described by a card containing its declared competence (role, domain, skills, tools) plus a self-evolving empirical profile of what it has actually done well and where it has failed. A rubric-based estimator matches what each piece of work demands against what each agent supplies, producing a cost matrix whose rows are work atoms and columns are agents.

Construction runs in two directions. Top-down, the task is broken into its finest atoms. Bottom-up, those atoms are coalesced into subtasks (Coalesce), merging only where a coarser grouping lowers overall cost, and binding each subtask to its lowest-cost agent. If no pooled agent clears the competence bar for an atom, a new agent is created at a penalty. The optimization target balances reliability cost, latency cost, and creation cost.

Execution is then treated as the first real evidence about the workflow. Because Coalesce records each subtask's contract — the input conditions it requires and the output conditions it promises — a fault becomes observable without knowing the answer. Detection reuses the same matching machinery retrospectively: unmet input conditions blame the decomposition, unmet output conditions blame the assignment. A faulty subtask is paused, corrected with the cheapest available move (re-assign an agent first, re-decompose only once re-assignment is exhausted), verified, and then execution resumes over only the subtask and its descendants, with all other cached results replayed. If a correction cannot be verified, or its budget runs out, the change is rolled back, so tempering never leaves the workflow worse than construction produced.

Why This Matters

Impact on research. The work reframes workflow construction and repair as minimizing a single annotation-free surrogate rather than a supervised learning problem, and it argues that many existing multi-agent benchmarks are satisfiable by a competent single agent — a claim it addresses by releasing Braid. It also supplies an explicit cost taxonomy (reliability, latency, creation, workflow, optimization) and reports negative results, such as global localization and failure-heavy profiles both hurting accuracy.

Real-world applications.

• Document and file-based analysis pipelines, the Doc domain, where the paper notes a single LLM scores near zero because inputs arrive as files it cannot access without tools.
• Financial analysis and chart reasoning, where the largest gains appear and where accurate, low-latency composition of specialist agents matters.
• Mathematical and scientific reasoning workflows, including the physics domain where all evaluated methods remain weak and the paper's own reporting shows little separation.
• Coding, slides, and science tasks, the three additional domains evaluated across the full eight-domain benchmark.

Industry relevance. The framework targets cost containment: faults are paid for at the size of the fault rather than the size of the workflow, re-assignment precedes re-decomposition

Authors’ abstract

Large language models (LLMs) increasingly construct multi-agent workflows that decompose a complex task and assign specialist agents from a pool. However, building such a workflow well remains challenging: how finely to divide the task, which agent to trust with each subtask, and when to create a new specialist are all critical decisions a workflow constructor needs to settle up front. Thus, whether each subtask succeeds remains unknown until the workflow runs. Yet, improving a workflow is costly. Locating a fault usually requires a reference answer, a graded outcome, or a trained assessor, and the fix is applied to the whole workflow through re-execution, re-search, or retraining. We propose InFlowOp, which prices every decision in one label-free cost that weighs how well an agent's competence meets what a subtask demands against how much that agent takes to run. Before execution, InFlowOp bidirectionally determines the granularity of task decomposition and agent assignment following from the cost rather than from a fixed template. During execution, InFlowOp corrects a fault with the cheapest move via the same cost that serves the workflow both as it is built and as it runs. Facing the workflow-level evaluation challenge, we introduce Braid, a benchmark whose tasks require multi-agent coordination beyond single-agent capability. Across various domains and backbones, InFlowOp outperforms single agent baselines by up to $+11.97\%$, achieving $+9.64\%$ with in-flow optimization. Our project page: https://xhguo7.github.io/InFlowOp/.