LLM Reasoning with Graphs

LLM: Large Language Model

Ask about this topic

Overview

The field studies how large language models can use graphs to represent relationships, retrieve evidence, and organize multi-step reasoning, especially when answers depend on several connected facts. Common approaches include retrieving paths or subgraphs from knowledge graphs for tasks such as WebQSP and CWQ question answering, giving models tools to navigate graphs, and integrating graph neural networks, symbolic rules, or executable code with language-model reasoning. Other work represents reasoning itself as a chain, tree, or directed graph, and trains models with supervised traces or reinforcement learning to explore paths and verify intermediate steps. These methods can improve multi-hop accuracy and make evidence easier to inspect, but benchmarks also show that graph information is not always used correctly; handling incomplete or noisy evidence, scaling to larger graphs, and demonstrating genuine structural understanding remain open challenges.

Latest papers

CardsList

211 papers28 papers in the last four weeks, up 12% on the four weeks before. 0.2% of all new papers.

Apr 8, 2026

ROZA Graphs: Self-Improving Near-Deterministic RAG through Evidence-Centric Feedback

Language model agents reason from scratch on every query, discarding their chain of thought after each run. The result is lower accuracy and high run-to-run variance. We introduce reasoning graphs, which persist the per-evidence chain of thought as structured edges. Unlike prior memory that retrieves distilled strategies by query similarity, reasoning graphs enable evidence-centric feedback: for every candidate item, the system traverses all incoming evaluation edges across prior runs to surface how that specific item has been judged before. We further introduce retrieval graphs, which feed a planner that prunes consistently-rejected candidates over successive runs. Together they form a ROZA graph: a self-improving feedback loop in which accuracy gains scale with gold-passage reuse (reasoning graph) and efficiency gains scale with candidate-pool overlap (retrieval graph). The base model remains frozen; all gains come from context engineering via graph traversal. We evaluate on MuSiQue and HotpotQA, plus a high-reuse deployment subset. Four findings stand out. (1) Dose-response: accuracy improves monotonically with evidence-profile coverage, reaching +10.6pp over Vanilla RAG at 50%+ coverage on the same questions (47% error reduction, p<0.0001p<0.0001; per-question Spearman ρ=+0.144ρ=+0.144, p<10−6p<10^{-6}, n=1,100n=1{,}100). (2) Multi-hop scaling: 4-hop accuracy improves by +11.0pp (p=0.0001p=0.0001). (3) Cross-cluster prediction: the cluster-level gain is predicted by gold-passage reuse density (r=0.604r=0.604, p=0.001p=0.001, n=26n=26 clusters). (4) High-reuse Pareto dominance: highest or tied-for-highest accuracy alongside 46% lower cost and 46% lower latency. Per-passage decision consistency across repeated runs (N=73N=73 paired probes, K=10K=10 runs each, two model families, three temperatures) rises by +8 to +13pp on a fixed 20-passage context and by +12 to +21pp when the retrieval graph also prunes (all p<0.005p<0.005).

Matthew Penaroza

Retrieval-Augmented GenerationGraph Retrieval-Augmented GenerationLLM Reasoning with GraphsMemory-Augmented Language Model AgentsReasoning Consistency in Language Models
AskPDF
Apr 8, 2026

From Business Events to Auditable Decisions: Ontology-Governed Graph Simulation for Enterprise AI

Existing LLM-based agent systems share a common architectural failure: they answer from the unrestricted knowledge space without first simulating how active business scenarios reshape that space for the event at hand -- producing decisions that are fluent but ungrounded and carrying no audit trail. We present LOM-action, which equips enterprise AI with event-driven ontology simulation: business events trigger scenario conditions encoded in the enterprise ontology~(EO), which drive deterministic graph mutations in an isolated sandbox, evolving a working copy of the subgraph into the scenario-valid simulation graph GsimG_{\text{sim}}; all decisions are derived exclusively from this evolved graph. The core pipeline is \emph{event →\to simulation →\to decision}, realized through a dual-mode architecture -- skill mode and reasoning mode. Every decision produces a fully traceable audit log. LOM-action achieves 93.82% accuracy and 98.74% tool-chain F1 against frontier baselines Doubao-1.8 and DeepSeek-V3.2, which reach only 24--36% F1 despite 80% accuracy -- exposing the illusive accuracy phenomenon. The four-fold F1 advantage confirms that ontology-governed, event-driven simulation, not model scale, is the architectural prerequisite for trustworthy enterprise decision intelligence.

Hongyin Zhu, Jinming Liang, Mengjun Hou +5

Yonyou AI Lab · Yonyou Network Technology Co., Ltd.

Ontology-Based ReasoningLLM Decision-MakingLLM Reasoning with GraphsAI Agent Auditing
AskPDF
Apr 5, 2026

Schema-Aware Planning and Hybrid Knowledge Toolset for Reliable Knowledge Graph Triple Verification

Knowledge Graphs (KGs) provide a critical foundation for many AI systems, yet their automated construction inevitably introduces noisy triples that undermine data trustworthiness. Reliable KG auditing requires jointly examining internal structural constraints and open-world evidence, whereas existing methods often rely on a single evidence source or static, one-shot inference, limiting adaptive evidence acquisition and auditability. We propose SHARP (Schema-Hybrid Agent for Reliable Prediction), a training-free agent that reformulates triple verification as a dynamic process of strategic planning, active investigation, and evidential reasoning. SHARP uses retrieved historical verification trajectories and entity--relation schema information to construct a task-specific investigation plan. It then iteratively coordinates KG and textual tools to cross-validate structural and semantic evidence, producing a verification verdict with a transparent evidence chain. On independently sampled, balanced test sets constructed from FB15K-237 and Wikidata5M-Ind, SHARP achieves average accuracies of 87.1% and 93.6%, respectively. Controlled comparisons with standard RAG using the same evidence sources, together with ablation studies, further show that the gains arise not merely from external retrieval, but from the combined effects of schema-aware planning, memory augmentation, and iterative hybrid tool use.

Xinyan Ma, Xianhao Ou, Chang Li +6

Harbin Institute of Technology, China · Huawei Technologies Co., Ltd., China

Knowledge GraphsAutomated Fact-CheckingLLM Reasoning with GraphsKG Construction
AskPDF
Apr 5, 2026

