acceptodds
Under review as a conference paper at ICLR 2027

What Matters for Agent Replacement? Low-Order Replaceability in Multi-Agent Workflows

Abstract

Replacing an agent in an established multi-agent workflow is inherently context-dependent: the same agent may help in one workflow but hurt in another. This seemingly suggests that predicting the effect of a replacement requires modeling the workflow context in detail. We ask whether this complexity is actually necessary. Specifically, how much information is actually needed to predict the effect of an unseen agent replacement before execution? We find that Agent Replacement exhibits Low-Order Replaceability: most of its predictive value is captured by first-order Agent Performance and second-order Agent Relations learned from historical workflows. In a controlled sequential LLM-based multi-agent system, Agent Performance provides a transferable prediction baseline, while most finer-grained agent and contextual information adds limited value. Agent Relations provide the strongest additional signal, increasing the Pearson correlation between predicted and observed replacement effects from to . Moreover, only 9 of 90 candidate relations are identified as stable, yet they retain nearly the full predictive performance of the complete relation model. This low-order structure also translates into better replacement decisions. Replacements selected using Agent Performance increase the average success rate from to , while incorporating Agent Relations further increases it to . These results suggest that although replacement effects depend on workflow context, the predictive structure needed to guide replacement decisions can be substantially simpler than the workflow itself.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models, Multi-Agent Systems, Agentic Workflows, Agent Replacement, Replacement Prediction, Agent Relations

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_cpsaOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies whether the effect of replacing one agent in a multi-agent workflow can be predicted before running the modified workflow. In a controlled sequential system, the authors find that an agent’s historical performance provides a useful prediction baseline, while a small number of ordered pairwise relationships between agents add most of the remaining predictive value. They call this pattern low-order replaceability.

The authors validate the finding through more than 200,000 workflow executions, testing both predictions on unseen replacements and replacement choices on a separate evaluation set. Adding agent relations raises the correlation between predicted and observed effects from 0.552 to 0.643; nine selected relations retain nearly the performance of all 90. Using these signals to choose replacements increases average workflow success from 46.86% to 53.17%.

Critical strengths
  1. The paper separates model fitting, replacement prediction, and actual replacement decisions across different task sets. This makes the improvement in workflow success a meaningful result on unseen tasks. It shows that patterns learned from historical workflows can guide useful changes to new workflows, which is the paper’s most convincing contribution.

  2. The authors also take care to assess execution noise and check whether their findings hold under different analysis choices. These checks are particularly valuable for a paper built around statistical patterns. They make the results easier to assess and give a clear basis for addressing the remaining concerns.

Critical weaknesses
  1. The claim that low-order information is sufficient has not been tested against a model that can use the full workflow sequence. The reported comparisons mainly use additive models with hand-crafted features; even the positional model cannot learn interactions between agents. A sequence-aware predictor might capture information these models miss. Please compare against one interaction-capable predictor using the same data and splits, and estimate the prediction ceiling set by execution noise. This would show how much unexplained signal remains beyond the reported correlation of 0.643.

  2. The prediction results also lack uncertainty estimates. Several differences used to rank the models are small, including the correlations for richer task features, all pairwise relations, and the selected relations. With only 100 workflow seeds drawn from shared tasks, it is unclear whether those differences are reliable. Please report paired, task-clustered confidence intervals for differences in correlation and prediction error, especially between the selected-relation and full-relation models.

Questions for authors

The paper uses a single shared backbone in every setting, with one DeepSeek-V4-Flash row in Table 11 that has no confidence interval. Could you add one or two more backbones?

5 comments
AuthorsOpenReview ↗

Response to Reviewer cpsa (1/3): Summary of New Results and Revisions

Thank you very much for your careful and insightful review! You identified the decision gains on unseen tasks as the paper's most convincing contribution and noted our treatment of execution noise; this is very encouraging to us.

Your questions were a great inspiration to us, and we ran additional experiments and analyses. To save your time, we first summarize the most important new results:

Following your suggestion, we trained predictors that can model interactions and the full workflow sequence (XGBoost and MLP) on the same data and splits, and estimated the prediction ceiling set by execution noise. All hyper-parameters were selected by grouped cross-validation on the training tasks only. The results provide further evidence that replacement effects are low-order:

  • Noise ceiling: On the above-noise subset of MATH, the ceiling on r is 0.95 (0.90 on all 200 replacements). The original additive model's 0.643 explains 45% of the reliable variance.
  • The remaining signal is also low-order: Using only agents and ordered pairs, XGBoost explains 79% of the reliable variance (82% on all 200 replacements), and its gain comes from a saturation effect among solver agents.
  • The full sequence adds no information: The same MLP performs worse with the full sequence than with agents and ordered pairs alone.
  • Two new backbones: gpt-6-luna and gpt-6-sol, with CIs for all decision gains.

Your question about how much signal remains beyond 0.643 showed us the limits of the additive model, and also showed that the remaining signal lies in low-order information as well. Our central claim is that the predictable information lies in low-order signals, and the additive relation model is one simple, interpretable way to use them.

