<figure><img src="image_1.png" /></figure>

HAL
open science

# Demystifying Performer Attention: Handle Genome-Length Sequences Efficiently

Shakeel Ahmad Sheikh

► To cite this version:

Shakeel Ahmad Sheikh. Demystifying Performer Attention: Handle Genome-Length Sequences Efficiently. 2026. hal-05456769

HAL Id: hal-05456769

https://hal.science/hal-05456769v1

Submitted on 13 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC0 1.0 - Universal - International License
# Demystifying Performer Attention
## Handle Genome-Length Sequences Efficiently

Shakeel A. Sheikh

The Kashmir Hub for Artificial Intelligence Research (KHAIR)

shakeelzmail608@gmail.com

January 10, 2026

## Abstract

This document provides a comprehensive tutorial on attention mechanisms, starting from the fundamental self-attention mechanism and progressing to the efficient **Performer** attention. We explain all mathematical concepts with clarity, using gene sequence analysis as a motivating example throughout. The document includes step-by-step explanations, comparative analyses, practical examples, and complete PyTorch implementation code for **Performer** attention. All concepts are presented in an accessible manner suitable for both beginners and experienced practitioners in machine learning and computational biology.<fnref n="1" />

## Contents

<table><tr><td>1</td><td>Introduction</td><td>2</td></tr><tr><td>2</td><td>Normal Self-Attention</td><td>4</td></tr><tr><td>2.1</td><td>Intuition and Biological Motivation</td><td>4</td></tr><tr><td>2.2</td><td>Mathematical Formulation</td><td>4</td></tr><tr><td>2.2.1</td><td>Step 1: Linear Projections</td><td>4</td></tr><tr><td>2.2.2</td><td>Step 2: Attention Scores</td><td>5</td></tr><tr><td>2.2.3</td><td>Step 3: Softmax Normalization</td><td>5</td></tr><tr><td>2.2.4</td><td>Step 4: Weighted Combination</td><td>5</td></tr><tr><td>2.3</td><td>Example: 5 Genes</td><td>5</td></tr><tr><td>2.4</td><td>Computational Complexity</td><td>6</td></tr></table>

<footnote n="1">¹If you find any mistakes in the document, please let me know via email: shakeelzmail608@gmail.com.</footnote>
<table>
  <tbody>
    <tr>
      <td><b>3</b></td>
      <td><b>Performer Attention</b></td>
      <td><b>6</b></td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>Motivation and Core Idea</td>
      <td>6</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>Mathematical Foundation</td>
      <td>7</td>
    </tr>
    <tr>
      <td>3.2.1</td>
      <td>Kernel Reformulation</td>
      <td>7</td>
    </tr>
    <tr>
      <td>3.2.2</td>
      <td>Random Feature Maps</td>
      <td>8</td>
    </tr>
    <tr>
      <td>3.2.3</td>
      <td>Positive Random Features (PRF)</td>
      <td>8</td>
    </tr>
    <tr>
      <td>3.2.4</td>
      <td>Random Feature Maps: The Approximation Principle</td>
      <td>8</td>
    </tr>
    <tr>
      <td>3.2.5</td>
      <td>Positive Random Features (PRF) for the Softmax Kernel</td>
      <td>9</td>
    </tr>
    <tr>
      <td>3.3</td>
      <td>Step-by-Step Algorithm</td>
      <td>10</td>
    </tr>
    <tr>
      <td>3.4</td>
      <td>Detailed Example with 5 Genes</td>
      <td>10</td>
    </tr>
    <tr>
      <td>3.4.1</td>
      <td>Step 1: Compute Random Matrix W</td>
      <td>10</td>
    </tr>
    <tr>
      <td>3.4.2</td>
      <td>Step 2: Compute Random Features for Gene 1</td>
      <td>10</td>
    </tr>
    <tr>
      <td>3.5</td>
      <td>Complexity Analysis</td>
      <td>11</td>
    </tr>
    <tr>
      <td><b>4</b></td>
      <td><b>Comparative Analysis</b></td>
      <td><b>11</b></td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>Theoretical Differences</td>
      <td>11</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>Practical Considerations for Gene Analysis</td>
      <td>11</td>
    </tr>
    <tr>
      <td>4.2.1</td>
      <td>When to Use Self-Attention:</td>
      <td>11</td>
    </tr>
    <tr>
      <td>4.2.2</td>
      <td>When to Use Performer:</td>
      <td>12</td>
    </tr>
    <tr>
      <td><b>5</b></td>
      <td><b>PyTorch Implementation</b></td>
      <td><b>12</b></td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Complete Performer Attention Module</td>
      <td>12</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Training Example for Gene Function Prediction</td>
      <td>18</td>
    </tr>
    <tr>
      <td><b>6</b></td>
      <td><b>Biological Applications</b></td>
      <td><b>21</b></td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Gene-Gene Interaction Networks</td>
      <td>21</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>Single-Cell RNA-Seq Analysis</td>
      <td>22</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>Protein Sequence Analysis</td>
      <td>22</td>
    </tr>
    <tr>
      <td><b>7</b></td>
      <td><b>Advanced Topics</b></td>
      <td><b>22</b></td>
    </tr>
    <tr>
      <td>7.1</td>
      <td>Different Kernel Functions</td>
      <td>22</td>
    </tr>
    <tr>
      <td>7.2</td>
      <td>Hyperparameter Selection</td>
      <td>22</td>
    </tr>
    <tr>
      <td><b>8</b></td>
      <td><b>Conclusion</b></td>
      <td><b>23</b></td>
    </tr>
    <tr>
      <td>8.1</td>
      <td>Future Directions</td>
      <td>23</td>
    </tr>
    <tr>
      <td><b>A</b></td>
      <td><b>Appendix: Mathematical Derivations</b></td>
      <td><b>24</b></td>
    </tr>
    <tr>
      <td>A.1</td>
      <td>Softmax Kernel Derivation</td>
      <td>24</td>
    </tr>
    <tr>
      <td>A.2</td>
      <td>Random Feature Maps for Gaussian Kernel</td>
      <td>24</td>
    </tr>
  </tbody>
