## Diagram: KV Cache Workflow ### Overview The image illustrates a workflow involving a Key-Value (KV) cache through stages of prefill, decode, verify, and rollback. It shows how the cache is populated, how requests are processed, and how the system handles verification and potential rollbacks. ### Components/Axes * **Top Row:** Shows the state of the KV cache after each stage: prefill, decode, and verify-rollback. Each stage is represented by a cylinder. * KV cache after prefill * KV cache after decode * KV cache after verify-rollback * **Prefill:** Shows a "deterministic request" populating the cache, while "other requests" are also being processed. * **Decode:** Shows tokens T0, T1', T2', and T3' being decoded. * **Verify:** Shows the verification process, where tokens are compared. T1 is equal to T1', and T2 is not equal to T2'. Tokens T3 and T4 are also present. * **Accepted/Rejected Tokens:** Shows the outcome of the verification process, with accepted tokens marked with a checkmark and rejected tokens marked with an "X". * **Rollback:** Shows the state of the KV cache after a rollback, with the sequence and KV cache restored until the final accepted token (T2). ### Detailed Analysis * **KV Cache States:** * **Prefill:** The KV cache is partially filled with a light blue color. * **Decode:** The KV cache is partially filled with a yellow color. * **Verify-Rollback:** The KV cache is partially filled with a light green color. * **Prefill Stage:** * A "deterministic request" fills a horizontal bar with light blue. * "Other requests" are represented by a gray block below the deterministic request. * **Decode Stage:** * Tokens T0, T1', T2', and T3' are represented by adjacent blocks. * T0 is light green. * T1' is light yellow. * T2' is yellow. * T3' is dark yellow. * The gray block from the "other requests" in the prefill stage extends into this stage, with a cross-hatched pattern indicating a change. * **Verify Stage:** * Tokens T0, T1', T2', T3', and T4 are represented by vertical blocks. * T0 is light green. * T1' is light yellow. * T2' is yellow with a cross-hatched pattern. * T3' is light red. * T4 is red. * Arrows connect the decoded tokens to the verification tokens. * **Accepted/Rejected Tokens:** * T1 (=T1') is accepted (checkmark). * T2 (!=T2') is accepted (checkmark). * T3 and T4 are rejected (X marks). * **Rollback Stage:** * The sequence and KV cache are restored until the final accepted token (T2). * The tokens T0, T1, and T2 are represented by adjacent blocks. * T0 is light blue. * T1 is light green. * T2 is yellow with a cross-hatched pattern. ### Key Observations * The diagram illustrates a process where requests are decoded, verified, and potentially rolled back based on token verification. * The KV cache changes its state as it progresses through the workflow. * The verification process determines which tokens are accepted and which are rejected. * The rollback stage restores the system to a previous state based on the accepted tokens. ### Interpretation The diagram depicts a mechanism for ensuring data integrity and consistency in a system utilizing a KV cache. The prefill stage initializes the cache, while the decode and verify stages process incoming requests and validate their authenticity or correctness. The rollback mechanism provides a way to revert to a known good state if verification fails, ensuring that the system does not operate on corrupted or invalid data. The use of tokens and their verification suggests a security or consistency protocol is in place. The diagram highlights the importance of verification in maintaining the integrity of the KV cache and the overall system.

