acceptodds
Under review as a conference paper at ICLR 2027

Exact Attention Merging Beyond Softmax Mixtures

Abstract

Efficient attention relies on compact summaries that merge exactly across blocks. Does retaining more states simply amount to combining more softmax compo- nents? We show that coupled moment states provide a different design space. For positive real-rate exponential-polynomial generators, we characterize the mini- mum number of retained value vectors, give an attaining merge rule, and prove a matching lower bound even with nonlinear decoding. A finite Hankel crite- rion separates nonnegative softmax mixtures from positive, monotone maps with coupled states. The simplest instance uses two value vectors and cannot be rep- resented by any nonnegative softmax mixture on the same scores. Controlled learning experiments connect this structural separation to estimation risk: learned two- and three-state maps approach Bayes performance, and the three-state map transfers to unseen scores. In language modeling, the two-state map improves held-out loss over softmax at three context lengths while maintaining comparable full-model latency to FlashAttention-2. Learned-shape diagnostics in the trained decoder, together with fused execution on Qwen and SmolLM2, further connect the construction to Transformer computation. These results establish state cou- pling as a design axis for expressive, exactly mergeable attention.

Primary area:
learning theory
Keywords:
attention mechanisms, exact blockwise computation, associative summaries, state complexity, Hankel matrices, efficient Transformers

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_gJjxOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The draft studies what attention maps can be computed using a fixed number of exactly mergeable value states. Under a fixed-query, value-linear summary model, the authors show that the minimum number of retained value vectors for a positive real-rate exponential-polynomial generator equals its translation dimension. They give a moment-based construction and a matching lower bound, including when the decoder is nonlinear. They also characterize when these maps can be represented by nonnegative softmax mixtures on the same scores through a finite Hankel matrix. Based on these results, the authors introduce two-state and three-state attention maps and evaluate their estimation risk, language-modeling performance, and execution cost.

Critical strengths
  1. The authors give a way to compute attention by merging summaries from different blocks. Within their specific setting, they prove the minimum number of value vectors that need to be stored, and their method uses exactly this number.

  2. The authors show that their two-state Ray attention cannot be represented by a nonnegative softmax mixture on the same scores. Their synthetic experiments also show examples where it gives lower prediction error than these mixtures.

Critical weaknesses
  1. The gain over learned temperature is small. In Tab 1, Ray improves NLL by only about 0.000139, 0.000057, and 0.000686 at lengths 128, 256, and 512. At length 512, the gain over Coxian is only about 0.000066. The reported confidence interval is against ordinary softmax. It is therefore unclear whether Ray is reliably better than these stronger baselines. Please report confidence intervals for these comparisons.

  2. In Section 4, the authors claim the long-context FP32 implementation first finds the global maximum for each row, then makes a second pass to compute the output. Once the maximum is known, any positive h can be evaluated with one weighted value sum and a normalizer. This does not directly test the online merge in Algorithm 1. Please report the time, memory use, and numerical error of that merge, and clarify which GPU results use it.

Correct me if I'm wrong

Questions for authors

See Weaknesses

1 comment

Response to Reviewer gJjx

Thank you for a careful and constructive review, and for pointing out the distinction between two-pass evaluation and the single-pass online merge of Algorithm 1.

[W1] Gains over learned temperature and over Coxian (at 512) are small, and confidence intervals were only reported against softmax. Please report confidence intervals for these stronger baselines.

Response: Under the calibrated protocol, Ray⋆ has the lowest mean NLL at every length; its paired 95% article intervals exclude zero against Coxian⋆ and softmax at every length, and it leads Mix-2⋆ at every length (−2.18 [−3.88, −0.47] at 512; Table 2; Supp. B.2, Table S3, Figure S4).

Calibrated contrast (10−310^{-3} nats)128256512512: article 95% CI
Ray⋆ − Coxian⋆−1.78−1.90−1.86[−3.43, −0.12]
Ray⋆ − Mix-2⋆−1.63−1.89−2.18[−3.88, −0.47]
Ray⋆ − Softmax−5.14−5.03−5.44[−7.10, −3.69]
  • Coupled controls: Under the default protocol both coupled maps (Ray and Coxian) beat every non-coupled map at every length (Table 1); under calibration, two-state Ray⋆ beats Coxian⋆ at all lengths ([−3.27, −0.09] at 128, [−3.45, −0.16] at 256; 7/8 seeds at 512) with one fewer rate parameter.
  • Learned temperature: Ray − Temperature is negative in mean and median across all 6 protocol × length cells (winning 6/8 seeds at 256 and 512; calibrated means −0.77, −0.96, −1.23 and medians −1.15, −1.43, −1.35; default 512 mean −1.32, median −1.91; per-seed values: Table S4). All 24 logged coupled runs (Ray, Coxian) end at γ<0\gamma < 0, excluded from temperatures (γ≡0\gamma \equiv 0) and positive mixtures (γ≥0\gamma \ge 0, Mix-2 collapsing to γ=0\gamma = 0; Figure 4b–c), and projecting every Ray head of the seed-42 model onto its best positive temperature changes layer outputs by 1.6–4.6%, 64–160× the FP16 reconstruction error (Section 5.4).

[W2] Finding each row's maximum in pass 1 and accumulating values in pass 2 works for any positive hh and does not test the online merge of Algorithm 1. Clarify which GPU results use Algorithm 1, and report its time, memory, and numerical error.