</table>

# 1 Introduction

Attention mechanisms have revolutionized deep learning, particularly in natural language processing and computational biology. However, the quadratic complexity of standard self-attention limits its applicability to long sequences, such as gene sequences, protein sequences,
UNDERSTANDING ATTENTION MECHANISMS: SELF vs. PERFORMER

<figure><img src="image_3.png" /><figcaption>Figure 1: Comparison between standard self-attention (left) and Performer attention (right). In self-attention, the input sequence $X \in \mathbb{R}^{N \times d}$ is first projected into Queries ($Q$), Keys ($K$), and Values ($V$). The attention matrix is then computed using the softmax of the similarity scores $QK^\top$, producing a dense $N \times N$ matrix that assigns a weight to every pair of tokens, resulting in quadratic time and memory complexity $O(N^2)$. The final output is obtained as $Z = \mathrm{softmax}(QK^\top)V$. In contrast, Performer attention replaces the softmax kernel with a randomized feature map $\phi(\cdot)$ that approximates the exponential kernel. Queries and keys are transformed into low-dimensional random features $Q' = \phi(Q)$ and $K' = \phi(K)$, allowing the attention computation to be reordered as $Z = Q'(K'^\top V) \odot (Q'(K'^\top I))$, which avoids explicitly forming the $N \times N$ attention matrix. This reduces both time and memory complexity from $O(N^2)$ to $O(N)$, enabling efficient modeling of very long sequences such as genomic data or long documents.</figcaption></figure>
or single-cell RNA-seq data. The Performer (Performer Attention) addresses this limitation by providing a linear-time approximation to self-attention through kernel methods and random features.

In this tutorial, we:

1. Explain normal self-attention with intuitive examples

2. Introduce the mathematical foundation of attention mechanisms

3. Detail the Performer attention mechanism step-by-step

4. Compare computational complexities

5. Provide practical examples with gene sequences

6. Include complete PyTorch implementation

# 2 Normal Self-Attention

## 2.1 Intuition and Biological Motivation

Consider a set of $N$ genes, where each gene is represented by its expression levels across different conditions or time points. In biological systems, genes interact with each other in complex networks. Self-attention allows each gene to "attend" to all other genes, determining which relationships are most important for understanding its function within a pathway or network.

## 2.2 Mathematical Formulation

Let $X \in \mathbb{R}^{N \times d}$ represent our input matrix, where:

* $N$: Number of genes (sequence length)

* $d$: Number of features per gene (embedding dimension)

### 2.2.1 Step 1: Linear Projections

We define three learnable weight matrices:

$$W^Q \in \mathbb{R}^{d \times d_k} \quad (\text{Query weights})$$

$$W^K \in \mathbb{R}^{d \times d_k} \quad (\text{Key weights})$$

$$W^V \in \mathbb{R}^{d \times d_v} \quad (\text{Value weights})$$

These project the input into query, key, and value representations:

$$Q = XW^Q \in \mathbb{R}^{N \times d_k} \qquad (1)$$

$$K = XW^K \in \mathbb{R}^{N \times d_k} \qquad (2)$$

$$V = XW^V \in \mathbb{R}^{N \times d_v} \qquad (3)$$
assuming dimension $d_k = d_v = d$

**Biological Interpretation:**

* Q (Query): "What information does this gene need?"

* K (Key): "What information does this gene provide?"

* V (Value): "What is this gene's actual expression profile?"

### 2.2.2 Step 2: Attention Scores

The attention scores measure similarity between queries and keys:

$$S = \frac{QK^T}{\sqrt{d_k}} \in \mathbb{R}^{N \times N} \qquad (4)$$

The scaling factor $\sqrt{d_k}$ prevents extreme values that could cause vanishing gradients in softmax.

### 2.2.3 Step 3: Softmax Normalization

Apply softmax row-wise to obtain attention weights:

$$A = \mathrm{softmax}(S) = \frac{\exp(S_{ij})}{\sum_{k=1}^{N} \exp(S_{ik})} \in \mathbb{R}^{N \times N} \qquad (5)$$

Each row sums to 1, representing a probability distribution over genes to attend to.

### 2.2.4 Step 4: Weighted Combination

The output is a weighted sum of values:

$$Z = AV \in \mathbb{R}^{N \times d_v} \qquad (6)$$

## 2.3 Example: 5 Genes

Consider 5 genes with 4-dimensional feature vectors representing expression levels:

<table><caption>Table 1: Example gene expression features</caption><thead><tr><th>Gene</th><th>Feature 1</th><th>Feature 2</th><th>Feature 3</th><th>Feature 4</th></tr></thead><tbody><tr><td>G1</td><td>1.0</td><td>0.5</td><td>0.2</td><td>1.5</td></tr><tr><td>G2</td><td>0.8</td><td>1.2</td><td>0.9</td><td>0.3</td></tr><tr><td>G3</td><td>0.3</td><td>0.7</td><td>1.8</td><td>0.4</td></tr><tr><td>G4</td><td>1.2</td><td>0.4</td><td>0.6</td><td>1.1</td></tr><tr><td>G5</td><td>0.9</td><td>1.0</td><td>0.5</td><td>0.8</td></tr></tbody></table>

Let $d_k = d_v = 4$ for simplicity. After linear projections:
**Step 1:** Compute $Q, K, V$ (using small random weights)

