PaperlayerView exact revision on arXiv

Source-linked AI summary

Trace2Tower: Transition-Aware EigenTrace Induction of Multi-Level Skills for LLM Agents

Jiazheng Sun, Boyu Yang, Binhao Yuan, Mingxuan Li, Xin Peng

arXiv:2609.05261v1cs.AIcs.SE

TL;DR

LLM agents need methods that capture temporal dependencies and outcome-conditioned behavior rather than relying on shallow trajectory retrieval or flat skill summaries. Trace2Tower induces canonical events, an outcome-aware transition graph, and contrastive spectral behavioral modes organized into a verifier-refined skill tower. It achieves 87.31% ALFWorld success and 50.67% WebShop exact success while using 10.35 steps and 0.26 invalid actions on ALFWorld.

  • Problem

    Existing trajectory-reuse and skill-extraction methods do not retain compact behavioral structures that capture decision patterns while removing task-specific noise and failure-related shortcuts.

  • Method

    Trace2Tower abstracts trajectories into canonical events, integrates semantic, transition, and outcome evidence in a graph, applies contrastive spectral decomposition, and organizes modes into action-, procedure-, and strategy-level skills.

  • Results

    Trace2Tower outperforms existing baselines across ALFWorld and WebShop, achieving 87.31% ALFWorld success and 50.67% WebShop exact success.

  • Takeaways & Limitations

    The induced hierarchy supports compact, adaptable experience reuse across distinct execution environments and remains editable through feedback without re-induction.

Abstract

from arXiv · show

Large language model agents increasingly rely on execution traces to master complex interactive tasks. However, current paradigms are bottlenecked by shallow trajectory retrieval and flat skill summarization, fundamentally ignoring the temporal dependencies and outcome-conditioned topology of agent behavior. We introduce Trace2Tower, a transition-aware EigenTrace framework that distills raw trajectories into a robust skill hierarchy. Trace2Tower abstracts step-level interactions into canonical events, constructing a unified graph governed by semantic compatibility, transition dynamics, and outcome evidence. Through a novel contrastive spectral decomposition, it isolates stable, success-aligned behavioral modes while rigorously suppressing failure-prone shortcuts. These modes organically populate a dynamic skill tower of action templates, procedural routines, and overarching task strategies, continuously refined via verifier-guided feedback. On ALFWorld, Trace2Tower achieves 87.31% success requiring only 10.35 steps and 0.26 invalid actions; on WebShop, it reaches 50.67% exact success. Across both benchmarks, Trace2Tower significantly outperforms existing baselines in task mastery and context-efficient experience reuse.

Introduction

Trace2Tower addresses the challenge of converting execution traces into compact, reliable behavioral structures by modeling semantic relations, execution dependencies, outcomes, and hierarchical composition. It induces multi-level skills and reports strong results on ALFWorld and WebShop.

  • Historical trajectories capture effective action patterns, intermediate states, recovery procedures, and long-term strategies beyond pretrained knowledge.
  • Existing approaches reuse demonstrations, memories, guidelines, or skills, but the underlying behavioral relations remain implicit.
  • Trace2Tower transforms raw trajectories into canonical events, an outcome-aware transition graph, and success-aligned behavioral modes through contrastive spectral decomposition.
  • Trace2Tower achieves 87.31% ALFWorld success and 50.67% WebShop exact success while using 10.35 steps and 0.26 invalid actions on ALFWorld.
  • The induced modes form action-, procedure-, and strategy-level skills refined through verifier-guided feedback for compact, transferable experience reuse.

Related Work

Related work advances from trajectory reuse toward persistent skill libraries and structured skill relations. Trace2Tower instead constructs outcome-conditioned behavioral structure before reusable procedures exist.

  • Experience-learning agents reuse prior interactions through reasoning loops, feedback, executable programs, retrieved episodes, and step-level evidence.
  • Skill-library systems discover, refine, accumulate, and organize persistent capabilities for lifelong learning and inter-skill retrieval.
  • Trace2Skill distills successful and failed trajectories, while graph-based methods represent dependencies or directed skill relations.
  • Trace2Tower differs by building an outcome-conditioned graph over canonical events before reusable procedures exist.

Problem Formulation

Trace2Tower represents interaction histories as successful or failed trajectories composed of task-contextual step records, then abstracts them into ordered canonical events and a three-level skill tower.

  • Each interaction history records task success and an ordered trajectory of step-level interaction records.
  • Each step contains the task, observation, available actions, selected action, and feedback.
  • Trace2Tower maps each trajectory to an ordered sequence of canonical events for structure induction.
  • The induction function produces a three-level tower representing action-, procedure-, and strategy-level skills.
  • The target is a compact hierarchy whose relations are supported by semantic, transition, and outcome evidence.