Response: Sections 4 and 5.5–5.6 label every GPU route, and our single-pass GPU implementation of Algorithm 1 (Supp. D) matches softmax's online-merge precision (2.0–5.9×10−72.0\text{–}5.9 \times 10^{-7} vs. FP64) and decodes within 0.5–6.6% of FlashAttention-2. (Supp. C.4–C.6, Tables S9–S14, Figure S12.)

  • Which results use Algorithm 1: The Section 5.6 training kernel (Tables S9–S11), split-KV decoding (Tables S12–S13), and the matched Qwen2.5-0.5B benchmark (Table S14) merge key tiles online through Algorithm 1's Pascal action, (S0,Z,U0,W)←(eS0,e(Z−λδS0),eU0,e(W−λδU0))(S_0, Z, U_0, W) \leftarrow (eS_0, e(Z - \lambda\delta S_0), eU_0, e(W - \lambda\delta U_0)), e=eaδe = e^{a\delta} (δ<0\delta < 0; Supp. C.4). Only the FP32 Qwen/SmolLM2 scaling and fidelity study (Section 5.5; Tables S7–S8) uses the two-pass kernel, and the one-pass kernel reproduces its FP32 loss bit for bit at 2k (Supp. C.6). The 5.51M forward (n≤512n \le 512) holds each row in one tile.
  • Split-KV decoding (16k–128k keys; Supp. C.5, Tables S12–S13, Figure S12a): Merges 2D+32D+3-float chunk states across blocks in sequential, reversed, random, or tree order, matching softmax's online merge in the same code, below dense FP32 error, and within 0.5–6.6% of FA2 flash-decoding (1.4–1.9× faster than two-pass, 80–93% DRAM BW, ≤8.2\le 8.2 MiB state vs. 2–4 GiB KV cache):
Rel. L2L_2 error vs. FP64 (16k16\text{k})Ray online (1–256 splits, 4 orders)Softmax onlineRay dense FP32
Random scores2.0–4.3×10−72.0\text{–}4.3 \times 10^{-7}1.9–4.0×10−71.9\text{–}4.0 \times 10^{-7}1.2×10−61.2 \times 10^{-6}
Sharp / peaked scores3.8–5.9×10−73.8\text{–}5.9 \times 10^{-7}4.0–5.6×10−74.0\text{–}5.6 \times 10^{-7}7.8×10−77.8 \times 10^{-7}
Max moves at every one of 256 tiles2.7×10−62.7 \times 10^{-6}2.4×10−62.4 \times 10^{-6}4.4×10−64.4 \times 10^{-6}
  • Fused BF16 training kernel (Supp. C.4, C.6): Merges key tiles online in registers, tracks 60 dense Ray training steps to mean ∣Δloss∣=1.3×10−4|\Delta \text{loss}| = 1.3 \times 10^{-4}, runs kernel forward at 1.55–1.60× same-code softmax at 8k (at its 1.5× FLOP ratio), and runs Qwen2.5-0.5B forward at 1.03–1.19× fastest softmax (memory within 0.7% of fastest core) and training f+b at 1.13–1.17× FA2 at 4k–8k (Table S14).

Thank you again for feedback that led directly to our paired baseline intervals and single-pass GPU online merge benchmarks.

Reviewer_CreMOpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper asks which attention weighting rules allow exact blockwise merging, as FlashAttention's online softmax does, under a fixed state budget.

  • State cost (Theorem 1). For positive exponential-polynomial generators h(t) = Σₖ e^(aₖt) qₖ(t) applied to max-centred scores, the minimum number of retained value vectors (the "merge-rank") is exactly R = Σₖ (deg qₖ + 1).
    • Sufficiency: max-aligned moments that update through a lower-triangular Pascal action.
    • Necessity: a continuation argument (appending zero-valued tokens at higher scores) that holds even with nonlinear decoders.
  • Mixture membership (Theorem 2). A finite Hankel-inertia criterion characterizes when such a map is a nonnegative softmax mixture: only when every rate block is constant with a positive coefficient. Any polynomial factor adds a negative direction while the weights stay positive and monotone.
  • The "Ray" instance. h = e^(at)(1 − λt) uses two value states and is log-concave, so it lies outside every positive mixture.
  • Experiments.
    • Gaussian aggregation tasks: learned coupled maps beat a certified positive-mixture risk bound and transfer to unseen score grids.
    • A 5.5M-parameter decoder trained on 134M tokens: Ray lowers held-out NLL relative to softmax by between 2.5×10⁻³ and 3.1×10⁻³ nats at context lengths 128, 256 and 512.
    • Fused kernels: full-model latency matches FlashAttention-2 for this small model, and Ray is inserted into Qwen2.5-0.5B and SmolLM2-135M to study memory and latency scaling.
Critical strengths
  1. A well-posed question with a clean answer. Tying the choice of attention map to its state cost under exact merging is a useful framing.
    • Theorem 1 gives matching upper and lower bounds in the value-linear model.
    • The lower bound holds even for nonlinear decoders, and the continuation argument is short and elegant.
  2. A sharp mixture characterization. Theorem 2 gives the full inertia, not just a determinant sign. It therefore catches cases the three-point test misses, such as the five-token certificate in App. E.1. The blind-spot examples in Apps. E–K (spacing, witness size, complex-rate aliasing) are instructive.
  3. The mathematics checks out. I re-derived the following, and all agree with the paper. The authors also report exact-arithmetic identity checks, and floating-point merges that agree with dense evaluation to about 3×10⁻¹⁵.
    • the Ray obstruction (Eq. 14);
    • Ray's monotonicity condition a ≥ λ and its log-curvature;
    • the quadratic family's three-point quantity;
    • the five-token certificate (Eq. 29, yᵀH₃y = −1);
    • Eqs. 27–28 for the signed three-rate family;
    • the coefficient-block determinant (Eq. 23) for small degrees.
  4. Serious implementation and transparent reporting. The paper includes fused kernels, numerical-fidelity checks across execution routes (Table 5), per-seed results (Table 2), and stated limitations.
