acceptodds
Under review as a conference paper at ICLR 2027

How Much Memory Does Temporal Graph Reasoning Need?

Abstract

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 independently queryable facts, any prefix-summary or one-pass streaming protocol requires 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
temporal graphs, memory, communication complexity, lower bounds, diagnostic benchmark

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_novHOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how much state a system must keep when it summarizes a temporal graph prefix before the completion (and hence the query) is revealed. On a three-vertex family where the prefix encodes a k-bit string as the presence or absence of incomparable (start, arrival) labels, and the completion picks an index j, the fastest-path optimum reveals x_j through a fixed threshold, so any prefix-summary or one-pass streaming protocol is a one-way INDEX protocol and needs Omega(k) bits (Theorem 1). A Fano envelope gives an average-case accuracy ceiling (Prop. 1), and revealing the query before encoding makes one bit sufficient (Prop. 2). The authors then build a benchmark, TempoFrontier, with exact solvers, hard bit bottlenecks at evaluation, and a completion-relative label count W_suf for non-gadget graphs. Empirically, learned encoders stay well below the achievable truncation code even when b is at least k, degrade under interleaved updates while a linear probe still decodes the bits, and node-indexed memory beats a global summary at matched budgets on procedural graphs and a TriMet timetable.

Critical strengths

The experiments are done carefully. Every prefix-dependent value crossing the boundary is counted in b, the side-channel audit (Appendix C) shows accuracy collapses when the message is replaced or permuted and the identity-aligned versus hidden-permutation pair is parameter- and bit-identical, which I think is a good test of addressability. The theorem file in the supplement matches the main text, including the scope note.

Critical weaknesses

First, I do not think the theory carries as much weight as the title and abstract suggest. Theorem 1 is the INDEX lower bound with a temporal-path encoding in front of it. The reduction is correct, but with k+2 events the result says one cannot compress a prefix that literally stores k independent bits, and Prop. 2 is the familiar observation that INDEX with the index known to Alice costs one bit. Nothing in the theory ties the bit requirement to the frontier width of general instances. The only statement about W_suf (Appendix A.4) concerns executors that store exact labels and keep no summary of discarded ones, which is close to definitional. So the title question is answered for one constructed family, and the procedural and transit results rest on an empirical width measure, not a bound. I would also object to the abstract's phrase "unavoidable low-capacity regime". The Fano envelope at k=8, b=2 allows roughly 0.79 accuracy and the truncation code gets about 0.625, yet the scan sits at the 0.5 baseline for b up to 2. That plateau is a learning failure. The theorem does not force it.

Second, several learned-memory conclusions are hard to separate from optimization of small models. Plain straight-through failed even at b=2k (Appendix C), the GRU and Deep Sets end below the query-only baseline in Table 3 (0.34 to 0.40 against 0.49), and the node-keyed scan reaches the baseline by k=32. Below-chance accuracy points to training trouble rather than a capacity effect, so the "persistent gap" is a statement about this protocol. On procedural graphs the unquantized global summary scores 0.05 at W_suf=1, matching the majority baseline, while the decoder is itself a scan that consumes per-node state. A global model that fails without any bit constraint suggests an interface mismatch, which makes the global versus node-indexed gap less informative than the identity intervention (+0.06 per bin). That intervention also shows aligned channels losing 12 points at W_suf=0 (0.695 vs 0.817), which is not discussed.

Smaller point: in Section 6.4 per-bit probe error rises sixteenfold (0.998 to 0.968), and the decisive branch depends on several bits, so "barely moves" overstates the dissociation.

Questions for authors

(1) Is there any result, even for restricted encoders, linking W_suf (or frontier size) to a bit lower bound on instances outside the gadget family?

(2) Can you show the b at most 2 plateau is not inherent, for example by training with the truncation code as an auxiliary target, and would you revise the "unavoidable" wording?

(3) What explains the aligned model losing 12 points to the permuted one at W_suf=0, and does the global model improve with a decoder not built around per-node state?

(4) How much of the accuracy drop in Figure 3a is predicted by the per-bit probe error alone, if you plug probe outputs into the exact decision rule?

1 comment
AuthorsOpenReview ↗

Response to Reviewer novH

We appreciate the reviewer's comments and we would like to respond point by point below:

1. Is the INDEX result too limited to support the paper's broader claim?

We agree that the INDEX reduction itself is conceptually simple and will not present it as a new communication-complexity result. Its role is to provide a temporal reasoning family for which the information requirement and attainable accuracy can be calibrated exactly.

The broader contribution is the combination of:

  • a deferred temporal-query formulation;
  • a theorem-aligned hard memory boundary;
  • exact solvers and witness verification;
  • learned-utilization diagnostics;
  • retention interventions;
  • memory-organization experiments.

The new independently-future-queryable-alternatives corollary makes the intended generalization precise without claiming that WsufW_{\mathrm{suf}} itself implies a universal bit lower bound.

2. Could the learned conclusions be optimization artifacts?

Yes, partly. The new scaling experiments confirm this and we will revise the claims accordingly.

At k=16k=16, the gap to an exact code shrinks from approximately 0.260.26 under the submitted protocol to approximately 0.060.06 after increasing data and optimization and correcting the quantizer. At k=32k=32, a substantial gap remains, but the continuous prefix representation itself fails to reliably recover all input bits, indicating upstream representation-learning difficulty rather than an information-capacity barrier.

The auxiliary-code experiments further show that the same model and channel can reach perfect performance at k=8,b=8k=8,b=8, while standard end-to-end training does not.

We will therefore describe the learned-utilization gap as optimization- and representation-dependent rather than information-theoretically unavoidable.

3. Could the global-summary failure be a decoder mismatch?

We added direct global MLP and GRU decoders and increased both model capacity and training. These controls do not remove the organization gap once the models have enough data to generalize on W=0W=0. We will nevertheless demote the global-vs-node comparison from causal evidence and use the matched aligned-versus-hidden-permutation intervention as the primary addressability result.

At 24k training instances, aligned and permuted node memories use the same encoder, decoder, parameter count, bit budget, number of cells, and read pattern; they differ only in whether stable node identity is preserved. Their mean accuracy over Wsuf≥1W_{\mathrm{suf}}\ge1 is 0.2640.264 versus 0.1250.125, respectively.

4. Could the retention drop be explained simply by accumulated bit errors?

We tested this directly.

At the largest retention load:

  • trained decoder accuracy: 0.8470.847;
  • linear-probe bit accuracy: 0.9710.971;
  • exact decision rule applied to linear-probe bits: 0.9260.926;
  • nonlinear MLP-probe bit accuracy: 0.9870.987;
  • exact decision rule applied to MLP-probe bits: 0.9670.967;
  • exact decision rule applied to true bits: 1.0001.000.

Thus both effects occur. Some information is genuinely lost under retention load, but a substantial amount remains decodable yet is not used by the trained decoder. With the stronger MLP probe, approximately 0.0330.033 of the error is attributable to information lost before the decoder, while another 0.1200.120 arises after information sufficient for substantially better decisions remains recoverable.

We will replace the previous statement that “decodability barely moves” with the more precise conclusion that retention load causes both information loss and failure to use still-recoverable information.

Reviewer_34eVOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies memory for deferred temporal path queries, where routes must be preserved because a currently suboptimal path may become optimal after future connections. It shows any prefix summary or one-pass streaming protocol needs Ω(k) bits on a three-vertex family, while 1 bit suffices if the query is known. It introduces TempoFrontier, a benchmark with exact solvers and bit-bottleneck analysis. Experiments show learned encoders suffer capacity limits and a persistent gap from achievable codes; node-indexed memory with stable identities outperforms global summaries at matched budgets. Overall, it separates capacity, learned utilization, retention, and addressability in temporal graph reasoning.

Critical strengths

Understanding how a system should preserve historical information before knowing which future completion will matter is a good topic.

Critical weaknesses

I cannot identify a sufficiently precise overarching conclusion that brings its results together. The paper does not sufficiently connect its results into a clear account of the memory requirement it seeks to characterize. The theoretical analysis concerns arbitrary bit encodings for a binary decision problem on a constructed family. The subsequent quantity, W_suf, concerns explicit labels for a fixed prefix and a declared completion family. The experiments then concern branch identification or optimal-value prediction by particular learned models. These are related but distinct objects, and their relationship is not established sufficiently to support the paper's overarching account of capacity, utilization, retention, and addressability.

