Elamur Research⌕
☰
home / papers / 2026 / Efficient Multi-Agent System Training with Data Influence-Oriented Tree Search

Efficient Multi-Agent System Training with Data Influence-Oriented Tree Search

Paper · 2026 · Wentao Shi, Zichun Yu, Fuli Feng et al.

Summary

Jointly optimizing LLM-based multi-agent systems (MAS) is difficult, partly because each agent's contribution to the outcome is hard to measure. Earlier self-training methods such as Optima run Monte Carlo Tree Search (MCTS) to synthesize interaction trajectories and build DPO preference pairs ranked by Q-values. However, a high Q-value does not guarantee that a sample improves the trained model. The authors propose Data Influence-oriented Tree Search (DITS), which scores synthetic data by its influence, meaning its expected effect on model performance. This score guides both the tree search and the selection of preference pairs. DPO loss is a poor proxy for downstream quality, so the authors redefine influence as the change in non-differentiable validation metrics such as F1 or accuracy. They estimate it through inference passes rather than expensive gradient computations. On seven datasets spanning Information Exchange, Debate and DeepSearch tasks, DITS outperforms state-of-the-art MAS optimization methods. The results suggest that, for a fixed synthesis budget, spending compute on influence estimation helps more than refining Q-values.

Key points

  • Reported gains over prior methods:
    • about 2.7% on average with one training iteration;
    • 2.5% with multiple iterations on Information Exchange;
    • 2.6% on DeepSearch.
  • The correlation between DPO loss and validation F1/accuracy was weak (below 0.2), which motivated the metric-based influence score.
  • Training on a well-chosen top-scoring subset beat training on all MCTS data, pointing to noise in the raw synthetic data. Very small subsets hurt performance.
  • Across iterations, the mean influence of synthetic data rose and its distribution narrowed, at a possible cost to diversity. Larger validation sets improved the estimates but required more compute.
  • DITS is meant for offline, training-time data selection and may be too slow for real-time use. Code: github.com/swt-user/DITS.

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

🎓Carnegie Mellon UniversityPittsburgh · United States539 works · 179,533 citations🎓University of Science and Technology of ChinaHefei · China108 works · 112,698 citations

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 works

Cite

Cite as Wentao Shi, Zichun Yu, Fuli Feng, Xiangnan He and Chenyan Xiong. 2026. Efficient Multi-Agent System Training with Data Influence-Oriented Tree Search. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

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