Critical weaknesses

W1. The language-modeling evidence does not isolate the central claim: that state coupling helps, rather than simply adding one learnable parameter.

In Table 1, a learned temperature alone recovers 78–98% of Ray's gain over softmax (ΔNLL vs. softmax, in units of 10⁻³ nats):

Context lengthLearned temperatureRay
128−2.341−2.480
256−2.398−2.455
512−2.409−3.095
  • In Table 2, Ray is worse than temperature for seed 137 at all three lengths, at the reported precision.
  • The only bootstrap interval reported is Ray vs. softmax at length 512. Ray vs. temperature, the comparison that matters here, has no uncertainty estimate.
  • In the Qwen continued-training study (App. C.2), all four maps reach the same mean perplexity (13.17); Ray − softmax is −7×10⁻⁵ nats.

The claim that Ray "improves held-out loss over softmax" is literally true. On the current evidence, though, most of that improvement is explained by a learned temperature.

W2. The mixture control looks under-optimized, which confounds the "coupled vs. independent" comparison.

  • Mix-2 is worse than plain softmax at every length (+1.9 to +3.3×10⁻³), even though a positive two-exponential mixture contains softmax and learned temperature as special cases.
  • Likewise, Coxian contains Ray at equal rates (App. B) but is worse than Ray at every length.

Both patterns point to optimization or initialization effects rather than function-class effects. The Ray vs. Mix-2 gap therefore cannot yet be read as evidence for coupling.

W3. The efficiency evidence does not test the regime that matters for adoption.

  • Overhead-dominated regime. The FlashAttention-2 comparison is a batch-1 forward pass of a 5.5M-parameter model that takes about 0.38 ms. At that size, launch overhead and the LM head dominate the cost, which is why fused softmax and fused Ray come out at a ratio of about 1.001.
  • Untested cost of the extra state. Coupled moments double the on-chip value accumulators, which could reduce tile sizes or occupancy at head dim 128 on modern GPUs. This is not measured.
  • No backward pass. No backward kernel is described, so the training cost relative to FlashAttention is unknown.
  • Missing long-context comparison. The Qwen/SmolLM2 study compares dense, blocked and fused Ray routes in FP32. It never compares against softmax with FlashAttention at 2k–8k tokens.
Questions for authors
  1. Please report the 95% article-bootstrap interval for Ray − learned temperature at each length, together with the seed-level differences. Is the difference distinguishable from zero?
  2. Can you rerun Mix-2 and Coxian initialized at the softmax/temperature solution, with a tuned generator learning rate, so that each is at least as good as softmax? Does Ray still beat them?
  3. Please report kernel-level forward and backward throughput for Ray vs. FlashAttention-2 at head dim 128, sequence lengths 2k–16k and a training batch size. Does the second accumulator affect tile size or occupancy?
  4. Is every positive, own-score-monotone generator with finite merge-rank necessarily an exponential polynomial (with real or complex rates)? If yes, can this be stated as a theorem?
2 comments

Response to Reviewer CreM · Part 1/2

Thank you for a rigorous and constructive review, and in particular for independently re-deriving and verifying our Hankel certificates, monotonicity conditions, and block determinants.

[W1 & Q1] A learned temperature recovers much of Ray's gain over softmax. Please report 95% article-bootstrap intervals and seed-level differences for Ray vs. temperature at each context length, and clarify whether the difference is real rather than tuning.

Response: Across 8 paired seeds, Ray − Temperature is negative in both mean and median across all 6 protocol × length cells (winning 6/8 seeds at lengths 256 and 512); the paired loss intervals include 0, and the separation is in shape: all 24 logged coupled runs end at negative log-curvature γ<0\gamma < 0, outside every temperature and mixture. (Table 2; Supp. B.2, Tables S3–S4, Figure S4.)

Ray − Temperature (10−310^{-3} nats)128256512
Default: mean / median−1.13 / −0.47−1.16 / −1.05−1.32 / −1.91
Calibrated (⋆): mean / median−0.77 / −1.15−0.96 / −1.43−1.23 / −1.35
  • Intervals and calibration: Full paired intervals and all 8 per-seed differences are in Tables S3–S4; under calibration, seed 137 leads temperature at every length (−1.66, −2.56, −2.96; Table S4). Calibrating the generator LR improves temperature (−2.48 at 512) and Ray (−2.38 at 512) by nearly the same margin, preserving Ray's lead and giving Ray⋆ the lowest mean NLL at all lengths (24/24 wins over softmax; 512 seed+article 95% CI [−8.20, −2.73]).
  • Shape separation: All 24 logged coupled runs end at γ<0\gamma < 0 (Figure 4c; Ray deepens from −0.25-0.25 to [−0.44, −0.32]), a region excluded from every temperature (γ≡0\gamma \equiv 0) and positive mixture (γ≥0\gamma \ge 0; Section 4, Theorem 2). Projecting every Ray head of the seed-42 model onto its best positive temperature changes layer outputs by 1.6–4.6%, 64–160× the FP16 reconstruction error (Section 5.4).
  • Qwen2.5-0.5B continued training (Supp. C.2, Figures S7–S8): Tests drop-in replacement on a softmax-pretrained checkpoint (2.1M tokens) rather than full pretraining; Ray matches softmax perplexity (13.17) without loss, and all 336 trained heads have λ>0\lambda > 0, hence γ<0\gamma < 0 (Figure S7).

