Procedural Graphs: What-to-Do Knowledge as Triplets, Not a Growing History

Paper: 2609.09153 Authors: Yuxing Lu, Yicheng Chen, Shanchan Wu, Sercan Ö. Arık Categories: cs.AI, cs.CL, cs.MA

The Gap

Agents are increasingly deployed to plan over long horizons and act through external tools, and most of them select actions the same way: unconstrained generation over an accumulating history. Whatever the model knows about procedure — what to do, in what order, under which conditions — stays implicit, encoded only in the weights and whatever context happens to be present.

That makes long trajectories fail in recognisable ways: agents lose track of their objectives, invoke tools out of order, and repeat unproductive actions. These are not three separate bugs; they are what happens when procedural knowledge is implicit. Nothing in the system represents “this step must precede that one”, so nothing prevents the ordering error. Nothing represents “this action was already tried and failed”, so nothing prevents the repetition.

   HOW MOST AGENTS SELECT ACTIONS

   unconstrained GENERATION over an ACCUMULATING HISTORY
        |
        v
   whatever the model knows about PROCEDURE --
   WHAT to do, in WHAT ORDER, under WHICH conditions --
   stays IMPLICIT
     -> encoded only in the WEIGHTS and whatever context
        happens to be present
        |
        v
   [RECOGNISABLE FAILURES ON LONG TRAJECTORIES]
     lose track of OBJECTIVES
     invoke tools OUT OF ORDER
     REPEAT unproductive actions
        |
        v
   THESE ARE NOT THREE SEPARATE BUGS
     they are what happens when procedural knowledge is IMPLICIT:
       nothing represents "this step must PRECEDE that one"
         -> nothing prevents the ORDERING error
       nothing represents "this action was ALREADY TRIED and failed"
         -> nothing prevents the REPETITION

The Increment

One sentence: Before this paper, procedural knowledge lived implicitly in weights and context; after it, a Procedural Graph holds it as explicit triplets that localise the active step and self-evolve from comparisons of failed and successful trajectories.

Core Mechanism

The organising analogy is exact and worth stating: just as a knowledge graph organises factual knowledge into (entity, relation, entity) triplets for what-is questions, a Procedural Graph organises procedural knowledge into (procedure, relation, procedure) triplets for what-to-do questions. The parallel is not decorative — it says the same representational move applies, and it identifies what was missing: agents had no equivalent of a knowledge graph for procedure.

At each decision step, the framework localises the agent’s active node — so the agent’s position in the procedure is an explicit variable rather than something to be inferred from history. And a guidance model translates the surrounding subgraph into step-level situational guidance that biases the solver’s next action without dictating it. That second clause is a deliberate design choice: guidance biases rather than dictates, so the graph constrains the choice without removing the policy’s ability to act on what it observes. A graph that dictated actions would be a hardcoded controller; one that biases is a prior over the policy.

The graph is self-evolving, and the evolution mechanism is the most interesting part. An LLM refiner contrasts failed trajectories with successful ones and edits the graph’s topology and attributes, and then — the two constraints that make it reliable:

• Edits are committed only if they preserve or improve held-out validation performance. So the refiner proposes and validation adjudicates; the graph cannot drift toward whatever the refiner finds plausible.
• Rejected edits are retained — to discourage repetition. Keeping the record of what did not work is what stops the refiner from proposing the same failed edit again, which is the same repetition problem the agent suffers from, applied one level up.

The result is that starting from a minimal skeleton, the loop builds graphs that match or surpass hand-designed ones, and it can also repair a flawed expert prior. The second capability is notable: an expert-provided procedure that is wrong somewhere is a realistic input, and a mechanism that improves on a bad prior rather than inheriting it is more useful than one that only builds from nothing.

Across multiple datasets, task types and LLMs, the Procedural Graph gives consistent gains over memory-based baselines, with self-evolution further improving performance without manual engineering.

   THE ORGANISING ANALOGY (EXACT, NOT DECORATIVE)

   a KNOWLEDGE GRAPH organises FACTUAL knowledge into
     (entity, relation, entity) triplets      -> WHAT-IS questions
   a PROCEDURAL GRAPH organises PROCEDURAL knowledge into
     (procedure, relation, procedure) triplets -> WHAT-TO-DO questions
        |
        v
   the parallel identifies WHAT WAS MISSING:
     agents had no equivalent of a knowledge graph for PROCEDURE

   [1] AT EACH DECISION STEP, LOCALISE THE AGENT'S ACTIVE NODE
         -> the agent's POSITION in the procedure is an EXPLICIT
            VARIABLE, not something inferred from history

   [2] A GUIDANCE MODEL translates the surrounding SUBGRAPH into
       STEP-LEVEL SITUATIONAL GUIDANCE that
         BIASES the solver's next action
         WITHOUT DICTATING IT
       <- a deliberate design choice:
          "biases" not "dictates" -> the graph CONSTRAINS the
          choice without removing the policy's ability to act on
          what it OBSERVES
       <- a graph that DICTATED would be a HARDCODED CONTROLLER
          one that BIASES is a PRIOR OVER THE POLICY

   [3] THE GRAPH IS SELF-EVOLVING
         an LLM REFINER contrasts FAILED trajectories with
         SUCCESSFUL ones and edits the graph's topology and
         attributes
       TWO CONSTRAINTS THAT MAKE IT RELIABLE
         (a) edits are committed ONLY IF they PRESERVE OR IMPROVE
             HELD-OUT VALIDATION PERFORMANCE
             -> the refiner PROPOSES, VALIDATION ADJUDICATES
             -> the graph cannot drift toward whatever the refiner
                finds plausible
         (b) REJECTED EDITS ARE RETAINED -- to DISCOURAGE
             REPETITION
             <- keeping the record of what did NOT work stops the
                refiner re-proposing the same failed edit
             <- the SAME repetition problem the AGENT suffers
                from, applied ONE LEVEL UP

   RESULTS
     starting from a MINIMAL SKELETON, the loop builds graphs that
       MATCH OR SURPASS hand-designed ones
     it can also REPAIR A FLAWED EXPERT PRIOR
       <- an expert-provided procedure that is WRONG SOMEWHERE is
          a realistic input; improving on a bad prior beats
          inheriting it
     across MULTIPLE datasets, task types and LLMs: CONSISTENT
       GAINS over MEMORY-BASED BASELINES
     self-evolution further improves performance WITHOUT MANUAL
       ENGINEERING

