PAY WHEN ASKED: DEMAND-DRIVEN AGENT MEMORY

Long-term agents must organize growing archives without knowing which information future queries will need. We view memory as demand-driven computation: retain source evidence while postponing structure until it is useful. Yet query-time construction alone leaves a second cost unresolved: repeatedly rebuilding relations for different questions about the same evidence. We formalize this trade-off by separating global access coverage, local reuse, and answer computation. Our central insight is that sparse global access can coexist with repeated local demand, making selective construction and persistent reuse complementary. Guided by this insight, we introduce SRH-Graph, a demand-driven relation-memory method that constructs source-grounded relations on retrieval, reuses them across distinct questions, and invalidates them when sources change; SRH-Base provides the lightweight retrieval-only variant. On controlled multi-hop chains, SRH-Graph reaches 80.83–100% accuracy where Naive RAG reaches 0–3.33%; reuse reduces repeated construction, while deferral savings vanish near full coverage. On real benchmarks, we find gains on a fixed sparse document stream, but retain Naive RAG's conversational advantage and report higher graph costs. Our results identify when organizing memory on demand is useful, and when simpler retrieval or advance construction remains preferable.