Source-linked AI summary
GraphMemix: Query-Aware Evidence Forests for Long-Term Multimodal Agent Memory
Geng Li, Yuhao Wang, Dong Li, Jianye Hao, Yuxin Peng
TL;DR
Long-term multimodal memory must avoid costly question-agnostic preprocessing and incomplete or redundant similarity-based retrieval. GraphMemix constructs a query-aware evidence forest by expanding candidate graphs, verifying node and relation utility, and optimizing a budgeted forest. Across four benchmarks and different reader families, it improves answer quality while occupying the empirical time-accuracy Pareto frontier.
Problem
Long-term multimodal memory must retrieve precise, complementary context from large heterogeneous archives without relying on costly question-agnostic summaries or similarity-only selection.
Method
GraphMemix builds a bounded query-relevant candidate graph, separately evaluates direct node support and anchor-conditioned relation value, and jointly selects an evidence forest under a memory budget.
Results
GraphMemix outperforms the strongest public result in Judge Accuracy on all four benchmarks, reaching a four-dataset macro-average of 61.55% versus UniversalRAG’s 49.80%.
Takeaways & Limitations
GraphMemix recovers low-similarity complementary evidence while suppressing redundant or conflicting information and reducing lifecycle cost through query-relevant subgraph reasoning.
Abstract
from arXiv · showhide
Organizing long-term memory for multimodal agents remains challenging because existing methods either suffer from expensive question-agnostic offline summaries or naive embedding similarity matching that introduces incomplete and redundant context. To address these issues, we propose GraphMemix, a combinatorial-optimization graph memory framework that models memory organization as query-aware evidence-forest construction. Specifically, our method consists of three key components:(1) candidate graph construction, which expands multi-view seed memories through schema and semantic relations to acquire query-aware original context; (2) evidence utility and activation costs, which decouples direct memory support from anchor-conditioned relation verification to suppress redundant or conflicting information; and (3) forest optimization, which jointly selects a forest-format memory context under a maximum evidence budget and its reliable relational structure. By organizing memory into a query-relevant subgraph, the method avoids substantial lifecycle cost and recovers low-similarity complementary evidence. Experimental results across four long-term multimodal memory benchmarks demonstrate significant improvements with different foundation models and establish a new Pareto frontier between accuracy and lifecycle cost.
1 Introduction
Multimodal agent memory must preserve diverse, continuously updated user data while retrieving precise, query-relevant context. GraphMemix addresses this by reconstructing a query-conditioned evidence forest from memory archives.
- 1 Introduction: Multimodal agents must maintain interaction consistency while incorporating large, heterogeneous collections of user-centric data.Examples include photo albums, emails, chat logs, and work documents.
- 1 Introduction: Existing memory systems commonly preprocess histories into summaries, typed fields, linked notes, or other reusable representations before future questions arrive.These approaches include episodic, semantic, procedural, and knowledge-vault memories, shared multimodal records, and linked structured notes.
- 1 Introduction: Question-agnostic preprocessing does not account for the future question when compressing history.The supplied passage identifies the absence of future-question information as a limitation of these methods.
- 1 Introduction: GraphMemix reconstructs a bounded, query-relevant evidence forest after the question arrives using multi-view anchors, relation expansion, and joint node-edge selection.Nodes represent direct memory utility, while edges represent anchor-conditioned incremental value; reliable relations are selected with relevant memories.
2 Related Work
Prior long-term memory systems establish persistent writing, organization, and controlled retrieval, while multimodal systems make heterogeneous records jointly searchable. GraphMemix instead reconstructs a query-conditioned evidence subgraph to retain structural context while reducing lifecycle overhead.
- 2 Related Work: Persistent-memory systems write observations, synthesize reflections, manage hierarchical storage, or organize new experiences into linked structured notes.These systems primarily operate on textual experiences or textualized memory units.
- 2 Related Work: Multimodal memory systems jointly search text and images using non-parametric memory, captions, OCR, metadata, multimodal similarity, or unified schemas.Examples include MuRAG, Pensieve, MIRIX, and SGM.
- 2 Related Work: Some multimodal approaches connect semantic indices or editable memories back to original media logs.AUGUSTUS and M2A preserve links to source records while organizing stored memories.
- 2 Related Work: Existing approaches can require lengthy preprocessing or lose structural context from stored memories.GraphMemix conditions evidence-subgraph reconstruction on each query rather than relying solely on prior organization.
- 2 Related Work: Query-conditioned retrieval methods adapt memory access to the current information need, including missing information, temporal constraints, causal relations, and multi-turn coreference.The cited examples include MemGuide, MemReranker, and listwise comparison methods in general retrieval.
3 Method
GraphMemix formulates query-conditioned multimodal memory selection as evidence-forest optimization over a bounded candidate graph. It combines multi-view retrieval, direct and anchor-conditioned evidence judgments, and forest optimization to select complementary context under a budget.
- Problem formulation: GraphMemix models long-term multimodal memory organization as query-conditioned forest optimization over a bounded candidate graph.The selector chooses evidence nodes and their reliable relational structure for each question.
- Candidate graph construction: Multi-view retrieval seeds candidates from original images, captions, OCR, and video frames, then expands through schema and semantic relations within bounded hops.The expansion preserves local context while limiting subsequent semantic reasoning.
- Evidence utility: A listwise node verifier estimates independent question support while retrieval similarity supplies a global prior.The fusion balances retrieval and conditional judgment through scaling and offset parameters.
- Evidence utility: The Evidence-Chain Verifier assigns anchor-conditioned candidate roles and retains only positive edges marked as new facts, clarifications, or corroborations.Redundant, conflicting, and irrelevant relations receive no structural reward.
- Activation costs and forest structure: Independent-chain costs penalize disconnected evidence components, while nonnegative edge costs allow an optimal selected structure to be a forest.The resulting objective protects trusted complementary evidence while removing low-utility isolated memories.
- Forest optimization: The deterministic solver first reaches a fixed-cardinality 1-swap local optimum with exact Kruskal recomputation, then solves variable cardinality exactly over the proposal.Optimization behavior is audited over 6,592 questions, and the method is evaluated in end-to-end and evidence-accessibility tables.
4 Experiments
GraphMemix is evaluated on four multimodal memory benchmarks against text, structured, and multimodal retrieval baselines. It improves answer quality, recovers complementary evidence, and reduces lifecycle cost through query-conditioned forest optimization.
- Experimental setup: The experiments cover ATM-Bench, Mem-Gallery, MemEye, and H2HMem, using LLM-as-a-Judge plus benchmark-native metrics and evidence-selection diagnostics.Baselines use the same reader for final answering.
- Main results: 61.55% macro-average Judge Accuracy exceeds UniversalRAG by 11.75 percentage points with Qwen3-VL-8B-Instruct across all four benchmarks.Native metrics include 53.83 ATM EM, 36.76 Gallery EM, 54.25 MemEye MCQ EM, and 54.70 H2H lexical Recall.
- Main results: 67.42% macro-average Judge Accuracy exceeds UniversalRAG by 12.33 percentage points under Gemma 4 12B Unified.The gains transfer across foundation models and heterogeneous memory benchmarks.
- Lifecycle cost: GraphMemix shortens complete lifecycle time by approximately 1.78×, 4.27×, and 4.74× relative to A-MEM, VimRAG, and LightMem, respectively.It lies on the empirical time-accuracy Pareto frontier.
- Evidence recovery: Candidate-recoverable gold evidence appears in all four datasets, and GraphMemix retains at least one gold memory for 40.08–68.48% of eligible questions.Recovered memories account for 12.01–19.58% of all retained gold evidence.
- Ablations: ECV improves Hit@10 on all four datasets while reducing selected edges from roughly six or seven to 0.25–1.47.Separated node and edge verification improves macro-average Accuracy and Recall@10 by 2.00 and 3.00 points.
- Qualitative analysis: In a Mem-Gallery example, five improving 1-swaps raise the objective from 1.340 to 2.133 and gold coverage from 3/4 to 4/4.The resulting forest supports both Lumi the Maltese and Coco the Toy Poodle.
5 Conclusion
The conclusion frames long-term multimodal memory as query-time evidence organization. GraphMemix constructs bounded candidate graphs, separates direct and relational verification, and selects adaptive evidence forests while evaluating answer quality, evidence behavior, and lifecycle cost.
- 5 Conclusion: GraphMemix reconstructs query-conditioned evidence forests from bounded candidate graphs for a frozen multimodal reader.Its pipeline separately verifies node utility and anchor-conditioned incremental relations.
- 5 Conclusion: The optimizer first constructs a bounded proposal, then selects no more than K memories and computes exact maximum-weight forests for considered node sets.The evaluation separately tests answer quality, evidence behavior, and lifecycle cost.
A.1 Dataset Details and Preprocessing
The experiments use four personal multimodal memory benchmarks with different archive structures, interaction settings, and evidence formats. Preprocessing preserves available multimodal metadata and uses frozen captions where captions are absent.
- ATM-Bench: ATM-Bench contains 6,742 emails, 3,759 images, 533 videos, and 1,044 questions, with captions, OCR, time, and location fields retained.Every question has at least one canonical evidence memory.
- Mem-Gallery: Mem-Gallery contains 20 dialogue contexts, 240 sessions, 7,944 canonical memory rows, and 1,711 questions across nine task types.Its 1,490 images include 1,003 history images and 487 query images with native captions.
- MemEye: MemEye evaluates 1,855 rows across 3,392 memory rows and 16 mode-specific contexts, retaining native captions and resolvable gold evidence.The release includes open-answer and position-balanced multiple-choice forms.
- H2HMem: H2HMem contains 25 dialogue contexts, 7,078 memory turns, 1,300 images, and 2,236 questions without release-provided image captions.A frozen caption sidecar is generated for all 1,300 assets and shared by compared methods.
- Preprocessing: Explicit schema relations provide typed structural candidates to the edge-conditioned verifier across all four benchmarks.Missing query captions are generated using a fixed frozen verifier backbone without access to answers or retrieval results.
A.2 Models and Fixed Parameters
The implementation fixes model assignments, retrieval and graph budgets, verifier execution, and utility parameters across datasets and reader backbones. Anchors are frozen before relation verification to avoid circular selection.
- Models: Qwen3-VL and Gemma 4 settings use the same backbone family for node verification, ECV, and reading, while the answer evaluator remains fixed.The setup avoids introducing a stronger verifier for GraphMemix.
- Execution: All generation stages use a 32,768-token context limit and temperature 0, with node verification and ECV implemented as parallel listwise passes.The reader reserves at most 1,000 output tokens, while each verifier reserves at most 8,192.
- Node utility: The node utility combines frozen Atomic retrieval scores with verifier scores normalized from the [0, 5] interval.The parameters α, τ, and δ control retrieval weighting, utility sharpness, and midpoint.
- Reproducibility: The same parameter setting is used for every dataset and reader, without benchmark- or backbone-specific retuning.Anchors are deduplicated and frozen from retrieval before node and edge verification.
A.3 Full-Lifecycle Wall-Clock Analysis
The complete-lifecycle estimates combine one memory-representation construction pass with one answer pass for every evaluation question. GraphMemix achieves the highest Judge Accuracy on all three benchmarks while remaining on the empirical Pareto frontier under this workload.
- Workload definition: The lifecycle workload constructs each benchmark’s memory representation once and answers every evaluation question once.The estimates cover 7,944 memories and 1,711 questions for Mem-Gallery, 3,392 memories and 1,855 questions for MemEye, and 7,078 memories and 1,982 questions for H2HMem.
- Accuracy–lifecycle trade-off: 2.19, 2.71, and 3.44 hours are GraphMemix’s estimated lifecycles on Mem-Gallery, MemEye, and H2HMem, respectively.GraphMemix obtains the highest Judge Accuracy on each benchmark.
- Accuracy–lifecycle trade-off: No compared system matches or exceeds GraphMemix’s accuracy with a shorter estimated lifecycle.Faster systems remain lower in accuracy.
- Pareto frontier: Together with ATM-Bench, GraphMemix lies on the empirical Pareto frontier on all four benchmarks under the common lifecycle definition.The frontier summarizes the observed accuracy–lifecycle trade-off across the four benchmarks.
A.4 Prompts and Structured Outputs
The prompts constrain verification to canonical, query-aware candidate information and enforce structured outputs for node and edge-conditioned scoring. The evaluation protocol separately standardizes multimodal reader inputs and judge decisions.
- Canonical verifier input: Verifier candidates use anonymous IDs, modality tags, dates, locations, and query-aware snippets bounded to 420 text and 120 OCR characters.Node verification sees at most 48 candidates, comprising 24 retrieval seeds and graph-expanded candidates, without gold evidence or reference answers.
- Query-image captions: Question images use dataset captions when available; otherwise the verifier backbone generates captions marked as noisy descriptions rather than ground truth.Images are downscaled only when necessary, with longest edge at most 2,500 pixels.
- Verifier inputs and outputs: The node verifier receives question fields and candidates, while the edge-conditioned verifier receives anchors, eligible relations, and canonical anchor metadata.ECV outputs one row per candidate with direct support, best anchor, incremental support, and role.
- Validation rules: Structured parsers reject invalid IDs, scores, roles, anchors, or malformed responses, with retries capped at three and omitted sparse candidates assigned zero.Edge-only mode forces direct_support=0 and conservatively clears inconsistent role–score combinations.
- Reader and judge protocol: The reader receives ordered labeled evidence blocks plus selected visual media, while the shared judge sees only standardized question, reference, and prediction fields.The judge uses temperature 0 and JSON-object decoding; empty predictions and reader errors are marked incorrect.
A.5 Evidence Serialization
GraphMemix serializes the selected forest by prioritizing high-utility roots and traversing each component breadth-first. This ordering presents direct anchors before contextual evidence while respecting the reader’s memory budget.
- Forest ordering: Each connected component uses its highest-utility node as root, with components ordered by root utility.Ties use node utility and then original retrieval order.
- Evidence presentation: Breadth-first traversal presents a direct anchor before contextual evidence recovered through trusted relations.The reader receives at most K canonical multimodal memories.
A.6 Controlled Evidence-Set Selection
The controlled fixed-K study isolates proposal selection using frozen candidates, utilities, verifier outputs, and evidence budgets. Verified relational composition improves evidence selection and net gold-memory recovery beyond generic diversity, coverage, and forward-greedy alternatives.
- Experimental control: The fixed-cardinality comparison holds 48 candidates, calibrated node utilities, ECV outputs, and the evidence budget constant, with every selector returning exactly 10 memories.The proposed row evaluates fixed-K forest proposal before the complete system’s variable-cardinality refinement.
- Compared selectors: The study compares generic diversity and coverage methods with anchor-based, pointwise ECV, and greedy-forest selectors.Generic baselines do not use ECV relations, while structured variants use increasingly explicit relational signals.
- Selection results: 57.74 is the macro-average for joint node–edge optimization, versus 57.26 for pointwise ECV bonuses and 57.29 for Greedy Forest.These results use Recall@10 (%) on four held-out sets.
- Gold-evidence recovery: 43 net gold memories are recovered by the joint forest selector, compared with 18 for forward greedy and 12 for pointwise ECV bonuses.Net recovery accounts for gold evidence displaced from the node-selection baseline.
- Gold-evidence recovery: On H2HMem, joint node–edge optimization recovers 31 net gold memories, versus 9 for Greedy Forest and at most 1 for generic selectors.The benchmark’s answers often require several complementary memories, making this separation diagnostic of relational composition.
- Judge audit: Manual decisions agree with 194 of 200 GPT-5-mini judgments, corresponding to 97.0% agreement across benchmarks and compared methods.The audit uses a stratified sample of answers.