Elamur Research⌕
☰
home / papers / 2026 / NG-Router: Graph-Supervised Multi-Agent Collaboration for Nutrition Question Answering

NG-Router: Graph-Supervised Multi-Agent Collaboration for Nutrition Question Answering

Paper · 2026 · Kaiwen Shi, Zheyuan Zhang, Zhengqing Yuan et al.

Summary

The paper tackles nutrition question answering, where a system must judge whether a food suits a particular person given their health conditions, habits and the food's nutritional profile. The authors see two obstacles. Single LLM agents reason poorly in this specialised domain, and no one agent or backbone is best for every query. Feeding models the full context also tends to bury the useful evidence. Building on the Graph QA setting of the NGQA benchmark, they propose NG-Router. It adds query and agent nodes to each question's knowledge graph and trains a heterogeneous GNN to output a probability distribution over agents. The training labels are soft and come from how well each agent actually performed. Final answers combine agent outputs, weighted by these probabilities. A second component uses gradients during training to find influential nodes and extract compact subgraphs, which removes irrelevant context. Across benchmarks and backbones, NG-Router beats single agents and ensemble methods. This shows that agent coordination can be learned from graph supervision instead of being hand-designed.

Key points

  • NGQA is built from NHANES and FNDDS data. Its graphs link users, health conditions, foods and nutrition tags. Experiments cover its Standard, Sparse and Complex datasets.
  • The ensemble baselines are Majority Vote, Hybrid LLM and LLM Blender.
    • On binary classification, NG-Router reaches 55.06 accuracy and 71.00 F1, compared with 53.38 and 69.67 for the best baseline.
    • On text generation, it scores ROUGE-1 70.88, BLEU 51.55 and BERTScore 96.14, all the highest.
  • Hyperparameter study:
    • Increasing the hidden size from 64 to 256 gives steady gains.
    • Adding layers beyond two or three tends to hurt on the Sparse and Complex datasets.
  • Cost profile:
    • Training requires querying every candidate agent to obtain supervision labels.
    • At inference, only the agent(s) chosen by the router are called.
  • The authors argue the approach could transfer to other expert-routing domains, such as legal, medical or financial reasoning.

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

🏢IBMArmonk · United States139 works · 70,691 citations🎓University of Notre DameNotre Dame · United States51 works · 36,717 citations🎓University of ConnecticutStorrs · United States11 works · 357 citations

 Fields, topics and concepts

📚 Shelves 6The 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 worksInformation Systems · 1,437 works

🧭 Topics 1Research subjects and languages the work is about.Question answering · 441 works

Cite

Cite as Kaiwen Shi, Zheyuan Zhang, Zhengqing Yuan, Keerthiram Murugesan, Vincent Galassi, Chuxu Zhang and Yanfang Ye. 2026. NG-Router: Graph-Supervised Multi-Agent Collaboration for Nutrition Question Answering. 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.352

@inproceedings{shi2026ng,
  title = {{NG-Router: Graph-Supervised Multi-Agent Collaboration for Nutrition Question Answering}},
  author = {Kaiwen Shi, Zheyuan Zhang, Zhengqing Yuan, Keerthiram Murugesan, Vincent Galassi, Chuxu Zhang and Yanfang Ye},
  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.352},
  url = {https://doi.org/10.18653/v1/2026.eacl-long.352}
}