Method

Trace2Tower builds a transition-aware behavioral graph from canonical events, contrasts successful and failed evidence, extracts stable spectral modes, and organizes them into an editable skill tower.

  • Event-Level Trajectory Segmentation: Trajectories are segmented into canonical events at changes in subgoals, action families, entities, states, or feedback.
  • Event-Level Trajectory Segmentation: Typed arguments normalize equivalent behavior while preserving event order for executable transition estimation.
  • Transition-Aware EigenTrace Graph Construction: The graph integrates semantic compatibility, transition dependency, and outcome-conditioned transition evidence into robust behavioral topologies.
  • Transition-Aware EigenTrace Graph Construction: These signals transfer evidence across varied language, preserve executable direction, and distinguish useful dependencies from failure-correlated shortcuts.
  • Contrastive EigenTrace Decomposition: Contrastive affinity increases with success evidence, decreases with failure evidence, and remains bounded by successful affinity.
  • Contrastive EigenTrace Decomposition: Spectral decomposition partitions graph components into procedure groups using an eigengap-selected count, with isolated or tiny components kept separate.
  • Contrastive EigenTrace Decomposition: Well-separated behavioral modes remain stable under bounded graph-estimation error.
  • Hierarchical Skill Induction and Deployment: The hierarchy maps events to action skills, clusters procedure skills, and derives strategy paths from successful contrastive procedure edges.

Experiments

Trace2Tower is evaluated on ALFWorld and WebShop under matched trajectory pools, models, tasks, and budgets, using two deployment policies. It consistently outperforms baselines, while ablations and transfer tests probe hierarchy structure, efficiency, and robustness.

  • Benchmark setup: The evaluation covers 134 ALFWorld test tasks across six families and a fixed 100-task WebShop test manifest.Skills are induced from 1,240 ALFWorld and 400 WebShop trajectories.
  • Overall performance: Both Trace2Tower deployment policies consistently outperform baselines across ALFWorld and WebShop.The High-only policy uses retrieved strategy paths, whereas Full additionally injects step-aligned procedure skills.
  • Overall performance: 50.67% WebShop exact success is achieved by Full, while High-only reaches 48.33% and prioritizes lower context cost.Full maximizes performance, whereas High-only offers a more cost-efficient deployment choice.
  • Generalization: Trace2Tower maintains high performance across all six ALFWorld task families, while competing baselines degrade on specific families.Full leads on Clean-and-Place, Heat-and-Place, and Pick-Two-and-Place; High-only leads on Pick-and-Place.
  • Structural ablations: Removing transition dynamics lowers ALFWorld success from 87.31% to 70.15% and reduces the hierarchy from 39 procedures and 118 strategies to 19 and 76.Removing outcome evidence or contrastive affinity lowers success to 73.88%; contrastive affinity reduces the hierarchy to 10 procedures and 44 strategies.
  • Cross-model transfer: The Flash-authored Tower improves both user models by 12.69 percentage points, while a GPT-5.4-authored Tower raises Flash-user success from 65.67% to 88.06%.The GPT-5.4-authored result records 34 paired wins against 4 losses with p = 6.04 × 10^-7.
  • Hierarchy organization: The hierarchy compresses 13,724 segments into 3,764 quotient nodes, inducing 39 procedures and 118 strategies with 16.85% fewer GPT tokens than SkillX.Each procedure aggregates 352 event segments on average, and strategy paths compose two to four procedures.

Conclusion

Trace2Tower builds editable multi-level skill hierarchies from semantic, transition, and outcome evidence. Across ALFWorld and WebShop, it achieves strong task success with efficient execution and supports transfer, feedback refinement, and adaptable experience reuse.

  • Conclusion: Trace2Tower induces action-, procedure-, and strategy-level skills from semantic, transition, and outcome evidence.Verifier-guided feedback can refine the hierarchy after deployment without re-induction.
  • Conclusion: Trace2Tower achieves 87.31% ALFWorld success and 50.67% WebShop exact success with efficient execution.Ablations and cross-model transfer validate the induced behavioral structure.
  • Conclusion: The hierarchy remains editable after deployment rather than becoming a static skill library tied to its original trajectory pool.Feedback-based graph edits improve a frozen Tower without re-induction.

Appendix A: Proof of Contrastive Stability

