PaperlayerView exact revision on arXiv

Source-linked AI summary

SCAFFOLD: Self-Improving Web Agents via Recursive Parametric Skill Abstraction

Bowei He, Xiaokun Zhang, Meng Ding, Xue Liu

arXiv:2609.05511v1cs.AIcs.CL

TL;DR

Web agents often discard reusable procedures, while existing skill libraries are shallow, redundant, and prompt-only. SCAFFOLD induces validated parametric skills, composes them recursively, compacts the library with MDL, and distills their use into model weights. Across three benchmarks, it outperforms skill-augmented baselines and improves through five iterations without library collapse.

  • Problem

    Existing web agents learn tasks in isolation, while current skill libraries remain flat or two-tier, lack principled redundancy compression, and do not internalize skills into model weights.

  • Method

    SCAFFOLD combines multi-instance parametric skill induction, recursive skill composition, MDL-driven compaction with behavioral checks, and trajectory distillation into a self-improvement loop.

  • Results

    11.1–17.2 absolute points improve success over the strongest skill-induction and skill-RL baselines across WebArena, VisualWebArena, and held-out Online-Mind2Web, with gains continuing through five iterations.

  • Takeaways & Limitations

    The framework keeps library size bounded while enabling recursive abstractions and progressively transferring skill knowledge from in-context trajectories into policy weights.

  • Takeaways & Limitations

    SCAFFOLD depends on GPT-4o for induction and compaction proposals, accounting for approximately 70% of experimental dollar cost.

Abstract

from arXiv · show