Your questionRevisionLocation
W1 Interaction- or sequence-aware predictorsComparison with XGBoost and MLP, including an MLP on the full sequence§5.3, Table 2, App. F.2–F.5
W1 Noise ceilingReliability, ceiling on r, and share of reliable variance explained by each modelApp. F.6, Table 19
W2 Paired, task-clustered CIsTable 1 reports paired Δr and CIs for each information type relative to Agent Performance; paired difference between Stable and Full RelationTable 1, §6.1
Q1 More backbones and CIsTwo new backbones, gpt-6-luna and gpt-6-sol; Table 11 adds sample sizes, CIs, and a pooled estimateApp. E.1, Table 11
PresentationUnified terminology; Figure 2 replaced by Table 1Throughout, Table 1

We answer your questions in turn in the following comments. All intervals are 95% task-cluster bootstrap CIs.

(Our answer to W1 follows in the next comment.)

AuthorsOpenReview ↗

Response to Reviewer cpsa (2/3): W1 (Interaction-Capable Predictors and Noise Ceiling)

W1: Comparison with predictors that can use the full sequence or interactions, and the prediction ceiling set by execution noise

On MATH, your expectation partly holds: predictors that model interactions do recover signal the additive model misses. This signal comes from two low-order inputs, agents and ordered pairs; adding the full sequence or positions brings no further information. All predictors use the same training tasks and test replacements as the original paper.

Predictor comparison. The table below matches Table 2 in the paper: r is reported on all replacements / the above-noise subset, and Δr is the paired difference from the additive model on all replacements.

PredictorInputMATH rMATH ΔrMMLU-Pro rMMLU-Pro Δr
Additive (Full Relation)agents + ordered pairs0.531 / 0.643—0.479 / 0.586—
XGBoostagents + ordered pairs0.819 / 0.849+0.289 [+0.183, +0.326]0.422 / 0.572−0.057 [−0.158, +0.071]
MLPagents + ordered pairs0.782 / 0.817+0.251 [+0.148, +0.294]0.531 / 0.639+0.052 [−0.039, +0.120]
MLPfull sequence0.687 / 0.743+0.156 [+0.063, +0.211]0.433 / 0.553−0.046 [−0.155, +0.102]

(MATH: 200 replacements, 100 above noise; MMLU-Pro: 100 replacements, 41 above noise.)

  • The full sequence adds no information in either setting: The same MLP performs worse with the full sequence than with agents and ordered pairs alone (MATH, all replacements: Δr −0.095 [−0.120, −0.047]; MMLU-Pro: 0.433 vs. 0.531).
  • Positions and interactions: You noted that the positional model cannot learn interactions. Giving XGBoost positions together with counts and pairs yields r = 0.818 / 0.850, the same as without positions (Δr −0.001 [−0.012, +0.010]) (App. F.3).
  • On MATH, the gain comes from a low-order solver saturation effect: The first solver-type agent matters most, and additional solvers add little. When interactions are allowed only among solver features, XGBoost retains 86% of its gain over the additive model; forbidding these interactions removes 59% of the gain (App. F.4). This structure can be expressed with agent counts and their pairwise combinations alone. Six of our nine stable relations are exactly the negative solver–solver relations, which approximate the same structure additively.
  • On MMLU-Pro: Replacement effects are noisier here, and the training data contain little learnable interaction; the flexible predictors perform on par with the additive model (App. F.5).

Noise ceiling. We estimate the reliability ρ of the observed effects by variance decomposition over three repeated runs; the ceiling on r is √ρ. Parentheses give the share of reliable variance explained by each model, r²/ρ (App. F.6, Table 19):

MATH all 200MATH above-noiseMMLU-Pro all 100MMLU-Pro above-noise
Reliability ρ0.816 [0.69, 0.88]0.908 [0.84, 0.94]0.476 [0.20, 0.63]0.798 [0.69, 0.87]
Ceiling √ρ0.900.950.690.89
Full Relation0.531 (35%)0.643 (45%)0.479 (48%)0.586 (43%)
Stable / Top-9 Relation0.540 (36%)0.641 (45%)0.467 (46%)0.637 (51%)
XGBoost (agents + pairs)0.819 (82%)0.849 (79%)0.422 (37%)0.572 (41%)
MLP (full sequence)0.687 (58%)0.743 (61%)0.433 (39%)0.553 (38%)
  • How much signal remains beyond 0.643: On the above-noise subset of MATH, 0.643 explains 45% of the reliable variance, leaving 55%. XGBoost, with the same low-order inputs, explains another 34 percentage points of it (45% → 79%), leaving 21%; the MLP on the full sequence reaches only 61%.
  • MMLU-Pro: The relation models explain 43–51%, and the flexible predictors do not differ significantly from them (all Δr CIs in Table 2 include 0).
  • Decisions still use the Stable Relation Model: Each of its terms corresponds to a specific agent or relation, so one can see directly how low-order signals drive replacement decisions. Its explained share is also more stable across the two settings (MATH 36%, MMLU-Pro 46%; XGBoost 82% and 37%).

(Answers to W2, Q1, and the presentation issues follow in the next comment.)

