SharedKV-BT: fast typed decisions for behavior-tree agents

Our new paper, SharedKV-BT, written with Justin Wagle, looks at a problem every agent runs into: making a chain of dependent decisions quickly, in the right order, and without trusting the model to say when the job is done.

Why this is hard

A robot cannot place an object before grasping it. A computer-use agent cannot paste a file before selecting it. Each decision depends on the stage of the task and on what actually happened in the environment.

Letting an LLM generate the next action as free text is flexible, but decoding token by token adds latency that grows with the output. A classifier is fast, but it picks from one fixed set of labels. Typed decisions sit in between: the model fills named fields, such as a skill and an object, by choosing from candidate lists. On their own, though, typed decisions don't know when a decision is needed, which candidates make sense at that moment, or whether the last action worked. Without that, an agent can act out of order, repeat what it already did, or stop because the model claimed success.

The idea

SharedKV-BT splits the work three ways.

The behavior tree decides when to ask and what can be chosen. Each active node exposes only its own fields and candidates. In pick-and-place, the Acquire, Transport, and Deposit nodes each offer different skills and arguments.
The model only ranks candidates. We encode the instruction and the observed state once, keep the key-value cache of that shared prefix, and score every candidate in a single batch. A candidate's score is the average log-probability of its own tokens, which avoids favoring short labels.
An external check decides whether to move on. The model's own "done" output is recorded but never advances the task. Retries have a fixed budget.

Diagram of SharedKV-BT. Left: a behavior tree runs Acquire, Transport, and Deposit, and the Acquire stage loops through a decision, execution, and an external check. Right: the instruction and state are encoded once, and skill, object, and completion candidates are scored in parallel. — The tree runs each stage as a bounded loop of decision, execution, and an external check. Inside a decision, the instruction and state are encoded once and the stage's candidates are scored in parallel. Figure from the paper (arXiv:2610.07327).

What we found

All numbers below use Qwen2.5-3B-Instruct on a single RTX 2080 Ti.

Speed. Against prompt-matched constrained autoregressive decoding, one decision took 99.8 ms instead of 413.8 ms on robot stacking (4.15×), 121.4 ms instead of 286.0 ms on kitchen navigation (2.36×), and 134.2 ms instead of 318.8 ms on a Windows Clock task (2.38×).
Accuracy from node-local options. On 120 saved pick-and-place states, offering only the active node's options gave the correct skill-and-object decision in 113 states (94%), against 90 (75%) when every stage's options were offered at once. In closed loop, the node-local version finished 18 of 30 four-object episodes. The global version finished none.
Order and completion. Replaying identical scores on 15 stacking states, full behavior-tree control made no errors. Without stage gating, the policy chose DONE before grasping or placing in 10 states. Without the external check, the model's completion claim ended the task early in 10 states.

Limits

The experiments run in simulation and on three fixed Windows tasks, so they don't show generalization to new tasks or real hardware. The method assumes the behavior tree, candidates, skills, and checks are defined in advance. Saying "none of these" is still open: candidate scores alone were not enough to reject invalid options reliably. And the speedup depends on the setup. With only two field-candidate pairs, shared-KV scoring was slower than decoding (0.51×), because copying the cache cost more than it saved.

The paper has the full method, ablations, and failure cases: arXiv:2610.07327.