EPGM: Execution Provenance for Budgeted Agent Memory Retrieval

A paper posted to arXiv on 22 September 2026 by Jiaqi Zhang introduces EPGM, a method that reframes language-agent memory retrieval as budgeted evidence completion and scores exact gold spans in shared source coordinates. Evaluated on 2,000 span-grounded memory queries over 1,207 held-out execution-grounded ISETrace trajectories, source-aligned provenance units improved Full Support@2048 by 19.07 points over flat 512-token windows and stayed 11.96 points above a per-metric oracle across four flat chunk sizes, while a zero-initialized residual R-GCN over typed provenance edges added 4.55 points (95% CI [2.98, 6.18]) with candidates and seed scores held fixed. The authors report the graph gain concentrates when gold evidence spans multiple events, and that entity co-occurrence expansion produced no comparable benefit.

Computer Science Multiagent Systems Submitted on 22 Sep 2026 v1 https://arxiv.org/abs/2609.25913v1 , last revised 6 Oct 2026 this version, v2 Title:EPGM: Execution Provenance for Budgeted Agent Memory Retrieval View PDF https://arxiv.org/pdf/2609.25913 HTML experimental https://arxiv.org/html/2609.25913v2 Abstract:A language agent's execution history can exceed its context window, requiring its memory system to retrieve complete supporting evidence under a hard token budget. Evidence may span multiple execution events, yet conventional retrievers use fixed token windows and fixed-k metrics that reward individual fragments without showing whether the complete evidence set fits in context. Smaller windows reduce irrelevant text but scatter evidence across candidates, while flat-versus-graph comparisons can conflate candidate design with graph propagation. To address these limitations, we formulate agent-memory retrieval as budgeted evidence completion and score exact gold spans in shared source coordinates. We first construct source-aligned provenance units from tool arguments and outputs. We then apply a zero-initialized residual R-GCN to refine frozen dense-retrieval scores over typed provenance edges. We evaluate 2,000 span-grounded memory queries over 1,207 held-out execution-grounded ISETrace trajectories. With matched Dense-FT scoring, provenance units improve Full Support@2048 by 19.07 points over flat 512-token windows and remain 11.96 points above a per-metric oracle over four flat chunk sizes; the pattern also holds with cross-encoder scoring. Holding the candidates and seed scores fixed, graph propagation adds 4.55 points in Full Support@2048 95% CI 2.98, 6.18 . This gain is concentrated when gold evidence spans multiple events; entity co-occurrence expansion produces no comparable benefit, and relation and topology controls confirm dependence on typed transformations and observed graph structure. Overall, source-aligned candidates address the dominant granularity trade-off, while graph-conditioned propagation adds a smaller, targeted benefit for distributed evidence. Submission history From: Jiaqi Zhang view email https://arxiv.org/show-email/34d621e7/2609.25913 Tue, 22 Sep 2026 09:20:51 UTC 375 KB \ v1\ https://arxiv.org/abs/2609.25913v1 v2 Tue, 6 Oct 2026 01:58:15 UTC 374 KB Additional Features References & Citations Loading... Bibliographic and Citation Tools Bibliographic Explorer What is the Explorer? https://info.arxiv.org/labs/showcase.html arxiv-bibliographic-explorer Connected Papers What is Connected Papers? https://www.connectedpapers.com/about Litmaps What is Litmaps? https://www.litmaps.co/ scite Smart Citations What are Smart Citations? https://www.scite.ai/ Code, Data and Media Associated with this Article alphaXiv What is alphaXiv? https://alphaxiv.org/ CatalyzeX Code Finder for Papers What is CatalyzeX? https://www.catalyzex.com DagsHub What is DagsHub? https://dagshub.com/ Gotit.pub What is GotitPub? http://gotit.pub/faq Hugging Face What is Huggingface? https://huggingface.co/huggingface ScienceCast What is ScienceCast? https://sciencecast.org/welcome Demos Recommenders and Search Tools Influence Flower What are Influence Flowers? https://influencemap.cmlab.dev/ CORE Recommender What is CORE? https://core.ac.uk/services/recommender arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs https://info.arxiv.org/labs/index.html .