## Process Diagram: Speculative Decoding and Verification Flow
### Overview
This diagram illustrates the lifecycle of a request within an LLM inference system utilizing speculative decoding. It depicts the progression from the initial prefill phase through decoding, verification of speculative tokens, and the necessary rollback mechanism when speculative tokens are rejected. The diagram tracks the state of the Key-Value (KV) cache and the token sequence across these four distinct phases.
### Components/Axes
The diagram is organized into two horizontal tiers:
1. **Top Tier (KV Cache State):** Three cylinder icons representing the state of the KV cache at different stages:
* "KV cache after prefill"
* "KV cache after decode"
* "KV cache after verify-rollback"
2. **Bottom Tier (Process Phases):** Four distinct vertical sections separated by black lines:
* **Prefill:** Initial request processing.
* **Decode:** Speculative token generation.
* **Verify:** Validation of speculative tokens.
* **Rollback:** Restoration of the sequence to the last valid state.
### Detailed Analysis
#### 1. Prefill Phase
* **Components:** A blue rectangle labeled "deterministic request" and a gray block labeled "other requests."
* **KV Cache State:** The "KV cache after prefill" cylinder is entirely blue, indicating the initial state.
#### 2. Decode Phase
* **Components:** A grid of yellow squares representing speculative tokens: $T_0, T_1', T_2', T_3'$.
* **KV Cache State:** The "KV cache after decode" cylinder is split: blue on top, yellow on the bottom, indicating the addition of speculative data.
#### 3. Verify Phase
* **Input:** A vertical column of tokens: $T_0$ (green), $T_1'$ (yellow), $T_2'$ (yellow), $T_3'$ (yellow).
* **Output:** A vertical column of tokens being validated:
* $T_1$ (green, labeled "$T_1 (=T_1')$")
* $T_2$ (cross-hatched, labeled "$T_2 (!=T_2')$")
* $T_3$ (red)
* $T_4$ (red)
* **Status Indicators:**
* $T_1$ and $T_2$ have checkmarks, labeled "accepted tokens."
* $T_3$ and $T_4$ have X-marks, labeled "rejected tokens."
* **Flow:** Arrows point from the input speculative tokens to the verified tokens, showing the comparison process.
#### 4. Rollback Phase
* **Components:** A sequence of blocks: $T_0$ (blue), $T_1$ (green), $T_2$ (cross-hatched).
* **Text Annotation:** "Sequence and KV cache restored until the final accepted token (T2)".
* **KV Cache State:** The "KV cache after verify-rollback" cylinder is split: blue on top, green on the bottom, indicating the state has been reverted to the last valid token.
### Key Observations
* **Token Mismatch:** The diagram explicitly shows a discrepancy in the verification phase. While $T_1$ matches the speculative $T_1'$, $T_2$ does not match $T_2'$ (indicated by the cross-hatching and the "$!=T_2'$" label).
* **Rejection:** The system rejects tokens $T_3$ and $T_4$ entirely.
* **State Restoration:** The "Rollback" phase demonstrates that the system does not keep the speculative tokens that were rejected. It truncates the sequence at $T_2$, ensuring the KV cache and the sequence are consistent with the ground truth.
* **Visual Coding:**
* **Blue:** Deterministic/Base state.
* **Yellow:** Speculative/Unverified state.
* **Green:** Verified/Accepted state.
* **Red:** Rejected state.
* **Cross-hatching:** Indicates a specific token ($T_2$) that was accepted but potentially differs from the speculative prediction.
### Interpretation
This diagram demonstrates the **Speculative Decoding** optimization technique. In this process, a smaller, faster model generates multiple "speculative" tokens ($T_1', T_2', T_3'$) in parallel. The larger, more accurate model then verifies these tokens in a single pass.
The diagram highlights the critical "Verify-Rollback" loop:
1. **Efficiency:** By generating multiple tokens at once, the system attempts to speed up inference.
2. **Correction:** Because speculative tokens are guesses, they are not always correct. The "Verify" phase acts as a filter.
3. **Consistency:** The "Rollback" phase is essential for correctness. It ensures that if the speculative model guesses incorrectly (as seen with $T_3$ and $T_4$), the system discards the bad data and reverts the KV cache to the last known good state ($T_2$). This prevents the model from hallucinating or continuing from an incorrect sequence.
