Continuous Batching (In-Flight Batching) Simulator

MediumML Coding

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:

  1. Arrive: Any request with arrival_time <= current_time that has not yet been enqueued is added to the waiting queue (in the order they appear in the input list).
  2. Fill: Empty batch slots are filled from the front of the queue (FIFO), up to max_batch_size total active slots. Each admitted request records its processing start time.
  3. Generate: Every active slot produces exactly one token (decrement remaining tokens by 1).
  4. Complete: Any slot with zero remaining tokens is removed. Its completion time is the current time step.
  5. 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