The persistent headache for autonomous agents is context window management. When execution history exceeds available tokens, standard retrieval systems fail to reconstruct complete evidence chains. A new arXiv paper, "EPGM: Execution Provenance for Budgeted Agent Memory Retrieval," tackles this by reframing memory retrieval as a budgeted evidence completion problem. The authors, led by Jiaqi Zhang, propose a system that prioritizes source-aligned provenance units over arbitrary text chunks, addressing the fragmentation issues that plague current agent architectures.

Provenance Units vs. Fixed Windows

Conventional retrievers rely on fixed token windows and fixed-k metrics, which often scatter critical evidence across multiple candidates. EPGM introduces a method to construct source-aligned provenance units directly from tool arguments and outputs. By scoring exact gold spans in shared source coordinates, the system ensures that the complete evidence set fits within the hard token budget. This approach decouples candidate design from graph propagation, allowing for a cleaner analysis of what actually drives retrieval performance.

Graph Propagation Adds Targeted Gains

The core innovation involves a zero-initialized residual R-GCN that refines frozen dense-retrieval scores over typed provenance edges. In evaluations using 2,000 span-grounded memory queries across 1,207 held-out ISETrace trajectories, the results were stark. With matched Dense-FT scoring, provenance units improved Full Support@2048 by 19.07 points compared to flat 512-token windows. Even more impressively, they remained 11.96 points above a per-metric oracle across four flat chunk sizes. The graph propagation component added a further 4.55 points, specifically when gold evidence spanned multiple events.

Key Takeaways

  • Provenance units outperform flat windows by ~19 points in Full Support@2048.
  • Graph propagation adds ~4.55 points, but only for distributed evidence.
  • Entity co-occurrence expansion showed no comparable benefit.
  • The method uses zero-initialized residual R-GCN for score refinement.

The Bottom Line

Stop dumping raw logs into your vector DB; structure your agent's memory around execution provenance, or you're just retrieving noise with extra steps.