Unmasking Hallucinations: A Causal Graph-Attention Perspective on Factual Reliability in Large Language Models

This paper primarily focuses on the hallucinations caused due to AI language models(LLMs).LLMs have shown extraordinary Language understanding and generation capabilities .Still it has major a disadvantage hallucinations which give outputs which are factually incorrect ,misleading or unsupported by input data . These hallucinations cause serious problems in scenarios like medical diagnosis or legal reasoning.Through this work,we propose causal graph attention network (GCAN) framework that reduces hallucinations through interpretation of internal attention flow within a transformer architecture with the help of constructing token level graphs that combine self attention weights and gradient based influence scores.our method quantifies each tokens factual dependency using a new metric called the Causal Contribution Score (CCS). We further introduce a fact-anchored graph reweighting layer that dynamically reduces the influence of hallucination prone nodes during generation. Experiments on standard benchmarks such as TruthfulQA and HotpotQA show a 27.8 percent reduction in hallucination rate and 16.4 percent improvement in factual accuracy over baseline retrieval-augmented generation (RAG) models. This work contributes to the interpretability,robustness, and factual reliability of future LLM architectures.

Sailesh kiran kurra, Shiek Ruksana, Vishal Borusu

Amazon,Texas, United States of America · Vasavi College of Engineering, Telangana,India

LLM Hallucination MitigationFactual Knowledge in Language ModelsLLM InterpretabilityCausal Interventions in Language ModelsLLM Reasoning with Graphs
AskPDF
Apr 4, 2026

When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression

Reasoning hallucinations in large language models (LLMs) often appear as fluent yet unsupported conclusions that violate either the given context or underlying factual knowledge. Although such failures are widely observed, the mechanisms by which decoder-only Transformers produce them remain poorly understood. We model next-token prediction as a graph search process over an underlying graph, where entities correspond to nodes and learned transitions form edges. From this perspective, contextual reasoning is a constrained search over a sampled subgraph (intrinsic reasoning), while context-free queries rely on memorized structures in the underlying graph (extrinsic reasoning). We show that reasoning hallucinations arise from two fundamental mechanisms: Path Reuse, where memorized knowledge overrides contextual constraints during early training, and Path Compression, where frequently traversed multi-step paths collapse into shortcut edges in later training. Together, these mechanisms provide a unified explanation for reasoning hallucinations in LLMs and connected to well-known behaviors observed in downstream applications.

Xinnan Dai, Kai Yang, Cheng Luo +3

Michigan State University · University of Michigan · Independent Researcher

Hallucination in Language ModelsKnowledge Conflicts in Language ModelsLLM Reasoning with GraphsLLM Memory
AskPDF
Apr 3, 2026

Analysis of Optimality of Large Language Models on Planning Problems

Classic AI planning problems have been revisited in the Large Language Model (LLM) era, with a focus of recent benchmarks on success rates rather than plan efficiency. We examine the degree to which frontier models reason optimally versus relying on simple, heuristic, and possibly inefficient strategies. We focus on the Blocksworld domain involving towers of labeled blocks which have to be moved from an initial to a goal configuration via a set of primitive actions. We also study a formally equivalent task, the generalized Path-Star (P∗P^*) graph, in order to isolate true topological reasoning from semantic priors. We systematically manipulate problem depth (the height of block towers), width (the number of towers), and compositionality (the number of goal blocks). Reasoning-enhanced LLMs significantly outperform traditional satisficing planners (e.g., LAMA) in complex, multi-goal configurations. Although classical search algorithms hit a wall as the search space expands, LLMs track theoretical optimality limits with near-perfect precision, even when domain-specific semantic hints are stripped away. To explain these surprising findings, we consider (and find evidence to support) two hypotheses: an active Algorithmic Simulation executed via reasoning tokens and a Geometric Memory that allows models to represent the P∗P^* topology as a navigable global geometry, effectively bypassing exponential combinatorial complexity.

Bernd Bohnet, Michael C. Mozer, Kevin Swersky +4

Google DeepMind

LLM PlanningSymbolic PlanningLLM Reasoning with Graphs
AskPDF
Apr 3, 2026

LLM+Graph@VLDB'2025 Workshop Summary

The integration of large language models (LLMs) with graph-structured data has become a pivotal and fast evolving research frontier, drawing strong interest from both academia and industry. The 2nd LLM+Graph Workshop, co-located with the 51st International Conference on Very Large Data Bases (VLDB 2025) in London, focused on advancing algorithms and systems that bridge LLMs, graph data management, and graph machine learning for practical applications. This report highlights the key research directions, challenges, and innovative solutions presented by the workshop's speakers.

Yixiang Fang, Arijit Khan, Tianxing Wu +2

The Chinese University of Hong Kong, Shenzhen · Bowling Green State University · Southeast University +1

LLMs for Graph LearningLLM Reasoning with Graphs
AskPDF
Apr 2, 2026

GraphWalk: Enabling Reasoning in Large Language Models through Tool-Based Graph Navigation

The use of knowledge graphs for grounding agents in real-world Q&A applications has become increasingly common. Answering complex queries often requires multi-hop reasoning and the ability to navigate vast relational structures. Standard approaches rely on prompting techniques that steer large language models to reason over raw graph context, or retrieval-augmented generation pipelines where relevant subgraphs are injected into the context. These, however, face severe limitations with enterprise-scale KGs that cannot fit in even the largest context windows available today. We present GraphWalk, a problem-agnostic, training-free, tool-based framework that allows off-the-shelf LLMs to reason through sequential graph navigation, dramatically increasing performance across different tasks. Unlike task-specific agent frameworks that encode domain knowledge into specialized tools, GraphWalk equips the LLM with a minimal set of orthogonal graph operations sufficient to traverse any graph structure. We evaluate whether models equipped with GraphWalk can compose these operations into correct multi-step reasoning chains, where each tool call represents a verifiable step creating a transparent execution trace. We first demonstrate our approach on maze traversal, a problem non-reasoning models are completely unable to solve, then present results on graphs resembling real-world enterprise knowledge graphs. To isolate structural reasoning from world knowledge, we evaluate on entirely synthetic graphs with random, non-semantic labels. Our benchmark spans 12 query templates from basic retrieval to compound first-order logic queries. Results show that tool-based traversal yields substantial and consistent gains over in-context baselines across all model families tested, with gains becoming more pronounced as scale increases, precisely where in-context approaches fail catastrophically.