AuthorsOpenReview ↗

Response to Reviewer cpsa (3/3): W2, Q1, Scope, and Presentation

W2: Paired, task-clustered CIs for model differences

The 9 selected relations show no detectable difference from all 90 in r, MAE, or RMSE; the improvement of the relation model over Agent Performance is significant in r and RMSE.

Table 1 now reports paired Δr and CIs for each information type relative to Agent Performance, on both all 200 replacements and the above-noise subset. The bootstrap resamples tasks as clusters, which accounts for the correlation among workflows that share tasks. The differences you highlighted are below (MAE and RMSE are reductions in pp; positive is better):

ComparisonSubsetΔrMAE reductionRMSE reduction
Stable vs. Fullabove-noise−0.001 [−0.023, +0.022]−0.11 [−0.34, +0.12]−0.07 [−0.26, +0.16]
Stable vs. Fullall 200+0.009 [−0.014, +0.031]+0.25 [−0.03, +0.32]+0.14 [−0.05, +0.27]
Stable vs. APabove-noise+0.089 [+0.030, +0.130]+0.19 [−0.10, +0.64]+0.89 [+0.36, +1.21]
Stable vs. APall 200+0.105 [+0.043, +0.140]+0.00 [−0.24, +0.31]+0.48 [+0.11, +0.69]
Function-Type Richness vs. APabove-noise+0.065 [+0.030, +0.091]+0.07 [−0.04, +0.32]+0.50 [+0.25, +0.65]
Stable vs. Function-Type Richnessabove-noise+0.024 [−0.037, +0.076]
  • The 9 selected relations show no detectable difference from all 90: For all three metrics, the CIs of the differences include 0 on both subsets.
  • Relations significantly improve r and RMSE over Agent Performance. On all 200 replacements, MAE is unchanged: half of these replacements have effects within execution noise, and these near-zero replacements dominate the MAE.
  • Richer task features: Among Position, MATH Type, Agent Richness, Stage, Functional Composition, and Function-Type Richness, only Function-Type Richness improves significantly over Agent Performance, and it does not differ significantly from the Stable Relation Model.

Q1: Could you add one or two more backbones, and a CI for the DeepSeek-V4-Flash row?

We added two backbones, gpt-6-luna and gpt-6-sol. As with DeepSeek-V4-Flash, each backbone is evaluated on 20 OMNI-MATH test tasks × 10 workflows, with test tasks disjoint from training tasks; the models are estimated from 500 (DeepSeek-V4-Flash), 2,000 (gpt-6-luna), and 1,000 (gpt-6-sol) historical executions (App. E.1). Success-rate gains (pp):

BackboneAgent − No Repl.Relation − No Repl.Relation − Agent
DeepSeek-V4-Flash+3.5 [−2.5, +9.0]+4.5 [−0.5, +9.5]+1.00 [−4.50, +6.50]
gpt-6-luna+6.5 [+2.0, +11.5]+7.0 [+2.0, +12.0]+0.50 [−3.50, +4.00]
gpt-6-sol+6.0 [+1.0, +11.0]+7.5 [+3.5, +13.0]+1.50 [−2.00, +5.50]
  • On all three backbones, replacements chosen by both models raise the success rate; on the two new backbones, both gains have CIs that exclude 0. The Relation − Agent gain is positive on all three backbones.
  • Each backbone has only 200 test executions, so the Relation − Agent CI of a single setting is wide. Table 11 now reports sample sizes and CIs for all 8 settings: the gain is positive in all 8, there is no detectable heterogeneity across settings (τ² = 0), and the pooled gain is +1.19 pp [+0.61, +1.76], and still +0.92 pp [+0.17, +1.67] without the main experiment.

Scope: The new backbones test whether the conclusions hold across models. Within a workflow, agents still share one backbone; workflows that mix different models are left for future work.

Presentation: We unified the terminology (above-noise subset, Full / Stable Relation Model) and replaced the original Figure 2 with main-text Table 1, which lists the values and CIs for each information type directly.

Thank you again for your review! We hope these additions address your concerns, and we would be glad to discuss any further questions.

Reviewer_A3BmOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies whether the effect of replacing a single agent in a sequential multi-agent workflow can be predicted from historical executions. It identifies “Low-Order Replaceability”: agent-level performance and a small set of ordered pairwise relations provide useful predictive signals. The authors connect replacement prediction to executed decisions, increasing success rate from 46.86% to 53.17%. The problem is relevant, although the evidence supporting the breadth of the low-order claim could be stronger.

Critical strengths
  • The paper clearly formulates local agent replacement and connects historical effect estimation, prediction, and executed replacement decisions.

  • The large controlled execution study, disjoint task sets, repeated executions, and training-only relation selection strengthen the empirical evaluation.

  • Retaining only 9 of 90 candidate relations nearly matches the full relation model in predictive correlation (0.641 versus 0.643), providing useful evidence that pairwise predictive gains are concentrated.

  • The execution-based evaluation demonstrates practical value: relational modeling improves success rate over the Agent Performance baseline by 1.58 percentage points, with a task-cluster 95% confidence interval of [0.68, 2.50].

