Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Linear Attention › Performer: Unbiased Softmax Approximation

Michael BrenndoerferUpdated June 28, 20255 min read

Language AI HandbookAll chapters

Part 17 of 67Efficient Attention

Chapter 123Linear Attention › Performer: Unbiased Softmax Approximation

Reading section 9 of 15 · Performer: Unbiased Softmax Approximation · 5 minSection 9 of 15 · 5 min

Section 9 of 15 · 5 min read

Linear Attention › Performer: Unbiased Softmax ApproximationOne section · Sections in this chapter9 / 15 ↓

Sections in this chapter15

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

The simple feature maps we've examined (ELU, ReLU) don't approximate softmax attention well. Performer, introduced by Choromanski et al. in 2020, addresses this with a clever approach called FAVOR+ (Fast Attention Via positive Orthogonal Random features).

The goal is to find a feature map $\phi$ such that:

\mathbb{E}[\phi(q)^T \phi(k)] = \exp(q^T k)

where:

$\mathbb{E}[\cdot]$ : the expectation operator, averaging over the random projection vectors
$\phi(q)^T \phi(k)$ : the inner product of feature-mapped query and key
$\exp(q^T k)$ : the true softmax kernel (without the scaling factor)

When this equality holds in expectation, we say the approximation is unbiased: on average, linear attention produces the same result as softmax attention. Performer achieves this by using positive random features:

\phi(x) = \frac{\exp(-\|x\|^2/2)}{\sqrt{m}} \left[ \exp(\omega_1^T x), \ldots, \exp(\omega_m^T x) \right]

where $\omega_i \sim \mathcal{N}(0, I)$ are random projection vectors drawn from a standard normal distribution, and $m$ is the number of random features that controls the trade-off between approximation quality and computational cost.

In[25]:

Code

def performer_attention(Q, K, V, num_features=256, eps=1e-6):
    """
    Performer attention using FAVOR+ positive random features.

    Args:
        Q: Query matrix of shape (n, d_k)
        K: Key matrix of shape (n, d_k)
        V: Value matrix of shape (n, d_v)
        num_features: Number of random features m
        eps: Numerical stability constant

    Returns:
        Output of shape (n, d_v)
    """
    n, d_k = Q.shape

    # Sample random projection matrix (in practice, this would be fixed per layer)
    np.random.seed(0)  # For reproducibility
    random_matrix = np.random.randn(d_k, num_features) / np.sqrt(d_k)

    def favor_plus_features(x):
        """Compute FAVOR+ positive random features."""
        # x: (n, d_k), random_matrix: (d_k, m)
        projection = x @ random_matrix  # (n, m)
        norm_sq = np.sum(x**2, axis=-1, keepdims=True)  # (n, 1)

        # Positive features with normalization
        features = np.exp(projection - norm_sq / 2) / np.sqrt(num_features)
        return features

    Q_prime = favor_plus_features(Q)  # (n, m)
    K_prime = favor_plus_features(K)  # (n, m)

    # Linear attention with FAVOR+ features
    KV = K_prime.T @ V  # (m, d_v)
    K_sum = K_prime.sum(axis=0)  # (m,)

    numerator = Q_prime @ KV  # (n, d_v)
    denominator = Q_prime @ K_sum + eps  # (n,)

    return numerator / denominator[:, np.newaxis]

In[26]:

Code

np.random.seed(42)
n, d = 64, 32
Q = np.random.randn(n, d).astype(np.float32) * 0.3
K = np.random.randn(n, d).astype(np.float32) * 0.3
V = np.random.randn(n, d).astype(np.float32)

# Compare Performer with different numbers of features
output_softmax, _ = softmax_attention(Q, K, V)

performer_results = []
for m in [32, 64, 128, 256, 512]:
    output_performer = performer_attention(Q, K, V, num_features=m)

    cosine_sim = np.mean(
        [
            np.dot(output_softmax[i], output_performer[i])
            / (
                np.linalg.norm(output_softmax[i])
                * np.linalg.norm(output_performer[i])
            )
            for i in range(n)
        ]
    )
    mse = np.mean((output_softmax - output_performer) ** 2)
    performer_results.append((m, cosine_sim, mse))

Out[27]:

Console

Performer Approximation Quality vs Number of Random Features:

Num Features    Cosine Sim      MSE            
---------------------------------------------
32              0.9800          0.000958       
64              0.9828          0.000857       
128             0.9821          0.000871       
256             0.9821          0.000870       
512             0.9808          0.000927

The results show that Performer's approximation improves with more random features. With 512 features, the cosine similarity approaches 1.0 and MSE drops significantly. This trade-off between approximation quality and feature dimension is central to Performer's design: more features mean better approximation but higher compute cost.

Out[28]:

Visualization

Bar plot of softmax attention weights showing sharp peaks at a few key positions with most weights near zero. — Standard softmax attention weights for a sample query position, showing the characteristic peaked distribution where a few positions dominate.

Bar plot of Performer attention weights showing similar peaked structure with slightly more noise in the distribution. — Performer's approximation with 256 random features. The overall shape is preserved, though fine details differ. More features improve fidelity.

Performer's key innovation is that by using positive features with the right normalization, the approximation is unbiased: the expected value equals true softmax attention. The variance of the approximation decreases as $O(1/m)$ , where $m$ is the number of random features. This means doubling the number of features halves the variance. This provides a controllable trade-off between computational cost and approximation fidelity.