Elamur Research⌕
☰
home / papers / 2026 / Taming “Zombie” Agents: A Markov State-Aware Framework for Resilient Multi-Agent Evolution

Taming “Zombie” Agents: A Markov State-Aware Framework for Resilient Multi-Agent Evolution

Paper · 2026 · Taolin Zhang, Pukun Zhao, Qizhou Chen et al.

Summary

LLM-based multi-agent systems often save compute by pruning agents or links from the communication graph. These cuts are permanent. An agent that fails for a moment, through a hallucination or a knowledge gap, is removed even if it could have helped in later rounds. The authors call such agents "zombie" agents. Their framework, AgentRevive, treats collaboration as a Markov decision process and gives each agent one of three states: Active, Standby or Terminated. A lightweight policy network decides each round's transitions from:

  • the agent's previous state,
  • its own answer,
  • the messages it receives.

The reward combines task accuracy, token cost and a hallucination-risk penalty. A second stage builds a binary node mask from agent survival rates and applies it to the spatial and temporal adjacency matrices. Terminated agents are removed for good, while Standby agents remain available and can be revived. Across general reasoning, domain-specific and hallucination benchmarks, AgentRevive beats pruning-based and autoregressive graph-generation baselines. It also uses fewer tokens, which suggests that reversible agent scheduling is more efficient and more robust than hard pruning.

Key points

  • Overall results: averaged across tasks, accuracy rises by about +2.33% over strong baselines (AgentPrune, AgentDropout, ARG-Designer), and token overhead falls by about 15%.

  • MMLU efficiency test (Llama3-8B, one A100): accuracy is 64.30% for AgentRevive, compared with:

    • AgentDropout: 62.75%
    • ARG-Designer: 61.49%
    • fixed MAS round=T: 60.13%

    Token use drops from 1.99M to 1.32M (−33.7%). Inference costs 1.75 s/sample against 1.62 s for AgentDropout. Training takes 20.8 GPU hours against 15.2.

  • What drives transitions: a logistic-regression analysis shows that moving from Standby back to Active is linked mainly to high message information gain (0.69). Higher self-risk pushes agents out of Active.

  • Robustness: the method stays robust under prompt attacks and under different initial graph shapes (Layered, Random).

  • Limitations: experiments use at most 5 agents. The hyperparameters were set to γ = 0.6 and η_risk = 0.5 without broad tuning. The policy network is a simple MLP.

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

🏢Alibaba GroupHangzhou · China201 works · 17,173 citations🎓East China Normal UniversityShanghai · China69 works · 2,490 citations🎓Hefei University of TechnologyHefei · China17 works · 1,702 citations🎓Guangdong University Of Finances and EconomicsGuangzhou · China2 works

 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 Taolin Zhang, Pukun Zhao, Qizhou Chen, Jiuheng Wan, Chen Chen, Xiaofeng He, Chengyu Wang and Richang Hong. 2026. Taming “Zombie” Agents: A Markov State-Aware Framework for Resilient Multi-Agent Evolution. 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.373

@inproceedings{zhang2026taming,
  title = {{Taming “Zombie” Agents: A Markov State-Aware Framework for Resilient Multi-Agent Evolution}},
  author = {Taolin Zhang, Pukun Zhao, Qizhou Chen, Jiuheng Wan, Chen Chen, Xiaofeng He, Chengyu Wang and Richang Hong},
  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.373},
  url = {https://doi.org/10.18653/v1/2026.acl-long.373}
}

