- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper proposes reusable graph representations for answering multiple ordered-path queries without re-encoding the graph each time. It introduces the Edge–Vertex Transformer and characterizes the expressive power of different cache-reading strategies. Experiments on synthetic tasks, Internet routing, and biological splicing demonstrate computational savings and task-dependent benefits of relational path processing.
Critical strengths
The paper separates quite well what a cached representation can express from what a finite model learns in practice. Also, the expressivity hierarchy provides a useful account of the trade-offs between selection, joint cache reading, and query-specific encoding. Finally experiments span controlled synthetic tasks and two real applications. The same-weight timing comparisons convincingly demonstrate the benefits of cache reuse.
Critical weaknesses
In practice the scalability verification remains quite limited. Graph encoding has cubic computational cost and the cache requires quadratic storage from what I see. Synthetic scaling measurements reach only 112 vertices, while Atlas graphs are capped at 256. Reuse reduces repeated computation, but these experiments do not establish whether the approach remains practical on substantially larger graphs.
The Atlas comparison does not isolate the benefit of the proposed architecture. TT uses approximately 779k parameters, compared with 449k for PP-MLP and 101k for PathTransformer, with different search costs. Its MAE improvement is around 0.26–0.28 ms. Since simpler processors outperform TT on ThorAxe-Combo, a budget-matched Atlas comparison is important to establish when the additional architectural complexity is worthwhile.
Questions for authors
-
How do encoding time, peak memory, and the number of queries needed to amortize encoding scale beyond the evaluated graph sizes?
-
Does TT retain its Atlas advantage when parameter counts and tuning budgets are matched?
-
Can you identify task characteristics that predict when triangular path processing helps, given its gains on synthetic composition and Atlas but weaker performance on ThorAxe-Combo?
8 comments
Q1 — Encoding time, memory and cache amortization
Q1: Scaling to larger graphs requires using a tiling mechanism to lift the memory bottleneck, potentially at the price of a higher computational cost. This principle was already described in Appendix J.3 of the submission (Proposition J.2), but was not tested in the submitted experiments. Our bilinear triangular operator uses its own row/channel tiling, rather than a drop-in FlashAttention kernel. Activation checkpointing recomputes intermediate activations during the backward pass instead of retaining them. Neither technique removes the dense operator's cubic arithmetic cost. To evaluate more precisely the practical memory-time tradeoff, we have conducted two new evaluation experiments detailed below and in the revised version. These measurements establish computational feasibility up to 1,024 vertices without changing the submitted architecture. The profiles use one synthetic graph per size and do not establish predictive accuracy on larger real graphs.
Both experiments use the submitted Atlas TT architecture ( 778,897 parameters, width 64, two graph and two path EVT layers), an A100-SXM4-40GB, PyTorch 2.9.1/CUDA 12.9 and FP32 without TF32. Width, depth and precision remain unchanged.
Peak memory and execution time: forward + backward. This experiment uses initialized weights, one graph and 16 paths of length 16 processed together. It includes graph encoding, all predictions, a synthetic MSE loss and backward through both stages, without an optimizer step. Architecture, weights and inputs are identical across execution policies. Plain uses native execution; light and aggressive use progressively smaller triangular/cross-attention tiles and checkpointing, with additional whole-layer checkpointing in aggressive mode. Small-graph output, loss and parameter-gradient parity checks pass before profiling.
Each cell gives peak allocated memory in GiB (mean forward+backward time in ms) over ten timed repetitions after two warmups. Memory is the maximum allocated peak across repetitions, including resident weights and inputs. Initialization, transfers and gradient clearing are excluded.
| Graph size | Plain | Light | Aggressive |
|---|---|---|---|
| 256 | 17.95 (726.03) | 1.62 (571.94) | 0.70 (1695.45) |
| 512 | OOM | 6.29 (4839.51) | 2.59 (9019.97) |
| 1,024 | OOM | 24.92 (38442.36) | 10.16 (71448.49) |
OOM denotes failure under the common 35 GiB allocation cap. These are full forward/backward peaks and times, not cache sizes or isolated inference-encoding costs. Both optimized policies complete forward and backward at 1,024 vertices. At this size, aggressive execution reduces peak memory by 2.45×, at 1.86× the total time of light execution.
Encoding time and amortization: inference. Separately, we use a fixed trained checkpoint, aggressive graph-stage tiling and the unchanged path decoder; checkpointing is inactive. Distinct, unpadded paths of length (Atlas median) are processed individually. Encoding time and decoding time per path are measured separately; decoding includes selection, projections and the prediction head. Timings exclude initialization and transfers. We average ten encodings and 320 decodes after warmups.
For queries, with and expressed in the same units, total time is modeled as . The estimated count \widehat{Q}_{10\\%} = \lceil 9E/D \rceil makes initial encoding contribute at most 10% of this total.
| Graph size | Encoding (s) | Decoding (ms/path) | Estimated queries (10%) |
|---|---|---|---|
| 256 | 0.322 | 17.508 | 166 |
| 512 | 2.175 | 17.706 | 1,106 |
| 1,024 | 17.354 | 17.458 | 8,946 |
Counts use unrounded means. This is an amortization threshold, not the minimum query count that benefits from reuse. Re-encoding the same graph for every query would cost approximately ; under this model, reuse saves computation as soon as . At 1,024 vertices, encoding costs about 994 single-path decodes: approximately 994 queries make its share 50%, whereas 8,946 make it at most 10%.
Direct checks at , and the estimated 50% threshold differed from by at most 5.52%. The 10% thresholds were not directly timed. Paths of length gave similar decoding costs in this setup; this does not imply path-length-independent complexity.
We are sorry for our slow response, which is due to the extensive new numerical experiments we have been conducting to address questions precisely. First, we believe our new experiments now put the comparison between the different architectures on a fair basis. Second, it is indeed true that TT is not always the best-performing model, and its computational cost may lead one to consider lighter architectures. But it is important to recall that our contribution does not aim to demonstrate TT’s superiority, but to propose, theoretically analyze, and extensively benchmark a new family of modular two-stage architectures, which we now call StrikeTwice. This framework allows the graph encoder and path processor to be chosen independently. We denote these choices as ST[GraphEncoder, PathProcessor]: TT and PP-MLP correspond to ST[EVT, EVT] and ST[EVT, MLP], respectively, two configurations with different computational costs. Our new matched-capacity comparisons (Q2), frozen-cache ablations (Q3) and scaling measurements (Q1) directly address these concerns, while also documenting the remaining accuracy–cost trade-offs. We therefore hope you will consider these new results alongside our broader contribution of bringing together methods, theory and benchmarking around a well-defined learning problem. We are happy to elaborate further if the new numerical experiments do not adequately address your concerns.
As a small additional point, which was not requested in your questions, we adapted and evaluated RouteNet (Rusek et al., 2020): under a 24,000-update cap, RouteNet-SELU’s mean MAE is 10.886 ms, compared with 10.396 for TT and 10.460 for widened PP-MLP (see our response to Reviewer Q2t7, Q7 for more details).
Update after reading the other reviews. I am inclined to lower my score to 2. I had asked whether TT keeps its Atlas advantage under matched budgets. As Reviewer HxAF notes, Table E.5 already suggests an answer: a selection reader on frozen PP-MLP caches reaches 10.956 ms, close to TT’s 10.940 ms, although the training protocols differ. TT’s gain on its only winning real-data benchmark may therefore come from tuning rather than from triangular path processing, and it costs about 3× more per path (1.896 vs 0.647 ms). Together with the ThorAxe results and my scalability concerns, the evidence does not yet show that the architecture justifies its cost. I still value the expressivity analysis and would reconsider if the authors provide a budget-matched comparison.