PaperlayerView exact revision on arXiv

Source-linked AI summary

HyperSkill: Self-Evolving LLM Agents via Hypergraph-Structured Skill Memory

Ruiyao Xu, Tiankai Yang, Wei-Chieh Huang

arXiv:2608.16114v1cs.CL

TL;DR

Existing experiential-memory systems lose relationships among subtasks and skills by using isolated entries and flat retrieval. HyperSkill addresses this with hypergraph-structured storage, relational retrieval, and structure-informed maintenance, consistently outperforming ten baselines across three benchmarks, with gains up to +11.18 over No Memory.

  • Problem

    Existing memory systems discard compositional relationships among subtasks and skills and rely on flat similarity retrieval that cannot represent n-ary co-occurrence.

  • Method

    HyperSkill stores subtasks and reusable skills in trajectory-linked hyperedges, retrieves skills by trajectory co-occurrence, and maintains memory through quality-weighted propagation.

  • Results

    HyperSkill consistently outperforms ten memory baselines across xBench, GAIA, and WebWalkerQA, with gains up to +11.18 over No Memory.

  • Takeaways & Limitations

    The results support relational structure as a useful signal for experiential-memory retrieval and maintenance in the evaluated agentic tasks.

  • Takeaways & Limitations

    HyperSkill requires additional LLM calls for decomposition, skill extraction, and merge decisions, introducing extra inference cost.

Abstract

from arXiv · show

As agentic tasks grow in complexity, LLM agents increasingly rely on experiential memory to reuse procedural knowledge across tasks. Effective memory design must jointly address what to store, how memory is structured and retrieved, and how memory evolves. Existing systems tackle each only partially: they store trajectories, insights, or workflows as isolated entries, discarding compositional relationships among subtasks and reusable skills; retrieve by flat embedding similarity that ignores relational signals; and maintain memory without leveraging its relational structure. We propose HyperSkill, a hypergraph-based memory framework that jointly improves all three. HyperSkill represents memory as a hypergraph with two node types, subtask steps and reusable skills, where each hyperedge links the subtasks and skills from a single trajectory. Dual-path retrieval queries both subtask and trajectory levels, ranking skills by co-occurrence across retrieved trajectories. Periodic structure-informed maintenance prunes low-utility nodes and merges redundant skills via quality-weighted propagation. Across xBench, GAIA, and WebWalkerQA with GPT-4o and Qwen3-30B-A3B, HyperSkill outperforms ten memory baselines, yielding gains of up to +11.51 on GAIA and +11.18 on WebWalkerQA.

1 Introduction

Experiential agent memory must jointly determine what to store, how to structure and retrieve it, and how to evolve it, because existing systems address these dimensions only partially. HyperSkill addresses the gaps with hypergraph-structured memory that preserves compositional relationships among subtasks and skills, supports relational retrieval, and enables structure-informed maintenance.

  • Motivation: Experiential memory distills agents’ past trajectories into reusable knowledge, supporting self-improvement beyond a single context window.Unlike external-fact memory, it captures the agent’s own experience for reuse across episodes.
  • Representation gap: Flat trajectory, insight, workflow, and skill representations discard compositional relationships among subtasks and skills, preventing retrieval from exploiting shared procedural structure.Because tasks are compositional, superficially different tasks may still share reusable procedural structure.
  • Open problem: Existing experiential memory systems leave three fundamental questions unresolved: what to store, how memory is structured and retrieved, and how it evolves.These partial solutions limit agents’ capacity for self-improvement.
  • HyperSkill: HyperSkill models each trajectory as an n-ary hypergraph association among subtasks, skills, and an outcome, preserving structure that flat lists and pairwise edges represent only lossily.Its design combines hyperedges over subtasks and skills, dual-path retrieval, and quality-weighted propagation for merging redundant skills.
  • Results: Across xBench, GAIA, and WebWalkerQA under two model families, HyperSkill consistently outperforms ten memory baselines.The framework uses relational signals such as skill frequency across retrieved trajectories and quality-weighted propagation over hypergraph neighborhoods.

2 Related Work

