acceptodds
Under review as a conference paper at ICLR 2027

Preserving Regularity in Finite-Precision Transformer Approximation

Abstract

Transformers are the dominant architecture for large language models and are widely used in multimodal foundation models. Their substantial storage requirements have made low-bit quantization an important tool for practical deployment. Yet quantitative Transformer approximation theory predominantly treats weights as unconstrained real numbers, leaving a gap between theoretical guarantees and finite-precision representations. This question goes beyond approximation accuracy: quantization can increase a model's sensitivity to small input perturbations even when the approximation error remains small. It is therefore important to understand whether finite-precision Transformers can simultaneously achieve accurate approximation, controlled storage complexity, and preservation of a prescribed regularity bound. In this paper, we construct a finite-precision Transformer that approximates matrix-valued -Hölder functions on while preserving a prescribed componentwise -Hölder bound . Its hidden feature weights are discrete at and target-independent, while target dependence is confined to the output coefficients. This separation allows us to directly control the effects of quantization on both approximation accuracy and regularity. For , the resulting Transformer achieves uniform error with nonzero parameters and a common -bit fixed-point format for all parameters. These guarantees concern parameter storage under exact forward evaluation. As an application, empirical risk minimization over a structured finite-precision Transformer class achieves expected squared prediction risk under sub-Gaussian noise, matching the classical Hölder minimax exponent up to a logarithmic factor.

Primary area:
learning theory
Keywords:
Approximation theory, Transformer networks, Finite-Precision Networks, Nonparametric Regression, Expressive Power

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_cxJNOpenReview ↗
Rating
2(+1)
Confidence
1(−1)
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the approximation capabilities, regularity preservation, and statistical properties in nonparametric regression of finite-precision Transformers. Building on existing Kuhn triangulation and ReLU MLP constructions, the authors first construct a single-head Transformer with one self-attention layer to approximate matrix-valued Hölder functions, with hidden weights restricted to a finite discrete set. They then apply fixed-point quantization to the output coefficients and introduce coefficient contraction before quantization to preserve the prescribed ℓ1\ell_1-Hölder regularity bound while controlling approximation error, together with asymptotic bounds on parameter count and storage bit complexity. Finally, the authors construct a finite-precision Transformer hypothesis class and show, through finite-class complexity analysis, that exact empirical risk minimization under sub-Gaussian noise achieves the classical minimax convergence exponent for Hölder nonparametric regression, up to logarithmic factors. The paper is primarily theoretical, providing mathematical derivations and proofs without numerical experiments or practical quantization deployment evaluations.

Critical strengths

Strength 1: The paper jointly investigates the approximation accuracy, finite-precision parameter storage complexity, and regularity preservation of Transformers. The relationships among these properties are of theoretical interest. In particular, the authors explicitly distinguish parameter count from the number of bits required to represent the parameters and incorporate storage precision into the theoretical analysis.

Strength 2: The paper provides an explicit network construction and parameter characterization, together with an analysis of how coefficient perturbations affect the Hölder seminorm. By introducing coefficient contraction, the authors preserve the prescribed regularity bound while establishing corresponding asymptotic complexity guarantees. The detailed proofs also facilitate verification of the theoretical claims.

Critical weaknesses

Weakness 1: I have substantial concerns regarding the theoretical novelty of this work. The main approximation construction builds directly upon the regularity-preserving Kuhn-triangulation ReLU MLP developed by Hong and Kratsios [1]. Moreover, the conversion of feedforward approximation constructions into Transformer architectures and the establishment of nonparametric regression guarantees for Transformers have already been investigated in prior work [2, 3]. The primary additional steps in this paper involve combining these existing constructions with fixed-point truncation and coefficient contraction to control perturbations of the output coefficients. While these operations are mathematically reasonable, the paper does not sufficiently establish which aspects constitute a substantial theoretical advance beyond existing results and standard perturbation analysis. In particular, the query and key projection matrices are explicitly set to zero, reducing the self-attention mechanism to input-independent uniform averaging. Consequently, the main approximation capability is inherited from the existing ReLU MLP construction rather than arising from any nontrivial attention mechanism. This further weakens the Transformer-specific novelty of the proposed theoretical results.

Weakness 2: The paper motivates its investigation through the practical deployment of low-bit Transformers. However, its main guarantees concern only the storage precision of parameters in a specially constructed network, while forward evaluation is assumed to use exact real arithmetic. The analysis does not account for finite-precision softmax computation, activation rounding, intermediate numerical errors, or input-dependent attention. Furthermore, it does not establish whether the prescribed regularity bound remains valid under realistic finite-precision inference. Therefore, although the results characterize a particular form of finite-precision parameter representation, they do not directly address the numerical behavior of practically deployed quantized Transformers. This substantially limits the practical implications of the theoretical guarantees.

