PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Simple Test-Time Environments for LLM Web Agents

Junxuan Li, Zijun Liu, Ziyi Huang, Peng Li, Yuzhou Liu, Ming Yan, Yang Liu

arXiv:2608.29305v1cs.CLcs.AIcs.LG

TL;DR

LLM web agents often fail when familiar interface components appear together in complex real-world environments, while existing test-time learning remains limited by compositional gaps and noisy or sparse signals. TTED decomposes observations into simpler sub-environments, gathers self-assessed experience, and adapts agents through ICL or RL during inference. Across synthetic and realistic benchmarks, TTED mitigates compositional failures and achieves 21.0% success on WebArena with full training budget, surpassing the reported baselines.

  • Problem

    LLM agents struggle to compose familiar web components in realistic environments, and existing test-time learning methods remain limited by sparse, noisy, or insufficiently informative supervision.

  • Method

    TTED decomposes complex observations into aligned sub-environments and uses self-assessed experience within them to adapt behavior through ICL or RL at test time.

  • Results

    TTED mitigates compositional generalization failures on synthetic and realistic benchmarks, reaching a state-of-the-art 21.0% success rate on WebArena with full budget.

  • Takeaways & Limitations

    Experience learned in simpler decomposed environments can be composed to improve performance on full web tasks, including realistic automation settings.

  • Takeaways & Limitations

    TTED depends on the backbone model producing meaningful decompositions, while self-assessment can inherit model bias and noise that affect training stability and gains.

Abstract

from arXiv · show

Large language model (LLM) agents have demonstrated remarkable proficiency in manually constructed environments, yet their performance frequently collapses when transitioned to complex real-world settings. Existing research largely attribute this degradation to the compositional generalization gaps in LLMs on combinations of multiple simple, well-structured environments. In this work, we propose that LLM web agents can learn simple environment observations at test time. Specifically, we introduce trial steps for agents to decompose a complex environment observation into sub-modules, and implement a label-free learning method, Test-Time Environment Decomposition (TTED), to adapt agent behaviors with experience during inference. Our empirical evaluations demonstrate the framework's efficacy across both synthetic and realistic benchmarks, showing (1) experience gains acquired within simpler sub-environments can be effectively composed to improve performance in the full one, and (2) test-time training on sub-environments can significantly enhance the compositional generalization of agents in real-world web automation tasks. We also provide key insights in the design of the label-free learning algorithm. As more complex environments are accessed by LLM agents, we believe learning environment decomposition skills at test time will be critical for robust real-world deployment.

Introduction

LLM agents perform well in controlled environments but struggle with compositionally complex real-world web interfaces. TTED addresses this gap by decomposing observations into simpler sub-environments, adapting behavior at test time, and improving performance across synthetic and realistic benchmarks.

  • LLM agents show strong sequential decision-making in manually curated environments but a substantial performance gap remains in realistic settings.
  • Realistic web observations combine functional structures such as search panels, forms, content containers, and modals, challenging compositional generalization.
  • Existing test-time methods improve inference-time performance without external rewards, but the compositional generalization gap remains under complex observations.
  • TTED partitions complex observations into specialized submodules and adapts behavior using self-assessed interaction experience within those local contexts.
  • TTED with ICL alleviates degradation on CompWoB+, while TTED with RL improves WebArena generalization and outperforms RL trained with ground-truth rewards.
  • The framework contributes TTED, the expanded CompWoB+ benchmark, realistic WebArena results, and analysis of factors influencing test-time adaptation.

Related Work

Prior work studies environment generalization and test-time learning, but web agents remain brittle when familiar modules must be composed in realistic interfaces. TTED differs by decomposing both the representation used for action generation and the local context used for self-assessment.

  • Environment generalization concerns solving novel combinations of familiar components, yet web agents often generalize brittly across modules, pages, and websites.
  • Test-time learning adapts agents during inference from test-instance signals rather than ground-truth labels, using methods such as prompting, sampling, planning, reflection, ICL, and test-time training.
  • Existing test-time training methods face limitations from synthetic task assumptions, matching-based rewards, and sparse or noisy learning signals in complex web environments.
  • TTED decomposes complex environments into aligned sub-goals and sub-observations, then adapts through query-level ICL or task-level RL.
  • Unlike planning, reflection, history shrinking, and context pruning, TTED makes localized sub-environments the test-time learning units for both action generation and self-assessment.

Preliminaries

