Course contentsShow
← Machine Learning and Deep Learning
Lesson 1197 of 3,53827. Pretrained Language Models: GPT Family and BeyondFree lesson

Sequence Length and Computational Cost

Analyzing the O(n²) attention cost and sequential generation bottleneck in autoregressive models.

Sequence Length and Computational Cost

You'll learn: Why longer sequences make autoregressive models exponentially more expensive to train and generate text.

The O(n²) Attention Problem

In autoregressive models like GPT, self-attention computes relationships between every token and every other token it can see. For a sequence of length n, that's n × n comparisons. If you double your sequence length from 512 to 1024 tokens, you quadruple the attention computation cost.

Think of it like a group conversation where everyone must shake hands with everyone they've met so far. Two people? One handshake. Four people? Six handshakes. Eight people? Twenty-eight handshakes. The growth accelerates quickly.

The Sequential Generation Bottleneck

During text generation, autoregressive models face a second challenge: they must generate tokens one at a time, in order. Each new token requires:

  1. Running the entire model forward with all previous tokens
  2. Selecting the next token
  3. Appending it to the sequence
  4. Repeating

You can't parallelize generation across tokens because token t+1 depends on token t. It's like writing an essay where you must finish sentence 1 before starting sentence 2—you can't write all sentences simultaneously.

Real-World Impact

A 2048-token sequence costs 4× more attention than a 1024-token one during training, and generating a 100-token response requires 100 sequential forward passes. This is why:

  • Long-context models are expensive
  • Real-time chat feels slower with longer conversations
  • Context window size is a key specification

Key Takeaway: Autoregressive models face O(n²) scaling in attention computation and cannot parallelize token generation, making sequence length the dominant factor in computational cost and latency.