Critical weaknesses
  1. The results establish the practical usefulness of the tested low-order models, but do not yet establish that they capture most of the predictive information available to a suitably regularized richer predictor. The higher-order comparison adds all 720 ordered triples, whose weaker performance may reflect estimation difficulty, as the authors acknowledge. A regularized higher-order or full-sequence predictor trained on the same historical data, with model selection confined to training or development data, would provide a stronger test of the central claim.

  2. The headline prediction results emphasize an outcome-conditioned diagnostic subset. The main analysis retains 100 of 200 replacements based on their observed effects, using the same noisy measurements for selection and evaluation. Although this is disclosed and does not affect model fitting, these results do not directly characterize performance over the full random-replacement distribution. On all 200 replacements, the zero-change and Stable Relation models have nearly identical MAE (5.25 versus 5.24 percentage points). Relational information still improves RMSE and correlation over Agent Performance, so the full-sample results remain informative and should receive greater prominence, together with paired uncertainty estimates.

  3. The cross-setting evidence would benefit from clearer model-selection procedures and uncertainty estimates. In particular, the MMLU-Pro prediction experiment reports the “best observed Top-k” variant without explaining whether K was selected using a separate validation set. Several additional decision gains are small, including 0.16 and 0.56 percentage points, and are reported without confidence intervals. These results provide encouraging point estimates, but their statistical reliability remains unclear.

Presentation issues (minor):

  • Use consistent terminology for the “above-noise” and “Large-change 100” subsets, and for the relation-model variants.
  • Figure 2 would be easier to compare across methods if the complete numerical results for candidate information types were presented in a main-text table.
  • Briefly discussing the selected relation patterns in the main text would help readers interpret the relational signal.

Overall assessment: The paper addresses a worthwhile problem and presents useful evidence that compact historical signals can improve replacement decisions. My main reservations concern the support for the central low-order claim, the prominence of outcome-conditioned prediction results, and the uncertainty of the cross-setting findings. The conclusions are most directly supported for sequential, shared-context workflows with fixed role pools and single-point replacements. Stronger predictive comparisons and clearer full-sample and robustness evidence could materially change my assessment.

Questions for authors
  1. Would a suitably regularized richer predictor improve replacement prediction when trained on the same historical data?

  2. Can the authors report paired confidence intervals for model differences on the full replacement set?

  3. How was K selected in the MMLU-Pro experiment, and can uncertainty estimates be provided for the additional experiments?

  4. Beyond the reported standard-error and ranking checks, how stable are the selected relation sets and their predictive gains under task-level resampling of the training data?

6 comments
AuthorsOpenReview ↗

Response to Reviewer A3Bm (1/3): Summary of New Results and Revisions

Thank you very much for your careful and insightful review!

Your questions were a great inspiration to us. We ran additional experiments and analyses, and the results surprised us; we are eager to share them with you. To save your time, we first summarize the most important new results:

We trained three stronger predictors on the same historical data and compared them with our original additive model: an MLP on the full workflow sequence, an MLP on agents + ordered pairs, and XGBoost on agents + ordered pairs. All hyper-parameters were selected by grouped cross-validation on the training tasks only. On MATH, these predictors do outperform the additive model, and the results provide further evidence that replacement effects are low-order:

  • Using only the two low-order signals identified in our paper, XGBoost reaches r = 0.819 on all 200 replacements of MATH-486, close to the ceiling of 0.90 set by execution noise, and explains 82% of the reliable variance. Low-order signals therefore carry most of the predictable information in replacement effects, further confirming the low-order nature of agent replacement. Our central claim is that the predictable information lies in low-order signals, and the additive relation model is one simple, interpretable way to use them.
  • Given the full workflow sequence, the MLP can model higher-order positional effects and interactions, yet its r drops from 0.782 with low-order input only to 0.687 (Δr −0.095 [−0.120, −0.047]), also below XGBoost.

Your suggestion to compare against stronger and richer predictors showed us the limits of a simple additive model and further confirmed the low-order nature of agent replacement. Your attention to the full set of 200 replacements also made our conclusions more solid and reliable.

Your questionRevisionLocation
Q1 Stronger predictorsComparison with flexible predictors; regularization and training-size analysis of third-order relations; noise ceiling§5.3, Table 2, App. F
Q2 Full sample and paired CIsTable 1 reports all 200 replacements alongside the above-noise subset, with paired Δr and CIsTable 1, App. D.2
Q3 Choice of K and cross-setting CIsChoice of K explained; Table 11 adds sample sizes, CIs, a pooled estimate, and two new backbonesApp. D.4, Table 11
Q4 Relation stabilitySelection frequencies and predictive gains over 200 task-level bootstrap resamplesApp. C.2, Table 9
PresentationUnified terminology; Figure 2 replaced by Table 1; discussion of relation patternsThroughout, §6.1

We answer your questions in turn below.

(Answers to Q1 and Q2 follow in the next comment.)

AuthorsOpenReview ↗

Response to Reviewer A3Bm (2/3): Q1 and Q2

Q1: Would a suitably regularized richer predictor improve replacement prediction?