Questions for authors

Please check the weakness part

1 comment
AuthorsOpenReview ↗

Response to Reviewer 34eV

We agree with the reviewer's main conceptual criticism: the submitted framing did not make the relationship among the communication lower bound, WsufW_{\mathrm{suf}}, and the learned tasks precise enough.

We will revise the paper around two explicitly distinct notions.

Family-level information complexity asks how many bits an arbitrary reusable summary must preserve over a family/distribution of prefixes and future queries. This is where the Ω(k)\Omega(k) lower bound and Fano-style bound apply.

Per-prefix exact-label complexity asks how many exact boundary labels an explicit executor must preserve for one prefix and one declared completion family. This is what WsufW_{\mathrm{suf}} measures.

Neither quantity generally determines the other. In particular, a fixed prefix with large WsufW_{\mathrm{suf}} need not require many communicated bits if the prefix is known in advance, while an arbitrary binary representation may compress several label facts.

To make the bridge precise, we add the following general corollary: if mm alternatives vary independently across a prefix family and each can be individually queried by some future completion, then any reusable prefix summary requires Ω(m)\Omega(m) bits. Our temporal INDEX construction realizes this condition. This is stronger than simply requiring Wsuf=mW_{\mathrm{suf}}=m for one fixed prefix.

Accordingly, the revised paper will not claim that “frontier width determines memory requirements.” Instead:

The theory characterizes information requirements created by independently future-queryable uncertainty; WsufW_{\mathrm{suf}} is a separate structural measure of exact-label demand; and the empirical study asks when that structural demand predicts learned difficulty and when organized memory helps preserve and retrieve the required information.

We also plan to narrow the title to “TempoFrontier: Information Limits and Memory Organization for Deferred Temporal Path Queries”, which better reflects the actual contribution.

Reviewer_h3fvOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper investigates temporal pathfinding under deferred queries, where a system must first compress a prefix of a temporal graph into a bb-bit summary before observing the subsequent connections (the completion) that determine the optimal route. The theoretical analysis constructs a family of instances with three vertices and k+2k+2 events, embedding the INDEX problem into the optimal duration of a fastest path. This establishes that any prefix summary or single-pass streaming protocol requires Ω(k)\Omega(k) bits. The paper further derives an upper bound on average-case accuracy using Fano’s inequality and shows that only one bit is sufficient when the query is known at encoding time. The authors introduce the TempoFrontier diagnostic benchmark, featuring an exact solver, witness-path verification, and a hard bit bottleneck.

Critical strengths
  1. Clear problem formulation and appropriately scoped conclusions.
  2. Well-designed controlled experiments.
  3. High engineering credibility.
Critical weaknesses
  1. Section 6.2 and the abstract claim that the learned encoder exhibits a “persistent gap” when b≥kb \geq k, with performance degrading toward the baseline as kk increases (at k=32k=32). However, this gap may primarily stem from the training protocol. Since no scaling experiments are provided for training steps, model width, or quantizer capacity, it is difficult to distinguish between a problem that is fundamentally difficult to learn and one that is difficult to learn under the specific optimization setup used in this work.
  2. The paper’s central narrative is that “frontier width / minimum sufficient width determines memory requirements.” However, the interactive model in Section 6.5 shows that the effect is concentrated in the first bin that requires prefix-derived labels.
  3. In Figure 4a, “global cont.” uses an unquantized 128-dimensional continuous vector with effectively unrestricted information capacity, yet achieves only 0.05 when Wsuf=1W_{\text{suf}} = 1. This suggests that the bottleneck lies in the pooling or readout architecture rather than in the number of bits available.
  4. The procedurally generated graphs contain only 10 vertices and 30 events, which limits the external validity of the findings.
  5. What might explain why the permuted variant performs better when Wsuf=0W_{\text{suf}} = 0?
Questions for authors

See above.

2 comments
AuthorsOpenReview ↗

Response to Reviewer h3fv

We appreciate the reviewer's comments, and we would like to respond point by point below.

1. Could the learned-utilization gap reflect training budget or model capacity?

We agree and added controls varying training data, optimization steps, hidden width, and quantization.

