{"id":"d5099838-bfc7-41a6-98ca-113cf7eead14","arxiv_id":"2505.12252","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"SchoenbAt approximates dot-product kernelized attention with random Maclaurin features under Schoenberg's theorem, adding a batch-normalization step that keeps inputs within the theorem's domain.","lead":"Kernelized attention can be approximated by random Maclaurin features with polynomial basis weights, giving a fast attention layer called SchoenbAt that scales linearly with sequence length. The paper warrants attention for its speed claims, but the proof that the approximation is unbiased contains a clear mathematical gap.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unbiasedness proof in Appendix A.3 equates E[RMFA] with a ratio of expectations for dependent numerator and denominator; without this invalid step Theorem 3 does not follow.","rationale":"The paper's central contribution is a claimed unbiased random-feature approximation of dot-product kernelized attention. The single most load-bearing step is in Appendix A.3: after Equation (5), the proof writes E[RMFA] as a ratio of expectations. RMFA is literally a quotient of two random sums built from the same D random Maclaurin features, so numerator and denominator are dependent and E[A/B] = E[A]/E[B] does not hold. This is not a minor gap: Theorem 3 states exactly that E[SchoenbAt_K(Q,K,V)] = attn_K(Q,K,V), and Theorem 4 is the only other theoretical support. The Theorem 4 proof has an independent defect as well: it replaces the event that an average deviates by a union over individual feature deviations, which is not equivalent to the actual event, and it applies Hoeffding to non-centered ratio terms. The ℓ2(0,1) assertion in A.3 is also false as stated, and the proof does not use the ppSBN-normalized inputs; the 'properly trained' parameters γ and β are assumed, not shown, to restore the expectation. The numerical approximation-error experiments and LRA results are appreciable and may indicate the method works in practice; however, they do not compensate for the unsupported central theorem, and the paper explicitly claims a rigorous theoretical proof of unbiasedness as a foundation. I therefore agree with the reader's REJECT verdict and see no reason to change it.","tokens_in":14755,"tokens_out":7018,"duration_ms":72700,"concrete_test":"Independently verify Appendix A.3 in the minimal nontrivial setting: fix d≥2, n=2, choose fixed Q, K, V, set D=1, and compute by Monte Carlo over the Rademacher vectors and geometric N in the RMF definition both E[RMFA_K(Q,K,V)] and attn_K(Q,K,V) for the exp kernel. If these differ by more than the Monte Carlo standard error, the step E[num/den] = E[num]/E[den] in A.3 is invalid and Theorem 3 fails as stated. Repeating the same check with the ppSBN-normalized inputs Q_SBN, K_SBN would also test whether the restoration asserted in Equation (5) actually holds in expectation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central theoretical claim is Theorem 3 (Appendix A.3): E[SchoenbAt_K(Q,K,V)] = attn_K(Q,K,V). The proof reduces to writing E[RMFA_K] as (Σ_i E[ϕ(Q)ϕ(K_i)] V_i) / (Σ_j E[ϕ(Q)ϕ(K_j)] 1_d^T). This is an expectation of a ratio replaced by the ratio of expectations. The numerator and denominator are built from the same random Maclaurin features, so they are dependent; even if each feature map is unbiased for the kernel, E[num/den] ≠ E[num]/E[den] in general. For positive denominators, Jensen's inequality gives a strict gap unless the denominator is constant. Thus Theorem 3 is not established by the supplied proof. Theorem 4 does not repair this: its proof rewrites the deviation event as 'there exists a feature φ_t such that ...' and unions over t, but RMFA averages features in both numerator and denominator; that event decomposition does not match the actual estimator, and Hoeffding is applied to individual uncentered ratio terms. A further issue is that A.3's assertion that Q/d^{1/4}, K/d^{1/4} ∈ ℓ2(0,1) follows from d≥1 is false in general, and the proof never uses the ppSBN-normalized inputs that are actually fed to RMFA. The 'properly trained' assumption for γ and β is also not a theorem; it is an unproved condition. The empirical results may indicate the method is practically useful, but the load-bearing theoretical guarantee claimed in the abstract and in Theorem 3 is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SchoenbAt, an approximation of dot-product kernelized attention using random Maclaurin features based on Schoenberg's theorem, with a two-stage normalization (ppSBN) intended to keep inputs in a bounded domain and restore output scale. The authors claim an unbiasedness result (Theorem 3) and a concentration bound (Theorem 4), and they report experiments on synthetic approximation error, speedup, and the LRA benchmark, together with an ablation study. The central theoretical contribution is the characterization of SchoenbAt as an unbiased estimator of kernelized attention.","tokens_in":15133,"tokens_out":2909,"duration_ms":31006,"significance":"If the theoretical guarantees were valid, the paper would offer a useful alternative to Fourier-based random feature attention by directly expanding dot-product kernels in a polynomial basis, with a complexity of O(ndD) and empirical speedups on long sequences. The empirical evaluation is broad: five kernels, synthetic convergence checks, and LRA comparisons with several efficient attention baselines. The anonymous code link and reproducible experimental protocol are positive features. However, the load-bearing theoretical results are not established: the unbiasedness proof contains an invalid expectation-of-ratio step, the concentration proof mischaracterizes the estimator's randomness, and the key domain assumption is unjustified. As a result, the paper's main claims of guaranteed approximation quality are unsupported, and the contribution reduces to an empirically tested heuristic.","major_comments":[{"comment":"The proof of Theorem 3 replaces E[RMFA_K(Q,K,V)], which is the expectation of a ratio, with a ratio of expectations. In the displayed equations, the numerator and denominator are built from the same random Maclaurin features phi(Q/d^{1/4}) and phi(K_i/d^{1/4}), so they are dependent random variables. For positive denominators, Jensen's inequality shows E[N/D] != E[N]/E[D] in general unless D is constant. Therefore the claimed unbiasedness E[SchoenbAt_K(Q,K,V)] = attn_K(Q,K,V) does not follow from the supplied argument.","section":"Appendix A.3, Theorem 3"},{"comment":"The proof of Theorem 4 rewrites the deviation event as the existence of a single feature phi_t whose ratio deviates from attn_K, and then unions over t. This does not match the actual estimator: both the numerator and denominator of RMFA are averages over all D random features, and the deviation of the averaged ratio cannot be decomposed into independent single-feature events. Moreover, Hoeffding's inequality is applied to the uncentered ratio terms without verifying their range or independence. Consequently the bound P(|SchoenbAt_K(D)-attn_K(D)|>epsilon) <= 2D exp(-D epsilon^2/(2 S^2 d^2)) is not established.","section":"Appendix A.4, Theorem 4"},{"comment":"The claim that 'with d>=1, we can ensure that Q/d^{1/4}, K/d^{1/4} in ell_2(0,1)' is false in general: arbitrary attention inputs can have arbitrary norms, and dividing by d^{1/4} does not place them in the unit ball. The actual algorithm feeds the ppSBN-normalized inputs QSBN and KSBN to RMFA, but the proof of Theorem 3 uses the unnormalized Q and K. This gap affects both Theorem 3 and Theorem 4, since the input-domain assumption is needed for Schoenberg's theorem to apply.","section":"Appendix A.3 and Section 3.3"},{"comment":"The condition that 'the parameters gamma and beta are properly trained to restore the attention output' is not a mathematical assumption that can be verified or guaranteed. The proof of Theorem 3 relies on Equation (5), which already presupposes the exact restoration property expressed by Theorem 2 and the fitted gamma, beta. The toy experiment in Figure 3 only shows that training with ppSBN reaches similar loss, perplexity, and BLEU scores; it does not establish equality of the output with attn_K. Thus the unbiasedness result is conditional on an unproved learned-correction assumption.","section":"Theorem 3 statement and Algorithm 1"}],"minor_comments":[{"comment":"The notation X/Y for element-wise division is nonstandard and could be confused with matrix division; it should be defined more prominently or replaced with a symbol such as ⊘.","section":"Section 2.1"},{"comment":"There is a typo: 'Combinign' should be 'Combining'. The proof of Theorem 2 is also difficult to follow because the definitions of r, s, and t are introduced only after they are used; reorganizing the derivation would improve readability.","section":"Appendix A.2"},{"comment":"The caption says 'reporting normalized training time and prediction accuracy under different settings', but the row labels 'exp(.) inv(.) logi(.) trigh(.) sqrt(.)' are ambiguous; they should be clearly identified as the kernel choices for the RMFA and SchoenbAt configurations.","section":"Table 3 caption"},{"comment":"The statement that the approximation error 'confirms our Theorem 4' is too strong: a numerical decrease in error with increasing D is consistent with many convergence mechanisms and does not by itself validate the specific exponential bound in Theorem 4.","section":"Section 4.1"}],"recommendation":"reject","confidential_remarks":"The central theoretical claims in Theorems 3 and 4 are not supported by the provided proofs, and the errors are not localized presentation issues: they concern the core argument that SchoenbAt is an unbiased and concentrated approximation. The empirical results alone may be of interest to a small community, but they do not compensate for the invalid theoretical foundation claimed in the abstract and introduction. I recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about this paper. First, the empirical story is real and reasonably complete: SchoenbAt is a faster attention mechanism that uses random Maclaurin features to approximate dot-product kernels, and the LRA results show competitive accuracy with substantial speedups. The code is available, and the ablation isolating RMFA and ppSBN is useful. Second, the theoretical backbone is not sound. The proof of Theorem 3, which claims unbiasedness, replaces the expectation of a ratio of dependent random variables with the ratio of their expectations. That step is false in general, and since numerator and denominator share the same random features, the theorem is not established. The concentration bound in Theorem 4 has a similar problem: it treats the averaged estimator as if the deviation event could be decomposed into single-feature events, which doesn't match the actual estimator.\n\nWhat is genuinely new here is the application of Kar and Karnick's random Maclaurin features to attention, justified via Schoenberg's theorem, and the ppSBN normalization that keeps inputs in the bounded domain required by the theorem. That is a reasonable extension of existing random-feature attention work, even if the components are known. The empirical comparison with Performer, RFA, and others on LRA is competent and gives a fair picture.\n\nThe soft spots are mostly in the theory. Apart from the expectation/division error, the paper assumes that the trainable γ and β are 'properly trained to restore the attention output' without proving that training converges to such values. That makes the unbiasedness claim conditional in a way that isn't explored. Also, the claim that Q/d^{1/4} ∈ ℓ2(0,1) for d≥1 is not true in general; the proof would need a bound on the norms of the inputs, which is exactly what ppSBN is supposed to provide, but the proof doesn't use the normalized inputs. So the proof doesn't actually rely on the mechanism that makes the theorem plausible.\n\nWho is this for? If you work on efficient transformers, the empirical results are worth a look. The paper deserves a serious referee because the idea is plausible and the experiments are substantial, but the theory needs major repair. My recommendation: send it to review, but with the expectation that the authors will need to either fix the proofs or significantly weaken the claims. As it stands, I wouldn't rely on the unbiasedness guarantee.","headline":"SchoenbAt is a plausible efficient-attention idea with solid experiments, but its central unbiasedness theorem is not proven — the proof swaps expectation and division for dependent random variables.","tokens_in":15592,"tokens_out":2318,"would_cite":false,"duration_ms":21748,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Polynomial-basis random Maclaurin features make dot-product kernelized attention unbiased and linear-time.","keywords":["kernelized attention","random Maclaurin features","Schoenberg's theorem","polynomial basis","efficient transformers","dot-product kernels","unbiased approximation"],"falsifier":"Fix a Q, K, V and a dot-product kernel with non-negative Maclaurin coefficients such as exp(·), draw many independent random feature sets with a fixed D, and compute the empirical average of SchoenbAt's output alongside the exact kernelized attention; if the average differs from the exact value by more than Monte Carlo error even as D grows, the claimed unbiasedness is not empirically supported. A more targeted check compares E[numerator]/E[denominator] with E[numerator/denominator] on the same feature draws to isolate the ratio-of-expectations step.","tokens_in":14553,"feed_emoji":"⚡","tokens_out":6412,"duration_ms":65751,"temperature":0.7,"pith_summary":"SchoenbAt re-expresses dot-product kernelized attention, the family that includes softmax attention when the kernel is exponential, as a polynomial basis expansion guaranteed by Schoenberg's theorem. Instead of forming the n by n attention matrix, it estimates each polynomial term with random Maclaurin features, cutting the computation from O($n^{2}$ d) to O(ndD), where D is the number of random features. A pre-post scaling batch normalization keeps the input in the bounded domain the theorem requires and rescales the output so that the estimator can remain unbiased. The paper proves unbiasedness in expectation and a concentration bound that shrinks as D grows, and shows on the Long Range Arena tasks that the replacement speeds up training while keeping accuracy competitive.","feed_headline":"Polynomial basis makes dot-product attention unbiased and linear-time","feed_subtitle":"A random Maclaurin feature map plus rescaling cuts quadratic attention cost to O(ndD).","key_machinery":"The load-bearing object is the Random Maclaurin Feature map Phi_K(x) = $\\sqrt$(1/D)[phi_1(x), ..., phi_D(x)], with each phi_i(x) = $\\sqrt$(a_N $p^{{N+1}}$) prod_{j=1}^N <omega_j, x>, where N is drawn from a geometric law, a_N is the N-th Maclaurin coefficient of the dot-product kernel, and the omega_j are Rademacher vectors. Its inner product reproduces, in expectation, the polynomial expansion that Schoenberg's theorem says such kernels possess. The two-stage ppSBN then normalizes Q and K into the $ell^{2}$(0,1) ball required by the theorem and applies trainable parameters to reverse the scaling on the output, so the estimator targets the original attention rather than a rescaled version.","core_discovery":"The central claim is that kernelized attention with any dot-product kernel whose Maclaurin coefficients are non-negative, including the exp, inverse, logarithmic, trigonometric-hyperbolic, and square-root kernels, can be approximated by a random Maclaurin feature attention (RMFA) that is unbiased in expectation and whose error concentrates like 2D exp(-D $epsilon^{2}$ / (2 $S^{2}$ $d^{2}$)). The proof route is that Schoenberg's theorem gives a polynomial expansion, random Maclaurin features estimate that expansion, and the ppSBN mechanism keeps inputs within the required bounded domain while trainable parameters restore the original output scale. When the scaling parameters are properly trained, SchoenbAt becomes a drop-in replacement for dot-product kernelized attention with cost linear in the sequence length, and the theory says accuracy improves as the random feature dimension D increases.","pith_inferences":["The same Schoenberg basis could be applied to any other dot-product kernel with non-negative Maclaurin coefficients, turning SchoenbAt into a general library of linear-time attention variants beyond the five kernels tabulated here.","Truncating the random polynomial degree N instead of drawing it from a geometric law would produce a deterministic bias-variance trade-off that the current bounds do not yet describe.","An empirical check of the estimator's finite-D expectation over many independent feature draws would show how quickly E[SchoenbAt] approaches the exact attention, a quantity the theorem guarantees only asymptotically."],"forward_implications":["Sequence-length cost drops from O(n^2 d) to O(ndD), so the speed benefit grows as the context gets longer.","Because the approximation is unbiased in expectation, SchoenbAt can be plugged into existing Transformer layers without changing the layer's input or output signature.","The concentration bound gives a quantitative control knob: raise D when accuracy is critical, lower D when latency or memory dominates.","The exponential-kernel case behaves like softmax attention, making SchoenbAt a drop-in accelerated softmax for typical Transformers.","Among the five tested kernels, no single one strictly dominates, and the paper recommends the exponential kernel by default while leaving the kernel choice open per task."],"supporting_citations":[{"why":"Supplies Schoenberg's theorem, which guarantees the non-negative Maclaurin coefficient expansion that the entire approximation rests on.","marker":"[38]"},{"why":"Supplies the Random Maclaurin Feature construction whose inner product estimates the dot-product kernel.","marker":"[40]"},{"why":"Provides the batch normalization idea that the ppSBN scaling mechanism adapts for input bounding and output restoration.","marker":"[41]"},{"why":"Introduces random feature sampling for kernel approximation, the general technique that RMF builds on.","marker":"[26]"},{"why":"Defines kernelized attention, the computation SchoenbAt is designed to approximate.","marker":"[17]"},{"why":"Supplies the random-feature attention baseline that SchoenbAt must beat in the LRA comparisons.","marker":"[33]"},{"why":"Defines the Long Range Arena benchmark tasks where accuracy and speed are measured.","marker":"[42]"}],"fun_headline_variants":["Random Maclaurin features make attention linear-time","Schoenberg's theorem powers unbiased attention","Polynomial basis unlocks linear-time attention","Unbiased polynomial attention runs in linear time","SchoenbAt: polynomial attention without the quadratic cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The unbiasedness proof assumes that the expected numerator divided by the expected denominator equals the expected ratio, even though the numerator and denominator are dependent because they share the same random features; that equality is false in general.","fun_headline_variants_meta":{"raw":{"variants":["Random Maclaurin features make attention linear-time","Schoenberg's theorem powers unbiased attention","Polynomial basis unlocks linear-time attention","Unbiased polynomial attention runs in linear time","SchoenbAt: polynomial attention without the quadratic cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000724,"raw_usage":{"total_tokens":3221,"prompt_tokens":894,"completion_tokens":2327,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":510,"completion_tokens_details":{"reasoning_tokens":2258}},"tokens_in":510,"tokens_out":2327,"duration_ms":17543,"temperature":1.0,"reasoning_tokens":2258,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:37:26.443420+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a Q, K, V and a dot-product kernel with non-negative Maclaurin coefficients such as exp(·), draw many independent random feature sets with a fixed D, and compute the empirical average of SchoenbAt's output alongside the exact kernelized attention; if the average differs from the exact value by more than Monte Carlo error even as D grows, the claimed unbiasedness is not empirically supported. A more targeted check compares E[numerator]/E[denominator] with E[numerator/denominator] on the same feature draws to isolate the ratio-of-expectations step.","supporting_citations":[{"cited_title":"Positive definite functions on spheres.Duke Mathematical Journal, 9(1):96–108, 1942","cited_arxiv_id":null,"evidence_quote":"Supplies Schoenberg's theorem, which guarantees the non-negative Maclaurin coefficient expansion that the entire approximation rests on."},{"cited_title":"Random feature maps for dot product kernels","cited_arxiv_id":null,"evidence_quote":"Supplies the Random Maclaurin Feature construction whose inner product estimates the dot-product kernel."},{"cited_title":"Batch normalization: accelerating deep network training by reducing internal covariate shift","cited_arxiv_id":null,"evidence_quote":"Provides the batch normalization idea that the ppSBN scaling mechanism adapts for input bounding and output restoration."},{"cited_title":"Random features for large-scale kernel machines.NeurIPS 20, 2007","cited_arxiv_id":null,"evidence_quote":"Introduces random feature sampling for kernel approximation, the general technique that RMF builds on."},{"cited_title":"Transformers are Rnns: fast autoregressive transformers with linear attention","cited_arxiv_id":null,"evidence_quote":"Defines kernelized attention, the computation SchoenbAt is designed to approximate."},{"cited_title":"Long range arena : A benchmark for efficient transformers","cited_arxiv_id":null,"evidence_quote":"Defines the Long Range Arena benchmark tasks where accuracy and speed are measured."}],"review_version":1}