GNNVerifier: Graph-based Verifier for LLM Task Planning

• URL: http://arxiv.org/abs/2603.14730v2
• Date: Tue, 17 Mar 2026 04:26:31 GMT
• Title: GNNVerifier: Graph-based Verifier for LLM Task Planning
• Abstract summary: Large language models (LLMs) facilitate the development of autonomous agents.<n>Recent research has introduced plan verifiers to identify and correct potential flaws.<n>Most existing approaches still rely on an LLM as the verifier.<n>We propose a graph-based verifier for LLM task planning.
• Score: 26.77252346424261
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models (LLMs) facilitate the development of autonomous agents. As a core component of such agents, task planning aims to decompose complex natural language requests into concrete, solvable sub-tasks. Since LLM-generated plans are frequently prone to hallucinations and sensitive to long-context prom-pts, recent research has introduced plan verifiers to identify and correct potential flaws. However, most existing approaches still rely on an LLM as the verifier via additional prompting for plan review or self-reflection. LLM-based verifiers can be misled by plausible narration and struggle to detect failures caused by structural relations across steps, such as type mismatches, missing intermediates, or broken dependencies. To address these limitations, we propose a graph-based verifier for LLM task planning. Specifically, the proposed method has four major components: Firstly, we represent a plan as a directed graph with enriched attributes, where nodes denote sub-tasks and edges encode execution order and dependency constraints. Secondly, a graph neural network (GNN) then performs structural evaluation and diagnosis, producing a graph-level plausibility score for plan acceptance as well as node/edge-level risk scores to localize erroneous regions. Thirdly, we construct controllable perturbations from ground truth plan graphs, and automatically generate training data with fine-grained annotations. Finally, guided by the feedback from our GNN verifier, we enable an LLM to conduct local edits (e.g., tool replacement or insertion) to correct the plan when the graph-level score is insufficient. Extensive experiments across diverse datasets, backbone LLMs, and planners demonstrate that our GNNVerifier achieves significant gains in improving plan quality. Our data and code is available at https://github.com/BUPT-GAMMA/GNNVerifier.

Related papers

• GLIP: Graph and LLM Joint Pretraining for Graph-Level Tasks [14.957822216791255]
  Graph neural networks (GNNs) have become a mainstream approach for learning graph representations.<n>With the rise of large language models (LLMs), recent studies have attempted to combine GNNs with LLMs.<n>We propose Graph-LLM JoInt Pretraining framework for graph-level tasks.
  arXiv  Detail & Related papers  (2026-06-29T04:30:45Z)
• Are Large Language Models Suitable for Graph Computation? Progress and Prospects [31.182390464506053]
  Large language models (LLMs) have been increasingly explored for graph computation.<n>We provide a comprehensive review of LLMs for graph computation through a role-based taxonomy.<n>Our review indicates that LLMs are promising for simple, small-scale tasks, but remain unreliable for large-scale and exactness-demanding tasks.
  arXiv  Detail & Related papers  (2026-06-05T03:24:38Z)
• Reducing Hallucinations in Complex Question Answering using Simple Graph-based Retrieval-Augmented Generation (long version) [0.0]
  Large language models (LLMs) have fundamentally transformed the landscape of Natural Language Processing.<n>Retrieval-augmented generation (RAG) systems have emerged as a common deployment scenario seeking to avoid the well known risk of the LLM "hallucinating" information.<n>In this work, we explore the idea of using a lightweight graph structure with a relatively simple graph schema, to support the RAG subsystem via a dedicated toolset.
  arXiv  Detail & Related papers  (2026-06-04T09:07:06Z)
• PlanningBench: Generating Scalable and Verifiable Planning Data for Evaluating and Training Large Language Models [52.48858778580074]
  Planning is a fundamental capability for large language models (LLMs)<n>PlanningBench is a framework for generating scalable, diverse, verifiable planning data for both evaluation and training.
  arXiv  Detail & Related papers  (2026-05-20T08:10:15Z)
• AGRAG: Advanced Graph-based Retrieval-Augmented Generation for LLMs [15.570965946461255]
  Graph-based retrieval-augmented generation (RAG) has demonstrated significant potential in enhancing Large Language Models (LLMs) with structured knowledge.<n>Existing methods face three critical challenges: Inaccurate Graph Construction; Poor Reasoning Ability; and Inadequate Answering.<n>We propose AGRAG, an advanced graph-based retrieval-augmented generation framework.
  arXiv  Detail & Related papers  (2025-11-02T06:13:06Z)
• GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning [50.40400074353263]
  Graph Neural Networks (GNNs) are powerful tools for precessing relational data but often struggle to generalize to unseen graphs.<n>We introduce textbfGraph textbfIn-context textbfL textbfTransformer (GILT), a framework built on an LLM-free and tuning-free architecture.
  arXiv  Detail & Related papers  (2025-10-06T08:09:15Z)
• GRIL: Knowledge Graph Retrieval-Integrated Learning with Large Language Models [59.72897499248909]
  We propose a novel graph retriever trained end-to-end with Large Language Models (LLMs)<n>Within the extracted subgraph, structural knowledge and semantic features are encoded via soft tokens and the verbalized graph, respectively, which are infused into the LLM together.<n>Our approach consistently achieves state-of-the-art performance, validating the strength of joint graph-LLM optimization for complex reasoning tasks.
  arXiv  Detail & Related papers  (2025-09-20T02:38:00Z)
• Align-GRAG: Reasoning-Guided Dual Alignment for Graph Retrieval-Augmented Generation [79.75818239774952]
  Large language models (LLMs) have demonstrated remarkable capabilities, but still struggle with issues like hallucinations and outdated information.<n>Retrieval-augmented generation (RAG) addresses these issues by grounding LLM outputs in external knowledge with an Information Retrieval (IR) system.<n>We propose Align-GRAG, a novel reasoning-guided dual alignment framework in post-retrieval phrase.
  arXiv  Detail & Related papers  (2025-05-22T05:15:27Z)
• Scalability Matters: Overcoming Challenges in InstructGLM with Similarity-Degree-Based Sampling [1.2805157669888096]
  We propose SDM-InstructGLM, a novel instruction-tuned Graph Language Model (InstructGLM) framework that enhances scalability and efficiency without relying on GNNs.<n>Our method introduces a similarity-degree-based biased random walk mechanism, which selectively samples and encodes graph information based on node-feature similarity and degree centrality.<n>Our results demonstrate the feasibility of LLM-only graph processing, enabling scalable and interpretable Graph Language Models (GLMs) optimized through instruction-based fine-tuning.
  arXiv  Detail & Related papers  (2025-05-02T06:08:21Z)
• Plan-over-Graph: Towards Parallelable LLM Agent Schedule [53.834646147919436]
  Large Language Models (LLMs) have demonstrated exceptional abilities in reasoning for task planning.<n>This paper introduces a novel paradigm, plan-over-graph, in which the model first decomposes a real-life textual task into executable subtasks and constructs an abstract task graph.<n>The model then understands this task graph as input and generates a plan for parallel execution.
  arXiv  Detail & Related papers  (2025-02-20T13:47:51Z)
• Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
  Task planning in language agents is emerging as an important research topic alongside the development of large language models (LLMs) In this paper, we explore graph learning-based methods for task planning, a direction that is to the prevalent focus on prompt design. Our interest in graph learning stems from a theoretical discovery: the biases of attention and auto-regressive loss impede LLMs' ability to effectively navigate decision-making on graphs.
  arXiv  Detail & Related papers  (2024-05-29T14:26:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.