- 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?
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:
The new independently-future-queryable-alternatives corollary makes the intended generalization precise without claiming that Wsuf 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=16, the gap to an exact code shrinks from approximately 0.26 under the submitted protocol to approximately 0.06 after increasing data and optimization and correcting the quantizer. At k=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=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=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≥1 is 0.264 versus 0.125, respectively.
4. Could the retention drop be explained simply by accumulated bit errors?
We tested this directly.
At the largest retention load:
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.033 of the error is attributable to information lost before the decoder, while another 0.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.