\n ## Diagram: KV Cache Workflow with Prefill, Decode, Verify, and Rollback ### Overview This diagram illustrates a workflow involving a KV (Key-Value) cache across four stages: Prefill, Decode, Verify, and Rollback. It depicts how a deterministic request progresses through these stages, interacting with the KV cache and undergoing token acceptance or rejection. The diagram highlights the state of the KV cache at each stage and the handling of accepted and rejected tokens. ### Components/Axes The diagram is segmented into four main sections, each representing a stage in the workflow: 1. **Prefill:** Shows the initial deterministic request and the KV cache state. 2. **Decode:** Illustrates the decoding process and the KV cache update. 3. **Verify:** Depicts the verification stage, token acceptance/rejection, and the KV cache state. 4. **Rollback:** Shows the rollback process and the final KV cache state. There are also labels indicating: * "KV cache after prefill" * "KV cache after decode" * "KV cache after verify-rollback" * "other requests" * "accepted tokens" * "rejected tokens" * Time steps: T₀, T₁', T₂', T₃', T₁, T₂, T₃, T₄ ### Detailed Analysis or Content Details **Prefill:** * A blue block represents the "deterministic request" with an arrow indicating its entry point. * Above the block is a cylinder labeled "KV cache after prefill", indicating an initial state. **Decode:** * The deterministic request transitions into a series of four blocks representing time steps: T₀, T₁', T₂', T₃'. These blocks are stacked vertically. * Above the blocks is a cylinder labeled "KV cache after decode", indicating the cache state after decoding. * "other requests" are shown as an arrow pointing towards the decode stage. **Verify:** * Four blocks are shown, representing time steps: T₀, T₁', T₂', T₃', T₄. * T₁ (=T₁') is marked with a green checkmark, indicating acceptance. * T₂ (=T₂) is marked with a green checkmark, indicating acceptance. * T₃ is marked with a red "X", indicating rejection. * T₄ is marked with a red "X", indicating rejection. * The blocks representing accepted tokens are colored light green, while rejected tokens are colored red. * Above the blocks is a cylinder labeled "KV cache after verify-rollback", indicating the cache state after verification and potential rollback. **Rollback:** * A series of three blocks representing time steps: T₀, T₁, T₂. These blocks are colored light green. * Text states: "Sequence and KV cache restored until the final accepted token (T2)". ### Key Observations * The workflow is sequential, progressing from Prefill to Decode, Verify, and potentially Rollback. * The KV cache is updated at each stage, reflecting the accepted tokens. * Rejected tokens trigger a rollback mechanism, restoring the sequence and KV cache to the state before the rejected token. * The time steps are denoted with primes (T₁', T₂', T₃') during the decode stage, and without primes (T₁, T₂) after verification. * The diagram clearly illustrates the concept of speculative execution (Decode) followed by verification and potential correction (Verify/Rollback). ### Interpretation The diagram demonstrates a mechanism for handling speculative execution in a system utilizing a KV cache. The "deterministic request" initiates the process, and the "Decode" stage speculatively processes tokens. The "Verify" stage then checks the validity of these tokens. If tokens are rejected, the "Rollback" stage restores the system to a consistent state, ensuring that only accepted tokens are committed to the KV cache. This approach allows for efficient processing while maintaining data integrity. The use of a KV cache suggests an optimization strategy to reduce latency by storing frequently accessed data. The diagram highlights the importance of verification and rollback in handling potential errors during speculative execution. The time step notation (primes vs. no primes) indicates a distinction between the speculative and committed states of the tokens.

