Source-linked AI summary
Walking Down the Memory Maze: Beyond Context Limit through Interactive Reading
Howard Chen, Ramakanth Pasunuru, Jason Weston, Asli Celikyilmaz
TL;DR
Long-text question answering remains difficult because finite context windows limit processing of long sequences despite extensions through positional embeddings, recurrence, and retrieval. MEMWALKER instead builds a tree of summary nodes and interactively navigates it with iterative prompting, outperforming recurrence, retrieval, vanilla LLM, and other open long-context systems on three question answering tasks. The method also exposes navigation reasoning and relevant text segments, but its scaling, reasoning-capability, and zero-shot prompting limitations remain.
Problem
Finite context windows limit long-text understanding, while existing positional-embedding, recurrence, and retrieval approaches remain limited by design.
Method
MEMWALKER builds a hierarchy of summary nodes from long text and interactively navigates it with iterative LLM prompting to find query-relevant segments.
Results
MEMWALKER outperforms recurrence, retrieval, vanilla LLM, and other open long-context systems across three long-context question answering tasks.
Takeaways & Limitations
Interactive reading lets MEMWALKER process beyond the context limit while localizing relevant segments and exposing navigation reasoning.
Takeaways & Limitations
MEMWALKER may scale poorly to extremely long sequences, depends on strong reasoning capability, and uses zero-shot prompting without fine-tuning.
Abstract
from arXiv · showhide
Large language models (LLMs) have advanced in large strides due to the effectiveness of the self-attention mechanism that processes and compares all tokens at once. However, this mechanism comes with a fundamental issue -- the predetermined context window is bound to be limited. Despite attempts to extend the context window through methods like extrapolating the positional embedding, using recurrence, or selectively retrieving essential parts of the long sequence, long-text understanding continues to be a challenge. We propose an alternative approach which instead treats the LLM as an interactive agent, allowing it to decide how to read the text via iterative prompting. We introduce MemWalker, a method that first processes the long context into a tree of summary nodes. Upon receiving a query, the model navigates this tree in search of relevant information, and responds once it gathers sufficient information. On long-text question answering tasks our method outperforms baseline approaches that use long context windows, recurrence, and retrieval. We show that, beyond effective reading, MemWalker enhances explainability by highlighting the reasoning steps as it interactively reads the text; pinpointing the relevant text segments related to the query.
1 INTRODUCTION
Long-text understanding is constrained by finite context windows, motivating MEMWALKER’s interactive approach to organizing and navigating long documents. The method builds a summary tree, then uses iterative prompting to locate relevant segments and achieves superior performance across long-context question answering tasks.
- Motivation: Longer-input understanding matters for information retrieval, legal and scientific document analysis, and extended conversational dialogues.These applications motivate the demand for processing larger amounts of context.
- Motivation: MEMWALKER treats a finite-context LLM as an interactive agent that decides how to read long text through iterative prompting.This differs from processing the entire sequence in one pass.
- Method: The method navigates summary nodes to identify relevant text segments and can revert to a parent node after choosing an irrelevant or incorrect path.Navigation decisions are made by reasoning about child summaries and selecting an action.
- Method: MEMWALKER builds a memory tree by segmenting long text, summarizing segments, and recursively summarizing those nodes into higher-level nodes.The model then navigates the tree from its root in response to a query.
- Results: MEMWALKER outperforms recurrence, retrieval, vanilla LLM, and other open long-context systems across three long-context question answering tasks.The reported analysis also examines navigation reasoning, working memory, and recovery from early navigation errors.
2 RELATED WORK
Prior approaches extend long-context processing through modified attention, positional-embedding extrapolation, recurrence, or retrieval, but each retains important limitations. These limitations motivate alternative approaches for handling long sequences.
- Context window scaling: Context-window scaling methods modify attention or positional embeddings, but may require fine-tuning and become less effective because of positional biases on very long sequences.Modified attention can reduce memory usage, while positional-embedding methods extend pretrained models to longer inputs.
- Recurrence: Recurrence can lose information at each step because its training objective does not specify how to compress content for downstream tasks.The passage notes that older information is therefore typically recalled more weakly.
- Retrieval: Retrieval methods embed text segments and select them using the query rather than feeding the entire sequence into the model.Examples include Fusion-in-Decoder and kNN-style external-memory variants.
- Reasoning agents: Reasoning-agent systems support interactive search, but the cited agents were not designed to understand long, coherent texts.Their atomic actions enable interactive content search rather than the targeted reading of a coherent long document.
3 MEMWALKER: AN INTERACTIVE READER
MEMWALKER constructs a query-independent hierarchy of textual summaries and uses an LLM to navigate it interactively for question answering. Navigation combines child-summary inspection, reversible actions, leaf-level answering, and optional working memory.
- Memory tree construction: MEMWALKER first constructs a tree from long text by summarizing segments and recursively summarizing groups of nodes up to a root.The construction is performed through iterative LLM prompting and can be computed before a query is received.
- Navigation: An example trajectory shows the model entering child summaries, reverting when a leaf lacks sufficient information, and eventually committing to an answer leaf.The trajectory illustrates back-and-forth navigation rather than a single irreversible path.
- Navigation: Given a query, the LLM starts at the root and chooses child nodes or reverts to the parent while navigating toward relevant content.At a leaf, it either commits to the segment and answers or returns upward if the information is insufficient.
- Navigational prompt design: Zero-shot triage prompts present the query and child summaries, while leaf prompts present the segment content and request an answer or reversion.Both prompt types specify the required output format for navigation.
- Working memory: Working memory lets the LLM retain contents from previously visited nodes during traversal, subject to the context-window limit.The retained trajectory information is inserted into subsequent prompts.
4 EXPERIMENTAL SETUP
The evaluation measures accuracy on three long-context question answering datasets, including subsets with especially long inputs. MEMWALKER is compared with long-context, recurrence, and retrieval baselines using a 4,096-token underlying model context.
- Datasets & evaluation: The study evaluates accuracy on QuALITY, SummScreenFD, and GovReport, using both original datasets and longer-sequence subsets.The long-input thresholds are above 8,000, 6,000, and 12,000 tokens respectively.
- Datasets & evaluation: QuALITY contributes 187 multiple-choice examples based on long-form Project Gutenberg stories and human-annotated questions.The experiments use a subset of the dataset.
- Datasets & evaluation: SummScreenFD is repurposed from dialogue scripts into 306 question-answering examples using generated who questions checked by a human expert.Its original task was summarization.
- Limitations: The evaluation includes an unexamined alternative of further summarizing accumulated working memory as it grows.The paper identifies this as an alternative approach rather than an evaluated component.
- Model & baselines: The main comparison uses full-context, recurrence, and retrieval baselines alongside MEMWALKER, with the shared Stable Beluga 2 model limited to 4,096 tokens.Full-context baselines truncate either the left or right side of overlength inputs.
5 RESULTS & ANALYSIS
MEMWALKER outperforms baselines most clearly on longer contexts, while its effectiveness depends on reasoning, working memory, and navigational recovery. Analyses also show that it can read less text, with construction choices creating a performance trade-off.
- Main results: MEMWALKER outperforms recurrence, retrieval, and full-context baselines on the Long versions of all three tasks.It also exceeds other publicly available long-context systems, while advantages are weaker or absent on shorter sequences.
- Reasoning capability: Reasoning improves navigation for Stable Beluga 2 but reduces accuracy and valid actions for weaker underlying language models.The comparison varies both model reasoning capability and whether navigation decisions include explicit justifications.
- Performance by context length: MEMWALKER surpasses both left- and right-truncated full-context baselines for longer sequences, after the input exceeds the 4,096-token context length.The advantage does not appear when text is short.
- Working memory: Removing working memory lowers accuracy by 5–13% across all tasks.Working memory preserves information from nodes traversed along the current navigation path.
- Navigation recovery: When MEMWALKER reverts from stray paths, it recovers correct answers in 70% of QuALITY, approximately 60% of SummScreenFD, and approximately 80% of GovReport cases.Revert navigation occurs for around 15–20% of examples.
- Reading efficiency and construction trade-offs: MEMWALKER reads 63–69% of the original text on average, falling to 59–64% among successful paths.Tree construction also trades off information fidelity and navigation difficulty as segment sizes and branching increase.
6 CONCLUSION
MEMWALKER is an interactive reading agent that builds structured memory from long contexts and navigates relevant parts through iterative prompting. It outperforms several baselines, particularly on longer sequences, while supporting navigation reasoning, path recovery, and working memory.
- 6 CONCLUSION: MEMWALKER uses iterative prompting to decide which parts of a long context to read closely after building structured memory.The method separates memory construction from query-dependent navigation.
- 6 CONCLUSION: MEMWALKER shows superior performance against long-context, retrieval, and recurrence baselines, especially on longer-sequence tasks.
- 6 CONCLUSION: Analysis identifies navigation reasoning, recovery from an alternative path, and working-memory incorporation as important factors.
- 6 CONCLUSION: Future work includes applying MEMWALKER to data structures other than trees and fine-tuning it for interactive reading.
7 LIMITATIONS
MEMWALKER’s limitations concern scalability, dependence on sufficiently capable instruction-tuned models, and the absence of fine-tuning for interactive reading.
- 7 LIMITATIONS: Memory-tree construction may become onerous as sequence length increases because longer inputs create more nodes.The authors suggest trading summary granularity for speed or exploring alternative data structures, but scaling remains limited.
- 7 LIMITATIONS: MEMWALKER requires strong reasoning capability, which the experiments associate with large, over-70B, instruction-tuned models.If reasoning capability is insufficient, errors compound and the method fails.
- 7 LIMITATIONS: MEMWALKER uses zero-shot prompting and does not fine-tune the model to improve interactive reading.The authors propose collecting successful interactive-reading paths for future fine-tuning.
A.1 PROMPTS
The appendix provides the prompts used to construct memory trees and navigate them. Construction summarizes leaf segments and then recursively summarizes grouped child summaries, while navigation uses separate triage and leaf prompts.
- A.1 PROMPTS: The appendix supplies full prompts for both memory-tree construction and navigation.
- A.1.1 MEMORY TREE CONSTRUCTION PROMPTS: Memory-tree construction uses a leaf prompt to produce a comprehensive summary of each text segment.
- A.1.1 MEMORY TREE CONSTRUCTION PROMPTS: Grouped child summaries are concatenated into parent-node content and summarized into non-leaf summaries.
- A.1.1 MEMORY TREE CONSTRUCTION PROMPTS: The construction prompts summarize segments into leaf nodes before progressively forming higher-level summaries.
- A.1.2 NAVIGATION PROMPTS: Navigation uses two prompts: triage for non-leaf nodes and leaf for segment-level answering or returning to the parent.
- A.1.2 NAVIGATION PROMPTS: The appendix presents a general navigation prompt template alongside the construction prompts.
A.2 EXAMPLES
The appendix provides additional prompt and trajectory examples illustrating MEMWALKER’s construction and navigation behavior.
- A.2 EXAMPLES: An additional navigation example is provided in the appendix.
- A.2 EXAMPLES: Table 5 lists prompts for memory-tree construction and navigation, including segment text, child summaries, queries, and options.
- A.2 EXAMPLES: Table 6 presents an example navigation trajectory from the SummScreenFD dataset.