Benchmarking and Enhancing Relational Diagrams Reasoning for Multimodal Large Language Models

Abstract

Multimodal Large Language Models (MLLMs) have achieved strong performance on a wide range of vision--language tasks. However, their capabilities remain unclear in relational-diagram (RD) reasoning, where correct answers must satisfy diagram-defined constraints such as directed dependencies, branching conditions, and prerequisite relations. RDs, including hierarchical diagrams, fishbone diagrams, and flowcharts, require models to not only retrieve nodes and relations, but also maintain valid reasoning paths over multi-step dependency chains. In this paper, we introduce RD-Bench, a large-scale benchmark of verified diagram--question pairs covering three diagram categories and four difficulty levels. RD-Bench evaluates hierarchical localization, branch-condition selection, constraint-guided traversal, step counting, and prerequisite identification. Experiments on representative open-source and proprietary MLLMs reveal a consistent limitation: models perform much better on single-step reasoning than on multi-step dependency reasoning, especially for complex flowcharts with branching logic and long-range prerequisites. To reduce this gap, we propose RD-MCTS, a Monte Carlo Tree Search framework that incorporates diagram-derived structural priors, constraint-consistent state transitions, and inference-time step-level process rewards. RD-MCTS guides search toward dependency-relevant nodes and valid next steps, improving constraint-consistent reasoning on high-difficulty questions.