On MATH, yes, and the improvement comes from low-order information; on MMLU-Pro, the flexible predictors do not differ significantly from the additive model. The table below matches Table 2 in the paper: r is reported on all replacements / the above-noise subset, and Δr is the paired difference from the additive model on all replacements.

PredictorInputMATH rMATH ΔrMMLU-Pro rMMLU-Pro Δr
Additive (Full Relation)agents + ordered pairs0.531 / 0.643—0.479 / 0.586—
XGBoostagents + ordered pairs0.819 / 0.849+0.289 [+0.183, +0.326]0.422 / 0.572−0.057 [−0.158, +0.071]
MLPagents + ordered pairs0.782 / 0.817+0.251 [+0.148, +0.294]0.531 / 0.639+0.052 [−0.039, +0.120]
MLPfull sequence0.687 / 0.743+0.156 [+0.063, +0.211]0.433 / 0.553−0.046 [−0.155, +0.102]
Noise ceiling √ρ—0.90 / 0.950.69 / 0.89

(MATH: 200 replacements, 100 above noise; MMLU-Pro: 100 replacements, 41 above noise.)

  • The full sequence adds no information in either setting: The same MLP performs worse with the full sequence than with agents and ordered pairs alone (MATH, all replacements: Δr −0.095 [−0.120, −0.047]; MMLU-Pro: 0.433 vs. 0.531). Adding positions likewise leaves XGBoost unchanged (Δr −0.001 [−0.012, +0.010]) (App. F.3).
  • On MATH, the gain comes from a low-order solver saturation effect: The first solver-type agent matters most, and additional solvers add little. When interactions are allowed only among solver features, XGBoost retains 86% of its gain over the additive model; forbidding these interactions removes 59% of the gain (App. F.4). This structure can be expressed with agent counts and their pairwise combinations alone. Six of our nine stable relations are exactly the negative solver–solver relations, which approximate the same structure additively.
  • On MMLU-Pro: Replacement effects are noisier here (reliability 0.476 vs. 0.816 on MATH); the cross-validated log loss of XGBoost changes by less than 0.0002 from depth 1 to depth 3; and the role pool has only two solvers, with a no-solver coefficient of −0.26 (−1.40 on MATH). Here, the flexible predictors perform on par with the additive model (App. F.5).
  • Third-order relations: With the L2 strength selected by cross-validation, adding all 720 ordered triples gives r = 0.638 on the above-noise subset, compared with 0.643 for pairs alone (Δr −0.005 [−0.037, +0.028]). Without regularization, the deficit of the triple model shrinks as the training set grows from 57 to 229 tasks (held-out log-loss gap 0.102 → 0.016), so the deficit in the original paper mainly reflects estimation difficulty, as you suggested. At every regularization strength and training size, the triple model does not exceed the pairwise model (App. F.1).
  • Decisions still use the Stable Relation Model: Each of its terms corresponds to a specific agent or relation, so one can see directly how low-order signals drive replacement decisions. Its explained share is also more stable across the two settings (MATH 36%, MMLU-Pro 46%; XGBoost 82% and 37%) (App. F.6).

Q2: Can the authors report paired confidence intervals for model differences on the full replacement set?

We replaced the original Figure 2 with Table 1, which now reports all 200 replacements alongside the above-noise subset, with paired Δr and CIs relative to Agent Performance. On all 200 replacements, Stable Relation vs. Agent Performance:

  • Δr +0.105 [+0.043, +0.140]
  • RMSE reduced by 0.48 pp [0.11, 0.69]
  • MAE unchanged (+0.00 [−0.24, +0.31]) and nearly identical to the zero-change model (5.24 vs. 5.25), as you noted. Half of the 200 replacements have effects within execution noise, and these near-zero replacements dominate the MAE.

To address the use of the same noisy measurements for selection and evaluation, we selected the above-noise subset by observed effect in one repeat and evaluated on the other two repeats. Stable Relation vs. Agent Performance then gives Δr +0.127 [+0.062, +0.168] and reduces MAE by 0.38 pp [0.08, 0.67]; its MAE is 6.67 pp, below the 7.53 pp of the zero-change model (App. D.2).

(Answers to Q3, Q4, and the presentation issues follow in the next comment.)

AuthorsOpenReview ↗

Response to Reviewer A3Bm (3/3): Q3, Q4, Presentation, and Scope

Q3: How was K selected in the MMLU-Pro experiment, and can uncertainty estimates be provided for the additional experiments?

Choice of K: Thank you for pointing this out. The submitted version reported the best K observed on the test set. In the revision, we fix K = 9, the number of stable relations selected on training data in the main experiment, without using any information from the MMLU-Pro test set. This value coincides with the original choice, so the reported values are unchanged (App. D.4, Table 10). Our conclusions do not depend on K: across all K, r ranges from 0.572 to 0.637, and the differences are not significant. The decision results do not depend on this choice either: excluding MMLU-Pro, the pooled decision gain is +1.53 pp [+0.80, +2.25].

CIs for decision gains: Table 11 now reports the number of test executions and the CI of Relation − Agent for each setting, and adds two new backbones, gpt-6-luna and gpt-6-sol:

