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

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 $0.552$ to $0.643$. 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 $46.86\%$ to $51.59\%$, while incorporating Agent Relations further increases it to $53.17\%$. 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.