{"id":"89d008fc-1b3e-4333-82ec-5f0f788352ec","arxiv_id":"2411.12663","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A polynomial state-summary mixer can replace multi-head attention in diffusion transformers at linear token complexity, with competitive ImageNet generation but weaker video results and an incomplete universality proof.","lead":"The paper introduces the Polynomial Mixer (PoM), a linear-complexity building block that replaces multi-head attention in diffusion transformers for image and video generation. It reports an ImageNet FID of 2.46 with fewer training images than DiT, but the video results trail published baselines and the universality proof has a gap.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's proof is invalid: the scalar argument fails even on a simple example, so the universal-approximation claim for PoM is unproven; the central 'just like MHA' contribution rests on this gap.","rationale":"The reader identified Lemma 3 as the weakest assumption; I agree. My stress test found a concrete counterexample to the proof's central step, making the gap more severe than a mere missing detail. The argument in Appendix C first discards the sigmoid and nonlinear activations, then proves a scalar claim that is false as stated. Because Theorem 2 is the paper's stated 'primarily fundamental' contribution, this is the most load-bearing weakness. The practical results (Figure 1, Table 1) are suggestive but also suffer from the mismatched evaluation reference noted by the reader, which reinforces the conditional verdict rather than overturning it. A corrected proof or a weakened claim would be needed; until then the manuscript's central theoretical assertion is unproven. I therefore keep the reader's CONDITIONAL verdict.","tokens_in":19091,"tokens_out":10872,"duration_ms":101681,"concrete_test":"Run a small script that enumerates finite sets X,X' of small integers (e.g., entries 1..10, size ≤4) and, for each k=1..10 with S_k != S'_k, checks whether there exist x∈X, x'∈X' with x*S_k = x'*S'_k. The pair X={2,3}, X'={1,9}, k=1 (2*5=1*10) already falsifies the proof's key assertion. If any such counterexample occurs for every k with differing sums, the scalar version of Lemma 3 is false. At minimum, the authors must supply a corrected choice of k or a proof for the sigmoid-gated PoM before Theorem 2 can be accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline contribution rests on Theorem 2 (universal approximation), which is inherited from Yun et al. [81] via Lemma 3 (contextual mapping). Appendix C's proof has two fatal gaps. First, it reduces to identity weight matrices and linear activations, discarding the sigmoid gating in Eq. (3); this reduction is not justified for the actual PoM. Second, the scalar argument is logically inverted: after finding k with S_k != S'_k, it assumes the existence of one pair (x,x') with x*S_k = x'*S'_k and then claims this would force the ratio x/x' to be constant for all pairs, which is a non sequitur. The assumption is existential, not universal. In fact, for X={2,3}, X'={1,9}, k=1, S=5, S'=10, and 2*5 = 1*10, so the asserted inequality is false. No alternative argument is provided to extend the scalar power-sum step to the full matrix-nonlinear PoM. Since the abstract and Section 6 explicitly tout universality as a primary contribution, Theorem 2 is currently unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Polynomial Mixer (PoM), a sequence-to-sequence block intended as a drop-in replacement for multi-head attention (MHA). PoM computes a fixed-size state by applying a degree-k polynomial expansion to each token and pooling across tokens, then gates this state per token with a sigmoid; the block has linear complexity in the number of tokens and can be trained in parallel while supporting sequential inference via causal or block-causal masks. The authors prove permutation equivariance, claim a universal approximation theorem for Polymorphers, and validate the approach by replacing MHA in DiT-style image and video diffusion models, reporting an ImageNet FID of 2.46, ablations over polynomial degree, scaling-law experiments, and VBench video results.","tokens_in":19382,"tokens_out":5720,"duration_ms":57468,"significance":"If fully established, the paper would make a meaningful contribution: a linear-complexity attention replacement with an explicit state, universal approximation guarantees, and competitive generative performance would be of broad interest. The paper has notable strengths: the code is released, the degree ablation and scaling-law experiments are informative, the block-causal video formulation is clearly described, and the authors are candid about limitations of their FID reference set and video training data. However, the central theoretical claim depends on Lemma 3, whose appendix proof contains a genuine logical gap, and the headline experimental comparisons are not directly comparable to the cited baselines. The current evidence therefore does not fully support the strong claims made in the abstract and Section 6.","major_comments":[{"comment":"The proof of Lemma 3 is not valid for the actual PoM defined in Eq. (3). It begins by removing the learned matrices and treating the weights as identity or full-rank, then replaces all activations with linear ones. This discards the sigmoid gating in Eq. (3) and the nonlinear activation h in Eq. (4), which are essential to the PoM operation. The statement that a similar argument holds for full-rank matrices and piecewise-linear activations is not demonstrated and does not preserve the polynomial structure used in the rest of the proof. Consequently, the contextual mapping property is not established for the true PoM.","section":"Appendix C, Lemma 3"},{"comment":"The scalar argument after Eq. (24) is logically inverted. The proof assumes there exist x in X and x' in X' such that x S_k = x' S'_k and then claims this would force the ratio x/x' to be constant for all pairs. The assumption is existential, not universal, so the contradiction does not follow. A concrete counterexample to this step is X={2,3}, X'={1,9}, k=1, where S_k=5 and S'_k=10 and 2*5=1*10. Since Theorem 2 is inherited from [81] only through Lemma 3, the universal approximation claim is currently unsupported.","section":"Appendix C, Eq. (21)-(26)"},{"comment":"The comparison between the reported FID of 2.46 and DiT's 2.27 is not meaningful as presented. The footnote states that DiT, SiT, and other marked methods are evaluated against the ImageNet training set, while the authors use the ADM evaluation archive. Using different reference sets can change FID substantially, and the paper itself notes that FID is highly sensitive to the reference set. Without re-evaluation on the same reference set and ideally with multiple seeds or error bars, the statement in Section 5.1 that the results are \"on par with the literature\" is not quantitatively supported.","section":"Table 1"},{"comment":"The video results are far below all reported published baselines on most VBench metrics, for example Multiple Objects (1.9% vs. 25.9-33.3%), Appearance Style (2.8% vs. 39.3-52.7%), and Overall Consistency (15.1% vs. 25.2-26.4%). The authors' disclaimer that the comparison is unfair because the baselines were trained on larger and richer datasets is honest, but it also directly undermines the claim in Section 1 that the video models do not sacrifice visual quality. The section should be reframed as a study of the block-causal mask and a proof of concept, not as evidence of competitive quality.","section":"Table 3"}],"minor_comments":[{"comment":"There is a typo in \"universal senquence-to-sequence approximator;\" it should read \"sequence-to-sequence.\"","section":"Section 6"},{"comment":"In the proof of Lemma 3, the sentence \"Assuming ker(Wo) =\" is missing the right-hand side; it should be something like \"ker(Wo) = {0}\" or \"ker(Wo) is trivial.\" Also, the notation x' is used both for an element of X' and for the set X' in Eq. (21), which is confusing.","section":"Appendix C"},{"comment":"The entry \"39/0%\" for ModeScope's Multiple Objects appears to be a typo and should likely be \"39.0%\".","section":"Table 3"},{"comment":"The timing plot shows a single measurement setup without error bars or details on batch size, token count, or number of warm-up iterations; reporting these details or repeated runs would strengthen the complexity claim.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The core issue is that the paper's headline theoretical contribution is currently unsupported by the supplied proof, and the main empirical comparisons are not directly comparable. I would like to see either a corrected proof of Lemma 3 or a clearly stated withdrawal of the universal approximation claim, together with a re-evaluation of at least the image results on the same reference set as DiT. The PoM architecture and its linear-complexity properties remain interesting; the revision should bring the claims in line with the evidence."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a look if you care about efficient diffusion transformers. The Polynomial Mixer is a clean idea: summarize the whole token sequence into a fixed-size polynomial state, then let each token gate that state. It is linear in tokens, gives O(1) autoregressive inference with a causal or block-causal mask, and the code is released. The ImageNet experiment is genuinely encouraging: an XL/2 model trained for half the steps DiT used gets FID 2.46, and the authors are honest that the reference sets differ, so it is not directly comparable to DiT's 2.27. They also show a sensible degree ablation and scaling curves. That part of the paper deserves credit.\n\nThe soft spots are real, though. The headline theoretical claim—that PoM is a universal sequence-to-sequence approximator just like MHA—does not hold up on inspection. Lemma 3's proof in Appendix C has exactly the gap the stress test flags. It reduces to identity weight matrices and linear activations, which sidesteps the actual PoM with its sigmoid gating, and the scalar argument is logically inverted: from an existential pair with x·S = x'·S' it concludes the ratio x/x' would have to be constant for all pairs, which does not follow. The counterexample with X={2,3}, X'={1,9} shows the asserted inequality is false even in the simplified setting. So Theorem 2 is currently unsupported. That matters because the abstract and discussion explicitly sell universality as a primary contribution.\n\nThe video results are also far below published baselines. The authors say the comparison is unfair because they train on WebVid-2M only, which is fair, but the gap is huge—V-DiPoM scores single digits on several VBench dimensions—and there is no matched-budget comparison against a DiT-style baseline trained on the same data. On the image side, the lack of error bars and the different reference sets are minor but worth noting.\n\nWho is this for? People designing sub-quadratic alternatives to attention for generative vision. The architecture itself is worth knowing and reproducing, and the code helps. But the paper needs a corrected Lemma 3 proof, or the universality claim needs to be downgraded to a conjecture or removed. It also needs a matched-budget evaluation, ideally with released checkpoints. I would send it to a serious referee, but the referee should be told the proof is currently the main obstacle, not a stylistic detail.","headline":"Interesting linear-complexity attention replacement with honest ImageNet results, but the universality proof has a real gap and the video numbers are far off baselines.","tokens_in":19879,"tokens_out":1577,"would_cite":false,"duration_ms":17703,"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 mixer replaces attention in diffusion models at linear cost","keywords":["Polynomial Mixer","diffusion transformer","linear complexity","universal approximation","image generation","video generation","block-causal masking","state-space models"],"falsifier":"Compute the polynomial state $H(X)$ for two distinct token matrices $X$ and $X'$ that differ in one column, and check whether any column of $\\mathrm{PoM}(X)$ equals any column of $\\mathrm{PoM}(X')$ across a range of degrees $k$; a concrete scalar example from the appendix's own simplification—$X=\\{1,2\\}$, $X'=\\{1,5\\}$ with $k=1$, where the sums differ (3 vs 6) yet $2\\cdot 3 = 1\\cdot 6$—shows distinct sums need not yield distinct columns, so such a search (or a proof that the full matrix case avoids it) would settle whether Lemma 3 and the universality theorem hold.","tokens_in":18859,"feed_emoji":"⚡","tokens_out":10121,"duration_ms":97587,"temperature":0.7,"pith_summary":"This paper proposes replacing multi-head attention (MHA) in transformer-based diffusion models with a linear-complexity building block called the Polynomial Mixer (PoM). Instead of computing pairwise token interactions, PoM compresses the whole sequence into an explicit state—an average of high-order polynomial expansions of the tokens—that every token then queries through a learned gate. The authors prove, by adapting the standard transformer universality argument, that PoM is a universal sequence-to-sequence approximator, and they show experimentally that DiT-style image and video generators built on PoM match the quality of attention-based ones while using less compute, especially at high resolution. If correct, this means the quadratic cost of attention is not needed for state-of-the-art generative quality, and scaling to higher resolutions or longer videos becomes far cheaper.","feed_headline":"Polynomial mixer replaces attention in diffusion models at linear cost","feed_subtitle":"A state-summary mixer keeps generation quality while cutting attention's quadratic cost.","key_machinery":"The load-bearing object is the explicit state $H(X)$, a vector obtained by averaging, over all tokens, the elementwise products of activations $h(W_1 X), h(W_1 X)\\circ h(W_2 X), \\ldots$ up to degree $k$. Each token independently queries this shared state through a sigmoid gate $\\sigma(W_s X)$, and the gated state is projected back by $W_o$. This 'blackboard' summary replaces the pairwise attention matrix: because $H(X)$ is computed once per sequence, complexity drops from $O(n^2)$ to $O(n)$ in token count. The universality proof leans on Lemma 3 (contextual mapping), which asserts that a sufficiently high-degree polynomial state distinguishes every pair of distinct sequences token by token, mirroring the lemma in the standard transformer universality proof.","core_discovery":"The paper's central claim is that the Polynomial Mixer—defined by $\\mathrm{PoM}(X) = W_o[\\sigma(W_s X) \\circ H(X)\\mathbf{1}^\\top]$, where $H(X)$ aggregates products of activations up to degree $k$ across all tokens—has the same expressive power as multi-head attention for sequence-to-sequence mapping, including a universal approximation theorem, while having linear rather than quadratic complexity in sequence length. It further claims that this replacement is drop-in: adapting DiT image models and text-to-video models by swapping MHA for PoM yields samples of comparable quality (ImageNet 256×256 FID 2.46 vs DiT's 2.27 with half the training steps) and, because PoM exposes an explicit state, video frames can be generated sequentially with constant per-frame cost.","pith_inferences":["If the universality theorem holds, PoM-like state mixers could be used in place of attention in long-context and multimodal LLMs, where O(1) per-token inference and parallel training could reduce serving costs without a fixed raster scan—an extension the paper mentions but does not test.","The explicit state suggests a natural streaming-video setup: keep $H(X)$ fixed for past frames and only update the state with the new frame's polynomial expansion, which would give bounded memory for arbitrarily long videos; this follows from the recurrence in Eq. (9) but is not evaluated.","The paper's proof gap (the appendix's scalar argument does not cover the full matrix nonlinear case) implies the universality claim should be tested empirically by probing whether distinct inputs ever collide in state space; a practical consequence is that polynomial degree $k$ may need to grow with sequence length or dimension.","Since the mixer is permutation equivariant and length-agnostic, it may transfer to other set-structured tasks—point clouds, object sets, or graphs—where attention's pairwise cost is prohibitive and variable cardinality matters."],"forward_implications":["Training a DiT-XL/2-scale model with PoM at high resolutions becomes cheaper than even inference with the attention-based DiT-XL/2, according to the paper's timing measurements.","Image generation on ImageNet 256×256 reaches FID 2.46 with 950M parameters, close to DiT-XL/2's 2.27, using half the training steps (the paper also reports a flow-matching variant at FID 3.70).","For video, block-causal masking lets the model generate frames sequentially with constant per-frame cost, improving temporal metrics like dynamic degree and human action at the price of some consistency scores.","PoM shows the same log-linear scaling of FID with compute as transformer-based DiT, indicating it retains favorable scaling laws.","Because PoM is a general sequence-to-sequence block, the same mixer can replace attention in any transformer, including autoregressive language models, where causal masking yields O(1) per-token inference."],"supporting_citations":[{"why":"Supplies the proof template and the contextual-mapping lemma that the paper adapts to prove PoM is a universal sequence-to-sequence approximator.","marker":"[81]"},{"why":"The DiT architecture that PoM replaces; source of block design, naming scheme, and the main quality baseline for image generation.","marker":"[58]"},{"why":"Origin of the high-order polynomial aggregation (power-sum style state) that PoM generalizes into a mixer block.","marker":"[41]"},{"why":"Closest attention-free diffusion baseline (DIFFUSSM); its state-space approach motivates PoM's linear-complexity goal and provides a comparison point.","marker":"[79]"},{"why":"Provides the 3D VAE used to tokenize video clips for the text-to-video experiments.","marker":"[80]"},{"why":"VBench benchmark used to evaluate the video generation quality of the PoM-based models.","marker":"[39]"},{"why":"WebVid-2M dataset used to train the video generation models.","marker":"[3]"},{"why":"SiT, the flow-matching variant of DiT, used as a baseline for the flow-matching loss experiments.","marker":"[56]"}],"fun_headline_variants":["Polynomial mixer: linear cost, attention-level quality","State-based mixer drops attention's quadratic cost","Linear mixer matches attention for diffusion at lower cost","PoM: drop-in linear mixer for diffusion transformers","Mixer with explicit state: linear diffusion generation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The universal-approximation result rests on Lemma 3's assumption that a high-degree polynomial state can distinguish every pair of distinct input sequences token by token; the paper's proof establishes this only for a simplified scalar, linear-activation version, not for the full nonlinear matrix mixer.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial mixer: linear cost, attention-level quality","State-based mixer drops attention's quadratic cost","Linear mixer matches attention for diffusion at lower cost","PoM: drop-in linear mixer for diffusion transformers","Mixer with explicit state: linear diffusion generation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00116,"raw_usage":{"total_tokens":4775,"prompt_tokens":891,"completion_tokens":3884,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":3822}},"tokens_in":507,"tokens_out":3884,"duration_ms":26992,"temperature":1.0,"reasoning_tokens":3822,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:16:54.976426+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the polynomial state $H(X)$ for two distinct token matrices $X$ and $X'$ that differ in one column, and check whether any column of $\\mathrm{PoM}(X)$ equals any column of $\\mathrm{PoM}(X')$ across a range of degrees $k$; a concrete scalar example from the appendix's own simplification—$X=\\{1,2\\}$, $X'=\\{1,5\\}$ with $k=1$, where the sums differ (3 vs 6) yet $2\\cdot 3 = 1\\cdot 6$—shows distinct sums need not yield distinct columns, so such a search (or a proof that the full matrix case avoids it) would settle whether Lemma 3 and the universality theorem hold.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the proof template and the contextual-mapping lemma that the paper adapts to prove PoM is a universal sequence-to-sequence approximator."},{"cited_title":"In: ICCV (2023) 1, 2, 5, 7, 8","cited_arxiv_id":null,"evidence_quote":"The DiT architecture that PoM replaces; source of block design, naming scheme, and the main quality baseline for image generation."},{"cited_title":"In: ICCV (2019) 3","cited_arxiv_id":null,"evidence_quote":"Origin of the high-order polynomial aggregation (power-sum style state) that PoM generalizes into a mixer block."},{"cited_title":"In: CVPR","cited_arxiv_id":null,"evidence_quote":"Closest attention-free diffusion baseline (DIFFUSSM); its state-space approach motivates PoM's linear-complexity goal and provides a comparison point."},{"cited_title":"In: CVPR (2024) 8","cited_arxiv_id":null,"evidence_quote":"VBench benchmark used to evaluate the video generation quality of the PoM-based models."},{"cited_title":"In: ECCV (2024) 2, 7","cited_arxiv_id":null,"evidence_quote":"SiT, the flow-matching variant of DiT, used as a baseline for the flow-matching loss experiments."}],"review_version":1}