Optimizing Mixture of Block Attention Guangxuan Xiao, Junxian Guo, Kasra Mazaheri, Song Han Abstract Mixture of Block Attention (MoBA) ( 23 ) is a promising building block for efficiently processing long contexts in LLMs by enabling queries to sparsely attend to a small subset of key-value blocks, drastically reducing computational cost. However, the design principles governing MoBA’s performance are poorly understood, and it lacks an efficient GPU implementation, hindering its practical adoption. In this paper, we first develop a statistical model to analyze MoBA’s underlying mechanics. Our model reveals that performance critically depends on the router’s ability to accurately distinguish relevant from irrelevant blocks based on query-key affinities. We derive a signal-to-noise ratio that formally connects architectural parameters to this retrieval accuracy. Guided by our analysis, we identify two key pathways for improvement: using smaller block sizes, and applying a short convolution on keys to cluster relevant signals, which enhances routing accuracy. While theoretically better, small block sizes are inefficient on GPUs. To bridge this gap, we introduce FlashMoBA , a hardware-aware CUDA kernel that enables efficient MoBA execution even with the small block sizes our theory recommends. We validate our insights by training LLMs from scratch, showing that our improved MoBA models match the performance of dense attention baselines. FlashMoBA achieves up to 14.7× speedup over FlashAttention-2 for small blocks, making our theoretically-grounded improvements practical. 1 Introduction Large Language Models (LLMs) ( 11 ; 26 ) are expanding into multimodal domains like video understanding ( 20 ; 37 ) and video generation ( 17 ) , requiring the ability to handle exceptionally long contexts. This vision is bottlenecked by the self-attention mechanism ( 36 ) , whose quadratic computational cost makes processing long sequences costly. Sparse attention ( 44 ; 12 ; 40 ) aims to solve this by focusing computation only on important regions. Among these methods, Mixture of Block Attention (MoBA) ( 23 ) is a promising approach where a learned router directs each query to a small subset of key-value blocks, reducing complexity to near-linear. However, MoBA’s success is hindered by two critical issues: the design principles governing its performance are poorly understood, and it lacks an efficient GPU implementation, especially for small block sizes. This raises a key question: how does the router reliably select a handful of correct blocks from thousands of candidates—a ”needle-in-a-haystack” problem—and how can we make this process fast on hardware? To answer this, we develop a statistical model of MoBA’s mechanics. Our analysis reveals that retrieval accuracy is governed by a signal-to-noise ratio (SNR) that directly links architectural parameters to performance: \text{SNR}\propto\sqrt{\frac{d}{B}} where d is the head dimension and B is the block size. This insight yields two key design principles: (1) optimizing the head-dimension-to-block-size ratio ( d/B ) , which we validate by systematically varying B while holding d constant, and (2) applying a short convolution on keys to better cluster relevant signals for the router. Figure 1: FlashMoBA forward pass in two stages. MoBA splits keys and values into blocks; each query scores centroids of key-blocks \tilde{\mathbf{K}} and attends only to its top- k blocks (plus causally to its own block). 1) Tiled Top- k Selection: a fused kernel streams tiles of \mathbf{Q} and \tilde{\mathbf{K}} to emit a sparse routing mask without materializing the full matrix. 2) Dense Computation: for each selected key block, queries are gathered into on-chip SRAM, computed densely with FlashAttention-2 logic, then scattered back. This gather-and-densify strategy coalesces memory, maximizes hardware utilization and makes small-block MoBA fast on GPUs (See Section 4 for more details). While our theory advocates for small block sizes, they are notoriously inefficient on GPUs. To solve this, we introduce FlashMoBA , a hardware-aware CUDA kernel that makes these theoretically optimal configurations practical. By adapting techniques from FlashAttention ( 9 ; 10 ) and adding novel optimizations for block-sparsity, FlashMoBA achieves significant speedups. We validate our approach by training LLMs from scratch, demonstrating that our improved MoBA models match the performance of dense attention baselines. Our contributions are threefold: • A statistical model of MoBA that connects architectural parameters ( d,B ) to router accuracy via a signal-to-noise ratio, providing a principled guide for design. • Two design principles for improving MoBA validated through controlled experiments : optimizing the d/B ratio (by varying block size B while controlling for model capacity) and applying a convolution on keys to improve signal clustering. • FlashMoBA , a hardware-aware CUDA kernel that makes theoretically optimal small block sizes practical, achieving up to 14.7× speedup on GPUs. 2 Preliminaries We briefly review MoBA ( 23 ) . Given a sequence of N key tokens, MoBA partitions them into n=N/B blocks of size B . For each query \mathbf{q} , instead of attending to all N keys and values, MoBA selects only the top k most relevant blocks. The block selection uses a gating mechanism. For block i with keys \mathbf{K}_{i}\in\mathbb{R}^{B\times d} , the relevance score is computed as s_{i}=\mathbf{q}^{\top}\cdot\mathbf{\tilde{k}}_{i} where \mathbf{\tilde{k}}_{i}=\frac{1}{B}\sum_{\mathbf{k}\in\mathbf{K}_{i}}\mathbf{k} represents the centroid —i.e., mean pooling of the block \mathbf{K}_{i} . The top- k blocks with highest scores are selected, and attention is computed only over their tokens: \text{MoBA}(\mathbf{q},\mathbf{K},\mathbf{V})=\text{softmax}(\mathbf{q}\mathbf{K}_{\mathcal{S}}^{\top}/\sqrt{d})\mathbf{V}_{\mathcal{S}}, where \mathcal{S} contains all tokens from selected blocks. To preserve causality, blocks containing future tokens are masked during selection. Additionally, each query always attends to its current block with causal masking. This reduces complexity from O(N^{2}) to O(N\cdot kB) when k\ll n . Our experiments systematically explore configurations with B\in\{512,256,128\} and corresponding k\in\{2,4,8\} to maintain constant sparsity of 7/8 when N=8192 . To encourage within-block clustering, we optionally apply a short depthwise causal convolution on keys ( 41 ) (kernel size 3 or 5); details are provided in Appendix B . 3 A Statistical Model of MoBA For MoBA to be effective, its router must select the correct key-value block for a given query. This is challenging because the router scores a block using its centroid (the average of all its keys), a process that risks drowning out the signal from a single relevant token. To understand how MoBA succeeds, we developed a statistical model of its block selection mechanism. 3.1 Modeling the Block Selection Challenge We model the router’s task by treating the dot products between a query \mathbf{q} and the keys as random variables. We assume that for a given query, ”signal” keys ( \mathbf{k}^{*} ) it is seeking have a higher expected dot product than irrelevant ”noise” keys ( \mathbf{k} ). Let \mu_{\text{signal}}=\mathbb{E}[\mathbf{q}^{\top}\mathbf{k}^{*}] and \mu_{\text{noise}}=\mathbb{E}[\mathbf{q}^{\top}\mathbf{k}] . The fundamental separation between signal and noise is the difference \Delta\mu=\mu_{\text{signal}}-\mu_{\text{noise}} . For a router to function, this separation must be positive ( \Delta\mu>0 ). The router scores each block j by computing the dot product with the block’s centroid, s_{j}=\mathbf{q}^{\top}\mathbf{\tilde{k}}_{j} , where \mathbf{\tilde{k}}_{j}=\frac{1}{B}\sum_{\mathbf{k}\in\text{block}_{j}}\mathbf{k} . The key question is whether the score of the signal-containing block ( s_{j^{*}} ) will reliably be higher than the score of any noise block ( s_{j} ). 3.2 Signal-to-Noise Ratio (SNR) Analysis To quantify when block selection succeeds, we analyze the signal-to-noise ratio (SNR) of the router’s scores. We consider the difference in scores, D=s_{j^{*}}-s_{j} , between the signal block j^{*} and a pure noise block j . The expected value of this difference represents the ”signal,” while its standard deviation represents the ”noise.” Through statistical analysis (see Appendix A ), we find: \displaystyle\mathbb{E}[D] \displaystyle=\frac{\Delta\mu_{\text{eff}}}{B} (1) \displaystyle\text{Var}(D) \displaystyle\approx\frac{2}{dB}\quad\text{(for normalized vectors)} (2) Here, \Delta\mu_{\text{eff}} is the effective signal separation . If m related signal tokens are clustered within the target block, this separation is amplified: \Delta\mu_{\text{eff}}=\Delta\mu+(m-1)(\mu_{\text{cluster}}-\mu_{\text{noise}}) , where \mu_{\text{cluster}} is the average affinity between the query and other clustered signal tokens. The SNR is the ratio of the expected outcome to its standard deviation, which is our central finding: \text{SNR}=\frac{\mathbb{E}[D]}{\sqrt{\text{Var}(D)}}=\Delta\mu_{\text{eff}}\sqrt{\frac{d}{2B}} (3) The probability of a retrieval failure—a noise block outranking the signal block—decreases exponentially as the SNR increases: p_{\text{fail}}=\Phi(-\text{SNR}) , where \Phi is the standard normal CDF. For reliable top- k retrieval in a long context with thousands of blocks, a high SNR is essential. 3.3 Architectural Insights from the SNR Model The SNR formula provides two clear and actionable principles for designing effective MoBA architectures: 1. The d/B ratio is the key. The SNR is proportional to \sqrt{d/B} . This ratio emerges as the most critical factor governing the router’s retrieval capability. This insight suggests two avenues for improvement: increasing the head dimension d or decreasing the block size B . However, the head dimension d is a confounding variable ; increasing it not only improves the theoretical SNR but also increases the model’s parameters and computational cost (FLOPs), adding capacity that makes a controlled comparison difficult. Therefore, to isolate and empirically validate the d/B ratio’s impact on retrieval accuracy alone, our study fixes d (controlling for model capacity) and systematically varies B . Halving the block size improves the SNR by a factor of \sqrt{2} , making it easier for the router to find the signal. 2. Within-block clustering is a performance multiplier. When semantically related tokens are grouped together in a block—a behavior encouraged by token-level key convolution ( 41 ) during training—the effective signal \Delta\mu_{\text{eff}} increases via larger m and \mu_{\text{cluster}} , significantly boosting the SNR. These principles form the theoretical foundation for our architectural improvements, which we validate systematically in Section 5 . 4 FlashMoBA: An Optimized Kernel for Small-Block MoBA Our theoretical model shows that smaller block sizes yield significant quality gains, but a naive GPU implementation is inefficient. The original MoBA implementation released by 23 , when configured with small blocks, suffers from performance bottlenecks that negate the computational savings from sparsity, resulting in slower execution than dense attention. We introduce FlashMoBA , an hardware-aware CUDA kernel designed to make small-block MoBA practical and fast. 4.1 Performance Challenges with Small Blocks Small block sizes introduce several critical performance challenges that must be addressed for practical deployment. First, inefficient memory access occurs when gathering sparse, non-contiguous key-value blocks for each query, leading to uncoalesced memory reads from HBM. Second, top-k and gating overhead becomes problematic as smaller block sizes B increase the number of blocks ( n=N/B ) that the router must score. The original implementation materializes a large N\times n score matrix, incurring substantial memory overheads. Finally, low GPU occupancy results from the reduced work per block and the overhead of launching many independent kernels, leading to poor parallelism and low hardware utilization. 4.2 FlashMoBA Kernel Design To overcome these challenges, FlashMoBA employs three fused kernels that minimize HBM round-trips and aligns computation with the GPU architecture, as depicted in Figure 1 . 1. Tiled Top-K Selection The top-k selection process is a primary bottleneck in the original MoBA implementation 23 , which materializes a full score matrix and processes batched sequences serially. We replace this with Flash TopK (Step 1 in Figure 1 ), a highly optimized three-stage pipeline of fused kernels. First, a Triton kernel computes key-block centroids, producing a much smaller matrix \mathbf{\tilde{K}} . Second, a tiled kernel inspired by FlashAttention-2 finds the top-k key-blocks for each query by computing scores between \mathbf{Q} and \mathbf{\tilde{K}} without ever materializing the full score matrix to HBM , as summarized in Algorithm 3 . Finally, an efficient epilogue reformats the query-centric indices into a key-block-centric varlen layout for the main attention pass. This entire pipeline is fully parallelized across batches and heads, eliminating the original performance bottleneck. The detailed breakdown of all three stages is provided in Appendix C.1 . 2. Forward Pass with Gather-and-Densify To handle MoBA’s irregular sparsity, our forward kernel uses a ”gather-and-densify” strategy based on a two-level blocking mechanism, detailed in Algorithm 1 . We distinguish between two types of blocks: • Logical Blocks: Large, contiguous blocks of queries ( \mathbf{Q_{i}} ) and keys ( \mathbf{K_{j}} ) that the kernel iterates over in its outer loops. A logical key block matches a MoBA key block. • Physical Blocks: Smaller tiles (e.g., 64\times 64 or 128\times 128 ) loaded into SRAM for matrix multiplication. Their optimal size depends on GPU architecture and head dimension. The kernel assigns a logical query block \mathbf{Q_{i}} to each thread block, iterating through all logical key blocks \mathbf{K_{j}} . For each pair, it uses varlen indices to find relevant queries. This subset is batched into dense physical blocks: a physical block of queries is gathered from HBM into a dense SRAM buffer for computation. This two-level approach is key, as caching the queries in SRAM allows reuse across all physical tiles of the logical key block, amortizing costly irregular memory access with efficient dense GEMMs. Algorithm 1 FlashMoBA Forward Pass 1: Matrices \mathbf{Q,K,V}\in\mathbb{R}^{N\times d} in HBM. Varlen indices A,\text{Offset},C . Logical block sizes B_{q},B . Physical tile sizes B_{r},B_{c} . 2: Divide \mathbf{Q} into T_{q}=\lceil\frac{N}{B_{q}}\rceil logical blocks \mathbf{Q}_{i} of size B_{q}\times d . 3: Divide \mathbf{K},\mathbf{V} into T_{k}=\lceil\frac{N}{B}\rceil logical blocks \mathbf{K}_{j},\mathbf{V}_{j} of size B\times d . 4: Initialize output matrix \mathbf{O}\in\mathbb{R}^{N\times d} , temporary output matrix \mathbf{O_{tmp}}\in\mathbb{R}^{N\times d} and logsumexp vector L\in\mathbb{R}^{N} in HBM. 5: for 0\leq i0 . To account for semantic clustering, let m denote the number of keys in the signal block with elevated similarity \mu_{\text{cluster}} where \mu_{\text{noise}}<\mu_{\text{cluster}}\leq\mu_{\text{signal}} . The expected scores become: \displaystyle\mathbb{E}[s_{j^{*}}] \displaystyle=\frac{1}{B}[\mu_{\text{signal}}+(m-1)\mu_{\text{cluster}}+(B-m)\mu_{\text{noise}}] (6) \displaystyle\mathbb{E}[s_{j}] \displaystyle=\mu_{\text{noise}}\quad\text{for }j\neq j^{*} (7) The expected advantage of the signal block is: \mathbb{E}[s_{j^{*}}]-\mathbb{E}[s_{j}]=\frac{\Delta\mu+(m-1)(\mu_{\text{cluster}}-\mu_{\text{noise}})}{B}=\frac{\Delta\mu_{\text{eff}}}{B} where \Delta\mu_{\text{eff}}=\Delta\mu+(m-1)(\mu_{\text{cluster}}-\mu_{\text{noise}}) is the effective similarity gap. A.3 Variance Analysis Assuming independent dot products with variance \sigma^{2}\approx 1/d for normalized vectors in high dimensions, the score difference D=s_{j^{*}}-s_{j} between signal and noise blocks satisfies: \displaystyle\mathbb{E}[D] \displaystyle=\frac{\Delta\mu_{\text{eff}}}{B} (8) \displaystyle\text{Var}(D) \displaystyle=\text{Var}(s_{j^{*}})+\text{Var}(s_{j})=\frac{\sigma^{2}}{B}+\frac{\sigma^{2}}{B}=\frac{2\sigma^{2}}{B} (9) A.4 Retrieval Probability Under the Central Limit Theorem for large B , D\sim\mathcal{N}(\Delta\mu_{\text{eff}}/B,2\sigma^{2}/B) . The probability that a noise block outranks the signal block is: \displaystyle p=P(D<0) \displaystyle=\Phi\left(\frac{0-\Delta\mu_{\text{eff}}/B}{\sqrt{2\sigma^{2}/B}}\right) (10) \displaystyle=\Phi\left(-\frac{\Delta\mu_{\text{eff}}}{\sigma\sqrt{2B}}\right) (11) \displaystyle=\Phi\left(-\Delta\mu_{\text{eff}}\sqrt{\frac{d}{2B}}\right) (12) This yields the signal-to-noise ratio: \text{SNR}=\Delta\mu_{\text{eff}}\sqrt{\frac{d}{2B}} For reliable top- k retrieval with n blocks, we need p\Phi^{-1}(1-k/n) . Appendix B Key Convolution Design To encourage within-block clustering of semantically related tokens, we apply a short convolution operator to the key representations. This section details the specific design choices. B.1 Architecture We use a depthwise causal 1-D convolution applied to token-level keys before they are used for routing and attention computation. The key design choices are: Depthwise convolution. The convolution is depthwise-separable with groups=hidden_size , meaning each channel (dimension) of the key vector is filtered independently. This reduces parameters while maintaining expressiveness across all dimensions. Causal structure. The convolution is causal (left-padded), ensuring that the representation at position t only depends on positions \{t-W+1,\ldots,t\} where W is the kernel width. This preserves the autoregressive property required for language modeling. Kernel size. We experiment with kernel widths W\in\{3,5\} , denoted as kconv3 and kconv5 respectively in our experiments. These short receptive fields allow local signal diffusion without excessive computational overhead. Activation and residual. Following recent work on efficient linear transformers ( 41 ) , we apply: • SiLU activation : \sigma(x)=x\cdot\text{sigmoid}(x) applied element-wise after convolution • Residual connection : The original key is added back to the convolved output Formally, for a key vector \mathbf{k}_{t}\in\mathbb{R}^{d} at position t , the transformed key is: \mathbf{k}^{\prime}_{t}=\mathbf{k}_{t}+\text{SiLU}\left(\sum_{\ell=0}^{W-1}\mathbf{W}_{\ell}\odot\mathbf{k}_{t-\ell}\right) where \mathbf{W}_{\ell}\in\mathbb{R}^{d} are the learnable kernel weights for each lag \ell , and \odot denotes element-wise multiplication (due to depthwise structure). B.2 Effect on Routing The key convolution is applied before block centroid computation. For block j , the centroid used for routing becomes: \mathbf{\tilde{k}}_{j}=\frac{1}{B}\sum_{\mathbf{k}^{\prime}\in\mathbf{K}^{\prime}_{j}}\mathbf{k}^{\prime} where \mathbf{K}^{\prime}_{j} contains the convolved keys in block j . During training, this design encourages gradient flow between neighboring tokens within a block. When the router learns to select a block containing relevant information, the gradients backpropagate through the convolution, implicitly encouraging nearby tokens to align with the query direction. This increases the number of related tokens m within selected blocks and raises their average affinity \mu_{\text{cluster}} , thereby amplifying \Delta\mu_{\text{eff}} according to our statistical model (Section 3 ). Appendix C Kernel Implementation Details C.1 FlashMoBA Top-K Selection and Index Reformatting Our algorithm for top-k selection and index reformatting, which we name Flash TopK, is divided into three logical stages, each implemented as a fused kernel to minimize HBM data transfers. 1. Computation of Block Centroids. We first compute key-block centroids using a fused Triton kernel (Algorithm 2 ). This step produces a centroid matrix \mathbf{\tilde{K}} that is B times smaller than the original key matrix \mathbf{K} , significantly reducing subsequent HBM accesses. Algorithm 2 Fused Key-Block Centroid Computation 1: Key matrix \mathbf{K}\in\mathbb{R}^{N\times d} , block size B . 2: Partition \mathbf{K} into blocks \{\mathbf{K}_{j}\}_{j=0}^{T_{k}-1} , where T_{k}=\lceil N/B\rceil . 3: Initialize centroid matrix \mathbf{\tilde{K}}\in\mathbb{R}^{T_{k}\times d} . 4: for j\in[0,T_{k}-1] do in parallel 5: \mathbf{\tilde{K}}[j,:]\leftarrow\frac{1}{|\mathbf{K}_{j}|}\sum_{\mathbf{v}\in\mathbf{K}_{j}}\mathbf{v} \triangleright Compute mean of each block 6: end for 2. Fused Top-K Selection. With the block centroids pre-computed, a second fused kernel identifies the top-k blocks for each query, adopting the tiling strategy from FlashAttention-2. For each block of queries loaded into SRAM, the kernel iterates through the centroid matrix \mathbf{\tilde{K}} in chunks. It computes gating scores and maintains a running list of the top-k indices and their corresponding scores for each query on-chip. This update is performed with a bubble sort algorithm which is highly efficient for k\ll N , as detailed in Algorithm 3 . This process avoids materializing the full score matrix to HBM. Algorithm 3 Fused Top-K Selection 1: Matrices \mathbf{Q}\in\mathbb{R}^{N\times d} and \mathbf{\tilde{K}}\in\mathbb{R}^{\lceil\frac{N}{B}\rceil\times d} in HBM, MoBA key-block size B , MoBA top-k k , block sizes B_{c},B_{r} 2: Divide \mathbf{Q} into T_{r}=\lceil\frac{N}{B_{r}}\rceil blocks \mathbf{Q}_{i} of dimensions B_{r}\times d each, and divide \mathbf{\tilde{K}} into T_{c}=\lceil\frac{T_{k}}{B_{c}}\rceil blocks \mathbf{\tilde{K}}_{j} of dimensions B_{c}\times d each. 3: Initialize the top-k indices matrix \mathbf{I}\in\mathbb{Z}^{N\times k} in HBM. 4: for 0\leq i