REVIEW 3 major objections 4 minor 19 references
An Uncertainty Principle for Linear Recurrent Neural Networks
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper proves that recalling an input from $K$ steps back with a linear RNN of size $S$ is governed by the ratio $S/K$: the best white-noise error is $1 - S/(K+1)$ up to constants, and the optimal filter blurs over a window of width…
desk verdict A clean, mostly sound asymptotic characterization of the shift-K copy task for linear RNNs, but the advertised uncertainty principle about the optimal filter's width is only proven for one explicit construction, not for all near-optimal filters. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the rational transfer function of a diagonal linear RNN, $C(e^{i\omega}) = \sum_s b_s/(1 - a_s e^{-i\omega})$, whose coefficients $c_k = \sum_s b_s a_s^k$ are the convolution kernel. For fixed eigenvalues $a_s$, the optimal output weights solve a quadratic form defined by the $S \times S$ matrix $C_{ss'} = 1/(1 - a_s \bar a_{s'})$, a Cauchy-type matrix with displacement structure; the paper inverts this matrix explicitly and uses the resulting Blaschke-product identities to bound the best achievable accuracy. The matching construction places the poles uniformly on a circle of radius $e^{-\alpha/K}$ with angular spacing $\pi/K$, so that each partial fraction term captures one oscillation of the target frequency response $e^{-iK\omega}$. Alternating-series remainder estimates and a Toeplitz eigenvector computation then yield the asymptotic optimal weights and the loss formula. The frequency windowing of this filter is what produces the time-domain blur.
What would settle it
For a concrete pair such as $S=50$ and $K=200$ with white noise, run the exact convex optimization over $b$ for a fine grid of poles $a$, or measure the full width at half height of the best filter learned by gradient descent; if any filter beats $1 - S/(K+1)$ or the width does not scale roughly like $K/S$ as $S$ and $K$ are varied, the central claim fails.
Extended reading notes
Core claim
On the paper's own terms, the discovery is that the shift-$K$ copying problem for a diagonal linear RNN is governed by the ratio $S/K$ and nothing else, up to constants. Theorem 2 shows that for white noise, every filter of the form $c_k = \sum_{s=1}^S b_s a_s^k$ has mean-square error at least $1 - S/(K+1)$ when asked to reproduce the delta filter $d_k = \mathbf{1}_{k=K}$. Theorem 4 constructs an explicit filter with poles $a_s = \exp(-\alpha/K)\exp(i\pi s/K)$ and weights $b_s \propto (-1)^s$ whose loss is asymptotically $1 - e^{-2\alpha}(e^{2\alpha}-e^{-2\alpha})S/(2K)$, so the lower bound is attained up to a constant factor. The same construction converges in frequency to an ideal window of width $\pi S/K$: inside it the transfer function reproduces $e^{-iK\omega}$, outside it vanishes, and therefore the time-domain filter is a smoothed copy with width $K/S$. For autoregressive inputs with correlation $\rho$, the paper proves a matching lower bound $\left(1 - \frac{3S}{K(1-\rho)}\right)_+$, showing that correlated inputs directly buy memorization precision. It also observes that its near-optimal pole placement coincides, at $\alpha = 1/2$, with the widely used gridded diagonal initialization with step $1/K$, giving a task-level explanation for that initialization.
Load-bearing premise
The upper bound and the closed-form output weights are proven asymptotically, in the regime where both $S$ and $K$ grow large with $S/K$ tending to zero; the constant factors and the predicted window width $K/S$ are not guaranteed at moderate ratios.
Editorial extensions
If this is right
- Exact copying with white noise requires $S$ at least $K$; below that, an error of at least $\sim 1 - S/K$ is unavoidable for any diagonal linear RNN.
- For fixed $S$, doubling the recall horizon $K$ roughly doubles the minimum error until $S = K$, and the recovered signal is an average over a window of width $\sim K/S$ around the target time.
- The explicit near-optimal filter gives a principled initialization: poles on a circle with phase step $\pi/K$ and magnitude $e^{-\alpha/K}$, which with $\alpha = 1/2$ is exactly a commonly used diagonal state-space initialization with step $1/K$.
- With autocorrelated inputs (correlation $\rho$), the same construction achieves much smaller error, since the effective frequency window narrows; the bound grows like $\left(1 - \frac{3S}{K(1-\rho)}\right)_+$.
- The frequency-domain picture predicts that a linear RNN approximates the shift filter only on a band of width $\sim S/K$; inputs with energy outside that band are essentially ignored.
Reading between the lines
- A natural extension is to finite-vocabulary copying: if the same $S/K$ law holds for discrete tokens, state width must grow linearly with the recall distance for reliable retrieval, which would align with earlier lower bounds for perfectly retrieving distant tokens.
- The windowing mechanism suggests a testable prediction for band-limited inputs: when the input power spectrum occupies only a few frequencies, effective resolution should improve beyond $K/S$, since the filter only needs to match the target on that spectrum; this could be checked by measuring copy accuracy on filtered noise.
- For input-dependent or gated linear recurrences, one might ask whether the same tradeoff persists or whether adaptivity can break the fixed-window blur; measuring the width at half height of learned shift filters across $(S, K)$ would settle it.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies how well a diagonal linear RNN with S hidden states can approximate the shift-K filter (delayed copy) under an expected quadratic loss on stationary inputs. For white noise the authors prove a lower bound on the best possible error of at least 1 - S/(K+1) (Theorem 2), and for AR(1) inputs with correlation rho they prove a lower bound of order (1 - (3S)/(K(1-rho)))_+ (Theorem 3). They then construct an explicit near-optimal filter with poles a_s = exp(-alpha/K) exp(i pi s/K) and coefficients b_s proportional to (-1)^s (Eqs. (12)-(13)), prove an asymptotic upper bound matching the lower bound up to a constant in the regime S,K -> infinity with S/K -> 0 (Theorem 4), and analyze its transfer function, showing convergence to a rectangular frequency window of width proportional to pi S/K (Theorem 5). The paper interprets these results as an uncertainty principle: the optimal filter must average around lag K with width K/S. It also connects the pole placement to the S4D-Lin initialization and reports experiments on autoregressive copy tasks.
Significance. If the main claims are taken in the right scope, this is a valuable contribution. The lower bound is obtained from independent rational-approximation and Cauchy-matrix techniques, and the upper bound is an explicit, parameterized construction rather than an existence statement; the closed-form filter also gives a concrete theoretical rationale for the phase-magnitude coupling in S4D-Lin. The matching of the lower and upper bounds up to constants in the asymptotic regime is a clean and nontrivial result. However, the paper's headline 'uncertainty principle' is stated as a property of the optimal filter, whereas the proofs concern the constructed filter; this overstatement, together with an error in the statement of Theorem 5 near the window edge, needs to be fixed before the paper can be accepted.
major comments (3)
- [Abstract; Sec. 1; footnote 3] The claim that 'the optimal filter has to average values around the K-th time step with width K/S' is not implied by the proven results. Theorem 2 is a lower bound on the minimal L2 error, and Theorems 4 and 5 analyze one explicit filter (Eqs. (12)-(13)), showing that this filter has a rectangular transfer function of width pi S/K. Nothing in the lower-bound proof (Appendix C.1) or in the matching upper bound rules out an equally good filter whose time-domain energy is localized differently, for example with a narrower main lobe and compensating side lobes, because the L2 distance to the delta filter is not a measure of localization. The paper should either prove a lower bound on the width of every near-optimal filter or restate the result as an existence/construction statement about a filter that achieves the optimal error rate. In addition, the informal phrasing 'for K > S' in Sec. 1 goes beyond the asymptotic regime S,K -> infinity, S/K -> 0 in which Theorem 4 is proved; no finite-ratio width guarantee is provided.
- [Theorem 5; Appendix D.4, Lemma 9] The formula in Theorem 5 for |Omega| > T is not well-defined. For any Omega in (T, T+1), one has floor(Omega) = T, so the denominator (floor(Omega) - T)(floor(Omega) + T) vanishes while the numerator is finite, giving an infinite claimed limit for a transfer function that is finite. The proof's use of Lemma 6 with a summation index of n - T = 0 invalidates the tail estimate in exactly this transition region. The theorem needs either an explicit exclusion of a neighborhood of the window edge or a separate transition-region asymptotic. Since this theorem is the mathematical basis for the 'rectangular window' and the K/S width interpretation, this is not a purely cosmetic issue.
- [Appendix D.2, Eqs. (22)-(23)] The perturbation estimates used to prove Lemma 1 are too terse as written. The expression after the factor 1/K contains the term (-1)^T [alpha/3 - i pi s/6], which is O(T), not O(1), and the subsequent claim '= O(1)' is therefore inconsistent. The alternating sum involving epsilon_{s'} also requires a uniform remainder bound rather than a termwise o(1) statement. These estimates are load-bearing because they lead to the coordinate-wise conclusion b = C^{-1} a^K ~ (e^{2 alpha} - e^{-2 alpha})/(2K) z. Please replace the o(1)/O(1) statements with explicit, uniform bounds in S and K, or state more precisely the conditions under which the asymptotic expansion holds.
minor comments (4)
- [Sec. 1, contributions bullet] The white-noise lower bound is quoted as 1 - S/K, while Theorem 2 states 1 - S/(K+1); unify these expressions so the reader is not left with a discrepancy.
- [Sec. 5.2] The idealized frequency-domain filter is written as 1_{|omega| <= 2 pi S/K}, but the integral immediately below is over +/- pi S/(2K). The relationship between this window and the pi S/K window of Theorem 5 should be clarified, and the factors should be made consistent.
- [Lemma 1] The lemma statement says 'asymptotic optimal parameters (when K -> +infinity)', but the proof requires T -> infinity and S/K -> 0 as well. State the full asymptotic regime in the lemma.
- [Theorem 4] The notation L_time(c,d) ~ ... with a right-hand side that still depends on S and K should specify the limit explicitly, e.g., as S,K -> infinity with S/K -> 0; the intended meaning is clear from the text but should be part of the statement.
Circularity Check
No circular derivation; the matching upper bound is a legitimate construction, though the uncertainty-principle wording overstates what the theorems prove.
full rationale
The paper's main results do not reduce to their inputs. Theorem 2 is a genuine lower bound: it starts from the exact quadratic loss (Eq. 8), eliminates b in closed form via C^{-1}, and bounds the resulting F_K using the displacement structure of the Cauchy-type matrix and rational-approximation tools from Baratchart et al. and Yang. The target δ_K enters only as the objective to be approximated, not as an assumed conclusion. Theorem 4 is an explicit construction: the filter a_s = exp(-α/K) exp(iπs/K) and b_s from Eq. (13) is chosen to match the lower bound, and the paper says so directly: 'This is how we designed it, to catch up with the lower bound.' That is a legitimate matching construction, not a fitted input renamed as a prediction. The scalar α is hand-chosen for stability, not estimated from data, and the asymptotic error formula (Eq. 15) is a computed consequence of the explicit filter, not a fitted curve. Self-citations to S4D-Lin, HiPPO, and Orvieto et al. are contextual and post-hoc; the load-bearing mathematical ingredients are external (Baratchart et al. 2016; Yang 2003). The only notable gap is that the informal claim 'the optimal filter has to average values around the K-th time step with width proportional to K/S' is stronger than what is proven: the theorems establish the error scaling and describe the width of the explicit near-optimal filter, but they do not prove that every near-optimal filter must have that localization. This is an overstatement of the theorem's strength, not circularity, because the derivation never assumes the width conclusion to obtain the error bounds.
Assumptions & free parameters
free parameters (1)
- alpha =
chosen as 1 in experiments, 1/2 for S4D-Lin match
assumptions (4)
- domain assumption The input is an infinite-length stationary process with autocorrelation gamma(k)=rho^|k|, and the loss is the expectation at a single time step, equivalent to the time average by the law of large numbers.
- domain assumption The recurrence matrix A is diagonalizable and the RNN is reduced to diagonal form A=diag(a) without loss of generality, justified by a measure-zero perturbation argument for non-diagonalizable matrices.
- standard math Classical results in rational approximation on the unit circle (Baratchart et al. 2016), Cauchy-Vandermonde displacement structure (Yang 2003), Dirichlet's theorem, and Parseval's theorem are assumed.
- ad hoc to paper The asymptotic expansions in Lemma 1 and Theorem 4 assume 1 << S << K with S/K to 0 and rely on the boundedness of the condition number of the Cauchy-type matrix C and on alternating-series remainder estimates.
Cite this review
Pith. "Pith review of An Uncertainty Principle for Linear Recurrent Neural Networks." pith.science (2026). https://pith.science/paper/5BLKGXCA
@misc{pith2026250209287,
author = {Pith},
title = {Pith review of: An Uncertainty Principle for Linear Recurrent Neural Networks},
year = {2026},
howpublished = {\url{https://pith.science/paper/5BLKGXCA}},
note = {Machine review of arXiv:2502.09287}
}
abstract
We consider linear recurrent neural networks, which have become a key building block of sequence modeling due to their ability for stable and effective long-range modeling. In this paper, we aim at characterizing this ability on a simple but core copy task, whose goal is to build a linear filter of order $S$ that approximates the filter that looks $K$ time steps in the past (which we refer to as the shift-$K$ filter), where $K$ is larger than $S$. Using classical signal models and quadratic cost, we fully characterize the problem by providing lower bounds of approximation, as well as explicit filters that achieve this lower bound up to constants. The optimal performance highlights an uncertainty principle: the optimal filter has to average values around the $K$-th time step in the past with a range~(width) that is proportional to $K/S$.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
The hidden attention of Mamba models
Ameen Ali, Itamar Zimerman, and Lior Wolf. The hidden attention of Mamba models. arXiv preprint arXiv:2403.01590,
-
[3]
We have the following equality: +∞X L=0 L|wl|2 = i 2π Z 2π 0 dW (ω) dω W (ω)dω
Let wn be a causal discrete-time complex-valued signal with Fourier transform W (ω). We have the following equality: +∞X L=0 L|wl|2 = i 2π Z 2π 0 dW (ω) dω W (ω)dω. 25 Proof. By definition of the DTFT, W (ω) = P+∞ L=0 wLe−iωL. Therefore, +∞X L=0 L|wL|2 = +∞X L=0 LwL ¯wL = 1 2π +∞X L=0 +∞X L′=0 LwL ¯wL′ Z 2π 0 e−iω(L−L′)dω = i 2π Z 2π 0 +∞X L=0 −iLωLe−iLω ...
work page 2017
-
[4]
In the white noise case, the correlation factor ρ is null. The loss Ltime(c, d) writes Ltime(c, d) = 1 + +∞X k=0 |ck|2 − 2Re +∞X k=0 ckdk , where ck = PS s=1 ak s bs. Therefore, the loss writes Ltime(c, d) = 1 + SX s,s′ bs¯bs′ 1 − as¯as′ − 2Re SX s=1 bsaK s . Proof. On the one hand, +∞X k=0 |ck|2 = +∞X k=0 SX s=1 ak s bs = +∞X k=0 SX s=1 SX s′=1 ak s ¯ak ...
work page 2003
-
[5]
In-context learning and induction heads
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. In-context learning and induction heads. arXiv preprint arXiv:2209.11895,
-
[6]
Byte latent transformer: Patches scale better than tokens
Artidoro Pagnoni, Ram Pasunuru, Pedro Rodriguez, John Nguyen, Benjamin Muller, Margaret Li, Chunting Zhou, Lili Yu, Jason Weston, Luke Zettlemoyer, et al. Byte latent transformer: Patches scale better than tokens. arXiv preprint arXiv:2412.09871,
-
[8]
HGRN2: Gated linear RNNs with state expansion
19 Zhen Qin, Songlin Yang, Weixuan Sun, Xuyang Shen, Dong Li, Weigao Sun, and Yiran Zhong. HGRN2: Gated linear RNNs with state expansion. arXiv preprint arXiv:2404.07904,
-
[9]
Provable benefits of complex parameterizations for structured state space models
Yuval Ran-Milo, Eden Lumbroso, Edo Cohen-Karlik, Raja Giryes, Amir Globerson, and Nadav Cohen. Provable benefits of complex parameterizations for structured state space models. arXiv preprint arXiv:2410.14067,
-
[11]
Mimetic initialization helps state space models learn to recall.arXiv preprint arXiv:2410.11135,
Asher Trockman, Hrayr Harutyunyan, J Zico Kolter, Sanjiv Kumar, and Srinadh Bhojanapalli. Mimetic initialization helps state space models learn to recall.arXiv preprint arXiv:2410.11135,
Show all 19 references
-
[13]
Li, Madian Khabsa, Han Fang, and Hao Ma
Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04768,
2006 arXiv
-
[14]
Gated linear at- tention transformers with hardware-efficient training
Songlin Yang, Bailin Wang, Yikang Shen, Rameswar Panda, and Yoon Kim. Gated linear at- tention transformers with hardware-efficient training. In International Conference on Machine Learning, 2024a. Songlin Yang, Bailin Wang, Yu Zhang, Yikang Shen, and Yoon Kim. Parallelizing l...
-
[15]
In particular it fully describes a linear time-invariant system
(17) This signal is useful because the response of a system to a impulse signal gives a lot of insights. In particular it fully describes a linear time-invariant system. For more on signal processing, we refer the reader to Oppenheim et al. (1996). B.1 Linear Time-invariant sy...
1996
-
[18]
Then, +∞X s=−∞ (−1)s 2α − iπs = 2 e2α − e−2α . 6This is due to the link between eigenvalues of Toeplitz matrices and the Fourier series of the first row Gray (2006), and the relationship Css′ = 1 1−exp(−2α/K) exp(iπ(s−s′)/K) ∼ K 2α−iπ(s−s′) together with Eq. (21). 39 0 5000 10...
2006
-
[19]
bu = e−α(e2α−e−2α) 2Kinit × (−1)u bu = e−α(e2α−e−2α) 2Kinit × (−1)u α 1 1 Kinit 1300 1300 Number epochs 60 60 Table E.1: Experimental details for Figure 4 (left)
au = e−α/Kinite iu π Kinit bs param. bu = e−α(e2α−e−2α) 2Kinit × (−1)u bu = e−α(e2α−e−2α) 2Kinit × (−1)u α 1 1 Kinit 1300 1300 Number epochs 60 60 Table E.1: Experimental details for Figure 4 (left). We use [. . .] to denote hyperparameters that were scanned over with grid sea...
2000
-
[1996]
Training deep nets with sublinear memory cost
Tianqi Chen, Bing Xu, Chiyuan Zhang, and Carlos Guestrin. Training deep nets with sublinear memory cost. arXiv preprint arXiv:1604.06174,
-
[2013]
Eagle and Finch: RWKV with matrix-valued states and dynamic recurrence
Bo Peng, Daniel Goldstein, Quentin Anthony, Alon Albalak, Eric Alcaide, Stella Biderman, Eu- gene Cheah, Xingjian Du, Teddy Ferdinan, Haowen Hou, et al. Eagle and Finch: RWKV with matrix-valued states and dynamic recurrence. arXiv preprint arXiv:2404.05892,
-
[2017]
An empirical study of Mamba-based language models
Roger Waleffe, Wonmin Byeon, Duncan Riach, Brandon Norick, Vijay Korthikanti, Tri Dao, Al- bert Gu, Ali Hatamizadeh, Sudhakar Singh, Deepak Narayanan, et al. An empirical study of Mamba-based language models. arXiv preprint arXiv:2406.07887,
-
[2020]
Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context
Gemini Team, Petko Georgiev, Ving Ian Lei, Ryan Burnell, Libin Bai, Anmol Gulati, Garrett Tanzer, Damien Vincent, Zhufeng Pan, Shibo Wang, et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv preprint arXiv:2403.05530,
-
[2022]
Smith, Anushan Fernando, Aleksandar Botev, George Cristian-Muraru, Albert Gu, Ruba Haroun, Leonard Berrada, Yutian Chen, Srivatsan Srinivasan, et al
Soham De, Samuel L. Smith, Anushan Fernando, Aleksandar Botev, George Cristian-Muraru, Albert Gu, Ruba Haroun, Leonard Berrada, Yutian Chen, Srivatsan Srinivasan, et al. Griffin: Mixing gated linear recurrences with local attention for efficient language models.arXiv preprint ...
-
[2024]
Flashattention-2: Faster attention with better parallelism and work partitioning
Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.08691,
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.