$$Q = \begin{bmatrix} 0.8 & -0.3 & 1.2 & 0.5 \\ 0.6 & 1.1 & 0.8 & -0.2 \\ -0.1 & 0.5 & 1.5 & 0.3 \\ 1.1 & 0.3 & 0.7 & 0.9 \\ 0.7 & 0.9 & 0.4 & 0.6 \end{bmatrix}, \quad K = \begin{bmatrix} 0.9 & -0.2 & 1.1 & 0.6 \\ 0.7 & 1.0 & 0.9 & -0.1 \\ -0.2 & 0.6 & 1.6 & 0.4 \\ 1.0 & 0.4 & 0.8 & 1.0 \\ 0.8 & 0.8 & 0.5 & 0.7 \end{bmatrix}$$

**Step 2:** Compute attention scores for Gene 1:

$$q_1 = [0.8, -0.3, 1.2, 0.5]$$

$$k_1 = [0.9, -0.2, 1.1, 0.6] \Rightarrow q_1 \cdot k_1 = 2.12$$

$$k_2 = [0.7, 1.0, 0.9, -0.1] \Rightarrow q_1 \cdot k_2 = 0.89$$

$$S_1 = [2.12, 0.89, 1.45, 2.01, 1.67]/2 \quad (\text{divided by } \sqrt{4} = 2)$$

**Step 3:** Apply softmax:

$$\begin{aligned} A_1 &= \mathrm{softmax}([1.06, 0.445, 0.725, 1.005, 0.835]) \\ &= [0.286, 0.115, 0.162, 0.239, 0.198] \end{aligned}$$

**Step 4:** Compute output for Gene 1:

$$z_1 = 0.286 \cdot v_1 + 0.115 \cdot v_2 + 0.162 \cdot v_3 + 0.239 \cdot v_4 + 0.198 \cdot v_5$$

## 2.4 Computational Complexity

The bottleneck is computing $QK^T$:

* **Memory:** $O(N^2)$ to store the attention matrix

* **Computation:** $O(N^2d_k)$ for matrix multiplication

For $N = 10,000$ genes and $d_k = 64$:

$$\text{Memory} = 10,000^2 \times 4 \text{ bytes} \approx 400 \text{ MB}$$

$$\text{Operations} = 10,000^2 \times 64 \approx 6.4 \times 10^9$$

This quadratic scaling makes standard attention impractical for large gene sequences.

# 3 Performer Attention

## 3.1 Motivation and Core Idea

The Performer attention mechanism addresses the quadratic complexity problem by:

1. Reformulating attention as a kernel method

2. Using random feature maps for kernel approximation

3. Reordering computations to avoid explicit $N \times N$ matrices
## 3.2 Mathematical Foundation

### 3.2.1 Kernel Reformulation

Recall that softmax attention can be written as:

$$ \text{Attention}(Q, K, V) = D^{-1} \exp \left( \frac{QK^T}{\sqrt{d_k}} \right) V \quad (7) $$

where $D = \text{diag} \left( \exp \left( \frac{QK^T}{\sqrt{d_k}} \right) \mathbf{1}_N \right)$.

The key insight is to treat $\exp(q_i^T k_j / \sqrt{d_k})$ as a kernel function:

$$ K_{\text{softmax}}(x, y) = \exp(x^T y) \quad (8) $$

## Understanding Softmax as a Kernel in Attention

### Why Softmax Acts as a Kernel in Attention Mechanisms

To understand why we treat softmax as a kernel, we need to examine the Attention mechanism at the element-wise level. A kernel can be viewed as a function $K(x, y)$ that takes two vectors and returns a scalar representing their similarity.

### 1. The Entry-Wise View

In standard attention, we compute the matrix $A = \exp \left( \frac{QK^T}{\sqrt{d_k}} \right)$. Focusing on a single entry at position $(i, j)$:

$$ A_{ij} = \exp \left( \frac{q_i^T k_j}{\sqrt{d_k}} \right) $$

This value $A_{ij}$ represents the raw *affinity* between the i-th query (e.g., Gene A) and the j-th key (e.g., Gene B). In kernel theory, any function computing such similarity can be interpreted as a **Kernel Function** $K(x, y)$.

### 2. The Normalization Role of D

Softmax isn't merely an exponential—it includes normalization so each row sums to 1. In standard notation:

$$ \text{Softmax}(\mathbf{z})_i = \frac{\exp(z_i)}{\sum_{j=1}^{N} \exp(z_j)} $$

In matrix formulation, this is captured through the diagonal matrix **D**. Each diagonal entry $D_{ii}$ contains the sum of affinities for row i:

$$ D_{ii} = \sum_{j=1}^{N} \exp \left( \frac{q_i^T k_j}{\sqrt{d_k}} \right) $$

The final attention weights are obtained by:

$$ \text{Attention}(\mathbf{Q}, \mathbf{K}, \mathbf{V}) = \mathbf{D}^{-1} \exp \left( \frac{\mathbf{Q}\mathbf{K}^T}{\sqrt{d_k}} \right) \mathbf{V} $$
Multiplication by $\mathbf{D}^{-1}$ divides each element in row $i$ by $D_{ii}$, exactly implementing the softmax operation. Thus, the softmax attention mechanism can be interpreted as applying a kernel (the exponential of scaled dot-products) followed by row-wise normalization.

### 3.2.2 Random Feature Maps

The kernel trick approximates the kernel function using random features:

$$K(x, y) = \mathbb{E}[\phi(x)^T \phi(y)] \approx \phi(x)^T \phi(y) \quad (9)$$

For the softmax kernel, we can use trigonometric random features or positive random features.

### 3.2.3 Positive Random Features (PRF)

The Performer uses:

$$\phi(x) = \frac{1}{\sqrt{m}} \exp \left( Wx - \frac{\|x\|^2}{2} \right) \quad (10)$$

where $W \in \mathbb{R}^{m \times d}$ is a random matrix with orthogonal rows.

