PaperlayerView exact revision on arXiv

Source-linked AI summary

HGMEM: Hypergraph-based Working Memory to Improve Multi-step RAG for Long-Context Complex Relational Modeling

Chulun Zhou, Chunkang Zhang, Guoxin Yu, Fandong Meng, Jie Zhou, Wai Lam, Mo Yu

arXiv:2512.23959v3cs.CLcs.AIcs.LG

TL;DR

Multi-step RAG working memories often store isolated facts without capturing higher-order relations needed for global sense-making across long contexts. HGMEM uses an evolving hypergraph to integrate facts and thoughts into memory units, and the paper reports consistent improvements over strong RAG baselines across challenging benchmarks.

  • Problem

    Existing multi-step RAG memories often store primitive facts without integrating higher-order correlations, limiting support for global sense-making across long contexts.

    Source: §1 · pp. 1–2

  • Method

    HGMEM represents working memory as an evolving hypergraph whose hyperedges are distinct memory points that progressively integrate higher-order relations among facts.

    Source: §1 · p. 2, §3.3 · p. 4

  • Results

    Across challenging global sense-making benchmarks, HGMEM consistently outperforms strong RAG baselines, and Qwen2.5-32B-Instruct matches or exceeds GPT-4o-powered baselines.

    Source: §1 · p. 2, §5.1 · p. 6, §6 · p. 9

  • Takeaways & Limitations

    The analysis links improved accuracy on sense-making queries to high-order correlations, evidenced by hyperedges connecting significantly more entities.

    Source: §1 · p. 2

    The problem setting assumes the document has been preprocessed into a graph with entities and relationships extracted from its passages.

    Source: §3.1 · p. 3

Abstract

from arXiv · show

Multi-step retrieval-augmented generation (RAG) has become a widely adopted strategy for enhancing large language models (LLMs) on tasks that demand global comprehension and intensive reasoning. Although many RAG systems incorporate a working memory to consolidate information, existing designs primarily function as a passive storage for isolated facts. This static nature overlooks crucial high-order correlations among primitive facts, thereby limiting models' capacity for multi-step reasoning and resulting in fragmented reasoning and weak global sense-making within extended contexts. We introduce HGMem, a hypergraph-based working memory system, extending the concept of memory beyond simple storage into a dynamic, expressive structure for complex reasoning and global understanding. In our approach, memory is represented as a hypergraph where hyperedges correspond to distinct memory units, enabling the progressive formation of high-order interactions within memory. This mechanism connects facts and thoughts around the focal problem, evolving the memory into an integrated and situated knowledge structure that provides strong propositions for deeper reasoning. We evaluate HGMem on several challenging global sense-making benchmarks. Extensive experiments and in-depth analyses demonstrate that our method consistently improves multi-step RAG and substantially outperforms strong baseline systems across diverse datasets.

1. Introduction

HGMEM addresses the limits of static fact storage by using an evolving hypergraph to organize higher-order relations for long-context reasoning. The paper reports consistent gains over strong multi-step RAG baselines, including Qwen2.5-32B-Instruct matching or exceeding GPT-4o-powered baselines.

1. Introduction

  • Existing memory mechanisms accumulate primitive facts but lack the capacity to integrate them, leaving LLMs with fragmented views of complex long-context relationships.The paper notes that long lists of facts can be inefficient and confusing when mixed with irrelevant information.Source: §1 · pp. 1–2
  • HGMEM represents working memory as a hypergraph whose hyperedges act as memory points and progressively integrate higher-order correlations through update, insertion, and merging.The LLM uses current memory to generate adaptive subqueries for local investigation or broad global exploration.Source: §1 · p. 2
  • The structured memory synthesizes primitive evidence and intermediate thoughts into propositions that guide later reasoning and hypergraph-topology-guided retrieval.This can provide a global perspective beyond predefined schemas.Source: §1 · p. 2
  • HGMEM consistently outperforms strong multi-step RAG baselines on challenging global sense-making benchmarks, while its Qwen2.5-32B-Instruct version matches or exceeds GPT-4o-powered baselines.The paper reports these results across diverse datasets.Source: §1 · p. 2