Taraneh Ghandi, Hamidreza Mahyar, Shachar Klaiman

Faculty of Science, McMaster University · BASF Digital Solutions

LLM Reasoning with GraphsLLM Tool UseKnowledge Graph Question AnsweringMulti-Hop Reasoning
AskPDF
Apr 1, 2026

Is One Token All It Takes? Graph Pooling Tokens for LLM-based GraphQA

The integration of Graph Neural Networks (GNNs) with Large Language Models (LLMs) has emerged as a promising paradigm for Graph Question Answering (GraphQA). However, effective methods for encoding complex structural information into the LLM's latent space remain an open challenge. Current state-of-the-art architectures, such as G-Retriever, typically rely on standard GNNs and aggressive mean pooling to compress entire graph substructures into a single token, creating a severe information bottleneck. This work mitigates this bottleneck by investigating two orthogonal strategies: (1) increasing the bandwidth of the graph-to-LLM interface via multi-token pooling, and (2) enhancing the semantic quality of the graph encoder via global attention mechanisms. We evaluate a suite of hierarchical pruning and clustering-based pooling operators including Top-k, SAGPool, DiffPool, MinCutPool, and Virtual Node Pooling (VNPool) to project graph data into multiple learnable tokens. Empirically, we demonstrate that while pooling introduces significant instability during soft prompt tuning, the application of Low-Rank Adaptation (LoRA) effectively stabilizes specific hierarchical projections (notably VNPool and pruning methods), though dense clustering operators remain challenging. This stabilization allows compressed representations to rival full-graph baselines (achieving ~73% Hit@1 on WebQSP). Conceptually, we demonstrate that a Graph Transformer with VNPool implementation functions structurally as a single-layer Perceiver IO encoder. Finally, we adapt the FandE (Features and Edges) Score to the generative GraphQA domain. Our analysis reveals that the GraphQA benchmark suffers from representational saturation, where target answers are often highly correlated with isolated node features. The implementation is available at https://github.com/Agrover112/G-Retriever/tree/all_good/

Ankit Grover, Lodovico Giaretta, Rémi Bourgerie +1

KTH Royal Institute of Technology, Stockholm, Sweden · RISE Research Institutes of Sweden, Stockholm, Sweden

LLM Reasoning with GraphsGraph PoolingKnowledge Graph Question AnsweringGraph Transformer
AskPDF
Mar 23, 2026

3D-Layout-R1: Structured Reasoning for Language-Instructed Spatial Editing

Large Language Models (LLMs) and Vision Language Models (VLMs) have shown impressive reasoning abilities, yet they struggle with spatial understanding and layout consistency when performing fine-grained visual editing. We introduce a Structured Reasoning framework that performs text-conditioned spatial layout editing via scene-graph reasoning. Given an input scene graph and a natural-language instruction, the model reasons over the graph to generate an updated scene graph that satisfies the text condition while maintaining spatial coherence. By explicitly guiding the reasoning process through structured relational representations, our approach improves both interpretability and control over spatial relationships. We evaluate our method on a new text-guided layout editing benchmark encompassing sorting, spatial alignment, and room-editing tasks. Our training paradigm yields an average 15% improvement in IoU and 25% reduction in center-distance error compared to Chain of Thought Fine-tuning (CoT-SFT) and vanilla GRPO baselines. Compared to SOTA zero-shot LLMs, our best models achieve up to 20% higher mIoU, demonstrating markedly improved spatial precision.

Haoyu Zhen, Xiaolong Li, Yilin Zhao +5

NVIDIA · UMass Amherst

Text-Guided 3D Scene Editing3D Scene Editing3D Spatial ReasoningLLM Reasoning with GraphsSpatial Reasoning Benchmarks
AskPDF
Mar 22, 2026

KG-Hopper: Empowering Compact Open LLMs with Knowledge Graph Reasoning via Reinforcement Learning

Large Language Models (LLMs) demonstrate impressive natural language capabilities but often struggle with knowledge-intensive reasoning tasks. Knowledge Base Question Answering (KBQA), which leverages structured Knowledge Graphs (KGs) exemplifies this challenge due to the need for accurate multi-hop reasoning. Existing approaches typically perform sequential reasoning steps guided by predefined pipelines, restricting flexibility and causing error cascades due to isolated reasoning at each step. To address these limitations, we propose KG-Hopper, a novel Reinforcement Learning (RL) framework that empowers compact open LLMs with the ability to perform integrated multi-hop KG reasoning within a single inference round. Rather than reasoning step-by-step, we train a Reasoning LLM that embeds the entire KG traversal and decision process into a unified ``thinking'' stage, enabling global reasoning over cross-step dependencies and dynamic path exploration with backtracking. Experimental results on eight KG reasoning benchmarks show that KG-Hopper, based on a 7B-parameter LLM, consistently outperforms larger multi-step systems (up to 70B) and achieves competitive performance with proprietary models such as GPT-3.5-Turbo and GPT-4o-mini, while remaining compact, open, and data-efficient. The code is publicly available at: https://github.com/Wangshuaiia/KG-Hopper.

Shuai Wang, Yinan Yu

Department of Computer Science and Engineering, Chalmers University of Technology and University of Gothenburg, SE-41296 Gothenburg, Sweden

LLM Reasoning with GraphsKnowledge Graph Question AnsweringMulti-Hop ReasoningRL for Language Model Reasoning
AskPDF
Mar 22, 2026

DomAgent: Leveraging Knowledge Graphs and Case-Based Reasoning for Domain-Specific Code Generation