## Why Random Feature Maps and Positive Random Features (PRF)

### Motivation: The Computational Bottleneck of Exact Kernel Methods

The standard attention mechanism with softmax has a quadratic computational complexity $O(N^2)$ in sequence length, as it requires computing all pairwise interactions between queries and keys. This becomes prohibitive for long sequences. Random feature maps provide a solution by approximating the kernel function with linear complexity.

### 3.2.4 Random Feature Maps: The Approximation Principle

The core idea comes from the kernel trick, which states that many kernel functions can be approximated by explicit feature maps:

$$K(\mathbf{x}, \mathbf{y}) = \mathbb{E}_{\omega \sim p(\omega)}[\phi_{\omega}(\mathbf{x})^T \phi_{\omega}(\mathbf{y})] \approx \phi(\mathbf{x})^T \phi(\mathbf{y}) \quad (11)$$

where $\phi(\mathbf{x})$ is a random feature map that projects the input into a higher-dimensional space (dimension $m$), and the expectation is over some distribution $p(\omega)$ of random parameters.

**Why this works:** Many kernels (including the softmax/Gaussian kernel) can be expressed as an inner product in some implicit feature space. Random feature maps make this explicit, allowing us to:

* Transform queries and keys separately: $\phi(\mathbf{q}_i)$ and $\phi(\mathbf{k}_j)$
* Compute attention as: Attention ≈ $\frac{\phi(\mathbf{Q})\phi(\mathbf{K})^T\mathbf{V}}{\text{normalizer}}$

* Achieve $O(Nmd)$ complexity instead of $O(N^2d)$

### 3.2.5 Positive Random Features (PRF) for the Softmax Kernel

For the softmax kernel $K(\mathbf{x}, \mathbf{y}) = \exp(\mathbf{x}^T\mathbf{y})$, we need a specific type of random features. The Performer model (Choromanski et al., 2020) uses:

$$ \phi(\mathbf{x}) = \frac{1}{\sqrt{m}} \exp \left( \mathbf{W}\mathbf{x} - \frac{\|\mathbf{x}\|^2}{2} \right) \qquad (12) $$

where $\mathbf{W} \in \mathbb{R}^{m \times d}$ is a random matrix with rows $\mathbf{w}_i \sim \mathcal{N}(0, \mathbf{I}_d)$, often made orthogonal for better approximation.

**Why this particular form?** This stems from the Gaussian integral identity:

$$ \exp(\mathbf{x}^T \mathbf{y}) = \mathbb{E}_{\mathbf{w} \sim \mathcal{N}(0, \mathbf{I})} \left[ \exp \left( \mathbf{w}^T \mathbf{x} - \frac{\|\mathbf{x}\|^2}{2} \right) \exp \left( \mathbf{w}^T \mathbf{y} - \frac{\|\mathbf{y}\|^2}{2} \right) \right] \qquad (13) $$

**Key properties of PRF:**

* **Positivity:** All features are positive ($\exp(\cdot) > 0$), which is crucial for stable attention computation

* **Unbiased estimator:** $\mathbb{E}[\phi(\mathbf{x})^T \phi(\mathbf{y})] = \exp(\mathbf{x}^T \mathbf{y})$

* **Variance reduction:** Orthogonal rows in $\mathbf{W}$ reduce the variance of the estimator

* **Linearization:** Allows rewriting attention as:

$$ \text{Attention}(\mathbf{Q}, \mathbf{K}, \mathbf{V}) \approx \mathbf{D}^{-1}(\phi(\mathbf{Q})(\phi(\mathbf{K})^T\mathbf{V})) $$

where $\mathbf{D}$ is computed from $\phi(\mathbf{Q})\phi(\mathbf{K})^T\mathbf{1}$

**Mathematical Derivation:** Given $\phi(\mathbf{x}) = \frac{1}{\sqrt{m}} \exp(\mathbf{W}\mathbf{x} - \|\mathbf{x}\|^2/2)$, we have:

$$ \phi(\mathbf{x})^T \phi(\mathbf{y}) = \frac{1}{m} \sum_{i=1}^{m} \exp \left( \mathbf{w}_i^T (\mathbf{x} + \mathbf{y}) - \frac{\|\mathbf{x}\|^2 + \|\mathbf{y}\|^2}{2} \right) $$

By the law of large numbers, as $m \to \infty$, this converges to $\exp(\mathbf{x}^T \mathbf{y})$.

**Practical Impact:** The PRF approach enables linear attention mechanisms that:

* Scale to very long sequences (thousands to millions of tokens)

* Maintain theoretical guarantees of approximation quality

* Can be trained end-to-end like standard transformers

* Have been successfully applied in models like Performer, Linear Transformer, and others
## 3.3 Step-by-Step Algorithm

**Algorithm 1 Performer Attention Algorithm**

**Require:** Input $X \in \mathbb{R}^{N \times d}$, random feature dimension $m$

**Ensure:** Output $Z \in \mathbb{R}^{N \times d}$

1: // Step 1: Linear projections (same as self-attention)

2: $Q, K, V \leftarrow \text{LinearProjections}(X)$

3: // Step 2: Compute random features

4: Generate random orthogonal matrix $W \in \mathbb{R}^{m \times d}$

5: $Q' \leftarrow \phi(Q) = \frac{1}{\sqrt{m}} \exp(WQ - \frac{\|Q\|^2}{2})$

6: $K' \leftarrow \phi(K) = \frac{1}{\sqrt{m}} \exp(WK - \frac{\|K\|^2}{2})$

7: // Step 3: Reorder computations

8: // Instead of: $Z = \text{softmax}(QK^T)V$

9: // We compute: $Z = (Q'(K'^T V)) \otimes (Q'(K'^T \mathbf{1}_N))$

10: numerator $\leftarrow Q' \times (K'^T \times V)$

