WorksComputer Science
Verify–Backtrack Loop: Structured Precondition Recovery for Long-Horizon Language Agents
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.
Introduction
Language models increasingly act through tools, web interfaces, software environments, and embodied systems [1, 2]. Many of these interactions are long-horizon: actions change an external state, their effects accumulate, and later decisions depend on earlier outcomes. Reliable execution therefore requires an agent to preserve the terminal goal while adapting its intermediate plan. The difficulty is not simply trajectory length. Dependencies among intermediate goals may be absent from the instruction and become visible only during execution. When such a prerequisite is missed, several subsequent actions may fail. Choosing another plausible action is rarely enough: the agent must identify the source of the failure and revise the corresponding level of task decomposition.
ReAct [1] provides a general basis for interactive agents by interleaving reasoning, action, and observation. It adapts the next decision to new evidence, but it does not impose an explicit hierarchy over goals. Its interaction history records what happened without specifying which short-horizon goal is active, how that goal contributes to the terminal goal, or where planning should resume after repeated failure. Adaptive and search-based planners revise plans or explore alternative paths [3, 4, 5], and reflection methods revise outputs or actions through critique and goal-conditioned feedback [6, 7, 8]. These approaches improve adaptation, yet recovery remains predominantly textual: there is typically no compact planning state that jointly represents the terminal goal, the active goal, and the causal source of a failure.
The central challenge is therefore not merely to revise the next action, but to revise the planning state at the appropriate level. Such revision requires two goal horizons. The terminal goal defines task completion, whereas the active goal defines the immediate objective under the current decomposition. Before execution, the active goal should both contribute to the terminal goal and be feasible in the current state. After failure, the agent must determine whether to insert a missing prerequisite, retry locally, or return to an earlier decomposition.
Based on this formulation, we propose the Verify–Backtrack Loop (VBL), a training-free extension of ReAct that converts precondition discovery and failure diagnosis into structured updates of planning state. VBL represents the evolving decomposition as a bounded goal stack whose root is the terminal task and whose top is the active goal. A dual-horizon verifier evaluates terminal-goal alignment and active-goal readiness when the active goal is installed, after an execution failure, and after a material state change. Typed failure attribution then maps repeated failures to explicit stack operations—inserting a missing prerequisite with PUSH, or BACKTRACKTO the parent—while a goal verified as complete is removed with POP. Because each stack update re-arms verification, a restored ancestor that is still misaligned triggers further steps upward. The executor is conditioned on the root task text and the selected active goal, so inserting a prerequisite or returning to a parent directly changes subsequent action selection. Backtracking changes the planning state rather than the environment state: executed actions are not reversed; instead, invalid descendants are removed and planning resumes from the restored ancestor under the current observation. This distinction makes VBL applicable to stateful environments in which actions may be irreversible. Figure 1 contrasts this control structure with the linear loops of ReAct and ReflAct.

