Task Graphs and Procedural Memory for Long-Horizon VLA Manipulation

Paper: 2609.05369 Authors: Vivek Chavan, Yahuan Shi, Oliver Heimann, Kevin Haninger, Jörg Krüger Categories: cs.RO, cs.CV

The Gap

Vision-language-action models can execute short manipulation skills, and they remain brittle in long-horizon procedures. The paper names four requirements that long-horizon tasks impose and that a reactive policy does not naturally satisfy: persistent task state, dependency-aware reasoning, conditional decisions, and reliable grounding.

These are not four unrelated weaknesses; they are all consequences of treating the task as a single skill to be executed. A reactive policy maps observation to action, which is sufficient when the next action depends only on what is visible now. In a procedure it does not: what to do next depends on what has already been completed, and on branches that were taken earlier. So the model must carry state, reason about dependencies between steps, handle conditionals, and ground its references reliably at each stage — and the failure mode when it cannot is a plausible-looking action at the wrong point in the procedure.

   VLA MODELS: SHORT SKILLS WORK, LONG PROCEDURES DO NOT

   they execute SHORT MANIPULATION SKILLS
   they remain BRITTLE in LONG-HORIZON PROCEDURES
        |
        v
   [FOUR REQUIREMENTS THE PAPER NAMES]
     PERSISTENT TASK STATE
     DEPENDENCY-AWARE REASONING
     CONDITIONAL DECISIONS
     RELIABLE GROUNDING
        |
        v
   [THEY ARE NOT FOUR UNRELATED WEAKNESSES]
     all consequences of treating the task as ONE SKILL TO EXECUTE
        |
        v
   a REACTIVE policy maps observation -> action
     -> sufficient when the next action depends ONLY on what is
        visible NOW
   in a PROCEDURE it does not:
     what to do next depends on WHAT HAS ALREADY BEEN COMPLETED,
     and on BRANCHES taken earlier
        |
        v
   -> the model must carry STATE, reason about DEPENDENCIES,
      handle CONDITIONALS, and GROUND reliably at each stage
   -> failure mode: a PLAUSIBLE-LOOKING ACTION AT THE WRONG POINT

The Increment

One sentence: Before this paper, long-horizon VLA manipulation relied on reactive policies that cannot carry procedure state; after it, a neuro-symbolic framework pairs VLA control with explicit task graphs and multimodal procedural memory, with pseudo-gaze annotation providing demonstration guidance.

Core Mechanism

The framework’s logic is a division of labour: learned control for the skill, explicit structure for the procedure.

Task graphs encode action dependencies, valid transitions, and branch conditions. This is where the procedure lives. Dependencies supply the ordering — which step requires which — and valid transitions supply what may follow what. Branch conditions are the part a reactive policy cannot represent at all: a procedure where the correct next step depends on an observed condition is not a sequence but a graph with alternative paths, and representing it explicitly is what makes conditional execution possible rather than hoped for.

Multimodal procedural memory maintains the active step, completed actions, textual context, and task-relevant visual evidence. The four fields correspond to the four requirements. The active step and completed actions give persistent task state — including the negative information that a step has not been done, which is what a reactive policy cannot know. Textual context supplies the procedure’s own description. And task-relevant visual evidence keeps the grounding anchored in observations that matter at this point rather than the whole scene.

Together, these structures guide object selection, destination grounding, subgoal dispatch, and verification of expected state transitions. Four operations, and the fourth deserves attention: the framework verifies expected state transitions rather than only issuing actions. So the symbolic layer does not merely decide what to do next — it checks whether the outcome matched expectation, which is what allows recovery from a step that failed silently.

Human demonstrations provide additional spatial and temporal guidance through gaze or saliency cues. This is the most distinctive element, and the design choice within it is honest about a hard problem. Gaze in a teleoperation video is recorded from the operator’s viewpoint, while the policy acts from the robot’s — transferring gaze across views is itself a research problem. So the initial study bypasses cross-view gaze transfer and directly annotates pseudo-gaze in robot-view teleoperation videos. That isolates the question being asked: does demonstration-derived visual guidance help policy learning, independent of the gaze-transfer problem? Getting that question answered first is the right sequencing, and stating the bypass explicitly is what makes the result interpretable.