11: denominator $\leftarrow Q' \times (K'^T \times \mathbf{1}_N)$

12: $Z \leftarrow$ numerator $\otimes$ denominator

13: **return** $Z$

# Why Random Feature Maps and Positive Random Features (PRF)

## 3.4 Detailed Example with 5 Genes

Let's use the same 5 genes from Table 1, with:

* $d = 4$ (original features)

* $m = 8$ (random features, much smaller than $N^2 = 25$)

* $d_k = d_v = 4$

### 3.4.1 Step 1: Compute Random Matrix $W$

Generate random orthogonal matrix $W \in \mathbb{R}^{8 \times 4}$:

$$W = \begin{bmatrix} 0.3 & -0.2 & 0.8 & 0.5 \\ -0.4 & 0.7 & 0.1 & -0.6 \\ 0.6 & 0.3 & -0.4 & 0.6 \\ 0.1 & -0.5 & 0.7 & 0.5 \\ -0.7 & 0.1 & 0.5 & -0.5 \\ 0.5 & 0.6 & 0.2 & 0.6 \\ -0.2 & 0.8 & -0.3 & 0.5 \\ 0.4 & 0.2 & 0.6 & -0.7 \end{bmatrix}$$

### 3.4.2 Step 2: Compute Random Features for Gene 1

After linear projection, suppose $q_1 = [0.8, -0.3, 1.2, 0.5]$.
Compute $Wq_1$:

$$ Wq_1 = \begin{bmatrix} 0.3 \times 0.8 + (-0.2) \times (-0.3) + 0.8 \times 1.2 + 0.5 \times 0.5 \\ -0.4 \times 0.8 + 0.7 \times (-0.3) + 0.1 \times 1.2 + (-0.6) \times 0.5 \\ \vdots \\ 0.4 \times 0.8 + 0.2 \times (-0.3) + 0.6 \times 1.2 + (-0.7) \times 0.5 \end{bmatrix} = [1.05, -0.62, 0.78, 0.45, -1.12, 1.21, -0.35, 0.92] $$

$$ \text{Compute } \|q_1\|^2/2 = (0.8^2 + (-0.3)^2 + 1.2^2 + 0.5^2)/2 = 0.955 $$

Apply transformation:

$$ \begin{aligned} \phi(q_1) &= \frac{1}{\sqrt{8}} \exp([1.05, -0.62, 0.78, 0.45, -1.12, 1.21, -0.35, 0.92] - 0.955) \\ &= \frac{1}{2.828} \times [\exp(0.095), \exp(-1.575), \dots, \exp(-0.035)] \\ &= [0.18, 0.05, 0.12, 0.09, 0.03, 0.21, 0.07, 0.14] \end{aligned} $$

## 3.5 Complexity Analysis

<table><caption>Table 2: Complexity comparison ($m \ll N$)</caption><thead><tr><th>Operation</th><th>Self-Attention</th><th>Performer</th><th>Savings</th></tr></thead><tbody><tr><td>Memory</td><td>O(N<sup>2</sup>)</td><td>O(Nm)</td><td>O(N/m)</td></tr><tr><td>Computation</td><td>O(N<sup>2</sup>d<sub>k</sub>)</td><td>O(Nmd<sub>k</sub>)</td><td>O(N/m)</td></tr><tr><td>Matrix Size</td><td>N × N</td><td>N × m</td><td>-</td></tr></tbody></table>

For $N = 10,000$, $d_k = 64$, $m = 256$:

$$ \text{Memory savings} = \frac{N}{m} = \frac{10,000}{256} \approx 39 \times $$

$$ \text{Computation savings} = \frac{N^2 d_k}{Nmd_k} = \frac{N}{m} \approx 39 \times $$

# 4 Comparative Analysis

## 4.1 Theoretical Differences

## 4.2 Practical Considerations for Gene Analysis

### 4.2.1 When to Use Self-Attention:

* Small gene sets ($N < 1,000$)

* When exact attention patterns are crucial
<table><caption>Table 3: Theoretical comparison</caption><thead><tr><th>Aspect</th><th>Self-Attention</th><th>Performer</th></tr></thead><tbody><tr><td>Exactness</td><td>Exact computation</td><td>Approximate via random features</td></tr><tr><td>Memory</td><td>Quadratic in sequence length</td><td>Linear in sequence length</td></tr><tr><td>Compute Time</td><td>Quadratic in sequence length</td><td>Linear in sequence length</td></tr><tr><td>Parallelization</td><td>Limited by N<sup>2</sup> matrix</td><td>Highly parallelizable</td></tr><tr><td>Theoretical Guarantees</td><td>Exact result</td><td>Probabilistic bounds</td></tr><tr><td>Biological Interpretation</td><td>Exact gene-gene interactions</td><td>Approximate interactions</td></tr></tbody></table>

* For interpretability studies requiring exact weights

* When computational resources are abundant

### 4.2.2 When to Use Performer:

* Genome-scale analysis ($N > 10,000$)

* Single-cell RNA-seq with many cells

* Protein sequence analysis

* Real-time biological applications

## 5 PyTorch Implementation

### 5.1 Complete Performer Attention Module

```python
1 import torch
2 import torch.nn as nn
3 import torch.nn(functional as F
4 import math
5
6
7 class PerformerAttention(nn.Module):
8     """
9     Performer Attention Module
10
11     Argss:
12         dim (int): Input dimension
13         heads (int): Number of attention heads
14         dim_head (int): Dimension per head
15         causal (bool): Whether to use causal masking
```
kernel_type (str): 'relu' or 'softmax' kernel
random_features (int): Number of random features (m)
"

def __init__(self, dim, heads=8, dim_head=64, causal=False,
kernel_type='relu', random_features=256):
super().__init__()
self.dim = dim
self heads = heads
self.dim_head = dim head
self.causal = causal
self.kernel_type = kernel_type
self.random_features = random_features