Large language models (LLMs) have shown impressive capabilities in code generation. However, because most LLMs are trained on public domain corpora, directly applying them to real-world software development often yields low success rates, as these scenarios frequently require domain-specific knowledge. In particular, domain-specific tasks usually demand highly specialized solutions, which are often underrepresented or entirely absent in the training data of generic LLMs. To address this challenge, we propose DomAgent, an autonomous coding agent that bridges this gap by enabling LLMs to generate domain-adapted code through structured reasoning and targeted retrieval. A core component of DomAgent is DomRetriever, a novel retrieval module that emulates how humans learn domain-specific knowledge, by combining conceptual understanding with experiential examples. It dynamically integrates top-down knowledge-graph reasoning with bottom-up case-based reasoning, enabling iterative retrieval and synthesis of structured knowledge and representative cases to ensure contextual relevance and broad task coverage. DomRetriever can operate as part of DomAgent or independently with any LLM for flexible domain adaptation. We evaluate DomAgent on an open benchmark dataset in the data science domain (DS-1000) and further apply it to real-world truck software development tasks. Experimental results show that DomAgent significantly enhances domain-specific code generation, enabling small open-source models to close much of the performance gap with large proprietary LLMs in complex, real-world applications. The code is available at: https://github.com/Wangshuaiia/DomAgent.

Shuai Wang, Dhasarathy Parthasarathy, Robert Feldt +1

Chalmers University of Technology, Gothenburg, Sweden · Volvo Group, Gothenburg, Sweden

Case-Based ReasoningCode GenerationAgentic Code GenerationDomain Adaptation for LLMsKnowledge Augmentation for Language ModelsLLM Reasoning with Graphs
AskPDF
Mar 22, 2026

Graph of States: Solving Abductive Tasks with Large Language Models

Logical reasoning encompasses deduction, induction, and abduction. However, while Large Language Models (LLMs) have effectively mastered the former two, abductive reasoning remains significantly underexplored. Existing frameworks, predominantly designed for static deductive tasks, fail to generalize to abductive reasoning due to unstructured state representation and lack of explicit state control. Consequently, they are inevitably prone to Evidence Fabrication, Context Drift, Failed Backtracking, and Early Stopping. To bridge this gap, we introduce Graph of States (GoS), a general-purpose neuro-symbolic framework tailored for abductive tasks. GoS grounds multi-agent collaboration in a structured belief states, utilizing a causal graph to explicitly encode logical dependencies and a state machine to govern the valid transitions of the reasoning process. By dynamically aligning the reasoning focus with these symbolic constraints, our approach transforms aimless, unconstrained exploration into a convergent, directed search. Extensive evaluations on two real-world datasets demonstrate that GoS significantly outperforms all baselines, providing a robust solution for complex abductive tasks. Code repo and all prompts: https://github.com/gaorch85/Graph-of-States.

Yu Luo, Rongchen Gao, Lu Teng +9

Nankai University · Wenzhou Medical University · Alibaba Cloud +2

Abductive ReasoningLLM Reasoning with GraphsNeuro-Symbolic Reasoning
AskPDF
Mar 22, 2026

Graph Fusion Across Languages using Large Language Models

Combining multiple knowledge graphs (KGs) across linguistic boundaries is a persistent challenge due to semantic heterogeneity and the complexity of graph environments. We propose a framework for cross-lingual graph fusion, leveraging the in-context reasoning and multilingual semantic priors of Large Language Models (LLMs). The framework implements structural linearization by mapping triplets directly into natural language sequences (e.g., [head] [relation] [tail]), enabling the LLM to map relations and reconcile entities between an evolving fused graph (Gc(t−1)G_{c}^{(t-1)}) and a new candidate graph (GtG_{t}). Evaluated on the DBP15K dataset, this exploratory study demonstrates that LLMs can serve as a universal semantic bridge to resolve cross-lingual discrepancies. Results show the successful sequential agglomeration of multiple heterogeneous graphs, offering a scalable, modular solution for continuous knowledge synthesis in multi-source, multilingual environments.

Kaung Myat Kyaw, Khush Agarwal, Jonathan Chan

Innovative Cognitive Computing Research Center (IC2) School of Information Technology, KMUTT

Knowledge GraphsLLM Reasoning with Graphs
AskPDF
Mar 22, 2026

KLDrive: Fine-Grained 3D Scene Reasoning for Autonomous Driving based on Knowledge Graph

Autonomous driving requires reliable reasoning over fine-grained 3D scene facts. Fine-grained question answering over multi-modal driving observations provides a natural way to evaluate this capability, yet existing perception pipelines and driving-oriented large language model (LLM) methods still suffer from unreliable scene facts, hallucinations, opaque reasoning, and heavy reliance on task-specific training. We present KLDrive, the first knowledge-graph-augmented LLM reasoning framework for fine-grained question answering in autonomous driving. KLDrive addresses this problem through designing two tightly coupled components: an energy-based scene fact construction module that consolidates multi-source evidence into a reliable scene knowledge graph, and an LLM agent that performs fact-grounded reasoning over a constrained action space under explicit structural constraints. By combining structured prompting with few-shot in-context exemplars, the framework adapts to diverse reasoning tasks without heavy task-specific fine-tuning. Experiments on two large-scale autonomous-driving QA benchmarks show that KLDrive outperforms prior state-of-the-art methods, achieving the best overall accuracy of 65.04% on NuScenes-QA and the best SPICE score of 42.45 on GVQA. On counting, the most challenging factual reasoning task, it improves over the strongest baseline by 46.01 percentage points, demonstrating substantially reduced hallucinations and the benefit of coupling reliable scene fact construction with explicit reasoning.

Ye Tian, Jingyi Zhang, Zihao Wang +4

University of California San Diego, La Jolla, California, USA · University of California Merced, Merced, California, USA

Question AnsweringLLM Reasoning with Graphs3D Scene UnderstandingKnowledge Graph Question Answering
AskPDF
Mar 21, 2026

Reasoning Topology Matters: Network-of-Thought for Complex Reasoning Tasks

