ProtocolBench: Which LLM MultiAgent Protocol to Choose?

Hongyi Du, Jiaqi Su, Jisen Li, Lijie Ding, Yingxuan Yang, Peixuan Han, Xiangru Tang, Kunlun Zhu, Jiaxuan You
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:26649-26695, 2026.

Abstract

As large-scale multi-agent systems evolve, the communication protocol layer has become a critical yet under-evaluated factor shaping performance and reliability. Despite the existence of diverse protocols (A2A, ACP, ANP, Agora, etc.), the selection of them is often intuition-driven and lacks standardized guidance. We introduce ProtocolBench, a benchmark that systematically compares agent protocols along four measurable axes: task success, end-to-end latency, message or byte overhead, and robustness under failures. On ProtocolBench, the choice of protocol significantly influences system behavior. In the Streaming Queue scenario, overall completion time varies by up to 36.5% across protocols, and mean end-to-end latency differs by 3.48 s. Under Fail-Storm Recovery, resilience also differs consistently across protocols. Beyond evaluation, we present ProtocolRouter, a lightweight constraint-aware protocol router that selects per-scenario (or per-module) protocols from requirement and runtime signals. ProtocolRouter reduces Fail-Storm recovery time by up to 18.1% versus the best single-protocol baseline and achieves scenario-specific gains such as higher success in GAIA, while exposing trade-offs across other metrics. We also release ProtocolRouterBench to standardize constrained protocol-selection evaluation and improve reliability at scale.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-du26l, title = {{P}rotocol{B}ench: Which {LLM} {M}ulti{A}gent Protocol to Choose?}, author = {Du, Hongyi and Su, Jiaqi and Li, Jisen and Ding, Lijie and Yang, Yingxuan and Han, Peixuan and Tang, Xiangru and Zhu, Kunlun and You, Jiaxuan}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {26649--26695}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/du26l/du26l.pdf}, url = {https://proceedings.mlr.press/v306/du26l.html}, abstract = {As large-scale multi-agent systems evolve, the communication protocol layer has become a critical yet under-evaluated factor shaping performance and reliability. Despite the existence of diverse protocols (A2A, ACP, ANP, Agora, etc.), the selection of them is often intuition-driven and lacks standardized guidance. We introduce ProtocolBench, a benchmark that systematically compares agent protocols along four measurable axes: task success, end-to-end latency, message or byte overhead, and robustness under failures. On ProtocolBench, the choice of protocol significantly influences system behavior. In the Streaming Queue scenario, overall completion time varies by up to 36.5% across protocols, and mean end-to-end latency differs by 3.48 s. Under Fail-Storm Recovery, resilience also differs consistently across protocols. Beyond evaluation, we present ProtocolRouter, a lightweight constraint-aware protocol router that selects per-scenario (or per-module) protocols from requirement and runtime signals. ProtocolRouter reduces Fail-Storm recovery time by up to 18.1% versus the best single-protocol baseline and achieves scenario-specific gains such as higher success in GAIA, while exposing trade-offs across other metrics. We also release ProtocolRouterBench to standardize constrained protocol-selection evaluation and improve reliability at scale.} }
Endnote
%0 Conference Paper %T ProtocolBench: Which LLM MultiAgent Protocol to Choose? %A Hongyi Du %A Jiaqi Su %A Jisen Li %A Lijie Ding %A Yingxuan Yang %A Peixuan Han %A Xiangru Tang %A Kunlun Zhu %A Jiaxuan You %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-du26l %I PMLR %P 26649--26695 %U https://proceedings.mlr.press/v306/du26l.html %V 306 %X As large-scale multi-agent systems evolve, the communication protocol layer has become a critical yet under-evaluated factor shaping performance and reliability. Despite the existence of diverse protocols (A2A, ACP, ANP, Agora, etc.), the selection of them is often intuition-driven and lacks standardized guidance. We introduce ProtocolBench, a benchmark that systematically compares agent protocols along four measurable axes: task success, end-to-end latency, message or byte overhead, and robustness under failures. On ProtocolBench, the choice of protocol significantly influences system behavior. In the Streaming Queue scenario, overall completion time varies by up to 36.5% across protocols, and mean end-to-end latency differs by 3.48 s. Under Fail-Storm Recovery, resilience also differs consistently across protocols. Beyond evaluation, we present ProtocolRouter, a lightweight constraint-aware protocol router that selects per-scenario (or per-module) protocols from requirement and runtime signals. ProtocolRouter reduces Fail-Storm recovery time by up to 18.1% versus the best single-protocol baseline and achieves scenario-specific gains such as higher success in GAIA, while exposing trade-offs across other metrics. We also release ProtocolRouterBench to standardize constrained protocol-selection evaluation and improve reliability at scale.
APA
Du, H., Su, J., Li, J., Ding, L., Yang, Y., Han, P., Tang, X., Zhu, K. & You, J.. (2026). ProtocolBench: Which LLM MultiAgent Protocol to Choose?. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:26649-26695 Available from https://proceedings.mlr.press/v306/du26l.html.

Related Material