Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

• URL: http://arxiv.org/abs/2609.09153v1
• Date: Tue, 08 Sep 2026 17:59:41 GMT
• Title: Procedural Graphs: Self-Evolving Execution Structures for LLM Agents
• Abstract summary: Procedural Graph organizes procedural knowledge into (procedure, relation, procedure) triplets for what-to-do questions.<n>At each decision step, the framework localizes the agent's active node, and a guidance model translates the surrounding subgraph into step-level situational guidance.<n>The graph is self-evolving: an LLM refiner contrasts failed trajectories with successful ones and edits the graph's topology and attributes.
• Score: 11.810729293911622
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large language models are increasingly deployed as agents that plan over long horizons and act through external tools. Most agents select actions through unconstrained generation over an accumulating history, leaving implicit the procedural knowledge of what to do, in what order, and under which conditions. As trajectories lengthen, agents can lose track of their objectives, invoke tools out of order, and repeat unproductive actions. We introduce the Procedural Graph: just as a knowledge graph organizes factual knowledge into (entity, relation, entity) triplets for what-is questions, a Procedural Graph organizes procedural knowledge into (procedure, relation, procedure) triplets for what-to-do questions. At each decision step, the framework localizes the agent's active node, and a guidance model translates the surrounding subgraph into step-level situational guidance that biases the solver's next action without dictating it. The graph is self-evolving: an LLM refiner contrasts failed trajectories with successful ones and edits the graph's topology and attributes, committing edits that preserve or improve held-out validation performance while retaining rejected ones to discourage repetition. Starting from a minimal skeleton, the loop builds graphs that match or surpass hand-designed ones. It can also repair a flawed expert prior. Across multiple datasets, task types, and LLMs, the Procedural Graph delivers consistent gains over memory-based baselines, and self-evolution further improves performance without manual engineering.

Related papers

• Inference-Time Graph Engineering for Multi-Agent LLM Workflows [51.56038180639833]
  We introduce ReActNet, a training-free framework that compiles a query and a set of role-specialized agents into a sequence of directed communication graphs.<n>We show that ReActNet consistently improves over fixed-topology and learned-topology baselines while maintaining competitive inference cost.
  arXiv  Detail & Related papers  (2026-09-04T23:32:11Z)
• Graph-Based Agentic AI with LangGraph: Workflow Pathways for Long-Running Stateful Business Processes [0.0]
  We present three executable recipes to show how typed state, conditional routing, deterministic tools, retries, interrupts, checkpoints, and traces fit together.<n>LangGraph is positioned by workflow-complexity fit, not as a universal default.
  arXiv  Detail & Related papers  (2026-07-21T17:07:13Z)
• Experience Memory Graph: One-Shot Error Correction for Agents [9.23684438376937]
  Large Language Model (LLM) agents suffer from compounding errors and struggle to recover from failures.<n>Existing self-correction mechanisms rely on prompt-based reflection, which is inherently brittle.<n>We propose Experience Memory Graph (EMG), a framework that reformulates agent failure recovery as a graph matching problem.
  arXiv  Detail & Related papers  (2026-07-15T14:33:15Z)
• Atomic Task Graph: A Unified Framework for Agentic Planning and Execution [13.978062792065215]
  Atomic Task Graph (ATG) is a unified control framework for planning and execution.<n>ATG maintains an explicit graph to expose dependencies and support reuse.<n>ATG consistently outperforms strong baselines in success rate and execution efficiency.
  arXiv  Detail & Related papers  (2026-07-02T09:34:20Z)
• GraphWalk: Enabling Reasoning in Large Language Models through Tool-Based Graph Navigation [0.2999888908665658]
  We present GraphWalk, a problem-agnostic, training-free, tool-based framework that allows off-the-shelf LLMs to reason through sequential graph navigation.<n>We evaluate whether models equipped with GraphWalk can compose these operations into correct multi-step reasoning chains.
  arXiv  Detail & Related papers  (2026-04-02T04:43:01Z)
• Semi-supervised Instruction Tuning for Large Language Models on Text-Attributed Graphs [62.544129365882014]
  We propose a novel Semi-supervised Instruction Tuning pipeline for Graph Learning, named SIT-Graph.<n> SIT-Graph is model-agnostic and can be seamlessly integrated into any graph instruction tuning method that utilizes LLMs as the predictor.<n>Extensive experiments demonstrate that when incorporated into state-of-the-art graph instruction tuning methods, SIT-Graph significantly enhances their performance on text-attributed graph benchmarks.
  arXiv  Detail & Related papers  (2026-01-19T08:10:53Z)
• GraphRunner: A Multi-Stage Framework for Efficient and Accurate Graph-Based Retrieval [3.792463570467098]
  GraphRunner is a novel graph-based retrieval framework that operates in three distinct stages: planning, verification, and execution.<n>It significantly reduces reasoning errors and detects hallucinations before execution.<n>Our evaluation using the GRBench dataset shows that GraphRunner consistently outperforms existing approaches.
  arXiv  Detail & Related papers  (2025-07-11T18:10:01Z)
• 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)
• 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)
• Non-Sequential Graph Script Induction via Multimedia Grounding [129.83134296316493]
  We train a script knowledge model capable of both generating explicit graph scripts for learnt tasks and predicting future steps given a partial step sequence. Human evaluation shows our model outperforming the WikiHow linear baseline by 48.76% absolute gains in capturing sequential and non-sequential step relationships.
  arXiv  Detail & Related papers  (2023-05-27T18:13:17Z)

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.