## Diagram: KV Cache State Transitions in a Speculative Decoding/Rollback Process ### Overview This diagram illustrates a technical process for managing Key-Value (KV) cache states during a sequence generation task, likely in the context of a language model using speculative decoding or a similar verification mechanism. The process flows from left to right through four distinct phases: Prefill, Decode, Verify, and Rollback. It shows how a "deterministic request" is processed alongside "other requests," how speculative tokens are generated and verified, and how the system state is restored upon rejection of tokens. ### Components/Axes The diagram is a flowchart with no traditional chart axes. It is organized into three horizontal sections representing the state of the KV cache at different stages, and four vertical phases detailing the process steps. **Top Section (KV Cache State):** * **Left:** "KV cache after prefill" - Represented by a single blue cylinder. * **Center:** "KV cache after decode" - Represented by a cylinder with a blue top and a yellow bottom. * **Right:** "KV cache after verify-rollback" - Represented by a cylinder with a blue top, a green middle, and a yellow bottom. **Bottom Section (Process Flow):** The process is divided into four labeled phases: 1. **Prefill** 2. **Decode** 3. **Verify** 4. **Rollback** **Key Labels and Elements:** * **Input:** "deterministic request" (pointing to a blue rectangle). * **Concurrent Work:** "other requests" (pointing to a stack of grey rectangles). * **Token Notation:** * `T0`, `T1`, `T2`, `T3`, `T4`: Likely represent actual or target tokens. * `T1'`, `T2'`, `T3'`: Represent speculative or predicted tokens (denoted with a prime symbol). * **Verification Outcomes:** * "accepted tokens" (pointing to two green checkmarks). * "rejected tokens" (pointing to two red X marks). * **Final State Description:** "Sequence and KV cache restored until the final accepted token (T2)". ### Detailed Analysis **1. Prefill Phase:** * A "deterministic request" (blue rectangle) is processed. * This occurs alongside "other requests" (grey rectangles), indicating concurrent processing. * The output is the initial "KV cache after prefill" (blue cylinder). **2. Decode Phase:** * The system generates a sequence of speculative tokens: `T0` (green), `T1'` (yellow), `T2'` (yellow), `T3'` (yellow). * These tokens are visualized as a horizontal bar. Below them are patterned blocks (grey with dots), likely representing the KV cache entries or attention patterns associated with these speculative tokens. * The "KV cache after decode" now contains the original prefill data (blue) plus new data from the speculative decode (yellow). **3. Verify Phase:** * The speculative tokens (`T0`, `T1'`, `T2'`, `T3'`) are compared against a separate sequence of actual or verified tokens (`T0`, `T1`, `T2`, `T3`, `T4`). * **Comparison Logic:** * `T1` is equal to `T1'` (`T1 = T1'`). This token is **accepted** (green checkmark). * `T2` is not equal to `T2'` (`T2 != T2'`). This token is **rejected** (red X). * The diagram implies `T0` was accepted (it matches and is the starting point). * Tokens `T3` and `T4` (red blocks) are shown but are not compared to primes, suggesting they are part of the verification sequence but were never proposed speculatively, or are beyond the point of failure. * The verification results in a set of "accepted tokens" (green checks) and "rejected tokens" (red Xs). **4. Rollback Phase:** * Based on the verification, the system rolls back. * The final state shows a sequence bar containing: the original blue block, the accepted green token (`T0`), the accepted green token (`T1`), and a patterned block for the rejected `T2`. * The "KV cache after verify-rollback" cylinder reflects this: it retains the prefill data (blue), the data from accepted tokens (green), and discards the data from rejected speculative tokens (the yellow section is now at the bottom, possibly indicating it's stale or marked for overwrite). * The text confirms: "Sequence and KV cache restored until the final accepted token (T2)". ### Key Observations * **Color Coding is Critical:** Blue represents the initial/prefill state. Green represents accepted/speculative tokens that are verified. Yellow represents speculative tokens that are generated but not yet verified. Red represents tokens in the verification sequence that are incorrect or beyond the failure point. Patterned fills represent KV cache data or states associated with tokens. * **Process Flow:** The diagram clearly shows a speculative-then-verify workflow. The system guesses multiple tokens ahead (`T1'`, `T2'`, `T3'`) in the Decode phase, then checks them in the Verify phase. * **Point of Failure:** The process fails at `T2` (`T2 != T2'`). All speculation after this point (`T3'`) is invalidated. * **State Restoration:** The Rollback phase does not revert to the very beginning. It reverts to the state after the last *accepted* token (`T2` in the sequence, which corresponds to `T1'` being correct). The KV cache is trimmed accordingly. ### Interpretation This diagram depicts a **speculative decoding with rollback** mechanism, a technique used to accelerate inference in autoregressive models like large language models. * **What it demonstrates:** The system uses a faster, possibly less accurate "draft" model to propose multiple future tokens (`T1'`, `T2'`, `T3'`) in one forward pass (Decode). A slower, more accurate "verification" model then checks these proposals against its own generated tokens (`T1`, `T2`, `T3`). If a mismatch is found (`T2 != T2'`), the system discards all subsequent speculative work and rolls back its state (KV cache and token sequence) to the last point of agreement. * **Why it matters:** This approach aims to achieve a speedup. If the draft model's guesses are often correct, the system can generate multiple tokens per verification step, reducing the total number of expensive verification passes needed. The cost of occasional rollbacks is offset by the gains from successful speculation. * **Underlying Logic:** The "deterministic request" likely refers to the initial prompt or a guaranteed starting point. The "other requests" suggest this process can be batched or run concurrently for multiple sequences. The preservation of the blue (prefill) and green (accepted) sections in the final KV cache shows efficient memory management—only the incorrect speculative data (yellow) is discarded. * **Notable Detail:** The final accepted token is labeled as `T2` in the rollback description, but in the verification column, `T1` was the last token marked with a check (`T1 = T1'`). This suggests `T2` in the final sequence bar corresponds to the *position* where the mismatch occurred, and the system restores up to and including the token *before* the failure, which is `T1`. The patterned block labeled `T2` in the rollback bar may represent the now-invalidated slot or the point from which regeneration must occur.

