BehaVerify: A Formal Verification Tool for Behavior Trees

Serena S. Serbinowska, Ben Wooding, Diego Manzanas Lopez, Luke Nam, Anne M. Tumlin, Nicholas K. Potteiger, Hongchao Zhang, Taylor T. JohnsonarXiv 2026 · DOI · arXiv

TL;DR

BehaVerify is a new open-source toolbox designed to formally verify Behavior Trees (BTs), including modern Neuro-Symbolic variants that incorporate neural networks. By utilizing an efficient encoding technique called "fastforwarding," it compresses complex tree executions into single transitions, allowing researchers to verify safety-critical robotic controllers with thousands of nodes in seconds.

What Problem Does This Paper Address?

Behavior Trees (BTs) have become the go-to architecture for robotic task planning, favored for their modularity and readability over traditional finite state machines. They are increasingly deployed in high-stakes environments—from surgical robots to autonomous drones placing explosives in mines.

However, as BTs grow in complexity, ensuring they are "correct-by-design" becomes a massive challenge. Existing verification tools often suffer from the "state space explosion" problem, where the number of possible states grows too fast for a computer to analyze. Furthermore, the rise of Neuro-Symbolic BTs—which use neural networks for perception or decision-making at the leaf nodes—adds a layer of non-determinism that traditional tools simply aren't equipped to handle. BehaVerify aims to bridge this gap by providing a scalable, user-friendly framework for verifying both standard and neural-network-enhanced BTs.

Methods

The core of BehaVerify is its ability to translate a BT into a formal model that can be checked by nuXmv, a powerful symbolic model checker. The architecture is summarized in the following figure:

Figure 2: Architecture of BehaVerify. One DSL front end builds a single internal model that every backend reads.

Key technical innovations include:

  • Domain Specific Language (DSL): Users define the BT, the environment, and the requirements (using Linear Temporal Logic or Computation Tree Logic) in a structured text format.
  • Fastforwarding Encoding: This is the "secret sauce." Instead of modeling every single node visit as a separate step (which leads to massive traces), BehaVerify computes the final state of an entire "tick" in one transition. It uses a Static Single Assignment (SSA) style to track variable changes within a tick.
  • Neuro-Symbolic Support: For leaf nodes containing neural networks, BehaVerify can evaluate the network across all possible bounded integer inputs to create a precise "table mode" representation for the model checker.
  • Code Generation: Once verified, the tool can automatically generate executable Python (integrated with ROS and PyTrees) or Haskell code, ensuring the deployed controller matches the verified model.

Datasets

Rather than a single training dataset, the authors evaluated BehaVerify using several complex benchmarks:

  • Binary-Tree Scaling: A synthetic benchmark used to test scalability, scaling up to 2,055 nodes.
  • The "Drunken Drone": A navigation task involving non-deterministic movement and goal-seeking (see Figure 1).
  • Recreated Benchmarks: The authors recreated classic examples from other tools, including the Mars Rover and Train Control examples from BT2BIP, and a UAV drone example from BT2Fiacre.
  • Obstacle Avoidance (NSBT): A drone navigating a 10x10 grid with 22 obstacles, where the navigation logic is handled by a neural network with 1,000 neurons.

Key Insights and Ideas

  • Tick Compression is Essential: The "aha moment" for scalability is realizing that a BT tick is a loop-free computation. By treating the entire tick as one transition, BehaVerify achieves linear growth in reachable states relative to tree size, whereas naive encodings grow quadratically or exponentially.
  • Closing the Loop on NNs: Verifying a neural network in isolation isn't enough for robotics. BehaVerify focuses on closed-loop verification—checking how the NN interacts with the BT logic and a non-deterministic environment over time.
  • Semantic Precision Matters: The paper highlights that "Behavior Trees" isn't a single monolithic standard. Different libraries (like PyTrees vs. BehaviorTree.cpp) handle memory and sequences differently. BehaVerify specifically aligns with PyTrees semantics to ensure its verifications are relevant to real-world deployments.

Key Results

BehaVerify demonstrates significant performance leads over existing state-of-the-art tools:

  • Massive Scalability: In the binary-tree benchmark, BehaVerify verified a 2,055-node tree in just 2.24 seconds. In contrast, the "naive" encoding method timed out after 5 minutes on a tree with only 263 nodes.
  • Superior Speed: When compared to BT2Fiacre on a drone height-invariant check, BehaVerify completed the task in 0.48 seconds, while BT2Fiacre timed out.
  • Bug Discovery: BehaVerify successfully identified a battery-priority violation in a drone model that had been previously published but not flagged by other tools, proving that faster verification allows for checking more (and more complex) properties.

The execution flow and state transitions are illustrated in this hypothetical execution table:

Hypothetical execution of the BT

Limitations and Future Work

While powerful, the authors acknowledge a few current limitations:

  • Parallel Execution: BehaVerify follows PyTrees' sequential execution model and does not currently support "true" parallel node execution (where multiple nodes run simultaneously in one tick).
  • DSL Verbosity: The current DSL can be verbose for end-users. Future updates aim to allow users to edit leaf behaviors and specifications directly within the Graphical User Interface (GUI).
  • Tool Integration: The team plans to expand output options to support other frameworks like BehaviorTree.cpp and develop a language server for VS Code to provide real-time verification during the design phase.

Summary updated

Abstract

This paper presents BehaVerify, a verification toolbox for behavior trees (BTs) and Neuro-Symbolic BTs. BTs are a graphical language for planning and sequencing behaviors - similar to extended state machines - and are increasingly used in safety-critical domains. BehaVerify enables users to specify a BT using a Domain Specific Language (DSL) with formal syntax and semantics. This language further includes Linear Temporal Logic and Computation Tree Logic specifications. BehaVerify uses an efficient encoding into nuXmv, called fastforwarding, to quickly verify if a specification holds over the BT. Additionally, BehaVerify can generate implementations of the BT in Python and Haskell. Through Python, BehaVerify has been integrated with PyTrees and Robot Operating System (ROS) and has been deployed to several autonomous robotic systems, including for verifying runtime monitors. While prior works have developed the underlying theory, this manuscript focuses on the toolbox usage, functionality and implementation. BehaVerify is open source: https://github.com/verivital/behaverify
BibTeX
@misc{serbinowska2026behaverify,
  author = {Serena S. Serbinowska and Ben Wooding and Diego Manzanas Lopez and Luke Nam and Anne M. Tumlin and Nicholas K. Potteiger and Hongchao Zhang and Taylor T. Johnson},
  title = {{BehaVerify: A Formal Verification Tool for Behavior Trees}},
  year = {2026},
  eprint = {2611.22403},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22403},
}
Figure