# Inner dimension for multi-head attention
inner_dim = dim head * heads

# Linear projections for Q, K, V
self.to_qkv = nn.Linear(dim, inner_dim * 3, bias=False)

# Output projection
self.to_out = nn.Linear(inner_dim, dim)

# Random projection matrix (not learned, fixed during training)
self.register_buffer('projection_matrix',
self.create projection _matrix(dim head,
random_features))

# Layer normalization for stability
self.norm = nn LayerNorm(dim head)

def create projection _matrix(self, dim, random_features):
"
Create random orthogonal matrix for kernel approximation

Args:
    dim: Input dimension
    random_features: Number of random features (m)

Returns:
    Random orthogonal matrix of shape [dim, random_features]
"

# Generate random matrix
rand mat = torch random _matrix, dim)

# Orthogonalize using QR decomposition
q, _ = torch lINALg.qr(rand mat, mode='reduced')

# Transpose to get [dim, random_features]
return q.t()

def relu kernel(self, x, is_query=False):
"
ReLU kernel approximation
```python
phi(x) = max(0, x) for both queries and keys
"
"
return F relu(x)

def softmax_kernel(self, x, is_query, projection_matrix):
    """
    Softmax kernel approximation using random features
    """
    For queries: $\phi(q) = \frac{1}{\sqrt{m}} * \exp(Wq - ||q||^2)$
    For keys: $\phi(k) = \frac{1}{\sqrt{m}} * \exp(Wk - ||k||^2)$
    """
    # Normalize inputs for numerical stability
    x = F normalize(x, dim=-1, p=2)

    # Project using random matrix
    projected = torch matmul(x, projection_matrix)

    # Compute squared norm
    x_normimm = (x ** 2). sum(dim=-1, keepdim=True)

    projected = projected - x_normimm / 2
    return torch exp(projected) / math sqrt(self.random_features)

def forward(self, x, mask=None):
    """
    Forward pass
    """
    # Step 1: Linear projections to get Q, K, V
    qkv = self.to_qkv(x).chunk(3, dim=-1)
    q, k, v = map(
        lambda t: t reshape(batch_size, seq_len, self heads, self dim head). transpose(1, 2),
        qkv
    )

    # Normalize for stability
    q = self .norm(q)
    k = self .norm(k)

    # Step 2: Apply kernel approximation
    if self .kernel_type == 'relu':
        q_prime = self .relu_kernel(q, is_query=True)
```
```python
k_prime = self gelu kernel(k, is_query=False)
else: # softmax kernel
    q_prime = self softmax kernel(q, is_query=True,
                                     projection_matrix = self.
projection_matrix)
    k_prime = self softmax kernel(k, is_query=False,
                                     projection_matrix = self.
projection_matrix)

# Step 3: Compute attention using kernel trick

# Transpose K' for efficient multiplication
k_prime_t = k_primeeadate(-2, -1) # [batch, heads, dim head,
                                seq_len]

# Compute K'^T V
ktv = torch matmul(k_prime_t, v) # [batch, heads, dim head,
                                dim head]

# Compute Q'(K'^T V)
numerator = torch matmul(q_prime, ktv) # [batch, heads, seq len,
                                dim head]

# Normalization: compute denominator
# Create ones tensor for denominator calculation
ones = torch ones(batch_size, seq_len, 1, device=x device)

# Compute K'^T * 1
kt_ones = torch matmul(k_prime_t, ones) # [batch, heads, dim head
                                , 1]

# Compute Q'(K'^T 1)
denominator = torch matmul(q_prime, kt_ones) # [batch, heads,
                                seq_len, 1]

# Avoid division by zero
denominator = denominator + 1e-8

# Normalize to get attention output
out = numerator / denominator

# Reshape back to original dimensions
out = out transpose(1, 2).reshape(batch_size, seq_len, -1)

# Final linear projection
return self to out(out)
```

