💻 computer science

Agentproof: Static Verification of Agent Workflow Graphs

Agentproof is a static verification system that automatically extracts unified graph models from major agent frameworks to detect structural defects and enforce temporal safety policies via a specialized DSL and DFA-based analysis, complementing runtime guardrails by identifying topology-level issues before deployment.

Original authors: Melwin Xavier, Vaisakh M A, Melveena Jolly, Midhun Xavier

Published 2026-03-24

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Melwin Xavier, Vaisakh M A, Melveena Jolly, Midhun Xavier

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a complex robot butler. You don't just tell it "clean the house"; you write a detailed flowchart: Pick up the broom → Go to the kitchen → If the floor is dirty, sweep → If the floor is clean, go to the living room → Put the broom away.

In the world of AI, these "robots" are called Agents. They use tools (like searching the web or sending emails) based on these flowcharts, which are called Workflow Graphs.

The problem is that when developers build these flowcharts, they often make silly mistakes. They might draw a path that leads to a dead end (the robot gets stuck), or they might forget to put a "human approval" step before the robot deletes a database.

Currently, we only check for these mistakes while the robot is running. If the robot gets stuck, we only find out when it actually tries to run that specific path. It's like waiting for a car to crash before you realize the brakes were never connected.

Agentproof is a new tool that acts like a super-smart architect who checks the blueprints before you even build the house.

Here is how it works, using simple analogies:

1. The Universal Translator (The Extractor)

Different robot builders use different languages. Some use "LangGraph," others use "CrewAI" or "AutoGen." It's like one builder speaks French, another speaks Japanese, and another speaks German.

Agentproof's job: It has a translator for all of them. It reads the blueprint in any of these languages and instantly converts it into a single, standard "Universal Blueprint" that it can understand. You don't have to rewrite your code; Agentproof just reads it.

2. The "Spot the Glitch" Inspector (Structural Checks)

Once it has the universal blueprint, Agentproof runs six quick checks to find logical errors. Think of it like a game of "Where's Waldo" for logic errors:

The Dead End: "Hey, this path leads to a wall. The robot will get stuck here forever."
The Ghost Exit: "You have an 'End' button, but there is no path leading to it. The robot will never know when to stop."
The Missing Gate: "You are about to let the robot delete a file, but you forgot to put a 'Human Approval' checkpoint in front of it!"
The Magic Trick: If it finds a mistake, it doesn't just say "Error." It gives you a Witness Trace. This is like a GPS route showing you exactly: Start → Turn Left → Go Straight → CRASH. It shows you the exact path the robot will take to get stuck.

3. The Rulebook Enforcer (Temporal Policies)

Sometimes the problem isn't a dead end, but the order of things.

Rule: "You must never delete a table without first backing it up."
Rule: "If you send an email, a human must review it first."

Agentproof translates these rules into a simple "traffic light" system (called a DFA). It checks the blueprint to see if any possible path the robot could take breaks these rules.

Static Check: It simulates every possible journey the robot could take on the blueprint. If any path breaks a rule, it stops you before you deploy.
Runtime Check: It can also watch the robot while it's working, acting like a security guard who yells "Stop!" if the robot tries to do something bad in real-time.

Why is this a big deal?

No Manual Work: Old tools required you to rewrite your robot's code into a special "verification language" (like translating a novel into a math equation). Agentproof does this automatically.
Speed: It checks huge blueprints (up to 5,000 steps) in less than a second.
Safety: In a test of 18 different robot blueprints, Agentproof found that 27% had structural glitches (dead ends) and 55% were missing human safety gates. These are mistakes that would have been very hard to catch just by testing the robot a few times.

The Bottom Line

Think of Agentproof as the safety inspector for AI robots.

Runtime Guardrails (the old way) are like a seatbelt: they catch you if you crash, but they don't stop the crash from happening.
Agentproof is like checking the car's engine and brakes before you drive it. It ensures the map you gave the robot actually leads to a destination and doesn't have any holes in the road.

It doesn't check if the robot is "smart" or telling the truth (that's a different problem); it just makes sure the robot's plan is logically sound and safe to execute.

1. Problem Statement

As Large Language Model (LLM) agents increasingly interact with external tools and APIs via orchestration frameworks (e.g., LangGraph, CrewAI, AutoGen, Google ADK), their behavior is encoded as explicit workflow graphs. However, current safety enforcement relies almost exclusively on runtime guardrails (e.g., NeMo Guardrails, LlamaGuard). These runtime tools have three fundamental limitations:

Latency Overhead: They impose per-call latency.
Reactive Detection: They only detect violations when the offending execution path is actually triggered.
No Coverage Guarantees: They cannot verify paths that remain untriggered during testing.

Consequently, topological defects (structural errors in the workflow graph) often go unnoticed until they cause silent failures or security breaches in production. Examples include:

Dead-end nodes: Execution paths that halt without reaching an exit.
Unreachable exits: Loops or branches that prevent the workflow from terminating.
Missing human gates: Sensitive actions (e.g., deleting data) that bypass required human approval steps.

