Elamur Research⌕
☰
home / papers / 2026 / Verification-Aware Planning for Multi-Agent Systems

Verification-Aware Planning for Multi-Agent Systems

Paper · 2026 · Tianyang Xu, Dan Zhang, Kushan Mitra et al.

Summary

Multi-agent LLM pipelines often break not because an agent reasons badly, but because of subtle mismatches: an agent misreads its subtask, returns output in the wrong format, or hands off something downstream agents did not expect. Standard verification checks factual accuracy or the final answer, so it rarely catches these handoff failures.

The authors propose VeriMAP, a framework with four modules: a Planner, Executors, a Verifier and a Coordinator. The planner splits a task into a DAG of subtasks. It fixes structured, consistently named JSON inputs and outputs for each node. It also writes its own acceptance tests, called verification functions (VFs), as Python assertions or natural-language criteria. Executors see only their local instruction and context. The Coordinator handles retries and, when a node keeps failing, replanning.

Across five math, coding and QA benchmarks, VeriMAP beats single- and multi-agent baselines, with the largest gains on the hardest sets. The work shows that putting the "global" reasoning into the planner lets cheaper models act reliably as executors. It also gives interpretable failure signals without external labels.

Key points

  • VFs come in two types. Python VFs give deterministic format and correctness checks, while natural-language VFs are judged by an LLM verifier for semantic criteria. A subtask passes only if all of its VFs pass (strict logical AND).
  • The planner never sees the benchmark's unit tests, so its VFs cannot exploit the gold checks.
  • Executors run on gpt-4o-mini as ReAct-style or tool-calling agents. Each node gets up to 3 execute–verify attempts before replanning is triggered.
  • Benchmarks include GSM8K, Olympiads and BigCodeBench-Hard. Compared with the next-best tool-enabled ReAct agents, VeriMAP gains up to 9.8% on Olympiads and 4.05% on BigCodeBench-Hard.
  • The authors list three limitations: a naive replanning signal (the full failure history is simply appended), dependence on a strong centralized planner, and high resource cost. Code is available at github.com/megagonlabs/veriMAP.

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

🎓Purdue University West LafayetteWest Lafayette · United States23 works · 1,417 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

Cite

Cite as Tianyang Xu, Dan Zhang, Kushan Mitra and Estevam Hruschka. 2026. Verification-Aware Planning for Multi-Agent Systems. Proceedings of the 19th Conference of the European Chapter 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.eacl-long.353

