| name | higher-order-linear-attention-mechanism |
| title | Higher-order Linear Attention |
| version | 0.0.2 |
| engine | skillxiv-v0.0.2-claude-opus-4.6 |
| license | MIT |
| url | https://arxiv.org/abs/2510.27258 |
| keywords | ["Linear Attention","Efficient Transformers","Streaming Inference","Long Context","Recurrent Architectures"] |
| description | Enable data-dependent higher-order interactions in attention using prefix-sufficient statistics that maintain linear time and constant state, replacing quadratic dot-product attention while preserving expressivity through compact matrix operations. |
Title: Scale Attention to Long Contexts via Linear-Time Matrix Interactions
Scaled dot-product attention requires O(n²) memory and time for sequence length n, crippling long-context applications. Higher-Order Linear Attention (HLA) maintains O(d²) state and O(d² + d·dᵥ) per-token cost by replacing the n×n attention matrix with compact prefix statistics—outer products of keys and query-value accumulators. The key insight is using extended summaries that prevent future-token leakage while enabling higher-order (beyond first-order) interactions.
The approach supports exact causal masking, streaming inference, and parallel training through associative scans.
Core Concept
Linear-Time Higher-Order Interactions:
- Prefix Statistics: Maintain key outer product sums (S^K_t) and query-value accumulators (C^QE_t)
- Streaming Computation: Compute outputs as
o_t = q_t^T S^K_t C^QE_t (linear time per token)
- Causal Masking: Extended summaries (G_t, h_t) prevent seeing future tokens
- Associative Scans: Enable chunk-parallel training that reproduces serial computation exactly
- Higher-Order Expressivity: Supports second-order and third-order tensor operations without quadratic scaling
Architecture Overview
- Key Statistics: d×d matrix of key outer products (S^K_t = Σ_i k_i k_i^T)
- Query-Value Accumulator: d×d_v matrix (C^QE_t = Σ_i φ(q_i) v_i)
- Cross-Term Accumulator: G_t prevents future-token leakage in causal setting
- Normalization: Denominator terms (h_t, m_t) for masked computation
- Multi-Head Support: Efficient with multi-query attention (O(h·d·d_v) space per head group)
Implementation Steps
1. Implement Prefix Statistics Computation
Maintain running statistics instead of materializing attention matrices.
class HigherOrderLinearAttention(nn.Module):
def __init__(self, dim, num_heads, dv=None):
self.num_heads = num_heads
self.dim = dim // num_heads
.dv = dv dim // num_heads
():
batch, seq_len, dim = query.shape
d = .dim
dv = .dv
S_K = torch.zeros(batch, .num_heads, d, d, device=query.device)
C_QE = torch.zeros(batch, .num_heads, d, dv, device=query.device)
G_t = torch.zeros(batch, .num_heads, d, dv, device=query.device)
h_t = torch.zeros(batch, .num_heads, d, device=query.device)
m_t = torch.zeros(batch, .num_heads, device=query.device)
q = query.view(batch, seq_len, .num_heads, d).transpose(, )
k = key.view(batch, seq_len, .num_heads, d).transpose(, )
v = value.view(batch, seq_len, .num_heads, dv).transpose(, )
outputs = []
t (seq_len):
q_t = q[:, :, t, :]
k_t = k[:, :, t, :]
v_t = v[:, :, t, :]
S_K = S_K + torch.einsum(, k_t, k_t)
phi_q_t = torch.softmax(q_t / np.sqrt(d), dim=-)
C_QE = C_QE + torch.einsum(, phi_q_t, v_t)
S_times_C = torch.einsum(, S_K, C_QE)
output = torch.einsum(, q_t, S_times_C)
causal:
output = output - torch.einsum(, q_t, G_t)
G_t = G_t + torch.einsum(, phi_q_t, v_t)
m_t = m_t +
output = output / (m_t.unsqueeze(-) + )
outputs.append(output)
output = torch.stack(outputs, dim=)
output = output.transpose(, ).reshape(batch, seq_len, dim)
output