@inproceedings{shi2026efficient,
  title = {{Efficient Multi-Agent System Training with Data Influence-Oriented Tree Search}},
  author = {Wentao Shi, Zichun Yu, Fuli Feng, Xiangnan He and Chenyan Xiong},
  booktitle = {Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.296},
  url = {https://doi.org/10.18653/v1/2026.acl-long.296}
}

References

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

  1. Juhan Bae, Wu Lin, Jonathan Lorraine, and Roger Grosse. 2024. Training data attribution via approximate unrolled differentiation. CoRR, abs/2405.12186. — [arXiv:2405.12186](https://arxiv.org/abs/2405.12186) find
  2. Sumithra Bhakthavatsalam, Daniel Khashabi, Tushar Khot, Bhavana Dalvi Mishra, Kyle Richardson, Ashish Sabharwal, Carissa Schoenick, Oyvind Tafjord, and Peter Clark. 2021. Think you have solved direct-answer question answering? try arc-da, the direct-answer AI2 reasoning challenge. CoRR, abs/2102.033… — [arXiv:2102.03315](https://arxiv.org/abs/2102.03315) find
  3. J. A. Bondy and U. S. R. Murty. 1976. Graph Theory with Applications. Elsevier, New York. find
  4. Baian Chen, Chang Shu, Ehsan Shareghi, Nigel Collier, Karthik Narasimhan, and Shunyu Yao. 2023. Fireact: Toward language agent fine-tuning. CoRR, abs/2310.05915.
  5. Weize Chen, Chenfei Yuan, Jiarui Yuan, Yusheng Su, Chen Qian, Cheng Yang, Ruobing Xie, Zhiyuan Liu, and Maosong Sun. 2024a. Beyond natural language: Llms leveraging alternative formats for enhanced reasoning and communication. In EMNLP (Findings), pages 10626–10641. Association for Computational Lin… find
  6. Weize Chen, Jiarui Yuan, Chen Qian, Cheng Yang, Zhiyuan Liu, and Maosong Sun. 2024b. Optima: Optimizing effectiveness and efficiency for llm-based multi-agent system. CoRR, abs/2410.08115. find
  7. Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. 2024. Improving factuality and reasoning in language models through multiagent debate. In ICML. OpenReview.net.
  8. Abhimanyu Dubey, Abhinav Jauhri, and et al. 2024. The llama 3 herd of models. Preprint, arXiv:2407.21783.
  9. Jonathan L. Gross and Jay Yellen. 2005. Graph Theory and Its Applications. find
  10. Xinyu Guan, Li Lyna Zhang, Yifei Liu, Ning Shang, Youran Sun, Yi Zhu, Fan Yang, and Mao Yang. 2025. rstar-math: Small llms can master math reasoning with self-evolved deep thinking. Preprint, arXiv:2501.04519.
  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. In IJCAI, pages 8048–8057. ijcai.org.
  12. Mandar Joshi, Eunsol Choi, Daniel S. Weld, and Luke Zettlemoyer. 2017. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. In ACL (1), pages 1601–1611. Association for Computational Linguistics.
  13. Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan, Saiful Haq, Ashutosh Sharma, Thomas T. Joshi, Hanna Moazam, Heather Miller, Matei Zaharia, and Christopher Potts. 2023. Dspy: Compiling declarative language model calls into self-improving pipelines. C…
  14. Frank R Hampel. 1974. The influence curve and its role in robust estimation. Journal of the american statistical association, 69(346):383–393. find
  15. Pang Wei Koh and Percy Liang. 2017. Understanding black-box predictions via influence functions. In ICML, volume 70 of Proceedings of Machine Learning Research, pages 1885–1894. PMLR.
  16. Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. 2023. Reasoning with language model is planning with world model. In EMNLP, pages 8154–8173. Association for Computational Linguistics. find
  17. Guohao Li, Hasan Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. 2023. CAMEL: communicative agents for "mind" exploration of large language model society. In NeurIPS.
  18. Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. 2021. Measuring massive multitask language understanding. In ICLR. OpenReview.net.
  19. Felix Hill, Antoine Bordes, Sumit Chopra, and Jason Weston. 2016. The goldilocks principle: Reading children’s books with explicit memory representations. In ICLR.
  20. Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. 2020. Constructing A multi-hop QA dataset for comprehensive evaluation of reasoning steps. In COLING, pages 6609–6625. International Committee on Computational Linguistics.
  21. Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, Lingfeng Xiao, Chenglin Wu, and Jürgen Schmidhuber. 2024. Metagpt: Meta programming for A multi-agent collaborative framework. In ICLR.…
  22. Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2022. Lora: Low-rank adaptation of large language models. In ICLR. OpenReview.net.
  23. Xueyu Hu, Tao Xiong, Biao Yi, Zishu Wei, Ruixuan Xiao, Yurun Chen, Jiasheng Ye, Meiling Tao, Xiangxin Zhou, Ziyu Zhao, Yuhuai Li, Shengze Xu, Shawn Wang, Xinchen Xu, Shuofei Qiao, Kun Kuang, Tieyong Zeng, Liang Wang, Jiwei Li, and 9 others. 2024. Os agents: A survey on mllm-based agents for general… find
  24. Md. Ashraful Islam, Mohammed Eunus Ali, and Md. Rizwan Parvez. 2024. Mapcoder: Multi-agent code generation for competitive problem solving. In ACL (1), pages 4912–4944. Association for Computational Linguistics. find
  25. Junyou Li, Qin Zhang, Yangbin Yu, Qiang Fu, and Deheng Ye. 2024a. More agents is all you need. CoRR, abs/2402.05120. find
  26. Shuangtao Li, Shuaihao Dong, Kexin Luan, Xinhan Di, and Chaofan Ding. 2025a. Enhancing reasoning through process supervision with monte carlo tree search. Preprint, arXiv:2501.01478. — [arXiv:2501.01478](https://arxiv.org/abs/2501.01478) find
  27. Xiaochuan Li, Zichun Yu, and Chenyan Xiong. 2024b. Montessori-instruct: Generate influential training data tailored for student learning. CoRR, abs/2410.14208. — [arXiv:2410.14208](https://arxiv.org/abs/2410.14208) find
  28. Xiaoxi Li, Guanting Dong, Jiajie Jin, Yuyao Zhang, Yujia Zhou, Yutao Zhu, Peitian Zhang, and Zhicheng Dou. 2025b. Search-o1: Agentic search-enhanced large reasoning models. CoRR, abs/2501.05366.
  29. Xiaoxi Li, Jiajie Jin, Guanting Dong, Hongjin Qian, Yutao Zhu, Yongkang Wu, Ji-Rong Wen, and Zhicheng Dou. 2025c. Webthinker: Empowering large reasoning models with deep research capability. CoRR, abs/2504.21776. find
  30. 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, pages 17889–17904. Association for Computational Linguistics.
  31. Zijun Liu, Yanzhe Zhang, Peng Li, Yang Liu, and Diyi Yang. 2024. A dynamic LLM-powered agent network for task-oriented agent collaboration. In COLM. find
  32. Taywon Min, Haeone Lee, Hanho Ryu, Yongchan Kwon, and Kimin Lee. 2025. Understanding impact of human feedback via influence functions. Preprint, arXiv:2501.05790. find
  33. Sumeet Ramesh Motwani, Chandler Smith, Rocktim Jyoti Das, Markian Rybchuk, Philip H. S. Torr, Ivan Laptev, Fabio Pizzati, Ronald Clark, and Christian Schröder de Witt. 2024. MALT: improving reasoning with multi-agent LLM training. CoRR, abs/2412.01928. — [arXiv:2412.01928](https://arxiv.org/abs/2412.01928) find
  34. OpenAI. 2023. GPT-4 technical report. abs/2303.08774.
  35. CoRR, Krista Opsahl-Ong, Michael J. Ryan, Josh Purtell, David Broman, Christopher Potts, Matei Zaharia, and Omar Khattab. 2024. Optimizing instructions and demonstrations for multi-stage language model programs. In EMNLP, pages 9340–9366. Association for Computational Linguistics.
  36. Richard Yuanzhe Pang, Weizhe Yuan, Kyunghyun Cho, He He, Sainbayar Sukhbaatar, and Jason Weston. 2024. Iterative reasoning preference optimization. CoRR, abs/2404.19733.
  37. Sung Min Park, Kristian Georgiev, Andrew Ilyas, Guillaume Leclerc, and Aleksander Madry. 2023. TRAK: attributing model behavior at scale. In ICML, volume 202 of Proceedings of Machine Learning Research, pages 27074–27113. PMLR. find
  38. Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. 2020. Estimating training data influence by tracing gradient descent. In NeurIPS. find
  39. Zhenting Qi, Mingyuan Ma, Jiahang Xu, Li Lyna Zhang, Fan Yang, and Mao Yang. 2024. Mutual reasoning makes smaller llms stronger problem-solvers. CoRR, abs/2408.06195. find
  40. Chen Qian, Jiahao Li, Yufan Dang, Wei Liu, Yifei Wang, Zihao Xie, Weize Chen, Cheng Yang, Yingli Zhang, Zhiyuan Liu, and Maosong Sun. 2024a. Iterative experience refinement of software-developing agents. CoRR, abs/2405.04219. — [arXiv:2405.04219](https://arxiv.org/abs/2405.04219) find
  41. Chen Qian, Wei Liu, Hongzhang Liu, Nuo Chen, Yufan Dang, Jiahao Li, Cheng Yang, Weize Chen, Yusheng Su, Xin Cong, Juyuan Xu, Dahai Li, Zhiyuan Liu, and Maosong Sun. 2024b. Chatdev: Communicative agents for software development. In ACL (1), pages 15174–15186. Association for Computational Linguistics…
  42. Chen Qian, Zihao Xie, Yifei Wang, Wei Liu, Yufan Dang, Zhuoyun Du, Weize Chen, Cheng Yang, Zhiyuan Liu, and Maosong Sun. 2024c. Scaling large-language-model-based multi-agent collaboration. Preprint, arXiv:2406.07155. find
  43. Rafael Rafailov, Yaswanth Chittepu, Ryan Park, Harshit Sikchi, Joey Hejna, W. Bradley Knox, Chelsea Finn, and Scott Niekum. 2024. Scaling laws for reward model overoptimization in direct alignment algorithms. CoRR, abs/2406.02900. — [arXiv:2406.02900](https://arxiv.org/abs/2406.02900) find
  44. Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D. Manning, Stefano Ermon, and Chelsea Finn. 2023. Direct preference optimization: Your language model is secretly a reward model. In NeurIPS.
  45. Wentao Shi, Xiangnan He, Yang Zhang, Chongming Gao, Xinyue Li, Jizhi Zhang, Qifan Wang, and Fuli Feng. 2024a. Large language models are learnable planners for long-term recommendation. In SIGIR, pages 1893–1903. ACM. find
  46. Wentao Shi, Mengqi Yuan, Junkang Wu, Qifan Wang, and Fuli Feng. 2024b. Direct multi-turn preference optimization for language agents. In EMNLP, pages 2312–2324. Association for Computational Linguistics. find
  47. Zhengyan Shi, Sander Land, Acyr Locatelli, Matthieu Geist, and Max Bartolo. 2024c. Understanding likelihood over-optimisation in direct alignment algorithms. CoRR, abs/2410.11677. — [arXiv:2410.11677](https://arxiv.org/abs/2410.11677) find
  48. David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray… find
  49. Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. 2024. Scaling LLM test-time compute optimally can be more effective than scaling model parameters. CoRR, abs/2408.03314.
  50. Qwen Team. 2024. Qwq: Reflect deeply on the boundaries of the unknown. https://huggingface.co. [50]. ↗
  51. Qwen Team. 2025. Qwen2.5 technical report. Preprint, arXiv:2412.15115. find
  52. 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. Preprint, arXiv:2501.06322. find
  53. Junlin Wang, Jue Wang, Ben Athiwaratkun, Ce Zhang, and James Zou. 2024a. Mixture-of-agents enhances large language model capabilities. CoRR, abs/2406.04692. find
  54. Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, Wayne Xin Zhao, Zhewei Wei, and Jirong Wen. 2024b. A survey on large language model based autonomous agents. Frontiers of Computer Science, 18(6).
  55. Xiyao Wang, Linfeng Song, Ye Tian, Dian Yu, Baolin Peng, Haitao Mi, Furong Huang, and Dong Yu. 2024c. Towards self-improvement of llms via MCTS: leveraging stepwise knowledge with curriculum preference learning. CoRR, abs/2410.06508. — [arXiv:2410.06508](https://arxiv.org/abs/2410.06508) find
  56. Zhenhailong Wang, Shaoguang Mao, Wenshan Wu, Tao Ge, Furu Wei, and Heng Ji. 2024d. Unleashing the emergent cognitive synergy in large language models: A task-solving agent through multi-persona self-collaboration. In NAACL-HLT, pages 257–279. Association for Computational Linguistics.
  57. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. 2022. Chain-of-thought prompting elicits reasoning in large language models. In NeurIPS.
  58. Jialong Wu, Wenbiao Yin, Yong Jiang, Zhenglin Wang, Zekun Xi, Runnan Fang, Deyu Zhou, Pengjun Xie, and Fei Huang. 2025. Webwalker: Benchmarking llms in web traversal. Preprint, arXiv:2501.07572.
  59. Chaoyun Zhang, Shilin He, Jiaxu Qian, Bowen Li, Liqun Li, Si Qin, Yu Kang, Minghua Ma, Guyue Liu, Qingwei Lin, Saravan Rajmohan, Dongmei Zhang, and Qi Zhang. 2024a. Large language model-brained gui agents: A survey. Preprint, arXiv:2411.18279. — [arXiv:2411.18279](https://arxiv.org/abs/2411.18279) find
  60. Dan Zhang, Sining Zhoubian, Yisong Yue, Yuxiao Dong, and Jie Tang. 2024b. Rest-mcts*: LLM self-training via process reward guided tree search. CoRR, abs/2406.03816.
  61. Di Zhang, Xiaoshui Huang, Dongzhan Zhou, Yuqiang Li, and Wanli Ouyang. 2024c. Accessing GPT-4 level mathematical olympiad solutions via monte carlo tree self-refine with llama-3 8b. CoRR, abs/2406.07394. find
  62. Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Shaokun Zhang, Erkang Zhu, Beibin Li, Li Jiang, Xiaoyun Zhang, and Chi Wang. 2023. Autogen: Enabling next-gen LLM applications via multi-agent conversation framework. CoRR, abs/2308.08155.
  63. Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. 2024. Inference scaling laws: An empirical analysis of compute-optimal inference for problem-solving with language models. Preprint, arXiv:2408.00724.
  64. Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, Rui Zheng, Xiaoran Fan, Xiao Wang, Limao Xiong, Yuhao Zhou, Weiran Wang, Changhao Jiang, Yicheng Zou, Xiangyang Liu, and 10 others. 2023. The rise and potential of large language mode…
  65. Mengzhou Xia, Sadhika Malladi, Suchin Gururangan, Sanjeev Arora, and Danqi Chen. 2024. LESS: selecting influential data for targeted instruction tuning. In ICML. OpenReview.net.
  66. Yuxi Xie, Anirudh Goyal, Wenyue Zheng, Min-Yen Kan, Timothy P. Lillicrap, Kenji Kawaguchi, and Michael Shieh. 2024. Monte carlo tree search boosts reasoning via iterative preference learning. CoRR, abs/2405.00451. find
  67. Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. In EMNLP, pages 2369–2380. Association for Computational Linguistics.
  68. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R. Narasimhan, and Yuan Cao. 2023. React: Synergizing reasoning and acting in language models. In ICLR. OpenReview.net.
  69. Zichun Yu, Spandan Das, and Chenyan Xiong. 2024. Mates: Model-aware data selection for efficient pre-training with data influence models. In NeurIPS. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/shi-2026-efficient-multi-agent-system-training/