Procedural Graphs: Self-Evolving Execution Structures for LLM Agents
Recorded: Sept. 9, 2026, 8:09 p.m.
| Original | Summarized |
[2609.09153] Procedural Graphs: Self-Evolving Execution Structures for LLM Agents
Skip to main content Search Log in Search arXiv Press Enter to search · Advanced search Computer Science > Artificial Intelligence arXiv:2609.09153 (cs) [Submitted on 8 Sep 2026] 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. Subjects: Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Multiagent Systems (cs.MA) Cite as: Focus to learn more arXiv-issued DOI via DataCite (pending registration) Submission history From: Yuxing Lu [view email] [v1]
Full-text links: View a PDF of the paper titled Procedural Graphs: Self-Evolving Execution Structures for LLM Agents, by Yuxing Lu and 3 other authorsView PDFHTML (experimental)TeX Source < prev | new Change to browse by: References & Citations NASA ADSGoogle Scholar export BibTeX citation BibTeX formatted citation loading... Data provided by: Bookmark
Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv (What is alphaXiv?) Links to Code Toggle CatalyzeX Code Finder for Papers (What is CatalyzeX?) DagsHub Toggle DagsHub (What is DagsHub?) GotitPub Toggle Gotit.pub (What is GotitPub?) Huggingface Toggle Hugging Face (What is Huggingface?) ScienceCast Toggle ScienceCast (What is ScienceCast?) Demos Demos Replicate Toggle Replicate (What is Replicate?) Spaces Toggle Hugging Face Spaces (What is Spaces?) Spaces Toggle TXYZ.AI (What is TXYZ.AI?) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower (What are Influence Flowers?) Core recommender toggle CORE Recommender (What is CORE?) Author About arXivLabs arXivLabs: experimental projects with community collaborators Which authors of this paper are endorsers? | We gratefully acknowledge support from About Major funding support from |
Large language models deployed as agents frequently struggle with complex tasks involving long-horizon planning and the use of external tools, primarily because action selection is based on unconstrained generation over accumulated history, which leaves implicit the necessary procedural knowledge regarding the correct sequence, conditions, and order of operations. As these execution trajectories become extensive, agents often experience a loss of focus on overall objectives, resort to invoking tools in an inappropriate sequence, or engage in repetitive, unproductive actions. To address these limitations, the authors introduce the Procedural Graph, a framework designed to explicitly structure and manage this procedural knowledge. This graph organizes procedural knowledge using (procedure, relation, procedure) triplets, analogous to how knowledge graphs organize factual knowledge using (entity, relation, entity) triplets, thereby structuring the system specifically for answering what-to-do questions. The framework operates by localizing the agent's active node at each decision step. A guidance model then analyzes the surrounding subgraph to generate step-level situational guidance. This guidance serves to bias the solver's selection of the next action, rather than dictating it outright, allowing the agent to make context-aware decisions within the structured environment. A critical feature of the Procedural Graph is its self-evolving nature. The system refines the graph by contrasting execution trajectories that resulted in failure against those that succeeded. This comparison-based feedback allows the large language model refiner to edit the graph's topology and attributes. Edits are committed only if they successfully preserve or enhance performance on held-out validation data, while rejected edits are retained to prevent the agent from repeating unsuccessful patterns. The process begins with a minimal skeleton, from which the system iteratively builds graphs that either match or surpass those designed manually. Furthermore, this methodology possesses the capability to repair flawed expert priors. When applied across diverse datasets, varied task types, and different large language models, the Procedural Graph consistently provides gains over memory-based baselines. The self-evolution mechanism further enhances this performance, enabling significant improvements without the need for extensive manual engineering. |