Elamur Research⌕
☰
home / papers / 2026 / RouterHGC: Optimized Router for LLM-based Multi-Agent Systems via Heterogeneous Graph Contrastive Learning

RouterHGC: Optimized Router for LLM-based Multi-Agent Systems via Heterogeneous Graph Contrastive Learning

Paper · 2026 · Yitao Xiao, Shaoyong Guo, Guoming Yang et al.

Summary

Routing in LLM-based multi-agent systems (MAS) means choosing, for each incoming query, a collaboration mode, a set of agent roles, and the LLMs behind them, so that answers stay accurate without excessive cost. Most earlier routers select only one model. The single prior multi-agent router makes its choices in a cascade, which can produce short-sighted configurations. RouterHGC instead treats queries, collaboration modes (e.g., Chain, Debate), roles and LLMs as four node types in one heterogeneous graph, linked by query–pattern, pattern–role and role–LLM edges. A heterogeneous GNN passes messages across these node types. Routing then becomes edge-weight prediction followed by extraction of the best-scoring subgraph. Training combines two terms: a graph-level contrastive loss that moves each query's graph toward strong configurations and away from weak or expensive ones, and an edge-level loss that calibrates individual selections. On five public benchmarks covering math reasoning, code generation and knowledge QA, the router beats both the strongest single LLM and earlier routers while lowering inference cost. This makes adaptive multi-agent services cheaper to run.

Key points

  • Node features come from BERT encodings. Queries and role prompts are encoded directly. Collaboration patterns and LLMs are first described by an LLM (e.g., Gemini 2.5 Pro), and the LLM descriptions include cost statistics.
  • The paper reports accuracy gains of 0.8%–6.17% over baselines and an inference-cost reduction of 27.40%, with MATH and HotpotQA cited as the main examples.
  • The full model reaches 72.15% on MATH and 78.88% on HotpotQA. Ablations show the following drops on MATH / HotpotQA:
    • without the global contrastive loss: 4.94 / 7.56 points;
    • without both contrastive losses: 10.29 / 12.95 points;
    • without the heterogeneous GNN: 19.67 / 21.17 points.
  • In the sensitivity analysis, a cost-penalty coefficient β = 0.6 cuts cost by 46.4% while lowering MATH accuracy by only 0.7%. The best global-to-local loss weighting is 2:1.
  • In the limitations, the authors note that tools are not yet modeled as routable nodes; extending the graph to tool nodes is planned.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Beijing University of Posts and TelecommunicationsBeijing · China78 works · 33,365 citations🔬State Key Laboratory of Networking and Switching TechnologyBeijing · China9 works · 273 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

Cite

Cite as Yitao Xiao, Shaoyong Guo, Guoming Yang, Qingnan Wang, Yinlin Ren, Xuesong Qiu and Qi Feng. 2026. RouterHGC: Optimized Router for LLM-based Multi-Agent Systems via Heterogeneous Graph Contrastive Learning. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.1589

@inproceedings{xiao2026routerhgc,
  title = {{RouterHGC: Optimized Router for LLM-based Multi-Agent Systems via Heterogeneous Graph Contrastive Learning}},
  author = {Yitao Xiao, Shaoyong Guo, Guoming Yang, Qingnan Wang, Yinlin Ren, Xuesong Qiu and Qi Feng},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.1589},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.1589}
}

References

