higher-order-linear-attention-mechanism

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  # d per head
        .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