2. Related Work

Prior multi-step RAG work uses evolving records and graph memories, but ordinary graph edges remain limited to binary relations. Structured knowledge indices support retrieval over extended corpora, while HGMEM's hypergraph memory evolves around the query.

2.1. Working Memory Mechanisms for Multi-step RAG

  • Earlier multi-step RAG systems consolidate observations or reasoning records, while graph-based memories such as ERA-CoT and KnowTrace remain limited to binary relations.HGMEM instead models n-ary relations with dynamically evolving hypergraphs.Source: §2.1 · p. 2

2.2. RAG with Structured Knowledge Index

  • Structured indices include tree- and graph-based approaches for organizing extended corpora, but are typically built offline and lack query-specific adaptation.HGMEM's workflow retrieves entities and associated relations or text from subqueries, then evolves its memory.Source: §2.2 · pp. 2–3

3. HGMem

HGMem models working memory as a hypergraph and evolves it during multi-step retrieval and reasoning. Its memory supports complex relational modeling by linking entities and evidence in higher-order memory units.

3.1. Problem Formulation

  • The document is assumed to be preprocessed into a graph of entities and relationships linked to their source text chunks.The LLM can access both the document and its derived graph as structured data sources.Source: §3.1 · p. 3

3.2. Methodology Overview

  • At each step, the LLM judges whether memory is sufficient; if not, it generates subqueries, retrieves entities and their associated relationships and text, then consolidates that information into memory.The target query serves as the initial subquery.Source: §3.2 · p. 4

3.3. Hypergraph-based Memory Storage

  • Memory is a hypergraph whose vertices represent entities and whose hyperedges represent relationship descriptions linked to participating vertices, allowing one memory unit to connect two or more vertices.Unlike binary graph edges, hyperedges can model higher-order correlations among multiple vertices.Source: §3.3 · p. 4

3.4. Adaptive Memory-based Evidence Retrieval

  • When memory is insufficient, adaptive retrieval either investigates a specific memory point through its subordinate vertices or explores aspects beyond the current memory’s scope.Both routes retrieve associated relationships and text chunks before memory is evolved.Source: §3.4 · pp. 4–5

3.5. Dynamics of Memory Evolving

  • Memory evolves through updating existing points, inserting new ones, and merging semantically or logically cohesive points into higher-order units.Merging builds high-order correlations among memory points; memory thus captures increasingly sophisticated relationships as interactions continue.Source: §3.5 · p. 5

3.6. Memory-enhanced Response Generation

  • A response is produced when the interaction-step limit is reached or memory is deemed sufficient, using memory-point descriptions and associated entity text chunks.The response is generated from the information in current memory.Source: §3.6 · p. 5

4. Experimental Settings

The evaluation covers generative sense-making QA and long-narrative understanding. The setup specifies shared retrieval constraints for baselines and metrics tailored to each task type.

4.1. Datasets

  • The evaluation uses generative sense-making QA on documents exceeding 100k tokens and three long-narrative benchmarks: NarrativeQA, NoCha, and Prelude.GPT-4o generates global queries for the sense-making task.Source: §4.1 · p. 6

4.2. Implementation Details

  • Implementation segments documents into 200-token chunks with 50-token overlap, builds shared graphs for graph-based methods, and uses GPT-4o or Qwen2.5-32B-Instruct as backbones.bge-m3 supplies vector representations; inference uses temperature 0.8 and a 2,048-token maximum.Source: §4.2 · p. 6

4.3. Baselines and Evaluation Metrics

  • Baselines retrieve comparable numbers of chunks, while multi-step baselines also share limits on subquery rewrites, execution steps, and chunks per step.Sense-making responses are scored for comprehensiveness and diversity; narrative tasks use prediction accuracy, with GPT-4o judging entailment for NarrativeQA.Source: §4.3 · p. 6

5. Results and Analysis

HGMEM outperforms single- and multi-step RAG baselines across the evaluation datasets, while tests examine its performance over turns, memory operations, query types, and offline graph quality. Results associate larger hyperedges with improved accuracy on sense-making queries, and show the framework retains an advantage with altered offline graphs.

