Google Researchers Release 'Procedural Graph' for LLM Agents… Self-Evolving via Failure Trajectory Analysis

Researchers from Google, Georgia Tech, and Peking University proposed Procedural Graph for LLM agents. This structure explicitly stores procedural knowledge as (procedure, relation, procedure) triples, similar to how knowledge graphs manage factual knowledge as (entity, relation, entity) triples.

Core Operating Principle

• Explicit Procedure Management: Unlike existing agents that implicitly determine actions based on accumulated history, this approach allows querying the graph for the sequence and conditions of what to do next.
• Context-Specific Guidance: At each step, the agent's current node is located, and 'context-specific guidance' is generated based on the surrounding subgraph to guide the next action. This acts as a bias rather than a mandatory command, allowing the agent to flexibly deviate if the graph is incorrect.

Self-Evolving Mechanism

• Failure/Success Trajectory Comparison: An LLM refiner contrasts failed trajectories with successful ones to modify the graph's topological structure and attributes.
• Pending Verification Gate: Modifications are committed only if they maintain or improve holdout validation performance. Rejected modifications are recorded to prevent the same changes from being repeatedly proposed.

Performance and Significance

• Starting from a minimal skeleton, it achieves performance equal to or better than manually designed graphs. It also demonstrates the ability to correct flawed expert prior knowledge.
• It shows consistent performance improvements over memory-based baselines across various datasets and backbone LLMs, with further performance gains achieved through self-evolution without manual engineering.