```python
class GenePerformer (nn.Module):
    """
    Complete gene sequence model using Performer attention

    Argss:
        num genes: Number of unique genes in vocabulary
```
```python
dim: Embedding dimension
depth: Number of Performer layers
heads: Number of attention heads
dim_head: Dimension per head
random_features: Number of random features for approximation


def __init__(self, num genes, dim=128, depth=6, heads=8,
              dim head=64, random_features=256):
    super().__init__()

# Gene embeddings (learnable representations)
self.gene_embeddings = nn Embedding(num genes, dim)

# Positional encodings (for sequence order)
self position embeddings = nn.Parameter(torch randn(1, 1000, dim))

# Multiple Performer layers
self layers = nn ModuleList([
    PerformerAttention(
        dim=dim,
        heads=heads,
        dim head=dim head,
        kernel type='softmax',
        random_features = random_features
    )
    for _ in range (depth)
])

# Layer normalization
self .norm = nn LayerNorm(dim)

# Output layer for gene prediction tasks
self .output layer = nn Linear(dim, num genes)

def forward(self, gene indices, mask = None):
    """
    Forward pass for gene sequence analysis

   Args:
        gene indices: Tensor of shape [batch_size, seq_len]
            containing gene indices
        mask: Optional attention mask

   Returns:
        Logits for gene predictions
    """
    batch_size, seq_len = gene indices.shape

# Get gene embeddings
x = self .gene embeddings(gene indices) # [batch, seq_len, dim]

# Add positional embeddings
pos emb = self .position embeddings[:, :seq_len, :]
```
```python
222     x = x + posEmb
223
224 # Apply Performer layers with residual connections
225 for layer in self layers:
226     # Residual connection
227     x = layer(x, mask = mask) + x
228
229 # Final normalization
230     x = self .norm(x)
231
232 # Output predictions
233     return self .output _layer(x)
234
235
236 def create _gene _attention _model(config):
237     """
238 Factory function to create gene attention model
239     """
240    Args:
241         config: Dictionary containing model configuration
242     Returns:
243         Initialized GenePerformer model
244     """
245     model = GenePerformer(
246         num genes = config ['num genes'],
247         dim =config .get('dim', 128),
248         depth =config .get('depth', 6),
249         heads =config .get('heads', 8),
250         dim head =config .get('dim head', 64),
251         random features =config .get('random features', 256)
252     )
253
254 # Initialize weights
255     for p in model .parameters():
256         if p .dim() >1:
257             nn .init .xavier _uniform_(p)
258
259     return model
260
261
262
263 # Example usage
264 if __name__ == "__main__":
265     # Configuration
266     config = {
267         'num genes': 1000, # Vocabulary size
268         'dim': 128,
269         'depth': 6,
270         'heads': 8,
271         'dim head': 64,
272         'random features': 256
273     }
274
275 # Create model
```
```python
model = create gene attention model (config)

# Create sample batch of gene sequences
batch_size = 32
seq_len = 50  # 50 genes per sequence
gene sequences = torch .randint(0, config['num genes'], (batch_size, seq_len))

# Forward pass
print(f"Input shape: {gene sequences.shape}")
output = model(gene sequences)
print(f"Output shape: {output.shape}")

# Memory usage comparison
total_params = sum(p .numel() for p in model .parameters())
print(f"Total parameters: {total_params :,}")

# Example of memory savings
N = seq_len
m = config['random_features']
d = config['dim head']

normal_memory = N * N * 4  # bytes for float32
performer_memory = N * m * d * 4

print(f"\nMemory comparison for seq_len={N}:")
print(f"Normal attention: {normal_memory :,} bytes")
print(f"Performer attention: {performer_memory :,} bytes")
print(f"Savings: {normal_memory /performer_memory :.1f}x")
```

<caption>Listing 1: Complete Performer Attention Implementation</caption>

## 5.2 Training Example for Gene Function Prediction

```python
import torch
import torch.nn as nn
import torch.optim as optim
from torch.utils.data import Dataset, DataLoader
import numpy as np

class GeneDataset(Dataset):
    """Dataset for gene sequence analysis"""

    def __init__(self, sequences, labels, max_len=100):
        self.sequences = sequences  # List of gene index sequences
        self.labels = labels      # Corresponding function labels
        self.max_len = max_len

    def __len__(self):
        return len(self.sequences)

    def __getitem__(self, idx):
```
```python
20 seq = self.sequences[idx][:self.max_len]
21 label = self.labels[idx]
22
23 # Pad sequence if necessary
24 if len(seq) < self.max_len:
25     seq = seq + [0] * (self.max_len - len(seq))
26
27 return torch.tensor(seq), torch.tensor(label)
28
29 def train_gene_model(model, train_loader, val_loader, config):
30     """
31     Training function for gene attention model
32     """
33     # Arguments:
34     model: GenePerformer model
35     train_loader: DataLoader for training data
36     val_loader: DataLoader for validation data
37     config: Training configuration
38     """
39
40 # Loss function and optimizer
41 criterion = nn.CrossEntropyLoss()
42 optimizer = optim.AdamW(
43     model.parameters(),
44     lr=config.get('lr', 1e-4),
45     weight_decay=config.get('weight_decay', 0.01)
46 )
47
48 # Learning rate scheduler
49 scheduler = optim.lr_scheduler.CosineAnnealingLR(
50     optimizer,
51     T_max=config.get('epochs', 50)
52 )
53
54 # Training loop
55 for epoch in range(config['epochs']):
56     model train()
57     total_loss = 0
58
59     for batch_idx, (sequences, labels) in enumerate(train_loader):
60         optimizer.zero_grad()
61
62     # Forward pass
63     outputs = model(sequences)
64     loss = criterion outputs.view(-1, outputs.size(-1)),
65                   labels.view(-1))
66
67     # Backward pass
68     loss backward()
69
70     # Gradient clipping
71     torch.nn.utils clipGradNorm_ (model.parameters(), 1.0)
72
73
```
```python
optimizer.step()

total_loss += loss.item()

if batch_idx % 100 == 0:
    print(f"Epoch {epoch}, Batch {batch_idx}, Loss: {loss.item()}
) : .4f}")

# Validation
model.eval()
val_loss = 0
correct = 0
total = 0

with torch.noGrad():
    for sequences, labels in val_loader:
        outputs = model(sequences)
        loss = criterion outputs.view(-1, outputs.size(-1)),
        labels.view(-1))
        val_loss += loss.item()

# Calculate accuracy
_, predicted = outputs.max(-1)
total += labels.numel()
correct += predicted.eq labels).sum().item()

avg_train_loss = total_loss / len(train_loader)
avg_val_loss = val_loss / len(val_loader)
accuracy = 100. * correct / total

print(f"\nEpoch {epoch} Summary:")
print(f"Train Loss: {avg_train_loss:.4f}")
print(f"Val Loss: {avg_val_loss:.4f}")
print(f"Val Accuracy: {accuracy:.2f}%")

# Update learning rate
scheduler.step()

print("Training complete!")

# Example of creating and training the model
def main():
    # Configuration
    config = {
        'num_genes': 20000,  # Human genome has ~20,000 protein-coding genes
        'dim': 256,
        'depth': 8,
        'heads': 8,
        'dim_head': 64,
        'random_features': 512,
        'lr': 1e-4,
        'epochs': 50,
```
```python
126         'batch_size': 32
127     }
128
129     # Create model
130     model = create gene attention model(config)
131
132     # Create synthetic dataset (in practice, use real gene data)
133     num Samples = 10000
134     max_seq_len = 100
135
136     # Generate random gene sequences
137     sequences = [
138         np.randomondeint(0, config['num genes'],
139                         np.randomondeint(50, max_seq_len)). tolist()
140         for _ in range(num Samples)
141     ]
142
143     # Generate random labels (e.g., pathway membership)
144     labels = np.randomondeint(0, 10, num Samples) # 10 different
145     pathways
146
147     # Split into train/val
148     split_idx = int(0.8 * num Samples)
149     train_dataset = GeneDataset(sequences[:split_idx], labels[:split_idx])
150     val_dataset = GeneDataset(sequences[split_idx:], labels[split_idx:])
151
152     train_loader = DataLoader(train_dataset, batch_size = config['batch_size'],
153                             shuffle = True)
154     val_loader = DataLoader(val_dataset, batch_size = config['batch_size'])
155
156     # Train the model
157     train gene model(model, train_loader, val_loader, config)
158
159     # Save the model
160     torch.save(model.state_dict(), 'gene performer model. pth')
161     print("Model saved!")
162
163     if __name__ == "__main__":
164         main()
```

