## 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.
