Elamur Research⌕
☰
home / papers / 2026 / Bayesian Social Deduction with Graph-Informed Language Models

Bayesian Social Deduction with Graph-Informed Language Models

Paper · 2026 · Shahab Rahimirad, Guven Gergerli, Lucia Romero et al.

Summary

The paper examines whether large language models can perform social reasoning, meaning inferring hidden roles and intentions from partial observations, in the hidden-role game Avalon. The authors find that the strongest reasoning models play well but need long test-time reasoning chains. Their smaller distilled versions, such as 8B and 70B Deepseek-R1 variants, perform much worse and fail even simple constrained probability puzzles. To fix this, the authors propose GRAIL (Graph Reasoning Agent Informed through Language). In GRAIL, a factor graph over player roles performs belief inference, while an LLM parses chat, supplies a language-based prior and writes messages. Inference uses max-product belief propagation, and a neural network trained on past games estimates the conditional probabilities. With a much smaller non-reasoning LLM, GRAIL matches or beats large reasoning models in Agent-Agent games. In a controlled study it beat novice humans, the first language agent reported to do so. This shows that pairing LLMs with external structured inference can give socially competent real-time agents.

Key points

  • Agent design: GRAIL plays only on the Good side, and special roles such as Merlin are left out. The factor graph covers six role variables plus party, vote and quest-outcome variables for each round, with a hard constraint of exactly two Evil players.
  • Human study setup: The study ran 15 trials with three participants each, giving 15 games with GRAIL and 15 with a GPT-o4-mini reasoning baseline. GPT-o4-mini replaced DeepSeek-R1 because of API latency and reliability problems.
  • Win rates: GRAIL won 67% of games against 27% for the baseline. The frequentist test gave p = 0.054, while a Bayesian analysis gave a 96.7% posterior probability that GRAIL is better.
  • Ratings and party assessment:
    • Participants rated GRAIL significantly higher than the reasoning agents on contribution and helpfulness.
    • Its suggestions were rated better than those of human teammates (p = 0.035).
    • Its F1 for judging party proposals beat humans (p = 0.007).
  • Released resources: The authors make their code, models and benchmark publicly available. They also release a collection of Avalon games played among agents and between humans and agents, which includes chat logs and game states.

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

🎓Virginia TechBlacksburg · United States36 works · 43,036 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

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,320 worksReasoning · 1,426 works

Cite

Cite as Shahab Rahimirad, Guven Gergerli, Lucia Romero, Angela Qian, Matthew Lyle Olson, Simon Stepputtis and Joseph Campbell. 2026. Bayesian Social Deduction with Graph-Informed Language Models. 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.1497

@inproceedings{rahimirad2026bayesian,
  title = {{Bayesian Social Deduction with Graph-Informed Language Models}},
  author = {Shahab Rahimirad, Guven Gergerli, Lucia Romero, Angela Qian, Matthew Lyle Olson, Simon Stepputtis and Joseph Campbell},
  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.1497},
  url = {https://doi.org/10.18653/v1/2026.acl-long.1497}
}

