LLM Inference Engine (chapter 6): Transformer Architecture From Scratch – Next Token Prediction

Continue the work from LLM Inference Engine (chapter 5): Transformer Architecture From Scratch – Feed Forward Sub-Layer, here we learn how to transform the hidden state to a token. This process is called Next Token Prediction and this explains the token-by-token generating behaviour we observed when using LLM-powered chatbots such as ChatGPT, Claude or Gemini, etc.

1. Next Transformer Decoder Blocks

Given that we have already built our first Transformer Decoder block in Chapter 4 and Chapter 5, the next step is to clone it into multiple Decoder blocks and connect them in a chain. The output intermediate hidden state of each block serves as the input to the next block. The total number of Decoder blocks is specified by the block_count GGUF metadata field. For example, Llama 3.2 1B uses 16 Decoder blocks, while Llama 3.2 3B uses 28.

Pseudocode:

# Number of Transformer Decoder blocks
num_blocks = gguf_metadata["block_count"]
# Initial hidden state from the input embeddings
hidden_state = input_embeddings
# Pass hidden state through each Decoder block
for i in range(num_blocks):
# Retrieve the weights belonging to this block
block_weights = load_block_weights(i)
# Process through attention and feed-forward sub-layers
hidden_state = transformer_decoder_block(
hidden_state,
block_weights
)
# Final hidden state after all Decoder blocks
final_hidden_state = hidden_state

The last block’s output is called the Final Hidden State. This Final Hidden State is used as input of Next Token Prediction.

Although all Transformer Decoder blocks share the same architecture, each block has its own set of learned weights (tensors). GGUF distinguishes these tensors using a block index embedded in their names. For example, consider the attention query projection (Q) weights in two different Decoder blocks:

  • blk.0.attn_q.weight: Query projection weights belonging to Decoder block 0.
  • blk.1.attn_q.weight: Query projection weights belonging to Decoder block 1.
  • blk.2.attn_q.weight: Query projection weights belonging to Decoder block 2.

The naming convention follows the pattern blk.{index}.{tensor_name}, where {index} identifies the Decoder block and {tensor_name} identifies the specific tensor within that block. The same convention applies to other components, including attention key, value and output projections, as well as feed-forward network weights. For example:

  • blk.0.ffn_gate.weight
  • blk.0.ffn_up.weight
  • blk.0.ffn_down.weight

These tensors belong to the feed-forward sub-layer of Decoder block 0, while their counterparts prefixed with blk.1 belong to Decoder block 1.

2. Next Token Prediction

After passing through all Transformer Decoder blocks, we obtain the final hidden state. However, this hidden state is not yet the predicted token. We need to transform it into a probability distribution over the model’s vocabulary to determine which token should come next.

In Llama, this process involves three main operations:

  1. Final normalization: Apply RMSNorm to normalize the final hidden state.
  2. Logits calculation: Multiply the normalized hidden state by the output projection weights (output.weight) to calculate a score (logit) for every token in the vocabulary.
  3. Token selection: Convert logits into probabilities using Softmax, then select the next token using a decoding strategy such as greedy decoding or sampling.

The output projection maps the hidden state into the vocabulary space. For example, if the model has a vocabulary of 128,256 tokens, the output projection produces 128,256 logits, one for each possible next token.

Greedy Decoding always selects the token with the highest probability. For example, if the model computes probabilities of 65% to “cat”, 20% to “dog”, and 15% to “bird”, greedy decoding will always select “cat”. This approach is deterministic: given the same input and model configuration, it generally produces the same output. However, it can make generation repetitive and less diverse.

Sampling, on the other hand, randomly selects a token according to its probability distribution. Using the same example, “cat” has a 65% chance of being selected, “dog” has a 20% chance, and “bird” has a 15% chance. Consequently, the model can produce different responses even when given the same input.

Pseudocode:

