Mining the Design Space of Multi-Agent Workflows

Xavier Cadet; Junyan Cheng; Peter Chin; Kyle Richardson

cs.SEOct 22, 2026

Mining the Design Space of Multi-Agent Workflows

Authors: Xavier Cadet, Junyan Cheng, Peter Chin, Kyle Richardson

Organizations: Dartmouth College · Allen Institute for AI

Abstract

Designing large language model (LLM) multi-agent systems (MAS) still relies on trial and error and informal "folk wisdom." Manual studies test only a few communication structures or topologies (e.g., sequential, parallel, shared-memory, or debate), while automated optimizers discard search trajectories after selecting a task-specific workflow. We present a two-phase pipeline for mining reproducible design principles from workflow code and execution traces. We repurpose AFlow's MCTS optimizer across six composable operators and 26 deterministically verified Enigmata tasks, retaining all intermediate rounds to build a corpus of 28,568 executable workflows. A sandboxed AutoResearch loop then mines orchestration code and prompt templates under an $L_0$ -penalized validation objective and tests candidate principles on held-out searches. Across 300 feature-mining trials, we identify effects that persist on held-out searches across three levels of workflow design: workflows beginning with independent solvers and one-shot aggregation (Star-first) perform worse ( $Δ= -0.045$ ); persistent shared documents (SharedMemory) outperform debate ( $Δ= +0.135$ ); and prompt specificity and placeholder-based context routing yield gains comparable to communication-structure selection ( $Δ= +0.118$ ). More broadly, our pipeline and results show the feasibility of turning discarded search trajectories into a statistical testbed for discovering and validating multi-agent workflow design principles.

Figures & tables

Fig. 1: Overview of our two-phase pipeline. (1) Sample: for each verified task bundle

T

, an AFlow MCTS search proposes and evaluates workflows; optimizers keep only the final

W^{*}

, whereas we keep every evaluated node (

N{=}20

rounds

\times

K{=}5

runs, failures included). (2) Build a corpus: each of the

28{,}568

entries is a triplet

(W,T,\boldsymbol{m})

, an executable workflow

W

(orchestration code graph.py plus its prompt templates prompt.py ), a task bundle

T

, and verified metrics

\boldsymbol{m}

(score, cost), split into train/val/test at the level of whole searches. (3) Mine features: a sandboxed AutoResearch loop proposes code and prompt features

\boldsymbol{a}=\phi(W)

(e.g., the entry operator or the number of {placeholders} ), fits a regressor

\kappa

from

(\boldsymbol{a},\boldsymbol{t})

\boldsymbol{m}

, and scores candidates by

L_{0}

-penalized validation

R^{2}

. (4) Verify principles: surviving features are tested on held-out searches as score contrasts

\Delta

between workflows that have vs. lack the feature.

Fig. 2: The six operator primitives

\mathcal{O}

spanning our design space , drawn for

n{=}3

workers and

r{=}2

rounds. Circles are worker calls and squares are hub calls (aggregator A, coordinator C, moderator M); blue edges show which earlier outputs a call reads, purple edges connect workers to a hub. Sequential chains prompts through one agent; Star fans out to isolated workers and aggregates once; Debate lets every worker read all peer proposals before revising; SharedMemory has workers take turns appending to one persistent document (blackboard); StarW/Coordinator and DebateW/Moderator add a hub call after every round. calls counts LLM calls (cost) and steps counts sequentially dependent calls (latency); with a single round the three multi-round operators reduce to Star . The optimizer composes operators in graph.py and writes their prompts in prompt.py (Fig. 3 ).

Fig. 3: Composing operators in graph.py . A Star workflow (three workers, one aggregator) drafts a Sudoku solution; graph.py then forwards the original puzzle together with the draft into a one-step Sequential validator. Every call’s prompt template lives in prompt.py , with placeholders such as {problem} and {worker_outputs} filled at run time. Features such as the entry operator, chain length, and placeholder counts are parsed from exactly these two files.

Fig. 6: Per-Puzzle Effect Sizes of Mined Design Principles. Per-puzzle score contrast

\Delta

