Technical Summary: When to Re-Commit: Temporal Abstraction Discovery for Long-Horizon Vision-Language Reasoning

Problem Definition

Long-horizon reasoning tasks (e.g., solving complex puzzles, navigating cluttered environments) require agents to repeatedly decide on actions, execute them, observe outcomes, and replan. A critical design choice in these systems is the commitment depth ($h$): the number of primitive actions an agent executes open-loop (without re-observing the environment) between replanning steps.

Current systems typically fix $h$ as a hand-tuned scalar hyperparameter. This creates a fundamental trade-off:

• Small $h$: Frequent replanning reduces compounding execution errors but incurs high computational costs (more forward passes) and decision latency.
• Large $h$: Reduces replanning overhead but increases the risk of compounding errors as the imagined state diverges from the realized state.

The paper argues that a fixed $h$ is suboptimal because the locally optimal commitment depth varies depending on the current state, task dynamics, and available decision budget. The core problem is formulated as a budget-constrained optimization: maximizing task success (solving the puzzle) subject to a cap ($K$) on the number of decision points (replans) per episode, where the policy must jointly select the commitment depth $h_k$ and the action sequence $a_k$ at every decision step $k$.

Methodology

The authors propose a unified, model-native Vision-Language Model (VLM) policy that learns to adaptively determine commitment depth.

1. Architecture

The policy is built upon a shared backbone (Qwen2.5-VL-7B) with two distinct heads:

• Depth Head ($\pi_h$): A categorical head that predicts the commitment depth $h_k \in \{1, 2, 4, 8\}$ based on the current state representation.
• Action Head ($\pi_a$): An autoregressive decoder that generates a sequence of primitive actions of length $h_k$, conditioned on the state and the predicted depth.
• Open-Loop Execution: Once $h_k$ and $a_k$ are predicted, the agent executes the sequence without re-querying the VLM or re-encoding intermediate states.

2. Training Pipeline

The model is trained via a two-stage process:

• Stage 1: Supervised Fine-Tuning (SFT): The action head is trained on "counterfactual macro-action" data. For every state on an expert trajectory, the model is trained to predict action prefixes of all admissible lengths ($h \in \{1, 2, 4, 8\}$). Crucially, the depth head is not trained during this stage; it remains untrained (flat prior) to avoid biasing the policy toward any specific depth before reinforcement learning.
• Stage 2: Reinforcement Learning (RL): Both heads are jointly fine-tuned using GRPO (Group Relative Policy Optimization). The reward function combines a binary success signal (solved/not solved) with a dense reward based on the reduction in optimal solution distance (derived from an exact solver, used only for training). The objective encourages the policy to select the depth that maximizes success while minimizing wasted actions.

3. Theoretical Foundation

The paper provides a theoretical model showing that if the locally optimal commitment depth $h^*(s)$ varies across states (which is empirically verified via an oracle distribution), a state-conditioned adaptive policy strictly dominates any fixed-depth policy in terms of expected log-success. This holds provided the commitment-level error grows sublinearly with depth.

Key Contributions

1. Problem Formulation: The authors formalize "when to re-commit" as a budget-constrained optimization problem and prove theoretically that fixed-depth strategies are suboptimal whenever the optimal depth varies across states.
2. Unified Adaptive Policy: They introduce a single VLM architecture with a learnable depth head and action head, trained end-to-end without auxiliary planners or separate depth predictors.
3. Infrastructure: They release a vision-language puzzle environment with a solver-grounded data generation pipeline for Sliding Puzzle and Sokoban, enabling controlled measurement of long-horizon reasoning.

Experimental Results

The method was evaluated on Sliding Puzzle and Sokoban, two tasks with known dynamics but varying error characteristics (reversible vs. irreversible).

• Pareto Dominance: The adaptive policy strictly Pareto-dominates every non-degenerate fixed-depth baseline ($h \in \{1, 2, 4, 8\}$). It achieves higher solve rates with fewer primitive actions per episode.
  • Sliding Puzzle: 56.3% solve rate (vs. 43.8% best fixed) with ~25% fewer actions.
  • Sokoban: 35.9% solve rate (vs. 32.8% best fixed) with ~25% fewer actions.
• Comparison to Frontier Models: Despite using a 7B parameter backbone, the fine-tuned adaptive policy outperforms frontier closed-source models (GPT-5.5, Claude Sonnet, Gemini 3.1 Pro) and significantly outperforms all tested open-weight VLMs (8B–78B), which scored 0% in zero-shot settings.
• Mechanism Analysis:
  • State-Conditioning: The policy learns to use shorter commitments ($h \approx 1-4$) in "noisy" or far-from-goal states where progress is uncertain, and longer commitments ($h \approx 6-8$) in "clean" states near the goal.
  • Efficiency: The improvement comes from solving the same instances via straighter trajectories (fewer wasted or backward actions), not by solving easier instances.
  • Robustness: The performance gains persist across different random seeds and training budgets, and the depth distribution does not collapse to a single fixed value.

Significance and Claims

The paper claims that temporal abstraction should be treated as a dynamic, state-conditioned control variable rather than a fixed architectural hyperparameter.

• Suboptimality of Fixed Depth: The work demonstrates that hand-tuning a single commitment depth is insufficient for long-horizon tasks where state uncertainty and error propagation vary significantly.
• Learnable Abstraction: By treating the "when to re-plan" decision as part of the policy itself, the model learns to balance the cost of replanning against the risk of compounding errors, achieving superior efficiency and success rates.
• Generalizability: The authors suggest this approach is applicable to broader long-horizon reasoning domains, such as web agents (deciding how many steps to take before re-reading a page) or code agents (deciding how many edits to make before re-evaluating the buffer), though their empirical validation is currently limited to puzzle domains.

The paper concludes that the ability to learn how long to commit is as critical as learning what to commit to, offering a path toward more efficient and robust autonomous agents in complex environments.