At k=b=16k=b=16, accuracy improves from 0.7370.737 to 0.8340.834 with 4× steps, 0.9020.902 with 16× data, and 0.939±0.0110.939\pm0.011 with both and the corrected quantizer. Increasing hidden width alone has little effect. At k=b=32k=b=32, accuracy improves from 0.5210.521 to 0.711±0.0150.711\pm0.015, but the continuous pre-quantizer representation still fails to reliably recover all presence bits, suggesting an upstream event-to-fact extraction bottleneck.

Code supervision further isolates learned utilization: at k=b=8k=b=8, accuracy rises from 0.929±0.0300.929\pm0.030 to 1.000±0.0001.000\pm0.000; at k=16,b=8k=16,b=8, from 0.648±0.0150.648\pm0.015 to 0.713±0.0040.713\pm0.004, near the 0.7190.719 truncation reference.

We will remove claims of an intrinsic or persistent utilization gap. Information bounds determine feasibility, while observed gaps depend strongly on data, optimization, and representation learning.

2. Does WsufW_{\mathrm{suf}} mainly indicate whether prefix-derived state is needed?

We agree that stable addressability exhibits a threshold effect: its benefit emerges when Wsuf≥1W_{\mathrm{suf}}\ge1. However, among prefix-dependent instances, larger WsufW_{\mathrm{suf}} remains negatively associated with accuracy after controlling for frontier mass, decisive-label delay, witness multiplicity, and target value.

We will distinguish the onset of addressability benefits from the increasing difficulty of exact-label retrieval, without treating WsufW_{\mathrm{suf}} as a monotonic bit threshold.

3. Is the global-summary result caused by decoder mismatch?

We added direct global MLP and GRU decoders with more parameters than the node-indexed model. At 6k training instances, global models fit training data but generalize poorly, revealing a small-data confound.

With 24k instances, accuracy across W=0/1/2/≥3W=0/1/2/\ge3 is:

  • Full instance: 0.957/0.736/0.632/0.4180.957/0.736/0.632/0.418.
  • Node-indexed continuous: 0.938/0.694/0.556/0.3230.938/0.694/0.556/0.323.
  • Original global interface: 0.881/0.189/0.098/0.0880.881/0.189/0.098/0.088.
  • Direct global GRU: 0.607/0.096/0.052/0.0610.607/0.096/0.052/0.061.

At a matched 80-bit budget, node-indexed memory achieves 0.924/0.355/0.256/0.1730.924/0.355/0.256/0.173, versus 0.617/0.097/0.064/0.0500.617/0.097/0.064/0.050 for the direct global GRU. Quadrupling optimization steps does not eliminate the gap.

We will frame this as a generalization and sample-efficiency advantage under tested conditions, not a universal capacity limitation. Aligned-versus-permuted memory provides cleaner causal evidence for addressability.

4. Are the procedural graphs too small?

We added a size sweep using 24k training instances, covering 10/30, 20/60, and 40/120 vertices/events. Mean accuracy over Wsuf≥1W_{\mathrm{suf}}\ge1 is:

  • Full instance: 0.593/0.568/0.5810.593/0.568/0.581.
  • Node-indexed continuous: 0.541/0.527/0.5200.541/0.527/0.520.
  • Global continuous: 0.123/0.092/0.0740.123/0.092/0.074.

The ordering persists through 40 vertices and 120 events. We will present this as robustness rather than scalability evidence and give the real TriMet experiment greater prominence.

5. Why did hidden permutation help at Wsuf=0W_{\mathrm{suf}}=0?

At 6k instances, aligned, permuted, and identity-dropout/aligned models achieve 0.6950.695, 0.8170.817, and 0.8590.859 at W=0W=0, respectively, suggesting a small-data regularization effect.

At 24k instances, the corresponding W=0W=0 accuracies are 0.928/0.917/0.9360.928/0.917/0.936, while mean accuracies for W≥1W\ge1 are 0.264/0.125/0.2600.264/0.125/0.260.

Thus, the original inversion disappears with more data. Stable identity is not inherently harmful at W=0W=0 and remains substantially beneficial when prefix-derived labels must be retrieved.

Thanks for the additional experiments. I will raise the soundness score.

Comments on the paper

2 comments

We thank the reviewers for the careful and technically substantive feedback. The reviews led us to revisit both the conceptual framing and several empirical controls. The additional analyses materially improve our understanding of the results, and we will revise the manuscript accordingly.

