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:
- 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).
- 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.
- 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.
- Spine Memory: Instead of replaying massive text transcripts, the traverser maintains a compact "task spine" of visited macro nodes, drastically reducing context bloat.
- 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.
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).
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