[W2 & Q2] Mix-2 and Coxian appear under-optimized. If both are initialized at the softmax solution with a tuned generator learning rate so each beats softmax, does Ray still outperform them?

Response: Initialized at softmax with calibrated generator LR 0.03, Mix-2⋆ and Coxian⋆ beat softmax in 8/8 seeds at every length, and Ray⋆ outperforms both across all three context lengths. (Section 5.1; Supp. B.3, Table 2, Tables S3 & S5.)

Contrast (10−310^{-3} nats)128256512512: article 95% CI512: seeds < 0
Ray⋆ − Mix-2⋆−1.63−1.89−2.18[−3.88, −0.47]7 / 8
Ray⋆ − Coxian⋆−1.78−1.90−1.86[−3.43, −0.12]7 / 8
  • Calibrated controls: Mix-2⋆ starts at (0.9,1.1)(0.9, 1.1) (γ=+0.01\gamma = +0.01) and Coxian⋆ at (1.05,0.05,a)(1.05, 0.05, a) (γ=−0.0025\gamma = -0.0025); all maps select LR 0.03 on 65,536 disjoint calibration targets (Mix-2⋆: −3.26, Coxian⋆: −3.59 vs. softmax at 512, 8/8 seeds). Ray⋆ has lower mean NLL than Mix-2⋆ at every length (−2.18 [−3.88, −0.47] at 512, 7/8 seeds), and its 95% article CIs exclude 0 at all three lengths against Coxian⋆ (Table S3). Started at softmax too, Ray reaches the lowest calibration NLL of any seed-42 run (3.54916 vs. 3.55370 Mix-2⋆, 3.55393 Coxian⋆; Table S5).
  • Mix-2 diagnosis and LR sweep (Supp. B.3, Figure 4b–c): Default Mix-2 started heavy-tailed (γ=+0.25\gamma = +0.25), adding +5+5 to +12+12 early training loss before merging its rates in 50–69% of heads (vanishing splitting gradient; normal grad norms 1.95–2.14). At every swept LR from 0.003 to 0.1, softmax-started Mix-2 merges its rates in 14–16 of 16 heads (γ→0\gamma \to 0; median smaller gate 0.20–0.27 at 0.03), whereas softmax-started Coxian enters γ<0\gamma < 0 at every swept LR and Ray stays at γ<0\gamma < 0 at both of its rates (Supp. B.3). Two-state Ray⋆ captures the coupled gain without Coxian's extra rate.

(Continued in Part 2/2)

Response to Reviewer CreM · Part 2/2

[W3 & Q3] Report kernel-level forward and backward throughput for Ray vs. FlashAttention-2 at head dim 128, sequence lengths 2k–16k, and training batch sizes, plus long-context comparisons against optimized softmax. Does the second value accumulator reduce tile size or occupancy?

Response: Single-pass BF16 training and split-KV decoding kernels keep the 128×64128 \times 64 forward tile and 8 warps/SM at D=128D = 128, run forward at Ray's 1.5× FLOP ratio at 8k, run Qwen2.5-0.5B training at 1.13–1.17× FA2 (4k–8k), and decode within 0.5–6.6% of FlashAttention-2. (Section 5.6; Supp. C.4–C.6, Tables S9–S14, Figure S12.)

  • Kernel design and accuracy: Each key tile updates (m,S0,Z,U0,W)(m, S_0, Z, U_0, W) in one pass via Algorithm 1's Pascal action (Supp. D). The fused backward differentiates through the row maximum. Against FP64, BF16 output error is 1.7–1.8×10−31.7\text{–}1.8 \times 10^{-3} (softmax kernels including SDPA-flash: 1.7–2.0×10−31.7\text{–}2.0 \times 10^{-3}), and 60 fused training steps track dense Ray to mean ∣Δloss∣=1.3×10−4|\Delta \text{loss}| = 1.3 \times 10^{-4}, the same order as FA2 vs. dense softmax (0.8×10−40.8 \times 10^{-4}; Supp. C.4).
  • Throughput vs. FA2 and Triton softmax (Table S9, Figure S12b): In causal BF16 (B⋅N=16kB \cdot N = 16\text{k}, H=2048/DH = 2048/D), Ray / FA2 is 1.57–2.19× fwd and 2.23–2.60× f+b at 2k–4k2\text{k–}4\text{k}, and 1.44–1.70× fwd and 1.64–1.89× f+b at 8k–16k8\text{k–}16\text{k}, where our Triton softmax is itself 1.34–1.45× FA2 in f+b (Table S9 ratio of ratios):
