💬 NLP

Co-Evolving Graph and Text Memory for Training-Free Multi-Hop Question Answering

The paper introduces Co-E, a training-free multi-hop question answering system that employs synchronized bidirectional working memory to dynamically integrate and reconcile textual context with relational graph evidence, achieving performance competitive with larger or trained models across six benchmarks.

Original authors: Hieu Man, Thien Huu Nguyen

Published 2026-07-28

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Hieu Man, Thien Huu Nguyen

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 you are trying to solve a massive, multi-layered mystery, like figuring out who the great-grandfather of a famous movie star is. To do this, you can't just ask one question and get one answer. You have to ask a chain of questions: "Who is the star's father?" then "Who is that father's mother?" and so on. This is what scientists call "multi-hop question answering."

For a long time, computers have tried to solve these mysteries using two main tools. The first is a giant library of text (like the internet or a huge book collection), which is great for finding stories and facts written in sentences. The second is a structured map of facts (called a Knowledge Graph), which is like a giant family tree or a subway map where everything is connected by clear lines. The problem is that these two tools usually work in separate rooms. The text finder reads a book but forgets the map, while the map reader looks at the connections but ignores the new details found in the books. This makes it hard for computers to solve complex puzzles where the answer depends on mixing a story from a book with a connection from a map.

Enter Co-E, a new system designed by researchers Hieu Man and Thien Huu Nguyen from the University of Oregon. Think of Co-E as a super-smart detective who doesn't just carry a notepad and a map separately, but keeps them in a single, magical "working memory" that updates itself every second. Instead of just reading a book and then looking at a map, Co-E constantly translates between the two. If it reads a sentence in a book that mentions a new person, it immediately draws that person onto its map. If it finds a connection on the map, it writes that connection back into its notes as a clear sentence. This "co-evolving" dance happens without the computer needing to be retrained or taught new lessons; it just uses its existing brain power to juggle both types of information at once.

The researchers tested this detective on six different puzzle sets, ranging from tricky Wikipedia riddles to complex database questions. They found that Co-E is incredibly good at solving these puzzles without any extra training. For example, on a tough test called 2WikiMultiHopQA, it got 72.6 out of 100 points (using a metric called Exact Match), and on another called Bamboogle, it scored 70.0. On a database challenge called CWQ, it hit 74.9 (using a metric called Hits@1). These scores are impressive because Co-E beats other systems that use similar-sized computer brains but don't have this special memory trick, and it even competes with much larger, more expensive systems that have been heavily trained.

The secret sauce isn't just having a big brain; it's how the system manages its memory. The researchers showed that if you stop the system from updating its map based on its notes (or vice versa), its performance drops significantly. It turns out that the key to solving these hard puzzles is keeping the text and the graph in sync, letting them fix each other's mistakes and fill in the gaps as the detective works through the mystery step by step. This suggests that for computers to get better at reasoning, they need to stop treating text and structured facts as separate worlds and start letting them talk to each other in real-time.

Technical Summary: Co-Evolving Graph and Text Memory for Training-Free Multi-Hop Question Answering

Problem Statement

Multi-hop question answering (QA) requires coordinating relational and textual evidence across multiple reasoning steps. A fundamental limitation of current paradigms is that neither a text corpus nor a knowledge graph (KG) alone can supply the necessary combination of unstructured context and structured relations. Standard Retrieval-Augmented Generation (RAG) pipelines select context before reasoning unfolds, preventing the system from updating its retrieval strategy based on intermediate discoveries (e.g., a "bridge entity" found in a passage). Conversely, graph-augmented methods often rely on pre-built or fixed subgraphs that cannot be revised during reasoning, leading to missed entities, noisy edges, and incomplete paths. Existing systems typically privilege one side of the reasoning state—either maintaining evolving textual memories or traversing fixed graph structures—but fail to reconcile graph memory with textual context within the same reasoning loop.

Methodology: The Co-E Framework

The authors propose Co-E (Co-Evolving), a training-free system designed around a synchronized, bidirectional graph-text working memory. The system operates without fine-tuning, utilizing a shared memory object $M(t) = (T(t), G(t))$ that evolves at each reasoning step $t$ .

Core Components

Shared Graph-Text Memory:
- Textual Memory ( $T$ ): Stores self-contained, question-relevant snippets, including extracted evidence, intermediate sub-answers, and natural-language statements derived from graph triples. Raw documents are filtered into atomic snippets before entering memory.
- Graph Memory ( $G$ ): A directed graph containing two types of triples:
  - KB-schema triples: Canonical relations retrieved directly from a knowledge base (e.g., Freebase, Wikidata).
  - Open-vocabulary triples: Relations extracted from textual memory using natural language labels, allowing the system to represent facts absent from the KG schema.
