Progressive compilation for structured generation

[rlouf]

Our current approach compiles an entire regex AST at once, blocking generation until compilation finishes. For large ASTs, this creates noticeable delays.

This discussions proposes a progressive approach that enables overlapping compilation and generation, allowing output to begin sooner and to decrease compilation time.

Core Approach

1. Break the AST into independently compilable segments
2. Compile segments in parallel with priority on earlier segments
3. Begin generation as soon as the first segment is ready

Segment Analysis and Optimization

We'll analyze sequences to identify:

• String literals (which need no compilation)
• Regex patterns (which require compilation)

flowchart TD
    subgraph "Input AST"
        input["Sequence AST"]
    end

    subgraph "Segmentation"
        analyze["analyze_sequence()"]
        optimize["optimize_segments()"]
    end
    
    subgraph "Segmented Result"
        segments["Identified Segments"]
        
        string1["String: 'Hello, '"]
        regex1["Regex: alternatives()"]
        string2["String: '! '"]
        regex2["Regex: \\d{4}-\\d{2}-\\d{2}"]
        
        segments --> string1
        segments --> regex1
        segments --> string2
        segments --> regex2
    end
    
    input --> analyze
    analyze --> optimize
    optimize --> segments

Loading

Progressive Compilation Engine

The engine uses a priority queue and worker threads to compile segments in parallel.

Progressive Generation

The generator starts producing output as soon as the first segment is ready.

Implementation Example

Here's how to use the progressive compilation system:

from outlines.types import either, regex
# Create a pattern
pattern = (
   "Hello"
    + either(
       "world",
       "universe",
       "everyone"
    )
   + "! Today is "
   + regex(r"\d{4}-\d{2}-\d{2}")
)

result = model(prompt, pattern)
print(result)  # "Hello, world! Today is 2025-03-15"

Performance Benefits

• Faster First Output: Generation begins as soon as the first segment is ready
• Parallelism: Compilation happens across multiple threads/workers
• Reduced Memory: Each segment is compiled independently

Implementation Strategy

1. Create a compilation engine using worker threads and a priority queue
2. Implement segment analysis and optimization
3. Add progressive generation

Follow-Up Work

For a future enhancement, we'll address token boundary handling to ensure proper text generation at segment boundaries.