References

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

  1. Li Boyi, Zhonghan Zhao, Der-Horng Lee, and Gaoang Wang. 2025. Adaptive graph pruning for multi-agent communication. CoRR, abs/2506.02951. — [arXiv:2506.02951](https://arxiv.org/abs/2506.02951) find
  2. Mert Cemri, Melissa Z. Pan, Shuyi Yang, Lakshya A. find
  3. Agrawal, Bhavya Chopra, Rishabh Tiwari, Kurt Keutzer, Aditya G. Parameswaran, Dan Klein, Kannan Ramchandran, Matei Zaharia, Joseph E. Gonzalez, and Ion Stoica. 2025. Why do multi-agent LLM systems fail? CoRR, abs/2503.13657.
  4. Chia-Yuan Chang, Zhimeng Jiang, Vineeth Rakesh, Menghai Pan, Chin-Chia Michael Yeh, Guanchu Wang, Mingzhi Hu, Zhichao Xu, Yan Zheng, Ma-hashweta Das, and Na Zou. 2025. MAIN-RAG: multi-agent filtering retrieval-augmented generation. In ACL, pages 2607–2622.
  5. Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Ion Stoica, Matei Zaharia, and James Zou. 2024a. Are more LLM calls all you need? towards scaling laws of compound inference systems. CoRR, abs/2403.02419. find
  6. 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
  7. Weize Chen, Yusheng Su, Jingwei Zuo, Cheng Yang, Chenfei Yuan, Chi-Min Chan, Heyang Yu, Yaxi Lu, Yi-Hsin Hung, Chen Qian, Yujia Qin, Xin Cong, Ruobing Xie, Zhiyuan Liu, Maosong Sun, and Jie Zhou. 2024b. Agentverse: Facilitating multi-agent collaboration and exploring emergent behaviors. In ICLR.
  8. Weize Chen, Yusheng Su, Jingwei Zuo, Cheng Yang, Chenfei Yuan, Chen Qian, Chi-Min Chan, Yujia Qin, Yaxi Lu, Ruobing Xie, Zhiyuan Liu, Maosong Sun, and Jie Zhou. 2023. Agentverse: Facilitating multi-agent collaboration and exploring emergent behaviors in agents. CoRR, abs/2308.10848.
  9. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021. Training verifiers to solve math word problems. CoRR, abs/2110.14168.
  10. DeepSeek-AI, Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Daya Guo, Dejian Yang, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, and 181 others. 2025. Deepseek-v3 technical report. Preprint, arXiv:2… find
  11. 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.
  12. Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, and 82 others. 2024… — The Llama 3 Herd of Models
  13. Bingzheng Gan, Yufan Zhao, Tianyi Zhang, Jing Huang, Yusu Li, Shu Xian Teo, Changwang Zhang, and Wei Shi. 2025. MASTER: A multi-agent system with LLM specialized MCTS. In NAACL, pages 9409– 9426. find
  14. 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.
  15. Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. 2021. Measuring massive multitask language understanding. In ICLR.
  16. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural Computation, 9(8):1735– 1780. find
  17. Samuel Holt, Max Ruiz Luyten, and Mihaela van der Schaar. 2023. L2MAC: large language model automatic computer for unbounded code generation. CoRR, abs/2310.02003. — [arXiv:2310.02003](https://arxiv.org/abs/2310.02003) find
  18. 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.
  19. Yue Hu, Yuzhu Cai, Yaxin Du, Xinyu Zhu, Xiangrui Liu, Zijie Yu, Yuchen Hou, Shuo Tang, and Siheng Chen. 2025. Self-evolving multi-agent collaboration networks for software development. In ICLR. find
  20. Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. 2023. Llm-blender: Ensembling large language models with pairwise ranking and generative fusion. In ACL, pages 14165–14178.
  21. 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. 2024. Dspy: Compiling declarative language model calls into state-of-the-art pipelines.… find
  22. Shiyuan Li, Yixin Liu, Qingsong Wen, Chengqi Zhang, and Shirui Pan. 2025. Assemble your crew: Automatic multi-agent communication topology design via autoregressive graph generation. CoRR, abs/2507.18224. — [arXiv:2507.18224](https://arxiv.org/abs/2507.18224) find
  23. Hongzhan Lin, Yang Deng, Yuxuan Gu, Wenxuan Zhang, Jing Ma, See-Kiong Ng, and Tat-Seng Chua. 2025a. FACT-AUDIT: an adaptive multi-agent framework for dynamic fact-checking evaluation of large language models. In ACL, pages 360–381.
  24. Stephanie Lin, Jacob Hilton, and Owain Evans. 2022. Truthfulqa: Measuring how models mimic human falsehoods. In ACL, pages 3214–3252.
  25. Xixun Lin, Yucheng Ning, Jingwen Zhang, Yan Dong, Yilong Liu, Yongxuan Wu, Xiaohua Qi, Nan Sun, Yanmin Shang, Pengfei Cao, Lixin Zou, Xu Chen, Chuan Zhou, Jia Wu, Shirui Pan, Bin Wang, Yanan Cao, Kai Chen, Songlin Hu, and Li Guo. 2025b. Llm-based agents suffer from hallucinations: A survey of taxono… find
  26. Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. 2017. Program induction by rationale generation: Learning to solve and explain algebraic word problems. In ACL, pages 158–167. find
  27. Zijun Liu, Yanzhe Zhang, Peng Li, Yang Liu, and Diyi Yang. 2024. A dynamic llm-powered agent network for task-oriented agent collaboration.
  28. Arkil Patel, Satwik Bhattamishra, and Navin Goyal. 2021. Are NLP models really able to solve simple math word problems? In NAACL, pages 2080–2094.
  29. 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. 2024. Chatdev: Communicative agents for software development. In ACL, pages 15174–15186.
  30. Yoichi Ishibashi and Yoshimasa Nishimura. 2024. Self-organized agents: A LLM multi-agent framework toward ultra large-scale code generation and optimization. CoRR, abs/2404.02183. — [arXiv:2404.02183](https://arxiv.org/abs/2404.02183) find
  31. 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 ICLR.
  32. Jiarui Ji, Runlin Lei, Jialing Bi, Zhewei Wei, Yankai Lin, Xuchen Pan, Yaliang Li, and Bolin Ding. 2024. Dynamic and textual graph generation via large-scale llm-based agent simulation. CoRR, abs/2410.09824. — [arXiv:2410.09824](https://arxiv.org/abs/2410.09824) find
  33. Song Wang, Zhen Tan, Zihan Chen, Shuang Zhou, Tianlong Chen, and Jundong Li. 2025a. Anymac: Cascading flexible multi-agent collaboration via next-agent prediction. CoRR, abs/2506.17784.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhang-2026-taming-zombie-agents-markov-state/