💻 computer science

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

HyperSkill is a novel framework that enhances LLM agent performance on complex tasks by representing experiential memory as a hypergraph of subtasks and reusable skills, enabling more effective storage, relational retrieval, and self-evolving maintenance that significantly outperforms existing baselines.

Original authors: Ruiyao Xu, Tiankai Yang, Wei-Chieh Huang

Published 2026-08-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ruiyao Xu, Tiankai Yang, Wei-Chieh Huang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a computer program designed to act like a human assistant, capable of navigating the internet, using tools, and solving complex, multi-step problems. These programs, known as AI agents, do not just answer questions; they take actions, observe the results, and try again if they fail. For these agents to get better over time, they need a way to remember what they have done before. Just as a human learns from a past mistake or a successful strategy, an agent needs to store its experiences so it can reuse them later. The challenge lies in how to organize this memory. If an agent simply saves a long list of every action it ever took, the information becomes a messy pile of noise. If it saves only the final answer, it loses the step-by-step logic that made the solution work. The key to building a truly self-improving agent is finding a way to store not just the raw data of an event, but the relationships between the small steps taken and the skills used to solve them.

Researchers have been trying to solve this problem by creating different systems for agent memory. Some systems save entire stories of past interactions, while others try to distill those stories into short summaries or lists of "skills." However, these existing methods often treat each piece of information as an isolated item. They might remember that a specific task was solved, but they fail to capture how the small steps of that task connect to the reusable skills that made it possible. They also struggle to update their memory efficiently, often just adding new information without checking if old information has become useless or if two similar skills are actually the same thing. This limitation prevents agents from truly evolving, as they cannot easily see the patterns that link different tasks together.

To address these gaps, a team of researchers has developed a new framework called HYPERSKILL. Instead of storing memories as a flat list or a simple chain of connections, this system organizes an agent's experiences into a complex web where a single memory unit links multiple related pieces of information at once. Think of a memory not as a single file, but as a group photo that captures a specific journey, the individual steps taken along the way, and the specific tools or strategies used to get there, all tied together in one package. When the agent faces a new problem, it does not just search for a similar past story. Instead, it breaks the new problem down into its smaller parts and looks for past journeys that share those same parts, regardless of whether the overall story looks different on the surface.

The system works by creating two types of memory nodes: one for the specific steps of a task and another for the reusable skills that can be applied across many different tasks. These nodes are connected by a special link that represents a complete journey the agent has taken. When a new task arrives, the agent uses a dual-path search to find the most helpful past experiences. First, it looks for past journeys that share the same small steps as the current task. Second, it looks for journeys that match the overall description of the task. By combining these two searches, the system can find relevant experiences that a simpler search would miss. Once it finds these past journeys, it ranks the skills used in them based on how often they appeared together in successful outcomes. This allows the agent to prioritize the most reliable strategies rather than just guessing based on how similar the words sound.

As the agent continues to work and accumulate more experiences, the system automatically refines its memory to keep it useful. It regularly checks the stored information to remove skills or steps that have proven to be ineffective or that are no longer needed. It also looks for skills that are essentially the same and merges them into a single, stronger entry. This process ensures that the memory remains compact and high-quality, preventing the agent from being overwhelmed by redundant or low-value information. The researchers tested this system on three different benchmarks involving complex web navigation, multi-step reasoning, and tool use. They compared HYPERSKILL against ten other memory systems using two different large language models. The results showed that the new framework consistently outperformed the others, achieving higher success rates on difficult tasks. For instance, on one specific test, it improved the success rate by more than eleven percentage points compared to having no memory at all, and it did so without requiring significantly more computing power or time.

The study suggests that the way memory is structured is just as important as the memory itself. By preserving the relationships between tasks, steps, and skills, and by allowing the system to evolve its own knowledge base, HYPERSKILL enables agents to learn more effectively from their own history. The researchers found that simply adding more memory without a smart way to organize and clean it could actually hurt performance, leading to confusion and errors. Their approach, which combines a structured web of connections with a disciplined process for pruning and merging, offers a path toward agents that can truly grow more competent with every experience they have. While the system currently relies on the agent to break down tasks and extract lessons, which adds a small cost to its operation, the gains in accuracy and efficiency suggest that this method of organizing knowledge is a significant step forward for autonomous systems.

Technical Summary: HYPERSKILL

Problem Statement

As Large Language Model (LLM) agents tackle increasingly complex, long-horizon tasks (e.g., web navigation, scientific reasoning), they increasingly rely on experiential memory to distill past trajectories into reusable knowledge. However, existing memory systems suffer from three fundamental limitations that hinder self-evolution:

What to Store: Current systems either store raw trajectories (noisy), abstract workflows (losing procedural detail), or extract isolated skills (discarding compositional relationships). They fail to preserve the n-ary associations between subtasks, reusable skills, and outcomes within a single trajectory.
How to Structure and Retrieve: Most approaches use flat vector stores or simple pairwise graphs. These structures rely solely on semantic embedding similarity, failing to capture relational signals such as the co-occurrence of a specific skill with a set of subtasks across multiple successful trajectories.
How Memory Evolves: Existing systems typically accumulate knowledge unconditionally or apply lightweight, isolated operations (e.g., simple deduplication). They lack mechanisms to jointly consider node quality and graph topology to prune low-utility knowledge or merge redundant skills.