Think of it as the difference between navigating a building with a floor plan and navigating it from memory of where you have been. From memory, you can lose track of which wing you are in, revisit a corridor you already found locked, and attempt a door that only opens after another one. A floor plan makes your position a definite thing, shows which rooms precede which, and lets you notice that you are re-walking a route that already failed. Two details of the paper’s version map cleanly. The plan suggests rather than compels — it tells you where you probably are and what usually comes next, while leaving you free to follow what you actually see. And the plan gets edited by the people who use it, but only where the change demonstrably helps, and with the failed revisions filed rather than binned so nobody proposes them again.

Key Concepts

• Procedural knowledge made explicit as triplets: (procedure, relation, procedure), mirroring knowledge graphs. It names what agents lacked — a representation for what-to-do knowledge rather than what-is knowledge.
• Localising the active node: making the agent’s position an explicit variable. It removes the need to infer position from an accumulating history, which is where objective-tracking failures originate.
• Guidance that biases rather than dictates: constraining the next action without removing responsiveness to observations. It keeps the graph a prior over the policy rather than a hardcoded controller.
• Validation-adjudicated self-evolution: the refiner proposes, held-out performance decides. It prevents drift toward plausible-looking edits.
• Retaining rejected edits: discouraging repeated proposals by remembering what failed. It is the agent’s own repetition problem applied at the level of the graph’s maintenance.

Framework Shift

Before (procedure implicit, generation over history):
  action = unconstrained generation over accumulating history
  -> procedure stays implicit
  -> objectives lost, tools called out of order, actions repeated
  -> long trajectories degrade in predictable ways

After (procedure explicit, localised, self-evolving):
  (procedure, relation, procedure) triplets
  active node localised at each decision step
  guidance BIASES the next action without dictating it
  refiner proposes edits; held-out validation commits them;
  rejected edits retained to discourage repetition
  -> minimal skeleton grows into graphs matching hand-designed ones
  -> can repair a flawed expert prior

From hoping a policy will infer procedure from history, to giving it an explicit graph of what precedes what and where it currently is, the core shift is that procedural knowledge can be represented and maintained rather than only learned implicitly.

Expert Assessment

Problem choice: Excellent, and the knowledge-graph analogy is the kind of framing that makes a design feel inevitable. Long-horizon agent failure has been treated as a context-management problem — fit more history, summarise better — and the paper relocates it as a representation problem: the procedure was never represented at all.

Method maturity: The two-part design is well judged. Localising the active node addresses objective-tracking directly, and guidance-that-biases is the correct strength of intervention, since a dictating graph would discard the policy’s perceptual advantages. The self-evolution loop has the two constraints that make such loops trustworthy — validation adjudication, and retention of rejected edits — and retaining failures is a notably good idea, because it recognises that the maintenance process suffers from the same repetition pathology as the agent.

Experimental integrity: The breadth claim — multiple datasets, task types and LLMs — is the right one for a framework paper, and consistency across them is more informative than a large gain in one setting. Repairing a flawed expert prior is the most convincing single capability, because it is a task that cannot be satisfied by memorisation. The limitation is that the graph’s benefit depends on trajectory quality and validation-set adequacy: the held-out criterion that adjudicates edits is doing a lot of work, and how the loop behaves when the validation signal is thin or noisy is not dwelt on.

Writing quality: The analogy is stated up front and every component follows from it, which makes the design memorable. Because the guidance model’s strength is the subtle part, a short worked example — one decision step, the localised node, and the guidance it produces alongside the action taken — would make “biases without dictating” concrete rather than stipulative.

Verdict: strong accept — it identifies implicit procedural knowledge as the cause of long-horizon drift, gives it an explicit representation with a well-guarded self-evolution loop, and shows the loop can improve on a flawed expert prior.

Takeaways

• Represent the procedure, do not hope to infer it. What precedes what, and under which conditions, has to be somewhere in the system.
• Make the agent’s position explicit. Objective-tracking failures come from having to infer your location from an accumulating history.
• Bias, do not dictate. A graph that constrains the next action while leaving the policy responsive to observations is a prior; one that dictates is a hardcoded controller.
• Adjudicate self-edits with held-out performance, and keep the rejected ones. The first stops drift toward plausibility; the second stops the maintenance process repeating itself.