Reassociate a feature-map kernel without claiming exact softmax

Map each query and key into r-dimensional features. Summing feature-key outer products with values produces an r-by-dv matrix, and summing feature keys produces an r-vector. A query feature multiplies both summaries: the first gives its value numerator, the second its normalization denominator. Keeping the denominator is essential for the normalized operator. Omitting it produces an unnormalized feature aggregation whose output scale depends on the key population and feature magnitudes.

Nonnegative similarities and a strictly positive denominator make the output a meaningful weighted average. Nonnegative feature coordinates are one sufficient way to avoid negative pair weights, but zero features or an empty key set can still give a zero denominator. A numerical epsilon changes the operator and should be specified rather than treated as an invisible algebraic fix. The feature-map domain and valid input assumptions belong beside the formula.

Given feature vectors, forming the summaries and applying N query features costs on the order of Nrdv arithmetic, with an aggregate state of rdv+r scalars for a streaming causal calculation. Feature construction adds its own cost, and output storage remains proportional to the query count. The attractive scaling assumes r and dv do not grow with N in the comparison. A very large feature width can erase the benefit even though no N-by-N score matrix is stored.

Causal attention uses prefix summaries rather than a summary of every key: after adding key/value j, only queries whose logical position permits that key may read the updated state. This recurrence resembles a recurrent model but does not grant arbitrary masks for free. Sliding windows need removals or another data structure, and general pairwise masks may destroy the single shared-summary factorization. Sequence packing must reset the state at the correct logical boundary.

The original linear-attention paper studies finite positive feature maps as alternative attention kernels. Performer studies random-feature approximations to the exponential similarity used by softmax-style attention. A finite alternative map can be computed exactly while differing substantially from exponential attention. A random-feature kernel estimate may have favorable expectation or concentration properties, yet dividing a random numerator by a random denominator does not generally yield an unbiased normalized output.

Evaluate error in outputs and gradients, and vary feature width, random seeds, input norms, and sequence length. Small denominators can amplify errors even when individual kernel estimates look reasonable. Also evaluate downstream task quality if the architecture changes. The same implementation can be mathematically correct for its finite feature map and a poor approximation to a target softmax distribution; correctness of reassociation and suitability of the similarity are separate claims.