The appendix establishes stability properties for Trace2Tower's outcome-conditioned contrastive affinities and characterizes the spectral procedure-induction relaxation. It also explains invariance and component-wise handling in the induced representation.

  • Contrastive Stability: The Contrastive Stability lemma defines the retained edge transformation from success- and failure-conditioned affinities.The proof shows the transformation is bounded, nondecreasing in success affinity, and nonincreasing in failure affinity.
  • Contrastive Stability: The stability bound does not require independence between success and failure affinities estimated from the same trajectory pool.The transformation does not amplify total affinity perturbation beyond the sum of its two inputs.
  • Spectral procedure induction: For each positive-degree connected component, Trace2Tower selects a procedure subspace through a constrained normalized-Laplacian relaxation.The minimizing subspace is spanned by the next eigengap-selected eigenvectors.
  • Representation invariance: Row normalization followed by K-means makes the procedure partition invariant to global orthogonal basis changes.Zero-norm rows become singleton groups, and symmetrization is used only for procedure discovery.

Appendix C: Proof of EigenTrace Stability

The appendix establishes stability of the retained EigenTrace subspace under graph perturbations and describes the component-wise procedure and skill-tower construction pipeline.

  • Proof of EigenTrace Stability: Δc > 2εc yields a Davis–Kahan stability guarantee for the retained EigenTrace invariant subspace under normalized-graph perturbations.The theorem controls subspace changes rather than discrete component membership or individual eigenvectors.
  • Proof of EigenTrace Stability: Contrastive transformation remains stable to errors in A+ and A−, while a separated EigenTrace block remains stable to normalized-graph perturbations.
  • Skill-Tower Induction: Component-wise induction constructs procedure skills from EigenTrace representations after selecting component-specific eigengaps and clustering them with K-means.Zero-degree nodes are singleton groups, and small components remain single groups.
  • Skill-Tower Induction: The pipeline builds canonical events, observed-transition graphs, procedure clusters, and three skill levels: action, procedure, and success-supported strategy skills.Algorithm 1 explicitly retains maximal success-supported paths as strategy skills.
  • Skill-Tower Induction: Consecutive repetitions are removed while procedure order is preserved before rebuilding transition, outcome, and contrastive graphs for strategy induction.
  • Complexity: The reported spectral configuration has dominant component-wise dense costs and bounds peak dense memory by the largest component.The complexity description applies to the reported full eigengap search and does not assume an unreported partial eigensolver.

E.2 Experimental Configuration

The experiments use controlled benchmark pools, fixed horizons, standardized models, and matched evaluation conditions, with structural ablations and cross-model tests examining the method’s components and transferability.

  • Experimental Configuration: ALFWorld evaluates 134 solvable unseen tasks, while WebShop uses a frozen 100-task test manifest under a shared 20-step horizon.
  • Experimental Configuration: GPT-5.4 authors and rewrites skills, DeepSeek-V4-Flash executes by default, and skill rendering is schema constrained.
  • Experimental Configuration: All automatic baselines share the benchmark pool, Skill User, evaluation manifest, environment implementation, and interaction horizon, while retaining native experience representations.
  • Structural Ablations: Removing transition evidence causes the largest degradation and reduces induced procedures and strategies from 39/118 to 19/76.The ablation is a single evaluation on all 134 ALFWorld tasks, whereas Full is averaged across three complete runs.
  • Cross-Model Transfer: With DeepSeek-V4-Flash as Skill User, the GPT-5.4-authored Tower reaches 88.06% success versus 65.67% for the DeepSeek-authored Tower.The paired comparison has p = 6.04 × 10−7; with DeepSeek-V4-Pro, the corresponding comparison is 85.82% versus 79.10%, p = 0.150.
  • Skill Construction: ALFWorld construction produces 39 procedure skills and 118 strategy skills, with deployment retrieval using 53 distinct High skills and 30 distinct Mid skills.

Appendix F: Verifier-Guided Refinement and Feedback Evaluation

Verifier-guided refinement updates a frozen skill hierarchy through structural edits selected using relevance and feedback evidence, without repeating the initial induction pipeline.

  • Refinement Procedure: Refinement operates on the frozen hierarchy without repeating event segmentation, graph construction, or spectral decomposition.This permits post-deployment correction of the learned structure.
  • Refinement Procedure: Candidate Towers are evaluated on the same task manifest using paired outcomes and compared by semantic relevance, structural relevance, and verifier-feedback evidence.
  • Refinement Procedure: The edit operators split heterogeneous procedures, merge compatible procedures, promote success-supported paths, or downweight harmful strategy reuse.

F.2 Feedback Evaluation

Structural refinement improves pooled success over the frozen Tower across two held-out sets, although the better relevance representation differs between sets.

  • Feedback Evaluation: 84.58% pooled success follows TF–IDF-based Pareto selection, compared with 80.42% for the frozen Tower.
  • Feedback Evaluation: 83.75% pooled success follows embedding-based selection, also exceeding the frozen Tower’s 80.42%.TF–IDF performs better on the first held-out set, while embedding relevance performs better on the second.
Loading 2609.05261v1…