Benchmark settingRay vs. softmaxHardware / memory note
Kernel forward, BF16, N=8kN=8\text{k}, D∈{64,128}D \in \lbrace 64, 128 \rbrace1.55–1.60× same-code (1.55–1.60× FA2)At the 1.5× matmul FLOP ratio
Forward & dQ at D=128D = 128Same 128×64128 \times 64 tileSame 8 warps/SM (255 vs. 213/236 regs; Table S10)
Kernel backward, BF16, N=16kN=16\text{k}, D∈{64,128}D \in \lbrace 64, 128 \rbrace1.01–1.12× same-code (1.87–1.89× FA2)dK, dV uses 32×6432 \times 64 (D=128D=128) / 64×6464 \times 64 (D=64D=64)
Full 5.51M training step, BF16 (16×51216 \times 512)1.08× same-code (1.24× FA2)1.74 GB vs. 2.97 GB dense (Table S11)
Qwen2.5-0.5B forward, BF16/FP16, 2k–8k2\text{k–}8\text{k}1.03–1.19× fastest of FA2/SDPA/TritonMemory within 0.7% of fastest core; FP32: 1.06–1.26×
Qwen2.5-0.5B train f+b, BF16, 4k–8k4\text{k–}8\text{k}1.13–1.17× FA2Matches same-code mem (+2.1–3.2% vs. FA2 GQA)
Split-KV decoding, 16k–128k16\text{k–}128\text{k} cached keysWithin 0.5–6.6% of FA2 flash-decodingMemory-BW bound (80–93% DRAM BW; Table S13)
  • Backward tiles and occupancy (Table S10): At D=128D = 128, forward and dQ keep the same 128×64128 \times 64 tile and 8 warps/SM. In dK, dV, autotuning selects a wider key tile (32×6432 \times 64 vs. 32×3232 \times 32 at D=128D = 128, 4 vs. 8 warps/SM) because keeping coupled moments in registers cuts HBM traffic and is faster end-to-end.

[Q4] Is every positive, own-score-monotone generator with finite merge-rank necessarily an exponential polynomial (with real or complex rates)? Can this be stated as a theorem?

Response: Theorem 3 (Section 3.3; full proof in Supp. I) proves this converse, completing the exact classification of finite-state mergeable attention maps.

  • Theorem 3: Let h>0h > 0 be own-score monotone (or measurable and locally bounded on t<0t < 0) with finite merge-rank rr, and let Vh=span{h(⋅−b):b≥0}V_h = \mathrm{span}\lbrace h(\cdot - b) : b \ge 0 \rbrace on t<0t < 0. Then: (1) dim⁡Vh≤r\dim V_h \le r; (2) on t<0t < 0, h(t)=∑keρktqk(t)h(t) = \sum_k e^{\rho_k t} q_k(t) with real or conjugate-paired complex rates ρk\rho_k and ∑k(deg⁡qk+1)=dim⁡Vh\sum_k (\deg q_k + 1) = \dim V_h; and (3) if hh is continuous at 00, its merge-rank equals dim⁡Vh\dim V_h (RR in Theorem 1 for real rates).
  • Proof (Supp. I): (i) Lemma 2 bounds the rank of every shifted evaluation matrix h(ti−bj)h(t_i - b_j), forcing dim⁡Vh≤r\dim V_h \le r; (ii) convolving against Cc∞C_c^\infty test functions makes shift coordinates smooth, forcing h∈C∞(−∞,0)h \in C^\infty(-\infty, 0); (iii) ddt\frac{d}{dt} preserves VhV_h, so hh solves a constant-coefficient linear ODE; Anselone–Korevaar (1964) treat continuous functions, including the half-line, and Engert (1970) measurable functions on the full line; we need the measurable one-sided case exposed by continuations.
  • Sharpness: Discontinuous Hamel-basis exp⁡∘Λ\exp \circ \Lambda has merge-rank 1 (ruled out by monotonicity/measurability), and a jump at t=0t = 0 adds at most one state vector.

Thank you again for a review whose questions sharpened our baseline calibration, GPU kernel benchmarks, and completeness theorem.

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

The paper studies how to compute attention in separate blocks while retaining only a small summary of each block. Its central idea is that additional stored vectors can hold related information that updates together, rather than than simply representing separate softmax components. This allows more flexible attention weights while preserving exact blockwise computation. The paper explains how much information its construction needs, describes how to combine the summaries, and studies the resulting attention functions through controlled learning tasks, language modeling, and GPU measurements. I find the connection between the attention function and its storage requirements interesting. My main concerns are about how strongly the experiments establish a practical advantage over the simpler alternatives.

Critical strengths

The paper offers a useful way to think about attention under a fixed storage budget. It makes a clear distinction between storing more independent components and storing related quantities that update together. This gives a concrete explanation of how additional storage can support different attention shapes. The storage argument is convincing within the stated assumptions, including the restriction that the stored summaries are linear in the values.

The controlled experiments connect the mathematical idea to a prediction problem. Section 5.2 shows that the proposed functions can learn weighting rules that approach the best achievable error in the specified tasks, while positive mixtures remain above that level. The transfer experiments also examine whether a learned weighting rule continues to work at score values not used during training. These are useful demonstrations of what the construction can do.

The paper examines what happens inside the trained model. Section 5.4 goes beyond reporting a loss difference. It checks whether the learned attention shapes differ from a temperature change and whether those differences survive the combination of value vectors. This supports the claim that the additional flexibility changes the model’s representations, rather than disappearing during aggregation.

The implementation work makes the proposal more concrete. The paper reports close agreement between dense and fused execution. The shared fused-softmax control is also useful: it helps assess the additional cost of the attention map within a common implementation. The nearly identical full-model latency and peak allocation in that setting are encouraging results.