58 references, 22 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Tomas Gavenciak, The Anh Han, Edward Hughes, Vojtech Kovarík, Jan Kulveit, Joel Z. Leibo, Caspar Oesterheld, Christian Schröder de Witt, Nisarg Shah, Michael P. Wellman, and 25 others. 2025. Multi-agent risks from advanced AI. preprint, abs/2502.14143. — [arXiv:2502.14143](https://arxiv.org/abs/2502.14143) find
  2. Lingjiao Chen, Matei Zaharia, and James Zou. 2023a. Frugalgpt: How to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.05176.
  3. Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Pondé de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, and 39 others. 202… — Evaluating Large Language Models Trained on Code
  4. Mengru Chen, Chao Huang, Lianghao Xia, Wei Wei, Yong Xu, and Ronghua Luo. 2023b. Heterogeneous graph contrastive learning for recommendation. In Proceedings of the sixteenth ACM international conference on web search and data mining, pages 544– 552. find
  5. Shuhao Chen, Weisen Jiang, Baijiong Lin, James Kwok, and Yu Zhang. 2024. Routerdc: Query-based router by dual contrastive learning for assembling large language models. Advances in Neural Information Processing Systems, 37:66305–66328. find
  6. Dujian Ding, Ankur Mallick, Chi Wang, Robert Sim, Subhabrata Mukherjee, Victor Ruhle, Laks VS Lakshmanan, and Ahmed Hassan Awadallah. 2024. Hybrid llm: Cost-efficient and quality-aware query routing. arXiv preprint arXiv:2404.14618.
  7. Yanhao Fan, Che Zhang, Xiaowen Hu, Zhijian Huang, Jiameng Xue, and Lei Deng. 2024. Sgcldga: unveiling drug–gene associations through simple graph contrastive learning. Briefings in Bioinformatics, 25(3):bbae231. find
  8. Tao Feng, Yanzhen Shen, and Jiaxuan You. 2025. Graphrouter: A graph-based router for LLM selections. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net. find
  9. Yao Fu, Hao Peng, Ashish Sabharwal, Peter Clark, and Tushar Khot. 2023. Complexity-based prompting for multi-step reasoning. In 11th International Conference on Learning Representations, ICLR 2023.
  10. Zihao Gao, Huifang Ma, Xiaohui Zhang, Yike Wang, and Zheyu Wu. 2023. Similarity measures-based graph co-contrastive learning for drug–disease association prediction. Bioinformatics, 39(6):btad357. find
  11. Taicheng Guo, Xiuying Chen, Yaqi Wang, Ruidi Chang, Shichao Pei, Nitesh V Chawla, Olaf Wiest, and Xiangliang Zhang. 2024. Large language model based multi-agents: A survey of progress and challenges. arXiv preprint arXiv:2402.01680.
  12. Lewis Hammond, Alan Chan, Jesse Clifton, Jason Hoelscher-Obermaier, Akbir Khan, Euan McLean, Chandler Smith, Wolfram Barfuss, Jakob N. Foerster, Wei He, Guohao Sun, Jinhu Lu, and Xiu Susie Fang. 2023. Candidate-aware graph contrastive learning for recommendation. In Proceedings of the 46th internati… find
  13. Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. 2021. Measuring mathematical problem solving with the math dataset. NeurIPS.
  14. Bin Lei, Yi Zhang, Shan Zuo, Ali Payani, and Caiwen Ding. 2024. Macm: Utilizing a multi-agent system for condition mining in solving complex mathematical problems. Advances in Neural Information Processing Systems, 37:53418–53437. find
  15. Pierre Lepagnol, Thomas Gerald, Sahar Ghannay, Christophe Servan, and Sophie Rosset. 2024. Small language models are good too: An empirical study of zero-shot classification. arXiv preprint arXiv:2404.11122. find
  16. Haonan Li, Yixuan Zhang, Fajri Koto, Yifei Yang, Hai Zhao, Yeyun Gong, Nan Duan, and Timothy Baldwin. 2023. Cmmlu: Measuring massive multitask language understanding in chinese. Preprint, arXiv:2306.09212.
  17. Shuangli Li, Jingbo Zhou, Tong Xu, Dejing Dou, and Hui Xiong. 2022. Geomgcl: Geometric graph contrastive learning for molecular property prediction. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pages 4541–4549. find
  18. Tian Liang, Zhiwei He, Wenxiang Jiao, Xing Wang, Yan Wang, Rui Wang, Yujiu Yang, Shuming Shi, and Zhaopeng Tu. 2024. Encouraging divergent thinking in large language models through multi-agent debate. In EMNLP.
  19. Feng Lin, Dong Jae Kim, and Tse-Hsun Chen. 2025. SOEN-101: code generation by emulating software process models using large language model agents. In 47th IEEE/ACM International Conference on Software Engineering, ICSE 2025, Ottawa, ON, Canada, April 26 - May 6, 2025, pages 1527–1539. IEEE. find
  20. Zijun Liu, Yanzhe Zhang, Peng Li, Yang Liu, and Diyi Yang. 2024. A dynamic llm-powered agent network for task-oriented agent collaboration. In First Conference on Language Modeling.
  21. Keming Lu, Hongyi Yuan, Runji Lin, Junyang Lin, Zheng Yuan, Chang Zhou, and Jingren Zhou. 2023. Routing to the expert: Efficient reward-guided ensemble of large language models. arXiv preprint arXiv:2311.08692.
  22. Guanghui Ma, Chunming Hu, Ling Ge, Junfan Chen, Hong Zhang, and Richong Zhang. 2022a. Towards robust false information detection on social networks with contrastive learning. In Proceedings of the 31st ACM international conference on information & knowledge management, pages 1441–1450. find
  23. Guanghui Ma, Chunming Hu, Ling Ge, and Hong Zhang. 2022b. Open-topic false information detection on social networks with contrastive adversarial learning. In Proceedings of the 2022 conference on empirical methods in natural language processing, pages 2911–2923. find
  24. Kai Mei, Wujiang Xu, Shuhang Lin, and Yongfeng Zhang. 2025. Omnirouter: Budget and performance controllable multi-llm routing. arXiv preprint arXiv:2502.20576. — [arXiv:2502.20576](https://arxiv.org/abs/2502.20576) find
  25. Alireza Mohammadshahi, Arshad Rafiq Shaikh, and Majid Yazdani. 2024. Routoo: Learning to route to large language models effectively. arXiv preprint arXiv:2401.13979. — [arXiv:2401.13979](https://arxiv.org/abs/2401.13979) find
  26. Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E Gonzalez, M Waleed Kadous, and Ion Stoica. 2024. Routellm: Learning to route llms with preference data. arXiv preprint arXiv:2406.18665.
  27. Yinghui Pan, Fanke Chen, Biyang Ma, Yifeng Zeng, and Prashant Doshi. 2025. Model-based individual learning for competitive agents. find
  28. Chen Qian, Zihao Xie, YiFei Wang, Wei Liu, Kunlun Zhu, Hanchen Xia, Yufan Dang, Zhuoyun Du, Weize Chen, Cheng Yang, Zhiyuan Liu, and Maosong Sun. 2025. Scaling large language model-based multi-agent collaboration. In The Thirteenth International Conference on Learning Representations.
  29. David Radke, Kate Larson, Tim Brecht, and Kyle Tilbury. 2023. Towards a better understanding of learning with multiagent teams. arXiv preprint arXiv:2306.16205. — [arXiv:2306.16205](https://arxiv.org/abs/2306.16205) find
  30. Evgenia Rusak, Patrik Reizinger, Attila Juhos, Oliver Bringmann, Roland S. Zimmermann, and Wieland Brendel. 2024. InfoNCE: Identifying the gap between theory and practice. In ICML 2024 Workshop on Geometry-grounded Representation Learning and Generative Modeling. find
  31. Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. 2023. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36:8634–8652.
  32. Tal Shnitzer, Anthony Ou, Mírian Silva, Kate Soule, Yuekai Sun, Justin Solomon, Neil Thompson, and Mikhail Yurochkin. 2023. Large language model routing with benchmark datasets. arXiv preprint arXiv:2309.15789.
  33. Wei Song, Zhenya Huang, Cheng Cheng, Weibo Gao, Bihan Xu, GuanHao Zhao, Fei Wang, and Runze Wu. 2025. Irt-router: Effective and interpretable multi-llm routing via item response theory. arXiv preprint arXiv:2506.01048. find
  34. KV Srivatsa, Kaushal Kumar Maurya, and Ekaterina Kochmar. 2024. Harnessing the power of multiple minds: Lessons learned from llm routing. arXiv preprint arXiv:2405.00467. find
  35. Dimitris Stripelis, Zijian Hu, Jipeng Zhang, Zhaozhuo Xu, Alay Dilipbhai Shah, Han Jin, Yuhang Yao, Salman Avestimehr, and Chaoyang He. 2024. Tensoropera router: A multi-model router for efficient llm inference. arXiv preprint arXiv:2408.12320. find
  36. Yiliu Sun, Zicheng Zhao, Sheng Wan, and Chen Gong. 2025. Cortexdebate: Debating sparsely and equally for multi-agent debate. arXiv preprint arXiv:2507.03928. find
  37. Khanh-Tung Tran, Dung Dao, Minh-Duong Nguyen, Quoc-Viet Pham, Barry O’Sullivan, and Hoang D Nguyen. 2025. Multi-agent collaboration mechanisms: A survey of llms. arXiv preprint arXiv:2501.06322.
  38. Karl Tuyls. 2023. Multiagent learning: From fundamentals to foundation models. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 1–1. find
  39. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations.
  40. Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, and 1 others. 2025. The rise and potential of large language model based agents: A survey. Science China Information Sciences, 68(2):121101.
  41. Zhankun Xiong, Shichao Liu, Feng Huang, Ziyan Wang, Xuan Liu, Zhongfei Zhang, and Wen Zhang. 2023. Multi-relational contrastive learning graph neural network for drug-drug interaction event prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 5339–5347. find
  42. Yingxuan Yang, Mulei Ma, Yuxuan Huang, Huacan Chai, Chenyu Gong, Haoran Geng, Yuanjian Zhou, Ying Wen, Meng Fang, Muhao Chen, Shangding Gu, Ming Jin, Costas J. Spanos, Yang Yang, Pieter Abbeel, Dawn Song, Weinan Zhang, and Jun Wang. 2025. Agentic web: Weaving the next web with AI agents. preprint, a… — [arXiv:2507.21206](https://arxiv.org/abs/2507.21206) find
  43. Yonghui Yang, Zhengwei Wu, Le Wu, Kun Zhang, Richang Hong, Zhiqiang Zhang, Jun Zhou, and Meng Wang. 2023. Generative-contrastive graph learning for recommendation. In Proceedings of the 46th international ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1117– 1126. find
  44. Yuhao Yang, Chao Huang, Lianghao Xia, and Chenliang Li. 2022. Knowledge graph contrastive learning for recommendation. In Proceedings of the 45th international ACM SIGIR conference on research and development in information retrieval, pages 1434– 1443. find
  45. Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D Manning. 2018. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing. Association…
  46. Junliang Yu, Xin Xia, Tong Chen, Lizhen Cui, Nguyen Quoc Viet Hung, and Hongzhi Yin. 2023a. Xsimgcl: Towards extremely simple graph contrastive learning for recommendation. IEEE Transactions on Knowledge and Data Engineering, 36(2):913–926. find
  47. Large language models collaborating on long-context tasks. Advances in Neural Information Processing Systems, 37:132208–132237. find
  48. Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. 2023. Automatic chain of thought prompting in large language models. In The Eleventh International Conference on Learning Representations.
  49. Ming Zhou, Dan Zhang, Yuandong Wang, Yangli-Ao Geng, and Jie Tang. 2023. Detecting social bot on the fly using contrastive learning. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pages 4995–5001. find
  50. Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. 2021. Graph contrastive learning with adaptive augmentation. In Proceedings of the web conference 2021, pages 2069–2080. find
  51. Lizheng Zu, Lin Lin, Song Fu, Na Zhao, and Pan Zhou. 2025. Collaborative tree search for enhancing embodied multi-agent collaboration. In Proceedings of the Computer Vision and Pattern Recognition Conference, pages 29513–29522. find
  52. Longhui Yu, Weisen Jiang, Han Shi, Jincheng Yu, Zhengying Liu, Yu Zhang, James T Kwok, Zhenguo Li, Adrian Weller, and Weiyang Liu. 2023b. Metamath: Bootstrap your own mathematical questions for large language models. arXiv preprint arXiv:2309.12284.
  53. Yanwei Yue, Guibin Zhang, Boyang Liu, Guancheng Wan, Kun Wang, Dawei Cheng, and Yiyan Qi. 2025. Masrouter: Learning to route llms for multi-agent systems. arXiv preprint arXiv:2502.11133.
  54. Guibin Zhang, Luyang Niu, Junfeng Fang, Kun Wang, Lei Bai, and Xiang Wang. 2025a. Multi-agent architecture search via agentic supernet. arXiv preprint arXiv:2502.04180. — [arXiv:2502.04180](https://arxiv.org/abs/2502.04180) find
  55. Guibin Zhang, Yanwei Yue, Xiangguo Sun, Guancheng Wan, Miao Yu, Junfeng Fang, Kun Wang, Tianlong Chen, and Dawei Cheng. 2024a. G-designer: Architecting multi-agent communication topologies via graph neural networks. arXiv preprint arXiv:2410.11782. — [arXiv:2410.11782](https://arxiv.org/abs/2410.11782) find
  56. Jiayi Zhang, Jinyu Xiang, Zhaoyang Yu, Fengwei Teng, Xiong-Hui Chen, Jiaqi Chen, Mingchen Zhuge, Xin Cheng, Sirui Hong, Jinlin Wang, Bingnan Zheng, Bang Liu, Yuyu Luo, and Chenglin Wu. 2025b. AFlow: Automating agentic workflow generation. In The Thirteenth International Conference on Learning Repres…
  57. Yu Zhang, Kexue Fu, and Zhicong Lu. 2025c. Revto-gether: Supporting science story revision with multiple ai agents. In Proceedings of the Extended Abstracts of the CHI Conference on Human Factors in Computing Systems, pages 1–7. find
  58. Yusen Zhang, Ruoxi Sun, Yanfei Chen, Tomas Pfister, Rui Zhang, and Sercan Arik. 2024b. Chain of agents: find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/xiao-2026-routerhgc-optimized-router-llm-based/