{"id":"4b76babb-06f2-40df-8d6b-5e268eecd35f","arxiv_id":"2504.13558","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A Transformer with one attention head and ReLU-floor feedforward layers can approximate Hölder functions to accuracy ε with width O(ε^{-2/β}) and depth O(log 1/ε), avoiding the curse of dimensionality.","lead":"This paper proves a theoretical result: certain Transformer networks can approximate any Hölder-continuous function on a high-dimensional space using a number of parameters that grows polynomially, not exponentially, in the dimension. The trick is to use a mathematical formula that compresses many inputs into one number, then let the network memorize the function on a carefully chosen grid.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof uses per-token bias matrices outside the standard Transformer definition; without them (or positional encoding) the network is permutation-equivariant and cannot approximate arbitrary Holder maps, so the advertised claim overreaches.","rationale":"I read the paper as a construction that is internally plausible under the authors' own definition of a Transformer with column-dependent feedforward biases. The proof error in the tail estimate of Lemmas 2 and 3 is a genuine flaw, but it changes constants and can likely be repaired by choosing K one unit larger; it does not undermine the polynomial-in-dimension rates. The more load-bearing issue is architectural scope. The abstract and title say 'Transformers' can overcome the curse of dimensionality, yet the construction relies on bias matrices with distinct columns per token, which the paper explicitly acknowledges is not the standard definition. Standard Transformers with shared biases and no positional encoding are permutation-equivariant, while the Holder class is not, so the unqualified claim is false for the standard architecture. The concrete two-token example gives a rigorous lower bound showing no standard Transformer can approximate a simple 1-Holder map to arbitrary accuracy. This does not invalidate the mathematical contribution under the paper's definition, but it requires the authors to either embed the construction in a standard Transformer (for example, by adding and accounting for positional encoding) or to qualify the theorem's scope. Since the reader already recommended CONDITIONAL for related reasons, I would keep that verdict; the concern strengthens the condition but does not move the verdict. I do not see a need to reject the paper: the core construction, if the tail-bound constant is fixed and the architectural gap is acknowledged, still demonstrates a strong approximation result for a clearly defined Transformer variant.","tokens_in":24748,"tokens_out":30939,"duration_ms":278456,"concrete_test":"Analytic check: take d=n=2, f(X)=x_{1,1}E_{11}, X=[[1,0],[0,0]], and P swapping the two columns. Then f(XP)=0 and P f(X)=E_{12}, so ||P f(X)-f(XP)||_∞=1. For any standard Transformer T with shared feedforward biases and no positional encoding, T(XP)=T(X)P. If d_∞(T,f)≤ε, the triangle inequality gives 1 ≤ ε + 0 + ε = 2ε, so ε≥1/2, contradicting Theorem 1 for ε<1/2. This verifies that the result requires column-dependent biases or an explicit positional encoding.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof's translation technique depends on feedforward bias matrices B^l with different columns (Section 2.1, Section 3.2 steps one and five, and the b0, b1, b_sgt matrices in Appendix A). A standard Transformer feedforward layer applies the same affine map Wx+b to every token, and the paper does not include positional encoding. With shared biases and no positional encoding, every feedforward block and every softmax self-attention layer is permutation-equivariant in the token index, so the whole network is permutation-equivariant. The target class H^β_Q([0,1]^{d×n},R^{d×n}) is not restricted to permutation-equivariant functions; for example, f(X)_{1,1}=x_{1,1} with all other entries 0 is 1-Holder but not equivariant under token swaps. A standard Transformer T satisfies T(XP)=T(X)P, so no such T can approximate f to error below 1/2 on X=[[1,0],[0,0]] and XP. Thus the advertised claim 'Transformers can overcome the curse of dimensionality' is not established for the standard architecture; it holds only for the paper's strictly more expressive variant. The tail-bound error in Lemmas 2 and 3 is real but repairable by adjusting K; the architecture gap is the load-bearing concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the approximation of Hölder-continuous functions mapping [0,1]^{d×n} to R^{d×n} by a Transformer architecture consisting of one softmax self-attention layer and feedforward blocks. Using the Kolmogorov–Arnold representation theorem, the authors construct feedforward blocks that compute an approximate inner feature (a finite-bit approximation of the KST coordinate sum), a self-attention layer that sums across tokens, and a second feedforward block that memorizes the outer KST functions on a finite grid. They claim that for any ε>0 the resulting network approximates any f in the Hölder class to accuracy ε in L∞ (Theorem 1) or Lp (Theorem 2), with widths and depths that are polynomial in 1/ε rather than exponential in the input dimension, thereby 'overcoming the curse of dimensionality.' The proof relies on a 'translation technique' in which the feedforward blocks are allowed to use bias matrices whose columns differ across tokens, on known FNN memorization results, and on superexpressive activations for constant-size memorization.","tokens_in":24969,"tokens_out":12921,"duration_ms":115076,"significance":"If the central claim were established for the standard Transformer architecture, it would be a notable advance: previous Transformer universal-approximation results scale exponentially in the sequence length or dimension, and this paper would give the first construction with polynomial-in-1/ε complexity for a smoothness class. The paper's organization around KST is conceptually clean and avoids the contextual-mapping machinery of earlier work; the explicit reduction of Transformer approximation to FNN approximation and memorization is a useful methodological idea. The paper also ships concrete rates for several activation-function combinations, including fixed-width memorization networks using superexpressive activations. However, the advertised claim is currently tied to a nonstandard definition of the feedforward block, and the correctness of the stated error bounds is undermined by a false tail estimate. Both issues are repairable, but the architectural gap in particular affects the scope of the results as presented.","major_comments":[{"comment":"The construction uses feedforward blocks with bias matrices B^l whose columns may differ across tokens, which is explicitly introduced as a generalization of the standard definition. A standard Transformer feedforward layer applies the same affine map, including the same bias vector, to every token, and the paper does not include positional encoding. Under these standard restrictions every feedforward block and every softmax self-attention layer is permutation-equivariant in the token index, so the whole network satisfies T(XP)=T(X)P for every permutation P of the n columns. The target class H^β_Q([0,1]^{d×n}, R^{d×n}) is not restricted to permutation-equivariant functions: for example, f(X)_{1,1}=x_{1,1} and f_{rs}(X)=0 otherwise is 1-Hölder but not equivariant under swaps of the first two tokens. For X=[[1,0],[0,0]] and XP=[[0,1],[0,0]], any permutation-equivariant T must have d∞(T,f)≥1/2, so no standard Transformer without positional encoding can approximate all functions in the class. Theorems 1 and 2 therefore hold only for the paper's more expressive variant with column-dependent biases; the manuscript does not show that this variant can be simulated by a standard Transformer of the same size, nor does it restrict the target class to permutation-equivariant functions. This is the load-bearing gap between the title/abstract and the actual construction.","section":"Section 2.1; Section 3.2; Appendix A"},{"comment":"The displayed tail estimate |φ_K(x)-φ(x)| = 2 Σ_{j=K+1}^∞ a_j^x 3^{-dn(j-1)-1} ≤ 2/(3^{2dn+1}-3^{dn+1}) · 3^{-dnK} is not correct. The worst-case tail (e.g., all a_j^x=1) equals (2/3)·3^{-dnK}/(1-3^{-dn}), which is Θ(3^{-dnK}), whereas the paper's bound is Θ(3^{-dn(K+2)}), a factor Θ(3^{2dn}) smaller in the linear tail. After applying Hölder continuity with exponent γ ∝ β/(dn), this discrepancy becomes a constant factor of order 2^{2β} in the second error term of Lemmas 2 and 3 and in the Lp estimate in Section 3.3.2. The qualitative conclusions survive because the extra constant can be absorbed by increasing K by an O(1) amount, but as written the lemmas overstate the accuracy of the construction. The authors should correct the tail bound and restate the parameter choices in Theorems 1 and 2 accordingly.","section":"Appendix B and Appendix C; Lemmas 2 and 3"}],"minor_comments":[{"comment":"The Hölder space H^{β log 2/(d log 3)}_{2βQ}(C) is typeset in a garbled way in the statement of Proposition 2; please make the exponent and the constant explicit.","section":"Section 2.2, Proposition 2"},{"comment":"Definition 1 restricts to β ≤ 1, but the main theorems use H^β_Q for general β ∈ (0,1]; the paper should state this parameter range consistently.","section":"Section 2.2, Definition 1"},{"comment":"The abstract says the ReLU-floor construction needs only O(log(1/ε)) feedforward layers, but the depth of ~F^{(mmr)}_{FF} in Theorem 1(1) is 7dn−2, which depends on the sequence length n; the O(log(1/ε)) statement is only with respect to ε for fixed d,n. This should be qualified in the abstract.","section":"Abstract and Theorem 1"},{"comment":"In the six-step diagram, the transition from the second matrix to the third matrix repeats the same row twice; the accompanying text attributes this to a feedforward block, but with shared weights this row duplication requires the two rows to be constructed separately. Please clarify how the row dimension is expanded.","section":"Section 3.2"},{"comment":"In the proof of Lemma 4, the measure condition '2^{-kβp}' should read '2^{-Kβp}'.","section":"Appendix D, Lemma 4"},{"comment":"The proof of Lemma 6(2) contains a rendering artifact '/BD x≥0' in the definition of σ3; please fix the notation.","section":"Appendix E, Lemma 6"},{"comment":"Table 2 has several blank or misaligned entries in the width/depth columns for the compared works; a cleaner table would help readers verify the comparison.","section":"Table 2"}],"recommendation":"major_revision","confidential_remarks":"The architectural gap is the main risk: the paper's title and abstract claim that 'Transformers' overcome the curse of dimensionality, but the construction is for a Transformer variant with token-dependent FF biases, which is strictly more expressive than the standard architecture. I would advise the editor that this needs to be confronted head-on, either by adding positional encoding to make the construction standard or by explicitly rescoping the results to the generalized architecture. The KST-based proof strategy itself is sound in outline and the polynomial rates are valuable; the tail-bound error is a technical flaw that is easily fixed. The paper is likely salvageable as a major revision, but not in its current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the construction is genuinely interesting and likely correct in outline, but it proves less than the title promises. The new device is the translation technique: by using per-column biases, they convert the problem of approximating different column functions into memorizing one function on a discrete set, and then apply KST-based FNN approximation to a single-head softmax Transformer. That yields width roughly ε^{-2/β} for the ReLU-floor case and O(1) width with superexpressive activations, against ε^{-dn/β} for prior Transformer approximation results. They avoid contextual mapping, and the proof is modular and easy to follow. The cited FNN lemmas are standard and mostly independent, so the dependency tree looks honest. The price is nonstandard activations, so this is an expressivity result, not a practical algorithm.\n\nThe first soft spot is the tail estimate in Lemmas 2 and 3. They bound |φ_K−φ| by 2/(3^{2dn+1}−3^{dn+1}) 3^{−dnK}, but the actual worst-case tail is about 2/(3(1−3^{−dn})) 3^{−dnK}, larger by a factor ≈3^{2dn}. After raising to the Hölder exponent this inflates the error term by roughly 2^{2β}. The fix is to increase K by 2, so the main theorem survives, but the displayed bounds are not proven as written.\n\nThe more serious issue is architectural. Their feedforward block uses bias matrices B^l with different columns, which they explicitly allow in Section 2.1. A standard Transformer applies the same affine map to every token, and with no positional encoding the whole network is permutation-equivariant. Their target class H^β_Q contains non-equivariant maps, so a standard Transformer cannot approximate them to arbitrary accuracy. In other words, the theorem is true for their generalized Transformer, not for the architecture normally called a Transformer. The title and abstract overstate the result. Closing this gap means adding positional encodings or clearly scoping the claim.\n\nIf I were handling this paper, I would send it to referees. The core idea is novel, the proof is mostly transparent, and both problems are repairable. The right outcome is a major revision that fixes the constant and re-frames the contribution as a result about a generalized Transformer or about Transformers with positional information. This is worth the attention of approximation-theory researchers working on Transformer expressivity, but I would not yet cite it as a proof about standard Transformers.","headline":"The construction is genuinely novel and likely repairable, but the paper proves less than its title promises: the result holds for a generalized Transformer with token-dependent biases, not the standard token-wise feedforward architecture.","tokens_in":25540,"tokens_out":7179,"would_cite":false,"duration_ms":66644,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["41A25","41A30","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single self-attention layer can approximate any Hölder map to accuracy ε at polynomial cost","keywords":["Transformer approximation","curse of dimensionality","Kolmogorov-Arnold representation theorem","Hölder continuous functions","self-attention","feedforward networks","memorization","approximation rates"],"falsifier":"Take $d=1,n=2$ and enforce the standard constraint $B^l = b^l \\mathbf{1}_{1\\times 2}$ in every feedforward block of the constructed Transformer. If, for the simple target $f(x)=(x_1,x_2)$ and some small $\\epsilon$, no weights of the depth and width stated in Theorem 1 produce the required inner matrix $Z$ for all $X\\in[0,1]^{1\\times 2}$, then the uniform-approximation claim fails for standard Transformers.","tokens_in":24475,"feed_emoji":"🧠","tokens_out":11492,"duration_ms":101923,"temperature":0.7,"pith_summary":"This paper tries to establish that Transformers can approximate the full class of Hölder-continuous maps from $[0,1]^{d\\times n}$ to $\\mathbb{R}^{d\\times n}$ without paying the exponential-in-dimension cost known as the curse of dimensionality. It constructs explicit networks made of one softmax self-attention layer and small feedforward blocks that achieve uniform error $\\epsilon$ for any $\\epsilon>0$; with ReLU and floor activations the feedforward depth is $O(\\log 1/\\epsilon)$ and width $O(\\epsilon^{-2/\\beta}\\log 1/\\epsilon)$, and with additional exotic activations the width becomes constant. Earlier universal-approximation results for Transformers all had approximation costs that grew exponentially with the token dimension, so this is a different and stronger statement about the architecture's expressive capacity. The proof routes the problem through the Kolmogorov-Arnold Representation Theorem and a feedforward memorization step, bypassing the contextual-mapping technique of previous work.","feed_headline":"One self-attention layer escapes the curse of dimensionality","feed_subtitle":"Construction approximates Hölder maps with width polynomial in 1/ε, not exponential in dimension.","key_machinery":"Two pieces carry the argument. First, Proposition 2, a space-filling-curve form of the Kolmogorov-Arnold Representation Theorem, writes every Hölder component $f_{rs}$ as $g_{rs}(3\\sum_{p,q} a_{pq}\\varphi(x_{pq}))$ with univariate outer functions $g_{rs}$ on the Cantor set and a digit-extracting inner function $\\varphi$; this transfers smoothness to the outer function and reduces high-dimensional approximation to one-dimensional operations. Second, the translation technique lets a single shared-weight feedforward block implement different column functions by adding different integer offsets to each token column, so that the inner $\\varphi_K$ computation can be done once for all columns; the self-attention layer then performs the summation over token columns. The memorization lemmas for feedforward networks, covering binary memorization with ReLU-floor, sine/cosine variants, and constant-size memorization with superexpressive activations, finish the construction by fitting the finitely many values of the outer functions.","core_discovery":"The central claim, stated as Theorem 1, is that for any $f \\in \\mathcal{H}_Q^\\beta([0,1]^{d\\times n},\\mathbb{R}^{d\\times n})$ and any $\\epsilon>0$, there is a Transformer $T = \\widetilde{F}_{FF}^{(mmr)} \\circ F_{SA} \\circ F_{FF}^{(sr)}$ with one one-headed softmax self-attention layer such that $d_\\infty(T,f)\\le \\epsilon$. The first feedforward block approximates the inner functions of a Kolmogorov-Arnold representation, the attention layer sums across token columns, and the final feedforward block memorizes the values of the outer functions on a finite set of integers. Depending on the activation inventory, the final block has depth $7dn-2$ and width $O(\\epsilon^{-2/\\beta}\\log 1/\\epsilon)$ with ReLU and floor, or depth $6$ and width $O(\\log 1/\\epsilon)$ with an added $2^x$ activation, or depth $3$ and constant width when a nonpolynomial analytic or reciprocal activation is allowed. Theorem 2 extends the statement to $L^p$ distance for all $p\\in[1,\\infty)$, using ReLU for the inner block and sine/cosine or periodic-plus-nonpolynomial activations for memorization.","pith_inferences":["The proof uses feedforward blocks whose bias matrices may have different columns for different tokens, while a standard Transformer feedforward layer applies one bias vector to every token; the paper does not show how to simulate the per-column bias at the same size, so the headline claim should be read for the generalized architecture unless such a simulation is supplied.","If the per-column-bias assumption turns out to be simulable with only a modest width increase, the proof strategy would extend to the vanilla Transformer; if not, the result identifies a representational advantage of an architectural variant, not of the standard model.","The construction suggests a testable empirical direction: a Transformer with token-dependent bias terms should represent high-dimensional Hölder functions with far fewer parameters than a standard Transformer of the same depth, and measuring that gap would separate representational benefit from optimization behavior."],"forward_implications":["If Theorem 1 is correct, Hölder-continuous sequence-to-sequence maps are approximable by Transformers whose width grows only polynomially in $1/\\epsilon$ for fixed $d,n$, so the exponential dimensional barrier in earlier approximation bounds is not intrinsic to the architecture.","The $L^p$ version in Theorem 2 shows the same escape from the curse of dimensionality holds under the weaker metric used in statistical learning, at least for inputs outside a small measure-zero failure set in the ReLU construction.","The ReLU-floor and exotic-activation cases imply that the activation inventory matters for the bound: adding one nonstandard activation can reduce width from polynomial in $1/\\epsilon$ to constant.","The construction template turns feedforward approximation and memorization results into Transformer results, so any future improvement in feedforward memorization size should transfer directly to this class of Transformers."],"supporting_citations":[{"why":"Supplies Proposition 2, the space-filling-curve version of the Kolmogorov-Arnold representation theorem that transfers Hölder smoothness to univariate outer functions; this is the construction's starting point.","marker":"[47]"},{"why":"Defines the Transformer architecture with self-attention and feedforward blocks that the paper builds on.","marker":"[56]"},{"why":"Earlier universal-approximation result for Transformers via contextual mapping; the comparison baseline whose curse-of-dimensionality this paper removes.","marker":"[69]"},{"why":"Supplies the ReLU-floor memorization network used in Lemma 6(1) for the binary-expansion memorization step.","marker":"[49]"},{"why":"Supplies fixed-depth memorization networks with ReLU-floor-2x and ReLU-cosine activations used in Lemma 6(2) and 6(4).","marker":"[50]"},{"why":"Supplies the ReLU-sine memorization network used in Lemma 6(3) for the $L^p$ construction.","marker":"[25]"},{"why":"Provides the rational-independence lemma that lets a nonpolynomial analytic activation generate dense windings for constant-width memorization.","marker":"[66]"},{"why":"Provides the rational-independence result for the reciprocal activation used by the constant-width memorization of Lemma 3.","marker":"[72]"}],"fun_headline_variants":["One attention head breaks the curse of dimensionality","Single softmax attention layer conquers high-dim approximation","Transformers need polynomial width, not exponential, for Hölder maps","Kolmogorov-Arnold trick lets Transformers dodge curse of dimensionality","Softmax attention escapes exponential width in function approximation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction depends on feedforward blocks accepting bias matrices whose columns may differ between tokens; a standard Transformer applies the same bias vector to every token, and the paper does not show how to simulate that difference at the same cost.","fun_headline_variants_meta":{"raw":{"variants":["One attention head breaks the curse of dimensionality","Single softmax attention layer conquers high-dim approximation","Transformers need polynomial width, not exponential, for Hölder maps","Kolmogorov-Arnold trick lets Transformers dodge curse of dimensionality","Softmax attention escapes exponential width in function approximation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000284,"raw_usage":{"total_tokens":1752,"prompt_tokens":1096,"completion_tokens":656,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":712,"completion_tokens_details":{"reasoning_tokens":581}},"tokens_in":712,"tokens_out":656,"duration_ms":7009,"temperature":1.0,"reasoning_tokens":581,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T12:08:46.932416+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $d=1,n=2$ and enforce the standard constraint $B^l = b^l \\mathbf{1}_{1\\times 2}$ in every feedforward block of the constructed Transformer. If, for the simple target $f(x)=(x_1,x_2)$ and some small $\\epsilon$, no weights of the depth and width stated in Theorem 1 produce the required inner matrix $Z$ for all $X\\in[0,1]^{1\\times 2}$, then the uniform-approximation claim fails for standard Transformers.","supporting_citations":[{"cited_title":"The kolmogorov–arnold represent ation theorem revisited","cited_arxiv_id":null,"evidence_quote":"Supplies Proposition 2, the space-filling-curve version of the Kolmogorov-Arnold representation theorem that transfers Hölder smoothness to univariate outer functions; this is the construction's starting point."},{"cited_title":"Reddi, and Sanjiv Kumar","cited_arxiv_id":null,"evidence_quote":"Earlier universal-approximation result for Transformers via contextual mapping; the comparison baseline whose curse-of-dimensionality this paper removes."},{"cited_title":"Deep network w ith approximation error being reciprocal of width to power of square root of depth","cited_arxiv_id":null,"evidence_quote":"Supplies the ReLU-floor memorization network used in Lemma 6(1) for the binary-expansion memorization step."},{"cited_title":"Neural networ k approximation: Three hidden layers are enough","cited_arxiv_id":null,"evidence_quote":"Supplies fixed-depth memorization networks with ReLU-floor-2x and ReLU-cosine activations used in Lemma 6(2) and 6(4)."},{"cited_title":"Deep neural networks with relu-sine-exponentia l activations break curse of dimensionality in approximation on h¨ older class","cited_arxiv_id":null,"evidence_quote":"Supplies the ReLU-sine memorization network used in Lemma 6(3) for the $L^p$ construction."},{"cited_title":"Elementary superexpressive activations","cited_arxiv_id":null,"evidence_quote":"Provides the rational-independence lemma that lets a nonpolynomial analytic activation generate dense windings for constant-width memorization."},{"cited_title":"Deep network a pproximation: Achieving arbitrary accuracy with fixed number of neurons","cited_arxiv_id":null,"evidence_quote":"Provides the rational-independence result for the reciprocal activation used by the constant-width memorization of Lemma 3."}],"review_version":1}