Existing prompting paradigms structure LLM reasoning in limited topologies: Chain-of-Thought (CoT) produces linear traces, while Tree-of-Thought (ToT) performs branching search. Yet complex reasoning often requires merging intermediate results, revisiting hypotheses, and integrating evidence from multiple sources. We propose Network-of-Thought (NoT), a framework that models reasoning as a directed graph with typed nodes and edges, guided by a heuristic-based controller policy. Across four benchmarks (GSM8K, Game of 24, HotpotQA, ProofWriter) and three models (GPT-4o-mini, Llama-3.3-70B-Instruct, Qwen2.5-72B-Instruct), we investigate when network topology outperforms chain or tree structures, whether LLM-generated heuristics can guide graph-based reasoning search, and the computation-accuracy tradeoff across topologies, evaluating each method on accuracy, topology simplicity, and token efficiency. Our results show that CoT remains effective for sequential tasks with GPT-4o-mini (89.5% on GSM8K), while NoT surpasses ToT on multi-hop reasoning (91.0% vs.\ 88.0% on HotpotQA with LLM-as-Judge). With 72B open-source models, NoT achieves the highest accuracy on GSM8K (91.5%), and Qwen2.5-72B achieves the best multi-hop QA result overall (91.7% on HotpotQA). Self-generated controller heuristics outperform fixed and random strategies on logical reasoning, with uncertainty-only weighting achieving 57.0% on ProofWriter. We also find that evaluation methodology significantly impacts method rankings: string-match underestimates all methods on open-ended QA, with the largest gap for NoT, a pattern consistent across all three models (14--18 percentage point gap on HotpotQA).

Fan Huang

Indiana University Bloomington

LLM ReasoningLLM Reasoning with GraphsEfficient Language Model ReasoningMulti-Hop Reasoning
AskPDF
Mar 20, 2026

Learning Dynamic Belief Graphs for Theory-of-mind Reasoning

Theory of Mind (ToM) reasoning with Large Language Models (LLMs) requires inferring how people's implicit, evolving beliefs shape what they seek and how they act under uncertainty -- especially in high-stakes settings such as disaster response, emergency medicine, and human-in-the-loop autonomy. Prior approaches either prompt LLMs directly or use latent-state models that treat beliefs as static and independent, often producing incoherent mental models over time and weak reasoning in dynamic contexts. We introduce a structured cognitive trajectory model for LLM-based ToM that represents mental state as a dynamic belief graph, jointly inferring latent beliefs, learning their time-varying dependencies, and linking belief evolution to information seeking and decisions. Our model contributes (i) a novel projection from textualized probabilistic statements to consistent probabilistic graphical model updates, (ii) an energy-based factor graph representation of belief interdependencies, and (iii) an ELBO-based objective that captures belief accumulation and delayed decisions. Across multiple real-world disaster evacuation datasets, our model significantly improves action prediction and recovers interpretable belief trajectories consistent with human reasoning, providing a principled module for augmenting LLMs with ToM in high-uncertainty environment. https://anonymous.4open.science/r/ICML_submission-6373/

Ruxiao Chen, Xilei Zhao, Thomas J. Cova +2

Department of Civil and Systems Engineering, Johns Hopkins University, Baltimore, MD, USA · Civil and Coastal Engineering, University of Florida, Gainesville, FL, USA · School of the Environment, Society & Sustainability, University of Utah, Salt Lake City, UT, USA +1

Computational Cognitive ModelingLLM Reasoning with GraphsTheory of MindProbabilistic Graphical ModelsDisaster ResponseLLM Reasoning
AskPDF
Mar 20, 2026

RouterKGQA: Specialized--General Model Routing for Constraint-Aware Knowledge Graph Question Answering

Knowledge graph question answering (KGQA) is a promising approach for mitigating LLM hallucination by grounding reasoning in structured and verifiable knowledge graphs. Existing approaches fall into two paradigms: retrieval-based methods utilize small specialized models, which are efficient but often produce unreachable paths and miss implicit constraints, while agent-based methods utilize large general models, which achieve stronger structural grounding at substantially higher cost. We propose RouterKGQA, a framework for specialized--general model collaboration, in which a specialized model generates reasoning paths and a general model performs KG-guided repair only when needed, improving performance at minimal cost. We further equip the specialized with constraint-aware answer filtering, which reduces redundant answers. In addition, we design a more efficient general agent workflow, further lowering inference cost. Experimental results show that RouterKGQA outperforms the previous best by 3.57 points in F1 and 0.49 points in Hits@1 on average across benchmarks, while requiring only 1.15 average LLM calls per question. Codes and models are available at https://github.com/Oldcircle/RouterKGQA.

Bo Yuan, Hexuan Deng, Xuebo Liu +1

Institute of Computing and Intelligence, Harbin Institute of Technology, Shenzhen, China · Zhongguancun Academy, Beijing, China

Knowledge Graph Question AnsweringLLM Reasoning with GraphsLLM Routing
AskPDF
Mar 19, 2026

GIP-RAG: An Evidence-Grounded Retrieval-Augmented Framework for Interpretable Gene Interaction and Pathway Impact Analysis

Understanding mechanistic relationships among genes and their impacts on biological pathways is essential for elucidating disease mechanisms and advancing precision medicine. Despite the availability of extensive molecular interaction and pathway data in public databases, integrating heterogeneous knowledge sources and enabling interpretable multi-step reasoning across biological networks remain challenging. We present GIP-RAG (Gene Interaction Prediction through Retrieval-Augmented Generation), a computational framework that combines biomedical knowledge graphs with large language models (LLMs) to infer and interpret gene interactions. The framework constructs a unified gene interaction knowledge graph by integrating curated data from KEGG, WikiPathways, SIGNOR, Pathway Commons, and PubChem. Given user-specified genes, a query-driven module retrieves relevant subgraphs, which are incorporated into structured prompts to guide LLM-based stepwise reasoning. This enables identification of direct and indirect regulatory relationships and generation of mechanistic explanations supported by biological evidence. Beyond pairwise interactions, GIP-RAG includes a pathway-level functional impact module that simulates propagation of gene perturbations through signaling networks and evaluates potential pathway state changes. Evaluation across diverse biological scenarios demonstrates that the framework generates consistent, interpretable, and evidence-supported insights into gene regulatory mechanisms. Overall, GIP-RAG provides a general and interpretable approach for integrating knowledge graphs with retrieval-augmented LLMs to support mechanistic reasoning in complex molecular systems.

Fujian Jia, Jiwen Gu, Cheng Lu +5

Kanghua Juntai Biotech Co. Ltd., Room 1504, Building 7, Dongwang Jingyuan, No. 768 Jingwang Road, Kunshan, Suzhou, Jiangsu Province, China · Department of Radiation Oncology, Cancer Treatment Center, The Second Affiliated Hospital of Hainan Medical University, Haikou, China · Department of Nutrition, University of California, Davis, USA +1

LLM Reasoning with GraphsGene Regulatory Network InferenceBiomedical KGs
AskPDF
Mar 18, 2026

