{"id":"24a71c5b-049b-45f3-a01e-041d7fbf694f","arxiv_id":"2505.19488","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"Frames the Transformer as associative memory, derives retrieval SNR for linear, softmax, ReLU, and SoLU kernels, and proposes DeltaFormer, a softmax-plus-delta-rule variant claimed to exceed TC0 expressivity.","lead":"A ByteDance team views Transformers as associative memory: attention acts as short-term contextual recall and feed-forward networks as long-term knowledge storage, and they add a retrieval noise analysis to explain why softmax attention works. They propose DeltaFormer, a softmax-attention variant that writes memory with a delta rule, which they claim can track state exchange beyond standard Transformer expressivity.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'surpasses TC0' claim is an upper-bound inference: Theorem 1 shows DeltaFormer can solve a tracking task, but the paper never shows that task is outside TC0; since TC0 vs NC1 is open, the separation does not follow.","rationale":"The reader's conditional verdict is appropriate. The paper contains a useful associative-memory framing, internally consistent SNR derivations, and a constructive state-tracking theorem with supporting toy experiments. However, the central expressivity claim overreaches: Theorem 1 is only an upper-bound construction, and the leap to 'surpasses TC0 and theoretically reaches NC1' requires a lower bound that the tracking task is outside TC0. The paper does not provide one, and the TC0 vs NC1 question is open, so the claim cannot be accepted as stated. The reader's weakest assumption correctly flags this missing lower bound alongside the strong assumptions on f and near-orthogonal keys; my stress-test agrees that the lower-bound gap is the most decisive issue. I would keep the reader's conditional verdict: the paper's other contributions can stand, but the strongest claim must be fixed or removed.","tokens_in":37639,"tokens_out":6423,"duration_ms":60389,"concrete_test":"Take the tracking task underlying Theorem 1 (input: a sequence of transpositions on n labeled tokens; output: the current token at a fixed position) and determine whether it is computable by a polynomial-size, constant-depth threshold-circuit family. Concretely, connect it to the word problem over S5: Barrington's theorem makes this problem NC1-complete under AC0 reductions, so exhibiting a TC0 circuit for it would imply TC0 = NC1 and would directly falsify the paper's separation claim. The test is therefore to write down such a TC0 circuit or, failing that, to locate the cited lower bound in the paper; if neither can be done, the 'surpasses TC0' statement must be retracted or downgraded to 'DeltaFormer can solve a nontrivial tracking task.'","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing flaw is in Sec. 2.2.1's expressivity conclusion. The paper proves (Appendix E, Theorem 1) that a DeltaFormer-type recurrence with a rounding-like kernel f can track n states under nearly orthogonal keys and hand-constructed assignments k_t = k_{t1} - k_{t2}, v_t = 0. That is an upper bound: it shows one problem is solvable by DeltaFormer. From this alone the paper concludes that DeltaFormer 'surpasses TC0 and theoretically reaches NC1.' This does not follow. A separation requires a matching lower bound that the tracked task is not in TC0, and the paper provides none. The task is iterated permutation composition; for n = 5 the underlying group is S5, whose word problem is NC1-complete under AC0 reductions (Barrington). Proving this task lies outside TC0 would settle TC0 vs NC1, which is open. Thus the strongest claim is not merely unproven; it is a non-sequitur. Moreover, the construction relies on an exact f constant on neighborhoods of {-1, 0, 1, 2} and on d = O(log n) near-orthogonal keys; the experiments in Fig. 5 hand-set orthogonal keys and only train the readout, so they do not rescue the learned-projection claim. The paper should either remove the TC0-surpassing claim or supply the missing lower-bound argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes that Transformer components—self-attention and FFNs—can be understood as associative memories, and it develops this view along two axes: memory capacity and memory update. For capacity, it introduces an inverse SNR metric under i.i.d. Gaussian keys/values and uses a kernel perspective to argue that the softmax/exponential kernel offers much higher retrieval precision than linear or ReLU kernels. For update, it presents a general recurrent form S_t = A_t S_{t-1} B_t + C_t and constructs matching optimization objectives, then interprets linear attention, DeltaNet, gated attention, and softmax attention as special cases. This leads to a new model, DeltaFormer, which combines softmax-style kernels with a delta-rule update. The paper claims that DeltaFormer can track the exchange of n elements and therefore 'surpasses TC0 and theoretically reaches NC1.' It also argues that infinite-context in-context learning may degrade because the memory update objective shrinks as t grows. Experiments include a GPT-2 head-count study, swap-tracking tasks, a DAG reachability task, and stress tests with hand-set orthogonal keys.","tokens_in":37939,"tokens_out":6797,"duration_ms":63593,"significance":"The paper is thought-provoking and clearly written in many places. Its strongest assets are the concrete DeltaFormer proposal (Eqs. 41–42), the reproducible toy experiments and code in Appendix E.4, and the generally honest labeling of exploratory claims. The SNR analysis in Section 2.1 offers a useful heuristic for kernel design and makes falsifiable predictions about dimension scaling, temperature, and multi-head trade-offs. If the expressivity claim were established, the result would be significant for the theory of recurrent memory architectures, since it would show a concrete architecture combining softmax retrieval with delta-rule writes can track states with O(log n)-dimensional keys. However, as it stands, the paper's central separation claim is not supported, and several idealizations are unvalidated; the contribution is best viewed as a position paper with preliminary evidence rather than a formal proof of new complexity-theoretic results.","major_comments":[{"comment":"The statement that DeltaFormer 'surpasses TC0 and theoretically reaches NC1' does not follow from Theorem 1. Theorem 1 in Appendix E is an upper bound: it constructs a DeltaFormer recurrence that can track n elements under specific assumptions. It contains no lower bound showing that the tracking problem is outside TC0. Since separating TC0 from NC1 is an open problem in circuit complexity, and tracking n elements (iterated permutation composition, e.g., S5) is NC1-complete under AC0 reductions, the claimed separation would imply a major open result. This claim must be removed or supported by a matching lower-bound argument.","section":"Section 2.2.1, 'Model Expressivity' paragraph after Eq. (43)"},{"comment":"The construction in Theorem 1 requires d = O(log n) near-orthogonal keys, a rounding-like function f that is constant on neighborhoods of {-1, 0, 1, 2}, and hand-set assignments k_t = k_{t1} - k_{t2} and v_t = 0. The experiments in Figure 5 fix orthogonal keys and train only the readout, so they do not verify that learned projections W_k and W_v can realize these assignments. The expressivity conclusion is therefore conditional on an unverified representational assumption. Please either prove realizability by the model's learned projections or state the claim as conditional.","section":"Appendix E, Assumptions 1–2 and E.2; Section 3.2 stress test"},{"comment":"The inverse-SNR formulas are derived under i.i.d. Gaussian keys and values and by omitting the softmax denominator (Eq. 3 states 'we ignore the normalization term'). These assumptions are not validated for trained transformers, where keys are learned and the normalization term affects retrieval. Consequently, the abstract's claim that the analysis 'mathematically reveals why Softmax Attention is so effective' overstates what is proven. I recommend framing this as an analysis under idealized assumptions and adding empirical validation of the predicted scaling behavior.","section":"Section 2.1.1, Eq. (13), and Appendix A"}],"minor_comments":[{"comment":"The paper describes itself as 'a blog-style sharing' rather than a formal research paper, yet it makes formal theorem claims. Please reconcile this framing with the journal format and ensure all technical claims receive the same rigor as a standard submission.","section":"Page 3, footnote 1"},{"comment":"The symbol k_t is used both for the current key at time t and for the constructed difference k_{t1} - k_{t2} in the proof. Using different notation (e.g., p_t for the difference key) would improve readability.","section":"Section 2.2.1 and Theorem 1"},{"comment":"The final expression SNR^{-1}_SoLU ≈ 5N/(d_k exp(2√d_k)) drops the constant exp(2) that appears when substituting τ = √d_k into exp(-2(τ - 1)); state explicitly that O(1) constants are omitted.","section":"Appendix A, SoLU derivation"},{"comment":"The caption says '⌊·⌋ means round to two decimal,' but the code in Appendix E.4 uses x.round(), which rounds to the nearest integer. Please align the description with the implementation.","section":"Section 3.2, Figure 4 caption"},{"comment":"The sentence 'Both any element of λ and η ∈ (0, 1)' is ungrammatical; it should be 'Each element of λ and η lies in (0, 1).'","section":"Table 2"}],"recommendation":"major_revision","confidential_remarks":"The main technical claim—that DeltaFormer surpasses TC0 and reaches NC1—is not supported by the proof, and the gap is not a minor detail: it requires either a lower bound that is currently an open problem or a substantial rephrasing of the result. The paper's own footnote describing it as a blog-style post suggests the authors may not intend the same standard as a journal article; if the venue accepts position papers, the claims should be correspondingly qualified. No concerns about citation practice or novelty disclosure beyond the need to more clearly distinguish DeltaFormer from existing delta-rule-plus-kernel variants such as DeltaProduct and Titans."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—worth a look, but read the expressivity claim with a skeptical eye. The DeltaFormer construction is the real contribution: Eqs. 41–42 give a clean way to combine a softmax readout with a delta-rule write, and the state-exchange theorem shows a single-layer recurrence can track n states with O(log n)-dimensional keys under near-orthogonal key assumptions. The proof is constructive, the toy experiments (including the hand-set orthogonal key stress test) back the existence claim, and the code is shipped. The SNR comparison across linear, ReLU, exp, and SoLU kernels is also internally consistent under the stated i.i.d. Gaussian assumptions; as a design heuristic it is plausible. The unified update framework in Table 2 is a useful organizing device, even if the optimization-objective column is post-hoc by construction.\n\nThe soft spot is the 'surpasses TC0 and theoretically reaches NC1' conclusion. It does not follow. The theorem proves an upper bound: DeltaFormer can solve a tracking task. It does not prove the task is outside TC0. In fact, for n=5 the task is essentially the S5 word problem, which is NC1-complete under AC0 reductions (Barrington); proving it is outside TC0 would settle TC0 vs NC1, which is open. So that claim is not just unproven—it is a non-sequitur. Same for the DAG reachability remark: matrix inversion is not a complexity class argument. The paper also leans on assumptions (exact rounding-like f, O(log n) near-orthogonal keys, hand-constructed k_t = k_{t1} - k_{t2}) that are not validated for learned projections; the stress-test experiments hand-set the keys and only train the readout, so they do not rescue that gap. The SNR analysis also drops the softmax denominator, which is fine for a toy model but should be flagged as a departure from trained attention.\n\nDespite the overclaim, this is a serious-minded paper. The authors explicitly call it a reflection, they engage with the relevant literature, and the DeltaFormer state-tracking result is worth keeping in mind. Anyone working on linear attention, state-space models, or associative memory will get value from the framing and the construction. My recommendation: treat it as a workshop-level contribution. Do not desk-reject it, but do not accept the circuit-complexity claim as-is. It needs either a corrected statement (e.g., 'DeltaFormer can solve a tracking task that standard constant-depth Transformers are not known to solve') or a real lower-bound argument. I would send it to a reviewer with a note to focus on the proof and the assumptions.","headline":"A clever DeltaFormer construction and useful SNR heuristics, marred by an expressivity claim that is a non-sequitur.","tokens_in":38502,"tokens_out":2772,"would_cite":true,"duration_ms":24792,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"Transformers are associative memories; a delta-rule variant with softmax retrieval provably tracks n states using O(log n)-dimensional keys, exceeding the TC0 expressivity of standard Transformers.","keywords":["associative memory","Transformer","retrieval SNR","attention kernel","delta rule","expressivity","circuit complexity","in-context learning"],"falsifier":"Train a single-layer DeltaFormer end-to-end on the swap-tracking task (n = 5 elements, 16 swaps) from random initialization and token embeddings, with key dimension d = 3-4 and no hand-set orthogonal keys; if the model cannot reach 100% accuracy while a hand-wired construction with orthogonal keys does, then the theorem's assumptions are not satisfied by learned representations. Alternatively, test tracking n = 128 elements with learned keys at d = 7; failure there would show the $O(\\log n)$ dimension requirement is not learnable.","tokens_in":37360,"feed_emoji":"🧠","tokens_out":12494,"duration_ms":96994,"temperature":0.7,"pith_summary":"Viewing the Transformer as an associative memory, this paper develops a quantitative theory of memory capacity and memory update. It introduces a retrieval signal-to-noise ratio (SNR) to show why the exponential kernel of softmax attention far outperforms linear attention, and it interprets feed-forward networks as ReLU-kernel associative memories whose lower precision buys superposition and knowledge density. On the update side, it unifies linear attention, DeltaNet, gated attention, and softmax attention as instances of one recurrent memory update $S_t = A_t S_{t-1} B_t + C_t$ with an associated optimization objective. From this unification it proposes DeltaFormer, a model that adds the delta rule to softmax attention, and proves that a single DeltaFormer layer can track the exchange of n elements using $d = O(\\log n)$-dimensional keys, placing its expressivity beyond $TC^0$ and reaching $NC^1$. It further argues that as context length grows to infinity, the softmax-attention memory-update objective carries a $1/t$ factor that drives gradients to zero, so infinite-context in-context learning degrades.","feed_headline":"A delta-rule Transformer tracks n elements in log n dimensions","feed_subtitle":"Softmax plus delta-rule writes outperform standard attention and explain why infinite context hurts reasoning.","key_machinery":"The load-bearing object is the recurrent associative-memory update $S_t = S_{t-1} + u_t \\phi(k_t)^\\top$, where the new write vector $u_t$ is obtained by removing from $v_t$ the information already stored under similar keys: $u_t = \\alpha_t v_t - \\beta_t \\sum_{i<t} \\kappa_1(k_i, w_t) u_i$, and reads use a second kernel $\\kappa_2$. The proof machinery is Theorem 1, the State Exchange theorem: with keys on the unit sphere satisfying near-orthogonality ($d = O(\\log n)$) and a rounding function $f$ that is exact on neighborhoods of $\\{-1, 0, 1, 2\\}$, writing $k_t = k_{t_1} - k_{t_2}$ with $v_t = 0$ swaps the stored values of keys $t_1$ and $t_2$; induction over arbitrarily many steps shows all $n$ states remain traceable. For capacity, the central identity is the inverse-SNR formula $\\mathrm{SNR}^{-1} \\approx N\\, \\mathbb{E}[\\kappa^2(k_j, k_i)] / \\kappa^2(k_i, k_i)$, whose exponential-kernel evaluation gives $N / \\exp(2(\\tau - 1) d_k / \\tau^2)$, implying softmax attention needs only $O(\\log^2 N)$ dimensions for reliable recall.","core_discovery":"The paper's central claim is that the Transformer architecture is best understood as a form of associative memory, and that this view yields both explanation and new capability. Attention layers form short-term contextual memories through a kernel-weighted outer-product update, while FFNs form persistent memories through a ReLU-like kernel. The paper proves, in Section 2.2.1 and Appendix E, that an architecture called DeltaFormer, defined by the recurrence $u_t = \\alpha_t v_t - \\beta_t \\sum_{i<t} \\kappa_1(k_i, w_t) u_i$ and readout $o_t = \\sum_i \\kappa_2(k_i, q_t) u_i$, can track the positions of n swapped elements for arbitrarily many exchange steps using keys of dimension $d = O(\\log n)$, provided the keys are nearly orthogonal and a rounding-like function maps neighborhoods of $\\{-1, 0, 1, 2\\}$ to the exact integers. Since a constant-depth standard Transformer is known to lie in $TC^0$ and arbitrary-length swaps are beyond it, the paper concludes DeltaFormer reaches $NC^1$ expressivity. The same framework yields a negative result: for softmax attention the memory-update objective carries a $1/t$ factor, so in the infinite-context limit gradients vanish, memory stops updating, and in-context learning degrades.","pith_inferences":["A testable extension: if DeltaFormer's advantage depends on learned keys realizing the near-orthogonal construction, then on tasks with structured, non-orthogonal embeddings (such as natural-language tokens) the advantage should shrink; experiments varying key dimension and orthogonality would reveal the practical scope of the $TC^0$ separation.","The SNR framework suggests a direct design experiment: sweep the temperature $\\tau$ of the attention kernel and the slope of FFN activations while measuring both a retrieval-precision metric and a knowledge-density metric; the framework predicts a monotone tradeoff curve.","The memory-convergence argument for single-head DeltaNet (memory converging to $S^* = W_v W_k^{-1}$) implies a concrete failure mode: a single-head linear recurrent model should show degrading in-context learning on longer sequences, while multi-head models should not; this is testable in a controlled synthetic ICL benchmark.","The matrix-inverse view $u = (I + A)^{-1}v$ suggests DeltaFormer naturally computes graph reachability; extending the paper's 32-node DAG experiments to larger graphs and measuring length extrapolation would test whether the expressivity advantage persists at scale."],"forward_implications":["A single-layer DeltaFormer can provably track $n$ elements with $d = O(\\log n)$-dimensional keys, a capability beyond the $TC^0$ class of constant-depth Transformers; if the proof's constructions are realizable by learning, this gives a concrete architecture with expressivity reaching $NC^1$.","The inverse-SNR analysis predicts that softmax attention maintains reliable retrieval when key dimension scales as $O(\\log^2 N)$, whereas linear attention needs $O(N)$; this quantitatively explains why linear-attention models struggle at long-context precise retrieval and where to set head counts and dimensionality.","Interpreting FFNs as ReLU-kernel associative memories explains polysemanticity as deliberate superposition, predicts that higher-precision kernels such as SoLU trade knowledge density for monosemanticity, and licenses transferring design elements like multihead, sparsity, and gating between attention and FFN.","In the infinite-context limit, the softmax-attention update objective carries a factor $1/t$, so memory updates stall and in-context learning degrades; the paper argues that multi-head structure, gating, memory decay, and cross-layer fluctuations can mitigate the convergence to a fixed memory."],"supporting_citations":[{"why":"Establishes that constant-depth, log-precision Transformers solve only problems in TC0, the baseline the paper claims DeltaFormer surpasses.","marker":"[23]"},{"why":"Introduces DeltaNet's delta-rule memory update, the mechanism DeltaFormer generalizes with kernels.","marker":"[33]"},{"why":"Provides the parallelized delta-rule implementation and chunk-wise training that DeltaFormer adapts for efficient GPU computation.","marker":"[48]"},{"why":"Shows state-tracking in linear RNNs through negative eigenvalues, one of the works demonstrating expressivity beyond TC0 that motivates the delta-rule direction.","marker":"[13]"},{"why":"Shows the illusion of state in state-space models and bounds their expressivity, cited as evidence that delta-rule models exceed TC0.","marker":"[24]"},{"why":"Extends delta-rule state tracking with Householder products, a recent result the paper draws on for the claim that delta-rule recurrences surpass TC0.","marker":"[38]"},{"why":"Supplies the probabilistic packing theorem used to justify the existence of nearly-orthogonal unit vectors with d = O(log n), an assumption of Theorem 1.","marker":"[50]"},{"why":"Introduces gated linear attention and memory decay, the gating mechanism that DeltaFormer's general form with gates alpha and beta subsumes.","marker":"[47]"},{"why":"GQA is used in Appendix E.2 to approximate the rounding function with multiple shared heads, making Theorem 1's f realizable by grouped-query attention.","marker":"[1]"},{"why":"Defines linear attention as the baseline associative memory whose O(N) capacity limit the paper contrasts with softmax's O(log^2 N).","marker":"[17]"}],"fun_headline_variants":["Delta rule Transformer achieves NC^1 with log n dimensions","Softmax attention's infinite context causes memory update collapse","Associative memory view explains Transformer expressivity","Delta rule beats softmax: log n memory for n elements","Unified memory framework demystifies Transformer architecture"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The expressivity result assumes the model can realize a near-orthogonal key set with $d = O(\\log n)$ and a rounding-like function that exactly maps neighborhoods of $\\{-1, 0, 1, 2\\}$ to the correct integers, and that learned projection matrices can produce the constructed keys $k_t = k_{t_1} - k_{t_2}$ and zero values; if gradient descent cannot discover this construction, the claimed separation from $TC^0$ does not hold in practice.","fun_headline_variants_meta":{"raw":{"variants":["Delta rule Transformer achieves NC^1 with log n dimensions","Softmax attention's infinite context causes memory update collapse","Associative memory view explains Transformer expressivity","Delta rule beats softmax: log n memory for n elements","Unified memory framework demystifies Transformer architecture"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001151,"raw_usage":{"total_tokens":4810,"prompt_tokens":1020,"completion_tokens":3790,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":636,"completion_tokens_details":{"reasoning_tokens":3714}},"tokens_in":636,"tokens_out":3790,"duration_ms":19154,"temperature":1.0,"reasoning_tokens":3714,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:13:58.256653+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train a single-layer DeltaFormer end-to-end on the swap-tracking task (n = 5 elements, 16 swaps) from random initialization and token embeddings, with key dimension d = 3-4 and no hand-set orthogonal keys; if the model cannot reach 100% accuracy while a hand-wired construction with orthogonal keys does, then the theorem's assumptions are not satisfied by learned representations. Alternatively, test tracking n = 128 elements with learned keys at d = 7; failure there would show the $O(\\log n)$ dimension requirement is not learnable.","supporting_citations":[{"cited_title":"Linear transformers are secretly fast weight programmers","cited_arxiv_id":null,"evidence_quote":"Introduces DeltaNet's delta-rule memory update, the mechanism DeltaFormer generalizes with kernels."},{"cited_title":"Probabilistic methods in combinatorics.Draft available at https://yufeizhao","cited_arxiv_id":null,"evidence_quote":"Supplies the probabilistic packing theorem used to justify the existence of nearly-orthogonal unit vectors with d = O(log n), an assumption of Theorem 1."}],"review_version":1}