Elamur Research⌕
☰
home / papers / 2026 / Map-of-Actions: Deliberate Reasoning over Multi-Labeled Graphs

Map-of-Actions: Deliberate Reasoning over Multi-Labeled Graphs

Paper · 2026 · Wuguang Ni and Kai Yang

Summary

LLMs usually reason in free-form text, which makes intermediate steps hard to track, check, or correct. This leads to repeated work and errors that compound across steps. Ni and Yang propose Map-of-Actions (MoA), a neuro-symbolic framework inspired by Tolman's cognitive map theory. MoA represents the reasoning state with a graph that carries multiple labels. Every node in this graph is a labeled reasoning unit, tagged valid or invalid and connected to the nodes that precede it. The LLM proposes graph edits (Add, Edit, Delete, Merge, Split), and symbolic programs check and apply them. This blocks circular dependencies and allows backtracking. Nodes can gather evidence through three retrieval actions: web search, a local vector index, and reusable "thought templates" drawn from earlier successful solutions. Once the graph converges, the answer is built from the valid nodes only. On complex QA benchmarks, MoA beats prompt-based baselines (CoT, ToT, GoT) and tool-augmented ones (Self-Ask, ReAct, DSP) by up to 17.9 percentage points. The work suggests that explicit structured state makes LLM reasoning more controllable and interpretable.

Key points

  • Evaluation uses QA datasets including NQ, QASC, HotpotQA, 2WikiMQA and MuSiQue, with the largest gains on multi-hop tasks. MoA's reported accuracy is 61.6 on QASC and 52.7 on HotpotQA.
  • Local retrieval embeds text chunks with BAAI's bge-m3 model (1024-dimensional vectors) and searches them with a Faiss index. Thought templates are kept only if their similarity to the query is at least σ = 0.5.
  • Robustness test on QASC: flipping 0–100% of valid nodes to invalid lowers accuracy only from 61.6 to 59.4. The cost is more operations (6.9 → 13.0) and longer runtime (21.5s → 35.7s).
  • In ablations, removing predecessor links causes the largest drop, 7.5 points on QASC. Removing thought retrieval mainly hurts HotpotQA and MuSiQue, and removing the Delete operator mainly hurts 2WikiMQA and MuSiQue.
  • Stated limitations:
    • Evaluation is limited to QA.
    • Inference is slower than with plain prompting.
    • Answer quality still depends on the LLM's intermediate decisions.

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

🎓Tongji UniversityShanghai · China19 works · 2,162 citations

 Fields, topics and concepts

📚 Shelves 5The 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 worksComputer Vision and Pattern Recognition · 2,869 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,426 works

Cite

Cite as Wuguang Ni and Kai Yang. 2026. Map-of-Actions: Deliberate Reasoning over Multi-Labeled Graphs. Proceedings of the First Workshop on Structured Understanding, Retrieval, and Generation in the LLM Era (SURGeLLM 2026).

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