Web agents need to navigate visually rich, long-horizon interfaces that change across sites, yet most previous agents still learn each task in isolation and discard the procedural knowledge they accumulate. Recent skill-augmented frameworks take an important first step, but they treat the skill library as a flat or two-tier prompt-side cache and offer no principled mechanism for compressing redundancy or composing skills recursively. We introduce \textsc{Scaffold}, a self-improving framework for visual web agents that (i) induces parametric, executable skills from successful trajectories under a multi-instance abstraction constraint, (ii) maintains a recursively composed hierarchy in which higher-level skills invoke lower-level ones, (iii) compacts the library via a minimum-description-length (MDL) criterion and behavioral equivalence checking, and (iv) periodically distills skill-augmented trajectories back into model weights to internalize the abstractions. Across WebArena, VisualWebArena, and a held-out split of Online-Mind2Web, \textsc{Scaffold} improves success rate by $11.1$--$17.2$ absolute points over the strongest skill-augmented baseline and shows monotonic gains across five self-improvement iterations without library collapse. We release the code and documents in the Github \href{https://github.com/BokwaiHo/SCAFFOLD}{repository}.

1 Introduction

SCAFFOLD addresses the limits of task-isolated web agents and flat skill libraries with multi-instance induction, recursive composition, MDL compaction, and weight distillation. It improves success across three benchmarks while continuing to improve over five iterations.

  • Current web agents often discard procedural knowledge between tasks, even when later tasks share sub-procedures.
  • Existing skill-augmented agents use flat or two-tier libraries, accumulate redundant skills, and leave learned knowledge only in prompts.
  • SCAFFOLD requires multiple similar trajectories to support each parametric skill abstraction, reducing spurious skills caused by incidental trajectory details.
  • Recursive composition lets newly induced skills invoke skills from earlier iterations, producing hierarchies with monotonically increasing depth.
  • MDL-driven compaction merges equivalent skills, refactors recurring patterns, and prunes unused skills, while distillation transfers skill-augmented behavior into model weights.
  • 13.6–17.7 absolute success-rate points separate SCAFFOLD from SKILLWEAVER across WebArena, VisualWebArena, and held-out Online-Mind2Web.

2 Related Work

Related work spans web and GUI agents, self-improvement, and skill libraries. SCAFFOLD differs through recursive visual-web skill composition, MDL compaction, and explicit transfer evaluation.

  • Web and GUI agents: Web agents either prompt proprietary models or fine-tune vision-language models, with static datasets limiting procedural diversity.
  • Self-improvement through experience: Self-improvement methods train on filtered generations or use in-context correction, while agent-specific work has improved WebArena performance.
  • Concurrent skill frameworks: SKILLRL jointly trains an agent with a two-tier hierarchical skill library using GRPO, whereas SCAFFOLD uses truly recursive hierarchies for visual web agents.
  • Concurrent skill frameworks: POLYSKILL separates abstract goals from site implementations through abstract interfaces, while classical hierarchical reinforcement learning and program-synthesis library learning motivate SCAFFOLD’s design.

3 Methodology

SCAFFOLD repeatedly collects successful trajectories, induces and composes validated skills, compacts the library, and distills skill-augmented behavior into the policy. Its design controls abstraction quality, hierarchy growth, redundancy, and recursive improvement.

  • Problem Setup and Notation: Each task combines an instruction, initial environment state, and binary verifier; trajectories contain screenshot, DOM, URL observations and primitive or skill actions.
  • Overall Pipeline: Each iteration executes rollout, multi-instance induction, recursive composition, MDL-driven compaction, and distillation in sequence.
  • Multi-Instance Skill Induction: Multi-instance induction requires at least nmin trajectories with the same parameter structure and validates each induced skill on a held-out instance.
  • Recursive Composition and Depth Tracking: Recursive composition allows a new skill to invoke any prior skill, with depth tracked explicitly, no maximum depth enforced, and cycles prevented by topological checks.
  • MDL-Driven Library Compaction: The library grows in depth and width before periodic compression through MDL-driven compaction.
  • MDL-Driven Library Compaction: MDL favors concise libraries that compactly explain successful behavior, using greedy merge, refactor, and prune operations constrained by held-out success.
  • Distillation Back into Weights: Distillation fine-tunes the policy on successful trajectories with skill plans and an auxiliary next-skill prediction loss, excluding trajectories that invoke pruned skills.
  • Distillation Back into Weights: The distillation loop compounds improvement because each updated policy produces richer trajectories for subsequent skill induction.

4 Experiments

Across three web-agent benchmarks, SCAFFOLD improves success rates over skill-augmented baselines and continues scaling across iterations while its recursive library remains compact, reusable, and more transferable. Ablations and robustness tests attribute these gains to complementary abstraction, composition, compaction, and distillation mechanisms.

  • Main Results: SCAFFOLD achieves 42.7% SR on WebArena, 36.3% on VisualWebArena, and 43.5% on OM2W-X, improving over SKILLRL by 11.1, 13.6, and 17.2 points respectively.All three improvements are statistically significant under paired bootstrap.
  • Ablation Study: Removing distillation lowers WebArena performance by 8.0 points, while removing recursive composition lowers WebArena by 6.3 points and OM2W-X by 7.4 points.Multi-instance induction, holdout validation, and MDL compaction contribute smaller but distinct effects.
  • Skill Abstraction vs. Iterative Fine-Tuning: Standard SFT on identical trajectories reaches 38.6, compared with 30.4 without a library and 34.7 with abstraction without distillation.The results separate benefits from self-generated-data fine-tuning, abstraction, and skill-call-aware distillation.
  • Iteration Scaling: SCAFFOLD continues improving through k=5, whereas flat-cache baselines plateau near k=2 and SKILLRL flattens after k=3.The reported slope remains positive at k=5, but experiments did not run beyond that iteration.
  • Library Depth and Reuse: MDL compaction reduces the library from nearly 470 skills without compaction to about 181, while mean depth rises from 1.05 at k=1 to 2.71 at k=5.Reuse reaches 64% at k=5 versus about 21% without compaction.
  • Cross-Site Transfer: SCAFFOLD reaches 35.9% mean off-diagonal transfer SR versus SKILLWEAVER’s 16.6%, a 19.3-point gap across Online-Mind2Web site pairs.Parametric skills transfer through parameter rebinding, while opaque selector-based APIs require site-specific rediscovery.
  • Stability Under Perturbations: SCAFFOLD degrades by at most 2.1 points under latency, DOM shuffling, and temporal drift, versus 3.6–4.4 points for SKILLWEAVER and SKILLRL.The reported robustness is associated with semantic grounding and postcondition checks.
  • Efficiency: SCAFFOLD uses 12.4 primitive actions per successful task, fewer than SKILLRL’s 14.3, SKILLWEAVER’s 15.1, and AWM’s 16.9.Primitive actions inside skills count toward the same horizon budget for every method.

5 Conclusions and Future Work

SCAFFOLD combines multi-instance parametric skill induction, recursive composition, MDL-driven compaction, and weight-level distillation in a self-improving web-agent loop. Across three benchmarks, it improves over strong skill-based baselines while continuing to improve through five iterations and keeping library size bounded.

  • SCAFFOLD combines multi-instance parametric skill induction, recursive hierarchical composition, MDL-driven library compaction, and weight-level distillation.
  • SCAFFOLD improves over the strongest skill-induction and skill-RL baselines by 11.1–17.2 absolute points across WebArena, VisualWebArena, and held-out Online-Mind2Web.
  • The framework continues improving through five iterations while keeping the skill library size bounded.
  • Future Work: Future work includes lighter self-trained inducers, OSWorld-style desktop agents, environment-grounded verification, and convergence analysis for recursive MDL compaction.

Limitations

The paper identifies five limitations involving model and verifier dependence, greedy compaction, and reduced transfer when held-out sites differ qualitatively from training sites. These constraints affect cost, autonomous deployment, optimization guarantees, and cross-site generalization.

  • Inducer dependence: SCAFFOLD relies on GPT-4o for skill induction and MDL refactoring, with the inducer accounting for approximately 70% of experimental dollar cost.
  • Verifier dependence: SCAFFOLD assumes a per-task verifier to label rollout success, limiting extension to fully autonomous deployment where success is rarely binary or self-evident.
  • Greedy MDL approximation: The MDL compaction step is greedy, has no convergence guarantee, and occasionally plateaus before a non-local refactor could further reduce F.
  • Cross-site transfer ceiling: Parametric skills generalize better than site-specific APIs, but gains shrink when held-out sites differ qualitatively from training sites.

Ethical Considerations

The paper discusses misuse, bias amplification, and energy costs, while the supplied passages also describe the prompts and mechanisms used to induce, compose, validate, and compact executable skills. These mechanisms include parameterized functions, preconditions, postconditions, recursive calls, and behavioral-equivalence checks.

  • Ethical Considerations: More capable web agents could enable spam, large-scale scraping, credential stuffing, or rate-limit evasion.
  • Ethical Considerations: Biases in induced skills can be reinforced across iterations through distillation, motivating audits of the skill library at each iteration.
  • Ethical Considerations: A full five-iteration run on one benchmark consumes approximately 36 A100-hours, making repeated full-loop hyperparameter searches costly.
  • Skill Induction: The inducer abstracts at least two successful, instruction-similar trajectories into one executable skill with typed parameters, observation predicates, primitive or skill calls, and a postcondition.
  • Library Compaction: Refactoring is accepted only when the MDL objective decreases and rewritten skills pass behavioral-equivalence checks on held-out trajectories.
  • Recursive Composition: Recursive skills can call lower-level skills, allowing a depth-3 checkout procedure to invoke one depth-2 skill and two depth-1 skills.

C Per-Site Analysis

SCAFFOLD’s strongest per-site gains occur on long-horizon, multi-step environments, especially GitLab, CMS, and VisualWebArena Shopping, while gains on shorter Reddit tasks are more modest. Both systems still share verifier brittleness and difficulty with modal occlusion.

  • Per-site performance: SCAFFOLD’s largest gains occur on GitLab, CMS, and VisualWebArena Shopping, the most long-horizon and multi-step sites.Recursive composition contributes most on these sites.
  • Evaluation scope: Table 4 reports per-site success rates for four WebArena sites and three VisualWebArena sites, with bootstrap-significant differences for every row.
  • Per-site performance: Gains on Reddit are more modest because its tasks are shorter and more retrieval-oriented, where flat libraries already perform well.
  • Failure analysis: Both systems can fail when exact-string verification rejects semantically correct trajectories or modal dialogs occlude target elements.SCAFFOLD’s precondition checks help with occlusion but do not fully solve it.

D Hyperparameter Sensitivity

The component and hyperparameter analyses support treating SCAFFOLD as an interacting mechanism rather than a collection of independent add-ons. Performance is broadly robust across tested hyperparameter ranges, with the multi-instance threshold most sensitive.

  • Hyperparameter sensitivity: Performance varies by ≤2.4 SR points across tested hyperparameter ranges, with nmin the most sensitive parameter.Smaller nmin values admit spurious skills, whereas larger values delay skill creation.
  • Component build-up: The ablation and incremental-build analyses jointly support induction, compaction, distillation, and multi-instance validation as one interacting mechanism.Induction abstracts, MDL compaction compresses, distillation consolidates, and validation keeps abstraction sound.
  • Component interactions: Composition creates the depth needed for long-horizon skills, while compaction prevents redundancy from burying that depth and diluting distillation signals.
  • Experimental controls: The comparisons hold the base model, task pool, iteration count, inducer, and evaluation protocol fixed.This controls the component comparisons against engineering scale and extra compute.

F Efficiency and Grounding Measurements

Efficiency experiments examine performance under action limits and the cost of semantic grounding, showing that cached hybrid grounding can remove most grounder calls while preserving robustness. The analysis also connects transferability to skills that are not bound to one site’s selectors.

  • Action-budget efficiency: SCAFFOLD remains at 42.3 success rate under pessimistic accounting that charges one extra primitive step per skill invocation.
  • Grounding efficiency: The hybrid grounding cache removes 62% of grounder calls at essentially no cost in accuracy or robustness.It reuses validated accessibility-tree paths and falls back to VLM grounding when cached selectors mismatch.
  • Grounding trade-offs: Static selectors are cheaper but lose 7.1 points under DOM-shuffle, identifying runtime semantic grounding as the source of the robustness gap.
  • Skill reuse: The most valuable skills are not necessarily site-specific: their 64% reuse rate and transfer results motivate per-site fast paths that preserve transfer.

G Skill Lifecycle and Distillation Hygiene

SCAFFOLD manages skill execution, degradation, and distillation through preconditions, postconditions, pruning, quarantine, and re-parsing against the current library. These mechanisms address runtime failures and stale abstractions while retaining a small regression on previously solved tasks.

  • Runtime failure handling: Unmet preconditions suppress skill invocation, while postcondition violations trigger one refreshed-state retry before control returns to the policy.
  • Skill lifecycle: Skills below 60% success over their last 20 invocations are quarantined and queued for re-induction from fresh trajectories.Skills unused for M iterations are also removed by the prune operator.
  • Lifecycle-driven repair: Adding a dismiss_blocking_modal skill improves WebArena SR by 0.9 points and reduces modal-related failures from 6.1% to 2.3% of episodes.
  • Related extensions: POLYSKILL’s interface typing and SKILLEVO’s fine-grained reward model are identified as complementary extensions that could address parameter typing and verifier dependence.
  • Distillation hygiene: Re-parsing trajectories against the post-compaction library prevents supervision toward deprecated skills, while a small replay buffer removes most of a remaining 1.2-point regression.

H Comparison with Concurrent Frameworks

Table 11 compares SCAFFOLD with POLYSKILL and SKILLEVO across the four design axes motivating the framework. The comparison also cautions that reported results differ in backbone, observation modality, and benchmark scale.

  • POLYSKILL maintains per-site implementations behind a shared interface, whereas SCAFFOLD uses one implementation with semantic references rebound at runtime.
  • POLYSKILL uses a prompt-side library that grows without a compression objective and induces skills without a multi-instance support requirement.
  • SKILLEVO’s reported results are not directly comparable with Table 1 because it uses text-only LLMs on WebArena-Lite’s 165 tasks, unlike SCAFFOLD’s visual-agent evaluation.
  • 63.8 SR is reported for SCAFFOLD on WebArena-Lite with Qwen2.5-VL-7B, versus 60.4 for SKILLEVO with Llama-3.1-8B, under an explicit backbone and observation-space caveat.
  • Table 11 presents the comparison as component-level analysis of SCAFFOLD and two concurrent skill-centric frameworks.
Loading 2609.05511v1…