Graph Memory Framework LExGraph: Solving the Memory Challenge in Long-Horizon Exploration Tasks

Long-term problem-solving processes—such as scientific research or software development—often approach the core objective along a trajectory of constant trial and error and circuitous progress. Researchers call such tasks "exploration tasks." Unlike conventional question answering, exploration tasks require models to remember not only facts, but also how each solution was tested by intermediate results and how early attempts were repeatedly revised or even reactivated. Most existing long-term memory research focuses on the recall and updating of facts, while neglecting the intrinsic relatedness of the exploration process itself. Research from the MBZUAI NLP team targets exactly this gap.

The Exploration Process Is Naturally a Graph, Not a Linear Record

The research team observed a key phenomenon: the exploration process naturally forms a graph structure—different branch approaches are interconnected through revision and reconsideration. A failed attempt may be picked up again after three rounds of iteration, and the conclusion of one branch may become the premise of another. If a memory system stores conversations only in a flat timeline, this cross-branch referencing relationship is lost.

Based on this insight, the team proposed LExMem, a graph-guided benchmark specifically designed to evaluate memory capabilities in long-horizon exploration tasks. They model the exploration process as a graph and introduce an evolution mechanism to increase structural complexity, ultimately generating 224 dialogues and 2,018 question-answering instances, all derived from graph structures. This means that questions in the benchmark inherently require crossing branches and tracing revision history to be answered correctly.

Benchmark In the fields of machine learning and natural language processing, a benchmark refers to a standardized evaluation dataset and evaluation protocol used to compare the capabilities of different systems under uniform conditions. The core challenges of building a benchmark lie in ensuring the answerability of questions, the determinacy of answers, and sufficient difficulty discrimination. What makes LExMem special is that its questions are not manually written and directly paired with context; rather, they are derived from graph structures—first modeling exploration trajectories, then automatically generating question-answer pairs based on the node relationships and revision history of the graph, thereby ensuring that every question truly depends on cross-branch, cross-time memory associations rather than being solvable through single-turn local matching.

LExGraph: Weaving Conversations into Interconnected Memory Nodes

Beyond the benchmark, the team also proposed LExGraph, a graph-based memory framework. Its approach shares the same origin as the benchmark: incrementally organizing conversations into interconnected memory nodes, and acquiring evidence through hybrid retrieval and neighbor expansion.

The key to this design is "neighbor expansion"—when retrieval hits a certain memory node, the framework pulls in its associated nodes along the graph structure, thereby bringing revision chains and branch dependencies back into context together. Compared with pure vector similarity retrieval, this approach better fits the reasoning paths of exploration tasks.

Experimental results show that LExMem poses a significant challenge to existing retrieval-based and memory-based systems, while LExGraph achieves superior performance and can effectively generalize to external benchmarks. The code and dataset have been open-sourced on GitHub (mbzuai-nlp/LExMem).

Neighbor Expansion is a common strategy in graph retrieval: after initially recalling several seed nodes, it traverses one or more hops of neighbors along the edges of the graph, incorporating associated nodes into the context. Unlike vector retrieval, which relies on semantic similarity, neighbor expansion leverages explicit structural relationships, such as "which node this solution was revised from" or "which branch cited this conclusion." In exploration tasks, revision chains and branch dependencies are often not semantically similar; pure vector recall easily misses them, whereas neighbor expansion can bring back abandoned-then-reactivated solutions together with their causes and consequences as a group, giving the model a complete reasoning path rather than isolated fragments.

Hybrid Retrieval refers to a retrieval paradigm that simultaneously uses multiple recall signals and fuses the results. A common combination is dense vector retrieval with sparse keyword retrieval (such as BM25), merged through reciprocal rank fusion or weighted scoring. Its advantage lies in complementarity: vector retrieval excels at semantic generalization, while keyword retrieval excels at exact matching of proper nouns, identifiers, and rare terms. In LExGraph, hybrid retrieval is responsible for locating seeds among memory nodes, while neighbor expansion supplements structural associations on that basis, forming a two-stage evidence acquisition process of "locate first, then diffuse."

Why This Work Deserves Attention

Long-term memory is becoming a core capability bottleneck for agents and dialogue systems. Most solutions treat memory as a "fact warehouse," good at answering "what is X," but losing points on questions like "why was solution X abandoned, and who later re-adopted it." LExMem shifts the evaluation focus from fact recall to understanding exploration trajectories, filling a gap in evaluation dimensions; LExGraph provides a practical graph-based memory organization scheme.

For developers, the takeaway from this work is: when building agents that require multi-round trial and error, the topological structure of memory is as important as its content. The code and dataset have been made public and are worth further validation in real engineering scenarios.

One-line Summary

MBZUAI proposes the graph-based benchmark LExMem and the memory framework LExGraph to solve the memory challenge in long-horizon exploration tasks.

Paragraph Summary

Targeting "exploration tasks" such as scientific research and software development that require repeated trial and error, the MBZUAI NLP team points out that existing long-term memory research focuses only on fact recall and neglects the intrinsic relatedness of the exploration process. The team proposes the LExMem benchmark, which models the exploration process as a graph and introduces an evolution mechanism, generating 224 dialogues and 2,018 question-answering instances whose questions inherently require cross-branch tracing of revision history. They also propose the LExGraph memory framework, which incrementally organizes conversations into interconnected memory nodes and acquires evidence through hybrid retrieval and neighbor expansion. Experiments show that existing retrieval and memory systems struggle on LExMem, while LExGraph performs better and can generalize to external benchmarks; the code and dataset have been open-sourced.