SettingTest executions (workflows × tasks × runs)Relation − Agent (pp)
Main100 × 50 × 3+1.58 [+0.68, +2.50]
L = 1225 × 50 × 1+3.54 [+0.99, +6.16]
L = 425 × 50 × 1+1.04 [−1.36, +3.76]
5 agents25 × 50 × 1+0.56 [−1.68, +2.88]
DeepSeek-V4-Flash10 × 20 × 1+1.00 [−4.50, +6.50]
gpt-6-luna10 × 20 × 1+0.50 [−3.50, +4.00]
gpt-6-sol10 × 20 × 1+1.50 [−2.00, +5.50]
MMLU-Pro100 × 50 × 1+0.60 [−0.34, +1.56]
  • The Relation − Agent gain is positive in all 8 settings. Six settings have individual CIs that include 0: the five extended settings have only 200–1,250 test executions, and on MMLU-Pro the gain itself is small. There is no detectable heterogeneity across settings (τ² = 0), so the settings can be pooled: the pooled gain is +1.19 pp [+0.61, +1.76], and still +0.92 pp [+0.17, +1.67] without the main experiment, showing that the gain is stable across settings.
  • Correction: The 0.16 for MMLU-Pro in the submitted version was computed before the last 100 of the 5,000 cells had completed; with the complete data, it is +0.60.

Q4: Beyond the reported checks, how stable are the selected relation sets and their predictive gains under task-level resampling of the training data?

We drew 200 task-level bootstrap resamples of the 286 training tasks and reran the full Cluster-FDR selection on each:

  • The 9 selected relations are re-selected in 70–100% of resamples, and the 6 solver–solver relations in at least 86%. The most frequent other relation reaches 53%, and all remaining ones at most 37%.
  • With these 9 relations fixed, the median Δr vs. Agent Performance is +0.09 [+0.06, +0.13], positive in all 200 resamples. When the relations are reselected and refit in each resample, the median Δr is +0.080 [+0.018, +0.144], positive in 99% of resamples (App. C.2, Table 9).

Presentation: We have adopted all three suggestions.

  • Terminology is unified as the above-noise subset, the Full Relation Model (90 relations), and the Stable Relation Model (9 relations).
  • Figure 2 is replaced by main-text Table 1, which lists MAE, RMSE, r, and paired CIs for each information type.
  • §6.1 now discusses the relation patterns: six negative relations cover both orders of every pair among the three solvers, so once one solver is present the others are largely redundant; three positive relations place a reflection or compression agent upstream. This pattern matches the source of the XGBoost gain in Q1.

Scope: We agree with your summary. The Discussion states that our conclusions apply to sequential, shared-context workflows with fixed role pools and single-point replacement.

Thank you again for your review! We hope these additions address your concerns, and we would be glad to discuss any further questions.

Reviewer_487COpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates whether the performance impact of replacing an agent in an existing multi-agent workflow can be predicted without executing the modified workflow. The authors introduce Low-Order Replaceability, hypothesizing that replacement effects can be largely predicted using Agent Performance and Agent Relations.

Critical strengths
  1. This paper addresses a practical problem in multi-agent workflow optimization: predicting the effects of local agent replacement without expensive execution. The finding that simple agent-level statistics and sparse pairwise relations capture much of the predictive information is interesting and could motivate more efficient workflow optimization methods.
  2. This paper evaluates different information sources, including agent occurrence counts, position, task properties, workflow composition, and pairwise relations. It employs disjoint task splits, repeated workflow executions, noise analysis, and cluster-aware statistical tests. Experiments on sequential LLM-based multi-agent workflows show that incorporating pairwise relations improves Pearson correlation. The proposed approach also improves actual workflow success, demonstrating the practical utility of historical performance signals for agent replacement.
  3. This work demonstrates that their predictions translate into improved replacement decisions. The Agent Relation Model increases success rates, outperforming the Agent Performance baseline. Additional experiments across different workflow lengths, agent pools, models, and datasets further support the robustness of the findings.
Critical weaknesses
  1. The experiments primarily consider fixed-length, sequential workflows with shared context and single-agent replacement. Real-world multi-agent systems frequently involve dynamic routing, branching execution, heterogeneous models, and complex communication structures. Furthermore, the agents in the main experiments share the same backbone model and differ mainly in their functional configurations. Consequently, it remains unclear whether Low-Order Replaceability holds in more realistic and heterogeneous agent architectures.
  2. The central conclusion that replacement effects exhibit a low-order structure is supported mainly by comparisons with relatively simple statistical models. The authors report that including third-order relations reduces predictive performance, but this could result from increased dimensionality, insufficient training data, or inadequate regularization rather than an absence of meaningful higher-order interactions. Comparisons against stronger nonlinear predictors would help establish whether low-order information is genuinely sufficient or merely better suited to the available data budget.
  3. Although the proposed approach improves upon unreplaced workflows and the Agent Performance baseline, the paper does not directly compare replacement decisions against alternative optimization strategies, such as random replacement, greedy local search, or budget-matched execution-based selection. Moreover, constructing the historical performance estimates requires substantial workflow execution data. Without explicit analysis of training-data requirements, execution costs, and performance gains under fixed computational budgets, the claimed practical efficiency advantages remain insufficiently established. //