Critical weaknesses
  1. Table 1 shows that learned temperature achieves results close to Ray. Using the rounded table entries, Ray’s additional improvement is approximately 0.00014 at context lengths 128 and similar for other context lenghts. These differences are much smaller than the reported improvements over ordinary softmax. This matters because learned temperature is a simple alternative that already changes how strongly attention favors high-scoring tokens. The comparison with this baseline is therefore important for understanding the benefit of the additional shape flexibility. Given these small margins, I would like to know whether the improvement is consistent across training seeds and what the uncertainty is in the paired Ray-versus-temperature comparison. The interval reported in Section 5.3 compares Ray with ordinary softmax, so it does not answer that question. I am not concluding that the smaller improvement is insignificant; the current evidence leaves its reliability unclear.

  2. Mix-2 performs worse than learned temperature, and even worse than ordinary softmax on average in Table 1. A more flexible model can be harder to optimize, so this outcome is not itself a contradiction. However, it makes the comparison harder to interpret. Before treating the Ray–Mix-2 gap as evidence that one way of organizing the stored information is better, I would like some explanation of why Mix-2 performs poorly and what checks were made on its training. Coxian provides another important comparison because its results are close to Ray’s, particularly at context length 512. Including this baseline is a strength, but the main discussion could explain more clearly what is learned from it. At present, the results support the usefulness of considering alternative attention functions more clearly than they establish an advantage specific to Ray’s form of coupling.

  3. The synthetic experiments are well suited to illustrating the intended behavior. At the same time, the noise patterns are deliberately specified, and the quadratic task directly uses an inverse-noise weighting rule from the proposed family. Success in that setting shows that the method can learn the right rule when that rule is well matched to its design. The unseen-score experiments are valuable within this controlled setting. However, they do not by themselves establish that the same flexibility will reliably improve prediction on less structured data. I would like the conclusions to distinguish more clearly between demonstrating an expressive capability, learning it in a controlled task, and obtaining a useful improvement in language modeling.

  4. The direct FlashAttention-2 comparison uses a 5.510M-parameter model, batch size one, and context lengths up to 512. The results show that Ray can have similar full-model forward latency in this setting. The shared fused-softmax comparison strengthens that observation. The larger-backbone experiments answer a different question. The reported Qwen speedup of 2.61 times is relative to dense Ray, as Section 5.5 clearly states. This demonstrates the benefit of fusing the proposed computation. It does not establish how its cost compares with optimized softmax attention on the same backbone. A matched FlashAttention-2 or SDPA comparison on one of these backbones would make the practical tradeoff easier to assess. The longer-context measurements also use FP32 forward execution, so they leave lower-precision performance and training costs unresolved in those settings.

Questions for authors

Given the small gains over learned temperature, can the authors report paired uncertainty estimates and explain whether those gains are consistent across training seeds?

What checks were made to understand Mix-2’s weaker performance? How should the close Coxian results affect the interpretation of the benefit specific to coupling?

Can the larger-backbone execution study include a matched FlashAttention-2 or SDPA comparison, with the same precision, batch size, sequence length, and memory measurement?

2 comments

Response to Reviewer NKHa · Part 1/2

Thank you for a thoughtful and constructive review, especially for highlighting our storage-budget framing, the unseen-score transfer experiments, and the internal representation analyses.

[W1 & Q1] Because Ray's margin over learned temperature is smaller than its margin over softmax, please report paired uncertainty estimates and clarify whether the gain is consistent across seeds.

Response: Across 8 paired seeds, Ray − Temperature is negative in both mean and median across all 6 protocol × length cells (winning 6/8 seeds at lengths 256 and 512), and Ray⋆ beats softmax in all 24/24 calibrated seed-length pairs. (Table 2; Supp. B.2, Tables S3–S4, Figure S4.)

Ray − Temperature (10−310^{-3} nats)128256512
Default: mean / median−1.13 / −0.47−1.16 / −1.05−1.32 / −1.91
Calibrated (⋆): mean / median−0.77 / −1.15−0.96 / −1.43−1.23 / −1.35
  • Paired intervals and seeds: Full article and seed+article bootstrap intervals and all 8 per-seed differences are in Tables S3–S4 and Figure S4. Calibration improves temperature (−2.48 at 512) and Ray (−2.38 at 512) by nearly the same amount, leaving Ray⋆ with the lowest mean NLL of all maps at every length (−5.44 vs. softmax at 512; seed+article 95% CI [−8.20, −2.73]).
  • Shape separation: All 24 logged coupled runs end at γ<0\gamma < 0 (Figure 4c; Ray deepens from −0.25-0.25 to [−0.44, −0.32]), a region excluded from every temperature (γ≡0\gamma \equiv 0) and positive mixture (γ≥0\gamma \ge 0; Section 4, Theorem 2). Projecting every Ray head of the seed-42 model onto its best positive temperature changes layer outputs by 1.6–4.6%, 64–160× the FP16 reconstruction error (Section 5.4).

[W2 & Q2] What checks explain Mix-2's weak performance, and how do the close Coxian results affect the interpretation of coupling?

Response: Initialized at softmax (Mix-2⋆), Mix-2 beats softmax in 8/8 seeds yet merges its rates (γ→0\gamma \to 0) at every swept learning rate from 0.003 to 0.1, whereas Coxian is a coupled map containing Ray and calibrated Ray⋆ beats both Mix-2⋆ and Coxian⋆ at every length. (Section 5.1; Supp. B.3, Figure 4b–c.)