References

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

  1. Ashkan Afshin, Patrick J Sur, Kairsten A Fay, Leslie Cornaby, Giannina Ferrara, Jason S Salama, and Christopher J L Murray. 2019. Health effects of dietary risks in 195 countries, 1990–2017: a systematic analysis for the global burden of disease study 2017. The Lancet. find
  2. Qwen Alibaba. 2025. Qwen2.5-7b-instruct. https://huggingface.co/Qwen/Qwen2.5-7B-Instruct. ↗
  3. Jinheon Baek, Alham Fikri Aji, and Amir Saffari. 2023. Knowledge-augmented language model prompting for zero-shot knowledge graph question answering. In ACL.
  4. Felix Bölz, Diana Nurbakova, Sylvie Calabretto, Armin Gerl, Lionel Brunie, and Harald Kosch. 2023. Hummus: A linked, healthiness-aware, user-centered and argument-enabling recipe data set for recommendation. In RecSys. find
  5. Jon Nicolas Bondevik, Kwabena Ebo Bennin, Önder Babur, and Carsten Ersch. 2024. A systematic review on food recommender systems. Expert Systems with Applications. find
  6. Yuxuan Cao, Jiarong Xu, Carl Yang, Jiaan Wang, Yunchao Zhang, Chunping Wang, Lei Chen, and Yang Yang. 2023. When to pre-train graph neural networks? from data generation perspective! In KDD. find
  7. CDC. 2020. Adult obesity facts. find
  8. Justin Chih-Yao Chen, Swarnadeep Saha, and Mohit Bansal. 2024a. Reconcile: Round-table conference improves reasoning via consensus among diverse LLMs. In ACL.
  9. Shuhao Chen, Weisen Jiang, Baijiong Lin, James Kwok, and Yu Zhang. 2024b. Routerdc: Query-based router by dual contrastive learning for assembling large language models. NeurIPS. find
  10. Weize Chen, Yusheng Su, Jingwei Zuo, Cheng Yang, Chenfei Yuan, Chi-Min Chan, Heyang Yu, Yaxi Lu, Yi-Hsin Hung, Chen Qian, et al. 2024c. Agentverse: Facilitating multi-agent collaboration and exploring emergent behaviors. In ICLR.
  11. D. Ding, Ankur Mallick, Shaokun Zhang, Chi Wang, et al. 2025. Best-route: Adaptive llm routing with test-time optimal compute. In ICML. find
  12. Dujian Ding, Ankur Mallick, Chi Wang, Robert Sim, Subhabrata Mukherjee, Victor Ruhle, Laks VS Lakshmanan, and Ahmed Hassan Awadallah. 2024. Hybridllm: Cost-efficient and quality-aware query routing. In ICLR. find
  13. Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. 2024. Improving factuality and reasoning in language models through multi-agent debate. In ICML. find
  14. Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. 2023. Talk like a graph: Encoding graphs for large language models. arXiv. find
  15. Yihan Feng, Tianyu Zhao, Haotian Liu, Diyi Yang, and Tuo Zhao. 2025. Graphrouter: Learning graph-based routing for large language model selection. In ICLR. find
  16. Yifu Gao, Linbo Qiao, Zhigang Kan, Zhihua Wen, Yongquan He, and Dongsheng Li. 2024. Two-stage generative question answering on temporal knowledge graph using large language models. arXiv. find
  17. Mouzhi Ge, Francesco Ricci, and David Massimo. 2015. Health-aware food recommender system. In RecSys. find
  18. Tiezheng Guo, Qingwen Yang, Chen Wang, Yanyi Liu, Pan Li, Jiawei Tang, Dapeng Li, and Yingyou Wen. 2024. Knowledgenavigator: Leveraging large language models for enhanced reasoning over knowledge graph. Complex & Intelligent Systems. find
  19. Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. NeurIPS.
  20. Xiaoxin He, Yijun Tian, Yifei Sun, Nitesh V Chawla, Thomas Laurent, Yann LeCun, Xavier Bresson, and Bryan Hooi. 2024. G-retriever: Retrieval-augmented generation for textual graph understanding and question answering. arXiv.
  21. Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, et al. 2024. Metagpt: Meta programming for a multi-agent collaborative framework. In ICLR.
  22. Jiho Kim, Yeonsu Kwon, Yohan Jo, and Edward Choi. 2023. Kg-gpt: A general framework for reasoning on knowledge graphs using large language models. In EMNLP. find
  23. Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv.
  24. Angeliki Lazaridou, Elena Gribovskaya, Wojciech Stokowiec, and Nikolai Grigorev. 2022. Internet-augmented language models through few-shot prompting for open-domain question answering. arXiv.
  25. Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. NeuralIPS.
  26. Zheyuan Liu, Xiaoxin He, Yijun Tian, and Nitesh V Chawla. 2024. Can we soft prompt llms for graph learning tasks? In WWW, pages 481–484. find
  27. Tianyi Ma, Yiyue Qian, Zheyuan Zhang, Zehong Wang, Xiaoye Qian, Feifan Bai, Yifan Ding, Xuwei Luo, Shinan Zhang, Keerthiram Murugesan, et al. 2025. Autodata: A multi-agent system for open web data collection. arXiv preprint arXiv:2505.15859. — [arXiv:2505.15859](https://arxiv.org/abs/2505.15859) find
  28. MetaAI. 2024. Llama-3.2-3b-instruct. https://hugg ingface.co/meta-llama/Llama-3.2-3B-Instr uct. find
  29. Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. 2023a. LLM-blender: Ensembling large language models with pairwise ranking and generative fusion. In ACL.
  30. Weiqing Min, Chunlin Liu, Leyi Xu, and Shuqiang Jiang. 2022. Applications of knowledge graphs for food science and industry. Patterns. find
  31. Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Wayne Xin Zhao, and Ji-Rong Wen. 2023b. Structgpt: A general framework for large language model to reason over structured data. In EMNLP. find
  32. MistralAI. 2024. Mistral-7b-instruct-v0.2. https://huggingface.co/mistralai/Mistral-7B-Instr uct-v0.2. ↗
  33. Jinhao Jiang, Kun Zhou, Wayne Xin Zhao, Yang Song, Chen Zhu, Hengshu Zhu, and Ji-Rong Wen. 2024. Kg-agent: An efficient autonomous agent framework for complex reasoning over knowledge graph. arXiv.
  34. Bo Ni, Zheyuan Liu, Leyao Wang, Yongjia Lei, Yuying Zhao, Xueqi Cheng, Qingkai Zeng, Luna Dong, Yinglong Xia, Krishnaram Kenthapadi, et al. 2025. Towards trustworthy retrieval augmented generation for large language models: A survey. arXiv.
  35. Bowen Jin, Chulin Xie, Jiawei Zhang, Kashob Kumar Roy, Yu Zhang, Zheng Li, Ruirui Li, Xianfeng Tang, Suhang Wang, Yu Meng, et al. 2024. Graph chain-of-thought: Augmenting large language models by reasoning on graphs. In ACL.
  36. Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E. Gonzalez, M. Waleed Kadous, and Ion Stoica. 2025. Routellm: Learning to route llms with preference data. In ICLR. find
  37. Mingxuan Ju, Shifu Hou, Yujie Fan, Jianan Zhao, Yanfang Ye, and Liang Zhao. 2022a. Adaptive kernel graph neural network. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pages 7051–7058. find
  38. OpenAI. 2024. Gpt-4o mini: advancing cost-efficient intelligence. https://openai.com/index/gpt-4 o-mini-advancing-cost-efficient-intellige nce/. ↗
  39. Mingxuan Ju, Wenhao Yu, Tong Zhao, Chuxu Zhang, and Yanfang Ye. 2022b. Grape: Knowledge graph enhanced passage reader for open-domain question answering. arXiv preprint arXiv:2210.02933. find
  40. Boci Peng, Yun Zhu, Yongchao Liu, Xiaohe Bo, Haizhou Shi, Chuntao Hong, Yan Zhang, and Siliang Tang. 2024. Graph retrieval-augmented generation: A survey. arXiv.
  41. Chen Qian, Zihao Xie, YiFei Wang, Wei Liu, Kunlun Zhu, Hanchen Xia, Yufan Dang, Zhuoyun Du, Weize Chen, Cheng Yang, et al. 2025. Scaling large language model-based multi-agent collaboration. In ICLR. find
  42. Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. 2023. Reflexion: Language agents with verbal reinforcement learning. NeurIPS.
  43. Sola S Shirai, Oshani Seneviratne, Minor E Gordon, Ching-Hua Chen, and Deborah L McGuinness. 2021. Identifying ingredient substitutions using a knowledge graph of food. Frontiers in Artificial Intelligence. find
  44. D. Stripelis et al. 2024. A multi-model router for efficient llm inference. In EMNLP. find
  45. Haitian Sun, Tania Bedrax-Weiss, and William Cohen. 2019. Pullnet: Open domain question answering with iterative retrieval on knowledge bases and text. In EMNLP-IJCNLP. find
  46. Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel Ni, Heung-Yeung Shum, and Jian Guo. 2024. Think-on-graph: Deep and responsible reasoning of large language model on knowledge graph. In ICLR. find
  47. Dhaval Taunk, Lakshya Khanna, Siri Venkata Pavan Kumar Kandru, Vasudeva Varma, Charu Sharma, and Makarand Tapaswi. 2023. Grapeqa: Graph augmentation and pruning to enhance question-answering. In WWW. find
  48. Y Tian, C Zhang, Z Guo, C Huang, R Metoyer, and N Chawla. 2022a. Reciperec: A heterogeneous graph learning model for recipe recommendation. In IJCAI. find
  49. Yijun Tian, Chuxu Zhang, Zhichun Guo, Yihong Ma, Ronald Metoyer, and Nitesh V Chawla. 2022b. Recipe2vec: Multi-modal recipe representation learning with graph neural networks. arXiv. find
  50. Yijun Tian, Chuxu Zhang, Ronald Metoyer, and Nitesh V Chawla. 2021. Recipe representation learning with networks. In CIKM. find
  51. Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv. find
  52. Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. 2024a. Can language models solve graph problems in natural language? NeuralIPS. find
  53. Junlin Wang, WANG Jue, Ben Athiwaratkun, Ce Zhang, and James Zou. 2025a. Mixture-of-agents enhances large language model capabilities. In ICLR. find
  54. Wenjie Wang, Ling-Yu Duan, Hao Jiang, Peiguang Jing, Xuemeng Song, and Liqiang Nie. 2021. Market2dish: health-aware food recommendation. TOMM. find
  55. X. Wang, Y. Fu, Y. Zhang, W. Cheng, et al. 2025b. Mixllm: Dynamic routing in mixed large language models. In NAACL. find
  56. Xintao Wang, Qianwen Yang, Yongting Qiu, Jiaqing Liang, Qianyu He, Zhouhong Gu, Yanghua Xiao, and Wei Wang. 2023a. Knowledgpt: Enhancing large language models with retrieval and storage access on knowledge bases. arXiv. find
  57. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, and Denny Zhou. 2023b. Self-consistency improves chain of thought reasoning in language models. In ICLR.
  58. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2022. Self-consistency improves chain of thought reasoning in language models. In ICLR.
  59. Zehong Wang, Sidney Liu, Zheyuan Zhang, Tianyi Ma, Chuxu Zhang, and Yanfang Ye. 2025c. Can llms convert graphs to text-attributed graphs? In NAACL. find
  60. Zehong Wang, Zheyuan Zhang, Nitesh Chawla, Chuxu Zhang, and Yanfang Ye. 2024b. Gft: Graph foundation model with transferable tree vocabulary. NeruIPS. find
  61. Zehong Wang, Zheyuan Zhang, Tianyi Ma, Nitesh V Chawla, Chuxu Zhang, and Yanfang Ye. 2025d. Learning cross-task generalities across graphs via task-trees. ICML. find
  62. Zehong Wang, Zheyuan Zhang, Tianyi Ma, Nitesh V Chawla, Chuxu Zhang, and Yanfang Ye. 2025e. Neural graph pattern machine. ICML. find
  63. Zehong Wang, Zheyuan Zhang, Chuxu Zhang, and Yanfang Ye. 2024c. Subgraph pooling: tackling negative transfer on graphs. In IJCAI. find
  64. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022. Chain-of-thought prompting elicits reasoning in large language models. NeuralIPS.
  65. Yilin Wen, Zifeng Wang, and Jimeng Sun. 2023. Mindmap: Knowledge graph prompting sparks graph of thoughts in large language models. arXiv.
  66. WHO. 2023. Obesity info page of the world health organization. find
  67. 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 ICLR.
  68. Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. 2021. Qa-gnn: Reasoning with language models and knowledge graphs for question answering. In NAACL. find
  69. Yanfang Ye, Zheyuan Zhang, Tianyi Ma, Zehong Wang, Yiyang Li, Shifu Hou, Weixiang Sun, Kaiwen Shi, Yijun Ma, Wei Song, et al. 2025. Llms4all: A review of large language models across academic disciplines. arXiv preprint arXiv:2509.19580. — [arXiv:2509.19580](https://arxiv.org/abs/2509.19580) find
  70. Wenbin Yue, Zidong Wang, Jieyu Zhang, and Xiaohui Liu. 2021. An overview of recommendation techniques and their applications in healthcare. IEEE/CAA Journal of Automatica Sinica. conference on machine learning and knowledge discovery in databases, pages 319–334. Springer. find
  71. Li Zhong, Zilong Wang, and Jingbo Shang. 2024. Debug like a human: A large language model debugger via verifying runtime execution step by step. In Findings of ACL. find
  72. Jing Zhang, Xiaokang Zhang, Jifan Yu, Jian Tang, Jie Tang, Cuiping Li, and Hong Chen. 2022. Subgraph retrieval enhanced model for multi-hop knowledge base question answering. In ACL. find
  73. Lingzi Zhang, Yinan Zhang, Xin Zhou, and Zhiqi Shen. 2024a. Greenrec: A large-scale dataset for green food recommendation. In WWW. find
  74. Zheyuan Zhang, Lin Ge, Hongjiang Li, Weicheng Zhu, Chuxu Zhang, and Yanfang Ye. 2025a. Mapro: Recasting multi-agent prompt optimization as maximum a posteriori inference. arXiv.
  75. Zheyuan Zhang, Yiyang Li, Nhi Ha Lan Le, Zehong Wang, Tianyi Ma, Vincent Galassi, Keerthiram Murugesan, Nuno Moniz, Werner Geyer, Nitesh V Chawla, et al. 2025b. Ngqa: A nutritional graph question answering benchmark for personalized health-aware nutritional reasoning. ACL. find
  76. Zheyuan Zhang, Kaiwen Shi, Zhengqing Yuan, Zehong Wang, Tianyi Ma, Keerthiram Murugesan, Vincent Galassi, Chuxu Zhang, and Yanfang Ye. 2025c. Agentrouter: A knowledge-graph-guided llm router for collaborative multi-agent question answering. arXiv.
  77. Zheyuan Zhang, Zehong Wang, Shifu Hou, Evan Hall, Landon Bachman, Jasmine White, Vincent Galassi, Nitesh V Chawla, Chuxu Zhang, and Yanfang Ye. 2024b. Diet-odin: A novel framework for opioid misuse detection with interpretable dietary patterns. In Proceedings of the 30th ACM SIGKDD Conference on Kno… find
  78. Zheyuan Zhang, Zehong Wang, Tianyi Ma, Varun Sameer Taneja, Sofia Nelson, Nhi Ha Lan Le, Keerthiram Murugesan, Mingxuan Ju, Nitesh V Chawla, Chuxu Zhang, et al. 2024c. Mopi-hfrs: A multi-objective personalized health-aware food recommendation system with llm-enhanced interpretation. arXiv. find
  79. Jianan Zhao, Qianlong Wen, Mingxuan Ju, Chuxu Zhang, and Yanfang Ye. 2023. Self-supervised graph structure refinement for graph neural networks. In Proceedings of the sixteenth ACM international conference on web search and data mining, pages 159– 167. find
  80. Jianan Zhao, Qianlong Wen, Shiyu Sun, Yanfang Ye, and Chuxu Zhang. 2021. Multi-view self-supervised heterogeneous graph embedding. In Joint European find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/shi-2026-ng-router-graph-supervised-multi/