TTED treats long-horizon web interaction as inference-time adaptation over localized decision contexts. It gathers experience in decomposed sub-environments, estimates local feedback, and composes the resulting improvements during full-task execution.

  • A test-time environment: A long-horizon web task is modeled as a Markov decision process with states, actions, transitions, and rewards.
  • A test-time environment: Direct optimization in complex web environments is difficult because irrelevant information and multi-step execution make rewards sparse, delayed, and hard to estimate accurately.
  • Environment decomposition: TTED decomposes the original environment into localized contexts containing aligned sub-goals and task-relevant sub-observations.
  • Environment decomposition: Localized environments preserve the original action space and transition dynamics while reducing irrelevant information and decision ambiguity, enabling more reliable local reward estimation.
  • Environment decomposition: TTED composes learning gains from localized environments into policy improvements for solving the full task.
  • Test-time learning: ICL collects successful state-action pairs during trials as demonstrations, while RL updates parameters from assessed rewards on multi-turn trajectories before full-environment execution.
  • Evaluation: CompWoB+ evaluates Qwen3-8B and GPT-4o-mini on 600 synthesized tasks spanning composition sizes from 3 to 8 components.

TTED: Test-Time Environment Decomposition

TTED decomposes complex web observations into localized sub-environments, gathers self-assessed trial experience, and adapts the agent before final execution. Its designs use environment-preserving decomposition, selective experience, and distinct ICL/RL mechanisms to support reliable test-time learning.

  • Overall framework: TTED gathers self-assessed experience in decomposed sub-environments, then adapts the agent with query-level ICL or task-level RL before final execution.The same process is used to collect trial experience and improve behavior for the original task.
  • Environment decomposition: Each trial predicts a localized sub-goal and task-relevant sub-observation, forming a textual or simulated sub-environment while preserving the original action space and transition dynamics.Interactive websites use textual views; static webpages use isolated simulators.
  • Trial-step design: The action policy generates an action for the sub-goal, after which self-assessment scores decomposition quality and action correctness.Sub-goal and sub-observation receive scores in [0, 5], while the action receives a binary reward.
  • Trial-step design: A trial passes only when decomposition scores exceed a threshold and the action reward equals 1; otherwise it is rejected and retried up to a fixed limit.Passed trials can be summarized into natural-language history and used for subsequent learning.
  • Learning from trials: ICL retains only passed same-task trials, whereas RL retains passed and rejected trials so sparse correct trajectories and useful decomposition behavior can both contribute.The RL design decouples rewards for decomposition and action quality.
  • Test-time RL: The RL procedure uses off-policy importance sampling and minibatch advantage normalization; empirically, normalization stabilizes advantage estimation and improves scalability across diverse web layouts.Decomposition and action generation are counted within the same interaction step.

Experiments and Analysis

Experiments evaluate TTED across synthetic and realistic web benchmarks, testing decomposition, adaptation, reward labeling, scaling, and failure modes. TTED improves robustness as interface complexity grows, outperforms comparison methods on WebArena and WorkArena, and depends on both decomposition components and stable self-assessment.

  • Evaluation Protocol: TTED is evaluated with query-level ICL on CompWoB+ and task-level RL on WebArena and WorkArena, using success, efficiency, and human-evaluated adaptation measures.CompWoB+ controls web-component compositions, while WebArena and WorkArena provide heterogeneous real-world interfaces.
  • Synthetic Compositional Generalization: As CompWoB+ complexity increases from 3 to 8 concurrent components, TTED with ICL arrests the base models’ performance collapse.Qwen3-8B maintains 80%+ success for fewer than 6 components and reaches 61% at 8 components; GPT-4o-mini retains 88%.
  • Realistic Web Environments: On WebArena, TTED (RL) reaches a 21.0% success rate with the full budget and outperforms monolithic test-time methods and ground-truth-trained baselines.The base Qwen3-8B scores 12.1%, while ground-truth RL reaches 14.8%; TTED also achieves superior performance with one-quarter of the training budget.
  • Out-of-Distribution Generalization: Without further training on WorkArena, TTED (RL) achieves a 22.7% success rate and maintains superior cross-environment performance.This evaluates transfer after adaptation on WebArena.
  • Importance of Decomposition Components: Removing sub-goal decomposition lowers success from 21.0% to 12.4%, removing sub-observation partitioning lowers it to 15.0%, and removing both yields 12.5%.The ablation identifies joint structural and goal decomposition as the primary contributors to TTED’s efficacy.
  • Self-Assessment and RL Design: TTED’s reward labeling reaches 0.85 Cohen’s κ with human judgments, while standard TTRL and TTT reach 0.68 and 0.71 overall agreement.Advantage normalization stabilizes test-time RL: TTED scales to 21.0%, whereas standard TTT plateaus at 13.5% and REINFORCE or GRPO peak at 17.8%.
  • Qualitative Observations and Failure Cases: Remaining failures usually arise from action-space misalignment or overthinking rather than incorrect decomposition.Examples include clicking to extract already identified text instead of terminating with the answer.