(high arm

-

low arm) for the three principles on the search-level train split (filled circles,

n=19{,}822

) and held-out test split (open squares,

n=4{,}468

), with

95\%

cluster-robust CIs; effect directions are consistent out-of-sample.

		Train					Held-out test					Sign agreement		Test-verified
	Variant	$n$	$k_{+}$	$k_{-}$	med $\Delta$	$p_{\mathrm{W}}$	$n$	$k_{+}$	$k_{-}$	med $\Delta$	$p_{\mathrm{W}}$	$k/n_{\cap}$	$p_{\mathrm{B}}^{\cap}$	$k/n_{\mathrm{tr}}$	$p_{\mathrm{B}}^{\mathrm{tr}}$
Principle 1 (RQ1, Entry-Point Topology): Star-first hurts performance (claim direction $-$ )
	Star 1st	13	0	7	$-0.036$	.008	12	0	4	$-0.045$	.038	9/12	$<$ .001	9/10	.011
	Star $\times$ compute	13	0	7	$-0.036$	.008	12	0	3	$-0.041$	.038	9/12	$<$ .001	9/10	.011
Principle 2 (RQ2, Communication State): SharedMemory boosts reasoning (claim direction $+$ )
	SM present	13	10	0	$+0.072$	.002	10	6	0	$+0.135$	.011	9/10	$<$ .001	9/10	.011

TABLE I: Statistical Summary of Mined Design Principles. Per variant: gate-admitted puzzles (

n

), cells with strictly positive (

k_{+}

) / negative (

k_{-}

) 95% cluster-Wald CIs, median effect size (

\Delta

), and Wilcoxon

p