5.1. Overall Results

  • HGMEM consistently outperforms single-step and multi-step RAG baselines across all evaluation datasets.With Qwen2.5-32B-Instruct, it matches or outperforms baselines powered by GPT-4o.Source: §5.1 · p. 6, Table 1 · p. 7

5.2. Performance at Different Steps

  • HGMEM performs best at t=3 on long narrative understanding tasks, while additional steps bring no further improvement at higher cost.The comparison uses Qwen2.5-32B-Instruct; t=0 is the initial retrieval step.Source: Figure 3 · p. 7, §5.2 · p. 7

5.3. Ablation Studies

  • Adaptive evidence retrieval outperforms using only Local Investigation or only Global Exploration, and removing update or merging lowers performance.Removing merging causes a substantially larger degradation than removing update.Source: §5.3 · pp. 7–8

5.4. Dissecting Query Resolving: Primitive vs. Sense-making

  • On sense-making queries, HGMEM has higher accuracy and larger average hyperedge size than HGMEM without merging; primitive-query accuracy is comparable or slightly lower.Average hyperedge size is consistently greater for sense-making than primitive queries, especially with merging.Source: Table 3 · p. 8, §5.4 · p. 8

5.5. Sensitivity to Offline Graph

  • HGMEM retains a significant performance advantage with a graph missing 50% of entities and relationships or one built using Stanford OpenIE.Offline graph quality affects performance, but HGMEM is described as moderately sensitive to the initial graph compared with other methods.Source: Table 4 · p. 9, §5.5 · p. 9

6. Conclusion

HGMEM represents working memory as a hypergraph whose hyperedges are separate memory points. As multi-step RAG proceeds, memory builds high-order correlations among facts to guide reasoning about a focal problem.

6. Conclusion

  • HGMEM structures working memory as a hypergraph composed of separate memory points represented by hyperedges.The system aims to support complex relational modeling in multi-step RAG.Source: §6 · p. 9
  • During multi-step RAG, HGMEM progressively establishes high-order correlations among accumulated primitive facts.These correlations help organize and connect thoughts around a focal problem.Source: §6 · p. 9
  • Experiments and analyses validate HGMEM against strong RAG baselines on challenging datasets with global sense-making questions over long contexts.Source: §6 · p. 9

Impact Statement

The paper presents HGMEM as a way to model high-order correlations in multi-step RAG over long contexts. It links this approach to global sense-making applications and reports that structured memory can help open-source models match proprietary ones.

Impact Statement

  • HGMEM enhances multi-step RAG by modeling high-order correlations within long contexts.Source: Impact Statement · p. 9
  • The paper identifies scientific literature review, legal case analysis, and narrative understanding as applications requiring scattered evidence to be synthesized into integrated insights.Source: Impact Statement · p. 9
  • The findings indicate that open-source models equipped with structured memory can match proprietary models.The paper connects this possibility with accessible and sustainable AI development.Source: Impact Statement · p. 9

A. Dataset Statistics

The experiments cover generative sense-making QA and long narrative understanding. The dataset statistics are organized by document count, average tokens per document, and query count.

A. Dataset Statistics

  • Table 5 reports the number of documents, average tokens per document, and total queries for the experimental data.Source: Table 5 · p. 12, A. Dataset Statistics · p. 12
  • Generative sense-making QA uses documents over 100k tokens from Longbench V2 in the Financial, Government, and Legal domains.Source: A. Dataset Statistics · p. 12
  • Long narrative understanding uses NarrativeQA, NoCha, and Prelude, which test story synthesis, global claim understanding, and consistency between a character’s prequel and original story.The evaluation uses 10 long NarrativeQA books, the publicly released NoCha subset, and all English books in Prelude.Source: A. Dataset Statistics · p. 12

B. Detailed Implementation Settings

The appendix specifies HGMEM's runtime retrieval settings, hardware and baseline controls, comparison methods, pseudocode, and supplementary-results scope.

B.1. Retrieval Dynamics and Hyperparameters

  • HGMEM retrieves up to 20 entities per sub-query, expands at most 5 relationships per entity, retrieves Top-k = 10 chunks in each evidence mode, and caps aggregation at 50 chunks.These settings balance structural recall with context efficiency and limit noise propagation.Source: §B.1 · p. 12

