PADME: Two-Phase Procedure Execution via a Dependency Graph

PHASE 1 — TEACH (building the decision graph):

STEP 1: Filter → remove irrelevant content (disclaimers, comments)
STEP 2: Segment → split into chunks (numbered steps or topics)
STEP 3: Build local graphs for each segment → a DAG with nodes and dependencies
STEP 4: Merge into a global graph → the final decision graph
STEP 5: Categorize nodes → HumanInput, InfoProcessing, InfoExtraction, Knowledge, Decision
STEP 6: Attach executable functions → code/API for each node (except Decision)

PHASE 2 — EXECUTE (running along the graph):

STEP 1: Topological traversal of the graph → execute nodes in the correct dependency order
STEP 2: At a Decision node → choose a branch based on context
STEP 3: Continue traversal along the chosen branch → until all nodes are complete

Both phases are run by an LLM agent. Teach happens once per procedure; Execute happens every time for a new task.

Task: You're a technician at a repair shop. A customer brings in a broken iPhone. You need to run the standard diagnostic and repair procedure.

The procedure (simplified):

1. Check in the device, record the customer's details
2. Do a visual inspection
3. Connect to diagnostic software
4. Run tests (screen, battery, camera, speakers)
5. DECISION: If all tests pass → return to the customer. If there are faults → go to repair
6. Determine the list of parts
7. Check inventory
8. DECISION: If parts are in stock → do the replacement. If not → order from the supplier and wait
9. Perform the repair
10. Rerun the tests
11. DECISION: If tests pass → process the return to the customer. If the fault persists → escalate to a senior technician
12. Complete the return paperwork

PADME prompt (Teach phase):

Convert this procedure into a decision graph:

1. Filter out irrelevant content (if there are disclaimers, legal notes, comments — remove them)
2. Split the procedure into segments (each numbered step = a separate segment)
3. For each segment, build a local graph:
   - Node = a specific action
   - Edge = a dependency (step B requires the result of step A)
4. Categorize each node:
   - HumanInput (data from the user)
   - InfoProcessing (processing, calculations, transformations)
   - InfoExtraction (fetching data from external sources: API, database, inventory)
   - Knowledge (reference information, no action required)
   - Decision (conditional branching: if-then logic)
5. Merge the local graphs into one global decision graph
6. For each node (except Decision), describe exactly what to do (executable function)

iPhone diagnostic procedure:
[paste the procedure above]

Result: The model builds a graph where:

• Nodes 1-4 form a sequential chain (InfoProcessing → InfoExtraction)
• Node 5 is a Decision node with two branches (OK → node 12, fault → node 6)
• Nodes 6-10 form a second chain
• Node 11 is another Decision node

PADME prompt (Execute phase):

Use the decision graph to complete the task:

Task: iPhone belonging to customer Johnson, IMEI 123456789, complaint “won't turn on.”

Run the procedure:
1. Walk the graph in topological order
2. At each node:
   - If HumanInput → request the data
   - If InfoProcessing → perform the action
   - If InfoExtraction → fetch info from the source
   - If Decision → choose a branch based on context
3. Continue until all nodes are complete

[paste the decision graph from the Teach phase]

The model walks the graph: checks in the device → inspects → connects → tests → at the Decision node evaluates the test results and picks a branch (e.g., “battery drained, screen cracked” → goes to repair).

The LLM's weakness: When executing long procedures directly, the model doesn't see the dependencies between steps and searches a huge space of actions. For a 20-step procedure with 10 possible actions per step, the search space = 10^20 variants. The model piles up errors: forgets what's done, repeats steps, does things in the wrong order.

The LLM's strength: The model is good at following explicit instructions, categorizing information, and choosing from a limited set of options. Give it a dependency graph and it won't guess what to do next — at each step only the valid options from the graph exist.

How PADME exploits this: Splitting into two phases gives you:

1. Teach cuts complexity — instead of an O(|actions|^steps) search space, the graph gives an O(steps^2) traversal
2. Execute cuts errors — the model doesn't invent the next step, it takes it from the graph
3. Decision nodes localize branching — instead of conditional logic at every step, the model makes decisions only at explicitly marked points (5-7 decision nodes for a 20-step procedure)

Control knobs for adaptation:

• Node categories → add your own (e.g., APICall, DatabaseQuery) for your domain
• Graph granularity → coarser nodes for simple procedures (less overhead), finer for complex ones (more control)
• Decision criteria → swap the branching conditions (instead of “if the test passes” → “if the customer approved the repair”)
• Graph validation → manual review for critical domains (finance, health), automatic for the rest

