Prefix-Sum PSD Attention Kernel

Integrate this as a structured attention branch or structured covariance kernel. Store unconstrained parameters a_1,...,a_n and define d_k=softplus(a_k), then compute x_k=sum_{r=1}^k d_r. The kernel is K_ij=x_min(i,j), or equivalently K=U diag(d) U^T. Do not materialize K for the value path: compute U^T V using suffix cumulative sums, multiply each row by d_k, and compute U times the result using prefix cumulative sums. This costs O(n d_model) time and O(n d_model) working memory. To use it in attention, either add beta K to dense QK^T/sqrt(d_model), or use K V as a parallel linear-attention branch with a learned scalar beta. If an entrywise transform is needed, use f(t)=softplus(c t+b) with c>=0, or f(t)=t^alpha with alpha>=1, and verify nonnegativity numerically. The paper provides the PSD guarantee from d_k>=0 and the scalar PSD-preserver condition; normalization, causal masking, beta selection, and quality improvements are empirical. First test on a 2-layer Transformer with 4 heads on WikiText-2 or synthetic long-range sequence prediction. Compare dense attention, standard linear attention, and one Min-kernel head at matched hidden size. Measure validation perplexity versus sequence length, wall-clock time, peak memory, and the smallest eigenvalue on short sequences. Success means stable nonnegative spectra and comparable perplexity with subquadratic value computation.