Contrast (10−310^{-3} nats)128256512512: article 95% CI512: seeds < 0
Ray⋆ − Mix-2⋆−1.63−1.89−2.18[−3.88, −0.47]7 / 8
Ray⋆ − Coxian⋆−1.78−1.90−1.86[−3.43, −0.12]7 / 8
  • Checks on Mix-2 (Supp. B.3): Starting at γ=+0.25\gamma = +0.25 added +5+5 to +12+12 training NLL over the first 4k steps (with normal gradient norms 1.95–2.14 and no spikes), after which its two rates merged in 50–69% of heads where the rate-splitting gradient vanishes (5/8 seeds still beat softmax). Starting at softmax removes that penalty (Mix-2⋆ beats softmax by −3.26 at 512, 8/8 seeds), and Ray⋆ has lower mean NLL than Mix-2⋆ at every length (−2.18 [−3.88, −0.47] at 512, 7/8 seeds).
  • Coxian and the LR sweep: Coxian puts a negative weight on its faster exponential (for λ>max⁡(a−b,0)\lambda > \max(a-b, 0); Supp. B.1) and equals Ray at equal rates, so it is a coupled map. Under the default protocol both coupled maps beat every non-coupled map at every length (Table 1). At every swept LR from 0.003 to 0.1, softmax-started Mix-2 merges its rates in 14–16 of 16 heads (γ→0\gamma \to 0), while all 24 logged coupled runs end at γ<0\gamma < 0 (Figure 4c). Ray⋆ beats Coxian⋆ at every length with article intervals excluding 0 (Table S3) and has one fewer rate parameter.

(Continued in Part 2/2)

Response to Reviewer NKHa · Part 2/2

[W3] Distinguish clearly between expressive capability, controlled-task learning, and language-modeling improvements.

Response: Section 7 separates four levels of evidence, and Section 5.2 ends by separating learnability of a coupled target from whether text training selects a coupled shape, which Sections 5.3–5.4 test.

  1. Expressivity and state cost (Theorems 1–3): Coupled moments attain the minimum value-state count RR, the Hankel inertia criterion certifies non-mixture structure, and Theorem 3 (Section 3.3, Supp. I) proves that exponential polynomials are the only positive monotone generators with finite merge-rank.
  2. Controlled learnability and unseen-score transfer (Section 5.2, Figure 3, Figure S1): The controlled task's noise is built from the quadratic family by design, so it tests whether a matched coupled rule is learnable from finite data: the coupled map recovers the inverse-noise weight function between training scores and keeps MSE 0.5002 on the 9- and 17-score grids, whereas Mix-3 and learned-score softmax leave systematic allocation errors (Figure S1).
  3. Language modeling on natural text (Sections 5.3–5.4, Figure 4): Sections 5.3–5.4 test whether natural text selects that shape: in 8-seed pretraining (5.51M parameters, 134M tokens), all 24 logged coupled runs end at γ<0\gamma < 0 while every mixture collapses to γ=0\gamma = 0, and calibrated Ray⋆ attains the lowest mean NLL across all context lengths.
  4. Execution (Sections 5.5–5.6): The exact online merge in one-pass training and split-KV decoding kernels, decoding within 0.5–6.6% of FA2.

[W4 & Q3] Add a matched FlashAttention-2 / SDPA comparison on a larger backbone (same precision, batch size, length, memory), including BF16/FP16 and training cost.

Response: On Qwen2.5-0.5B with only the attention core swapped, fused Ray costs 1.03–1.19× the fastest of FA2, SDPA and Triton softmax in BF16/FP16 forward (peak memory within 0.7%) and 1.13–1.17× FA2 in BF16 training at 4k–8k; the 2.61× figure compares fused with dense Ray (Section 5.5). (Section 5.6; Supp. C.4–C.6, Tables S9–S14, Figure S12.)