The graph also gives you transparency — you can show the customer “which step we're on” or explain “why this branch was chosen.”

Teach Phase (building the decision graph):

Convert the procedure into a decision graph:

1. Filter out irrelevant content (disclaimers, comments, administrative headers)
2. Split into segments:
   - If the procedure is numbered → each step = a segment
   - If it's free-form → split by topic
3. For each segment, build a local graph:
   - Node = a specific action or check
   - Edge = a dependency (B requires the result of A)
4. Categorize nodes:
   - HumanInput: requires data input from the user
   - InfoProcessing: processing, calculations, transformations
   - InfoExtraction: fetching data from outside (API, database, external source)
   - Knowledge: reference information (no action required)
   - Decision: conditional branching (if-then logic)
5. Merge the local graphs into one global graph
6. For each node (except Decision), describe the executable function:
   - What exactly to do
   - What inputs are needed
   - What the output is

Procedure:
{procedure text}

Output the graph in this format:
- List of nodes with categories
- List of edges (dependencies)
- For each node: description, inputs, outputs

Execute Phase (running along the graph):

Use the decision graph to complete the task:

{paste the graph from the Teach phase}

Task: {description of the specific task}

Execution algorithm:
1. Start with the initial nodes (those with no dependencies)
2. For each node:
   - HumanInput → request data from the user
   - InfoProcessing → perform the action
   - InfoExtraction → fetch info from the source
   - Knowledge → use as context
   - Decision → choose a branch based on the current state
3. Continue through the graph in topological order
4. At a Decision node:
   - Analyze the context (results of previous steps)
   - Choose one branch
   - Continue along the chosen branch
5. Finish: when all reachable nodes are complete

Track:
- Which nodes are already complete
- The current state (step results)
- Available next nodes

Placeholders:

• {procedure text} — the source instruction in any format (numbered steps, free text, SOP, manual)
• {description of the specific task} — what needs to be done with the specific inputs

🚀 Quick start — paste into the chat:

Here's the PADME methodology for structuring procedures as a decision graph. Adapt it to my task: [your task].

First build the decision graph (Teach phase), then complete the task along the graph (Execute phase).

[paste both templates above]

The LLM will ask which procedure to convert and which specific task to run — because structuring (once) and execution (many times) need to be separated. It will take the methodology from the template and build a dependency graph for your procedure.

⚠️ Graph quality depends on the source procedure: If the procedure is incomplete, contradictory, or has implicit dependencies, the graph will be wrong. PADME doesn't fill gaps in documentation — it only structures what's there.

⚠️ Needs validation in critical domains: In finance, medicine, and security, the graph must be reviewed manually before use. Automatic validation exists but doesn't replace expertise.

⚠️ Overhead on short procedures: For 3-5 step tasks, building a graph is overkill — just execute directly.

The team took 4 different domains and pitted PADME against baseline methods (ReAct, Chain-of-Thought, Act-Only, SPRING). Benchmarks:

• Business processes (80 procedures from real companies) — task variants: easy (direct execution), medium (noisy data), hard (uncertainty)
• Recipes (a cookbook of ~80 dishes) — variants: easy (all ingredients on hand), medium (extra ingredients), hard (“what can I make from this?”)
• ScienceWorld (lab experiments of 20-50 steps) — an RL environment adapted for testing procedures
• ALFWorld (household tasks of 5-15 steps) — find an object, move it, heat it, etc.

Evaluation metrics:

• Prefix Match Length (PML) — how many consecutive steps matched the ground truth
• Prefix Accuracy (PA) — PML / total sequence length
• Sequential Match (SM) — 0/1 for a full match of the whole sequence
• Final Match (FM) — 0/1 for correctness of the final action

Key findings:

1. PADME wins on every benchmark — FM from 0.69 (ALFWorld) to 0.87 (Recipes), PML 2-3x higher than baselines
2. Baselines fail in different ways: ReAct gets stuck in loops (sensor → capture → sensor → capture), Chain-of-Thought hallucinates during long planning, Act-Only sometimes works (!) because it doesn't accumulate reasoning errors
3. Hard tasks show the graph's strength: On recipes with uncertainty (“what can I cook from these ingredients?”), PADME reaches FM=0.81, 3x better than Chain-of-Thought