SG-CoT: An Ambiguity-Aware Robotic Planning Framework using Scene Graph Representations

Ambiguity poses a major challenge to large language models (LLMs) used as robotic planners. In this letter, we present Scene Graph-Chain-of-Thought (SG-CoT), a two-stage framework where LLMs iteratively query a scene graph representation of the environment to detect and clarify ambiguities. First, a structured scene graph representation of the environment is constructed from input observations, capturing objects, their attributes, and relationships with other objects. Second, the LLM is equipped with retrieval functions to query portions of the scene graph that are relevant to the provided instruction. This grounds the reasoning process of the LLM in the observation, increasing the reliability of robotic planners under ambiguous situations. SG-CoT also allows the LLM to identify the source of ambiguity and pose a relevant disambiguation question to the user or another robot. Extensive experimentation demonstrates that SG-CoT consistently outperforms prior methods, with a minimum of 10% improvement in question accuracy and a minimum success rate increase of 4% in single-agent and 15% in multi-agent environments, validating its effectiveness for more generalizable robot planning.

Akshat Rana, Peeyush Agarwal, K. P. S. Rana +1

Netaji Subhas University of Technology, Dwarka, 110078, Delhi, India.

Large Language Model-Based Robot PlanningRobot Task PlanningLLM Reasoning with GraphsMulti-Agent Planning
AskPDF
Mar 17, 2026

EmoLLM: Appraisal-Grounded Cognitive-Emotional Co-Reasoning in Large Language Models

Large language models (LLMs) demonstrate strong cognitive intelligence (IQ), yet many real-world interactions also require emotional intelligence (EQ) to produce responses that are both factually reliable and emotionally appropriate. In settings such as emotional support, technical assistance, and consultation, effective dialogue depends on how situations are appraised with respect to the user's needs, goals, and coping capacity. Inspired by appraisal theory, we propose EmoLLM, an appraisal-grounded framework for IQ/EQ co-reasoning in dialogue. EmoLLM uses an explicit Appraisal Reasoning Graph (ARG) to structure intermediate reasoning over contextual facts, inferred user needs, appraisal dimensions, emotional states, and response strategies before generating a reply. We train EmoLLM in a multi-turn role-play environment with reinforcement learning, where reverse-perspective reasoning provides reward signals based on predicted user-side consequences of responses. Across diverse dialogue settings, EmoLLM improves emotional state outcomes and response quality over strong baselines while preserving strong factual reliability.

Yifei Zhang, Mingyang Li, Henry Gao +1

Department of Computer Science, Emory University

Emotion-Aware Dialogue GenerationLLM Reasoning with Graphs
AskPDF
Mar 16, 2026

Brain-Inspired Graph Multi-Agent Systems for LLM Reasoning

Large Language Models (LLMs) have demonstrated remarkable capabilities across a wide range of language tasks, yet complex multi-step reasoning remains a fundamental challenge. While Large Reasoning Models (LRMs) equipped with extended chain-of-thought mechanisms demonstrate improved performance over standard LLMs, both model types still suffer from accuracy collapse on sufficiently complex tasks, suggesting that scaling model-level reasoning alone is insufficient. Inspired by the global workspace theory of human cognition, we propose Brain-Inspired Graph Multi-Agent Systems (BIGMAS), in which specialized LLM agents are organized as nodes in a dynamically constructed directed graph and coordinate exclusively through a centralized shared workspace. A problem-adaptive GraphDesigner constructs task-specific agent topologies, while a global Orchestrator leverages the complete shared state for routing decisions, overcoming the local-view bottleneck of reactive approaches. Experiments on Game24, Six Fives, and Tower of London across six frontier LLMs demonstrate that BIGMAS consistently improves reasoning performance for both standard LLMs and LRMs, outperforming existing multi-agent baselines including ReAct and Tree of Thoughts, showing that multi-agent architectural design provides complementary gains orthogonal to model-level reasoning enhancements.

Guangfu Hao, Yuming Dai, Xianzhe Qin +1

Laboratory of Brain Atlas and Brain-inspired Intelligence, Institute of Automation, Chinese Academy of Sciences (CASIA) · School of Artificial Intelligence, University of Chinese Academy of Sciences (UCAS) · University of the Chinese Academy of Sciences (UCAS) +2

Multi-Agent LLM SystemsLLM Reasoning with GraphsCognitive Architectures for AI AgentsLarge Reasoning Models
AskPDF
Mar 14, 2026

The Reasoning Bottleneck in Graph-RAG: Structured Prompting and Context Compression for Multi-Hop QA

Graph-RAG systems achieve strong multi-hop question answering by indexing documents into knowledge graphs, but strong retrieval does not guarantee strong answers. Evaluating KET-RAG, a leading Graph-RAG system, on three multi-hop QA benchmarks (HotpotQA, MuSiQue, 2WikiMultiHopQA), we find that 77% to 91% of questions have the gold answer in the retrieved context, yet accuracy is only 35% to 78%, and 73% to 84% of errors are reasoning failures. We propose two augmentations: (i) SPARQL chain-of-thought prompting, which decomposes questions into triple-pattern queries aligned with the entity-relationship context, and (ii) graph-walk compression, which compresses the context by ~60% via knowledge-graph traversal with no LLM calls. SPARQL CoT improves accuracy by +2 to +14 pp; graph-walk compression adds +6 pp on average when paired with structured prompting on smaller models. Surprisingly, we show that, with question-type routing, a fully augmented budget open-weight Llama-8B model matches or exceeds the unaugmented Llama-70B baseline on all three benchmarks at ~12x lower cost. A replication on LightRAG confirms that our augmentations transfer across Graph-RAG systems.

Yasaman Zarrinkia, Venkatesh Srinivasan, Alex Thomo

University of Victoria · Santa Clara University

Structured CoT ReasoningGraph Retrieval-Augmented GenerationMulti-Hop QALLM Reasoning with GraphsCoT Reasoning
AskPDF
Mar 12, 2026

TRACE: Temporal Rule-Anchored Chain-of-Evidence on Knowledge Graphs for Interpretable Stock Movement Prediction