Prior agent-memory systems differ in what they store, how they structure and retrieve it, and how they maintain it, but each leaves gaps in preserving or exploiting compositional procedural knowledge. Raw trajectories preserve context yet add noise, abstractions lose procedural detail, and isolated skills, flat retrieval, and entry-level maintenance discard structural information.

  • How memory is structured and retrieved: Most systems use flat vector databases or JSON files with embedding-based semantic retrieval, while pairwise graph edges discard joint n-ary episode context.Graph-based methods capture relational dependencies but decompose n-ary co-occurrence into disconnected binary links.
  • How memory evolves: Most systems accumulate memory unconditionally, while pruning, consolidation, and deduplication methods operate on individual entries without using graph topology or quality signals jointly.Existing maintenance therefore does not leverage structural information.
  • What is stored: Raw trajectories preserve full episode context but introduce substantial noise, whereas insights and workflows improve generalizability while discarding fine-grained procedural detail.These approaches represent different trade-offs in experiential-memory abstraction.
  • What is stored: Reusable-skill methods retain concise knowledge units but treat skills in isolation, lacking reusable subtask decompositions that capture procedural sequences across episodes.This limits transfer of compositional planning knowledge between tasks.

3 HYPERSKILL

HyperSkill organizes experiential memory as a hypergraph linking task subtasks with reusable skills extracted from trajectories. It retrieves complementary procedural and semantic evidence, ranks skills by trajectory co-occurrence, and periodically maintains memory through pruning and merging.

  • Memory representation: HyperSkill uses hyperedges to represent trajectories, connecting subtask nodes that encode workflow structure with reusable skill nodes that encode transferable execution strategies.Skill nodes are extracted from successful and failed trajectories as strategies to follow or error patterns to avoid.
  • Memory evolution: After each task, HyperSkill extracts new skills and a lesson, deduplicates similar skills, adds a trajectory hyperedge, updates utility scores, and periodically prunes or merges stale knowledge.Maintenance occurs every Nmaint tasks through quality-driven pruning and structure-informed merging.
  • Memory representation: Each trajectory hyperedge stores its task description and distilled lesson alongside the trajectory’s subtask and skill nodes, enabling retrieval of both wording and transferable patterns.Hyperedge embeddings concatenate the original task description with its distilled lesson.
  • Dual-path retrieval: Dual-path retrieval combines subtask matching for shared procedural structure with direct trajectory matching for similar high-level task semantics.The fused trajectories provide distilled lessons as trajectory-level context during execution.
  • Skill selection: HyperSkill ranks candidate skills by their co-occurrence across retrieved hyperedges rather than embedding similarity alone, then selects the top-k skills as execution guidance.Co-occurrence reflects whether a skill was applied in trajectories relevant to the current task; ties use embedding similarity to the task description.

4 Experiments

HyperSkill is evaluated on three diverse benchmarks with two backbone models against ten memory systems and a no-memory baseline. It achieves consistent success-rate gains, favorable token efficiency, and benefits from structure-aware memory maintenance and dual-path retrieval.

  • Datasets and Benchmarks: The evaluation spans xBench, GAIA, and WebWalkerQA, covering tool-augmented reasoning, open-ended web interaction, and compositional planning.xBench assesses agentic planning, tool use, and multi-step reasoning; GAIA requires multi-hop reasoning, multimodality, web browsing, and tool use; WebWalkerQA tests complex multi-turn web navigation.
  • Baselines: HyperSkill is compared with ten representative memory systems spanning trajectory-, workflow-/insight-, and graph-based methods, plus a No Memory baseline.All baselines use the same agent backbone and tool access for fair comparison.
  • Main Results: Under GPT-4o, HyperSkill improves SR over the second-best method by +3.00 on xBench, +2.30 on GAIA, and +0.59 on WebWalkerQA.Under Qwen3-30B-A3B, gains are +6.00, +4.85, and +11.18 over No Memory on xBench, GAIA, and WebWalkerQA, respectively.
  • Cost Analysis: 67K, 72K, and 57K average tokens per task place HyperSkill at the highest performance with moderate cost on xBench, GAIA, and WebWalkerQA, respectively.Generative and Voyager consume over 100K tokens yet perform below HyperSkill, while PlugMem costs substantially more and performs worse.
  • Sensitivity Analysis: ρ=0.1 yields the best maintenance-ratio performance; disabling pruning degrades retrieval quality, whereas ρ=0.4 removes still-useful skills.The results indicate that light pruning is sufficient to maintain effective memory.
  • Hypergraph Visualization: Shared skill nodes enable compositional reuse across trajectories, while failed trajectories form separate error-pattern skills that provide targeted warnings for recurring subtask patterns.The xBench visualization shows Cross-Source Validation and Targeted Database Search reused across trajectories, alongside Premature Entity Assumption among failure patterns.