Methodology: HYPERSKILL

The authors propose HYPERSKILL, a memory framework that models experiential knowledge as a hypergraph $G = (V, E)$ to jointly address storage, retrieval, and evolution.

1. Memory Architecture

The memory is structured as a hypergraph with two node types and hyperedges connecting them:

Nodes ( $V = V_u \cup V_s$ ):
- Subtask Nodes ( $V_u$ ): Represent discrete steps in a task decomposition, encoding preconditions and step descriptions.
- Skill Nodes ( $V_s$ ): Represent reusable execution strategies (positive or error patterns) extracted via outcome-conditioned prompting. Each node carries a utility score ( $\gamma$ ) dynamically updated based on empirical success rates and step efficiency.
Hyperedges ( $E$ ): Each hyperedge corresponds to a single trajectory $\tau$ . It connects the specific set of subtask nodes and skill nodes involved in that trajectory, along with a distilled lesson and the original task description. Unlike pairwise edges, hyperedges preserve the full compositional context of an episode.

2. Dual-Path Retrieval

To retrieve relevant context, HYPERSKILL employs a two-path strategy that queries both subtask and trajectory levels:

Subtask Path: The current task is decomposed into subtasks. These are matched against stored subtask nodes to retrieve candidate hyperedges sharing the same procedural structure, regardless of surface-level wording differences.
Trajectory Path: The full task description is matched directly against hyperedge embeddings (concatenation of task description and distilled lesson) to retrieve trajectories with similar high-level semantics.
Fusion: The candidate sets from both paths are merged.

3. Skill Ranking via Co-occurrence

Instead of ranking retrieved skills solely by semantic similarity to the query, HYPERSKILL ranks them by co-occurrence frequency across the retrieved hyperedges. A skill appearing in many retrieved trajectories is deemed more likely to be relevant, leveraging the structural signal that semantic similarity alone cannot provide.

4. Structure-Informed Maintenance

The memory undergoes periodic refinement to prevent stagnation and noise:

Quality-Driven Pruning: Nodes that are frequently retrieved but consistently fail to improve outcomes (low utility score $\gamma$ ) are removed.
Structure-Informed Merging: Redundant skill nodes are identified and merged. This process uses quality-weighted propagation over the hypergraph to compute structural embeddings. Nodes with high structural similarity and high utility are consolidated into higher-order skills, preserving the integrity of the graph.

Key Contributions

Hypergraph-Based Representation: The paper introduces a novel memory structure that natively preserves n-ary associations between subtasks, skills, and outcomes, addressing the lossy nature of flat lists and pairwise graphs.
Dual-Path Retrieval Mechanism: A retrieval system that combines procedural substructure matching (subtask path) with semantic task matching (trajectory path), enhancing the recall of relevant trajectories.
Co-occurrence Based Ranking: A method for selecting execution guidance that prioritizes skills based on their structural frequency in retrieved trajectories rather than just semantic similarity.
Joint Evolution Strategy: A maintenance protocol that leverages graph topology and node utility to prune and merge knowledge, ensuring the memory remains compact and high-quality.

Experimental Results

HYPERSKILL was evaluated on three benchmarks (xBench, GAIA, WebWalkerQA) using two backbone models (GPT-4o and Qwen3-30B-A3B).

Performance Gains: HYPERSKILL outperformed ten representative baselines (including trajectory-level, workflow-level, and graph-based methods) across all benchmarks.
- On GAIA with Qwen3-30B-A3B, it achieved a +4.85% improvement in success rate over the No Memory baseline.
- On WebWalkerQA with Qwen3-30B-A3B, it achieved a +11.18% improvement.
- With GPT-4o, it consistently achieved the highest or near-highest success rates, outperforming the second-best method by significant margins (e.g., +2.30% on GAIA).
Efficiency: Unlike some baselines that increased token usage and step counts without proportional gains, HYPERSKILL achieved high success rates with moderate token costs. For instance, on xBench with GPT-4o, it matched the fewest steps (5.27) among top performers while maintaining high accuracy.
Ablation Studies: Removing the hypergraph structure (reverting to flat retrieval) or removing either the subtask or trajectory retrieval path resulted in significant performance drops, validating the necessity of the dual-path and hypergraph design.

Significance and Claims

The paper claims that HYPERSKILL represents a significant step toward self-evolving agents. By treating a trajectory not as a single unit of knowledge but as an n-ary association, the framework enables agents to grow more competent with each interaction rather than starting from scratch.

The authors emphasize that the improvements stem from the memory framework itself rather than specific backbone behaviors, as gains were consistent across different model families. Furthermore, the structure-informed maintenance mechanism is highlighted as crucial; without it, unconditional accumulation of memory introduces noise that actively harms agent performance. The work demonstrates that preserving compositional structure and leveraging relational signals (co-occurrence) are essential for effective procedural knowledge transfer in complex agentic tasks.