{"id":"cf60e14a-ecf0-4ced-8564-6743652c7188","arxiv_id":"2412.03214","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A continual inference formulation of Nyström attention that updates landmark-based low-rank attention incrementally, cutting per-step FLOPs by up to three orders of magnitude.","lead":"This paper derives a continual, streaming version of Nyström-based attention, a low-rank approximation of the standard transformer attention mechanism. It reports large reductions in per-step computation and memory for online audio, video, and electricity forecasting tasks, at some cost in accuracy.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (24) updates the inverse row-sum vector by subtracting and adding inverses of individual exponential terms; because 1/(a+b) is not 1/a+1/b, the non-updated-landmark and fixed-landmark Continual Nyströmformer outputs (Eqs. 23 and 26) are not correctly derived from Eq. (9).","rationale":"The paper's central claim is that Eq. (9) can be made continual with the displayed updates. The non-updated-landmark and fixed-landmark variants are the cheapest advertised modes, and both rely on the cached inverse row-sum vector. Eq. (24) is algebraically false: it updates reciprocals as if the reciprocal of a sum were the sum of reciprocals. The same vector is directly multiplied into the attention output in Eqs. (23) and (26), so the derivation as written does not implement Eq. (9). Eq. (19) also contains an internal inconsistency in the updated-landmark path, though this looks like a typo. The reader identified the same weakest assumption, and I agree. A corrected Eq. (24) is straightforward, so the appropriate outcome remains a conditional acceptance pending a corrected derivation and an explicit statement of which update the released code actually uses. The omitted token-buffer memory accounting noted by the reader is a separate, valid concern, but it is secondary to the algebraic error.","tokens_in":21443,"tokens_out":8133,"duration_ms":78125,"concrete_test":"Implement the update of Section IV-A2 for a random sliding window: maintain φ(Δ) and ΔV as specified, but at each step compute a reference value of φ(Δ)^{-1} by fully recomputing Δ = ρ(˜Q, K), and compare it with the value produced by Eq. (24). For any nontrivial K, the two diverge. Then rerun the Table III and Table IV fixed-landmark configurations with the corrected inverse update and check whether the reported accuracies and relative FLOPs are reproduced; this distinguishes a typographical slip from a genuine implementation bug.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing weakness is Eq. (24) in Section IV-A2. For the non-updated-landmark variant, Δ = ρ(˜Q, K) is an m×n matrix whose row sums are φ(Δ) = Δ 1_n. When the window slides, the correct row-sum recurrence is φ(Δ) = φ(Δ)_prev − ρ(˜Q, k_old) + ρ(˜Q, k_new), so the inverse row-sum vector must be updated as 1/(φ(Δ)_prev − ρ(˜Q, k_old) + ρ(˜Q, k_new)), with the reciprocal taken after the addition and subtraction. Eq. (24) instead writes φ(Δ)^{-1} = φ(Δ)^{-1}_prev − ρ(˜Q, k_old)^{-1} + ρ(˜Q, k_new)^{-1}, treating the reciprocal of a sum as a sum of reciprocals. This is false for every nontrivial window. Because φ(Δ)^{-1} is used directly in the attention outputs of Eqs. (23) and (26), and in the fixed-landmark variants of Section IV-B, the formulas as written do not compute the Nyström attention defined by Eq. (9). The same section also contains the typo in Eq. (19), where the old landmark term is written as ρ(˜Q_mem, ˜k_new) in both the subtracted and added slots, so the updated-landmark derivation is not internally consistent either. A corrected Eq. (24) is easy to write, but until the derivation is fixed or the released code is shown not to follow Eq. (24), the reported results for the non-updated and fixed-landmark variants do not establish the paper's central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Continual Nyströmformer, a continual-inference adaptation of the Nyström-based low-rank approximation of Scaled Dot-product Attention. The authors derive update rules for the B, Γ, and Δ matrices that appear in the Nyström attention formula under a sliding window, and propose two landmark-selection schemes: continually updated landmarks based on segment means, and fixed landmarks obtained by k-means clustering of training tokens followed by fine-tuning. They report asymptotic computational and memory costs, FLOPs measurements, and experiments on audio classification (GTZAN), online action detection (THUMOS14), and electricity forecasting, claiming up to three orders of magnitude FLOPs reduction relative to standard attention while retaining accuracy comparable to competing continual and Nyström-based baselines.","tokens_in":21820,"tokens_out":6072,"duration_ms":56506,"significance":"The problem of making transformer-style attention applicable to online, resource-constrained inference is timely, and the idea of extending the Nyströmformer approximation to a continually updated sliding window is a natural and potentially useful contribution. The paper also introduces a fixed-landmark variant whose memory cost, if the derivation were correct, could be attractive. The authors provide a public code repository, a detailed FLOPs analysis, and experiments on multiple tasks, which are strengths. However, the core algebraic derivation of the non-updated-landmark and fixed-landmark variants contains a load-bearing error in the inverse row-sum update, an internal inconsistency in the updated-landmark update, and the memory accounting omits the key and value buffers needed to perform the sliding-window updates. These issues must be resolved before the reported results can be taken as validating the claimed method.","major_comments":[{"comment":"Equation (24) is algebraically incorrect as the update for the inverse row-sum vector. The row sums of Δ satisfy φ(Δ) = φ(Δ)_{prev} − ρ(˜Q, k_old) + ρ(˜Q, k_new), so the correct inverse update is the elementwise reciprocal of that sum, i.e., 1/(φ(Δ)_{prev} − ρ(˜Q, k_old) + ρ(˜Q, k_new)). Equation (24) instead writes φ(Δ)^{-1} = φ(Δ)^{-1}_{prev} − ρ(˜Q, k_old)^{-1} + ρ(˜Q, k_new)^{-1}, which asserts that the reciprocal of a sum equals a sum of reciprocals. This is false for every nontrivial window. Because φ(Δ)^{-1} is used directly in Eqs. (23) and (26) and in the fixed-landmark variants of Section IV-B, the formulas as written do not compute the Nyström attention defined by Eq. (9). The reported results for the non-updated and fixed-landmark variants therefore do not establish the paper's central claim unless the released code implements the correct recurrence; the paper should be corrected and the code checked against the corrected equation.","section":"Section IV-A2, Eq. (24)"},{"comment":"Equation (19) contains an internal inconsistency: the subtracted and added terms in the first row block are both ρ(˜Q_mem, ˜k_new). Since the landmark update removes the oldest landmark ˜k_old and adds ˜k_new, the subtracted term should be ρ(˜Q_mem, ˜k_old), not another ρ(˜Q_mem, ˜k_new). As written, the update cancels these two identical terms and does not account for the eviction of the old landmark. This makes the updated-landmark derivation inconsistent with the stated landmark update in Eqs. (13)-(14).","section":"Section IV-A1, Eq. (19)"},{"comment":"The memory accounting omits the input token buffers needed to perform the sliding-window updates. For the non-updated and fixed-landmark variants, equations (24)-(25) require ρ(˜Q, k_old) and ρ(˜Q, k_new), and equation (25) additionally requires v_old and v_new. While k_new and v_new are available from the current input, k_old and v_old must have been stored from earlier tokens, so the model must maintain buffers for the key and value matrices (or equivalently for the raw token representations). The valley costs listed for AttFix_CoNySi and AttFix_CoNyRe in Table I and in Appendices O and P do not include these O(nd) buffers. The claimed valley memory of O(dm + m^2) for the fixed-landmark single-output variant is therefore understated by O(nd), which directly affects the comparisons in Figure 4 and the corresponding claims in Section V-B.","section":"Table I and Appendices O/P"}],"minor_comments":[{"comment":"The sentence \"The use of landmarks may translate into a slightly lower performance at the expense of a slightly lower performance\" is garbled; it appears that the second occurrence should refer to reduced computational cost, and the sentence should be rewritten.","section":"Conclusion, Section VI"},{"comment":"The abstract claims a reduction in the number of operations of \"up to three orders of magnitude,\" while the conclusion states \"up to two orders of magnitude.\" Table III does report a relative reduction of ×1028 for the one-layer fixed-landmark variant, so the abstract is supportable in that case, but the inconsistency should be resolved.","section":"Abstract vs. Conclusion"},{"comment":"The relative FLOPs entries \"144,04\" and \"294,35\" use commas as decimal separators, which is inconsistent with the decimal-point notation used in Tables III and IV and with the surrounding text.","section":"Table V"},{"comment":"The figure captions contain typesetting artifacts such as \"....red.......lines\" and \"...red......lines\"; these should be cleaned up.","section":"Figures 5-7 captions"},{"comment":"The description of the online action detection experimental setup is brief; in particular, the number of training frames used for the learned fixed landmarks on THUMOS14 is specified as 50,000 tokens, but no information is given about how the five data seeds were combined with model initializations to produce the reported means and standard deviations in Table IV, making the uncertainty estimates difficult to interpret.","section":"Section V-C, experimental setup"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a relevant problem and the experimental infrastructure is a useful asset, but the derivation errors in Eqs. (19) and (24) are load-bearing for the central claims. If the authors can confirm that their released code implements the correct row-sum recurrence and correct the memory accounting, a resubmission could be suitable for publication. The current manuscript as written should not be accepted without these corrections."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is a sensible idea with a real bug in the middle. The Continual Nyströmformer is the right next step after Continual Transformers, and the fixed-landmark training procedure (train with continually updated landmarks, then cluster the training tokens, then fine-tune with those landmarks frozen) is a genuinely useful contribution. The paper also gives a much more detailed FLOPs and memory breakdown than most papers in this area, and runs experiments on three tasks with multiple seeds. That part is solid.\n\nThe soft spot is the derivation in Section IV. Eq. (24) updates the inverse row-sum vector φ(Δ)^{-1} by subtracting and adding reciprocals of the individual terms. That is algebraically wrong: the reciprocal of a sum is not the sum of reciprocals. The correct update is to update φ(Δ) first and then take the reciprocal. Because φ(Δ)^{-1} is used directly in Eqs. (23) and (26), the non-updated-landmark and fixed-landmark variants as written do not compute the Nyström attention defined by Eq. (9). This is not a typo; it is a load-bearing error. Eq. (19) also has a typo (it subtracts and adds the same term), which is minor by comparison but shows the derivation section needs a careful rewrite.\n\nThe memory accounting has the same kind of issue. Table I and Appendix P claim the fixed-landmark single-output variant has valley memory O(dm + m^2), but the update in Eq. (25) requires the keys and values of the current window so you can subtract the leaving token. That means you need an n×d buffer, not just the landmarks. The claimed constant-memory property is therefore not established.\n\nOne more thing: the abstract says the method retains the predictive performance of competing models. The continual-landmark variant is roughly comparable, but the fixed-landmark variant drops noticeably on THUMOS14 (e.g., 55.5 mAP vs 64.3 for a 1-layer model). The claim should be softened.\n\nWho this is for: anyone working on continual inference or efficient attention for streaming applications. The idea is worth a serious referee. My recommendation: send it to review, but expect major revision. The authors need to fix Eq. (24), correct Eq. (19), redo the memory accounting, and either show the released code does not implement Eq. (24) or rerun the experiments with the corrected update. If the code already implements the correct update, that is an easy thing to demonstrate.","headline":"Good idea, useful fixed-landmark training trick, but the central update equation is algebraically wrong as written and the memory numbers ignore the token buffer; needs a careful revision before it can be trusted.","tokens_in":22292,"tokens_out":3820,"would_cite":false,"duration_ms":32678,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces the Continual Nyströmformer, a Nyström-based Scaled Dot-product Attention whose incremental updates process streaming tokens in linear time and cut FLOPs by up to three orders of magnitude while retaining predictive…","keywords":["Continual Inference","Scaled Dot-product Attention","Nyström approximation","low-rank attention","Transformer","landmark selection","online action detection","audio classification"],"falsifier":"Implement the fixed-landmark single-output Continual Nyströmformer on a tiny synthetic stream (e.g., $n=4$, $m=2$, $d=2$) and compare its output to the exact Nyström attention recomputed from scratch at each step; the outputs will differ whenever the departing and arriving tokens both have nonzero similarity, because Eq. (24) conflates $1/(a-b+c)$ with $1/a-1/b+1/c$. For a concrete numeric check, take a row whose row-sum moves from 1 to 0.75 to 0.5: the true updated inverse is $1/(1-0.75+0.5)=4/3$, while Eq. (24) gives $1-4/3+2=5/3$.","tokens_in":21269,"feed_emoji":"⚡","tokens_out":11369,"duration_ms":89522,"temperature":0.7,"pith_summary":"This paper tries to make Transformer attention usable in continual inference, where a model must produce a prediction for every incoming token of a stream without recomputing the whole sliding window. It introduces the Continual Nyströmformer, a Nyström-based low-rank formulation of Scaled Dot-product Attention whose per-step updates reuse cached intermediate matrices, giving linear per-step cost in the sequence length and, for the fixed-landmark single-output variant, cost independent of sequence length. The central move is to decouple the numerator and denominator of the softmax inside the Nyström approximation and update them incrementally as tokens slide through the window. In Audio Classification, Online Action Detection, and electricity forecasting experiments, the reported FLOP counts drop by up to three orders of magnitude relative to standard attention while accuracy remains comparable to the original and Continual Transformer baselines.","feed_headline":"Continual Nyströmformer cuts attention cost by up to 1000×","feed_subtitle":"A streaming-friendly Nyström attention keeps accuracy on audio and video while slashing per-step FLOPs.","key_machinery":"The load-bearing object is the Nyström approximation of the softmax attention matrix, $s(QK^\\top/\\sqrt d)\\approx s(Q\\tilde K^\\top/\\sqrt d)\\,s(\\tilde Q\\tilde K^\\top/\\sqrt d)^\\dagger\\,s(\\tilde QK^\\top/\\sqrt d)$, where $\\tilde Q,\\tilde K$ are $m\\times d$ landmark matrices and $\\dagger$ denotes the Moore–Penrose pseudo-inverse. The paper makes this object continual by splitting each softmax factor into numerator and denominator, caching the row-sum vectors $\\phi(B),\\phi(\\Gamma),\\phi(\\Delta)$ and the product $\\Delta V$, and updating them incrementally as tokens enter and leave the window. The pseudo-inverse $(\\Gamma_\\phi)^\\dagger$ is the one piece that resists incremental updating: it is recomputed with an iterative method when landmarks change, and computed once during training when landmarks are fixed.","core_discovery":"This paper's central claim is that the Nyström approximation of softmax attention can be maintained incrementally over a sliding window, making low-rank attention genuinely continual. The Continual Nyströmformer writes the attention as $\\mathrm{Att}_{\\mathrm{CoNy}}(q_{\\mathrm{new}},k_{\\mathrm{new}},v_{\\mathrm{new}}) = (B_\\phi(\\Gamma_\\phi)^\\dagger \\Delta_\\phi)V$, where $B=\\rho(Q,\\tilde K)$, $\\Gamma=\\rho(\\tilde Q,\\tilde K)$, and $\\Delta=\\rho(\\tilde Q,K)$ are exponential similarity matrices computed with $m$ landmark tokens $\\tilde Q,\\tilde K$, and the subscript $\\phi$ denotes the softmax numerator/denominator decoupling $\\Omega_\\phi=\\phi(\\Omega)^{-1}\\odot\\Omega$. When a new token arrives, the similarity matrices are updated by removing the departing token's contribution and adding the new token's; the landmark matrices themselves are refreshed every $n/m$ steps using segment means (continual landmarks) or fixed after training by clustering the training data's Q and K features (fixed landmarks). The paper argues that this yields $O(nd)$ per-step cost, and $O(dm+m^2)$ for the fixed-landmark single-output variant, with accuracy comparable to the original Transformer and Continual Transformer on the evaluated tasks.","pith_inferences":["Beyond the paper: if Eq. (24) is corrected to recompute $\\phi(\\Delta)^{-1}$ by inverting the updated row sums elementwise, the fixed-landmark and non-updated-landmark variants remain well-defined, and their reported cost savings do not depend on the erroneous identity.","Beyond the paper: the fixed-landmark variant's sequence-length-independent cost suggests a drop-in attention module for latency-critical streaming settings such as robotics control, a use the paper does not test.","Beyond the paper: the observation that a few landmarks often match full attention may reflect redundancy in audio and video token streams; evaluating the method on non-redundant inputs, such as shuffled tokens or diverse text, would test how much of the accuracy retention relies on stream redundancy.","Beyond the paper: the amortized cost of the continually updated landmarks depends on the ratio $n/m$; selecting $m$ adaptively from stream statistics could trade accuracy against computation without changing the update equations."],"forward_implications":["With the fixed-landmark single-output attention, per-step cost becomes $O(dm+m^2)$ and no longer depends on the sequence length $n$, so streams can be processed with bounded latency as the window grows.","The incremental update reuses cached numerator and denominator quantities, eliminating the $n$-fold redundant recomputation that a sliding-window Transformer performs when each frame is processed multiple times.","On GTZAN audio classification, the single-layer fixed-landmark model reports a relative FLOP reduction of about $1000\\times$ versus standard attention, at 90.76% accuracy versus 93.12% for the original attention baseline.","Because every intermediate layer is itself a Nyström layer, more Transformer layers can be stacked with lower computational overhead than in Continual Transformers, whose intermediate layers use full attention.","The same decouple-and-update pattern is proposed as a template for adapting other low-rank attention approximations to continual inference."],"supporting_citations":[{"why":"Defines the Scaled Dot-product Attention whose quadratic cost the paper aims to reduce in continual settings.","marker":"[1]"},{"why":"Establishes the Nyström approximation for Gram matrices that underlies the low-rank attention approximation.","marker":"[17]"},{"why":"Supplies the Nyströmformer formulation and segment-means landmark scheme that the continual updates adapt.","marker":"[19]"},{"why":"Defines Continual Inference and the redundant-free processing principle used to derive the incremental updates.","marker":"[27]"},{"why":"Provides the Continual Transformer attention updates (retroactive and single output) that the paper extends with Nyström landmarks.","marker":"[31]"},{"why":"Justifies using cluster centers as landmarks, the basis of the proposed fixed-landmark training procedure.","marker":"[43]"},{"why":"Gives the iterative algorithm used to compute the Moore–Penrose pseudo-inverse of the landmark similarity matrix when landmarks are updated.","marker":"[44]"}],"fun_headline_variants":["Nyström attention goes streaming: up to 1000x cheaper","Continual low-rank attention: 1000x fewer ops, same accuracy","Streaming Nyström attention cuts FLOPs by 1000x","Low-rank attention made continual, costs 1000x less"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that Eq. (24) correctly updates the inverse row-sum vector $\\phi(\\Delta)^{-1}$ by subtracting and adding inverses of individual exponential terms; this is algebraically false, since the inverse of a sum is not the sum of inverses, and the fixed-landmark and non-updated-landmark variants rely on that update.","fun_headline_variants_meta":{"raw":{"variants":["Nyström attention goes streaming: up to 1000x cheaper","Continual low-rank attention: 1000x fewer ops, same accuracy","Streaming Nyström attention cuts FLOPs by 1000x","Low-rank attention made continual, costs 1000x less"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000605,"raw_usage":{"total_tokens":2845,"prompt_tokens":990,"completion_tokens":1855,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":606,"completion_tokens_details":{"reasoning_tokens":1783}},"tokens_in":606,"tokens_out":1855,"duration_ms":12641,"temperature":1.0,"reasoning_tokens":1783,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T22:39:33.126058+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement the fixed-landmark single-output Continual Nyströmformer on a tiny synthetic stream (e.g., $n=4$, $m=2$, $d=2$) and compare its output to the exact Nyström attention recomputed from scratch at each step; the outputs will differ whenever the departing and arriving tokens both have nonzero similarity, because Eq. (24) conflates $1/(a-b+c)$ with $1/a-1/b+1/c$. For a concrete numeric check, take a row whose row-sum moves from 1 to 0.75 to 0.5: the true updated inverse is $1/(1-0.75+0.5)=4/3$, while Eq. (24) gives $1-4/3+2=5/3$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the Nyström approximation for Gram matrices that underlies the low-rank attention approximation."},{"cited_title":"Nystr ¨omformer: A nystr ¨om- based algorithm for approximating self-attention","cited_arxiv_id":null,"evidence_quote":"Supplies the Nyströmformer formulation and segment-means landmark scheme that the continual updates adapt."},{"cited_title":"Continual inference: A library for efficient online inference with deep neural networks in pytorch","cited_arxiv_id":null,"evidence_quote":"Defines Continual Inference and the redundant-free processing principle used to derive the incremental updates."},{"cited_title":"Con- tinual transformers: Redundancy-free attention for online inference","cited_arxiv_id":null,"evidence_quote":"Provides the Continual Transformer attention updates (retroactive and single output) that the paper extends with Nyström landmarks."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Justifies using cluster centers as landmarks, the basis of the proposed fixed-landmark training procedure."},{"cited_title":"Razavi, A","cited_arxiv_id":null,"evidence_quote":"Gives the iterative algorithm used to compute the Moore–Penrose pseudo-inverse of the landmark similarity matrix when landmarks are updated."}],"review_version":1}