- Active Maintenance: The graph is not monotonically accumulated; a triple pruner removes irrelevant, redundant, or contradicted edges, and nodes resolving to the same entity are collapsed.
Bidirectional Synchronization Cycle:
At each step, Co-E executes a four-operation synchronization cycle to co-evolve the memories:
- Textual Consolidation: Deduplicates overlapping snippets, merges complementary evidence, and retracts contradicted predictions from the current textual memory $T(t)$ and new snippets $S(t)$ .
- Text-to-Graph Propagation: Identifies entities in the consolidated text, maps them to KB identifiers, and extracts open-vocabulary triples. These are merged into $G(t)$ , expanding the relational frontier based on textual discoveries.
- Graph-to-Text Propagation: Textualizes surviving graph triples and injects them back into $T(t)$ as explicit relational statements. This ensures the generator has direct access to graph constraints in natural language.
- Textual Re-consolidation: A second pass over the textual memory to reconcile the injected graph facts, producing a coherent state $M(t+1)$ for the next step.
Dual-Stream Retrieval:
- Corpus Retrieval: Generates search queries conditioned on the current memory to retrieve text snippets.
- Graph Retrieval: Uses the current memory to seed $k$ -hop SPARQL queries. The seed set is augmented with entities already present in $G(t)$ , making retrieval memory-conditioned rather than a fixed traversal.
Reasoning Modes:
- MCTS Mode: Uses Monte Carlo Tree Search to explore multiple reasoning trajectories (sub-questions, self-correction, synthesis). A verifier scores candidate states, and feedback is used to prune weak branches and update the shared memory.
- CoT Mode: Follows a sequential chain of reasoning, applying the same synchronization operator at each step without tree expansion.

Key Contributions

Synchronized Bidirectional Memory: Co-E introduces a mechanism where textual evidence expands the graph frontier and graph facts reshape the textual context within the same reasoning loop, addressing the limitation of static or unidirectional memory systems.
Training-Free Architecture: The system achieves strong performance without fine-tuning the backbone LLM, relying instead on the synchronization of retrieved evidence and structured memory.
Active Memory Maintenance: Unlike systems that merely accumulate context, Co-E actively prunes, deduplicates, and reconciles contradictions in both modalities, preventing the accumulation of noisy or stale information.

Experimental Results

Co-E was evaluated on six benchmarks spanning KGQA (WebQSP, CWQ) and multi-hop text-QA (2WikiMultiHopQA, HotpotQA, MuSiQue, Bamboogle) using a Qwen3-8B backbone.

KGQA Performance:
- On CWQ, Co-E (MCTS) achieved 74.9 Hits@1, outperforming trained systems like RoG (62.6) and ReKG-MCTS (59.8), and surpassing the previous best open-source baseline, PoG (74.7).
- On WebQSP, Co-E (MCTS) reached 85.5 Hits@1, competitive with the strongest open-source trained baselines (RoG and GNN-RAG at 85.7).
Text-QA Performance:
- On 2WikiMultiHopQA, Co-E (MCTS) achieved 72.6 EM, improving over comparable open-backbone baselines by significant margins (e.g., +10.7 over SubQRAG).
- On Bamboogle, Co-E (MCTS) reached 70.0 EM, outperforming Search-R1 (43.2) and PAGER (62.4).
- On MuSiQue, Co-E (MCTS) achieved 52.5 EM, outperforming HopRAG-GPT-4o by 10.3 points.
Ablation Studies:
- Removing bidirectional synchronization caused a significant drop in performance (e.g., MCTS EM on Bamboogle dropped from 70.0 to 61.1), confirming that both propagation directions are necessary.
- Removing either graph or textual memory individually degraded performance, supporting the necessity of paired modalities.
- Active maintenance (pruning/consolidation) was shown to be critical; without it, performance dropped to 49.5 EM.

Significance and Claims

The paper claims that Co-E demonstrates that graph-text co-evolution is a practical mechanism for training-free multi-hop reasoning. The authors argue that the central challenge in multi-hop QA is maintaining a reasoning state where textual evidence and relational structure revise each other dynamically.

Key claims include:

Superiority over Static Graphs: Co-E outperforms systems relying on pre-built or fixed topic-centered subgraphs, particularly on datasets requiring long relation chains (CWQ, MuSiQue) where maintaining a dynamic relational state is crucial.
Competitiveness with Trained Systems: Despite being training-free and using an 8B parameter backbone, Co-E competes with or exceeds larger (e.g., 32B, 70B) or supervised fine-tuned systems.
Robustness in Open-Domain Settings: In a stress test using full Wikidata (without benchmark-specific subgraph preprocessing), Co-E retained strong performance, reducing Hits@1 on CWQ by only 1.5 points compared to the topic-subgraph protocol.
Limitations: The authors acknowledge that Co-E is limited by the quality of retrieved evidence. If the corpus consistently supports an incorrect fact, synchronization cannot correct it. Additionally, errors in entity linking and incomplete reasoning chains remain challenges.

The paper concludes that synchronized working memory allows the system to revise its relational state during inference, offering a robust alternative to static retrieval or fixed graph traversal for complex reasoning tasks.