Verify--Backtrack Loop: Structured Precondition Recovery for Long-Horizon Language Agents
Organizations: Department of Computer Science, City University of Hong Kong · Huawei Noah’s Ark Lab, Hong Kong
Abstract
Language agents increasingly tackle long-horizon tasks in interactive environments, where actions often depend on latent preconditions. The core difficulty is not trajectory length but recovery: when a prerequisite is missing or an earlier decomposition fails, trying another plausible action rarely helps. ReAct and later reflection or adaptive-planning methods support local correction, but express recovery as free-form text, with no explicit control state linking the terminal goal, the active goal, and the failure source. We introduce the Verify--Backtrack Loop (VBL), a training-free extension of ReAct that turns precondition discovery and failure diagnosis into structured planning-state updates. VBL maintains the task decomposition as a bounded goal stack and, on goal activation, execution failure, or material state change, jointly verifies two horizons---whether the active goal contributes to the terminal goal and whether it is feasible in the current state. These dual-horizon judgments, combined with typed failure attribution, trigger explicit operations---Push, Pop, retry, or BacktrackTo the parent. We evaluate VBL with Qwen3.5-9B, GPT-4o, and DeepSeek-V3.2 on AppWorld, ALFWorld, and ScienceWorld. VBL improves over ReAct and reflection-based control on every backbone--benchmark pair. On the challenging AppWorld setting, it improves task success by up to 22.07 percentage points over ReAct. Ablations show that removing either verification or diagnosis degrades performance, in several settings below ReAct, confirming that the two mechanisms are complementary. These results show that reliable long-horizon interaction benefits from revising the planning state, not merely the next action.
Figures & tables
| AppWorld | |||||
|---|---|---|---|---|---|
| Model | Method | Normal | Chall. | ALFW. | SciW. |
| Qwen3.5-9B | NoThinking | 14.29 | 7.43 | 69.40 | 21.80 |
| ReAct | 17.26 | 8.63 | 81.34 | 33.18 | |
| ReflAct | 22.62 | 13.19 | 86.57 | 36.97 | |
| VBL | 35.71 | 30.70 | 87.31 | 47.39 | |
| GPT-4o | NoThinking | 17.86 | 10.55 | 67.16 | 35.55 |
| Benchmark | Method | SR | kTok | kTok/S |
|---|---|---|---|---|
| AW-N | ReAct | 17.26 | 138.9 | 804.8 |
| VBL | 35.71 | 221.5 | 620.2 | |
| AW-C | ReAct | 8.63 | 223.3 | 2587.5 |
| VBL | 30.70 | 448.5 | 1460.9 | |
| ALFW. | ReAct | 81.34 | 63.1 | 77.6 |
| VBL | 87.31 | 67.1 | 76.9 |
| AppWorld | ALFW. | SciW. | ||
| Variant | Normal | Chall. | ||
| Qwen3.5-9B | ||||
| VBL (full) | 35.71 | 30.70 | 87.31 | 47.39 |
| w/o Verify | 35.12 | 28.06 | 76.12 | 40.28 |
| w/o Diagnose | 34.52 | 28.54 | 79.85 | 41.23 |
| GPT-4o | ||||
| Push | Backtrack | ||||
|---|---|---|---|---|---|
| Bench. | Model | mean | %ep | mean | %ep |
| AW-N | Qwen3.5-9B | 1.10 | 63.1 | 0.22 | 13.7 |
| GPT-4o | 0.42 | 33.9 | 0.05 | 4.8 | |
| DeepSeek-V3.2 | 0.77 | 69.0 | 0.04 | 4.0 | |
| AW-C | Qwen3.5-9B | 1.55 | 93.5 | 0.47 | 27.3 |
| GPT-4o | 0.89 | 71.2 | 0.12 | 8.2 | |
| Task: settle shared dinner on Venmo (taxi requests + pay Nancy) |
|---|
| ReAct / ReflAct (fail). search_contacts / search_users 401 (no token) retry unauthorized / ill-formed calls step limit or incomplete settlement. ReAct , ReflAct |
| VBL (succeed). |
| 1. phone.search_contacts(‘‘Nancy’’) 401 (token missing) 2. Verify Push (login) : phone.login / venmo.login tokens issued 3. create_payment_request (“Taxi”), create_transaction (“Food”) sent. |
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| AppWorld | ALFWorld | ScienceWorld | |
|---|---|---|---|
| Stack depth | 6 | 6 | 6 |
| Retry limit | 8 | 8 | 8 |
| Push limit | 4 | 4 | 4 |
| at the root goal | 1 | 1 | 1 |
| Backtrack limit | 3 | 3 | 3 |
| Diagnosis threshold | 2 | 2 | 2 |
| Field | Content |
|---|---|
| Active-goal description at the time of the segment | |
| context | Short local context (recent observation / stack focus) |
| action | Action (or code block) that closed the segment |
| outcome | Post-action observation or success/failure signal |
| attribution | Diagnose label when the segment ended in failure; empty on clean Pop |
| recovery | Stack operation applied ( Push / Pop / BacktrackTo / retry) |
| Task: request $13 from Stacy on Venmo (note: “For yesterday’s meal”, privacy: public) | |
|---|---|
| ReflAct (fail) | VBL (succeed) |
| login find Stacy | Verify Push ( login ) token |
| Action: create_transaction (send money) | search_friends arg error |
| Diagnose BacktrackTo (parent) | |
| Obs: “Sent money.” mutates Transaction | Action: create_payment_request ($13, public note) |
| Result: tests | Result: tests |
| Qwen3.5-9B | DeepSeek-V3.2 | |||
|---|---|---|---|---|
| ALFWorld task type | ReAct | VBL | ReAct | VBL |
| look_at_obj_in_light | 77.8 | 100.0 | 100.0 | 100.0 |
| pick_and_place_simple | 100.0 | 100.0 | 95.8 | 100.0 |
| pick_clean_then_place | 77.4 | 83.9 | 87.1 | 100.0 |
| pick_cool_then_place | 95.2 | 95.2 | 90.5 | 95.2 |
| pick_heat_then_place | 52.2 | 65.2 | 69.6 | 78.3 |
Long-Horizon LLM Agents
Long-horizon large language model agents plan, use tools, and preserve task state across extended, multi-step interactions.
See all 484 papers