@inproceedings{ni2026map,
  title = {{Map-of-Actions: Deliberate Reasoning over Multi-Labeled Graphs}},
  author = {Wuguang Ni and Kai Yang},
  booktitle = {Proceedings of the First Workshop on Structured Understanding, Retrieval, and Generation in the LLM Era (SURGeLLM 2026)},
  year = {2026},
  doi = {10.18653/v1/2026.surgellm-1.15},
  url = {https://doi.org/10.18653/v1/2026.surgellm-1.15}
}

References

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

  1. Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, and 1 others. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774.
  2. Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. 2024. Graph of thoughts: Solving elaborate problems with large language models. Proceedings of the AAAI Conference… find
  3. Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter,… — Language Models are Few-Shot Learners
  4. Jianlv Chen, Shitao Xiao, Peitian Zhang, Kun Luo, Defu Lian, and Zheng Liu. 2024. Bge m3-embedding: Multi-lingual, multi-functionality, multi-granularity text embeddings through self-knowledge distillation. Preprint, arXiv:2402.03216.
  5. Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W. Cohen. 2023. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. Transactions on Machine Learning Research. find
  6. Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. 2018. Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv preprint arXiv:1803.05457.
  7. Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, and 1 others. 2025. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arX…
  8. Chunyuan Deng, Yilun Zhao, Xiangru Tang, Mark Gerstein, and Arman Cohan. 2024. Investigating data contamination in modern benchmarks for large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technol…
  9. Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2025. The faiss library. IEEE Transactions on Big Data.
  10. M Fang, S Deng, Y Zhang, Z Shi, L Chen, M Pechenizkiy, and J Wang. 2024. Large language models are neurosymbolic reasoners. In Proceedings of the AAAI Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence (AAAI). find
  11. Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. 2021. Did aristotle use a laptop? a question answering benchmark with implicit reasoning strategies. Transactions of the Association for Computational Linguistics, 9:346– 361. find
  12. Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, and 1 others. 2025. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv:2501.12948. arXiv preprint Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawar…
  13. Chengtao Jian, Kai Yang, Tianhao Gao, Wuguang Ni, Keying Yang, Bowen Xiao, Jiajun Liu, and Ye Ouyang. 2025. Stable preference optimization: A bilevel approach to catastrophic preference shift. arXiv preprint arXiv:2507.07723. — [arXiv:2507.07723](https://arxiv.org/abs/2507.07723) find
  14. Yang Jiao, Xiaodong Wang, and Kai Yang. 2025. Pr-attack: Coordinated prompt-rag attacks on retrieval-augmented generation in large language models via bilevel optimization. In Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 656–… find
  15. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. 2023. Self-refine: Iterative refinement with… find
  16. Vaibhav Mavi, Anubhav Jangra, and Adam Jatowt. 2022. Multi-hop question answering. arXiv preprint arXiv:2204.09140. — [arXiv:2204.09140](https://arxiv.org/abs/2204.09140) find
  17. Zhenyu Pan, Haozheng Luo, Manling Li, and Han Liu. 2025. Chain-of-action: Faithful and multimodal question answering through large language models. In The Thirteenth International Conference on Learning Representations. find
  18. Omar Khattab, Keshav Santhanam, Xiang Lisa Li, David Hall, Percy Liang, Christopher Potts, and Matei Zaharia. 2023. Demonstrate-search-predict: Composing retrieval and language models for knowledge-intensive nlp. Preprint, arXiv:2212.14024.
  19. Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A Smith, and Mike Lewis. 2023. Measuring and narrowing the compositionality gap in language models. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 5687–5711. find
  20. Tushar Khot, Peter Clark, Michal Guerquin, Peter Jansen, and Ashish Sabharwal. 2020. Qasc: A dataset for question answering via sentence composition. In Proceedings of the AAAI Conference on Artificial Intelligence. find
  21. Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023. Toolformer: Language models can teach themselves to use tools. Preprint, arXiv:2302.04761.
  22. Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. 2019. Natural…
  23. Gemma Team, Morgane Riviere, Shreya Pathak, Pier Giuseppe Sessa, Cassidy Hardin, Surya Bhupatiraju, Léonard Hussenot, Thomas Mesnard, Bobak Shahriari, Alexandre Ramé, and 1 others. 2024. Gemma 2: Improving open language models at a practical size. arXiv preprint arXiv:2408.00118. find
  24. Yinghao Li, Haorui Wang, and Chao Zhang. 2024. Assessing logical puzzle solving in large language models: Insights from a minesweeper case study. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume… find
  25. Stephanie Lin, Jacob Hilton, and Owain Evans. 2022. TruthfulQA: Measuring how models mimic human falsehoods. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 3214–3252, Dublin, Ireland. Association for Computational Linguistics…
  26. Ya Liu, Kai Yang, Yu Zhu, Keying Yang, Chengtao Jian, Wuguang Ni, Xiaozhou Ye, and Ye Ouyang. find
  27. Edward C. Tolman. 1948. Cognitive maps in rats and men. Psychological Review, 55(4):189–208. find
  28. Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. 2022. Musique: Multi-hop questions via single-hop question composition. Transactions of the Association for Computational Linguistics, 10:539–554. find
  29. Wenguan Wang, Yi Yang, and Fei Wu. 2024. Towards data-and knowledge-driven ai: a survey on neuro-symbolic computing. IEEE Transactions on Pattern Analysis and Machine Intelligence. find
  30. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, and 1 others. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824– 24837.
  31. Shicheng Xu, Liang Pang, Huawei Shen, Xueqi Cheng, and Tat-Seng Chua. 2024. Search-in-the-chain: Interactively enhancing large language models with search for knowledge-intensive tasks. In The Web Conference 2024. find
  32. An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, and 1 others. 2024. Qwen2. 5 technical report. arXiv preprint arXiv:2412.15115. find
  33. 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 Conference on Empirical Methods in Natural Language Processing (EMNLP).
  34. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2023a. Tree of thoughts: Deliberate problem solving with large language models. Advances in neural information processing systems, 36:11809–11822. find
  35. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2023b. React: Synergizing reasoning and acting in language models. Preprint, arXiv:2210.03629.
  36. Haotong Zhang. 2024. Large language models still face challenges in multi-hop reasoning with external knowledge. Preprint, arXiv:2412.08317. — [arXiv:2412.08317](https://arxiv.org/abs/2412.08317) find
  37. Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. 2022. Automatic chain of thought prompting in large language models. arXiv preprint arXiv:2210.03493.
  38. Da Zheng, Lun Du, Junwei Su, Yuchen Tian, Yuqi Zhu, Jintian Zhang, Lanning Wei, Ningyu Zhang, and Huajun Chen. 2025. Knowledge augmented complex problem solving with large language models: A survey. Preprint, arXiv:2505.03418. — [arXiv:2505.03418](https://arxiv.org/abs/2505.03418)
  39. Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V Le, and Ed H. Chi. 2023. Least-to-most prompting enables complex reasoning in large language models. In The Eleventh International Conference on Learning Representation…

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/ni-2026-map-actions-deliberate-reasoning-over/