The resulting guidance is used during VLA fine-tuning and inference — so it shapes both learning and execution.

Two domains test the framework, chosen because each requires all four capabilities: workspace clearing and surgical-instrument handling, both needing ordered execution, visually grounded decisions, and conditional branching. The evaluation then measures across a spread of granularity, from correct-object and destination selection through subtask completion, task progress, step-order consistency, complete-task success, to procedural or execution mistakes. Measuring step-order consistency separately is notable — it is precisely the failure mode a reactive policy exhibits and a task graph should prevent, so it is the metric that tests the paper’s own thesis.

   DIVISION OF LABOUR: LEARNED CONTROL FOR THE SKILL,
   EXPLICIT STRUCTURE FOR THE PROCEDURE

   [1] TASK GRAPHS encode:
         action DEPENDENCIES
         valid TRANSITIONS
         BRANCH CONDITIONS
       -> this is where the PROCEDURE lives
       -> dependencies supply ORDERING (which step requires which)
       -> valid transitions supply what MAY FOLLOW what
       -> branch conditions are what a reactive policy cannot
          represent at all: a procedure whose correct next step
          depends on an observed condition is not a SEQUENCE but
          a GRAPH WITH ALTERNATIVE PATHS
          -> representing it explicitly makes conditional
             execution POSSIBLE rather than hoped for

   [2] MULTIMODAL PROCEDURAL MEMORY maintains:
         the ACTIVE STEP        }
         COMPLETED ACTIONS      } -> PERSISTENT TASK STATE,
         TEXTUAL CONTEXT        }    including the NEGATIVE
         TASK-RELEVANT VISUAL   }    information that a step
           EVIDENCE             }    has NOT been done
                                           (which a reactive
                                            policy cannot know)
       <- textual context supplies the procedure's own description
       <- visual evidence keeps grounding anchored in what matters
          NOW rather than the whole scene

   [3] THE FOUR OPERATIONS THESE STRUCTURES GUIDE
         object selection | destination grounding |
         subgoal dispatch | VERIFICATION of expected state transitions
       <- the fourth deserves attention: the framework CHECKS
          whether the outcome matched expectation
       -> allows recovery from a step that failed SILENTLY

   [4] DEMONSTRATION GUIDANCE via GAZE or SALIENCY cues
       AND AN HONEST DESIGN DECISION:
         gaze in a TELEOPERATION video is from the OPERATOR's view;
         the policy acts from the ROBOT's view
         -> cross-view gaze transfer is ITSELF a research problem
         -> so the initial study BYPASSES it and directly annotates
            PSEUDO-GAZE in ROBOT-VIEW teleoperation videos
         <- ISOLATES the question: does demonstration-derived visual
            guidance help policy learning, INDEPENDENT of the
            gaze-transfer problem?
         <- right SEQUENCING, and stating the bypass explicitly is
            what makes the result interpretable
       -> guidance used DURING FINE-TUNING AND INFERENCE
          (shapes both learning and execution)

   TWO DOMAINS, each requiring ALL FOUR capabilities
     workspace clearing
     surgical-instrument handling
     both needing ORDERED EXECUTION, VISUALLY GROUNDED DECISIONS,
     CONDITIONAL BRANCHING

   EVALUATION ACROSS GRANULARITIES
     correct-object and destination selection
     subtask completion | task progress
     STEP-ORDER CONSISTENCY
     complete-task success | procedural or execution mistakes
       <- measuring step-order consistency separately is notable:
          it is precisely the failure mode a REACTIVE policy shows
          and a TASK GRAPH should prevent
          -> the metric that TESTS THE PAPER'S OWN THESIS

Think of it as the difference between a skilled pair of hands and a checklist plus a memory of what has been done. Give the hands a task and they will perform it well; that part is solved. Now put them in a procedure where step four assumes step two succeeded, where step five has two variants depending on what was observed at step three, and where a failed step two must be noticed and retried. The hands cannot hold any of that — they act on what is in front of them. What you need is a checklist for the ordering and the branches, a memory of what has actually been completed, and a step where you verify the outcome before moving on. The pseudo-gaze annotation is the equivalent of a supervisor’s eyes: recorded guidance showing where to look at each moment, which helps the hands find the right object without changing their skill at all.