5 Conclusion

HyperSkill is a hypergraph memory framework for self-evolving LLM agents that preserves compositional structure in trajectories. It combines dual-path retrieval with structure-informed maintenance to rank relevant skills and evolve memory.

  • HyperSkill stores each trajectory as a hyperedge binding subtask decompositions and outcome-conditioned skills.This preserves compositional structure discarded by flat and pairwise designs.
  • Dual-path retrieval matches at both subtask and task levels, then ranks skills by co-occurrence frequency across retrieved hyperedges.
  • Periodic maintenance prunes low-utility nodes and merges redundant skills through quality-weighted propagation.

Limitations … A.1 Dataset Details

HyperSkill’s limitations include extra inference costs, benchmark scope, and dependence on accumulated trajectories, while the appendices document datasets and implementation details. The evaluation follows MemEvolve’s protocol across GAIA, WebWalkerQA, and xBench.

  • Limitations: HyperSkill incurs extra inference costs because LLM calls perform task decomposition, skill extraction, and merge decisions during memory maintenance.Its current evaluation covers web navigation and multi-step reasoning benchmarks; broader generalization remains future work.
  • Limitations: HyperSkill may provide limited benefit in extremely low-data regimes because hypergraph retrieval and maintenance require enough trajectories to form a sufficiently populated memory graph.Sparse accumulated trajectories weaken the framework’s relational retrieval and maintenance processes.
  • Appendix Overview: The appendices include datasets and implementation details, additional analysis, broader impact, LLM-use disclosure, extended related works, ethics, and additional case studies.These materials are organized across Appendices A through G.
  • A.1 Dataset Details: The evaluation follows MemEvolve’s protocol and adopts the same three benchmarks.The three benchmarks are GAIA, WebWalkerQA, and xBench.
  • A.1 Dataset Details: 165 tasks comprise GAIA across Level-1 (53 tasks), Level-2 (86 tasks), and Level-3 (26 tasks), requiring multi-hop reasoning, web browsing, and tool use.The benchmark is organized into three difficulty levels.
  • A.1 Dataset Details: 680 queries across four domains and over 1,373 webpages comprise WebWalkerQA, while evaluation uses the same 170-query subset as MemEvolve.WebWalkerQA targets complex multi-turn web navigation.
  • A.1 Dataset Details: 100 tasks in xBench assess agentic planning, tool use, and multi-step reasoning across diverse real-world scenarios.xBench is the third benchmark adopted under the evaluation protocol.

A.2 Implementation Details · B More Analysis

The implementation uses a shared MemEvolve-based architecture and standardized retrieval settings for fair comparison, with model-specific backends and budgets. Memory updates, maintenance, reproducibility controls, and hypergraph structure are explicitly configured.

  • A.2 Implementation Details: All methods share the MemEvolve codebase and agent architecture, with retrieval count 3 and all-MiniLM-L6-v2 embeddings using cosine similarity.These settings support fair comparison across methods.
  • A.2 Implementation Details: GPT-4o uses the OpenAI API at temperature 0.7 with retrieval budgets (ku, ke, ks) = (2, 2, 2).
  • A.2 Implementation Details: Qwen3-30B-A3B runs locally via vLLM on NVIDIA A100 80 GB GPUs at temperature 0.7 with retrieval budgets (ku, ke, ks) = (5, 5, 5).
  • A.2 Implementation Details: The recent interaction-history sliding window is set to w = 3 steps.
  • A.2 Implementation Details: Memory updates use δdedup = 0.9, neutral prior γ = 0.5 for untested nodes, and utility-blending coefficient β = 0.7.
  • A.2 Implementation Details: Maintenance runs every ⌈0.1 × N⌉ tasks with τprune = 0.2, Nmin = 3, and δmerge = 0.85; tasks use fixed random order with seed 42.Tasks are processed sequentially, and the schedule depends on benchmark task count N.
  • A.2 Implementation Details: On WebWalkerQA, the hypergraph visualization shows trajectory hyperedges connecting success and failure skill nodes with subtask nodes, including 3 success and 2 failure hyperedges.

B.1 Self-Evolving Analysis