Weakness 3: The regularity-preservation results are established using the ℓ1\ell_1-Hölder seminorm, whereas the original Hölder regularity of the target functions is defined using the ℓ2\ell_2 distance. Consequently, preserving the same bound under the ℓ1\ell_1 metric does not necessarily imply preservation of the original bound under the ℓ2\ell_2 metric. More importantly, the nonparametric regression theorem guarantees only prediction risk and does not ensure that the learned empirical risk minimizer satisfies the same regularity constraint. As the authors acknowledge in Remark 6.2, the regularity-preservation guarantee applies to the explicitly constructed approximant rather than to the general estimator selected by empirical risk minimization. Although some of these limitations are acknowledged in the manuscript, the paper does not establish a unified guarantee of approximation accuracy, regularity preservation, and statistical generalization for the learned finite-precision Transformer. Given the already restrictive theoretical setting, the current results provide limited evidence that the proposed analysis offers new insights or practical guidance for real-world Transformer quantization.

[1] Ruiyang Hong and Anastasis Kratsios. "Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity." arXiv preprint arXiv:2409.12335, 2024. https://arxiv.org/abs/2409.12335

[2] Yanming Lai and Defeng Sun. "Standard Transformers Achieve the Minimax Rate in Nonparametric Regression with Cs,λC^{s,\lambda} Targets." arXiv preprint arXiv:2602.20555, 2026. https://arxiv.org/abs/2602.20555

[3] Jerry Yao-Chieh Hu, Mingcheng Lu, Yi-Chen Lee, and Han Liu. "Transformer Approximations from ReLUs." arXiv preprint arXiv:2604.24878, 2026. https://arxiv.org/abs/2604.24878

Questions for authors

Q1: Could the authors clarify the specific novel technical contributions of Theorem 4.1, Theorem 5.2, Corollary 5.4, and Theorem 6.1? In particular, compared with the regularity-preserving MLP construction of Hong and Kratsios [1] and the Transformer approximation and regression guarantees established by Lai and Sun [2], which results in this paper cannot be directly derived from existing constructions and standard fixed-point perturbation analysis? A rigorous theorem-level comparison with these prior works would help clarify the originality and significance of the proposed theoretical contributions.

Q2: In the proposed construction, the query and key projection matrices are set to zero (WQ=WK=0W_Q = W_K = 0), reducing the attention mechanism to input-independent uniform averaging. Under this setting, what new Transformer-specific theoretical insights does the proposed framework provide beyond applying finite-precision parameterization to an existing ReLU MLP construction? Furthermore, would the approximation and regularity-preservation guarantees remain valid if the architecture incorporated nontrivial input-dependent attention?

Q3: Corollary 5.4 establishes the prescribed ℓ1\ell_1-Hölder regularity bound for a specifically constructed approximant, whereas the empirical risk minimizer in Theorem 6.1 is not guaranteed to satisfy the same regularity constraint. Is it possible to impose an explicit regularity constraint on the learned estimator while preserving the same statistical convergence exponent? Additionally, to what extent does establishing the final guarantee under the ℓ1\ell_1 metric, rather than the ℓ2\ell_2 metric used in the original definition of the target function's Hölder regularity, limit the significance and applicability of the regularity-preservation result?

[1] Ruiyang Hong and Anastasis Kratsios. "Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity." arXiv preprint arXiv:2409.12335, 2024. https://arxiv.org/abs/2409.12335

[2] Yanming Lai and Defeng Sun. "Standard Transformers Achieve the Minimax Rate in Nonparametric Regression with Cs,λC^{s,\lambda} Targets." arXiv preprint arXiv:2602.20555, 2026. https://arxiv.org/abs/2602.20555

4 comments
AuthorsOpenReview ↗

Response to Reviewer cxJN (1/2)

W1 & Q1 (Contribution beyond existing results). We agree that the construction builds on [1, 2] and uses elementary perturbation and contraction arguments. We do not claim new proof techniques. Our contribution is a joint guarantee that, to our knowledge, is not established in [1–3]. Under exact forward evaluation, Transformers with all parameters stored in one explicit fixed-point format approximate every target in the stated λ\lambda-Hölder ball to accuracy ε\varepsilon, preserve the prescribed componentwise ℓ1\ell^1-Hölder bound LL, and admit complete encodings within a logarithmic factor of the worst-case encoding lower bound. Write D=dnD=dn.

Accuracy-only quantization does not guarantee preservation of LL, and direct truncation can exceed it (see our response to v4x1). At grid resolution NN, Lem. 5.1 bounds the seminorm perturbation by 2δNλ2\delta N^\lambda for coefficient errors bounded by δ\delta. This upper bound need not vanish under our accuracy-only schedule. Contracting coefficients by 1−ρ1-\rho reserves a margin ρL\rho L, and Cor. 5.4 chooses finer precision so that 2δNλ≤ρL2\delta N^\lambda\le\rho L. This sufficient schedule uses 2log⁡2(1/ε)+O(1)2\log_2(1/\varepsilon)+O(1) fractional bits, twice the leading term of our accuracy-only schedule, with unchanged parameter-count and storage upper-bound orders.