B.2. Hardware Infrastructure

  • Experiments ran on NVIDIA A100 (80GB) GPUs interconnected via NVLink, using PyTorch 2.1.0 and vLLM 0.11.2.Source: §B.2 · p. 13

B.3. Baseline Reproducibility

  • Baselines use official open-source implementations; GraphRAG and LightRAG share HGMEM's graph, while DeepRAG and ComoRAG use a maximum of three reasoning steps.These controls support reproducibility and align comparison conditions.Source: §B.3 · p. 13

C. Comparison Baselines

  • NaiveRAG retrieves chunks directly; GraphRAG builds entity communities, LightRAG uses dual-level graph retrieval, and HippoRAG v2 applies Personalized PageRank with dense-sparse integration.Source: C. Comparison Baselines · p. 13
  • DeepRAG iteratively decomposes queries as a Markov Decision Process, while ComoRAG probes external sources and integrates retrieved evidence into a dynamic global memory pool.Source: C. Comparison Baselines · p. 13

D. Pseudocode of HGMEM

  • Algorithm 1 formalizes HGMEM's control flow, including dynamic search-space selection and memory evolution through update, insertion, and merging.The LLM synthesizes semantic descriptions for high-order correlations; execution stops at the maximum steps or when memory is sufficient to answer.Source: D. Pseudocode of HGMEM · p. 13

E. More Experiment Results

E.1. Comparison with Several Recent Related Methods

HGMEM outperforms additional working-memory and hypergraph baselines, with reported online costs comparable to other working-memory systems; a toy example illustrates its evolving-memory workflow.

E.1. Comparison with Several Recent Related Methods

  • HGMEM outperforms working-memory methods KnowTrace and A-Mem and hypergraph method PropRAG on Qwen2.5-32B-Instruct.Table 6 presents the accuracy comparison; the supplied text does not report individual table values.Source: §E.1 · p. 14, Table 6 · p. 14
  • KnowTrace and A-Mem use linear buffers, while PropRAG uses hypergraphs as static retrieval storage; HGMEM instead evolves its hypergraph during reasoning.The authors attribute HGMEM's situated guidance to constructing integrated structures and forming high-order correlations.Source: §E.1 · p. 14

E.2. Cost Comparison

  • HGMEM's online token consumption and inference latency are reported as roughly comparable to DeepRAG and ComoRAG, while its performance is consistently better.The authors report that merging adds only minor computational overhead; Table 7 reports average tokens and latency.Source: §E.2 · p. 15, Table 7 · p. 15

F. A Toy Example

  • In the toy workflow, retrieved evidence becomes structured memory, memory-based subqueries seek missing reasoning elements, and update, insertion, and merging integrate new evidence before answering.The resulting representation includes high-order memory points beyond the source texts' surface content.Source: F. A Toy Example · p. 15

G. Case Study

Two illustrative cases contrast HGMEM's evolving-memory reasoning with baseline errors: it infers Xodar's enslavement cause and checks a misleading claim about White Sands. The appendix also shows memory-evolution and subquery prompts.

G. Case Study

  • For NarrativeQA, HGMEM links Xodar's punishment to his defeat by Carter, while LightRAG makes a surface-level prediction and DeepRAG fails to form the needed high-order correlation.Source: G. Case Study · p. 15
  • For Nocha, HGMEM investigates whether Anne named White Sands and finds no clear supporting evidence; LightRAG accepts the misleading claim and DeepRAG does not qualify it.Source: G. Case Study · p. 15

H. Prompts for Memory Evolving

I. Prompts for Subquery Generation

  • HGMEM first raises concerns about memory points or information outside memory, then generates corresponding subqueries for external retrieval.Source: §I · p. 17

J. Evaluation Prompts for Generative Sense-making QA

For generative sense-making QA, GPT-4o assesses response comprehensiveness and diversity, assigning a final score within the corresponding level's range.

J. Evaluation Prompts for Generative Sense-making QA

Related papers

Loading 2512.23959v3…