- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces NRTRL by framing the approximation of the RTRL influence matrix itself as a learnable problem. It adopts the unified perspective of encoder, decoder, and update operator proposed by Marschall et al. (2020): an influence code represents , an update network maintains this code, and an influence network decodes it into . The key construction involves reusing the original RNN cell: learnable virtual inputs, virtual states, and low-rank parameter perturbations () are applied over a virtual trajectory of length , and the Jacobian of the final virtual state with respect to parameters serves as the influence estimate (Eq. 6–8). This approach ensures the output is the Jacobian of a specific function (following the Sobolev approach) and maintains the structure of an influence matrix, all while relying solely on JVP/VJP operations without explicitly constructing the full matrix. Training employs a consistency loss to align "decoding the new code and taking one RTRL step" with the "RTRL target derived from the decoded old code" (Eq. 9); it uses Gaussian probes to express the Frobenius difference in a form suitable for unbiased estimation and applies bootstrapping with stop-gradient on the target (Eq. 10). Two theoretical results are presented: the contractivity of the RTRL operator under the RNN contraction assumption, and the fact that the average influence error is bounded by the average consistency loss (Proposition 1); and the formulation of the influence estimate as a sum of Kronecker products (Proposition 2, establishing the connection). Experiments conducted on pixel-by-pixel MNIST and character-level Penn Treebank compare the method against UORO, KF-RTRL, SnAp-1, and TBPTT variants (7/56 and 25), highlighting the advantage of a code size of compared to the complexity of the baselines.
Critical strengths
Reframing the task from "designing a low-rank/sparse structure" to "learning an approximator" brings a clear, novel perspective to RTRL influence approximation. This approach bridges RTRL with Sobolev training and amortized optimization; furthermore, the mechanism relies exclusively on JVPs/VJPs—avoiding the full matrix—making for a clean engineering implementation. Parameterizing the influence network using the RNN cell itself is highly parameter-efficient, while the combination of virtual trajectories and low-rank perturbations satisfies the dual constraints that the estimate must represent a Jacobian and must share the same architecture.
Additionally, the consistency loss used in the probe variant serves as an unbiased estimator of the Frobenius norm; the convergence analysis and the Kronecker-sum formulation in Proposition 2 effectively link the method to OK, demonstrating that the approach is not merely a haphazard assembly of ideas. The authors are also transparent about negative results—explicitly noting that SnAp-1 learns the fastest and best, that NRTRL performs only on par with KF-RTRL on MNIST, and that the method itself is biased—which makes the work more credible than most manuscripts on RTRL approximation.
Critical weaknesses
(1) The most clear-cut empirical value proposition lies in memory usage; however, this advantage relies on amortizing shared network parameters across the batch, and there is a complete lack of measured peak GPU memory data. The right-hand panels of Figures 3 and 4 do indeed show two bars: one for the "code" itself and another for "code + shared parameters/batch size 32" (in a lighter shade). Based on the MNIST (H=128) readings, the NRTRL code size is 3,845, rising to 8,631 when including the shared parameters divided by a batch size of 32; meanwhile, the smallest baseline code size is approximately 50,048. Thus, even when amortizing the shared parameters over a batch of 32, NRTRL remains roughly 5.8 times more efficient. The direction of this comparison is valid, and I do not consider the methodology "wrong." However, there are three genuine shortcomings. First, the shared parameters themselves are substantial: deducing from the difference (8,631 − 3,845 = 4,786), the update transformer (Table 2) and the U/V matrices of the influence network total around 150,000 scalar values—roughly 40 times the size of the "code" when H=128. Second, the amortization ratio depends entirely on the batch size. With a batch size of 1, the full 150,000 scalars must be accounted for, bringing the NRTRL total to approximately 157,000; this is significantly higher than the two baselines in the 50k range and comparable only to the largest baseline (approx. 164,000). While the paper does not claim that a batch size of 1 is mandatory, the targeted online use case could involve small batches; therefore, results across a range of batch sizes should at least have been reported. Third, there is no mention of Adam’s first- and second-order moments, activations, or peak memory usage in bytes. For a paper whose core claim centers on efficiency, providing only scalar code sizes—without curves showing batch-size dependency or actual measured memory usage—is unconvincing.
(2) "OK" does not appear at all in the main experiments. OK (Benzing et al., 2019) appears in the cost table in Figure 1(a), the theoretical discussion, and the detailed derivations in Appendix E.5—where it is treated as a stronger scheme within the Kronecker family—yet it is entirely absent from Section 6. The omission of OK represents a significant gap: it belongs to the same category as NRTRL (influence approximation), and Proposition 2 in this paper explicitly demonstrates that NRTRL can be formulated as a Kronecker sum. Consequently, without a comparison, it is impossible to answer the question of "whether a learned approximation outperforms an optimized fixed-structure approximation"—which is precisely the paper's core selling point. Regarding the approaches mentioned in related work that make RTRL feasible through architectural constraints (Irie et al. 2024; Elelimy et al. 2024), their reliance on different recurrent architectures makes them not directly comparable; however, the paper should have explicitly stated this scope limitation rather than implicitly assuming it covered the entire space of approximate RTRL methods.
(3) While the per-step computational complexity is O(H²), the actual constant factors may be substantial, yet the paper provides no wall-clock time measurements. Each step requires Nprobe=5 probes, with each probe involving three JVP passes over a virtual trajectory of length K=7 (for MNIST; K=5 for PTB), in addition to the online training updates for the transformer (Algorithm 4, lines 5–6, requires recomputing z(t) after a gradient step). Under the MNIST configuration, the dominant term in Eq. 189 is approximately 6×(7Cvirt + Cphys); ignoring CU, this equates to roughly 48 times the cost of a standard O(H²) recurrent/virtual step. This suggests a potentially large constant factor compared to UORO or SnAp-1, though without empirical speed comparisons, one cannot simply claim it is "dozens of times slower." From a fairness perspective: compared to the O(H³) complexity of KF-RTRL and the O(rH³) of OK, NRTRL actually holds an asymptotic advantage for large H; nevertheless, actual speed performance still requires verification via wall-clock timing. The paper glosses over efficiency with Big O notation; lacking FLOPs, ms/step, or wall-clock training times, it is impossible to assess actual efficiency.
(4) The theory holds only for strongly contracting RNNs, and the constants involved may render the bounds vacuous. The bound in Proposition 1 (Eq. 14) is general—applying to any —and Eq. 11 explicitly separates the decoder limit from the update limit . Thus, the paper directly addresses the question of whether targets generated by the previous step's estimates might converge to an incorrect fixed point; I do not see a logical flaw there. However, there are three genuine limitations. First, the assumption () implies global contraction, effectively excluding the very regimes where RNNs most need long-range memory. Second, the factor blows up as : in practice, even if the consistency loss is minimized, the corresponding influence error bound may remain extremely loose; consequently, the paper fails to explain how effectively "consistency loss as a principled training objective" guides learning outside the strong-contraction regime. Third, Eq. 14 bounds the average influence error (Frobenius norm); linking this to the actual task gradient requires to be bounded—a step that is not discussed.
(5) The comparison protocol conflates "update frequency" with "methodological superiority." Online methods update parameters at every step, whereas TBPTT-25 updates only every 25 steps; the main text itself acknowledges that "online methods make many more updates for the same data." The MNIST experiments use only three random seeds and lack significance testing, while the curves for NRTRL and SnAp-1 on the PTB dataset are indistinguishable. Given the constant-factor overhead associated with NRTRL, this comparison hardly supports a conclusion of "higher efficiency."
(6) The update protocols differ across baselines; this discrepancy should be noted in the conclusions. Appendix I clarifies that SnAp-1 updates its sparse influence estimate at every physical step, whereas NRTRL, KF-RTRL, and UORO update only once per TBPTT window (treating the sequence of steps as a single transition). This results in a higher update frequency for SnAp-1, which may give it an advantage in comparisons. While the paper discloses that all methods utilize TBPTT windows, the issue lies not in whether a method is "sufficiently online," but in the differing update frequencies of the carried representations across baselines. This point should be explicitly stated in the interpretation of results to prevent readers from misconstruing differences in update frequency as differences in approximation quality.
The abstract states that the code size is "several orders of magnitude" smaller than the full influence matrix. While this statement is technically correct (the full matrix is on the order of , while the NRTRL code is around 3.8k–5.7k—a difference of 2–3 orders of magnitude), it is easily misinterpreted as an advantage relative to the baselines. The actual difference compared to the baselines is approximately 13–43× for MNIST and 41–114× for PTB—representing a difference of 1–2 orders of magnitude, not "several." It is recommended to explicitly state the denominator in the main text.
Questions for authors
- Once θ, η, and Adam momentum terms are all accounted for, what is the per-sequence/total peak memory usage (in bytes)? What proportion of the total memory is consumed by the O(H) code? Is it possible to provide wall-clock time and FLOPs comparisons against SnAp-1, KF-RTRL, and UORO on the same hardware?
- Why was OK not included in the experiments? How do NRTRL and OK compare in terms of accuracy, memory usage, and runtime under identical H and training budget constraints?
- Under what ranges of κ and ρ is the bound in Eq. 14 tight? To ensure the task gradient error remains controllable, to what level must the consistency loss be reduced? In the experiments actually conducted (GRU, MNIST/PTB), what were the measured values for κ, ρ, and the average consistency loss?
- Could you show the relationship between the task gradient error ‖c(t)M̂(t) − c(t)M(t)‖ and the consistency loss, rather than just the influence error? How tight is this bound in practice given the variance of the Gaussian probe?
- Can the comparison with TBPTT be performed on an update-budget-matched basis (where each method is allowed the same number of parameter updates)? Otherwise, is the "higher accuracy" simply a result of performing more updates?
2 comments
Thanks for your clarification and explanation, which help me better understand your design and claims.
We thank you for your thorough review. We cover your questions about memory, the constant factor and the update protocols in the general reply, and your questions about OK, the theory, update frequency and code size below.
OK. We acknowledge that Proposition 2 writes NRTRL's estimate as a sum of K Kronecker products, which connects it to OK. This connection is in the general form of the approximation, and the two methods are very different. OK stores the Kronecker factors, whereas NRTRL generates them from its code through the influence network. With r Kronecker products, OK needs r times the memory of KF-RTRL, which already grows quadratically with the width. We left OK out because KF-RTRL already represents this family with less memory, and OK adds implementation complexity.
A future version will clarify that this work is only about the approximations of RTRL, and that we do not want to compare to methods that make RTRL tractable.
Scope of the theory. We agree that the contraction assumption excludes long memory, and that the factor κ2/(1−ρ)2 grows as ρ approaches 1. Proposition 1 presents one setting in which the consistency loss is a principled objective, and does not claim that its assumption holds in our experiments. We believe a result under limiting assumptions is still more informative than none. A future version will state these limits explicitly, and add the step from influence error to gradient error,
∥c(t)(M(t)−M(t))∥≤∥c(t)∥∥M(t)−M(t)∥F,
which bounds the gradient error when the credit c(t) is bounded.
Update frequency. Frequent updates are the purpose of online methods, and the works we compare with use the same protocol [1, 2, 3]. Thus we believe this is not a flaw of the protocol. It shows why online update methods like ours are relevant against TBPTT. A future version will also include TBPTT over one step, which updates the parameters as often as the online methods.
Code size against the baselines. We agree. A future version will state that "several orders of magnitude" refers to the full influence matrix, and give the ratio to each baseline separately.
References
[1] A. Mujika, F. Meier and A. Steger. Approximating Real-Time Recurrent Learning with Random Kronecker Factors. NeurIPS, 2018.
[2] F. Benzing, M. M. Gauy, A. Mujika, A. Martinsson and A. Steger. Optimal Kronecker-Sum Approximation of Real Time Recurrent Learning. ICML, 2019.
[3] J. Menick, E. Elsen, U. Evci, S. Osindero, K. Simonyan and A. Graves. Practical Real Time Recurrent Learning with a Sparse Approximation. ICLR, 2021.