<caption>Listing 2: Training Loop for Gene Function Prediction</caption>

# 6 Biological Applications

## 6.1 Gene-Gene Interaction Networks

Performer attention enables the analysis of large gene interaction networks by:

1. **Scalability**: Handling thousands of genes simultaneously
2. Attention Weights as Interactions: The attention matrix approximates gene-gene interaction strengths

3. Pathway Analysis: Identifying genes that co-attend to each other in biological pathways

## 6.2 Single-Cell RNA-Seq Analysis

For single-cell RNA-seq data with *N* cells and *G* genes:

* Normal attention: $O(N^2G)$ - impractical for $N > 10,000$ cells

* Performer attention: $O(NmG)$ where $m \approx 256 - 512$

* Enables analysis of large-scale single-cell datasets

## 6.3 Protein Sequence Analysis

Protein sequences can be very long (up to 35,000 amino acids for Titin):

* Normal attention fails due to quadratic complexity

* Performer attention scales linearly with sequence length

* Enables whole-protein sequence analysis

# 7 Advanced Topics

## 7.1 Different Kernel Functions

<table><caption>Table 4: Kernel functions for Performer attention</caption><thead><tr><td>Kernel</td><td>Random Features</td><td>Properties</td></tr></thead><tbody><tr><td>Softmax</td><td>$\phi(x) = \exp(Wx - \|x\|^2/2)$</td><td>Matches standard attention</td></tr><tr><td>ReLU</td><td>$\phi(x) = \max(0, Wx)$</td><td>Simpler, faster</td></tr><tr><td>Trigonometric</td><td>$\phi(x) = [\sin(Wx), \cos(Wx)]$</td><td>Theoretical guarantees</td></tr></tbody></table>

## 7.2 Hyperparameter Selection

* **Random features (m):** Typically 256-1024, trade-off between accuracy and efficiency

* **Number of heads:** 4-16, depends on task complexity

* **Dimension per head:** Usually 32-128

* **Kernel type:** 'softmax' for exact approximation, 'relu' for speed
# 8 Conclusion

The Performer attention mechanism represents a significant advance in scalable attention architectures. By reformulating attention as a kernel method and using random feature approximations, it achieves linear time and memory complexity while maintaining competitive performance with standard attention.

For biological applications, particularly in genomics, this enables:

* Analysis of genome-scale datasets

* Large-scale single-cell RNA-seq analysis

The provided PyTorch implementation offers a practical starting point for researchers and practitioners working with large biological sequences. The modular design allows easy integration into existing pipelines and adaptation to specific biological tasks.

## 8.1 Future Directions

1. **Adaptive random features**: Learning the projection matrix instead of random initialization

2. **Sparse attention patterns**: Combining Performer with sparse attention for even greater efficiency

3. **Biological priors**: Incorporating domain knowledge into attention mechanisms

4. **Multimodal integration**: Combining gene expression with other omics data

# Acknowledgments

The Performer attention architecture, proposed by Choromanski et al. in *Rethinking Attention with Performers* (ICLR 2021), introduces a linear-complexity alternative to standard self-attention. This document is designed for *educational and tutorial purposes*, providing a deep dive into its mathematical foundations via practical small example.” This document provides a pedagogical breakdown of those concepts and and its application to long-range sequence modeling.

# References

1. Vaswani, A., et al. (2017). Attention is all you need. NeurIPS.

2. Choromanski, K., et al. (2021). Rethinking attention with performers. ICLR.
# A Appendix: Mathematical Derivations

## A.1 Softmax Kernel Derivation

The softmax kernel is defined as:

$$K_{\text{softmax}}(x, y) = \exp(x^T y) \qquad (14)$$

We can rewrite this using the identity:

$$\exp(x^Ty) = \exp\left(\frac{\|x\|^2 + \|y\|^2 - \|x - y\|^2}{2}\right) \qquad (15)$$

$$= \exp\left(\frac{\|x\|^2}{2}\right) \exp\left(\frac{\|y\|^2}{2}\right) \exp\left(-\frac{\|x - y\|^2}{2}\right) \qquad (16)$$

The Gaussian kernel $\exp(-\|x - y\|^2/2)$ can be approximated using random Fourier features.

## A.2 Random Feature Maps for Gaussian Kernel

For the Gaussian kernel $K(x, y) = \exp(-\|x - y\|^2/(2\sigma^2))$, we have:

$$K(x, y) = \mathbb{E}_{w \sim \mathcal{N}(0, I)}[\cos(w^T(x - y))] \qquad (17)$$

This leads to the random feature map:

$$\phi(x) = \frac{1}{\sqrt{m}}[\cos(w_1^T x), \sin(w_1^T x), \dots, \cos(w_m^T x), \sin(w_m^T x)] \qquad (18)$$