HyperSkill is the only method showing sustained improvement in cumulative success across episodes, with GAIA accuracy rising from early to final episodes. This suggests its hypergraph memory accumulates transferable skills and benefits from diverse cross-task skill co-occurrence patterns.

  • Self-Evolving Analysis: HyperSkill is the only method exhibiting a sustained upward trajectory in cumulative success across episodes.The analysis evaluates cumulative success as a function of episode index across all three benchmarks.
  • Self-Evolving Analysis: On GAIA, HyperSkill’s cumulative accuracy climbs steadily from early episodes through the final ones, indicating transferable skills accumulate over time.This contrasts with baselines such as DiLu on xBench, which peak early and stagnate or dip before recovering.
  • Self-Evolving Analysis: HyperSkill benefits most when its hypergraph captures diverse cross-task skill co-occurrence patterns.The reported episodic trends attribute its self-evolving advantage to relational skill reuse across tasks.

B.2 Latency Analysis · B.3 Memory Growth Analysis

HyperSkill incurs moderate latency overhead primarily from task decomposition and skill extraction calls, while its hypergraph memory grows with linearly increasing subtask nodes but sublinearly increasing skill nodes. Deduplication and periodic merging keep skill counts below hyperedge counts across benchmarks and backbones.

  • B.2 Latency Analysis: Average per-task execution time is evaluated across all three benchmarks under both Qwen3-30B-A3B and GPT-4o.Figure 8 reports wall-clock latency for both backbones.
  • B.2 Latency Analysis: 42.6s vs. 26.5s on xBench, 33.6s vs. 33.6s on GAIA, and 31.3s vs. 23.9s on WebWalkerQA under Qwen3-30B-A3B.The comparisons are HYPERSKILL versus the fastest baseline, with GAIA matching DILU.
  • B.2 Latency Analysis: 48.3s, 47.6s, and 55.3s versus 29.7s, 32.5s, and 41.9s under GPT-4o across xBench, GAIA, and WebWalkerQA.The first triplet gives HYPERSKILL times; the second gives the fastest-baseline times.
  • B.2 Latency Analysis: The latency overhead primarily stems from the additional LLM call for task decomposition and skill extraction, rather than from the hypergraph.This attribution applies in both backbone settings.
  • B.3 Memory Growth Analysis: Subtask nodes grow roughly linearly over successive tasks because each task introduces a new decomposition.Figure 9 tracks hypergraph evolution over successive tasks.
  • B.3 Memory Growth Analysis: Both skill types grow sublinearly because insertion-time deduplication blocks near-duplicates and periodic structure-informed merging consolidates redundant entries.These mechanisms operate together during hypergraph evolution.
  • B.3 Memory Growth Analysis: Skill counts remain well below the number of hyperedges across all benchmarks and backbones.The passage attributes this pattern to deduplication and periodic merging.

B.4 Robustness Analysis … D Disclosure of LLM Use

HyperSkill remains robust when outcome labels are self-judged, while its hypergraph behavior is visualized across benchmarks. The paper also discusses potential efficiency benefits, bias risks, and the authors’ use of LLM tools during manuscript preparation.

  • B.4 Robustness Analysis: B.4 Robustness Analysis: Self-judge performance retains 87.7–96.8% of GT-judge success rates on GPT-4o.Retention is defined as Self-judge SR / GT-judge SR × 100%.
  • B.4 Robustness Analysis: B.4 Robustness Analysis: HyperSkill exhibits an upward cumulative success-rate trend across benchmarks on Qwen3-30B-A3B.Figure 7 plots cumulative success rate (%) over episode index.
  • B.4 Robustness Analysis: B.4 Robustness Analysis: Occasional mislabeled skills still leave the structural signal reliable without ground-truth feedback.The self-judge setting evaluates trajectory outcomes without access to the gold answer.
  • B.5 Hypergraph Visualization: B.5 Hypergraph Visualization: Figure 6 presents the WebWalkerQA counterpart of the xBench hypergraph subgraph shown in Figure 5.
  • C Broader Impact: C Broader Impact: Learning from past failures may reduce redundant computation and improve efficiency in deployed systems.The framework is general-purpose and does not target a specific high-risk application.
  • C Broader Impact: C Broader Impact: Accumulated memory could reinforce biases from early trajectories unless practitioners periodically audit stored skills for unintended patterns.
  • D Disclosure of LLM Use: D Disclosure of LLM Use: LLM-based tools assisted with grammar correction, code debugging, and figure design during manuscript preparation.The authors state that they conducted the scientific content, experimental design, and analysis and take responsibility for the final manuscript.

