Neural Mastery
← Practice
Continuous Batching Iteration Schedulermedium

Continuous Batching Iteration Scheduler

medium Inside an LLM 20–25 min

NumPy allowed · plain Python earns 10 bonus points

LLM step 1/4

Logits become a next-token distribution

Softmax turns a model score vector into probabilities.
Open lesson →
01prompt
02tokens
03logits
04probabilities
attention→next token
mechanism65%
layer20%
pattern10%
model5%

Softmax(logits) → probability distribution

Maximize GPU compute utilization and eliminate idle bubble time using iteration-level continuous batching.

Task

Implement schedule_continuous_batch(active_requests, waiting_queue, max_batch_size, max_total_tokens). Step 1: For each active request, increment current_tokens by 1. If current_tokens >= max_tokens, add its ID to completed_ids. Otherwise retain it in active and accumulate its tokens. Step 2: In FIFO order, admit requests from waiting_queue into active as long as len(active) < max_batch_size AND current_tokens_used + prompt_tokens <= max_total_tokens. Return dict with scheduled_active_ids, completed_ids, remaining_waiting_ids, and batch_token_budget_used. Raise ValueError if max_batch_size <= 0 or max_total_tokens <= 0.

Function Signature

schedule_continuous_batch(active_requests: list[dict], waiting_queue: list[dict], max_batch_size: int, max_total_tokens: int) -> dict

Examples

Example 1: Active request completes and admits waiting
Input: active_requests = [{'id': 'req_1', 'current_tokens': 9, 'max_tokens': 10}] waiting_queue = [{'id': 'req_2', 'prompt_tokens': 4, 'max_tokens': 15}] max_batch_size = 2 max_total_tokens = 50
Output: {'scheduled_active_ids': ['req_2'], 'completed_ids': ['req_1'], 'remaining_waiting_ids': [], 'batch_token_budget_used': 4}
Example 2: Token budget limits admission
Input: active_requests = [{'id': 'r1', 'current_tokens': 20, 'max_tokens': 50}] waiting_queue = [{'id': 'r2', 'prompt_tokens': 15, 'max_tokens': 30}] max_batch_size = 4 max_total_tokens = 30
Output: {'scheduled_active_ids': ['r1'], 'completed_ids': [], 'remaining_waiting_ids': ['r2'], 'batch_token_budget_used': 21}
Example 3: Invalid negative capacity error
Input: active_requests = [] waiting_queue = [] max_batch_size = 0 max_total_tokens = 10
Output: Raises ValueError

Constraints

  • max_batch_size <= 0 or max_total_tokens <= 0 must raise ValueError.
  • Active requests get priority over waiting queue.
  • Waiting queue processed strictly FIFO.
  • A plain-Python solution earns 10 bonus points.
Python3Saved ✓
def schedule_continuous_batch(active_requests: list[dict], waiting_queue: list[dict], max_batch_size: int, max_total_tokens: int) -> dict:
"""Perform one iteration of dynamic continuous batch scheduling.
Args:
active_requests: Currently running decode requests.
waiting_queue: Arrived requests awaiting initial scheduling.
max_batch_size: Maximum concurrent requests allowed in batch.
max_total_tokens: Memory budget cap for total active tokens.
Returns:
dict with 'scheduled_active_ids', 'completed_ids', 'remaining_waiting_ids', and 'batch_token_budget_used'.
"""
# Your implementation here
pass

Case 1: Active request completes and admits waiting
Input: active_requests = [{'id': 'req_1', 'current_tokens': 9, 'max_tokens': 10}] waiting_queue = [{'id': 'req_2', 'prompt_tokens': 4, 'max_tokens': 15}] max_batch_size = 2 max_total_tokens = 50
Expected: {'scheduled_active_ids': ['req_2'], 'completed_ids': ['req_1'], 'remaining_waiting_ids': [], 'batch_token_budget_used': 4}
Case 2: Token budget limits admission
Input: active_requests = [{'id': 'r1', 'current_tokens': 20, 'max_tokens': 50}] waiting_queue = [{'id': 'r2', 'prompt_tokens': 15, 'max_tokens': 30}] max_batch_size = 4 max_total_tokens = 30
Expected: {'scheduled_active_ids': ['r1'], 'completed_ids': [], 'remaining_waiting_ids': ['r2'], 'batch_token_budget_used': 21}
Case 3: Invalid negative capacity error
Input: active_requests = [] waiting_queue = [] max_batch_size = 0 max_total_tokens = 10
Expected: Raises ValueError