> For the complete documentation index, see [llms.txt](https://www.pranaypourkar.co.in/the-programmers-guide/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.pranaypourkar.co.in/the-programmers-guide/ai/generative-ai/large-language-models-llm/llm-foundations/transformer/why-transformer-complexity-is-o-n.md). # Why Transformer Complexity is O(n²) ## About When we say: > Transformer complexity is O(n²) We are specifically referring to the **self-attention mechanism**. Where: * `n` = number of tokens in the sequence ## What Self-Attention Actually Does ? In a Transformer, every token looks at **every other token** in the sequence. If your input has: ``` n tokens ``` Each token computes attention with: ``` n tokens (including itself) ``` So total attention comparisons: ``` n × n = n² ``` That’s where the quadratic complexity comes from. ### Visual Example Suppose we have 4 tokens: ``` ["The", "model", "predicts", "tokens"] ``` Attention matrix: | | The | model | predicts | tokens | | -------- | --- | ----- | -------- | ------ | | The | ✔ | ✔ | ✔ | ✔ | | model | ✔ | ✔ | ✔ | ✔ | | predicts | ✔ | ✔ | ✔ | ✔ | | tokens | ✔ | ✔ | ✔ | ✔ | Each token interacts with all 4 tokens. Total interactions: ``` 4 × 4 = 16 ``` If tokens double to 8: ``` 8 × 8 = 64 ``` If tokens become 1000: ``` 1000 × 1000 = 1,000,000 interactions ``` This grows very fast. ### Mathematical Breakdown Self-attention involves these steps: 1. Compute Query (Q), Key (K), Value (V) matrices 2. Compute attention scores: ``` Attention(Q, K) = Q × Kᵀ ``` If: * Q is n × d * K is n × d Then: ``` Q × Kᵀ → n × n matrix ``` This produces the attention matrix of size: ``` n² ``` Then: * Softmax is applied to this matrix * Weighted values are computed The dominant cost is creating that n × n matrix. ## Why Tokens Directly Affect Complexity ? Since: ``` n = number of tokens ``` If tokenization creates: * Shorter sequences → smaller n → cheaper computation * Longer sequences → larger n → expensive computation This is why: Character-level tokenization (long sequences)\ is computationally expensive. Subword tokenization (shorter sequences)\ is more efficient. ### Does O(n²) Limit Tokens? Yes. Directly. This quadratic scaling is the main reason why context windows cannot grow infinitely. Let’s see what happens. #### Example: Doubling Tokens If we increase tokens from: ``` 4,000 → 8,000 ``` Computation increases by: ``` (8000²) / (4000²) = 4× ``` Doubling tokens = 4× compute cost. If we go from: ``` 8,000 → 32,000 ``` That is: ``` (32000²) / (8000²) = 16× increase ``` This becomes extremely expensive in: * Memory * GPU usage * Latency * Energy cost ### Memory Impact The attention matrix size is: ``` n × n ``` If n = 100,000 tokens: ``` 100,000 × 100,000 = 10 billion entries ``` That is enormous memory usage. This is why: Context window expansion is expensive. ### Real Implication When a model says: * 8K context * 32K context * 128K context It is not just a configuration change. It significantly increases: * Training cost * Inference cost * Memory usage This is directly caused by O(n²) attention. ## Why Tokenization Matters Here ? Let’s compare: Sentence length = 200 characters Character-level tokens:\ 200 tokens Subword tokens:\ \~50 tokens Attention cost comparison: Character: ``` 200² = 40,000 ``` Subword: ``` 50² = 2,500 ``` That’s 16× cheaper. This is one of the strongest reasons modern LLMs use subword tokenization. ## Not All Transformer Cost is O(n²) Total transformer cost includes: * Self-attention: O(n²) * Feed-forward layers: O(n) But attention dominates at large sequence sizes. So we simplify complexity to: ``` O(n²) ``` Because that is the bottleneck. ## Does This Mean Tokens Are Limited ? Yes - practically. Because: * Memory is finite * GPUs are finite * Cost is finite This leads to: Context window limits. Common context sizes: * 4K tokens * 8K tokens * 32K tokens * 128K tokens * 200K+ tokens (advanced models) But increasing this further becomes exponentially expensive. ## How Modern Research Tries to Solve This ? Researchers are working on: * Sparse attention * Sliding window attention * Linear attention * Memory-compressed attention * Chunked processing These aim to reduce complexity to: ``` O(n) ``` Or near-linear scaling. But classical full self-attention remains O(n²). --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://www.pranaypourkar.co.in/the-programmers-guide/ai/generative-ai/large-language-models-llm/llm-foundations/transformer/why-transformer-complexity-is-o-n.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.