@inproceedings{xu2026verification,
  title = {{Verification-Aware Planning for Multi-Agent Systems}},
  author = {Tianyang Xu, Dan Zhang, Kushan Mitra and Estevam Hruschka},
  booktitle = {Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.eacl-long.353},
  url = {https://doi.org/10.18653/v1/2026.eacl-long.353}
}

References

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

  1. Ao Li, Yuexiang Xie, Songze Li, Fugee Tsung, Bolin Ding, and Yaliang Li. 2025. Agent-oriented planning in multi-agent systems. In The Thirteenth International Conference on Learning Representations. find
  2. Mert Cemri, Melissa Z. Pan, Shuyi Yang, Lakshya A. Agrawal, Bhavya Chopra, Rishabh Tiwari, Kurt Keutzer, Aditya Parameswaran, Dan Klein, Kannan Ramchandran, Matei Zaharia, Joseph E. Gonzalez, and Ion Stoica. 2025. Why do multi-agent llm systems fail? Preprint, arXiv:2503.13657. find
  3. Guohao Li, Hasan Abed Al Kader Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. 2023. Camel: Communicative agents for "mind" exploration of large language model society. Preprint, arXiv:2303.17760.
  4. Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde 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
  5. Jia Li, Edward Beeching, Lewis Tunstall, Ben Lipkin, Roman Soletskyi, Shengyi Costa Huang, Kashif Rasul, Longhui Yu, Albert Jiang, Ziju Shen, Zihan Qin, Bin Dong, Li Zhou, Yann Fleureau, Guillaume Lample, and Stanislas Polu. 2024. NuminaMath: The largest public dataset in ai4maths with 860k pairs of… find
  6. 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. Preprint, arXiv:2110.14168.
  7. Lutfi Eren Erdogan, Nicholas Lee, Sehoon Kim, Suhong Moon, Hiroki Furuta, Gopala Anumanchipalli, Kurt Keutzer, and Amir Gholami. 2025. Plan-and-act: Improving planning of agents for long-horizon tasks. Preprint, arXiv:2503.09572. — [arXiv:2503.09572](https://arxiv.org/abs/2503.09572) find
  8. Danil S. Grigorev, Alexey K. Kovalev, and Aleksandr I. Panov. 2025. Verifyllm: Llm-based pre-execution task plan verification for robots. find
  9. Sijia Gu, Noor Nashid, and Ali Mesbah. 2025. Llm test generation via iterative hybrid program analysis. Preprint, arXiv:2503.13580. — [arXiv:2503.13580](https://arxiv.org/abs/2503.13580) find
  10. Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, and Yujiu Yang. 2024. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. In The Twelfth International Conference on Learning Representations. find
  11. Yilun Hao, Yongchao Chen, Yang Zhang, and Chuchu Fan. 2025. Large language models can solve real-world planning rigorously with formal verification tools. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Tec…
  12. Yuxuan Liu, Tianchi Yang, Shaohan Huang, Zihan Zhang, Haizhen Huang, Furu Wei, Weiwei Deng, Feng Sun, and Qi Zhang. 2024. Calibrating LLM-based evaluator. In Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024), pag…
  13. Ning Miao, Yee Whye Teh, and Tom Rainforth. 2024. Selfcheck: Using LLMs to zero-shot check their own step-by-step reasoning. In The Twelfth International Conference on Learning Representations. find
  14. Archiki Prasad, Alexander Koller, Mareike Hartmann, Peter Clark, Ashish Sabharwal, Mohit Bansal, and Tushar Khot. 2024. ADaPT: As-needed decomposition and planning with language models. In Findings of the Association for Computational Linguistics: NAACL 2024, pages 4226–4252, Mexico City, Mexico. As…
  15. Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. 2024. Direct preference optimization: Your language model is secretly a reward model. Preprint, arXiv:2305.18290.
  16. Shreya Shankar, J.D. Zamfirescu-Pereira, Bjoern Hartmann, Aditya Parameswaran, and Ian Arawjo. 2024. Who validates the validators? aligning llm-assisted evaluation of llm outputs with human preferences. In Proceedings of the 37th Annual ACM Symposium on User Interface Software and Technology, UIST ’… find
  17. Harsh Singh, Rocktim Jyoti Das, Mingfei Han, Preslav Nakov, and Ivan Laptev. 2024. Malmm: Multi-agent large language models for zero-shot robotics manipulation. Preprint, arXiv:2411.17636. — [arXiv:2411.17636](https://arxiv.org/abs/2411.17636) find
  18. Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati. 2024. On the self-verification limitations of large language models on reasoning and planning tasks. Preprint, arXiv:2402.08115. find
  19. Haotian Sun, Yuchen Zhuang, Lingkai Kong, Bo Dai, and Chao Zhang. 2023. Adaplanner: Adaptive planning from feedback with language models. Preprint, arXiv:2305.16653. find
  20. Yoo Yeon Sung, Hannah Kim, and Dan Zhang. 2025. Verila: A human-centered evaluation framework for interpretable verification of llm agent failures. Preprint, arXiv:2503.12651. — [arXiv:2503.12651](https://arxiv.org/abs/2503.12651) find
  21. Mirac Suzgun and Adam Tauman Kalai. 2024. Meta-prompting: Enhancing language models with task-agnostic scaffolding.
  22. Yixuan Tang and Yi Yang. 2024. Multihop-rag: Benchmarking retrieval-augmented generation for multi-hop queries. Preprint, arXiv:2401.15391.
  23. Yunkun Wang, Yue Zhang, Zhen Qin, Chen Zhi, Binhua Li, Fei Huang, Yongbin Li, and Shuiguang Deng. 2025. ExploraCoder: Advancing code generation for multiple unseen APIs via planning and chained exploration. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (V… find
  24. Feijie Wu, Zitao Li, Fei Wei, Yaliang Li, Bolin Ding, and Jing Gao. 2025. Talk to right specialists: Routing and planning in multi-agent system for question answering. Preprint, arXiv:2501.07813. — [arXiv:2501.07813](https://arxiv.org/abs/2501.07813) find
  25. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2023. ReAct: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR).
  26. Kunlun Zhu, Hongyi Du, Zhaochen Hong, Xiaocheng Yang, Shuyi Guo, Zhe Wang, Zhenhailong Wang, Cheng Qian, Robert Tang, Heng Ji, and Jiaxuan You. 2025. MultiAgentBench : Evaluating the collaboration and competition of LLM agents. In Proceedings of the 63rd Annual Meeting of the Association for Computa… find
  27. Terry Yue Zhuo, Minh Chien Vu, Jenny Chim, Han Hu, Wenhao Yu, Ratnadira Widyasari, Imam Nur Bani Yusuf, Haolan Zhan, Junda He, Indraneil Paul, Simon Brunner, Chen Gong, Thong Hoang, Armel Randy Zebaze, Xiaoheng Hong, Wen-Ding Li, Jean Kaddour, Ming Xu, Zhihan Zhang, and 14 others. 2024. BigCodeBench…

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/xu-2026-verification-aware-planning-multi-agent/