Two points are common to the reviews.

First, we agree that the submitted paper did not distinguish sharply enough between two different notions of state requirement. The communication lower bound is a family-level information result: it asks how many bits a reusable summary must preserve when independently variable facts in a prefix may be queried later. In contrast, WsufW_{\mathrm{suf}} is a per-prefix exact-label quantity: it counts how many boundary labels an explicit label-based executor must retain for a declared completion family. We do not claim that Wsuf=wW_{\mathrm{suf}}=w for a fixed prefix implies an Ω(w)\Omega(w)-bit lower bound for an arbitrary compressed representation.

To make the connection precise, we will add a general corollary that abstracts the current three-vertex construction. If a prefix family contains mm independently variable alternatives and, for every alternative ii, a future completion can individually recover whether that alternative was present, then any reusable prefix summary requires Ω(m)\Omega(m) bits by the same one-way INDEX reduction. Thus the information requirement is created not by frontier cardinality alone, but by independently variable alternatives that future queries can select. Our three-vertex family is one realization of this condition. We will also state explicitly that a large WsufW_{\mathrm{suf}} for one fixed prefix does not by itself imply a bit lower bound.

Second, the requested robustness experiments uncovered an implementation issue at very small bit budgets. In the submitted model, LayerNorm was applied across the b)b) message logits before the hard sign operation. This unintentionally restricted the realizable discrete alphabet when bb is very small: at b=1b=1 the channel carries no prefix information, and at b=2b=2 it does not realize the advertised four codewords. We corrected the quantizer using per-bit normalization and reran the affected headline low-budget experiment. For k=8k=8, theorem-aligned accuracy changes from 0.490,0.490,0.682,0.904,0.9970.490,0.490,0.682,0.904,0.997 at b=1,2,4,8,16b=1,2,4,8,16 to 0.552,0.600,0.722,0.929,0.9980.552,0.600,0.722,0.929,0.998, respectively. The theorem is unaffected, and the headline results at ordinary budgets (b≥8)(b\ge8) are essentially unchanged. We will remove the phrase “unavoidable low-capacity regime,” replace all affected low-budget results with corrected runs, and remove any low-bit result that has not been rerun with the corrected channel. In particular, the submitted “2 bits per node” procedural arm did not provide a valid two-bit-per-node channel and will not be retained as such.

These corrections lead to a narrower and, we believe, more accurate central claim: the theory calibrates the information requirement created by deferred queries; the learning experiments study how effectively models extract, retain, and retrieve that information; and WsufW_{\mathrm{suf}} is a complementary exact-label measure used to stratify structural demand rather than a universal bit-complexity law.

Manuscript changes

In addition to the reviewer-specific revisions above, we will make the following global changes:

  1. Narrow the title and central claim.
  2. Explicitly distinguish information complexity from exact-label complexity.
  3. Add the independently-future-queryable-alternatives corollary and the non-implication from WsufW_{\mathrm{suf}} to arbitrary bit complexity.
  4. Remove “unavoidable low-capacity regime” and unqualified “persistent utilization gap.”
  5. Correct the small-budget quantizer and replace or remove every affected empirical result.
  6. Replace the submitted 6k organization experiments with the 24k results.
  7. Make aligned-versus-permuted memory the primary causal addressability experiment.
  8. Replace the retention interpretation with the probe-to-exact decomposition.
  9. Remove the defective 2-bits-per-node procedural and transit claims; in the transit study we will report memory in bits per node and retain only valid configurations.
  10. Add the graph-size robustness sweep and clarify that it is a robustness result rather than a scalability claim.

We appreciate that the reviews pushed us to distinguish what is imposed by information theory from what is caused by optimization, representation learning, retention, and memory organization. We believe the revised paper will make these distinctions much more explicit and substantially sharpen the contribution.

AuthorsOpenReview ↗

Revision uploaded

We have uploaded a revised manuscript incorporating the changes and additional experiments described in our responses. The revision corrects the small-budget quantizer issue, sharpens the distinction between family-level information complexity and WsufW_{\mathrm{suf}}, and adds the requested optimization, decoder-interface, retention, and scale controls. We also narrowed the affected claims accordingly. Please see the revised PDF and diff.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.