References

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

  1. Janice Ahn, Rishu Verma, Renze Lou, Di Liu, Rui Zhang, and Wenpeng Yin. 2024. Large language models for mathematical reasoning: Progresses and challenges. In Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics: Student Research Workshop, pages…
  2. Nitay Alon, Lion Schulz, Jeffrey Rosenschein, and Peter Dayan. 2023. A (dis-)information theory of revealed and unrevealed preferences: Emerging deception and skepticism via theory of mind. Open Mind, 7:1–17. find
  3. Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sashank Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, a… — PaLM: Scaling Language Modeling with Pathways
  4. DeepSeek-AI. 2025. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. Preprint, arXiv:2501.12948.
  5. Limitations: Xiao Pan Ding, Henry M. Wellman, Yu Wang, Genyue Fu, and Kang Lee. 2015. Theory-of-mind training causes honest young children to lie. Psychological Science, 26(11):1812–1821. PMID: 26431737. find
  6. GRAIL was designed as a Good agent for detecting rather than generating deception, using first-order Theory of Mind. Generating deception or persuasion (e.g., as in Merlin) requires second-order reasoning, which builds on a strong first-order foun-Jinhao Duan, Renming Zhang, James Diffenderfer, Bhav… find
  7. 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
  8. Don Eskridge. 2012. The resistance: Avalon. Board game. find
  9. Meta Fundamental AI Research Diplomacy Team (FAIR)†, Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, Athul Paul Jacob, Mojtaba Komeili, Karthik Konath, Minae Kwon, Adam Lerer, Mike Lewis, Alexander H. Miller, Sasha Mitts… find
  10. Jiawei Gu, Xuhui Jiang, Zhichao Shi, Hexiang Tan, Xuehao Zhai, Chengjin Xu, Wei Li, Yinghan Shen, Shengjie Ma, Honghao Liu, Saizhuo Wang, Kun Zhang, Yuanzhuo Wang, Wen Gao, Lionel Ni, and Jian Guo. 2025. A survey on llm-as-a-judge. Preprint, arXiv:2411.15594. find
  11. Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. 2017. On calibration of modern neural networks. Preprint, arXiv:1706.04599. find
  12. Jiaxian Guo, Bo Yang, Paul Yoo, Bill Yuchen Lin, Yusuke Iwasawa, and Yutaka Matsuo. 2024. Suspicion-agent: Playing imperfect information games with theory of mind aware gpt-4. Preprint, arXiv:2309.17277. — [arXiv:2309.17277](https://arxiv.org/abs/2309.17277) find
  13. Mark K. Ho, Rebecca Saxe, and Fiery Cushman. 2022. Planning with theory of mind. Trends in Cognitive Sciences, 26(11):959–971. find
  14. Samee Ibraheem, Gaoyue Zhou, and John DeNero. 2022. Putting the con in context: Identifying deceptive actors in the game of mafia. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 158–168, Seattle… find
  15. Michal Kosinski. 2024. Evaluating large language models in theory of mind tasks. Proceedings of the National Academy of Sciences, 121(45).
  16. F.R. Kschischang, B.J. Frey, and H.-A. Loeliger. 2001. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2):498–519. find
  17. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles.
  18. Bolin Lai, Hongxin Zhang, Miao Liu, Aryan Pariani, Fiona Ryan, Wenqi Jia, Shirley Anugrah Hayati, James Rehg, and Diyi Yang. 2023. Werewolf among us: Multimodal resources for modeling persuasion behaviors in social deduction games. In Findings of the Association for Computational Linguistics: ACL 20… find
  19. Yihuai Lan, Zhiqiang Hu, Lei Wang, Yang Wang, Deheng Ye, Peilin Zhao, Ee-Peng Lim, Hui Xiong, and Hao Wang. 2024. Llm-based agent society investigation: Collaboration and confrontation in avalon gameplay. Preprint, arXiv:2310.14985. find
  20. Huao Li, Yu Chong, Simon Stepputtis, Joseph Campbell, Dana Hughes, Charles Lewis, and Katia Sycara. 2023. Theory of mind for multi-agent collaboration via large language models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 180–192, Singapore. Assoc…
  21. Jonathan Light, Min Cai, Sheng Shen, and Ziniu Hu. 2023. Avalonbench: Evaluating llms playing the game of avalon. Preprint, arXiv:2310.05036. — [arXiv:2310.05036](https://arxiv.org/abs/2310.05036) find
  22. Ziyi Liu, Abhishek Anand, Pei Zhou, Jen-tse Huang, and Jieyu Zhao. 2024. InterIntent: Investigating social intelligence of LLMs via intention understanding in an interactive game context. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 6718–6746, Miam… find
  23. Niloofar Mireshghallah, Hyunwoo Kim, Xuhui Zhou, Yulia Tsvetkov, Maarten Sap, Reza Shokri, and Yejin Choi. 2024. Can LLMs keep a secret? testing privacy implications of language models via contextual integrity theory. In The Twelfth International Conference on Learning Representations. find
  24. Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. 2025. s1: Simple test-time scaling. Preprint, arXiv:2501.19393.
  25. Kevin P. Murphy, Yair Weiss, and Michael I. Jordan. 1999. Loopy belief propagation for approximate inference: an empirical study. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, UAI’99, page 467–475, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc. find
  26. OpenAI. 2025. Introducing openai o3 and o4-mini. Accessed 2025-05-09. find
  27. Shuofei Qiao, Yixin Ou, Ningyu Zhang, Xiang Chen, Yunzhi Yao, Shumin Deng, Chuanqi Tan, Fei Huang, and Huajun Chen. 2023. Reasoning with language model prompting: A survey. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5368–…
  28. Michael D. Richard and Richard P. Lippmann. 1991. Neural network classifiers estimate bayesian a posteriori probabilities. Neural Computation, 3(4):461– 483. find
  29. Matthew Riemer, Zahra Ashktorab, Djallel Bouneffouf, Payel Das, Miao Liu, Justin D. Weisz, and Murray Campbell. 2025. Position: Theory of mind benchmarks are broken for large language models. Preprint, arXiv:2412.19726. — [arXiv:2412.19726](https://arxiv.org/abs/2412.19726) find
  30. Bidipta Sarkar, Warren Xia, C. Karen Liu, and Dorsa Sadigh. 2025. Training language models for social deduction with multi-agent reinforcement learning. Preprint, arXiv:2502.06060. — [arXiv:2502.06060](https://arxiv.org/abs/2502.06060) find
  31. Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo. 2023. Are emergent abilities of large language models a mirage? In Thirty-seventh Conference on Neural Information Processing Systems.
  32. Jacob Schreiber. 2018. Pomegranate: fast and flexible probabilistic modeling in python. Journal of Machine Learning Research, 18(164):1–6. find
  33. Eli Schwartz, Leshem Choshen, Joseph Shtok, Sivan Doveh, Leonid Karlinsky, and Assaf Arbelle. 2024. NumeroLogic: Number encoding for enhanced LLMs’ numerical reasoning. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 206–212, Miami, Florida, USA. Asso… find
  34. Melanie Sclar, Sachin Kumar, Peter West, Alane Suhr, Yejin Choi, and Yulia Tsvetkov. 2023. Minding language models’ (lack of) theory of mind: A plug-and-play multi-character belief tracker. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pap…
  35. Jack Serrino, Max Kleiman-Weiner, David C Parkes, and Josh Tenenbaum. 2019. Finding friend and foe in multi-agent games. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc. find
  36. Natalie Shapira, Mosh Levy, Seyed Hossein Alavi, Xuhui Zhou, Yejin Choi, Yoav Goldberg, Maarten Sap, and Vered Shwartz. 2024. Clever hans or neural theory of mind? stress testing social reasoning in large language models. In Proceedings of the 18th Conference of the European Chapter of the Associati… find
  37. Mrinank Sharma, Meg Tong, Tomasz Korbak, David Duvenaud, Amanda Askell, Samuel R. Bowman, Esin DURMUS, Zac Hatfield-Dodds, Scott R Johnston, Shauna M Kravec, Timothy Maxwell, Sam Mc-Candlish, Kamal Ndousse, Oliver Rausch, Nicholas Schiefer, Da Yan, Miranda Zhang, and Ethan Perez. 2024. Towards under…
  38. David Smith and Vibhav Gogate. 2014. Loopy Belief Propagation in the Presence of Determinism. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, volume 33 of Proceedings of Machine Learning Research, pages 895–903, Reykjavik, Iceland. PMLR. find
  39. Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. 2024. Scaling llm test-time compute optimally can be more effective than scaling model parameters. Preprint, arXiv:2408.03314.
  40. Simon Stepputtis, Joseph Campbell, Yaqi Xie, Zhengyang Qi, Wenxin Zhang, Ruiyi Wang, Sanketh Rangreji, Charles Lewis, and Katia Sycara. 2023. Long-horizon dialogue understanding for role identification in the game of avalon with large language models. In Findings of the Association for Computational… find
  41. James W. A. Strachan, Dalila Albergo, Giulia Borghini, Oriana Pansardi, Eugenio Scaliti, Saurabh Gupta, Krati Saxena, Alessandro Rufo, Stefano Panzeri, Guido Manzi, Michael S. A. Graziano, and Cristina Becchio. 2024. Testing theory of mind in large language models and humans. Nature Human Behaviour,… find
  42. Qwen Team. 2025. Qwq-32b: Embracing the power of reinforcement learning. find
  43. Tomer Ullman. 2023. Large language models fail on trivial alterations to theory-of-mind tasks. Preprint, arXiv:2302.08399. find
  44. Martin J. Wainwright and Michael I. Jordan. 2008. Graphical models, exponential families, and variational inference. Foundations and Trends® in Machine Learning, 1(1–2):25–34. find
  45. Shenzhi Wang, Chang Liu, Zilong Zheng, Siyuan Qi, Shuo Chen, Qisen Yang, Andrew Zhao, Chaofei Wang, Shiji Song, and Gao Huang. 2023. Avalon’s game of thoughts: Battle against deception through recursive contemplation. Preprint, arXiv:2310.01320. — [arXiv:2310.01320](https://arxiv.org/abs/2310.01320) find
  46. 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 Advances in Neural Information Processing Systems.
  47. Shuang Wu, Liwen Zhu, Tao Yang, Shiwei Xu, Qiang Fu, Yang Wei, and Haobo Fu. 2024. Enhance reasoning for large language models in the game werewolf. Preprint, arXiv:2402.02330. — [arXiv:2402.02330](https://arxiv.org/abs/2402.02330) find
  48. Fengli Xu, Qianyue Hao, Zefang Zong, Jingwei Wang, Yunke Zhang, Jingyi Wang, Xiaochong Lan, Jiahui Gong, Tianjian Ouyang, Fanjin Meng, Chenyang Shao, Yuwei Yan, Qinglong Yang, Yiwen Song, Sijian Ren, Xinyuan Hu, Yu Li, Jie Feng, Chen Gao, and Yong Li. 2025. Towards large reasoning models: A survey o… find
  49. Xueyang Zhou, Guiyao Tie, Guowen Zhang, Weidong Wang, Zhigang Zuo, Di Wu, Duanfeng Chu, Pan Zhou, Lichao Sun, and Neil Zhenqiang Gong. 2025. Large reasoning models in agent scenarios: Exploring the necessity of reasoning capabilities. Preprint, arXiv:2503.11074. — [arXiv:2503.11074](https://arxiv.org/abs/2503.11074) find
  50. Lin Xu, Zhiyuan Hu, Daquan Zhou, Hongyu Ren, Zhen Dong, Kurt Keutzer, See-Kiong Ng, and Jiashi Feng. 2024a. MAgIC: Investigation of large language model powered multi-agent in cognition, adaptability, rationality and collaboration. In Proceedings of the 2024 Conference on Empirical Methods in Natura… find
  51. Yuzhuang Xu, Shuo Wang, Peng Li, Fuwen Luo, Xiaolong Wang, Weidong Liu, and Yang Liu. 2024b. Exploring large language models for communication games: An empirical study on werewolf. Preprint, arXiv:2309.04658.
  52. Zelai Xu, Chao Yu, Fei Fang, Yu Wang, and Yi Wu. 2024c. Language agents with reinforcement learning for strategic play in the werewolf game. Preprint, arXiv:2310.18940. — [arXiv:2310.18940](https://arxiv.org/abs/2310.18940) find
  53. Haotong Yang, Yi Hu, Shijia Kang, Zhouchen Lin, and Muhan Zhang. 2025. Number cookbook: Number understanding of language models and how to improve it. In The Thirteenth International Conference on Learning Representations. find
  54. Chen Yanover and Yair Weiss. 2003. Finding the m most probable configurations using loopy belief propagation. In Advances in Neural Information Processing Systems, volume 16. MIT Press. find
  55. Tong Yu, Yongcheng Jing, Xikun Zhang, Wentao Jiang, Wenjie Wu, Yingjie Wang, Wenbin Hu, Bo Du, and Dacheng Tao. 2025. Benchmarking reasoning robustness in large language models. Preprint, arXiv:2503.04550. — [arXiv:2503.04550](https://arxiv.org/abs/2503.04550) find
  56. Xuechen Zhang, Zijian Huang, Chenshun Ni, Ziyang Xiong, Jiasi Chen, and Samet Oymak. 2025. Making small language models efficient reasoners: Intervention, supervision, reinforcement. Preprint, arXiv:2505.07961. find
  57. Pei Zhou, Andrew Zhu, Jennifer Hu, Jay Pujara, Xiang Ren, Chris Callison-Burch, Yejin Choi, and Prithviraj Ammanabrolu. 2023. I cast detect thoughts: Learning to converse and guide with intents and theory-of-mind in dungeons and dragons. In Proceedings of the 61st Annual Meeting of the Association f… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/rahimirad-2026-bayesian-social-deduction-graph-informed/