Conclusion

TTED improves both in-domain adaptation and cross-environment transfer across synthetic and realistic web benchmarks, while analyses identify self-assessment quality and algorithm design as key factors.

  • TTED improves performance for both in-domain adaptation and cross-environment transfer across synthetic and realistic web benchmarks.

Ethical Statement

The paper frames environment decomposition as a distinct route to compositional generalization, with potential benefits for more reliable web automation but important deployment safeguards. Unlike planning, TTED structures complex environments into simpler sub-environments and uses localized learning signals, while real-world boundaries remain implicit and ambiguous.

  • Ethical Statement: TTED could support more reliable autonomous digital assistants and long-horizon behaviors that scale at inference time.
  • Environment Decomposition vs. Planning: Environment decomposition partitions goals, observations, and rewards into sub-environments, unlike planning, which decomposes only the global goal into subgoals.
  • Environment Decomposition vs. Planning: Simplified sub-environments provide reduced complexity, clearer objectives, and more accurate self-assessment reward signals.
  • Synthetic Environment vs. Real-world Environment: Synthetic environments have explicit boundaries, whereas real-world environments require agents to infer implicit, overlapping, or ambiguous decompositions.
  • Ethical Statement: Unsafe operations or actions with critical side effects during sub-environment exploration should be suspended pending user confirmation.
  • Environment Decomposition vs. Planning: TTED uses localized learning signals aligned with each decomposed environment rather than full-trajectory outcome rewards.

A.2 Limitations

TTED’s effectiveness is constrained by the reliability of model-generated environment decompositions and self-assessment, especially in realistic settings where boundaries are difficult to infer.

  • Poor decomposition quality can propagate errors or ambiguities into downstream decisions and limit compositional generalization.
  • The decomposition challenge is more pronounced in realistic settings because environment boundaries are implicit and difficult to infer.
  • Self-assessment can introduce backbone-model bias and noise, with inaccurate judgments potentially affecting training stability and performance gains.

B.1 CompWob+ Results with Larger LLMs

With larger models, base performance improves across compositional tasks but still drops sharply at high composition counts. TTED with ICL remains stable as complexity increases, including at eight compositions.

  • 25.3% decrease: the base model’s performance drops from tasks with 7 compositions to tasks with 8 compositions.
  • 78% accuracy: TTED combined with ICL remains stable on tasks with 8 compositions as task complexity increases.

B.2 Webarena Results with Additional LLMs

On the selected WebArena subset, TTED improves Qwen3 performance over bare models and ground-truth-reward RL, with gains also reported for Qwen3-14B. Results are evaluated with repeated runs and confidence intervals.

  • Additional LLMs: 16.6% and 4.2% relative gains over bare Qwen3-14B occur on undecomposed and decomposed environments, respectively, while TTED still outperforms ground-truth RL.The smaller decomposed-environment margin may reflect higher absolute performance and bottlenecks beyond environment complexity.
  • Additional LLMs: GPT-4o and GPT-5.5 achieve WebArena success rates of 23.5% and 67.3%, respectively, exceeding TTED’s reported performance.The comparison is presented as contextual because model scale differs.
  • Additional LLMs: Qwen3-8B TTED improves WebArena from 12.1% to 21.0% and WorkArena from 18.2% to 22.7% using the same backbone.These correspond to 73.6% and 24.7% relative improvements, respectively.
  • Additional LLMs: Across 561 WebArena tasks, Qwen3-8B TTED achieves 21.0% SR with a 95% Wilson CI of [17.9, 24.6].The base model, RL w/ GT, and TTT have confidence intervals of [9.7, 15.1], [12.1, 18.0], and [10.0, 15.5], respectively.

B.4 Efficiency Analysis