Figure 1. Control structures compared. (1) ReAct interleaves thought, action, and observation in a linear loop. (2) ReflAct replaces the thought with reflection on the current state relative to the task goal, but the loop stays linear. (3) VBL maintains an explicit goal stack: VERIFY checks alignment and readiness when is set (on activation, after failure, or after a material state change), a completed goal is removed with POP, and a failure is routed through DIAGNOSE to one of PUSH (insert a prerequisite), a local retry, or BACKTRACKTO (resume from the parent). The executor receives the root task text together with the active goal—here —not the full stack.
We evaluate VBL with Qwen3.5-9B, GPT-4o, and DeepSeek-V3.2 on three public benchmarks: AppWorld, ALFWorld, and ScienceWorld. Holding the backbone, interaction budget, and environment interface fixed within each setting, VBL improves over the baselines on every backbone–benchmark pair. Relative to ReAct, it improves task success by up to 22.07 percentage points on AppWorld, 14.21 percentage points on ScienceWorld, and 10.45 percentage points on ALFWorld. Component ablations further show that removing either verification or diagnosis degrades performance, in several settings to below the ReAct baseline, so the two mechanisms are complementary rather than redundant: a goal stack driven by only one of them can be worse than no stack at all. Our contributions are as follows:
We formulate long-horizon agent control as a dual-horizon problem that distinguishes terminal-goal alignment from active-goal readiness, allowing misaligned and blocked goals to trigger different planning decisions.
We propose VBL, a training-free extension of ReAct that maps verification and typed failure attribution to explicit transitions over a bounded goal stack.
We evaluate VBL across three public interactive benchmarks and three backbone models. With backbone, budget, and environment interface held fixed, VBL improves task success over the baselines on every evaluated pair, while ablations show that verification and diagnosis are complementary rather than redundant.
Related Work
Reasoning, acting, and reflection. Chain-of-thought prompting elicits intermediate reasoning for multi-step problems [9], and ReAct extends this principle to interactive settings by interleaving reasoning, action, and observation [1]. Feedback-based variants revise outputs or actions through critique and reflection: Self-Refine iterates on model outputs [6], Reflexion stores verbal lessons across attempts [7], and ReflAct conditions the next action on the relation between the current state and the task goal [8]. These methods show that reflection improves adaptation, but recovery typically remains free-form text rather than an update to an explicit control state. VBL addresses that interface by separating terminal-goal alignment from active-goal readiness and mapping verification and typed failure attribution to prescribed transitions over a goal stack. We compare against ReAct and ReflAct under a shared executor; multi-trial memory and multi-stage metacognitive controllers are outside our single-episode protocol.
Planning, decomposition, and search. Prompted decomposition [10, 11] and adaptive or search-based planners [3, 4, 5, 12, 13] revise an explicit plan or explore alternative reasoning and action paths. VBL asks a narrower within-episode question: when a single active path becomes blocked, which level of its decomposition should change? It retains one bounded goal stack rather than a search tree, inserts a missing prerequisite when the active goal is aligned but infeasible, and backtracks toward the parent when the current decomposition is invalidated. The emphasis is on explicit recovery points and targeted planning-state revision rather than broad path exploration.
Hierarchical control and agent memory. Hierarchical agents organize long trajectories around subgoals; HiAgent, for example, treats subgoals as working-memory units and summarizes observations tied to completed subgoals [14]. VBL’s hierarchy is the bounded goal stack: it represents the current decomposition and its recovery points, and the executor is conditioned on the root task text and the active goal rather than the full stack. Episode-local summaries used by the full VBL configuration (§ 3.4) are an implementation detail for limiting context rather than a separate memory contribution; they are discarded when the task ends.
VBL’s distinguishing contribution is therefore not any single ingredient above, but their coupling through a common control representation: a goal-stack transition that links terminal alignment, local feasibility, failure attribution, and subsequent execution.
Methodology
VBL augments a ReAct executor with an explicit planning state. Its central principle is to separate two decisions that are often merged in a free-form trajectory: whether the active goal is both relevant and feasible, and how the task decomposition should change when execution fails. A bounded goal stack turns these judgments into control operations. Figure 1 contrasts this control structure with the linear loops of ReAct and ReflAct.
Problem Formulation
We consider an agent that receives a natural-language instruction and acts in a stateful environment. A task is represented as a goal-conditioned, partially observed sequential decision process
Here, , , and denote the state, action, and observation spaces. The transition function governs changes to the environment, and produces an observation after each action. The instruction induces a terminal goal predicate . The interaction budget is .
The true state is not directly observed. Let denote the initial observation before any action, and let () denote the observation returned after executing . At decision step , the agent conditions on the interaction history
with . Before selecting , the controller reads the latest available observation when and . Post-action observations may carry execution feedback for the preceding action—for instance an error message or a failed unit test—which is the only failure signal the agent receives. An episode succeeds if the terminal goal is reached within budget:
Long-horizon tasks contain intermediate goals whose dependencies are not fully specified by the instruction. Let denote a latent set of subgoal predicates, with , and let denote a latent precedence relation. If , then must hold before an action can complete :
Neither nor is given to the agent. Both must be inferred from the instruction, the interaction history, and environmental feedback. The predicate is likewise unavailable to the agent; it is evaluated only by the environment to score an episode. Every judgment VBL makes internally is conditioned on the instruction text , which is the agent’s only representation of the terminal goal, together with and .
Dual-Horizon Control State
VBL represents the task at two temporal scales. The terminal goal defines successful completion. The active goal defines the immediate objective under the current decomposition. These goals serve different roles. Terminal-goal alignment prevents local progress from drifting away from the task, whereas active-goal readiness prevents the agent from attempting a step whose prerequisites are not yet satisfied.
At each decision point, VBL estimates two properties:
Alignment concerns the contribution of to . Readiness concerns the feasibility of in the current environment. Both are properties of the underlying task, so VBL only estimates them; as noted above, the estimates are formed from the instruction text rather than from itself. Keeping these judgments separate allows a goal to be represented as aligned but blocked, or feasible but misaligned. The former calls for a prerequisite; the latter calls for revision of the decomposition.
The planning state is a bounded goal stack . Its root stores the instruction text that induces the terminal predicate , and its top element is the active goal . Each node stores a description , a parent pointer, a consecutive-failure counter , a retry counter , and a set of previously proposed prerequisites; a path may additionally be marked failed when recovery abandons it.
The stack supports three operations:
PUSH places a missing prerequisite above the active goal;
POP marks the active goal as complete and restores its parent as the active goal; and
BACKTRACKTO removes the descendants of an ancestor and resumes decomposition from . In the controller, each invocation targets the parent of the active goal; because every stack update re-arms verification, a parent that is itself misaligned triggers a further step upward, so ascent continues until an aligned ancestor remains or the root is reached. All later mentions of backtracking assume this behavior.
Alignment holds trivially at the root, since is the terminal task description itself; VERIFY there only separates a completed task from an incomplete one, so ascent always terminates at the root. Backtracking at the root, which diagnosis can still prescribe, invalidates the current decomposition but retains . The operation changes planning state only. It does not reverse actions or restore an earlier environment state. Replanning therefore conditions on the current observation, including all effects of earlier actions.
Each control iteration optionally verifies the active goal and then executes it with the ReAct policy. If the goal is completed, VBL pops it; if execution repeatedly fails, VBL diagnoses the cause and applies one stack transition before resuming. Algorithm 1 states this control skeleton; admissibility checks, retry/backtrack budgets, episode-buffer updates, and the full branching logic used in experiments appear in Appendix B. The ReAct executor retains its original instruction and action format. At step , VBL supplies the decision context
where is the root instruction that induces , and is a lightweight episode buffer (Section 3.4). Thus, the executor observes the terminal-task text, the selected active goal, and only the records relevant to that goal; the remaining stack stays inside the controller.
Algorithm 1 Verify–Backtrack Loop (simplified)
Require: environment , ReAct policy , budget , threshold
with ;
while and do
if needs verification then on activation; after failure; after material state change
if complete then POP; continue
else if misaligned then BACKTRACKTO parent; continue re-verify the restored ancestor next
else if blocked and admissible then PUSH; continue
end if
end if
; execute ; observe ;
if complete under then POP; continue
end if
if is a failure then
if then
;
apply one of PUSH / retry / BACKTRACKTO(parent) according to
end if
end if
end while
Verify–Backtrack Loop
Verification and Structured Recovery
Verification is gated by a flag , raised on goal activation (including after PUSH, POP, or BACKTRACKTO), after failure, and after a material state change, and cleared once VERIFY runs. Between actions that leave readiness intact, the controller does not re-verify. Each call uses the same underlying model under a fixed output schema; its tokens are counted like executor calls. Prompts use in place of . The verifier returns
with alignment , readiness , an optional missing prerequisite , and evidence .
Three rules follow. A completed goal is popped. A misaligned goal triggers BACKTRACKTO its parent and re-arms , so the restored ancestor is re-verified before the next action. An aligned but blocked goal pushes when admissible—concrete, actionable, absent from both and the stack, and within depth and push limits. If readiness is uncertain, or if the goal is blocked but no admissible exists, the controller does not invent a subgoal: it executes the active goal and defers recovery to post-failure diagnosis. When an admissible is proposed, verification withholds the blocked action and inserts the prerequisite first (§ 4.5 ablates this module).
A single failure may be transient, so VBL permits up to local retries. After consecutive failures on the same goal, a schema-constrained diagnostic call returns
where is the failing post-action observation, the attributed cause, an optional prerequisite, and the evidence. Each invocation prescribes one stack transition (Table 1).
| Attribution | Interpretation | State transition |
| MISSINGPRECOND | prerequisite is absent | PUSH() |
| WRONGDECOMP | current decomposition is unsuitable | BACKTRACKTO parent |
| TRANSIENT | temporary execution failure | retry within |
| UNRECOVERABLE | current path cannot progress | mark failed; BACKTRACKTO parent |
Table 1. Failure attributions returned by DIAGNOSE and the single goal-stack transition each one prescribes.
If a proposed prerequisite is inadmissible, or a transient error exceeds , the path is treated as incorrect or unrecoverable and the controller backtracks to the parent. Thus VERIFY revises the active goal before the next action when evidence already supports a stack update, while DIAGNOSE resumes planning after local retries still fail.
Bounded Execution
The procedure uses a maximum stack depth , a per-goal retry limit , and a global interaction budget . Per-goal limits on pushes and on backtracks prevent repeated decompositions that do not produce a new state. These bounds also ensure termination: actions consume , retries consume the per-goal allowance, and stack changes consume the finite push and backtrack allowances.
In the full VBL configuration reported in our experiments, completed and failed trajectory segments are summarized into a short episode-local buffer
with each field grounded in an environment observation or a recorded state transition. Before execution, Retrieve() attaches records associated with the active goal or its current failure type to when such records exist. Retrieval is cleared when the task ends; cross-task storage is not considered here. The buffer is an implementation detail for limiting context rather than a separate memory contribution (§ 2).
Reduction to ReAct. If verification and diagnosis are disabled, the stack remains , the episode buffer is unused (Retrieve returns nothing), and reduces to the original instruction . Every action is then generated by the base ReAct executor from the same interaction history and action format. Under this configuration, our ReAct baseline matches the executor with no stack-conditioned control, enabling comparisons that vary only VBL’s additional control mechanisms. The ablations in § 4.5 sit between these two extremes: each disables exactly one of verification and diagnosis while retaining the goal stack. Algorithm 1 is the control skeleton; the complete procedure is given in Appendix § 8.
Experiments
We evaluate whether structured precondition handling improves long-horizon interactive agents relative to linear acting and goal-conditioned reflection. Unless otherwise noted, all methods share the same backbone model, interaction budget, and environment interface within each setting; the methods differ only in their control layer, which for VBL comprises the goal stack, the verification and diagnosis modules, and the episode-local buffer (§ 3.4).
Experimental Settings
Benchmarks. We evaluate on three complementary interactive environments that stress long-horizon planning under latent preconditions: AppWorld [15] (interactive coding), ALFWorld [16] (text-embodied household), and ScienceWorld [17] (scientific procedures). We use the AppWorld Normal (168) and Challenge (417) test splits, ALFWorld valid_unseen (134), and ScienceWorld test (211 episodes / 24 types); detailed environment descriptions are in Appendix § 7.
Agent models. To assess robustness across model families, we instantiate every method with three backbones spanning scale and access regime: Qwen3.5-9B (open-weight, smaller-scale), GPT-4o (closed-source, frontier-scale), and DeepSeek-V3.2 (open-weight, large-scale). Holding the agent framework fixed while varying the backbone isolates the contribution of VBL’s control layer from raw model capacity.
Metrics. Our primary metric is task success rate (%), i.e., the fraction of episodes for which the terminal goal predicate is satisfied within the interaction budget (for AppWorld, an episode counts as successful only when all unit tests pass). To characterize cost, we report average tokens per episode (kTok) and tokens per solved task (kTok/S). Token counts include every LLM call uniformly across benchmarks and methods—executor, VERIFY, DIAGNOSE, and SUMMARIZE in the full VBL configuration—so controller overhead is never omitted from the cost comparison.
Implementation details. All methods share the same environment adapters, ReAct action format, and decoding configuration within each backbone. We cap execution at 50 environment steps on ScienceWorld, 50 on ALFWorld, and 40/60 on AppWorld Normal/Challenge. The per-episode LLM-call budget is on every benchmark. For VBL we use a maximum stack depth , a per-goal retry limit , per-goal limits and , and a diagnosis threshold .1 Verification runs whenever due is set (§ 3.3). Episode-local buffers are cleared when the task ends. VBL is training-free; control bounds are shared across benchmarks, while the step budget follows each environment’s horizon.
Baselines
We compare VBL against three representative policies under a shared ReAct executor and single-episode protocol (§ 2): NoThinking emits actions directly from the observation and instruction (lower-bound acting); ReAct [1] interleaves free-form thoughts with actions in a linear think–act–observe loop (the template VBL wraps—with verification and diagnosis disabled, the executor matches this baseline; § 3); and ReflAct [8] replaces next-action prediction with goal-conditioned reflection, recovering via free-form textual revision rather than structured stack operations. No baseline maintains a comparable episode buffer, so ReAct–VBL isolates VBL’s control layer; we do not evaluate tree-search planners or multi-trial memory agents.
Main Results
Table 2 reports task success rates (%) across benchmarks and backbones. VBL is the best method on every backbone–benchmark pair.
| Model | Method | AppWorld Normal | AppWorld Chall. | ALFW. | SciW. |
| Qwen3.5-9B | NoThinking | 14.29 | 7.43 | 69.40 | 21.80 |
| Qwen3.5-9B | ReAct | 17.26 | 8.63 | 81.34 | 33.18 |
| Qwen3.5-9B | ReflAct | 22.62 | 13.19 | 86.57 | 36.97 |
| Qwen3.5-9B | VBL | 35.71 | 30.70 | 87.31 | 47.39 |
| GPT-4o | NoThinking | 17.86 | 10.55 | 67.16 | 35.55 |
| GPT-4o | ReAct | 48.81 | 30.22 | 85.07 | 50.71 |
| GPT-4o | ReflAct | 47.62 | 28.54 | 93.28 | 51.66 |
| GPT-4o | VBL | 50.00 | 31.65 | 94.78 | 57.35 |
| DeepSeek-V3.2 | NoThinking | 47.02 | 32.13 | 71.64 | 55.92 |
| DeepSeek-V3.2 | ReAct | 60.12 | 56.12 | 84.33 | 57.82 |
| DeepSeek-V3.2 | ReflAct | 61.31 | 48.68 | 86.57 | 66.35 |
| DeepSeek-V3.2 | VBL | 66.07 | 59.95 | 94.78 | 71.56 |
Table 2. Main results: task success rate (%) on AppWorld, ALFWorld, and ScienceWorld. Chall.: AppWorld Challenge split; ALFW.: ALFWorld; SciW.: ScienceWorld. VBL is the best method on every backbone–benchmark pair.
Gains over the acting baseline. Relative to ReAct, the largest improvements appear where latent preconditions dominate. On AppWorld Challenge, VBL improves by up to +22.07 points (Qwen3.5-9B, 8.63 → 30.70), with Normal-split gains of +18.45 points; the effect persists for stronger backbones (+3.83 and +5.95 for DeepSeek-V3.2). The pattern extends to embodied and scientific settings: up to +10.45 on ALFWorld (DeepSeek-V3.2) and +14.21 / +13.74 on ScienceWorld (Qwen3.5-9B / DeepSeek-V3.2). Explicit PUSH/BACKTRACK to control recovers from unmet preconditions more reliably than a linear think–act–observe loop.
Gains over reflection and consistency. Relative to ReflAct, structured stack operations remain more effective when the failure root lies several steps upstream. ReflAct is not uniformly better than ReAct—on some pairs it regresses (e.g., AppWorld with GPT-4o), consistent with unconstrained reflection endorsing fluent but goal-inverting actions. NoThinking is weakest on every backbone, confirming that VBL’s advantage is not merely the presence of any reasoning text, but the coupled verification–diagnosis loop. Token cost is analyzed in § 4.4; per-type gains appear in Appendix § 15.
Efficiency and Overhead
VBL adds verification and diagnosis calls, so a natural concern is overhead. Because those modules are themselves LLM calls, we compare token usage with all calls counted uniformly (§ 4.1). Table 3 reports average tokens per episode (kTok) and tokens per solved task (kTok/S = 100× kTok/SR) on Qwen3.5-9B. Per episode, VBL consumes more tokens on every benchmark. Per solved task, the cost–benefit picture is environment-dependent: on the harder AppWorld splits the success gain lowers kTok/S relative to ReAct; on easier ALFWorld the two methods are essentially tied; on ScienceWorld, despite a large SR gain, kTok/S rises because controller overhead outpaces the success improvement.
| Benchmark | Method | SR | kTok | kTok/S |
| AW-N | ReAct | 17.26 | 138.9 | 804.8 |
| AW-N | VBL | 35.71 | 221.5 | 620.2 |
| AW-C | ReAct | 8.63 | 223.3 | 2587.5 |
| AW-C | VBL | 30.70 | 448.5 | 1460.9 |
| ALFW. | ReAct | 81.34 | 63.1 | 77.6 |
| ALFW. | VBL | 87.31 | 67.1 | 76.9 |
| SciW. | ReAct | 33.18 | 66.6 | 200.7 |
| SciW. | VBL | 47.39 | 162.5 | 342.9 |
Table 3. Token cost on Qwen3.5-9B. AW-N/AW-C: AppWorld Normal/Challenge; ALFW.: ALFWorld; SciW.: ScienceWorld. SR: success rate (%); kTok: average thousands of tokens per episode (including VBL’s verification, diagnosis, and summarization); kTok/S: 100× kTok/SR. Bold: higher SR or lower kTok/S.
Ablation Study
To assess each control module, we compare full VBL against two leave-one-out variants that disable exactly one module while retaining the goal stack and the other: w/o VERIFY removes activation and feedback-triggered checks, and **w/o DIAGNOSE removes post-failure attribution together with the stack transitions and retry budget it prescribes.2 Table 4 summarizes the results.
| Variant | AppWorld | ALFW. | SciW. | |
| 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 | ||||
| VBL (full) | 50.00 | 31.65 | 94.78 | 57.35 |
| w/o VERIFY | 44.05 | 29.50 | 93.28 | 53.08 |
| w/o DIAGNOSE | 39.29 | 26.62 | 82.84 | 48.34 |
| DeepSeek-V3.2 | ||||
| VBL (full) | 66.07 | 59.95 | 94.78 | 71.56 |
| w/o VERIFY | 61.90 | 52.52 | 87.31 | 62.56 |
| w/o DIAGNOSE | 64.88 | 51.56 | 81.34 | 69.19 |
Table 4. Leave-one-out ablation of VBL’s two control modules across three backbone models (Qwen3.5-9B, GPT-4o, DeepSeek-V3.2). Success rate (%). Each variant retains the goal stack and the other module.
Full VBL outperforms both variants on every backbone–benchmark pair. Furthermore, the performance of some single-module variants is even lower than the ReAct baseline. The goal stack is therefore not a safe addition on its own; it pays off only when both modules govern it.
The two variants fail in characteristic ways. Without verification, a missing prerequisite or misaligned goal is handled only once DIAGNOSE fires after consecutive failures. Without diagnosis, the verifier still inserts prerequisites and backtracks on detected misalignment, but failures that verification does not resolve are never attributed, so a goal judged aligned and ready keeps spending actions at the wrong decomposition level.
Recovery-Operation Analysis
Beyond aggregate success, we ask which stack operations VBL actually uses on AppWorld, where multi-app control flow makes latent preconditions most severe. Table 5 reports PUSH and BACKTRACKTO frequencies.
| Bench. | Model | Push | Backtrack | ||
| 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 | |
| DeepSeek-V3.2 | 0.77 | 65.2 | 0.18 | 16.8 |
Table 5. Control-operation usage for VBL on AppWorld. AW-N/AW-C: AppWorld Normal/Challenge. “mean” is the average number of operations per episode; “%ep” is the fraction of episodes with at least one such operation. PUSH remains the dominant remedy; BACKTRACKTO is secondary but consistently higher on the harder Challenge split.
PUSH is the dominant remedy, firing in 33.9–93.5% of episodes: most unmet preconditions are resolved by inserting an enabling subgoal rather than discarding the plan. BACKTRACKTO is less frequent, but its rate tracks wrong-subgoal risk—on every backbone, Challenge episodes trigger backtracking more often than Normal ones (Qwen3.5-9B: 13.7% → 27.3%; GPT-4o: 4.8% → 8.2%; DeepSeek-V3.2: 4.0% → 16.8%). PUSH need not rise in parallel: for DeepSeek-V3.2 it is marginally lower on Challenge (65.2% vs. 69.0%) even as backtracking quadruples, consistent with harder episodes failing more often from a wrong decomposition than from a nameable missing prerequisite. Together with the ablation, this supports a coupled design: a high-frequency precondition inserter paired with a difficulty-sensitive stack repair.
Case Study
To illustrate how VBL converts unmet preconditions into successful trajectories, we examine an AppWorld episode using Qwen3.5-9B. In this episode, both ReAct and ReflAct fail, whereas VBL succeeds through a verification-triggered PUSH. A complementary example involving diagnosis and backtracking is provided in Appendix § 14. The task requires settling shared dinner expenses through Venmo: identifying the roommates, sending payment requests for the taxi fare, and paying Nancy for the food.3
Protected phone and Venmo endpoints return HTTP 401 when called without an access token. ReAct discovers this requirement only after a failed call. It then oscillates among unauthorized requests, login attempts with incorrect argument formats, and unproductive API-documentation lookups until reaching the step limit. ReflAct retains the overall objective but still repeatedly issues unauthorized calls or malformed search requests, failing to establish authentication reliably.
VBL, by contrast, treats authentication as an explicit precondition on the goal stack. The first 401 response raises due, causing VERIFY to run before the next protected call. VERIFY determines that the current goal remains aligned with the task but is blocked by missing authentication, and returns this prerequisite to PUSH as an enabling subgoal. Crucially, this intervention occurs without waiting for the consecutive failures required to trigger DIAGNOSE. Once the prerequisite has been satisfied, the agent obtains the required tokens before invoking the payment APIs, and the remaining calls proceed successfully (Figure 2).