Questions for authors

How to address the concerns mentioned in the Weaknesses section.

6 comments
AuthorsOpenReview ↗

Response to Reviewer 487C (1/3): Summary of New Results, Revisions, and W1

Thank you for your careful and professional review! We are greatly encouraged that you recognized the practical significance of the problem and our experimental design, and that predictions translate into better replacement decisions.

Your questions were a great inspiration to us, and we ran additional experiments and analyses. To save your time, we first summarize the most important new results:

Stronger nonlinear predictors (W2): We trained XGBoost and MLPs on the same historical data, with all hyper-parameters selected by grouped cross-validation on the training tasks only. The results provide further evidence that replacement effects are low-order:

  • Using only two low-order signals, agents and ordered pairs, XGBoost reaches r = 0.819 on all 200 replacements of MATH, close to the ceiling of 0.90 set by execution noise, and explains 82% of the reliable variance.
  • Given the full workflow sequence, the MLP's r drops from 0.782 with low-order input only to 0.687.

Decision baselines and cost (W3):

  • Random replacement barely changes the success rate (+0.22 pp); the Stable Relation Model exceeds it by 6.09 pp.
  • Executing all 72 candidate replacements and then selecting the best reaches a success rate of 63.4%; model-based selection requires no additional execution, reaches 62.0%, and attains 92% of the gain of execution-based selection.

Across models (W1): We added two backbones, gpt-6-luna and gpt-6-sol. The decision gain from relations is positive in all 8 settings, with a pooled gain of +1.19 pp [+0.61, +1.76].

Your questions about stronger predictors and decision baselines showed us the limits of a simple additive model and made the practical value of the decision experiments clearer.

Your questionRevisionLocation
W1 Scope and heterogeneous modelsAdded gpt-6-luna and gpt-6-sol; Table 11 adds sample sizes, CIs, and a pooled estimate; Discussion states the scopeApp. E.1, Table 11, §7
W2 Stronger nonlinear predictors and third-order relationsComparison with XGBoost and MLPs (incl. full sequence); regularization and training-size analysis of third-order relations; noise ceiling§5.3, Table 2, App. F
W3 Comparison with random replacementTable 3 adds random replacement§6.2, Table 3
W3 Execution-based selection, training data, and costComparison with execution-based selection; learning curve and execution costThis response

We answer your questions in turn below.


W1: Does low-order replaceability hold in more realistic, heterogeneous systems?

We tested the conclusion along four dimensions: backbone, dataset, workflow length, and role pool. The decision gain from relations is positive in all 8 settings.

  • New backbones: Beyond the main experiment, we repeated the full pipeline (model estimation, replacement selection, and execution-based evaluation) with three backbones: DeepSeek-V4-Flash, gpt-6-luna, and gpt-6-sol. On all three, the replacements selected by both models increase the success rate (Agent Performance +3.5 to +6.5 pp, Stable Relation +4.5 to +7.5 pp), and the Relation − Agent gain is positive (App. E.1).
  • Pooling across settings: Table 11 now reports the number of test executions and the CI for all 8 settings. The five extended settings have only 200–1,250 test executions each, so individual CIs are wide. There is no detectable heterogeneity across settings (τ² = 0); the pooled gain is +1.19 pp [+0.61, +1.76], and +0.92 pp [+0.17, +1.67] without the main experiment.
  • Scope: The Discussion states that our conclusions apply to sequential, shared-context workflows with fixed role pools and single-point replacement, and lists dynamic routing, richer communication structures, and multi-point replacement as future directions. In this setting, agents within a workflow share one backbone and differ in functional configuration; the new backbones test whether the conclusions hold across models. Heterogeneous systems that mix different models within one workflow are the next setting we plan to test.

(The answer to W2 follows in the next comment.)

AuthorsOpenReview ↗

Response to Reviewer 487C (2/3): W2

W2: Is low-order information truly sufficient, or merely better suited to the available data?

We examined this question from two directions: the third-order model under regularization and more training data, and stronger nonlinear predictors. Both show that the predictable information lies mainly in low-order signals.

Third-order relations: With the L2 strength selected by cross-validation, adding all 720 ordered triples gives r = 0.638 on the above-noise subset, compared with 0.643 for pairs alone (Δr −0.005 [−0.037, +0.028]). Without regularization, the deficit of the triple model shrinks as the training set grows from 57 to 229 tasks (held-out log-loss gap 0.102 → 0.016), so the deficit in the original paper mainly reflects estimation difficulty, as you suggested. At every regularization strength and training size, the triple model does not exceed the pairwise model (App. F.1).

Stronger nonlinear predictors: The table below matches Table 2 in the paper: r is reported on all replacements / the above-noise subset, and Δr is the paired difference from the additive model on all replacements.