E Extended Related Works · F Ethics Statement

The related-work review organizes experiential memory systems by storage, retrieval structure, and evolution, positioning HyperSkill’s hypergraph design as supporting relational skill reuse and topology-aware maintenance. The ethics statement describes reproducibility and privacy practices while acknowledging potential bias reinforcement in accumulated memory.

  • E Extended Related Works: Experiential memory systems are compared across what they store, how they structure and retrieve it, and how memory evolves.Table 3 summarizes this taxonomy.
  • E Extended Related Works: Stored experience ranges from raw trajectories and extracted insights to workflows, reasoning strategies, executable API skills, tips, and hierarchical skill libraries.SkillRL and MemSkill further use reinforcement learning to evolve skill-related memory or memory operations.
  • E Extended Related Works: Most systems retrieve from flat vector stores using semantic similarity, while alternatives use contrastive retrieval, prompt concatenation, function matching, or graph-based mechanisms.The review contrasts these approaches with HyperSkill’s relational retrieval design.
  • E Extended Related Works: HyperSkill uses hyperedges to preserve full trajectory context and combines subtask-level with task-level queries for retrieval.This dual-path mechanism supports co-occurrence-based skill ranking.
  • E Extended Related Works: Most memory systems accumulate knowledge without curation, while existing maintenance operations act independently per node rather than considering memory topology.The review lists test-and-prune, episodic consolidation, deduplication, and failure-driven adjustment as lightweight alternatives.
  • E Extended Related Works: Graph-structured systems mainly represent factual knowledge, whereas HyperMem uses a three-level hypergraph for coarse-to-fine factual retrieval and HyperSkill targets experiential task knowledge.Table 4 distinguishes factual versus experiential memory and pairwise versus n-ary edge types.
  • F Ethics Statement: The authors provide methodological details for reproducibility, use public benchmarks without processing personal information, and acknowledge that accumulated memory may reinforce biases without periodic auditing.They state that LLM tools were used only for grammar correction, code debugging, and figure design, while scientific work remained author-conducted.

G Additional Case Studies · H Algorithm · I Prompts

The appendix illustrates HyperSkill through three benchmark case studies, formalizes its per-task retrieval and periodic memory-evolution algorithms, and specifies prompts for decomposition, extraction, merging, and agent-context assembly.

  • G Additional Case Studies: G Additional Case Studies: The xBench literary-trivia case decomposes cross-domain verification into four steps and correctly identifies bitter-almond flavor as the prop poison detail.The agent progresses from identifying Madame Bovary and its 1991 adaptation to authoritative film-database verification, guided by multi-stage verification and source confirmation.
  • G Additional Case Studies: G Additional Case Studies: The GAIA scientific-calculation case retrieves measurements from two papers, computes round(1/4.5 × 100), and concludes that the sea-star piece was approximately 22% of shrimp length.Domain-specific query refinement and task splitting into parallel paper-retrieval subtasks support the calculation.
  • G Additional Case Studies: G Additional Case Studies: The WebWalkerQA game-knowledge case concludes that Malians use Griot Bara for global buffs, whereas Chinese use the Great Wall defensively.The execution first explores the official site, then consults community and wiki sources for fourth-age details.
  • H Algorithm: H Algorithm: Algorithm 1 retrieves top-k hyperedges through subtask and trajectory paths, fuses them, ranks skills by co-occurrence, executes with retrieved context, and updates memory.After execution, newly extracted skills and lessons are deduplicated or added, linked by a new hyperedge, and used to update utility.
  • H Algorithm: H Algorithm: Algorithm 2 evolves memory every ⌈0.1 × N⌉ tasks by pruning low-utility nodes and merging related skill nodes using propagated structural embeddings.Merging reassigns hyperedge memberships after LLM-based consolidation.
  • I Prompts: I Prompts: Benchmark-specific decomposition prompts constrain step counts and tool use, while GAIA prioritizes attached files and WebWalkerQA requires crawling the root URL before section navigation.The xBench prompt additionally requires each step to identify the data and processing method.
  • I Prompts: I Prompts: Success and failure prompts extract short reusable skills or mistakes, while merging prompts consolidate structurally related items into one broader JSON-formatted knowledge unit.Retrieved memory is assembled once per episode into past experience, relevant skills, and mistakes to avoid.
Loading 2608.16114v1…