ResultInherited / standardEstablished here
Thm. 4.1Hong–Kratsios (HK) interpolant and hidden construction [1], uniform gathering [2, Lem. 8]Exact token-specific output via positional ReLU gating (Lems. C.4–C.5), {0,1}\{0,1\} attention/embedding weights
Lem. 5.1, Thm. 5.2Kuhn geometry [1, Lems. 7.5, 7.8], fixed-point truncationSeminorm perturbation bound 2δNλ2\delta N^\lambda, exact hidden realization (Prop. B.2), one common fixed-point format for all parameters
Cor. 5.4Coefficient contractionSufficient precision schedule giving accuracy ε\varepsilon and bound LL at unchanged complexity upper-bound orders
Rem. 5.5 (new)Hölder-ball encoding lower bound Ω(ε−D/λ)\Omega(\varepsilon^{-D/\lambda}) [4–6]For fixed d,n,L,λd,n,L,\lambda, complete storage O(ε−D/λlog⁡(1/ε))O(\varepsilon^{-D/\lambda}\log(1/\varepsilon))
Thm. 6.1, Prop. 6.2 (new)Finite-class ERM, constrained classes [1, Sec. 4.2], real-valued rate [2, Thm. 3]Finite-precision regression class, ERM constrained to LL retaining the same risk upper-bound order (see Q3)

W1 & Q2 (Role of attention and scope of the result). Kajitsuka and Sato [7, Thm. 2] and He et al. [8, Lem. 4.10] use softmax attention to construct contextual mappings that distinguish tokens across contexts on suitable finite input sets. We use the gathering route of Lai and Sun [2, Lem. 8], , in which uniform attention (WQ=WK=0W_Q=W_K=0) gives each token a scaled copy of the complete ordered input, with its position code carried alongside. Our post-attention HK block computes the outputs and uses positional gating to select column qq for token qq (Lems. C.4–C.5). This makes each token's output depend on its context and position, using the full input rather than attention-generated context ids.

We choose this exact realization for its precision structure,, since it's attention/embedding entries lie in {0,1}\{0,1\}, and HK hidden feature weights use small discrete alphabets. Structural integers and output coefficients are also covered by the common fixed-point budget (Thm. 5.2(2)). Our focus is the joint approximation, storage, and componentwise ℓ1\ell^1-Hölder guarantee of Cor. 5.4, not a new account of attention's approximation power.

The same joint guarantee for nontrivial input-dependent attention remains open here (Sec. 7).

[1] R. Hong and A. Kratsios. Bridging the Gap between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity. arXiv:2409.12335, 2024.

[2] Y. Lai and D. Sun. Standard Transformers Achieve the Minimax Rate in Nonparametric Regression with Cs,λC^{s,\lambda} Targets. arXiv:2602.20555, 2026.

[3] J. Y.-C. Hu, M. Lu, Y.-C. Lee, and H. Liu. Transformer Approximations from ReLUs. arXiv:2604.24878, 2026.

[4] W. Ou, P. Schenkel, and H. Bölcskei. Three Quantization Regimes for ReLU Networks. arXiv:2405.01952, 2024.

[5] T. Mao and J. Xu. Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View. arXiv:2608.01357, 2026.

[6] A. N. Kolmogorov and V. M. Tikhomirov. ε\varepsilon-entropy and ε\varepsilon-capacity of sets in function spaces. Uspekhi Matematicheskikh Nauk, 14(2):3–86, 1959.

[7] T. Kajitsuka and I. Sato. Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators? In ICLR, 2024 (arXiv:2307.14023v3).

[8] X. He, Y. Jiao, X. Lu, and J. Z. Yang. Approximation Error Upper and Lower Bounds for Hölder Class with Transformers. In ICML, 2026 (arXiv:2605.07463v2).

AuthorsOpenReview ↗

Response to Reviewer cxJN (2/2)

W2 (Practical scope). We agree that our guarantees concern parameter storage under exact forward evaluation, not finite-precision inference. The abstract and Secs. 1–2 state this scope explicitly. In our approximation construction, all non-output parameters are exactly represented and counted in the common fixed-point format (Thm. 5.2(2)), so parameter-truncation error is confined to the output coefficients. This storage/evaluation separation also appears in the dyadic-parameter Transformer approximation of [1].

The regularity bound is not guaranteed under rounded evaluation. Rounding in softmax, activations, or intermediate arithmetic can introduce jumps, as illustrated by the runtime diagnostics in our response to v4x1. These are not deployment guarantees, and a rigorous inference-level analysis is not attempted here. A concrete takeaway for our construction under exact evaluation is that coefficient contraction plus roughly twice the fractional bits of the accuracy-only schedule suffices to retain accuracy ε\varepsilon and the componentwise ℓ1\ell^1-Hölder bound LL, at unchanged storage upper-bound order (Cor. 5.4).

