# Technical Document Extraction: FSM and LLM Decoding Comparison This document describes a technical diagram illustrating the optimization of Finite State Machines (FSM) for Large Language Model (LLM) decoding processes, specifically for regex-constrained generation. ## 1. Legend and Component Definitions The diagram uses color-coded and shape-coded blocks to represent different stages of the process: * **FSM state (Light Blue Rectangle):** Represents a discrete state within a Finite State Machine. * **Token (Light Yellow Rectangle):** Represents a specific string or character sequence processed as a unit. * **LLM decode (Light Green Hexagon):** Represents the computational step where the Large Language Model generates/decodes a token. --- ## 2. Diagram Analysis by Section ### Section (a): Normal FSM for regex `{"summary": "` This section shows a linear, character-by-character state transition for a specific JSON-like string. * **Flow:** A sequence of 14 states (numbered 0 through 13) connected by blue arrows. * **Transitions:** Each arrow represents a single character transition: * 0 → 1: `{` * 1 → 2: `"` * 2 → 3: `s` * 3 → 4: `u` * 4 → 5: `m` * 5 → 6: `m` * 6 → 7: `a` * 7 → 8: `r` * 8 → 9: `y` * 9 → 10: `"` * 10 → 11: `:` * 11 → 12: `_` (space character) * 12 → 13: `"` ### Section (b): Compressed FSM for regex `{"summary": "` This section demonstrates the optimization of the FSM by collapsing multiple character transitions into a single state jump. * **Flow:** A direct transition from state **0** to state **1**. * **Transition Label:** The entire string `{"summary": "` is handled in a single transition step. ### Section (c): Decoding process with normal FSM This section illustrates the interaction between the LLM and the unoptimized FSM. * **Sequence:** 1. **Token:** `{"` 2. **LLM decode** 3. **Token:** `summary` 4. **LLM decode** 5. **Token:** `":` 6. **LLM decode** 7. **Token:** `_"` (space and quote) 8. **LLM decode** * **Trend:** The process is fragmented, requiring four separate LLM decoding steps to complete the sequence because the FSM operates at a fine-grained level. ### Section (d): Decoding process with compressed FSM This section illustrates the interaction between the LLM and the optimized FSM. * **Sequence:** 1. **Token:** `{"` 2. **Token:** `summary` 3. **Token:** `":` 4. **Token:** `_"` (space and quote) 5. **LLM decode** * **Trend:** The tokens are processed sequentially without interruption. The LLM decoding step only occurs once at the end of the pre-defined sequence. --- ## 3. Summary of Key Information * **Objective:** To compare "Normal" vs. "Compressed" FSMs in the context of LLM decoding. * **Key Data Point:** The compressed FSM (b) reduces a 13-step character transition into a single transition. * **Process Efficiency:** The decoding process with a compressed FSM (d) significantly reduces the number of LLM decoding calls compared to the normal process (c), which requires an LLM call after almost every token segment. * **Textual Content:** The primary regex being processed is `{"summary": "`. Note that in the diagram, the space character is represented by an underscore `_` in the transition labels.

# Technical Document Extraction: FSM and LLM Decoding Processes ## Diagram Components and Flow Analysis ### Diagram (a): Normal FSM for Regex `{"summary": ""}` - **FSM States**: 14 states labeled 0–13 (blue squares). - **Transitions**: Sequential transitions between states (e.g., 0 → 1 → 2 → ... → 13). - **Regex Highlight**: `{"summary": ""}` (cyan highlight). - **Tokens**: Single token `"{"` (yellow rectangle) initiating the FSM. ### Diagram (b): Compressed FSM for Regex `{"summary": ""}` - **FSM States**: 2 states labeled 0–1 (blue squares). - **Transitions**: Direct transition from state 0 to 1. - **Regex Highlight**: `{"summary": ""}` (cyan highlight). - **Tokens**: Single token `"{"` (yellow rectangle) initiating the FSM. ### Diagram (c): Decoding Process with Normal FSM - **Components**: - **Token Input**: `"{"` (yellow rectangle). - **LLM Decodes**: 5 hexagonal nodes labeled "LLM Decode". - **FSM Integration**: - Token `"{"` → LLM Decode → `"summary"` (token) → LLM Decode → `":"` (token) → LLM Decode → `" "` (token) → LLM Decode → Final output `{"summary": ""}`. - **Flow**: Token → LLM Decode → Token → LLM Decode → Token → LLM Decode → Token → LLM Decode → Final Regex Output. ### Diagram (d): Decoding Process with Compressed FSM - **Components**: - **Token Input**: `"{"` (yellow rectangle). - **LLM Decodes**: 3 hexagonal nodes labeled "LLM Decode". - **FSM Integration**: - Token `"{"` → LLM Decode → `"summary"` (token) → LLM Decode → `":"` (token) → LLM Decode → Final output `{"summary": ""}`. - **Flow**: Token → LLM Decode → Token → LLM Decode → Token → LLM Decode → Final Regex Output. ## Key Observations 1. **FSM Compression**: - Normal FSM: 14 states (0–13) for regex `{"summary": ""}`. - Compressed FSM: 2 states (0–1) for the same regex, reducing complexity. 2. **LLM Decoding**: - Normal FSM: 5 LLM decodes required for full regex reconstruction. - Compressed FSM: 3 LLM decodes required, streamlining the process. 3. **Token Handling**: - Both processes start with the token `"{"` and end with the regex `{"summary": ""}`. - Compressed FSM merges intermediate steps, reducing token-LLM interactions. ## Legend and Color Mapping - **Blue Squares**: FSM States (Normal/Compressed). - **Yellow Rectangles**: Tokens (e.g., `"{"`, `"summary"`, `":"`). - **Green Hexagons**: LLM Decode Nodes. - **Cyan Highlight**: Regex `{"summary": ""}` (target output). ## Data Points and Trends - **Normal FSM**: - Longer path (14 states) with sequential token processing. - Higher computational overhead due to multiple LLM decodes. - **Compressed FSM**: - Shorter path (2 states) with direct transitions. - Reduced LLM decodes (3 vs. 5), improving efficiency. ## Conclusion The diagrams illustrate two approaches to regex decoding: 1. **Normal FSM**: Detailed state transitions with frequent LLM integration. 2. **Compressed FSM**: Optimized state reduction and fewer LLM decodes for efficiency. Both methods achieve the same output `{"summary": ""}`, but the compressed FSM offers a more streamlined process.