Current general-purpose model checkers (e.g., SPIN, NuSMV) could theoretically detect these issues but require manual modeling of the workflow into a specific language (e.g., Promela), which is a prohibitive overhead for developers iterating on agent designs.

2. Methodology: The Agentproof System

Agentproof is a system designed for pre-deployment static verification of agent workflows. It operates on the premise that modern agent frameworks expose their workflow structure via APIs, allowing for automated extraction and analysis without manual modeling.

A. Cross-Framework Extraction Pipeline

The system includes extractors for four major frameworks: LangGraph, CrewAI, AutoGen, and Google ADK.

Unified Abstract Model: The extractors normalize heterogeneous framework representations (e.g., state graphs, task lists, group chats) into a single, framework-agnostic AgentGraph model.
Typed Structure: The model consists of typed nodes (Entry, Exit, Tool, LLM, Router, Human, Subgraph) and typed edges (Direct, Conditional, Parallel, Loop).
Automation: This eliminates the need for developers to manually translate workflows into formal modeling languages.

B. Verification Layers

Agentproof employs two complementary verification layers:

Structural Checks (Topological Verification):
These checks analyze the graph topology using standard graph algorithms (BFS/DFS) with linear time complexity $O(|V| + |E|)$ . They include:
- Exit Reachability: Ensures all exit nodes are reachable from the start.
- Reverse Reachability (Livelock Detection): Ensures every reachable node can eventually reach an exit (detecting infinite loops).
- Dead-end Detection: Identifies nodes with no outgoing edges (excluding exits).
- Router Shape Validation: Ensures router nodes only have conditional outgoing edges.
- Human-in-the-Loop Coverage: Verifies that paths to sensitive tools pass through a "Human" node.
- Tool Declaration: Ensures tool nodes have explicit tool bindings.
- Witness Generation: Upon failure, the system generates a concrete witness trace (a path demonstrating the defect) to aid debugging.
Temporal Policy Verification:
- DSL: A Domain-Specific Language (DSL) covering the safety fragment of Linear Temporal Logic (LTL) is used to specify policies (e.g., "If draft_email occurs, human_review must follow").
- Compilation: Policies are compiled into Deterministic Finite Automata (DFA).
- Dual Evaluation Modes:
  - Static: A Graph $\times$ DFA product construction explores all possible paths in the graph to detect violations without executing the agent.
  - Runtime: The DFA monitors live or simulated event streams for violations.

3. Key Contributions

Automated Extraction: The first system to automatically extract unified abstract workflow models from four distinct agent frameworks, bridging the gap between programmatic APIs and formal verification.
Pre-Deployment Verification Pipeline: A complete pipeline combining six structural checks and a temporal policy DSL, capable of generating witness traces for defects.
Empirical Benchmark: A curated corpus of 18 workflows representing common patterns and anti-patterns across the supported frameworks, serving as a reproducible benchmark for the community.
Performance: Demonstrated sub-second verification times for graphs up to 5,000 nodes, proving scalability for complex agent systems.

4. Experimental Results

The system was evaluated on the 18-workflow benchmark:

Defect Detection:
- 27% of workflows contained structural defects (dead-ends, unreachable exits, router shape violations).
- 55% of workflows violated a human-gate policy (missing required human approval for sensitive actions).
- The system successfully detected all injected structural defects and generated accurate witness traces.
Temporal Policy Coverage:
- 15 real-world safety policies (covering domains like privacy, compliance, and DevOps) were defined.
- All 15 policies fit within the 7-form DSL fragment (Safety LTL).
- Static verification successfully identified violations that runtime trace evaluation missed (e.g., violations on paths not exercised in random traces).
Scalability:
- Structural checks completed in ~105 ms for graphs with 5,000 nodes.
- Runtime monitor evaluation is independent of graph size, processing events at ~247,000 events/second.
Extraction Accuracy:
- Achieved 100% precision and recall for node and edge detection on test suites, with the primary limitation being the heuristic-based detection of "Human" nodes (relying on naming conventions).

5. Significance and Impact

Complementarity to Runtime Guardrails: Agentproof does not replace runtime tools (which handle content toxicity and prompt injection) but complements them by catching topology-level defects that runtime tools cannot see unless the specific bad path is triggered.
Shift-Left Safety: It enables "shift-left" safety, allowing developers to catch critical design flaws (like infinite loops or missing approvals) before deployment, reducing the safety surface area runtime systems must cover.
Accessibility: By automating the extraction process, it makes formal verification techniques accessible to agent developers who lack the expertise to use manual model checkers like SPIN.
Foundation for Future Research: The paper establishes a new domain for applying formal methods to AI orchestration and provides a benchmark and toolset for future research into agent safety and reliability.

In conclusion, Agentproof demonstrates that static analysis of agent workflow graphs is feasible, scalable, and effective at detecting critical structural and policy violations that are currently invisible to standard runtime safety mechanisms.