-values (

p_{\mathrm{W}}

) on train and held-out test splits, with out-of-sample sign agreement (

p_{\mathrm{B}}^{\cap}

) and conditional test verification (

p_{\mathrm{B}}^{\mathrm{tr}}

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

Challenge	Manifestation in MAS Evaluation	Pipeline Stage	Methodological Design
Design-space coverage & implementation variance	Manual studies test only a few fixed topologies; argmax search discards intermediate designs; naive random code generation produces broken prompts or syntax errors.	AFlow Search ( Sampling ; § IV-A )	Retains all $N=20$ MCTS rounds across $K=5$ runs over 6 composable operators, sampling both failed and high-performing workflows under a consistent LLM optimizer policy (§ A ).
Domain & evaluation confounds	Downstream benchmarks conflate coordination topology with external tool APIs, domain knowledge, or noisy LLM-as-a-judge grading.	Enigmata Verification ( Sampling ; § IV-B )	Tool-free evaluation on 26 parametric abstract-reasoning tasks with exact, deterministic rule-based verifiers and fixed 20-instance bundles per difficulty tier (§ C-D ).
High-dimensional feature overfitting & leakage	Workflow code ( graph.py ) and prompts ( prompt.py ) admit infinitely many features; manual selection is narrow, while unconstrained search overfits or leaks test data.	AutoResearch Mining ( Analysis ; § IV-C )	Sandboxed AST/prompt feature mining with an $L_{0}$ -penalized validation $R^{2}$ objective on strict search-level splits; pre-specified directional verification on held-out test searches (§ D ).

Appendix

TABLE II: Core methodological challenges in empirical MAS design-space mining and corresponding pipeline components. Each stage of the pipeline addresses a specific operational threat to extracting reproducible design principles.

Models
Hyperparameters	Values
Optimizer	GPT-5.4
Opt. Temperature ( $t$ )	0
Worker	[GPT-5.4-mini, GPT-5.4-nano]
Worker temperature ( $t$ )	0
Aggregator	[GPT-5.4-mini, GPT-5.4-nano]

Appendix

TABLE III: Hyper-parameters

Model name	Snapshot
GPT-5.4	gpt-5.4-2026-03-05
GPT-5.4-mini	gpt-5.4-mini-2026-03-17
GPT-5.4-nano	gpt-5.4-nano-2026-03-17

Appendix

TABLE IV: Model snapshots for the OpenAI models.

	Star 1st
Puzzle	tr	te
Campsite	$-0.095$	$-0.111$
CarPainting	$+0.004$	$-0.021$
CryptoKKA	$-0.052$	$-0.076$
CryptoKPA	$-0.012$	$-0.003$
Game24	$-0.036$	$-0.020$

Appendix

TABLE V: Principle 1 (RQ1): Star as the first operator lowers score. Per-puzzle effect size

\Delta

score (high arm

-

low arm) on the train and held-out test splits. Feature definitions: Star 1st = binary indicator: 1 iff the first operator instantiated in graph.py (parsed in source order) is Star ; high arm = 1, low arm = 0.

k_{+}/n

and

k_{-}/n

count cells whose 95% cluster-Wald CI is strictly above / below zero (out of testable cells). Headline: Star 1st

-7/13

on train (median

\Delta=-0.036

); Star 1st

-4/12

on test (median

\Delta=-0.045

	SM present
Puzzle	tr	te
Campsite	$+0.168$	$+0.178$
CarPainting	$+0.003$	$+0.076$
CryptoKKA	$+0.178$	$+0.139$
CryptoKPA	$+0.036$	$+0.009$
Game24	$+0.072$	–

Appendix

TABLE VI: Principle 2 (RQ2): SharedMemory operators raise score. Per-puzzle effect size

\Delta

score (high arm

-

low arm) on the train and held-out test splits. Feature definitions: SM present = count of SharedMemory operator instantiations in graph.py , median-split within each puzzle; the per-puzzle median is 0 for every puzzle so the high arm = workflows with

\geq

1 SharedMemory operator and the low arm = workflows with none.

k_{+}/n

and

k_{-}/n

count cells whose 95% cluster-Wald CI is strictly above / below zero (out of testable cells). Headline: SM present

+10/13

on train (median

\Delta=+0.072

); SM present

+6/10

on test (median

\Delta=+0.135

	mean chars		#placeh.
Puzzle	tr	te	tr	te
Campsite	$+0.094$	$+0.123$	$+0.132$	$+0.145$
CarPainting	$+0.006$	$+0.015$	$+0.008$	$+0.049$
CryptoKKA	$+0.171$	$+0.132$	$+0.154$	$+0.132$
CryptoKPA	$+0.052$	$+0.028$	$+0.056$	$+0.029$
Game24	$+0.047$	$+0.025$	$+0.048$	$+0.020$

Appendix

TABLE VII: Principle 3 (RQ3): Longer, structurally rich prompts raise score. Per-puzzle effect size

\Delta

score (high arm

-

low arm) on the train and held-out test splits. Feature definitions: mean chars = mean character length of the module-level string-assignment prompt templates in prompt.py , median-split within each puzzle (high arm = above the puzzle’s median); #placeh. = total occurrence count of {name} -style format placeholders (matched by r"{[a-zA-Z_][a-zA-Z0-9_]*}" , with repeats) across all module-level prompt-template strings in prompt.py , median-split within each puzzle.

k_{+}/n

and

k_{-}/n

count cells whose 95% cluster-Wald CI is strictly above / below zero (out of testable cells). Headline: mean chars

+11/13

on train (median

\Delta=+0.073

) and

+6/13

on test (median

\Delta=+0.118

); #placeh.

+9/13

on train (median

\Delta=+0.102

) and

+7/13

on test (median

\Delta=+0.059

Operator	Communication	Structure	Params	Calls
Sequential	single agent	linear pipeline	$r,\mathbf{p}$	$\|\mathbf{p}\|\cdot r$
Star	isolated workers	fan-out $\to$ agg	$n,\mathbf{p}_{w},p_{a}$	$n+1$
SharedMemory	shared doc	writes $\to$ agg	$n,r,\mathbf{p}_{w},p_{a}$	$n\cdot r+1$
Debate	all-to-all	exchange $\to$ agg	$n,r,\mathbf{p}_{w},p_{a}$	$n\cdot r+1$
StarW/Coordinator	coord $\leftrightarrow$ workers	iterative hub-spoke	$n,r,\mathbf{p}_{w},p_{a}$	$(n+1)\cdot r$
DebateW/Moderator	all-to-all + mod	debate + mod/round	$n,r,\mathbf{p}_{w},p_{a}$	$(n+1)\cdot r$

Appendix

TABLE VIII: Composable operator primitives.

n\in[1,10]

workers;

r\in[1,5]

rounds.

\mathbf{p}_{w}

: list of worker prompts (one per agent);

p_{a}

: second-role prompt (aggregator / coordinator / moderator). Sequential is single-agent and takes a single prompt list

\mathbf{p}

. See Fig. 2 for the topology of each operator and Fig. 3 for how operators compose.

Fig. 7: Example of two AutoResearch searches, one exploring with access to only the executable workflow code without custom prompts, the other with access to both. The number of rounds differs based on when the AutoResearch instance considers it is stalling.

Fig. 8: Design-Space Coverage. Joint distribution of workflow evaluation accuracy versus inference cost (USD, log scale) across task categories, spanning a broad spectrum of accuracy-cost trade-offs.

Fig. 9: Sampling Sufficiency. Absolute deviation of the running cell mean from its full-sweep value across 26 puzzles as a function of search count

k

. Rapid convergence below

0.02

confirms estimator stability.

Fig. 10: Convergence of the population-mean score estimator. For each

k

(log scale), we draw

B{=}2{,}000

bootstrap replicates of

k

resampling units with replacement and plot the bootstrap median (line) and central

95\%

band of

\hat{\mu}(k)=\mathrm{mean}_{\mathrm{rows}}(\mathrm{score})

. Three resampling units: SRS over searches (blue), SRS stratified by (dataset, difficulty) (orange), SRS over configurations (red). Dashed horizontal line: full-population mean. Dotted verticals:

N_{\mathrm{search}}

(black),

N_{\mathrm{cfg}}

(red). Cleaned subset (4 sliding-tile puzzles dropped):

1{,}465

searches,

300

configurations,

26

puzzles,

\hat{\mu}_{\mathrm{full}}{=}0.168

Split	Count	Percentage
Total	28,568	100.0%
Train	19,822	69.4%
Validation	4,278	15.0%
Test	4,468	15.6%

Appendix

TABLE IX: Effective workflow counts across splits. Of 1,701 in-scope completed AFlow searches, each generating up to 20 workflows (34,020 candidates), 32,989 are executable. A further drop to 28,568 workflows removes the four filtered sliding-tile puzzles (Eight/Fifteen/Nine/SixteenPuzzle), where no workflow ever scored above zero. These are then divided into the train/val/test split.

Task	Easy ($)	Medium ($)	Hard ($)	Mean ($)
StarBattle	$0.0110	$0.0096	$0.0099	$0.0102
SumSkyscraper	$0.0108	$0.0092	$0.0102	$0.0100
Sudoku	$0.0096	$0.0105	$0.0090	$0.0097
ZebraLogic	$0.0062	$0.0097	$0.0116	$0.0091
Campsite	$0.0065	$0.0104	$0.0102	$0.0091
Kakurasu	$0.0094	$0.0063	$0.0113	$0.0090

Appendix

TABLE X: Average cost in USD to evaluate one workflow against a single target puzzle instance, by task and difficulty. “–” marks (puzzle, difficulty) cells that Enigmata’s generator does not provide.

Operator	# Workflows	Percentage	Score		Cost
Operator	# Workflows	Percentage	w	w/o	w	w/o
Sequential	13,473	47.16	0.14	0.19	0.14	0.15
Star	12,716	44.51	0.16	0.17	0.13	0.16
Debate	6,373	22.31	0.18	0.17	0.13	0.15
SharedMemory	5,948	20.82	0.23	0.15	0.25	0.12
DebateWithModerator	3,382	11.84	0.19	0.16	0.19	0.14

Appendix

TABLE XI: Operator presence over the filtered analysis corpus (28,568 workflows). For each operator we contrast the mean of score and cost between workflows that contain the operator ( w ) and those that don’t ( w/o ).

Operator combination	# WFs	Percentage	Score		Cost
Operator combination	# WFs	Percentage	w	w/o	w	w/o
Star $\to$ Seq	4,564	15.98	0.14	0.17	0.12	0.15
Star	4,125	14.44	0.15	0.17	0.07	0.16
Debate	2,346	8.21	0.17	0.17	0.09	0.15
SharedMemory $\to$ Seq	2,158	7.55	0.18	0.17	0.23	0.14
Seq	2,078	7.27	0.09	0.17	0.05	0.16

Appendix

TABLE XII: Top-10 most-used operator combinations over the filtered analysis corpus (28,568 workflows), ranked by frequency. Operators in a sequence are connected by

\to

. For each row, we contrast the mean of score and cost between workflows that use the exact sequence ( w ) and the rest of the corpus ( w/o ).

Graph
Puzzle	# WFs	Mean	Std	Min	25%	50%	75%	Max	Skew	Kurt.
HamilCycle	1,164	0.073	0.101	0.00	0.00	0.00	0.10	0.40	1.40	1.10
HamilPath	1,147	0.150	0.158	0.00	0.00	0.10	0.25	0.70	0.96	-0.05
Maze	1,075	0.479	0.221	0.00	0.35	0.50	0.65	1.00	-0.21	-0.29
NLNavigate	1,120	0.561	0.322	0.00	0.30	0.65	0.85	1.00	-0.36	-1.18
Logic

Appendix

TABLE XIII: Per-puzzle distribution of score over the full corpus of 32,989 workflows on the 30 Enigmata puzzles. Rows are grouped by category (Graph

\to

Logic

\to

Grid

\to

Crypto

\to

Arithmetic

\to

\to

Sequential), alphabetical within category. The four sliding-tile puzzles in the Sequential category (Eight/Fifteen/Nine/SixteenPuzzle) have all-zero distributions; they are excluded from the analysis corpus used by the other tables.

Category	Puzzle	GPT-5.4	GPT-5.4-mini	GPT-5.4-nano	$W_{\mu}$	$W_{max}$	USD($)@max
Arithmetic	Countdown	0.033	0.017	0.017	0.173	0.700	0.228
Arithmetic	Game24	0.150	0.083	0.050	0.288	0.700	0.220
Crypto	CryptoKKA	0.267	0.067	0.000	0.412	1.000	0.081
Crypto	CryptoKPA	0.050	0.050	0.000	0.139	0.650	0.238
Graph	HamilCycle	0.133	0.017	0.000	0.228	0.400	0.080
	HamilPath	0.300	0.100	0.017	0.363	0.700	0.233

Appendix

TABLE XIV: Single-backbone baselines: One-shot pass rate of GPT-5.4, GPT-5.4-mini, and GPT-5.4-nano evaluated directly on the per-puzzle bundle without scaffolding, alongside workflow-level statistics from our workflow corpus: mean score

W_{\mu}

, maximum score

W_{\max}

, and the per-instance inference cost of the maximum-scoring workflow (

\

@\max$ ). Puzzles are grouped by category. The four all-zero sliding-tile puzzles are listed for completeness and excluded from the analysis corpus.

	Granularity	Prior Rule?	Representative Mined Principle
RQ1	Entry-Point Topology	✓	Star as primary operator lowers score
RQ2	Communication State	✗	SharedMemory outperforms dialogue
RQ3	Sub-Topological Prompts	✗	Prompt specificity (length, #placeh. ) helps

Appendix

TABLE XV: Three Granularities of Mined Design Principles. We evaluate our framework across progressively finer levels of workflow specification: from verifying an established macro-topological failure mode ( RQ1 ), to comparing blackboard-style shared state against conversational topologies ( RQ2 ), to mining sub-topological code and prompt template structure ( RQ3 ).

Fig. 11: AFlow search trace for a single

(\text{puzzle},\text{model triple})

cell on EnigmataNaturalLanguageNavigation, with worker and aggregator at gpt-5.4-nano and optimizer at gpt-5.4 ( experiment_id = 1bf64a7c ). Top-left: per-round workflow score (orange bars) and best-so-far envelope (black step line); open circles mark rounds that improved the running maximum. Bottom-left: operator-composition trajectory, with bar height equal to the number of operator instantiations and color denoting operator type (gray = Sequential , purple = Star , green = Debate ). Right: MCTS lineage tree, with each node labeled by round and positioned vertically by score. The gold path traces the root-to-best lineage (

\text{root}\to r_{16}

, score

0.90

); edge color encodes whether the child improved (green) or regressed (red) relative to its parent.

Fig. 12: Per-puzzle predictability gate diagnostics across feature subsets. For each puzzle, bars show validation

R^{2}

and diamonds show validation Spearman

\rho

against the permutation-calibrated thresholds (

R^{2}>0.05

red dashed line;

\rho>0.30

purple dotted line; 95th-percentile permutation null bounds shown in gray). A puzzle is admitted iff both metrics clear their respective thresholds on

D_{\text{val}}

Multi-Agent Orchestration

Multi-agent orchestration coordinates specialized AI agents, tools, and workflows to solve complex tasks efficiently and reliably.

See all 207 papers

EvoMAS: Learning Execution-Time Workflows for Multi-Agent Systems
May 9, 2026Chengdong Xu, Kaiqiang Ke, Ziheng Liu +4Multi-Agent LLM Systems Multi-Agent System Optimization
Sun Yat-Sen University · ShanghaiTech University · Zhejiang University +1
WorkflowOps: Learning Agent Collaboration Priors for Multi-Agent Workflow Orchestration
Oct 6, 2026Qi Cheng, Shengyu Chen, Wei Cheng +4LLM Agent Orchestration LLM Agent Workflow Optimization
Rutgers University, New Brunswick, NJ · University of Pittsburgh, Pittsburgh, PA · NEC Labs America, Princeton, NJ
FlowMAS: Learning Multi-Agent Workflow Topology via Information-guided Generative Flow Network
Sep 29, 2026Haitao Wang, Chenjing Liang, Haipeng Zhang +6Multi-Agent LLM Systems Multi-Agent System Optimization
Fujian Key Laboratory of Urban Intelligent Sensing and Computing, Xiamen University, Xiamen, China · School of Computer, National University of Defense Technology, China

May 9, 2026J/K move · Enter open · S save

EvoMAS: Learning Execution-Time Workflows for Multi-Agent Systems

Chengdong Xu, Kaiqiang Ke, Ziheng Liu, Jiaqi Wei+3

Sun Yat-Sen University · ShanghaiTech University · Zhejiang University+1

Multi-Agent LLM Systems Multi-Agent System Optimization Multi-Agent Orchestration LLM Agent Workflow Optimization Long-Horizon LLM Agents RL for LLM Agents

Open paper AskPDF arXiv

Large language model (LLM)-based multi-agent systems have shown strong potential on complex tasks through agent specialization, tool use, and collaborative reasoning. However, most automated multi-agent system design methods still follow a one-shot paradigm: a workflow is optimized or selected before execution and then reused unchanged throughout the task. This static coordination strategy is ill-suited for long-horizon tasks whose subgoals, intermediate evidence, and information needs evolve over multiple execution stages. We propose EvoMAS, a framework for execution-time multi-agent workflow construction. EvoMAS formulates workflow construction as a meta-level sequential decision problem along a single task trajectory. At each stage, it constructs an explicit task state through a Planner-Evaluator-Updater pipeline and uses a learned Workflow Adapter to instantiate a stage-specific layered workflow from a fixed pool of candidate agents. The adapter is trained with policy gradients using sparse, verifiable terminal task success as the main supervision signal, while evaluator-based process reward is analyzed separately under very-hard sparse-reward settings. Experiments on GAIA, HLE, and DeepResearcher show that EvoMAS outperforms single-agent baselines and recent automated multi-agent workflow design methods. Our analyses further show that explicit task-state construction and learned workflow adaptation provide complementary benefits. Additional results indicate that process reward is most useful when terminal success is extremely sparse, and qualitative case studies illustrate that EvoMAS adapts agent coordination as the task state evolves.

Abstract

Multi-Agent Orchestration

Explore similar work

EvoMAS: Learning Execution-Time Workflows for Multi-Agent Systems

WorkflowOps: Learning Agent Collaboration Priors for Multi-Agent Workflow Orchestration

FlowMAS: Learning Multi-Agent Workflow Topology via Information-guided Generative Flow Network