How Much Memory Does Temporal Graph Reasoning Need?

A partial route that is not currently best may become optimal after a future connection appears. A system that summarizes a temporal graph before that future query is known must therefore preserve several possible routes. We formalize the resulting memory problem for deferred temporal path queries. On a three-vertex family encoding $k$ independently queryable facts, any prefix-summary or one-pass streaming protocol requires $\Omega (k)$ bits, whereas one bit suffices when the query is known during encoding. We introduce TempoFrontier, a diagnostic benchmark with exact solvers, verified witnesses, query-only and full-instance references, and explicit inference-time bit bottlenecks. Learned event encoders exhibit an unavoidable low-capacity regime and a persistent gap from an achievable code after lossless storage becomes possible. Under repeated updates, the prefix information remains partly decodable, while task accuracy and selective use of the code decline. On procedurally generated graphs and real transit timetables, node-indexed memory with stable node identities outperforms the tested global summaries at matched bit budgets, especially when the completion requires prefix-derived labels. These results separate the roles of information capacity, learned utilization, retention, and addressability in deferred temporal graph reasoning.