How Sparse-K Cuts Millions of Attention Computations in llama.cpp

Source: Dev.to

What Is Attention, Anyway?

Before diving into Sparse‑K, it’s important to understand what the Attention mechanism actually does, and why it’s so computationally expensive.

When a language model receives a sentence like:

“The cat sat on the gray carpet,”

it doesn’t just read the words — it needs to understand the meaning, the relationships, and how each word connects to the others. To achieve this, every word evaluates how strongly it relates to every other word in the sentence. This creates a dense web of connections, where each token computes a score against all other tokens.

Formula:
(N) tokens → (N \times N) attention score computations.

That quadratic growth is exactly what makes Attention costly, especially for long sequences.

Why Is This Such a Performance Problem?

Because the computation scales quadratically — (O(N^{2})).
A sequence of 2048 tokens requires over 4 million score computations in a single Attention layer.

When looking deeper into these matrices, most connections don’t meaningfully contribute to the final prediction; many are weak or irrelevant. Visually, instead of a dense web where every token attends to every other token, we often only need a few meaningful connections.

So What Does Sparse‑K Actually Do?

Sparse‑K introduces a simple but powerful idea: instead of evaluating all pairwise relationships between tokens, it keeps only the top‑K most meaningful connections for each token — and ignores the rest.

• The structure of the Attention mechanism stays the same; only the amount of data processed is reduced.
• This dramatically cuts the number of computations, lowers memory pressure, and speeds up the entire inference pipeline.

From Attention Scores to a Sparse Mask

In standard Attention, after computing the similarity scores ((Q \times K)), a full matrix of values is produced. Sparse‑K adds an extra step:

1. Top‑K selection – For each token, keep only the highest‑K scores.
2. Masking – All other values are “removed” by applying a mask.
3. Negative infinity – The masked values are set to a very large negative number ((-\infty)) so they do not affect the Softmax.

As a result, Softmax and all subsequent computations are performed only on the truly relevant connections.

The image shows attention score computations between each token and all other tokens. For each token, the top‑K highest scores are highlighted.

This illustrates the final Sparse‑K attention mask after top‑K selection.

Why Are Masks the Right Solution?

Masks are already a fundamental part of the Attention mechanism. Every Transformer model relies on several types of masks, such as:

• Causal masks – prevent the model from attending to future tokens.
• Sequence separation masks – distinguish between different input segments.

Sparse‑K does not introduce a new mechanism; it integrates naturally into the existing masking system:

• Build an additional mask that represents the Top‑K selection.
• Combine it with the existing base mask.
• Use it within the same Attention routine that already exists.

This approach:

• Fits seamlessly into the current pipeline without breaking compatibility.
• Leaves the computational graph structure untouched.
• Allows reuse of highly optimized Attention implementations (e.g., Flash Attention), because those implementations already accept masks as part of their interface.

Thus, using a mask enables Sparse‑K to benefit from existing optimizations while preserving efficiency, compatibility, and maintainability.

Integration into llama.cpp

Sparse‑K is inserted directly into the Attention block, at a natural point in the computation flow:

1. Compute similarity scores (Q \times K).
2. Construct the Sparse‑K mask (top‑K selection).
3. Apply the combined mask before the remaining Attention stages.

All other parts of the model — the embedding layer, MLP computations, and multi‑head composition — remain unchanged. In this way, Sparse‑K targets the most computationally expensive part of the model while leaving the rest of the architecture intact.