Why is PADME more stable? The graph constrains the search space. Baselines weigh actions at every step and accumulate errors. PADME walks the graph — at each step only the valid options are known. Errors can occur only at decision nodes (5-7 points in a 20-step procedure) and during parameter filling (but the graph constrains parameters via dependencies).

An interesting effect: Act-Only sometimes performs on par with ReAct/CoT, because simplicity avoids piling up reasoning errors. But it's not stable — it works by luck, not by design.

The paper doesn't include a single prompt template, only a description of the agent architecture.

Context: The researchers implemented two agents:

1. Procedure Structuring Agent — converts a procedure into a decision graph
2. Procedure Execution Agent — runs tasks along the graph via a topological traversal algorithm (Algorithm 1 in the paper)

Example decision graph from the paper (spindle manufacturing):

Nodes:
- Node 1 (HumanInput): Spindle Order → output: order_details
- Node 2 (InfoExtraction): Retrieve Raw Materials → input: order_details → output: materials
- Node 3 (InfoProcessing): Set Up Assembly Line → input: materials → output: setup_complete
- Node 4 (InfoProcessing): Assemble Spindle → input: setup_complete → output: assembled_spindle
- Node 5 (InfoProcessing): Test Spindle in Smart Tester → input: assembled_spindle → output: test_results
- Node 6 (Decision): Evaluate Spindle Test Outcome → input: test_results
  - Branch 1 (negative): → Node 7 (Maintenance)
  - Branch 2 (positive): → Node 8 (Success)
- Node 7 (InfoProcessing): Send to Maintenance → output: maintenance_done
- Node 8 (Knowledge): Successful Completion

Edges:
1 → 2, 2 → 3, 3 → 4, 4 → 5, 5 → 6
6 → 7 (if negative), 6 → 8 (if positive)

Node categories:

• HumanInput — requires data from the user
• InfoProcessing — internal calculations/transformations
• InfoExtraction — fetching data from external sources (API, database)
• Knowledge — reference information
• Decision — conditional branching

💡 Adaptation for Personal Productivity: Your To-Do List as a Decision Graph

A classic to-do list is flat. You can't see dependencies (“can't send the report until I get data from a coworker”). The PADME approach structures tasks as a graph.

Prompt:

Convert my task list into a decision graph:

Tasks:
- Write the report for project X
- Get the data from Mike
- Check the budget
- DECISION: If the budget is approved → order the equipment. If not → renegotiate with the CFO
- Send the report to the client
- Prepare the presentation for the meeting

Build the graph:
1. Identify dependencies between tasks
2. Categorize (HumanInput, InfoProcessing, InfoExtraction, Decision)
3. Mark the decision points (conditional forks)
4. Show which tasks can run in parallel and which only in sequence

Effect: Instead of “what do I do next?”, you see the available tasks (those whose dependencies are done) and the blockers (waiting on data from Mike → other tasks).

🔧 Technique: A Simplified Graph for Short Procedures → Token Savings

For 3-5 step procedures, full PADME is overkill. Use a compressed version without detailed categorization.

Prompt:

Simplified decision graph for a short procedure:

Procedure:
{your 3-5 step procedure}

Build a minimal graph:
1. Numbered list of steps
2. Dependencies (which step needs the result of which)
3. Only explicit decision points (if-then), if any

No detailed node categorization, no executable functions.

Effect: 50-70% fewer tokens while keeping the core value — visible dependencies.

💡 Extrapolation: PADME + Chain-of-Thought for Debugging Complex Procedures

Combine the graph (structure) with CoT (reasoning at each step).

Prompt:

Use the decision graph + Chain-of-Thought:

{graph from the Teach phase}

Task: {specific task}

At each graph node:
1. Describe the current state
2. Reason out loud: why you're choosing this action
3. Perform the action
4. Check: is the result correct for the next node

At a Decision node:
1. List the available branches
2. Justify your choice
3. Choose a branch

This is for debugging — I need to see every step.

Effect: Execution transparency — you see where the model went off track and which reasoning led to the error. Useful for critical procedures.

PADME: Procedure Aware DynaMic Execution

• Deepeka Garg, Sihan Zeng, Annapoorani L. Narayanan, Sumitra Ganesh, Leo Ardon
• J.P. Morgan AI Research
• Conference: First Conference on Language Modeling (2024)
• Repository: not listed in the paper
• Related work: AgentKit (Wu et al., 2024), SPRING (Wu et al., 2024), ProcBench (Fujisawa et al., 2024)