Stream2LLM: Overlap Context Streaming and Prefill for Reduced Time-to-First-Token

Rajveer Bachkaniwala, Chengqi Luo, Richard So, Divya Mahajan, Kexin Rong

Georgia Institute of Technology

1

LLMs benefit from context retrieval

2

Retrieval

• Dense retrieval �(e.g., vector search)
• Sparse retrieval �(e.g., BM25)
• Tool use �(e.g., web crawling)
• …

External

Knowledge Source

I have a question…

parametric

knowledge

External

Context

Context retrieval hurts request latency

Retrieval latency

3

Doc

Retrieval

Generation

t=0

Prefill (Doc)

TTFT

+ Prefill latency

Time to First Token =

Decode

Time

Stream2LLM: Streaming LLM Inference

Goal: Overlap retrieval and prefill to reduce TTFT

Deployment setting: prefill instances in P/D disaggregation

* Implemented on top of vLLM

4

D1

D2

Prefill (D1)

Prefill (D2)

Decode

Retrieval

Generation

t=0

Prefill (D1)

Prefill (D2)

Decode

Streaming

Baseline

TTFT

TTFT

Challenges with Context Streaming

Each iteration, the scheduler allocates compute (token budget) and memory (KV cache) across requests without knowing:

• Input size
• Chunk arrival pattern
• Finish time

Prior work:

• Single-request streaming: e.g., PipeRAG, AquaPipe
• Efficient serving with static inputs: e.g., vLLM, Sarathi-serve

5

Gap: concurrent, streaming inference.

Characterize Retrieval Workloads

6

• Progressive accumulation �(e.g., web crawler)
• Cache grows incrementally

• Iterative refinement �(e.g., vector search)
• Update could invalidate cache

Two distinct behavior modes:

​

Require different scheduling and cache management mechanisms

Two-Phase Scheduling

7

Phase 1: What to run Select requests based on priority; check feasibility �

Scheduling Priority

�LCAS | FCFS | MCPS | …

Feasibility check:

​

1. Token Budget

2. GPU Block Budget

Scheduled Requests

Unfinished��Requests

Separate scheduling decisions from resource allocation mechanisms

Two-Phase Scheduling

8

Phase 1: What to run Select requests based on priority; check feasibility �

Phase 2: How to allocate If allocation fails: preempt lowest-priority running request;

Phase 2: Resource Acquisition & Preemption

Scheduled Requests

GPU Block �Allocator

Unfinished��Requests

Success

Separate scheduling decisions from resource allocation mechanisms

Two-Phase Scheduling

9

Phase 1: What to run Select requests based on priority; check feasibility�

Phase 2: How to allocate If allocation fails: preempt lowest-priority running request;

Phase 2: Resource Acquisition & Preemption

Scheduled Requests

GPU Block �Allocator

Unfinished��Requests

Adaptive Preemption

Eviction Strategy

Failure

​

(OOM)

Separate scheduling decisions from resource allocation mechanisms

Two Phase Scheduling

10

Phase 1- What to run: Select requests based on priority; check feasibility�

Phase 2 - How to allocate: If allocation fails: preempt lowest-priority running request; choose recompute or swap (based on cost model)

Phase 2: Resource Acquisition & Preemption

Scheduled Requests

GPU Block �Allocator

Unfinished��Requests

Adaptive Preemption

Eviction Strategy

Failure

​

(OOM)

Recompute

Separate scheduling decisions from resource allocation mechanisms

Two Phase Scheduling

11

Phase 1- What to run: Select requests based on priority; compute scheduling feasibility�

Phase 2 - How to allocate: If allocation fails: preempt lowest-priority running request; choose recompute or swap (based on cost model)

Phase 2: Resource Acquisition & Preemption

Scheduled Requests

GPU Block �Allocator

Unfinished��Requests

Adaptive Preemption

Eviction Strategy

Failure

​

(OOM)

Swap

Recompute

Swap

Separate scheduling decisions from resource allocation mechanisms

Scheduling Policies�

Default (FIFO)

• Based on request arrival order

​

Most processed tokens (MCPS)

• Sort all requests based on progress (aka #tokens processed)

​

First-Come-First-Served (FCFS)

• Sort request in each tier using request arrival order

​

Last chunk arrival time (LCAS)

• Sort request in each tier using last chunk arrival time

​

12

Two-tier approach:

• Intuition: Complete requests have higher priority over Partial

�*Eviction in reverse scheduling priority

Evaluation Setup

Model: Llama-3.1-8B-Instruct

Hardware: H200 (TP=2)

Baselines:

​

�Retrieval Workloads:

• Append – web crawler
• Latency: median: 3.9s, P95: 8.5s
• #Tokens/Query: median: 10K, P95: 31K

​

• Update – diskANN (AquaPipe [SIGMOD’25])
• Retrieval Latency: median: 9.3s, P95: 16.7s
• #Tokens/Query: median: 5.8K, P95: 28.9K

​

13

Evaluation (Append): TTFT vs QPS

• Throughput is not reduced
• 11× speed up in median latency than non-streaming (QPS=4)

​

14

Methods of Comparison

Evaluation (Update): TTFT vs QPS

15

• Smaller gains compared to append mode: ~2× faster than non-streaming
• >10% of requests invalidate over 10K tokens

Methods of Comparison

Stream2LLM Summary

Overlapping retrieval with prefill to reduce TTFT

• Append vs update mode
• Streaming-aware scheduling design

​

16

D1

D2

Prefill (D1)

Prefill (D2)

Decode

Retrieval

Generation

t=0

Prefill (D1)

Prefill (D2)

Decode

Streaming

Baseline

TTFT

TTFT

Scan for Code!

Evaluation: Memory Pressure

Stress test: chunk inter-arrival delays to saturate GPU block pool

17

Naïve streaming algorithms could collapse under memory pressure!