Key Concepts

• The procedure as an explicit graph: dependencies, valid transitions and branch conditions. Conditional execution is not expressible as a sequence, which is why the structure has to be represented rather than learned implicitly.
• Procedural memory with four fields: active step, completed actions, textual context, task-relevant visual evidence. Completed actions carry the negative information — that a step has not been done — which no reactive policy can know.
• Verification of expected transitions: checking outcomes rather than only issuing actions. It is what makes silent failure recoverable, and it is a capability the symbolic layer provides that a policy cannot.
• Isolating the guidance question: bypassing cross-view gaze transfer by annotating pseudo-gaze in robot view. It separates “does demonstration guidance help” from “does gaze transfer work”, answering the tractable question first.
• Step-order consistency as the self-test: the metric that directly probes the paper’s thesis, since order failure is what a reactive policy produces and a task graph should prevent.

Framework Shift

Before (reactive policy, one skill at a time):
  observation -> action
  -> sufficient when the next action depends only on what is visible
  -> brittle in procedures: no state, no dependencies, no branches
  -> failure appears as a plausible action at the wrong point

After (learned control plus explicit procedure):
  task graphs: dependencies, transitions, branch conditions
  procedural memory: active step, completed actions, text, visual evidence
  -> guides selection, grounding, dispatch, AND verification
  -> demonstration guidance via pseudo-gaze during fine-tuning
     and inference
  -> evaluated on step-order consistency as well as success

From expecting a reactive policy to carry a procedure it cannot represent, to pairing learned control with an explicit structure for ordering, branching and state, the core shift is that long-horizon reliability comes from separating the skill from the procedure that sequences it.

Expert Assessment

Problem choice: Excellent, and the four requirements are a clean decomposition of why long-horizon manipulation resists scaling. Naming them as consequences of a single mistaken framing — treating a procedure as one skill — is what makes the framework’s shape follow from the diagnosis rather than being asserted.

Method maturity: The division of labour is well conceived: explicit graphs for the parts that are combinatorial (dependencies, branches, transitions) and learned control for the part that needs perception. Including verification among the guided operations is the element most often omitted in similar frameworks, and it is what makes silent failure recoverable. The pseudo-gaze decision is well handled methodologically — recognizing that cross-view transfer is a separate problem and bypassing it explicitly, rather than reporting a confounded result, is the honest sequencing.

Experimental integrity: The evaluation’s spread is the strength: measuring step-order consistency alongside success rates tests the paper’s own claim, since order failure is the failure a task graph is supposed to prevent. Two domains, one of which (surgical-instrument handling) requires conditional branching rather than just ordering, is a reasonable breadth. The obvious limitation is that bypassing gaze transfer means the demonstration-guidance result is established for pseudo-gaze in robot view only, and how much of the benefit survives real cross-view transfer — the harder and more deployable setting — remains open. The paper is clear about this.

Writing quality: The four requirements are stated once and then mapped onto the framework’s components, so a reader can see what addresses what. Because the branching capability is the least familiar, a short worked example — one procedure, its graph, and a branch taken or not taken — would make the contribution concrete for readers who have not built such a system.

Verdict: strong accept — it decomposes long-horizon manipulation into four explicit requirements, addresses them with a well-scoped neuro-symbolic structure including outcome verification, and evaluates the failure mode its own thesis predicts.

Takeaways

• Separate the skill from the procedure. Learned control handles manipulation; ordering, branches and state need an explicit structure.
• Store the negative information. Knowing which steps have not been completed is what a reactive policy cannot represent and a procedure requires.
• Verify transitions, not just actions. Checking whether the outcome matched expectation is what makes a silently failed step recoverable.
• Bypass the confound that is a research problem in itself. Isolating “does this guidance help” from “does view transfer work” answers the tractable question first, provided the bypass is stated.