We present a Temporal Rule-Anchored Chain-of-Evidence (TRACE) on knowledge graphs for interpretable stock movement prediction that unifies symbolic relational priors, dynamic graph exploration, and LLM-guided decision making in a single end-to-end pipeline. The approach performs rule-guided multi-hop exploration restricted to admissible relation sequences, grounds candidate reasoning chains in contemporaneous news, and aggregates fully grounded evidence into auditable UP/DOWN verdicts with human-readable paths connecting text and structure. On an S&P~500 benchmark, the method achieves 55.1% accuracy, 55.7% precision, 71.5% recall, and 60.8% F1, surpassing strong baselines and improving recall and F1 over the best graph baseline under identical evaluation. The gains stem from (i) rule-guided exploration that focuses search on economically meaningful motifs rather than arbitrary walks, and (ii) text-grounded consolidation that selectively aggregates high-confidence, fully grounded hypotheses instead of uniformly pooling weak signals. Together, these choices yield higher sensitivity without sacrificing selectivity, delivering predictive lift with faithful, auditably interpretable explanations.

Qianggang Ding, Haochen Shi, Luis Castejón Lozano +7

DIRO & Institut Courtois, Université de Montréal, Montreal, QC, Canada · Mila – Québec AI Institute, Montreal, QC, Canada · Aily Labs, Madrid, Spain +2

Stock Price ForecastingFinanceLLM Reasoning with GraphsTime Series ForecastingMulti-Hop Reasoning
AskPDF
Mar 11, 2026

Causal Concept Graphs in LLM Latent Space for Stepwise Reasoning

Sparse autoencoders can localize where concepts live in language models, but not how they interact during multi-step reasoning. We propose Causal Concept Graphs (CCG): a directed acyclic graph over sparse, interpretable latent features, where edges capture learned causal dependencies between concepts. We combine task-conditioned sparse autoencoders for concept discovery with DAGMA-style differentiable structure learning for graph recovery and introduce the Causal Fidelity Score (CFS) to evaluate whether graph-guided interventions induce larger downstream effects than random ones. On ARC-Challenge, StrategyQA, and LogiQA with GPT-2 Medium, across five seeds (n=15n{=}15 paired runs), CCG achieves \CFS=5.654±0.625\CFS=5.654\pm0.625, outperforming ROME-style tracing (3.382±0.2333.382\pm0.233), SAE-only ranking (2.479±0.1962.479\pm0.196), and a random baseline (1.032±0.0341.032\pm0.034), with p<0.0001p<0.0001 after Bonferroni correction. Learned graphs are sparse (5-6% edge density), domain-specific, and stable across seeds.

Md Muntaqim Meherab, Noor Islam S. Mohammad, Faiza Feroz

Daffodil International University, Dhaka, Bangladesh · New York University, Brooklyn, NY, USA

LLM Reasoning with GraphsCausal InterpretabilityCausal Interventions in Language ModelsCausal Structure Learning
AskPDF
Mar 10, 2026

Detecting Miscitation on the Scholarly Web through LLM-Augmented Text-Rich Graph Learning

Scholarly web is a vast network of knowledge connected by citations. However, this system is increasingly compromised by miscitation, where references do not support or even contradict the claims they are cited for. Current miscitation detection methods, which primarily rely on semantic similarity or network anomalies, struggle to capture the nuanced relationship between a citation's context and its place in the wider network. While large language models (LLMs) offer powerful capabilities in semantic reasoning for this task, their deployment is hindered by hallucination risks and high computational costs. In this work, we introduce LLM-Augmented Graph Learning-based Miscitation Detector (LAGMiD), a novel framework that leverages LLMs for deep semantic reasoning over citation graphs and distills this knowledge into graph neural networks (GNNs) for efficient and scalable miscitation detection. Specifically, LAGMiD introduces an evidence-chain reasoning mechanism, which uses chain-of-thought prompting, to perform multi-hop citation tracing and assess semantic fidelity. To reduce LLM inference costs, we design a knowledge distillation method aligning GNN embeddings with intermediate LLM reasoning states. A collaborative learning strategy further routes complex cases to the LLM while optimizing the GNN for structure-based generalization. Experiments on three real-world benchmarks show that LAGMiD achieves state-of-the-art miscitation detection with significantly reduced inference cost.

Huidong Wu, Haojia Xiang, Jingtong Gao +3

Chinese Academy of Sciences & City University of Hong Kong · City University of Hong Kong · Shenzhen University & Beijing Dongbi Data Technology +1

LLM Reasoning with GraphsLLMs for Graph Learning
AskPDF
Mar 10, 2026

DataFactory: Collaborative Multi-Agent Framework for Advanced Table Question Answering

