Continuous Batching (In-Flight Batching) Simulator
Problem statement
Implement a function continuous_batching_sim(requests, max_batch_size) that simulates the continuous batching (also called in-flight batching) strategy used in modern LLM serving systems.
Background
In traditional static batching, the server waits for all sequences in a batch to finish generating tokens before admitting new requests. This wastes GPU cycles on padding shorter sequences.
Continuous batching solves this by allowing new requests to fill freed slots immediately when existing sequences complete, maximizing GPU utilization.
Simulation Rules
At each discrete time step (starting at time 0), the following events occur in this exact order:
- Arrive: Any request with
arrival_time <= current_timethat has not yet been enqueued is added to the waiting queue (in the order they appear in the input list). - Fill: Empty batch slots are filled from the front of the queue (FIFO), up to
max_batch_sizetotal active slots. Each admitted request records its processing start time. - Generate: Every active slot produces exactly one token (decrement remaining tokens by 1).
- Complete: Any slot with zero remaining tokens is removed. Its completion time is the current time step.
- Advance: If there are no active slots, no queued requests, and only future arrivals remain, jump time forward to the next arrival. Otherwise, increment time by 1.
The simulation ends when all requests have been completed.
Input
requests: A list of dicts, each with'arrival_time'(int >= 0) and'tokens_needed'(int >= 1)max_batch_size: Maximum number of concurrent sequences (int >= 1)
Output
Return a dictionary with:
'total_time': The value of the time counter after the final Advance (one past the step in which the last request completes)'avg_latency': Average of (completion_time - arrival_time) across all requests, rounded to 4 decimal places'avg_ttft': Average time-to-first-token (start_time - arrival_time) across all requests, rounded to 4 decimal places'throughput': Total tokens generated divided by total_time, rounded to 4 decimal places
Example
Input:
requests = [{'arrival_time': 0, 'tokens_needed': 3}, {'arrival_time': 0, 'tokens_needed': 2}, {'arrival_time': 1, 'tokens_needed': 2}], max_batch_size = 2
Output:
{'total_time': 4, 'avg_latency': 1.6667, 'avg_ttft': 0.3333, 'throughput': 1.75}
Reasoning: Time 0: R0 and R1 arrive. Both fill the 2 slots. Generate: R0 has 2 left, R1 has 1 left. Time 1: R2 arrives, joins queue (batch full). Generate: R0 has 1 left, R1 completes (end=1). Slot freed. Time 2: R2 fills the open slot (start=2). Generate: R0 completes (end=2), R2 has 1 left. Time 3: Generate: R2 completes (end=3). Latencies: R0=2, R1=1, R2=2. TTFT: R0=0, R1=0, R2=1. Total tokens=7 in 4 steps.
Show hint
What happens to a slot the moment its sequence finishes, and when can a waiting request take it over?
Relevant roles: LLM Engineer, MLOps Engineer, AI Engineer, ML Engineer and Gen AI Engineer.
Related free problems
- Request Batching for InferenceML System DesignMedium
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium