Mining the Design Space of Multi-Agent Workflows

• Manual studies examine only a few fixed topologies, while automated optimizers discard over 95% of evaluated architectures when returning a task-specific optimum.The paper identifies these as bottlenecks to studying composed workflows and prompt implementations.Source: §I · p. 1
• The two-phase pipeline retains workflow-search trajectories, mines code and prompt features, and tests candidate principles on held-out searches.It uses AFlow MCTS and a sandboxed AutoResearch loop across 26 deterministically verified Enigmata tasks, producing 28,568 workflow–task–performance triplets.Source: §I · p. 1
• Δ = −0.045 for Star-first workflows, while SharedMemory yields Δ = +0.135 over conversational message passing and prompt structure yields held-out gains of Δ = +0.118.The reported effects span entry-point topology, communication state, and prompt specificity and placeholder-based context routing.Source: §I · pp. 1–2
• The work contributes full-trace design-space mining, a 28,568-workflow corpus covering 26 reasoning tasks, and held-out evidence across three levels of workflow design.The stated levels are entry-point topology, communication state, and prompt structure.Source: §I · p. 2

a) Multi-Agent System Design and Topologies

• Earlier MAS studies examine agent-count scaling, collaboration, load balancing, diversity collapse, large swarms, and canonical patterns.The cited work includes Zhang et al., Qian et al., He et al. [14], Chen et al., Willis et al. [28], and Kim et al. [19].Source: §II · p. 2
• Prior topology studies use small fixed sets of hand-crafted designs and treat prompts as fixed constants, whereas this work analyzes composed workflows and prompt structure.The contrast is between fixed topology benchmarks and mining regularities across dynamically composed workflows.Source: §II · p. 2

b) Automated Workflow and Prompt Search

• Automated methods search prompts, graph connections, agent code, or full workflows, but full-workflow optimizers discard intermediate candidates when returning one workflow.This paper repurposes MCTS workflow search to harvest complete trajectories for population-level analysis.Source: §II · p. 2

c) Controlled Reasoning Evaluation

• Downstream benchmarks can conflate coordination with domain knowledge, tool reliability, and grading variance; this work uses Enigmata's deterministic verifiers.Enigmata provides parametric generators and deterministic verification across difficulty tiers.Source: §II · p. 2

A. Workflow Representation and Mining Objective

• The design space includes sequential, Star, Debate, SharedMemory, and hub-augmented multi-round operators that can be composed into workflows.Sequential chains prompts through one agent; Star aggregates isolated parallel workers; SharedMemory uses a persistent document; Debate exchanges peer proposals.Source: Figure 2 · p. 3
• A workflow combines an orchestration graph and prompt module, while its environment pairs a task bundle with a deterministic verifier that returns score and inference cost.The score is mean verification accuracy in [0, 1].Source: A. Workflow Representation and Mining… · p. 3
• Feature mining parses workflow code and prompts into interpretable features, joins them with task descriptors, and tests feature-present versus feature-absent workflow arms on held-out searches.The held-out contrast is the difference in expected score between the high and low arms.Source: A. Workflow Representation and Mining… · p. 3

B. Methodological Challenges in Design-Space Mining

• Using arbitrary generated programs risks syntax errors and degenerate prompts, while retaining only an optimizer's final workflow removes intermediate and negative examples needed for contrasts.The proposed response is to search a structured six-operator vocabulary and retain all 20 intermediate workflows per search.Source: B. Methodological Challenges in… · p. 3
• Tool-free Enigmata evaluation with fixed instances and deterministic verification is used to isolate coordination and prompt structure from domain, tool, and grading confounds.The evaluation uses abstract reasoning puzzles scored by exact rule-based verifiers.Source: B. Methodological Challenges in… · pp. 3–4
• Search-level train, validation, and test splits, an L0-regularized objective, and removal of search and round identifiers address feature overfitting and leakage.The feature space is parsed from graph.py and prompt.py.Source: B. Methodological Challenges in… · p. 4

IV. Methodology: Sampling and Analysis Phases

• The sampling and analysis pipeline pairs full-trace AFlow search with deterministic Enigmata evaluation, then mines workflow-code and prompt features using sandboxed AutoResearch.Source: §IV · p. 4

A. Sampling Phase: Full-Trace Workflow Search via AFlow

• The workflow is executed on M=20 instances in T, with scores and costs recorded in the search tree; N=20 workflows per trace are retained across K=5 independent runs per condition, including successful and failed designs.Source: A. Sampling Phase: Full-Trace Workflow… · p. 4
• Six composable primitives cover sequential chaining, isolated fan-out with one-shot aggregation, shared-document writing, peer debate, and coordinator or moderator variants.Operators can be chained, and each workflow execution is capped at 20 LLM calls.Source: A. Sampling Phase: Full-Trace Workflow… · p. 4

B. Sampling Phase: Controlled Reasoning Evaluation via Enigmata

• The tool-free Enigmata evaluation uses deterministic rule-based verifiers on fixed instances, reusing 20 instances across searches and rounds for each bundle.After filtering syntax-invalid workflows and excluding four puzzles with zero scores, the corpus contains 28,568 executable workflows across 26 puzzles.Source: B. Sampling Phase: Controlled… · pp. 4–5
• Fig. 4 plots macro-mean raw score by MCTS round and puzzle category, with 95% bootstrap confidence intervals, showing the trajectory captured by retaining all 20 rounds.Source: Figure 4 · p. 5

C. Analysis Phase: Sandboxed Feature Mining via AutoResearch

• AutoResearch edits feature-extraction and regression scripts, scoring candidates on held-out validation with an L0-regularized objective to favor parsimony and mitigate overfitting.The penalty applies to the number of active features.Source: C. Analysis Phase: Sandboxed Feature… · p. 5
• Training, validation, and test data are split at the AFlow search level, while the read-only sandbox removes search identifiers and isolates the test set.The stated split proportions are 69.4%, 15.0%, and 15.6%, respectively.Source: C. Analysis Phase: Sandboxed Feature… · p. 5

A. Workflow Corpus and Coverage

• The corpus contains 28,568 executable workflows across 26 Enigmata puzzles, exercising all six operators individually and in chains.The traces comprise 1,701 completed AFlow searches out of 1,740 grid cells.Source: A. Workflow Corpus and Coverage · p. 5

Single-Agent Baselines, Coverage, and Sufficiency

• Multi-agent workflows using mini/nano workers exceeded the GPT-5.4 single-agent baseline on several iterative-constraint tasks, including NaturalLanguageNavigation (0.100 → 0.891 mean accuracy).The reported gains also include MagicSquare (0.033 → 0.359) and StackPermutation (0.467 → 0.849).Source: A. Workflow Corpus and Coverage · p. 5

Principle 1 (RQ1, Entry-Point Topology)

• −0.045 median Δ on held-out searches: Star-first fan-out performs worse than alternative entry topologies.The workflows begin with independent parallel workers and use one-shot aggregation; test effects replicated conditionally on 9/10 puzzles.Source: Figure 6 · p. 6, B. Mining and Verifying Design… · p. 6

Principle 2 (RQ2, Communication State)

• The written-document condition outperformed workflows without it on 6/10 test puzzles (median Δ = +0.135, pW = .011; 9/10 sign agreement) and 10/13 train puzzles (median Δ = +0.072, pW = .002).It had the highest corpus-wide mean accuracy among six operators: 0.23 versus 0.18 for Debate and 0.16 for Star.Source: B. Mining and Verifying Design… · p. 6

Principle 3 (RQ3, Sub-Topological Prompt Structure)

• +0.118 median Δ on 6/13 test puzzles: above-median prompt length predicts higher accuracy, while placeholder count shows a separate positive test effect of +0.059.The placeholder-count effect had 11/13 test puzzles in sign agreement; the authors do not claim character length is causal in isolation.Source: Figure 6 · p. 6, B. Mining and Verifying Design… · p. 6

Candidate Pool and Predictability Gating

• Jointly mining prompt.py raised validation R² from 0.521 with graph features alone to 0.638, across 300 feature-engineering trials and 70 candidate contrasts.The reported prompt-feature gains on held-out searches were comparable to selecting communication or orchestration topology.Source: B. Mining and Verifying Design… · pp. 5, 7

Out-of-Sample Verification and Test Precision

• Held-out effect directions were supported across seven variants, but fewer puzzles cleared strict 95% cluster-Wald intervals than on train because the test split had fewer search clusters.The authors characterize the findings as directionally robust while noting finite-sample uncertainty in task-specific magnitudes.Source: B. Mining and Verifying Design… · p. 7

Full-Trace Mining vs. Point Optimization

• Non-argmax search rounds preserve the intermediate and negative comparisons needed to analyze why workflow designs fail and which edits help.SharedMemory costs more than Debate or Star ($0.25 vs. $0.13) but has the highest corpus-wide mean accuracy.Source: §VI · p. 7

Beyond Topology-Only Benchmarks

• Adding prompt structure to graph features raised out-of-sample predictive power from R² = 0.521 to 0.638, so topology benchmarks should control for prompt richness and placeholder routing.The discussion notes that underspecified role instructions or missing context placeholders can bottleneck an otherwise strong communication graph.Source: §VI · p. 7

Operator Evolution and Tool-Rich Domains

• Future work could feed mined regularities into the operator registry and test the pipeline in tool-rich domains such as coding, games, and social simulations.These extensions would test how topology and prompt principles interact with external tool use and environment feedback.Source: §VI · p. 7

VII. Conclusion

• Full-trace AFlow search across 26 deterministically verified Enigmata tasks yielded 28,568 workflows, and 300 AutoResearch trials identified held-out effects at three workflow-design levels.The reported principles concern Star-first fan-out, SharedMemory versus debate, and prompt specificity and placeholder routing.Source: §VII · p. 7
• The authors release the workflow corpus, evaluation harness, and sandboxed analysis pipeline for reproducible empirical research on multi-agent systems.The conclusion presents these materials as a basis for reproducible research.Source: §VII · p. 7

Limitations

• The evidence is limited to tool-free, deterministically verified Enigmata reasoning tasks and one model family, with mined principles reflecting workflows explored along MCTS runs.The authors identify open-weight models, alternative search algorithms, and tool-interactive domains as directions for future work.Source: Limitations · p. 7

Methodological Formalization and Statistical Estimands

• The formalization frames the pipeline as recovering statistical estimands from observational workflow trajectories and maps validity threats to pipeline stages.The stages include AFlow traversal, Enigmata verification, and sandboxed AutoResearch.Source: Appendix A · p. 9

Implementation Variance and Policy-Conditioned Sampling

• Workflow performance is treated as a policy-conditioned observational estimand: measured feature profiles average over implementation details under the sampling policy, rather than representing an unconditioned intervention.The discussion contrasts trajectory harvesting with random code sampling, which could produce syntax errors or incoherent prompts, and with retaining only an optimizer’s final workflow, which collapses variation.Source: A. Implementation Variance and… · p. 9

Evaluation Variance and Fixed-Bundle Verification

• Observed evaluation scores on open-ended benchmarks can combine workflow reasoning performance with domain/tool bottlenecks and judge noise.The decomposition motivates treating external APIs, domain knowledge, and grading noise as evaluation-variance sources.Source: B. Evaluation Variance and… · p. 9
• Deterministic verification on the same reused instance bundles removes judge variance and lets paired per-puzzle contrasts cancel instance-sampling variance within each cell.The bundles contain 20 deterministically generated instances, reused across five searches and 20 MCTS rounds per puzzle-difficulty cell.Source: B. Evaluation Variance and… · p. 9

Overfitting, Trajectory Leakage, and Out-of-Sample Verification

• Two leakage risks are correlated MCTS rounds crossing data splits and feature selection depending on held-out test outcomes.The analysis splits data by complete AFlow search and confines feature mining to validation data before fixing candidate features and contrast directions for test verification.Source: C. Overfitting, Trajectory Leakage,… · p. 9

Workflow and Model Constraints

• Each workflow is capped at 20 atomic LLM calls, and each search trace at 8,000 calls; the Optimizer is GPT-5.4 while Worker and Aggregator roles use GPT-5.4-mini or GPT-5.4-nano.The workflow cap allows multiple-operator compositions while bounding per-evaluation cost; model snapshots and configuration choices are specified in the appendix tables.Source: Appendix B · p. 9

Sampling Grid and Corpus

• 1,701 completed searches produced 34,020 candidate workflows from a grid of 87 puzzle-bundle cells, with five searches and 20 MCTS rounds per cell.Thirty-seven searches aborted mid-search and two were dispatcher misses; the grid has 87 cells because three puzzles lack an easy bundle.Source: A. Enigmata puzzles · pp. 10–11

Workflow Filtering

• 28,568 workflows remain after filtering unevaluable graphs or prompts and removing four Sequential puzzles that scored zero across searches.The initial 34,020 candidates included 1,031 workflows (3%) with missing or unevaluable graphs; the removed puzzles were EightPuzzle, NinePuzzle, FifteenPuzzle, and SixteenPuzzle.Source: A. Enigmata puzzles · p. 11

Feature-Mining Search Evolution

• Feature-mining runs optimize validation R^2 while penalizing feature-set size, tracking search evolution to restore prior steps and reuse discovered features or combinations.The appendix considers both whole-population validation R^2 and average R^2 across per-puzzle splits.Source: 1) Feature-Mining Search Evolution · p. 11

Candidate Principle Evaluation

• Candidate principles compare per-puzzle mean scores between high and low feature arms, using presence/absence for binary features and median splits for count or continuous features.The effect is Δ = E[score | high arm] − E[score | low arm]; per-puzzle verdicts are aggregated at the principle level.Source: B. Analysis Phase · p. 11

Predictability Gate

• The predictability gate admits a puzzle only when validation R^2 > 0.05 and Spearman ρ > 0.30, with the surrogate’s feature set matched to the design principle being tested.The gate uses a LightGBM regressor; the feature-set choice matters because prompt features can explain variation that structural-only features would miss, and vice versa.Source: B. Analysis Phase · p. 11

Feature Construction

• The feature set combines handcrafted features from executable workflow code and prompt files with features extracted during AutoResearch explorations.Source: B. Analysis Phase · p. 11

Per-Puzzle Breakdowns

• Per-puzzle tables report train and held-out test contrasts, mark untestable cells with fewer than 20 workflows in an arm, and summarize significant directions and median Δ.Tables V–VII each break down a headline principle by puzzle.Source: 1) Per-Puzzle Breakdowns of Mined… · p. 11

Appendix C Design Space Specifications

• The six composable primitives vary agent count, rounds, and prompts while consuming worker and aggregator-role models or their equivalents.Concrete workflows clamp agents to 1–10 and rounds to 1–5; Sequential is the closest operator to a single-agent baseline.Source: A. Operator Set · pp. 11–12, Appendix C · p. 11
• Star-first workflows score lower: the test-split median Δ is −0.045, with 4/12 test cells negative.On training, Star 1st is −7/13 with median Δ = −0.036.Source: Table V · p. 12
• SharedMemory presence scores higher on test: median Δ = +0.135, with 6/10 test cells positive.On training, SM present is +10/13 with median Δ = +0.072; the high arm contains workflows with at least one SharedMemory operator.Source: Table VI · p. 12
• AFlow selects parent workflows with a mixed policy that combines uniform and score-weighted sampling; λ = 0.2 sets the mix and α = 0.4 the temperature.The uniform component is intended to prevent collapse onto the optimizer’s prior and support broad trajectory coverage.Source: B. Parent Selection Policy · pp. 12–13
• Mean prompt-template characters are positive in 6/13 test cells (median Δ = +0.118), after 11/13 positive training cells (median Δ = +0.073).The prompt contrasts also count {name}-style placeholders, with repeats, across module-level prompt-template strings.Source: B. Parent Selection Policy · p. 13, Table VII
• The analysis corpus contains 26 puzzles and 28,568 workflows after excluding four all-zero sliding-tile puzzles and 1,031 unevaluable workflows (3.0%).The four puzzles had no verifier-accepted solution at any difficulty; unevaluable graphs typically involved undefined placeholders or deleted prompt keys.Source: E. Filtered Puzzles and Failure Modes · pp. 13–14

Appendix D Analysis Phase Methodology

• Workflow features come from the operator graph, prompts, and two allow-listed problem descriptors; shared library code is excluded because it is identical across workflows.Base parsers cover operator counts and structure, prompt-length statistics, placeholder topology, and style markers.Source: A. Feature Engineering and Models · p. 14
• Train, validation, and test assignments are deterministic at the complete-search level, and identifiers, split labels, and target-derived features are prohibited.Pinned random seeds, a frozen dependency environment, and restricted machine-local state support byte-for-byte reproduction of findings.Source: A. Feature Engineering and Models · p. 14
• The feature-mining loop hides AFlow’s round index because later workflows inherit score-correlated parent histories that do not reflect architectural design.An early proposal used round index as a direct numerical feature; the mitigation removes it from feature-side metadata.Source: C. Caveats and Mitigated Failure Modes · p. 14
• The sandbox also prohibits aggregate statistics derived from the target column, after train-mean leakage produced spuriously high validation and test R².The prohibition applies regardless of split.Source: C. Caveats and Mitigated Failure Modes · p. 15
• The optimizer prompt allows graph and prompt edits using six operators, requires supported placeholders, and caps graph complexity at ten operator invocations.Each loop iteration commits analysis code and artifacts; the per-commit log records accepted, discarded, and aborted attempts.Source: B. AutoResearch Details · p. 14, D. Prompts · p. 15

Appendix E Corpus Details and Additional Analyses

• Workflow accuracy and log-scale inference cost jointly span a broad range of trade-offs across task categories.The design-space figure plots evaluation accuracy against inference cost in USD.Source: Figure 8 · p. 15
• Running cell means converge to within 0.02 of their full-sweep values well before the full search budget across 26 puzzles.The population-mean estimator figure reports a cleaned subset of 1,465 searches, 300 configurations, and 26 puzzles, with μ̂full = 0.168.Source: Figure 9 · p. 15, Figure 10 · p. 16
• The filtered corpus contains 28,568 workflows from 26 puzzles; four all-zero sliding-tile puzzles are excluded because they cannot contribute per-puzzle effect-size estimates.The corpus tables distinguish workflow counts and score distributions across the broader set of tasks.Source: Table IX · p. 16
• Cluster-Wald intervals use AFlow search as the clustering unit; train contrasts have at least 19 clusters per arm, while test contrasts range from 4 to 14.The test-split support is sparse, with most reported cells below 10 clusters per arm.Source: B. Cluster-Robust Inference and… · p. 16
• The analysis narrowed 300 feature-engineering trials across 10 AutoResearch searches to 70 candidate binarized contrasts spanning three granularities.A prompt-access search ran 49 trials and grew features from 12 to 32; a graph-only search ran 90 trials and decreased its feature set from 12 to 9.Source: C. Candidate Hypothesis Set · p. 17

Appendix F Single-Backbone Baseline Performance

• On puzzles where all three single-backbone baselines score zero, workflows reach at most 0.05 on Slant and LightUp, while four sliding-tile puzzles remain at 0.00.The four all-zero puzzles are excluded from the analysis corpus.Source: Appendix F · p. 17

Appendix G Computational Cost Analysis

• Evaluating one workflow on one puzzle instance costs an average of $0.0061 on Easy and $0.0067 on Hard; estimated evaluation for 1,740 searches is about $4,454.The estimate excludes additional optimizer-LLM search costs.Source: Appendix G · p. 17

Appendix H Trace Examples

• In the illustrated search, the best score reached 0.90 at round 16, while four of the final five rounds scored at or below 0.75.The trace moves from single-operator workflows in rounds 1–6 to two-operator chains thereafter, and its lineage tree shows both improvements and regressions.Source: Appendix H · p. 17, Figure 11 · p. 20

Appendix I Gate Calibration

• The predictability gate requires validation R² > 0.05 and Spearman ρ > 0.30, above the pooled permutation-null bounds of R²p95 ≤ −0.06 and ρp95 ≤ 0.23.The authors describe the gate as conservative, favoring false-negative robustness over admitting more puzzles.Source: Appendix I · pp. 17–18, Figure 12 · p. 21

Appendix J Broader Societal Impact

• The contribution is methodological: the framework statistically examines determinants of agentic performance but introduces no new agent and does not extend deployed-system capability.The authors say the work inherits the dual-use risk common to capability research.Source: Appendix J · pp. 18–19

Appendix K LLM Usage

• LLMs are used for automated workflow generation, including code generation, and for iterative data analysis.They were also used to polish writing, check typos, and provide initial programming skeletons later refined by the authors.Source: Appendix K · p. 19