Figure 2. Case study (task 2d9f728_1). Baselines thrash on auth errors; VBL inserts login via PUSH and completes the settlement.
The underlying ReAct loop remains unchanged; the improvement comes from inserting the missing enabling goal onto the stack, thereby turning a cascade of 401 errors into a short authenticated trajectory. This episode illustrates the feedback-triggered branch of verification described in § 3.
Conclusion
We presented the Verify–Backtrack Loop (VBL), a training-free extension of ReAct that maintains task decomposition as a bounded goal stack and converts verification and typed failure attribution into structured control operations (PUSH, POP, BACKTRACKTO). Across three interactive benchmarks and three backbones, VBL improves task success over linear acting and reflection-based control, with the largest gains where latent preconditions dominate; ablations show that removing either verification or diagnosis degrades performance, in several settings to below the ReAct baseline, so the two modules are complementary rather than redundant.
Several limitations remain. Both control modules rely on the backbone’s own judgment, so mistaken readiness or attribution decisions can corrupt the stack. Because backtracking revises planning state without reversing executed actions, VBL cannot undo irreversible side effects. The control layer also costs additional tokens. Natural next steps are stronger verification and diagnosis, true rollback when actions are reversible, and leaner control that preserves the same stack discipline at lower overhead.
Appendix
Benchmark Details
This section expands the three environments introduced in the experimental setup of § 4.1.
AppWorld. AppWorld [15] is a high-fidelity interactive coding benchmark in which agents complete day-to-day digital tasks by writing executable code against a suite of simulated applications and APIs. Tasks typically require multi-app control flow, authentication, identifier resolution, and recovery from API failures, making unmet preconditions a dominant failure mode. We evaluate on the Normal (168 tasks) and Challenge (417 tasks) test splits.
ALFWorld. ALFWorld [16] aligns text-based household goals with embodied ALFRED-style tasks. Agents navigate rooms, manipulate objects, and satisfy compositional instructions through text actions, so success depends on sequencing enabling subgoals (e.g., locating, cleaning, or heating an object) before the terminal action. We evaluate on the valid_unseen split (134 episodes).
ScienceWorld. ScienceWorld [17] is a text environment for elementary scientific experiments. Agents must operate instruments, track changing world state, and complete multi-step procedures, again exposing the need to establish experimental preconditions rather than jumping to the final measurement or conclusion. We evaluate on the test split (211 episodes spanning 24 task types).
Together, the three benchmarks cover interactive coding, household embodiment, and scientific procedural reasoning, providing a broad testbed for structured precondition recovery.
Full VBL Procedure
Section 3 states the control skeleton of VBL. Algorithm B.1 expands the procedure used in all experiments, including the due gate, admissibility constraints, episode-buffer updates, and bounded push/backtrack allowances. Hyperparameters for this procedure are listed in Appendix § 9. A prerequisite is admissible for iff it is concrete and actionable, and , the resulting depth stays within , and has fewer than pushes; each BACKTRACKTO consumes one of the backtracks of its target, and is skipped once that allowance is exhausted.
Implementation Details
Table C.1 lists the single shared control configuration used for full VBL in Algorithm B.1, together with the interaction budgets stated in § 4.1. Control bounds (, , , , ) are held fixed across benchmarks; only the environment step budget follows each benchmark’s horizon. All LLM calls—executor, VERIFY, DIAGNOSE, and SUMMARIZE—use greedy decoding (temperature 0, no nucleus truncation), so a run is deterministic up to provider-side non-determinism, and all methods share this decoding configuration within a backbone. Reported token costs count every such call the same way on all benchmarks; no controller call is excluded from kTok.
| 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 |
| Env. step budget | 50 | 50 | |
| LLM-call budget | |||
| Temperature | 0 | 0 | 0 |
Table C.1. Hyperparameters for full VBL. Control bounds are shared across benchmarks; matches the experimental setting in Section 4.1. Normal / Challenge.
Algorithm B.1 Verify–Backtrack Loop (full procedure)
Require: environment $M$, ReAct policy $\pi_\theta$, bounds $D_{\max}$, $N_{\max}$, $L_{\mathrm{push}}$, $L_{\mathrm{bt}}$, $B$, threshold $K$
1: $S \leftarrow [g_0]$ with $d(g_0) \leftarrow I$; $E \leftarrow \varnothing$; $t \leftarrow 0$; $due \leftarrow \mathrm{true}$
2: initialize history $h$ from $(I,o_0)$
3: while $S \ne \varnothing$ and $t < B$ do
4: $g \leftarrow \operatorname{top}(S)$; $o \leftarrow$ current observation
5: if $due$ then
6: $due \leftarrow \mathrm{false}$
7: $(q,u,p,e) \leftarrow \operatorname{VERIFY}(d(g_0),g,o,h,E)$ ▷ $d(g_0)=I$ only
8: if $q=\mathrm{complete}$ then
9: $E \leftarrow \operatorname{SUMMARIZE}(E,g,h)$; $\operatorname{POP}()$; $due \leftarrow \mathrm{true}$; continue
10: else if $q=\mathrm{misaligned}$ then
11: $E \leftarrow \operatorname{SUMMARIZE}(E,g,h)$; $\operatorname{BACKTRACKTO}$ parent; $due \leftarrow \mathrm{true}$; continue
12: else if $u=\mathrm{blocked}$ and $p$ is admissible then
13: $P(g) \leftarrow P(g) \cup \{p\}$; $\operatorname{PUSH}(p)$; $due \leftarrow \mathrm{true}$; continue
14: end if
15: end if
16: $c \leftarrow (d(g_0),d(g),\operatorname{Retrieve}(E,g))$
17: $a \sim \pi_\theta(\cdot \mid h,c)$; execute $a$; observe $o'$; append $(a,o')$ to $h$; $t \leftarrow t+1$
18: if $g$ is complete under $o'$ then
19: $E \leftarrow \operatorname{SUMMARIZE}(E,g,h)$; $\operatorname{POP}()$; $due \leftarrow \mathrm{true}$; continue
20: end if
21: if $o'$ indicates failure then
22: $n_{\mathrm{err}}(g) \leftarrow n_{\mathrm{err}}(g)+1$; $due \leftarrow \mathrm{true}$ ▷ re-verify before the next action
23: if $n_{\mathrm{err}}(g) \ge K$ then
24: $(z,p,e) \leftarrow \operatorname{DIAGNOSE}(d(g_0),g,o',h,E)$
25: $E \leftarrow \operatorname{UPDATE}(E,g,a,o',z,p,e)$; $n_{\mathrm{err}}(g) \leftarrow 0$
26: if $z=\mathrm{MISSINGPRECOND}$ and $p$ admissible then
27: $P(g) \leftarrow P(g) \cup \{p\}$; $\operatorname{PUSH}(p)$; $due \leftarrow \mathrm{true}$
28: else if $z=\mathrm{TRANSIENT}$ and $n(g) < N_{\max}$ then
29: $n(g) \leftarrow n(g)+1$
30: else
31: mark path failed; $\operatorname{BACKTRACKTO}$ parent; $due \leftarrow \mathrm{true}$
32: end if
33: end if
34: else if $o'$ indicates a material state change then
35: $due \leftarrow \mathrm{true}$
36: end if
37: end while
38: return success and interaction count $t$; discard $E$
Control-Module Output Schemas
VERIFY and DIAGNOSE are schema-constrained side-channel calls. They are never appended into the executor’s think–act dialogue as free-form thoughts. Below we give the paper-level fields used by Algorithm B.1 and the concrete JSON shapes used in experiments. Field names in JSON may differ slightly by environment wording, but the semantics match Section 3.3.
Verify. A call returns
with alignment , readiness , an optional prerequisite , and brief evidence . The experimental JSON is:
{“alignment”: “aligned” | “misaligned” | “complete”,
“readiness”: “ready” | “blocked” | “unknown”,
“prerequisite”: “<one concrete subgoal if blocked, else empty>”,
“evidence”: “<brief>”}
When readiness is blocked and is admissible, the controller issues . When alignment is misaligned, it issues the parent. When alignment is complete, it issues . If readiness is unknown, or the goal is blocked but no admissible exists, the controller executes the active goal and defers recovery to post-failure diagnosis—matching § 3.3.
In the released controller, the same decision is often emitted in a compact form that the router expands into :
{“ready”: 1 or 0,
“missing_precondition”: “<subgoal if ready=0, else empty>”,
“reason”: “<brief>”}
Here ready=1 maps to = ready; ready=0 with a concrete precondition maps to = blocked and ; completion and misalignment are routed by the controller when the observation or stack state supports POP / BACKTRACKTO.
Diagnose. After consecutive failures on the same goal, diagnosis returns
where is one of the four attributions in Table 1 (MISSINGPRECOND, WRONGDECOMP, TRANSIENT, UNRECOVERABLE). The experimental JSON is:
{“type”: “MISSING_PRECOND” | “WRONG_DECOMPOSITION”
| “TRANSIENT” | “UNRECOVERABLE”,
“precondition”: “<subgoal if MISSING_PRECOND, else empty>”,
“reason”: “<brief>”}
The mapping to stack transitions is exactly the attribution table (Table 1): MISSINGPRECOND→PUSH, WRONGDECOMP/UNRECOVERABLE→BACKTRACKTO parent, and TRANSIENT→ local retry within . Vague proposals (e.g., “explore”, “read docs”) are rejected; the call is treated as TRANSIENT so the executor can retry under the existing action format.
Episode Buffer and Retrieve
Full VBL maintains an episode-local buffer that stores short grounded records of completed or failed trajectory segments. As in § 3.4, each record has the form
Concrete fields used in the implementation are listed in Table E.1. Every field is grounded in an environment observation or a recorded stack transition; the buffer does not store cross-task memory.
| 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) |
Table E.1. Episode-buffer record fields. Records are written by SUMMARIZE/UPDATE when a goal is popped, a path is marked failed, or diagnosis assigns a recovery transition.
Write rules. SUMMARIZE appends a record when a goal is completed and popped, or when a path is abandoned. UPDATE appends or refreshes a record when DIAGNOSE fires, storing the failing action, observation, attribution , optional prerequisite , and the prescribed recovery. The buffer is cleared when the episode ends.
Retrieve rules. Before the executor samples , the controller forms
returns at most a few records that match either (i) the active goal description (same or closely related subgoal text) or (ii) the current failure type when the latest segment on carries an attribution. Records for other stack nodes are withheld. If no matching record exists, Retrieve returns the empty string and reduces to . Disabling verification and diagnosis leaves the stack at and makes Retrieve a no-op, recovering the ReAct baseline as stated in § 3.
Prompts and ICL Examples
All methods share the same environment adapter and action interface within each benchmark. They differ only in the control text shown to the model: turn format, optional one-shot ICL, and—for VBL—side-channel schemas from Appendix D. VBL’s executor uses the ReAct format; stack updates change (and retrieved buffer records) without rewriting the ReAct instruction.
Shared turn formats
NoThinking: emit only the environment action (no Thought / Reflection).
ReAct / VBL executor: Thought: . . . then one action.
ReflAct: Reflection: one sentence on current state relative to the task goal, then one action.
AppWorld
Agents interact by writing one fenced Python code block per turn that calls apis.<app_name>.<api_name>(...). The shared protocol prompt covers API discovery (show_app_descriptions / show_api_descriptions / show_api_doc), supervisor credentials, authentication via access_token, and finishing with apis.supervisor.complete_task(...). Method-specific turn formats and the compact one-shot ICL used for baselines are:
NoThinking format + ICL (excerpt).
NoThinking output format: write exactly ONE fenced Python code block
(no Thought / Reflection).
Example task: Pay my roommate $20 on Venmo for last week’s groceries.
```python
passwords = apis.supervisor.show_account_passwords()
print(passwords)
print(apis.api_docs.show_api_descriptions(
app_name=’venmo’))
Observation: {...passwords...} {...venmo API list...}
profile = apis.supervisor.show_profile()
result = apis.venmo.login(
username=profile[“email”],
password=passwords[“venmo”])
print(result)
ReAct format + ICL (excerpt).
Thought: <reasoning>
```python
# one code action
Example (same Venmo payment task): Thought: I need supervisor credentials and Venmo API docs before logging in.
passwords = apis.supervisor.show_account_passwords()
print(passwords)
print(apis.api_docs.show_api_descriptions(
app_name=’venmo’))
Observation: {...} Thought: I have credentials. Next I log into Venmo to obtain an access_token.
profile = apis.supervisor.show_profile()
result = apis.venmo.login(
username=profile[“email”],
password=passwords[“venmo”])
print(result)
ReflAct format + ICL (excerpt).
Reflection: <one sentence on state relative to the task goal>
““python
# one code action
““
Example (same Venmo payment task):
Reflection: I have not yet authenticated to Venmo or identified the roommate, so I am still at the start of completing the $20 payment.
““python
passwords = apis.supervisor.show_account_passwords()
print(passwords)
print(apis.api_docs.show_api_descriptions(
app_name=’venmo’))
““
Observation: {...}
Reflection: I now have credentials but still no Venmo access_token, which I need before I can send the payment.
““python
profile = apis.supervisor.show_profile()
result = apis.venmo.login(...)
print(result)
““
VBL side-channel prompts (AppWorld). The executor prompt is the ReAct protocol above. VERIFY / DIAGNOSE receive the root task text, the goal-stack view (top = current focus), a short recent-execution window, and the schema instructions from Appendix D. Representative instruction text:
Verify (non-root): Before executing the TOP goal, decide whether it can
be attempted now. ready=0 ONLY for a specific missing prerequisite
(e.g. must log in, must fetch an id). Never propose vague explore /
read-docs steps. missing_precondition must be concrete and different
from the TOP goal.
Verify (root): check ONLY for a missing login/auth step; do not
decompose the root into other subgoals.
Diagnose: The TOP goal failed twice in a row. Classify as
MISSING_PRECOND / WRONG_DECOMPOSITION / TRANSIENT / UNRECOVERABLE.
precondition must be a concrete state to obtain; vague API-discovery
proposals are treated as TRANSIENT.
ALFWorld
Instructions follow the ReflAct Appendix K.1 household template. The agent emits Thought:/Reflection: plus Action: from the admissible command set (go to, take, put, open/close, use, clean/heat/ cool). Each method uses one-shot ICL keyed by task type (pick_and_place, pick_clean_then_place, pick_heat_then_place, pick_cool_then_place, pick_two_obj, look_at_obj). NoThinking reuses the ReAct ICL with Thought lines stripped; ReflAct uses Reflection-rewritten trajectories; VBL’s executor shares the ReAct instruction and ICL bank.
ReAct instruction (excerpt).
Interact with a household to solve a task. ... For each turn, think about
the current condition and plan future actions, then output:
“Thought: ... / Action: ...” (one action per turn).
Available actions: go to recep; take obj from recep; put obj in/on recep;
open/close recep; use obj; clean/heat/cool obj with recep.
One-shot ICL excerpt (pick_and_place; ReAct):
Verify–Backtrack Loop
Task: put some spraybottle on toilet.
Thought: To solve the task, I need to find and take a spraybottle, then
put it on toilet. ... starting with cabinet 1.
Action: go to cabinet 1
Observation: On the cabinet 1, you see a cloth 1, a soapbar 1, ...
Action: go to cabinet 2
Observation: The cabinet 2 is closed.
Action: open cabinet 2
Observation: ... spraybottle 2.
Thought: Now I find a spraybottle (2). Next, I need to take it.
Action: take spraybottle 2 from cabinet 2
...
Action: put spraybottle 2 in/on toilet 1
ReflAct turn format. Same admissible actions; each turn is Reflection: (state relative to the goal) then Action: (one command). The corresponding ICL rewrites the trajectory above with state-grounded reflections (e.g., “Currently, I am at cabinet 2 and have found a spraybottle 2. . . ”).
VBL side channels. VERIFY/DIAGNOSE use the same JSON schemas as Appendix § 10, with household-specific rules: prerequisites must be concrete admissible commands (e.g., go to desk 1, open fridge 1); vague “search everywhere” proposals are rejected. When a non-root goal is active, the executor observation is augmented with a short focus line of the form “Current subgoal focus: ”.
ScienceWorld
Instructions follow the ReflAct Appendix K.§ 2 laboratory template (rooms, teleport, focus, mix, etc.). One-shot ICL is the green-paint mixing trajectory from that appendix; ReflAct uses the Reflection-rewritten variant; NoThinking strips Thought/Reflection lines; VBL shares the ReAct instruction and ICL.
ReAct instruction (excerpt).
You are a helpful assistant to do a scientific experiment. ...
Output format: “Thought: ... / Action: ...” (one action per turn).
Available actions include: open/close, activate/deactivate, connect,
use, look around, examine, pour, mix, teleport to LOC, focus on OBJ, wait.
One-shot ICL excerpt (create green paint; ReAct):
Task: use chemistry to create green paint. When done, focus on the green paint.
Thought: Materials are likely in an art studio.
Action: look around
Observation: This room is called the bedroom. ...
Thought: The bedroom doesn’t have the materials. Go to the art studio.
Action: teleport to art studio
...
Action: pour cup containing blue paint ... in cup containing nothing
Action: pour cup containing yellow paint ... in cup containing blue paint
Action: mix cup containing blue paint and yellow paint
Observation: Blue and yellow paint mix to produce green paint.
Action: focus on green paint
ReflAct / NoThinking. ReflAct replaces Thought with a state-relative Reflection (location, inventory, focused object). NoThinking emits only Action: . . . . VBL side-channel prompts reuse the Appendix § 10 JSON schemas with ScienceWorld-specific admissible-action constraints.
Model and Inference Settings
Backbones. Every method is evaluated under three backbones, held fixed within each comparison:
Qwen3.5-9B — open-weight; served locally via an OpenAI-compatible vLLM endpoint (
--served-model-name Qwen3.5-9B).
Verify–Backtrack Loop
GPT-4o — closed-source Chat Completions API.
DeepSeek-V3.2 — open-weight large model via API (or an OpenAI-compatible endpoint with served name
deepseek-v3.2).
Decoding and budgets. All calls use temperature 0 (greedy). Nucleus/top- sampling is disabled. Within a backbone, NoThinking, ReAct, ReflAct, and VBL share the same client configuration. Per-episode environment steps use the values in Table C.1; the LLM-call budget is and counts executor and controller calls uniformly. Approximate completion-token caps used by the controller are: executor 512–1536 (environment-dependent), VERIFY 200, DIAGNOSE 300, and short SUMMARIZE/UPDATE writes. Trajectories are truncated when the serialized history exceeds a fixed character budget (AppWorld default 20,000 characters), matching the shared ReAct harness.
Token accounting. Reported kTok sums prompt and completion tokens over every LLM call in the episode, including VBL’s VERIFY, DIAGNOSE, and SUMMARIZE. No controller call is omitted from the cost tables in Table 3.
Additional Case Study: Diagnostic Backtracking
Section 4.7 illustrates verification-time PUSH. Here we complement that example with diagnostic recovery on another AppWorld normal-split episode with Qwen3.5-9B, where free-form reflection commits to a goal-inverting operator while VBL repairs the plan via BACKTRACKTO.
A task asks the agent to request $13 publicly from Stacy on Venmo with note “For yesterday’s meal.”4 The critical distinction is operator choice: create_payment_request vs. create_transaction. ReflAct correctly locates Stacy after some auth noise, but then reflects itself into sending money (create_transaction)—a coherent yet goal-inverting action that mutates venmo.Transaction instead of creating a payment request, so nearly all unit tests fail. ReAct issues the right request API but still fails the answer check, illustrating that linear recovery can get close without reliable goal–operator alignment.
VBL keeps “request payment from Stacy” as the active stack goal. Verification supplies the episode’s single PUSH, the Venmo login prerequisite; after consecutive search-parameter errors on the resulting lookup subgoal, DIAGNOSE attributes the failure to a wrong decomposition and prescribes the one transition that follows from that attribution—a BACKTRACKTO the parent, which in this episode restores the request goal—instead of only revising the next free-form thought (Figure H.1). After returning to that ancestor, the agent reads the payment-request schema and executes create_payment_request with the required amount, note, and privacy. We do not claim that DIAGNOSE itself detected the operator inversion seen in ReflAct; the attributed failure was the lookup-parameter errors. The contrast is still informative: ReflAct’s free-form reflection can endorse a fluent wrong operator, whereas VBL routes the mid-horizon failure to a typed stack repair and then resumes from the outstanding request goal.

Figure H.1. Additional case (task 024c982_1). ReflAct inverts the goal with create_transaction; VBL repairs the failed lookup on the stack and keeps the request operator.
Per-Type Gain Analysis
Beyond aggregate success and control-operation usage, we examine where VBL’s gains concentrate at the task-type level.
Gains concentrate on precondition-heavy task types. Table I.1 breaks ALFWorld down by task type. AppWorld exposes no comparable type label, and ScienceWorld’s 24 types average fewer than nine test episodes each—too few for a stable per-type estimate—so we report ALFWorld quantitatively and summarize the ScienceWorld trend qualitatively.
VBL’s gains fall mainly on the compositional types that must establish an enabling state before the terminal placement: pick_heat_then_place (+13.0 points for Qwen3.5-9B, +8.7 for DeepSeek-V3.2) and pick_clean_then_place (+6.5 / +12.9), with the single largest gain on pick_two_obj_and_place for DeepSeek-V3.2 (+35.3). The already-easy pick_and_place_simple type is saturated for both methods. Two qualifications are worth stating explicitly. First, the pattern is not uniform across backbones: for Qwen3.5-9B pick_two_obj_and_place regresses by 5.8 points and pick_cool_then_place is flat, even though both require an enabling step, so the smaller backbone does not convert the extra control into gains evenly. Second, Qwen3.5-9B’s largest single gain is on look_at_obj_in_light (), a type whose difficulty lies in locating a light source rather than in a compositional state change; this is still consistent with VBL supplying a missing prerequisite, but the prerequisite is one of object discovery. On ScienceWorld the largest gains likewise fall on procedure-heavy types such as boil, melt, chemistry-mix, and find-living-thing, whereas open-ended types with no reliable procedure (e.g., grow-fruit) remain hard for all methods. Overall the gains are concentrated rather than uniform, which is consistent with VBL helping by supplying missing preconditions, although the ALFWorld type labels alone do not isolate that mechanism.
| ALFWorld task type | Qwen3.5-9B ReAct | Qwen3.5-9B VBL | DeepSeek-V3.2 ReAct | DeepSeek-V3.2 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 |
| pick_two_obj_and_place | 88.2 | 82.4 | 58.8 | 94.1 |
Table I.1. ALFWorld success rate (%) by task type. Gains often fall on compositional types that require establishing an enabling state (e.g., clean or heat) before the terminal action, though the pattern is not uniform across backbones.
References
- [1]Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023.arxiv.org/abs/2210.03629
- [2]Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jack Liang, Peter Florence, Andy Zeng, Jonathan Thompson, Igor Mordatch, Yevgen Chebotar, et al. Inner monologue: Embodied reasoning through planning with language models. In Conference on Robot Learning (CoRL), 2022.arxiv.org/abs/2207.05608
- [3]Haotian Sun, Yuchen Zhuang, Lingkai Kong, Bo Dai, and Chao Zhang. Adaplanner: Adaptive planning from feedback with language models, 2023.arxiv.org/abs/2305.16653
- [4]Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model, 2023. URL https://arxiv.org/abs/2305.14992.
- [5]Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models, 2024. URL https://arxiv.org/abs/2310.04406.
- [6]Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Niranjan Bhaskar, Dan Koll ar, et al. Self-refine: Iterative refinement with self-feedback. arXiv preprint, 2023.arxiv.org/abs/2303.17651
- [7]Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2023.arxiv.org/abs/2303.11366
- [8]Jeonghye Kim, Sojeong Rhee, Minbeom Kim, Dohyung Kim, Sangmook Lee, Youngchul Sung, and Kyomin Jung. Reflect: World-grounded decision making in llm agents via goal-state reflection. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 33421–33453, 2025.arxiv.org/abs/2505.15182
- [9]Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems (NeurIPS), 2022.arxiv.org/abs/2201.11903
- [10]Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint, 2023.arxiv.org/abs/2205.10625
- [11]Lei Wang, Wei Xu, Yifan Lan, Zhiqiang Hu, Yanyan Lan, and Weijun Tan. Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models. arXiv preprint, 2023.arxiv.org/abs/2305.04091
- [12]Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint, 2023.arxiv.org/abs/2305.10601
- [13]Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Luk as Gianinazzi, Jan Gajda, Andreas Kopf, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. arXiv preprint, 2024.DOI
- [14]Mengkang Hu, Tianxing Chen, Qiguang Chen, Yao Mu, Wenqi Shao, and Ping Luo. Hiagent: Hierarchical working memory management for solving long-horizon agent tasks with large language model, 2024. URL https://arxiv.org/abs/2408.09559.
- [15]Harsh Trivedi, Tushar Khot, Mareike Hartmann, Ruskin Manku, Vinty Dong, Edward Li, Shashank Gupta, Ashish Sabharwal, and Niranjan Balasubramanian. Appworld: A controllable world of apps and people for benchmarking interactive coding agents, 2024. URL https://arxiv.org/abs/2407.18901.
- [16]Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. Alfworld: Aligning text and embodied environments for interactive learning, 2021. URL https://arxiv.org/abs/2010.03768.
- [17]Ruoyao Wang, Peter Jansen, Marc-Alexandre Côté, and Prithviraj Ammanabrolu. Scienceworld: Is your agent smarter than a 5th grader?, 2022. URL https://arxiv.org/abs/2203.07540.