Traversal-as-Policy: Log-Distilled Gated Behavior Trees as Externalized, Verifiable Policies for Safe, Robust, and Efficient Agents

Peiran Li, Jiashuo Sun, Fangzhou Lin, Shuo Xing, Tianfu Fu, Suofei Feng, Chaoqun Ni, Zhengzhong TuarXiv 2026 · arXiv

TL;DR

Traversal-as-Policy introduces Gated Behavior Trees (GBTs) to transform autonomous LLM agents from unpredictable text generators into verifiable, structured controllers. By distilling successful execution logs into an externalized action tree and enforcing deterministic safety gates, this training-free method dramatically boosts agent success rates while driving safety violations to near-zero and slashing token costs.

What Problem Does This Paper Address?

When deployed on long-horizon tasks like software engineering or web navigation, autonomous LLM agents frequently fail due to "plan drift"—compounding errors over long sequences of actions that lead to irrecoverable dead-ends. This happens because their control policies remain implicit, buried within model weights and messy, ever-growing prompt transcripts.

Furthermore, current safety measures are usually retrofitted post-hoc using text-based guardrails or secondary "guardian" agents. These are not only expensive but also vulnerable to prompt injection, jailbreaking, and summarization errors. This paper addresses the need for an explicit, reusable, and verifiable policy artifact that unifies robust long-horizon control with ironclad safety enforcement.

Methods

The authors propose a "Policy-as-Data" paradigm that extracts an explicit control structure from execution logs without updating model weights:

  1. Offline Distillation: Raw trajectories from a sandboxed environment (OpenHands) are segmented into state-conditioned "action macros" (e.g., Inspect Failing Test, Apply Filters). Successful paths are merged into a single Gated Behavior Tree (GBT).
  2. Deterministic Gating: Unsafe traces are replayed and shrunk to minimal violating windows. The system synthesizes global and node-local pre-execution gates that evaluate structured sandbox context (e.g., file paths, domains, process metadata) rather than raw text. These gates follow experience-grounded monotonicity—once a context is rejected, it stays rejected forever.
  3. Online Traversal: At runtime, a lightweight traverser matches the base LLM's intent to the tree's macro nodes. If the agent stalls or gets blocked, it uses Dijkstra's algorithm to find a risk-aware shortest path to a feasible success leaf.
  4. Spine Memory: Instead of replaying massive text transcripts, the traverser maintains a compact "task spine" of visited macro nodes, drastically reducing context bloat.
  5. Self-Evolution (GBT-SE): A failure-driven loop optimizes the tree offline by locally repairing failed paths using analogical successes from other tasks, verified against strict regression tests.
Figure 1. Overview of Traversal-as-Policy. Gated Behavior Tree (GBT) distills offline logs into a gated tree artifact. Online traversal wraps a base LLM, executing macros under deterministic gates and using risk-aware recovery. Self-evolution safely evolves the policy under strict regression invariants.

Datasets

The framework was evaluated inside a unified OpenHands sandbox across 15+ benchmarks, prominently featuring:

  • SWE-bench Verified: 500 software engineering problems.
  • WebArena: 812 multi-step web interaction tasks.
  • GPQA: 448 graduate-level reasoning questions (with external web browsing disabled).
  • Safety Suites: Agent-SafetyBench, AgentHarm, and Agent Security Bench (ASB).

Key Insights and Ideas

  • Decoupling Reasoning from Execution: Because the long-horizon policy is externalized into the GBT, heavy reasoning models are only needed offline to build and refine the tree. At deployment, smaller, edge-friendly models can execute complex tasks simply by traversing the predetermined macros.
  • Immunity to Prompt Hacking: Because safety gates operate strictly on deterministic, structured sandbox states (JSON-like fields) rather than free-form text summaries, they cannot be bypassed by clever phrasing or prompt injections.
  • Arresting Long-Horizon Drift: By constraining the LLM's choices to successors grounded in prior successes, the traverser prevents the agent from wandering into unrecoverable states.

Key Results

  • SWE-bench Verified: GBT-SE raised the base model's success rate from 34.6% to 73.6%, while reducing safety violations from 2.8% to 0.2% and significantly cutting token usage.
  • WebArena: Success rates skyrocketed from 19.7% to 66.9%, proving that risk-aware recovery effectively converts stalls into progress.
  • Empowering Small Models: In executor-decoupling tests, smaller 8B-scale models (like Llama-3-8b and Qwen3-VL-8B) more than tripled their native performance when guided by a GBT distilled by a larger model (e.g., Llama-3-8b jumped from 12.6% to 46.4% on SWE-bench).
Table 3. GPQA (Protocol A, 448 questions): accuracy (Acc, %), coverage (Cov, %), and safety (Viol/USucc) under OpenHands monitors/checkers. External web browsing is disabled.

Limitations and Future Work

  • Coverage-Scoped Boundaries: GBT only steers long-horizon control when a task confidently routes to a known family subtree (covered=1). Outside this boundary (covered=0), the system abstains from tree guidance and falls back to standard generation, relying solely on global primitive guardrails.
  • Bounded-History Constraints: The deterministic safety gates look at a limited window of recent actions, meaning they might miss highly complex, long-range causal security hazards or deep semantic vulnerabilities.
  • Future Directions: The authors suggest expanding tree compositionality, scaling to open-world environments by dynamically updating tool schemas, and exploring more expressive safety specifications like lightweight temporal logic over event streams.

Summary updated

Abstract

Autonomous LLM agents fail because long-horizon policy remains implicit in model weights and transcripts, while safety is retrofitted post hoc. We propose Traversal-as-Policy: distill sandboxed OpenHands execution logs into a single executable Gated Behavior Tree (GBT) and treat tree traversal -- rather than unconstrained generation -- as the control policy whenever a task is in coverage. Each node encodes a state-conditioned action macro mined and merge-checked from successful trajectories; macros implicated by unsafe traces attach deterministic pre-execution gates over structured tool context and bounded history, updated under experience-grounded monotonicity so previously rejected unsafe contexts cannot be re-admitted. At runtime, a lightweight traverser matches the base model's intent to child macros, executes one macro at a time under global and node-local gating, and when stalled performs risk-aware shortest-path recovery to a feasible success leaf; the visited path forms a compact spine memory that replaces transcript replay. Evaluated in a unified OpenHands sandbox on 15+ software, web, reasoning, and safety/security benchmarks, GBT improves success while driving violations toward zero and reducing cost. On SWE-bench Verified (Protocol A, 500 issues), GBT-SE raises success from 34.6% to 73.6%, reduces violations from 2.8% to 0.2%, and cuts token/character usage from 208k/820k to 126k/490k; with the same distilled tree, 8B executors more than double success on SWE-bench Verified (14.0%58.8%) and WebArena (9.1%37.3%).
BibTeX
@misc{li2026traversal,
  author = {Peiran Li and Jiashuo Sun and Fangzhou Lin and Shuo Xing and Tianfu Fu and Suofei Feng and Chaoqun Ni and Zhengzhong Tu},
  title = {{Traversal-as-Policy: Log-Distilled Gated Behavior Trees as Externalized, Verifiable Policies for Safe, Robust, and Efficient Agents}},
  year = {2026},
  eprint = {2603.05517},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.05517},
}
Figure