TTED increases interaction steps through exploratory trials while reducing prompt-token consumption by restricting action generation to partitioned sub-observations. This localized processing addresses the large textual size of real-world websites.

  • Efficiency Analysis: 8.29 versus 4.72 average interaction steps per task reflects the additional exploratory trials used by TTED.The comparison is reported in the efficiency analysis of TTED-trained WebArena models.
  • Efficiency Analysis: Partitioned sub-observations significantly reduce average prompt-token consumption for the action-generation policy.TTED extends interaction scales while lowering per-action computational overhead.
  • Efficiency Analysis: Localized observations reduce overhead in settings where website textual representations can reach six-figure token counts.This motivates context efficiency for real-world web automation.

C.1 Webarena Case Studies

WebArena case studies show TTED helping agents isolate relevant interface components and select better strategies, while also exposing failures caused by action-space misalignment and overthinking.

  • Case 1: TTED succeeds where the undecomposed agent misinterprets key elements, because isolating relevant components enables more accurate reasoning and reduces hallucinations.The case contrasts successful decomposition with failure without TTED.
  • Case 1: Decomposition helps the agent identify the GitLab commit-history link that the undecomposed agent misinterprets or excludes.The successful sub-goal is to click the ‘2,320 Commits’ link and inspect commits by author and date.
  • Case 2: After training, the agent uses search to locate the target efficiently instead of scanning all entries and hallucinating under complex contexts.The same task fails before training because the agent adopts a brute-force strategy.
  • Case 3: Correct decomposition still fails when the agent maps a sub-goal to an unavailable extract action and selects an incorrect action.The agent had already identified the correct answer, but overthinking caused action-space misalignment.
  • Cross-case findings: The action-generation and self-assessment loop improves action reliability and robustness in compositional tasks.The case analysis connects environment simplification with more reliable interaction.

D.1 Implementation Details of Data Collection

CompWoB+ is built by composing independently implemented MiniWoB tasks into randomized composite web environments, while WebArena experiments use a selected subset because of network-related collection and evaluation constraints.

  • CompWoB+: CompWoB+ combines multiple base MiniWoB tasks into unified pages, with each base task implemented as an independent UI module.An automated generator selects tasks and composition sizes according to a configuration file.
  • CompWoB+: 10 base tasks are combined into composite tasks with composition sizes from 3 to 8, using 10 composite tasks and 10 randomized instances per size.The resulting construction expands the number of high-composition evaluation cases.
  • WebArena: WebArena experiments use 561 of 812 tasks because some tasks are difficult to collect and evaluate under network constraints.All Reddit tasks are removed because the site operates unreliably, with completion below 5%.
  • Evaluation: WebArena text answers are evaluated with GPT-5-mini fuzzy matching, used internally for success determination rather than as TTED’s reward model.The replacement is intended to improve matching quality.

D.2 Implementation Details of Model Training

The experiments train and evaluate TTED through decomposed web-environment rollouts, self-assessment, and label-free optimization, with separate configurations for WebArena and CompWob+. Training uses controlled rollout budgets, reward processing, and adaptation safeguards.

  • Data collection and budget: Training samples trajectories from 32 sub-environments per batch and runs for at most 100 steps, producing 3200 sub-environments for training.The computational-cost comparison evaluates all methods under this uniform 3200-sub-environment budget.
  • TTED optimization: TTED uses off-policy REINFORCE with rollout importance sampling, advantage normalization from REINFORCE++, and the GSPO loss for policy optimization.The method therefore combines off-policy correction and normalized policy-gradient optimization during test-time training.
  • Reward processing: Rewards are independently assessed per trajectory by a backbone-model grader and linearly mapped from raw goal, observation, and action scores to returns in [-1, 1].The raw scores are r_goal, r_obs ∈ [0, 5] and r_action ∈ {0, 1}.
  • Optimization settings: The implementation uses a 10^-6 peak RL learning rate, 10^-5 SFT learning rate, gradient clipping at 5.0, and RL importance-sampling ratio clipping.The settings were selected by grid search; no KL-divergence regularization is used.
  • Benchmark-specific configurations: CompWob+ uses TTED with in-context learning because its static single-turn webpages can be decomposed at once, while WebArena uses TTED with reinforcement learning.CompWob+ sub-environment trajectories guide final action generation through ICL; WebArena uses Qwen3-8B rollouts and training.
  • WebArena rollout pipeline: TTED rollouts decompose each WebArena observation into a sub-goal and sub-observation, generate an action, and self-assess both decomposition quality and action correctness before execution.Collected sub-environments and self-assessment signals become training data for subsequent reinforcement-learning optimization.
Loading 2608.29305v1…