# Input:
# final_hidden_state: [10, 4096]
# Step 1: Final RMS Normalization
# Input: [10, 4096]
# Output: [10, 4096]
normalized_hidden_state = RMSNorm(
final_hidden_state,
weights=load_tensor("output_norm.weight") # [4096]
)
# Step 2: Select the last token's hidden state
# Input: [10, 4096]
# Output: [4096]
last_hidden_state = normalized_hidden_state[-1, :]
# Step 3: Output Projection
# output.weight: [128256, 4096]
# Input: [4096]
# Output: [128256]
logits = matrix_multiply(
load_tensor("output.weight"),
last_hidden_state
)
# Step 4: Softmax
# Input: [128256]
# Output: [128256]
probabilities = softmax(logits)
# Step 5: Token Selection
# Input: [128256]
# Output: [1]
next_token_id = sample(probabilities)
# Step 6: Token Decoding
# Input: [1]
# Output: Text
next_token = tokenizer.decode(next_token_id)

The model computes contextual hidden states for all input tokens, but the inference engine only needs the last token hidden state for next-token generation.

After generating the a next token, this new token will be appended to the original input (user’s prompt) to continue generating another token. This loop runs until the model generates an EOS_TOKEN, signifying that the generation is complete. This loop pseudocode looks like so:

while not stop_generation:
# Predict the next token
next_token_id = predict_next_token(final_hidden_state)
# Append the predicted token
input_tokens.append(next_token_id)
# Stop if the end-of-sequence token is generated
if next_token_id == EOS_TOKEN:
break
# Process the new token to predict another token
final_hidden_state = run_transformer(input_tokens)

3. KV Caches

As we observe in the previous pseudocode, run_transformer reprocesses the input multiple times. This can hurt performance because the model repeatedly computes Attention Scores matrix for tokens that have already been processed. This is why KV Caches was proposed to improve model performence.

The key mathematical observation behind KV caching is that when a causal mask is used, the attention output of a token is independent of the attention outputs of future tokens and does not require the query vectors of previous tokens. Researchers can therefore calculate the attention output of a newly generated token without recalculating attention for previous tokens.

For example, when the token 11th is generated, model can calculate the 11th attention scores vector by below formula:

O11=softmax(Q11K1:11Tdk)V1:11\boxed{ O_{11} = softmax\left( \frac{Q_{11}K_{1:11}^{T}}{\sqrt{d_k}} \right)V_{1:11} }

Note that the K and V matrices still preserve the vectors for tokens 1 through 10; they are not discarded or recalculated. However, only the 11th vector of Q is required. This means that, when calculating the 11th row of the attention scores matrix, we only need to compute Q, K, and V for the 11th token while caching the K and V vectors from the previous 10 tokens. This is where the KV cache comes into play. Consequently:

  • K and V contains the cached values of tokens 1–10 plus the new value.
  • Q contains only the query vector of the new token.

Pseudocode:

# Convert new token into embedding
hidden_states = embedding(next_token)
for layer in decoder_layers:
# Normalize input
x = RMSNorm(hidden_states)
# Calculate Q, K, V ONLY for the new token
Q = x @ WQ
K = x @ WK
V = x @ WV
# Append new K and V to existing cache
layer.K_cache.append(K)
layer.V_cache.append(V)
# Retrieve all cached K and V
K_all = layer.K_cache
V_all = layer.V_cache
# Calculate attention for the new token only
attention_output = softmax(
(Q @ transpose(K_all)) / sqrt(head_dim)
) @ V_all
# Attention output projection and residual
hidden_states = hidden_states + WO(attention_output)
# Feed-forward network
x = RMSNorm(hidden_states)
ffn_output = SwiGLU(x, W_gate, W_up, W_down)
hidden_states = hidden_states + ffn_output
# Predict the next token
logits = LM_Head(RMSNorm(hidden_states))
next_token = sample(logits[-1])

Because the decoder only needs the hidden state of the last token to predict the next token, we use the computed hidden state of the new token to continue generating another token. The generation loop runs with KV caches until it reaches the EOS token, as before.

4. Next Step

So far, we have gone through the Inference Engine using Llama 3 as an example. In the next steps, we will learn how to transform a Transformer into a web service like ChatGPT, Gemini, or Claude.

Subscribe:

…

One thought on “LLM Inference Engine (chapter 6): Transformer Architecture From Scratch – Next Token Prediction”

Leave a Reply