Matched GPU benchmark (Table S14 / S13)Ray vs. fastest softmax (FA2 / SDPA / Triton)Peak memory
Qwen2.5-0.5B forward, BF16 & FP16 (2k–8k2\text{k–}8\text{k}, B∈{1,4}B \in \lbrace 1, 4 \rbrace)1.03–1.19× fastest of FA2 / SDPA / TritonWithin 0.7% of fastest softmax core
Qwen2.5-0.5B forward, FP32 (2k–8k2\text{k–}8\text{k}, B∈{1,4}B \in \lbrace 1, 4 \rbrace)1.06–1.26× fastest of SDPA / Triton (FA2 n/a)Within 0.2% of fastest softmax core
Qwen2.5-0.5B training f+b, BF16 (4k–8k4\text{k–}8\text{k})1.13–1.17× fastest softmax (FA2)Matches same-code softmax (+2.1–3.2% vs. FA2 GQA)
Split-KV decoding (16k–128k16\text{k–}128\text{k} cached keys)Within 0.5–6.6% of FA2 flash-decoding≤8.2\le 8.2 MiB merge state vs. 2–4 GiB KV cache
  • Training accuracy and standalone kernels (Supp. C.4, C.6): Against FP64, BF16 output error is 1.7–1.8×10−31.7\text{–}1.8 \times 10^{-3} (matching SDPA-flash's 1.7–2.0×10−31.7\text{–}2.0 \times 10^{-3}), and 60 fused training steps track dense Ray to mean ∣Δloss∣=1.3×10−4|\Delta \text{loss}| = 1.3 \times 10^{-4} (FA2 vs. dense softmax: 0.8×10−40.8 \times 10^{-4}). Standalone kernel forward runs at 1.55–1.60× same-code softmax at 8k (at its 1.5× FLOP ratio), backward reaches 1.01–1.12× at 16k (Table S9), and full 5.51M training steps cost 1.08× same-code softmax at the same 1.74 GB (Table S11). On Qwen2.5-0.5B training, the 2.1–3.2% memory difference vs. FA2 comes from expanding 2 KV heads to 14 in the Triton backward.

Thank you again for feedback that strengthened our paired statistical analysis, scope distinctions, and matched backbone benchmarks.

Comments on the paper

1 comment

General Response to All Reviewers

We thank all three reviewers for their detailed, constructive reviews and have uploaded the revised main paper (main.pdf) and supplementary material (supp.pdf). NLL differences are in 10−310^{-3} nats (A−B<0A - B < 0 favors AA); the default (submitted) protocol uses generator LR 0.003, and ⋆ marks the calibrated protocol (Mix-2⋆ and Coxian⋆ started at softmax, Ray⋆ at (1.5,0.5)(1.5, 0.5), every generator LR selected on disjoint calibration targets at 0.03). Default-protocol means now average all 8 seeds (the submission averaged seeds 42, 137 and 2026); both protocols are reported in Table 1 and Tables S3–S4.

1. Calibrated 8-seed language modeling, learned coupling, and generator completeness

Across 8 paired seeds under the calibrated protocol, Ray achieves the lowest mean held-out NLL of all attention maps at every context length, and the new Theorem 3 completes the classification by proving that every positive monotone finite-merge-rank generator is an exponential polynomial. (Section 3.3, Supp. I; Tables 1–2, Figure 4, Supp. B.2–B.3, Tables S3–S5.)

Calibrated NLL vs. softmax (10−310^{-3} nats)128256512
Temperature⋆−4.37−4.07−4.22
Mix-2⋆−3.51−3.14−3.26
Coxian⋆−3.36−3.13−3.59
Ray⋆ (ours)−5.14−5.03−5.44
  • Paired contrasts: Ray⋆ beats softmax in 24/24 seed-length pairs (length-512 article 95% CI [−7.10, −3.69], seed+article 95% CI [−8.20, −2.73]), beats Coxian⋆ at all lengths with 95% article CIs excluding 0 (−1.86 [−3.43, −0.12] at 512, 7/8 seeds), and has lower mean NLL than Mix-2⋆ at every length (−2.18 [−3.88, −0.47] at 512, 7/8 seeds; Table S3).
  • Learned temperature: Ray − Temperature is negative in both mean and median across all 6 protocol × length cells (6/8 seeds at 256 and 512; Tables S3–S4). All 24 logged coupled runs end at γ<0\gamma < 0 (Figure 4c), a region excluded from every temperature (γ≡0\gamma \equiv 0) and positive mixture (γ≥0\gamma \ge 0; Theorem 2), and projecting every Ray head of the seed-42 model onto its best positive temperature changes layer outputs by 1.6–4.6%, 64–160× the FP16 reconstruction error (Section 5.4).
  • Mix-2 diagnosis (Supp. B.3, Figure 4b–c): Default Mix-2 starts heavy-tailed (γ=+0.25\gamma = +0.25), pays an early loss penalty, then merges its rates in 50–69% of heads. Started near softmax (Mix-2⋆), it beats softmax in 8/8 seeds yet merges its rates in 14–16 of 16 heads at every swept LR from 0.003 to 0.1 (γ→0\gamma \to 0; median smaller gate 0.20–0.27 at 0.03). All 24 logged coupled runs end at γ<0\gamma < 0 (Ray −0.32-0.32 to −0.44-0.44; Coxian⋆ −0.79-0.79 to −1.58-1.58), and two-state Ray⋆ captures the coupled gain without Coxian's extra rate. Started at softmax too, Ray reaches 3.54916 calibration NLL, the lowest of any seed-42 run (Table S5).
  • Completeness and notation: Theorem 3 (Section 3.3, Supp. I) proves the converse to Theorem 1; Table S1 collects all notation, and Section 7 separates expressivity, controlled learnability, language modeling, and execution.

2. Single-pass GPU online merge: FlashAttention-2-level long-context decoding and matched Qwen2.5-0.5B execution

Single-pass GPU kernels implementing Algorithm 1 (Supp. D) decode within 0.5–6.6% of FlashAttention-2 at 16k–128k cached keys and run matched Qwen2.5-0.5B forward at 1.03–1.19× (BF16/FP16) and training at 1.13–1.17× (4k–8k) the fastest optimized softmax. (Section 5.6; Supp. C.4–C.6, Tables S9–S14, Figure S12.)

  • Split-KV decoding (16k–128k keys): Matches FP64 to 2.0–5.9×10−72.0\text{–}5.9 \times 10^{-7} across 1–256 splits in any merge order (matching softmax's online merge in the same code), at 80–93% DRAM bandwidth and ≤8.2\le 8.2 MiB state.
  • Fused BF16 training kernel: Forward runs at 1.55–1.60× same-code Triton softmax at 8k (at its 1.5× matmul FLOP ratio) with the same 128×64128 \times 64 tile and 8 warps/SM; backward reaches 1.01–1.12× same-code softmax at 16k.
  • Matched Qwen2.5-0.5B benchmark (Table S14): Swapping only the attention core keeps BF16/FP16 forward peak memory within 0.7% of the fastest softmax core, runs FP32 forward at 1.06–1.26× fastest softmax (memory within 0.2%), and matches same-code softmax training memory (+2.1–3.2% vs. FA2 native GQA).

We thank all three reviewers again for feedback that sharpened our theorems, experimental controls, and GPU evaluation.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.