PredictorInputMATH rMATH ΔrMMLU-Pro rMMLU-Pro Δr
Additive (Full Relation)agents + ordered pairs0.531 / 0.643—0.479 / 0.586—
XGBoostagents + ordered pairs0.819 / 0.849+0.289 [+0.183, +0.326]0.422 / 0.572−0.057 [−0.158, +0.071]
MLPagents + ordered pairs0.782 / 0.817+0.251 [+0.148, +0.294]0.531 / 0.639+0.052 [−0.039, +0.120]
MLPfull sequence0.687 / 0.743+0.156 [+0.063, +0.211]0.433 / 0.553−0.046 [−0.155, +0.102]
Noise ceiling √ρ—0.90 / 0.950.69 / 0.89

(MATH: 200 replacements, 100 above noise; MMLU-Pro: 100 replacements, 41 above noise.)

  • The full sequence adds no information: The same MLP performs worse with the full sequence than with agents and ordered pairs alone in both settings (MATH, all replacements: Δr −0.095 [−0.120, −0.047]; MMLU-Pro: 0.433 vs. 0.531). Adding positions likewise leaves XGBoost unchanged (Δr −0.001 [−0.012, +0.010]) (App. F.3).
  • On MATH, the gain comes from a low-order solver saturation effect: The first solver-type agent matters most, and additional solvers add little. When interactions are allowed only among solver features, XGBoost retains 86% of its gain over the additive model; forbidding these interactions removes 59% of the gain (App. F.4). This structure can be expressed with agent counts and their pairwise combinations alone. Six of our nine stable relations are exactly the negative solver–solver relations, which approximate the same structure additively.
  • On MMLU-Pro: Replacement effects are noisier here (reliability 0.476 vs. 0.816 on MATH), and the flexible predictors do not differ significantly from the additive model (App. F.5).
  • Decisions still use the Stable Relation Model: Each of its terms corresponds to a specific agent or relation, so one can see directly how low-order signals drive replacement decisions. Its explained share is also more stable across the two settings (MATH 36%, MMLU-Pro 46%; XGBoost 82% and 37%) (App. F.6).

(The answer to W3 follows in the next comment.)

AuthorsOpenReview ↗

Response to Reviewer 487C (3/3): W3

W3: Comparison with other optimization strategies, training-data requirements, and execution cost

Random replacement yields almost no gain; model-based selection, without executing any candidate, reaches a success rate comparable to execution-based selection.

Random replacement (§6.2, Table 3): On the same 100 workflows, randomly replacing the agent at one position changes the success rate from 46.86% to 47.08% (+0.22 pp [−0.77, +1.26]). The Stable Relation Model exceeds random replacement by 6.09 pp [4.31, 7.95].

Execution-based selection (one step of greedy local search): Under single-point replacement, a workflow has 72 candidate replacements (8 positions × 9 candidate agents), and one step of greedy local search executes all candidates and keeps the best one. We ran this selection on 5 workflows from the main experiment with the same backbone, using the 5 tasks whose original success rate in the main experiment is 40–60%, since such tasks best discriminate between candidates. Each candidate was executed twice on each task. Execution-based selection picks the best candidate on the 5 executions of the first repeat and is evaluated on the second repeat; we then swap the two repeats and average. The replacement selected by the model is also one of these 72 candidates and is evaluated on the same executions:

StrategySuccess rate (%)vs. no replacement (pp)
No replacement46.3—
Execution-based selection63.4+17.1
Stable Relation62.0+15.7
  • Model-based selection attains 92% of the gain of execution-based selection. The difference between Stable Relation and execution-based selection is −1.4 pp (workflow-level bootstrap CI [−30.5, +20.8]); Stable Relation is better in 3 of the 5 workflows.
  • Execution-based selection is affected by execution noise: each candidate has only 5 executions for selection, several candidates often tie for first in the selection round (up to 10), and the selected candidate regresses on new executions. The model is estimated from historical executions on 286 training tasks and needs no execution of candidates for a new workflow.

Training-data requirements and execution cost:

  • Cost: The model uses 28,600 historical executions (286 training tasks × 100 workflows), averaging 85 s per execution. Once trained, it selects replacements for a new workflow without any execution, whereas execution-based selection must execute all 72 candidates for every new workflow.
  • Learning curve: We subsampled the training tasks at each proportion with 10 repetitions; the table reports the mean r over all 200 replacements:
Training tasksFull RelationStable Relation (reselected each time)
57 (20%)0.3960.367
100 (35%)0.4720.448
143 (50%)0.4900.485
214 (75%)0.5110.537
286 (100%)0.5310.540
  • The r of both relation models increases steadily with more training tasks; with half of the training tasks (143), the Stable Relation Model already reaches 90% of its full-data r.
  • On the new backbones, the models are estimated from only 500–2,000 historical executions, and the replacements selected by the Stable Relation Model still increase the success rate by 4.5–7.5 pp (App. E.1).

Thank you again for your review! We hope these additions address your concerns, and we would be glad to discuss any further questions.

Comments on the paper

1 comment

Dear Reviewers,

The authors have submitted their responses to the questions and concerns raised in the reviews. Please review their responses and provide any further comments or clarifications, if applicable.

Thank you for your time and consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.