{"id":"aa9cdbed-d701-4cbf-908e-b089f2b4d4d2","arxiv_id":"2608.11427","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For Boolean Min-IP, a single normalized nonnegative kernel-attention head needs exponentially many features to solve all three-token sequences, even though rank one solves every sequence of length at most two and dense softmax uses m-dimensional scores.","lead":"Kernel attention compresses a sequence into a fixed-dimensional sketch, and this paper shows the compression already breaks at three tokens: any single nonnegative kernel-attention head needs exponentially many features to solve a simple Boolean minimum-overlap task. Dense softmax solves the same task with m-dimensional scores, giving a clean theoretical separation at the very first competing context length.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the scoped Theorem 6 lower bound is internally sound.","rationale":"The reader accepted the paper with high confidence and identified the scope restrictions (nonnegative single-head attention with affine readout) as the weakest assumption. I agree that these restrictions are the only place where the theorem could be escaped, but the paper states them explicitly in Section 3.3 ('Why the scope is necessary') and in the Limitations, and the abstract and Theorem 6 are carefully worded to match that scope. Therefore the scope is not a hidden flaw or an overclaim; it is the intended domain of the theorem. I looked for an internal gap in the proof chain: Lemma 3's three-input cancellation is algebraically correct; Theorem 5's amplification through intermediate Boolean overlaps is valid because every gap is at least g=5 and the code has directed distance Δ; the greedy packing bound for M≥168 checks; and the rank bound via Lemma 4 follows from the nuclear-norm argument. The dense-softmax upper bound also checks with temperature log 6. The only minor issue I noticed is the likely typo in Eq. (8) ('2p values per coordinate' instead of '2^p values'), which does not affect Theorem 6. Since no load-bearing concern materialized, I recommend no change to the reader's ACCEPT verdict.","tokens_in":10363,"tokens_out":28177,"duration_ms":238621,"concrete_test":"Independently re-derive Lemma 3 from the raw definitions: for n=3 write the six strict inequalities for the three inputs, form the identity N_M - (1/2)N_Y - (1/2)N_Z = 0, and confirm the coefficient algebra yields b > (d-1)c. Then recompute the numerical threshold in Theorem 6: verify (1-H_2(1/4))M - 2 log2(M+1) ≥ M/10 at M=168 and check Λ^2=2^{4floor(M/40)}≤2^{M/10}≤T; if either check fails, the exponential lower bound needs revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. I traced the proof end to end. Lemma 3 is the linchpin: for n=3, ε=1/2, and gap d≥2, the three exact-length inputs (x,y,y), (x,z,z), (x,y,z) give shifted outputs (p+2q)/D, (p+2s)/D, (p+q+s)/D, and the identity N_M - (1/2)N_Y - (1/2)N_Z = 0 cancels p,q,s identically. Combining the strict inequalities yields 0 < (1 - d/2)a + b - (d-1)c, whose a-coefficient is ≤0 by d≥2; hence b > (d-1)c, exactly (GD). The greedy middle-layer code has directed distance Δ=floor(M/8), and the standard packing bound T≥2^M/(M+1)/[(M+1)2^{M H_2(1/4)}] gives log2 T ≥ (1-H_2(1/4))M - 2 log2(M+1) ≥ M/10 for M≥168. With g=5, Λ=4^{floor(Δ/5)}=4^{floor(M/40)}, so Λ^2=2^{4floor(M/40)}≤2^{M/10}≤T, and Theorem 5 gives r≥Λ^2/2. I found no algebraic slip, missing positivity hypothesis, or unstated assumption. The scope restrictions (single nonnegative normalized head, affine readout) are explicit in Section 3.3 and the Limitations; signed kernels, multiple heads, and nonlinear decoders are admitted escape routes, so they do not threaten the stated theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Min-IP task over Boolean tokens as a testbed for comparing full softmax attention with kernelized linear attention. It shows that rank-one normalized nonnegative kernel attention solves Min-IP exactly for sequences of length at most two, but any single normalized nonnegative kernel-attention head that solves all length-three sequences with error strictly below 1/2 requires 2^{Omega(m)} kernel features, even with arbitrary tokenwise value maps and arbitrary query-dependent affine readout; dense softmax solves the same task with m-dimensional scores and temperature log 6. The proof combines a fixed-length gap domination lemma, amplification over Boolean overlap chains, a constant-weight code packing bound, and an approximate-identity rank lower bound. A separate information-theoretic result lower-bounds the total cross-token communication of deterministic multihead/multilayer sketch models on a multilevel Min-IP family. The paper also reports experiments on finite witness families and OOD feature-capacity scaling.","tokens_in":10611,"tokens_out":22157,"duration_ms":196638,"significance":"The central separation is crisp and, within its explicitly stated scope, rigorously established. I checked the main proof chain: Lemma 3's cancellation identity is algebraically correct, Theorem 5's amplification and rank argument hold, and the greedy code packing in Theorem 6 yields the stated exponent. The paper is careful to delimit the scope (single head, nonnegative kernels, normalized attention, affine readout) and explicitly identifies signed kernels, multihead compositions, and nonlinear decoders as escape routes; this transparency strengthens rather than weakens the contribution. The dense softmax upper bound with constant temperature and the exact 2^m positive-feature construction provide matching upper bounds, giving a sharp 2^{Theta(m)} phase transition at length three. The proofs are self-contained and the lower bound is unconditional, not contingent on computational complexity conjectures.","major_comments":[],"minor_comments":[{"comment":"The sentence preceding Eq. (8) says the sketch coordinates have 'at most 2p values per coordinate', but the logarithmic bound in Eq. (8) follows only if each coordinate has at most 2^p values. Please correct the typo to '2^p values per coordinate' and adjust the surrounding prose accordingly.","section":"Section 4, Eq. (8)"},{"comment":"The text says 'we train six ranks from five initializations' and lists r = 1, 2, 4, 8, 15, 32. The constructed r = 15 solution is mentioned but could be distinguished more clearly from the five trained seeds; the caption's star helps, but a sentence in the text stating that the constructed model is not one of the trained initializations would remove ambiguity.","section":"Section 5.1"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is sound; the only correction I request is the 2^p typo in Section 4, and the remaining issues are presentation-level. The proof chain is self-contained and the scope limitations are stated honestly. This is well within the journal's scope."},"author_rebuttal":null,"desk_editor":null,"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Three tokens force exponential kernel-attention rank.","keywords":["kernel attention","linear attention","feature rank","minimum inner product","Boolean tokens","attention expressivity","nonnegative kernels","lower bounds"],"falsifier":"Run the finite check behind Lemma 3: with $n=3$, $\\varepsilon=1/2$, query $x$, and candidates $y,z$ whose overlaps with $x$ differ by an integer gap $d\\ge2$, search over nonnegative $a,b,c$ and real scalarized values $p,q,s$ for a solution of the three strict correctness inequalities in which $b=\\alpha(x,y)\\le 2c=2\\alpha(x,z)$. If one exists, the domination lemma is false and the amplification/exponential bound collapses; if none exists, the lemma—and with it the code-based rank lower bound—stands.","tokens_in":10101,"feed_emoji":"🧠","tokens_out":12379,"duration_ms":104953,"temperature":0.7,"pith_summary":"Kernelized attention compresses a sequence into a fixed-dimensional sketch; full attention compares every token pair. The paper isolates the minimum-inner-product task on Boolean tokens to test whether that compression can exactly reproduce the comparison. It proves that a single normalized nonnegative kernel-attention head needs exponentially many features—at least $2^{m/10-6}$ for $m\\ge168$—to solve all three-token instances with error below $1/2$, even when token values and affine readouts are unrestricted. Dense softmax solves the same instances with $m$-dimensional scores and a constant temperature, and rank one already solves every sequence of length at most two exactly. If correct, the result locates the separation at the first context length with two competing candidates, before any long-context argument is needed.","feed_headline":"Three tokens force exponential kernel-attention rank","feed_subtitle":"At length three, one nonnegative kernel head needs 2^Ω(m) features; dense softmax needs only m scores.","key_machinery":"The argument rests on three ingredients. First, normalization and an affine readout collapse the head to a kernel-weighted average of scalarized values, so correctness on the three inputs $(x,y,\\ldots)$, $(x,z,\\ldots)$, $(x,y,z,\\ldots)$ forces a domination inequality $\\alpha(x,y)>\\frac{(n-2)(d-2\\varepsilon)}{2\\varepsilon}\\alpha(x,z)$ whenever the overlaps differ by $d$ (Lemma 3). Second, chaining intermediate Boolean tokens whose overlaps with the query rise in bounded gaps multiplies the domination factor exponentially, turning one comparison into a rank witness. Third, a greedily packed constant-weight code with directed distance $\\Delta$ supplies the many ordered pairs needed to build a matrix whose diagonal dominates its off-diagonal entries; an approximate-identity rank lemma (nuclear–Frobenius duality on a near-identity matrix) converts that domination into the rank lower bound. The finite-precision result instead embeds $(s+1)^q$ assignments into length-$2q$ Min-IP instances and counts the bits that any deterministic cross-token transcript must carry.","core_discovery":"On the paper's own terms: normalized kernel attention with nonnegative weights can exactly solve Boolean Min-IP for every sequence of length one or two using a single feature, but at length three the feature dimension must jump to $2^{\\Omega(m)}$. The precise statement is Theorem 6: for every $m\\ge168$, every single-head model whose attention kernel is a nonnegative bilinear score $\\alpha(x,z)=\\langle\\phi_Q(x),\\phi_K(z)\\rangle$, whose denominator is positive on every input, and whose readout is an arbitrary query-dependent affine map on the normalized attention vector, must use $r\\ge 2^{m/10-6}$ features to keep error strictly below $1/2$ on all length-three sequences. The bound survives position-dependent token maps and a causal final query. Dense softmax achieves the same guarantee with $m$-dimensional scores and temperature $\\log 6$ at length three. For an integer-valued context length $n(m)\\to\\infty$, the required rank grows to $2^{m-o(m)}$, matching the exact $2^m$ positive-feature realization. A separate finite-precision theorem shows that deterministic multihead/multilayer sketch models need a transcript of at least $q\\log_2(s+1)$ bits on a multilevel family, where $q$ is the number of independent answers.","pith_inferences":["Editorial inference: replacing the affine readout by a small nonlinear network on the normalized attention vector likely bypasses the exponential rank barrier, since the proof's reduction from arbitrary values to a weighted scalarized average depends on affine readout; a testable prediction is that polynomial-rank nonnegative heads plus a nonlinear readout solve the length-three family.","Editorial inference: the domination–amplification scheme should transfer to other discrete comparison tasks such as maximum-inner-product or Hamming-nearest retrieval; if so, the exponential lower bound is a property of normalized nonnegative comparison, not of the Min-IP target itself.","Editorial inference: the OOD experiments suggest that learned feature ranks in practice trail the proof's very sparse witness family; one could test whether a rank-$r$ model that fits the amplification witness ratios on the construction also solves the broader shuffled OOD pool, which would separate memorization from genuine comparison capacity."],"forward_implications":["At the first context length containing two competing candidates, a single normalized nonnegative kernel-attention head cannot match dense attention: matching its exact minimum retrieval requires an exponential number of features.","The exponential cut-off appears before long context, so the barrier for linear attention is not primarily about compressing many tokens; it is about having two candidates to compare.","As the fixed context length grows, the required feature rank approaches the exact $2^m$ endpoint; for very long contexts, essentially full-rank feature maps are needed within the single-head nonnegative setting.","Within the theorem's scope, signed kernels, multiple heads/layers, or nonlinear decoders are the known escape routes; the finite-precision theorem still forces any deterministic multihead/multilayer sketch model to pay a total cross-token transcript of at least $q\\log_2(s+1)$ bits on the multilevel family.","Dense softmax's constant temperature at length three shows the separation is not a score-counting artefact; dense attention uses the same $m$-dimensional embedding and succeeds."],"supporting_citations":[{"why":"Defines the dense softmax attention baseline whose explicit pairwise scores the lower-bound theorem is compared against.","marker":"Vaswani et al. (2017)"},{"why":"Introduces kernelized linear attention's fixed-dimensional key–value sketch, the architecture whose rank is being lower-bounded.","marker":"Katharopoulos et al. (2020)"},{"why":"Supplies positive random features for softmax kernels, the nonnegative-feature regime in which the main theorem is stated.","marker":"Choromanski et al. (2021)"},{"why":"Establishes minimum-inner-product/Orthogonal Vectors as a testbed for attention architecture separations, motivating the task.","marker":"Zaheer et al. (2020)"},{"why":"Gives conditional runtime lower bounds for Min-IP variants that the paper's unconditional feature-rank theorem contrasts with.","marker":"Alman and Yu (2025)"},{"why":"Identifies signed/zero-sum linear attention as an escape route, explaining why the main theorem restricts to nonnegative kernels.","marker":"Lu et al. (2026)"}],"fun_headline_variants":["Length-three tokens force exponential kernel-attention features","Kernel attention needs 2^Ω(m) features at just three tokens","Three tokens make kernel attention's feature count go exponential","Kernel attention hits exponential barrier at three tokens","Short sequences, huge feature cost: kernel vs softmax"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exponential lower bound rests on the head being a single normalized nonnegative kernel with an affine tokenwise readout; if the kernel is allowed signed weights or the readout is allowed to be nonlinear, the proof's domination step no longer applies and the theorem says nothing.","fun_headline_variants_meta":{"raw":{"variants":["Length-three tokens force exponential kernel-attention features","Kernel attention needs 2^Ω(m) features at just three tokens","Three tokens make kernel attention's feature count go exponential","Kernel attention hits exponential barrier at three tokens","Short sequences, huge feature cost: kernel vs softmax"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001396,"raw_usage":{"total_tokens":5674,"prompt_tokens":998,"completion_tokens":4676,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":614,"completion_tokens_details":{"reasoning_tokens":4596}},"tokens_in":614,"tokens_out":4676,"duration_ms":28534,"temperature":1.0,"reasoning_tokens":4596,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:14:00.260359+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the finite check behind Lemma 3: with $n=3$, $\\varepsilon=1/2$, query $x$, and candidates $y,z$ whose overlaps with $x$ differ by an integer gap $d\\ge2$, search over nonnegative $a,b,c$ and real scalarized values $p,q,s$ for a solution of the three strict correctness inequalities in which $b=\\alpha(x,y)\\le 2c=2\\alpha(x,z)$. If one exists, the domination lemma is false and the amplification/exponential bound collapses; if none exists, the lemma—and with it the code-based rank lower bound—stands.","supporting_citations":[],"review_version":1}