W3 & Q3 (Regularity of the learned estimator). Yes. Under the same assumptions as Thm. 6.1, new Prop. 6.2 (App. E.4) restricts TNm,sm′\mathcal T_{N_m,s_m'} to the subclass Hm\mathcal H_m satisfying the componentwise ℓ1\ell^1-Hölder and sup-norm bounds LL on [0,1]d×n[0,1]^{d\times n}. This links Sec. 6 to Cor. 5.4's regularity bound while keeping Thm. 6.1 as an unconstrained baseline. Measurable exact ERM over Hm\mathcal H_m attains the same expected squared prediction-risk upper-bound order, O((log⁡(em)/m)2λ/(2λ+D))O((\log(em)/m)^{2\lambda/(2\lambda+D)}) (D=dnD=dn). Hong and Kratsios [1, Sec. 4.2] likewise constrain their network class by a Lipschitz bound.

The key idea is to preserve the approximation–complexity balance of the finite-class bound (Thm. E.1). By Lem. 5.1, contracting the output coefficients reserves a margin ρmL\rho_m L that absorbs quantization when 2⋅2−sm′Nmλ≤ρmL2\cdot2^{-s_m'}N_m^\lambda\le\rho_m L. Prop. 6.2 ensures this by doubling the coefficient of log⁡2m\log_2 m in Thm. 6.1's precision schedule and adding an mm-independent offset. For fixed D,L,λD,L,\lambda, the precision remains O(log⁡m)O(\log m). With the constructive hidden configuration, this gives a comparison approximant in Hm\mathcal H_m with uniform error O(Nm−λ)O(N_m^{-\lambda}), while log⁡∣Hm∣≤log⁡∣TNm,sm′∣=O(D(Nm+1)Dlog⁡m)\log\lvert\mathcal H_m\rvert\le\log\lvert\mathcal T_{N_m,s_m'}\rvert=O(D(N_m+1)^D\log m) retains the same upper-bound order. Thm. E.1 then gives the stated risk bound. Exact ERM ranges over the full constrained class, not only contracted approximants. Efficient constrained optimization is not established here.

W3 & Q3 (cont.: ℓ1\ell^1 versus Euclidean metric). We thank the reviewer for highlighting this metric distinction. Both the approximant in Cor. 5.4 and the constrained estimator in Prop. 6.2 retain Hölder exponent λ\lambda. The metric distinction concerns the guaranteed constant. Writing ∣g∣C0,λ\lvert g\rvert_{C^{0,\lambda}} for the Euclidean seminorm in Eq. (1), we have [g]λ,1≤∣g∣C0,λ≤Dλ/2[g]λ,1[g]_{\lambda,1}\le\lvert g\rvert_{C^{0,\lambda}}\le D^{\lambda/2}[g]_{\lambda,1}. Our Euclidean target assumption implies the ℓ1\ell^1 bound LL, which the HK interpolant preserves and our quantization analysis retains. In Euclidean distance, the resulting guarantee is at most Dλ/2LD^{\lambda/2}L.

For fixed D,L,λD,L,\lambda, this metric conversion leaves the approximation and statistical convergence exponents established here unchanged. It does not certify the original Euclidean constant LL. The explicit factor Dλ/2D^{\lambda/2} becomes more consequential as input dimension or sequence length grows, so applications requiring that exact Euclidean bound are outside the guarantee. We state this limitation explicitly in Rem. 6.3.

[1] Furuya, de Hoop & Peyré. "Universality and Generalization of Causal Transformers Across Context Lengths." arXiv:2609.35055v1, https://arxiv.org/html/2609.35055v1

We welcome any remaining questions.

Thank you for the detailed rebuttal. The newly introduced Proposition 6.2 substantially addresses my concern regarding regularity preservation for the learned estimator. However, my main concern about limited theoretical novelty remains. Overall, I believe a rating of 2 (Weak Rejection) is fair.

Thank you for taking the time to read our rebuttal and reconsider your assessment. We appreciate your acknowledgment that Proposition 6.2 substantially addresses your concern about regularity preservation for the learned estimator. Your feedback helped us strengthen the connection between our approximation and statistical results. Please let us know if you have any further questions, and thank you again for your helpful feedback.

Reviewer_v4x1OpenReview ↗
Rating
3
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper constructs finite-precision Transformers that approximate Hölder functions while preserving a prescribed regularity bound. Its main technique combines discrete hidden weights with contraction of output coefficients before quantization, achieving explicit approximation and storage guarantees. It also derives a near-minimax regression rate under sub-Gaussian noise. Validation is theoretical, assuming exact forward evaluation with quantized parameters.

Critical strengths
  • The coefficient-contraction argument preserves the prescribed Hölder bound while controlling approximation error. This addresses input sensitivity, which small approximation error alone does not guarantee.
  • The constructive Transformer realization provides concrete parameter-count and bit-width bounds under exact forward evaluation. This clarifies the storage requirements for achieving approximation accuracy and regularity simultaneously.
  • The ERM analysis achieves the classical Hölder minimax exponent up to a logarithmic factor under sub-Gaussian noise. This connects the approximation construction to statistical estimation and establishes that finite-precision parameterization can retain favorable learning rates.
Critical weaknesses
  • Experiments on functions with known regularity bounds should compare unquantized, directly quantized, and contraction-before-quantization models. Reporting approximation error and regularity violations would clarify when contraction offers a meaningful advantage over direct quantization.

  • Contraction introduces approximation bias, while the regularity-preserving construction requires additional fractional precision. Experiments varying bit width and grid resolution, with comparisons at matched storage budgets, would establish whether the resulting accuracy–regularity trade-off is practically favorable.

  • The guarantees assume exact forward evaluation despite quantized parameter storage. Experiments incorporating rounding of activations and intermediate computations would clarify whether the proposed mechanism remains effective during low-precision inference, which is important for assessing the deployment relevance motivating the paper.

Questions for authors
  • Can the authors compare direct quantization and contraction-before-quantization on targets with known regularity bounds, using matched storage budgets and an unquantized reference? Reporting approximation error and regularity violations would help assess whether contraction provides a meaningful benefit at practical bit widths.

  • How does the proposed construction behave when forward evaluation also uses finite-precision arithmetic? Could the authors provide a small experiment measuring how rounding in activations and intermediate computations affects approximation accuracy and regularity relative to a high- precision reference? This would clarify the deployment relevance of the current results.

3 comments

Thank you for the helpful suggestions. We report the new experimental results below and will incorporate them into the appendix in the final version. We report the results below and will add the appendix section shortly. Exact Euclidean Lipschitz computation is NP-hard for general ReLU networks [1]. In 1D, our constructive interpolant allows exact global Lipschitz and uniform-error computation for our test functions, making comparisons directly verifiable. Higher-dimensional grid-based regularity checks remain possible but become costly. In addition, the (N+1)D(N+1)^D grid nodes (D=dnD=dn) make storage grow rapidly with resolution and dimension. We therefore use d=n=1d=n=1 for the accuracy-regularity sweep and three tokens for the rounding test.

W1/W2/Q1: accuracy, regularity and storage. Direct truncates output coefficients toward zero; Cert scales them by 1−ρc1-\rho_c and then truncates, where ρc=21−sN<1\rho_c=2^{1-s}N<1 (Lemma 5.1). We test f1(x)=∣x−1/3∣f_1(x)=|x-1/3|, f2(x)=x−x2/2f_2(x)=x-x^2/2, and f3(x)=xf_3(x)=x on [0,1][0,1], with d=n=λ=L=1d=n=\lambda=L=1, grid resolution NN, and ss fractional bits.

Direct quantization frequently violates the prescribed regularity bound. Direct exceeds L=1L=1 in 609 of 1068 tested configurations, whereas Cert has no violations, consistent with its theoretical guarantee. The scan covers three targets, each with 356 grid-precision pairs satisfying ρc<1\rho_c<1 within N=2,…,39N=2,\ldots,39 and s=3,…,14s=3,\ldots,14. This benefit comes with an accuracy trade-off: Cert has larger/equal/smaller uniform error in 948/1/119 comparisons, with a median error increase of 0.0201.

Table entries are uniform error / global Lipschitz constant; bold exceeds 1. Uniform errors are computed from error extrema. The unquantized reference can have finite-grid interpolation error; it has no coefficient-quantization error and is excluded from the finite-bit budget comparison. Within each row, Direct and Cert use (14N+29)w(14N+29)w bits, where w=1+s+⌈log⁡2(max⁡{N,2}+1)⌉w=1+s+\lceil\log_2(\max\{N,2\}+1)\rceil, counting fixed parameters and zero output coefficients.

Target, (N,s)(N,s), bitsUnquantizedDirectCert
f1f_1, (31,7), 60190.0143 / 10.0104 / 1.21090.3229 / 0.7266
f1f_1, (17,11), 45390.0261 / 10.0260 / 1.00440.0254 / 0.9878
f1f_1, (9,14), 29450 / 10.000054 / 1.00030.000773 / 0.9992
f2f_2, (11,11), 29280.00103 / 0.95450.00138 / 0.95070.00657 / 0.9399

At the same storage cap, Direct can be more accurate while also satisfying L=1L=1. On f2f_2, under 2945 bits, the best scanned Direct model with Lip ≤1\le1 has error 0.001383 at (N,s)=(11,11)(N,s)=(11,11) (2928 bits); the best scanned Cert model has error 0.002133 at (9,14)(9,14) (2945 bits). Both satisfy L=1L=1. Cert guarantees this through contraction; Direct's regularity is checked after construction.

W3/Q2: rounded forward evaluation. FP16 largely retains approximation accuracy here, and stronger contraction reduces observed input sensitivity. We test F(X)=(max⁡i∣xi−1/3∣,∣x2−1/3∣,1−∣x3−2/5∣)F(X)=(\max_i|x_i-1/3|,|x_2-1/3|,1-|x_3-2/5|) with d=1,n=3,N=5,s=10d=1,n=3,N=5,s=10. We evaluate on 845 fixed test points covering [0,1]3[0,1]^3, including target breakpoints. NumPy FP16 rounds inputs, parameters, activations, and intermediate computations, including attention.

The exact reference uses rational arithmetic on the equivalent Kuhn interpolant, without floating-point rounding. Approximation error is the maximum output discrepancy from FF over the test points; it is separate from Lipschitz regularity. The FP16 ratio divides the largest output-component change by the input ℓ1\ell^1 distance over pairs with unrounded distance at least 0.1. A ratio above 1 proves violation of L=1L=1, but values below 1 on tested pairs do not establish a global guarantee.

Method (ρ\rho)Global ℓ1\ell^1 Lip (exact)Approx. error (exact)Approx. error (FP16)Largest tested ratio (FP16)
Direct (0)1.00100.08850.08791.0195
Cert (5/5125/512)0.99120.08760.08791.0156
Stronger contraction (1/101/10)0.90330.10060.10160.9277

Cert's approximation error changes only from 0.0876 to 0.0879, but its FP16 ratio of 1.0156 proves violation of L=1L=1. Stronger contraction lowers the largest tested ratio to 0.9277 at higher error (0.1016). It reduces sensitivity on these pairs without proving global regularity.

The construction also suggests leaving a margin at gate thresholds. In Lemma C.4 (proof, Step 3), an off-position gate stays closed when the interpolated value does not exceed its threshold. The output-magnitude bound in Cor. 5.4 provides an additional margin after contraction. Accumulated rounding error must stay within that margin to avoid incorrect activation; this condition alone does not ensure global regularity.

[1] Aladin Virmaux and Kevin Scaman. "Lipschitz Regularity of Deep Neural Networks: Analysis and Efficient Estimation." NeurIPS, 2018. https://arxiv.org/abs/1805.10965

Thank you to the authors for their response. My concerns have been adequately addressed, and I will maintain my original score.

Thank you very much for your time and feedback. We are glad the additional results were helpful, and we will further polish the experimental details as we prepare the next version of the manuscript.

Reviewer_UjifOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper investigates the properties of Transformers with finite-precision, fixed-point-format weights, yet an exactly computed forward pass, in approximating Hölder-continuous functions. The main technical contribution lies in deriving upper bounds on the required number of bits per parameter and the total number of parameters, based on the target approximation error, while simultaneously ensuring that the Holder seminorm of the Transformer matches that of the approximated function. In the spirit of constructive approximation, the specific Transformer architecture underlying the proofs is highly artificial and distant from the real-world Transformer usage; it is further studied how well one can learn a fixed-point Transformer from this class via empirical risk minimization.

Critical strengths

The construction of the specific Transformer architecture is presented in a clear and detailed manner, while particular structural decisions behind its design are sufficiently motivated to facilitate the verification and comprehension of proofs.

Critical weaknesses
  1. The gap between how this paper is motivated and what is actually constructed is hard to overlook. The Introduction and Remark 5.3 frame the problem around practical LLM quantization and error propagation across layers, yet the actual construction completely disables the attention mechanism and acts as a basic wrapper around a hat-function interpolant. Moreover, it is only the output weight matrix that is "quantized".
  2. The main selling point of the paper is preservation of a prescribed regularity bound under fixed-point parameters, as the title, abstract, and introduction suggest. Nevertheless, the empirical-risk-minimization theorem omits this constraint entirely (as acknowledged in Remark 6.2), which begs the question: does this analysis belong to this paper in its current form?
Questions for authors
  1. Is there a fundamental obstacle to extending the empirical-risk-minimization analysis to the setting of preserved regularity bounds?
  2. The current analysis ignores the matrix nature of the Transformer inputs by vectorizing them. Is there any way within the constructive-approximation framework to leverage the token-wise structure to improve the parameter-count scaling?
4 comments

W1. Thank you. We agree the motivation exceeded the construction and narrowed the Abstract and Secs. 1 and 4 to exact-forward storage in our constructive setting. Remark 5.3 only notes a layer-wise precision parallel (coarse internal weights, higher-precision output layers), and we dropped its mention of error propagation. Two clarifications follow.

  • Non-output parameters are target-independent and discrete (weights in 0,±1,±1/2\\{0,\pm1,\pm1/2\\}, integer grid biases, and integer scaling/gating constants). Every parameter is stored without rounding error in the common fixed-point format and counted in the bit budget (Thm. 5.2(2)), so only the output-coefficient matrix W(Δ)W^{(\Delta)} needs to be quantized.
  • The attention layer is deliberately simple. With WQ=WK=0W_Q=W_K=0, it performs uniform gathering as in Lai and Sun [1, Lemma 8]. As the sole cross-token step, it gives each token Xflt/nX^{\mathrm{flt}}/n, and the post-attention feedforward block (Fpost\mathcal F_{\mathrm{post}}) then evaluates the interpolant. Our contribution is the precision and regularity analysis under this realization, rather than in a new constructive approximation via attention.

W2 and Q1. There is no fundamental obstacle. New Prop. 6.2 (App. E.4) restricts TNm,sm′\mathcal T_{N_m,s_m'} to the subclass Hm\mathcal H_m satisfying the componentwise ℓ1\ell^1-Hölder and sup-norm bounds LL on [0,1]d×n[0,1]^{d\times n}, linking Sec. 6 to Cor. 5.4's regularity bound while keeping Thm. 6.1 as an unconstrained baseline. Exact ERM over Hm\mathcal H_m attains the same risk bound, O((log⁡(em)/m)2λ/(2λ+D))O((\log(em)/m)^{2\lambda/(2\lambda+D)}). Hong and Kratsios [2, Sec. 4.2] likewise constrain their network class by a Lipschitz bound.

The key idea in Prop. 6.2 is to keep the approximation–complexity balance of the finite-class bound (Thm. E.1). By Lemma 5.1, the contracted, quantized approximant preserves the bound LL at ρm=(D/(2Nm))λ\rho_m=(D/(2N_m))^\lambda whenever 2⋅2−sm′Nmλ≤ρmL2\cdot 2^{-s_m'}N_m^\lambda\le\rho_m L. Prop. 6.2 ensures this by choosing sm′=⌈2λ2λ+Dlog⁡2m+cD,L,λ⌉s_m'=\lceil\frac{2\lambda}{2\lambda+D}\log_2 m+c_{D,L,\lambda}\rceil, where cD,L,λc_{D,L,\lambda} depends on D,L,λD,L,\lambda. This doubles the coefficient of log⁡2m\log_2 m in Thm. 6.1's schedule and adds an mm-independent offset, while remaining O(log⁡m)O(\log m) for fixed D,L,λD,L,\lambda. The resulting approximant lies in Hm\mathcal H_m with error O(Nm−λ)O(N_m^{-\lambda}), while log⁡∣Hm∣≤log⁡∣TNm,sm′∣=O(DGNmlog⁡m)\log|\mathcal H_m|\le\log|\mathcal T_{N_m,s_m'}|=O(DG_{N_m}\log m) retains the same upper bound. Plugging both bounds into Thm. E.1 yields the same risk bound.

Q2. Yes in principle under cross-token target structure, though not within our uniform-attention construction. Under permutation equivariance (f(XΠ)=f(X)Πf(X\Pi)=f(X)\Pi) on compactly supported continuous targets in LpL^p (1≤p<∞1\le p<\infty), Yun et al. [3, Thm. 2, Sec. 4.4] pair attention contextual codes with one shared token-wise feedforward map. At grid width hh, this cuts the parameter bound from O(dnh−dn)O(dn h^{-dn}) (flattened) to O(dnh−dn/n!)O(dn h^{-dn}/n!), saving n!n! in the prefactor while keeping the 1/h1/h exponent dndn. Reducing the worst-case 1/ε1/\varepsilon storage exponent requires assumptions that lower the metric-entropy exponent.

In contrast, our construction evaluates the dndn-output HK interpolant at the same XfltX^{\mathrm{flt}} on every token and uses positional gating to select each token's output. It therefore cannot exploit permutation equivariance in the same way as [3] without changing the post-attention token representations and routing.

In addition, on the general componentwise Hölder class (∥fpq∥C0,λ≤L\|f_{pq}\|_{C^{0,\lambda}}\le L), new Remark 5.5 shows from existing metric-entropy and code-length bounds that, at fixed d,n,L,λd,n,L,\lambda, uniform accuracy ε\varepsilon requires Ω(ε−dn/λ)\Omega(\varepsilon^{-dn/\lambda}) bits in any complete binary encoding, and hence Ω(ε−dn/λ/log⁡(1/ε))\Omega(\varepsilon^{-dn/\lambda}/\log(1/\varepsilon)) fixed-position parameters at O(log⁡(1/ε))O(\log(1/\varepsilon)) bits each. Our complete fixed-position encoding matches this bit lower bound in ε\varepsilon up to log⁡(1/ε)\log(1/\varepsilon), leaving room on this class only in prefactors (including (d,n)(d,n)-dependence) and log⁡(1/ε)\log(1/\varepsilon) factors.

[1] Yanming Lai and Defeng Sun. "Standard Transformers Achieve the Minimax Rate in Nonparametric Regression with Cs,λC^{s,\lambda} Targets." arXiv, 2026. https://arxiv.org/abs/2602.20555

[2] Ruiyang Hong and Anastasis Kratsios. "Bridging the Gap between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity." arXiv, 2024. https://arxiv.org/abs/2409.12335

[3] Chulhee Yun et al. "Are Transformers Universal Approximators of Sequence-to-Sequence Functions?" ICLR, 2020. https://openreview.net/forum?id=ByxRM0Ntvr

Thank you for your thoughtful review and the time you've invested in evaluating our work. As the discussion phase nears its end, we wanted to check, at your convenience, if there are any remaining questions or concerns regarding our rebuttal that we can clarify. We appreciate your time and look forward to any further feedback.

Reviewer_UjifOpenReview ↗

Thank you for the clarifications

I would like to thank the authors for their clarifications. My main criticism was, and is, that the paper is about transformers, yet it disables the attention mechanism entirely. While I sympathise with the response that the authors give and also value theoretical inquiry under simplifying assumptions, this assumption on the construction is in my eyes taking away the most fundamental part of a transformer. This issue was acknowledged and not resolved in the response. The paper is otherwise solid but, in my view, not strong enough for ICLR, which is why I gave a score of 2, which I will keep.

AuthorsOpenReview ↗

Thank you for your careful reading

Thank you for explaining your concern. We apologize for not clearly explaining the rationale for our attention design in our reply to you. Part of this explanation appeared only in our response to Reviewer cxJN.

We chose uniform gathering because its exactly representable internal parameters allow us to study approximation, finite-precision storage, and regularity together. Richer attention-based approximation constructions do exist, but we have not established our joint guarantees for those constructions. We understand why this limitation affects your assessment of the paper.

We appreciate your recognition of the paper’s soundness and your thoughtful feedback on its scope and significance. Your comments have helped us sharpen the motivation and distinguish more clearly what our results establish from what remains open. Thank you for the time and consideration you have given our work.

Comments on the paper

1 comment

We thank all reviewers for their careful reading. The revised manuscript marks changes in blue.

Main revisions

  1. New Prop. 6.2 (regularity-constrained ERM). Exact ERM over the subclass satisfying the prescribed ℓ1\ell^1-Hölder bound attains the same risk upper-bound order as Thm. 6.1, with a finer precision schedule. Proof in App. E.4. (Ujif W2/Q1, cxJN W3/Q3)
  2. New Remark 5.5 (storage lower bound). By metric-entropy and bit-complexity bounds [1–3], any binary representation that ε\varepsilon-approximates every target in the Hölder ball needs Ω(ε−D/λ)\Omega(\varepsilon^{-D/\lambda}) bits. Encoding all allowed parameter positions of our construction (including zero output weights) takes O(ε−D/λlog⁡(1/ε))O(\varepsilon^{-D/\lambda}\log(1/\varepsilon)) bits, so for fixed d,n,L,λd,n,L,\lambda token structure alone cannot reduce the exponent dn/λdn/\lambda. (Ujif Q2, cxJN Q1)
  3. Attribution. Our Transformer realization (Lemma C.5) refines Lai and Sun [4, Lemma 8]. This attribution is stated in Section 2 and App. C. (cxJN W1)
  4. Scope. The abstract and Sections 1 and 4 now present the exact-forward setting and the separation of exactly stored hidden parameters from quantized output coefficients, while Remark 5.3 removes the sentence on error propagation to match this scope. (Ujif W1, cxJN W2)
  5. Metric. Remark 6.3 states that the ℓ1\ell^1 bound LL implies a Euclidean seminorm of at most Dλ/2LD^{\lambda/2}L, not necessarily LL. (cxJN W3)
  6. Experiments. We report matched-storage comparisons and runtime-rounding diagnostics in our response to v4x1, and will incorporate them into the appendix in the final version. (v4x1)

[1] A. N. Kolmogorov and V. M. Tikhomirov. "ε\varepsilon-entropy and ε\varepsilon-capacity of sets in function spaces." Uspekhi Matematicheskikh Nauk 14(2):3–86, 1959 (English transl. in Selected Works of A. N. Kolmogorov, Vol. III, pp. 86–170, Springer, 1993).

[2] Weigutian Ou, Philipp Schenkel, and Helmut Bölcskei. "Three Quantization Regimes for ReLU Networks." arXiv:2405.01952, 2024. https://arxiv.org/abs/2405.01952

[3] Tong Mao and Jinchao Xu. "Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View." arXiv:2608.01357, 2026. https://arxiv.org/abs/2608.01357

[4] Yanming Lai and Defeng Sun. "Standard Transformers Achieve the Minimax Rate in Nonparametric Regression with Cs,λC^{s,\lambda} Targets." arXiv:2602.20555, 2026. https://arxiv.org/abs/2602.20555

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.