Table Question Answering (TableQA) enables natural language interaction with structured tabular data. However, existing large language model (LLM) approaches face critical limitations: context length constraints that restrict data handling capabilities, hallucination issues that compromise answer reliability, and single-agent architectures that struggle with complex reasoning scenarios involving semantic relationships and multi-hop logic. This paper introduces DataFactory, a multi-agent framework that addresses these limitations through specialized team coordination and automated knowledge transformation. The framework comprises a Data Leader employing the ReAct paradigm for reasoning orchestration, together with dedicated Database and Knowledge Graph teams, enabling the systematic decomposition of complex queries into structured and relational reasoning tasks. We formalize automated data-to-knowledge graph transformation via the mapping function T:D x S x R -> G, and implement natural language-based consultation that - unlike fixed workflow multi-agent systems - enables flexible inter-agent deliberation and adaptive planning to improve coordination robustness. We also apply context engineering strategies that integrate historical patterns and domain knowledge to reduce hallucinations and improve query accuracy. Across TabFact, WikiTableQuestions, and FeTaQA, using eight LLMs from five providers, results show consistent gains. Our approach improves accuracy by 20.2% (TabFact) and 23.9% (WikiTQ) over baselines, with significant effects (Cohen's d > 1). Team coordination also outperforms single-team variants (+5.5% TabFact, +14.4% WikiTQ, +17.1% FeTaQA ROUGE-2). The framework offers design guidelines for multi-agent collaboration and a practical platform for enterprise data analysis through integrated structured querying and graph-based knowledge representation.

Tong Wang, Chi Jin, Yongkang Chen +3

Institute of Systems Engineering, Academy of Military Sciences, Beijing, 100101, China · School of Information Resource Management, Renmin University of China, Beijing, 100872, China

Table QAMulti-Agent LLM SystemsMulti-Agent CollaborationLLM Reasoning with Graphs
AskPDF
Mar 9, 2026

CORE-Acu: Structured Reasoning Traces and Knowledge Graph Safety Verification for Acupuncture Clinical Decision Support

Large language models (LLMs) show significant potential for clinical decision support (CDS), yet their black-box nature -- characterized by untraceable reasoning and probabilistic hallucinations -- poses severe challenges in acupuncture, a field demanding rigorous interpretability and safety. To address this, we propose CORE-Acu, a neuro-symbolic framework for acupuncture clinical decision support that integrates Structured Chain-of-Thought (S-CoT) with knowledge graph (KG) safety verification. First, we construct the first acupuncture Structured Reasoning Trace dataset and a schema-constrained fine-tuning framework. By enforcing an explicit causal chain from pattern identification to treatment principles, treatment plans, and acupoint selection, we transform implicit Traditional Chinese Medicine (TCM) reasoning into interpretable generation constraints, mitigating the opacity of LLM-based CDS. Furthermore, we construct a TCM safety knowledge graph and establish a ``Generate--Verify--Revise'' closed-loop inference system based on a Symbolic Veto Mechanism, employing deterministic rules to intercept hallucinations and enforce hard safety boundaries. Finally, we introduce the Lexicon-Matched Entity-Reweighted Loss (LMERL), which corrects terminology drift caused by the frequency--importance mismatch in general optimization by adaptively amplifying gradient contributions of high-risk entities during fine-tuning. Experiments on 1,000 held-out cases demonstrate CORE-Acu's superior entity fidelity and reasoning quality. Crucially, CORE-Acu achieved 0/1,000 observed safety violations (95% CI: 0--0.37%), whereas GPT-4o exhibited an 8.5% violation rate under identical rules. These results establish CORE-Acu as a robust neuro-symbolic framework for acupuncture clinical decision support, guaranteeing both reasoning auditability and strict safety compliance.

Liuyi Xu, Yun Guo, Ming Chen +5

College of Information Science and Engineering, Northeastern University, Shenyang 110819, China · School of Information Science and Engineering, Yanshan University, Qinhuangdao, Hebei 066000, China · School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China +3

Structured CoT ReasoningClinical Decision SupportHealthcareLLM SafetyLLM Reasoning with GraphsNeuro-Symbolic Reasoning+1
AskPDF
Mar 9, 2026

SGG-R3^{\rm 3}: From Next-Token Prediction to End-to-End Unbiased Scene Graph Generation

Scene Graph Generation (SGG) structures visual scenes as graphs of objects and their relations. While Multimodal Large Language Models (MLLMs) have advanced end-to-end SGG, current methods are hindered by both a lack of task-specific structured reasoning and the challenges of sparse, long-tailed relation distributions, resulting in incomplete scene graphs characterized by low recall and biased predictions. To address these issues, we introduce SGG-R3^{\rm 3}, a structured reasoning framework that integrates task-specific chain-of-thought (CoT)-guided supervised fine-tuning (SFT) and reinforcement learning (RL) with group sequence policy optimization (GSPO), designed to engage in three sequential stages to achieve end-to-end unbiased scene graph generation. During the SFT phase, we propose a relation augmentation strategy by leveraging an MLLM and refined via embedding similarity filtering to alleviate relation sparsity. Subsequently, a stage-aligned reward scheme optimizes the procedural reasoning during RL. Specifically, we propose a novel dual-granularity reward which integrates fine-grained and coarse-grained relation rewards, simultaneously mitigating the long-tail issue via frequency-based adaptive weighting of predicates and improving relation coverage through semantic clustering. Experiments on two benchmarks show that SGG-R3^{\rm 3} achieves superior performance compared to existing methods, demonstrating the effectiveness and generalization of the framework.

Jiaye Feng, Qixiang Yin, Yuankun Liu +2

School of Software and Microelectronics, Peking University, Beijing, China · Zhongguancun Academy, Beijing, China

Scene Graph GenerationLLM Reasoning with Graphs
AskPDF
Mar 6, 2026

RouteGoT: Node-Adaptive Routing for Cost-Efficient Graph of Thoughts Reasoning

Large Language Models (LLMs) excel at multi-step reasoning, yet increasing the structural complexity of inference does not consistently improve system-level returns. Methods such as Tree of Thoughts (ToT), Graph of Thoughts (GoT), and Adaptive Graph of Thoughts (AGoT) can boost accuracy on some benchmarks, but often introduce substantial overhead in token consumption and latency, and their gains can be unstable across task distributions-sometimes underperforming simpler Chain-of-Thought (CoT) or direct input-output prompting (IO). We attribute this inefficiency to stage-wise and node-wise heterogeneity inside GoT-style reasoning pipelines: high-quality planning and final synthesis are globally coupled and typically benefit from strong models, whereas many intermediate subtasks are localized and can be solved accurately by lighter models with far fewer tokens. Motivated by these observations, we propose RouteGoT, a budget-controllable, node-adaptive routing framework for graph-structured reasoning. RouteGoT performs in-graph routing by prioritizing strong models for planning and synthesis, while dynamically allocating lightweight models and cost-effective strategies to leaf subtasks based on predicted difficulty. It further integrates explicit budget constraints into a global inference scheduler to control graph expansion under a user-specified token budget, enabling predictable performance-cost trade-offs. Experiments across reasoning, retrieval, and multi-hop QA benchmarks show that RouteGoT matching or improving accuracy while substantially reducing token usage; specifically, it achieves an average 8.1 percentage points accuracy improvement and 79.1% output token reduction compared to AGoT. Furthermore, RouteGoT outperforms existing routing baselines by maintaining a superior cost-accuracy trade-off, demonstrating improved robustness under varying budget targets and tasks.

Yuhang Liu, Ruijie Wang, Yunlong Chu +4

School of New Media and Communication, Tianjin University, Tianjin, China · School of Computer Science and Engineering, Beihang University, Beijing, China · Shanghai Jiao Tong University, Shanghai, China

LLM Reasoning with GraphsEfficient Language Model ReasoningLLM RoutingLLM Inference SchedulingCoT Reasoning
AskPDF