## Diagram: Deterministic Request Processing Flow with KV Cache Management ### Overview The diagram illustrates a multi-stage process for handling deterministic requests, including Prefill, Decode, Verify, and Rollback phases. It shows how a key-value (KV) cache evolves through these stages, with token acceptance/rejection logic and sequence restoration mechanisms. The flow emphasizes error recovery through token rollback while maintaining deterministic behavior. ### Components/Axes 1. **KV Cache States**: - **Prefill**: Blue cylinder (initial state) - **Decode**: Blue cylinder with yellow lower section (expanded state) - **Verify-Rollback**: Blue cylinder with green lower section (reduced state) 2. **Token Processing Flow**: - **Prefill**: Deterministic request → Gray blocks (other requests) + Blue block (deterministic request) - **Decode**: - Tokens: T₀ (green), T₁' (yellow), T₂' (yellow), T₃' (yellow) - Visual progression: Gray → Checkered → Solid blocks - **Verify**: - Token validation: T₁ (=T₁'), T₂ (=T₂') accepted (✓), T₃, T₄ rejected (✗) - **Rollback**: - Sequence restoration: T₀ (blue), T₁ (green), T₂ (checkered) 3. **Color Coding**: - Blue: Prefill/initial state - Green: Accepted tokens - Yellow: Proposed tokens during Decode - Red: Rejected tokens - Checkered pattern: Final accepted state ### Detailed Analysis 1. **Prefill Stage**: - Deterministic request triggers cache initialization - Other requests (gray blocks) are processed concurrently - KV cache remains in initial blue state 2. **Decode Stage**: - Token generation begins (T₀-T₃') - KV cache expands (blue + yellow) - Visual progression shows increasing token confidence (gray → checkered → solid) 3. **Verify Stage**: - Token validation against reference values - Accepted tokens (T₁', T₂') retain checkmarks - Rejected tokens (T₃, T₄) marked with X - KV cache transitions to blue + green 4. **Rollback Stage**: - Sequence truncated at last accepted token (T₂) - KV cache restored to blue + green state - Rejected tokens (T₃, T₄) permanently removed ### Key Observations 1. **Cache Dynamics**: - Cache grows during Prefill/Decode (blue → blue+yellow) - Shrinks during Verify-Rollback (blue+yellow → blue+green) - Final state retains only validated tokens 2. **Token Lifecycle**: - Proposed tokens (T₀-T₃') during Decode - Only T₁' and T₂' survive verification - Rejected tokens (T₃, T₄) excluded from final sequence 3. **Deterministic Guarantees**: - Final sequence (T₀-T₂) matches reference values - Rollback ensures consistency despite mid-process errors ### Interpretation This diagram demonstrates a fault-tolerant processing pipeline for deterministic systems. The KV cache acts as both a performance optimization (caching intermediate states) and a recovery mechanism (enabling rollback). The color-coded progression visually represents: - **State Evolution**: From initial prefill through error-prone decoding to final validation - **Error Handling**: Rejected tokens are permanently discarded, while accepted tokens form the immutable final sequence - **Deterministic Recovery**: The system recovers to a known-good state (T₂) rather than failing entirely The absence of explicit numerical values suggests this is a conceptual flow diagram rather than a performance benchmark. The checkmark/X system provides immediate visual feedback about token validity, while the KV cache's color transitions indicate state changes without requiring precise numerical tracking.