15-LLM-Inference-Scheduler

Appearance

Feature Inventory & Architectural Traces ​

F1: Continuous Iteration-Level Batching ​

Technical Description ​

Replaces static request-level batching with dynamic iteration-level batching (the Orca model). At every autoregressive generation step, the engine evaluates available memory and token budgets, flushes completed sequences, and injects newly arrived prompts without waiting for active requests to finish.

  • Primary Source: backend/src/batching/continuous.py
  • Key Method: ContinuousBatcher.step()
  • Complexity: $O(B)$ per forward step where $B$ is active batch size.

Say It Out Loud ​

"I built the continuous batching engine to solve the fundamental GPU underutilization problem in LLM serving. In traditional batching, if one request generates 10 tokens and another generates 500 tokens, the GPU sits idle on 90% of the batch for hundreds of iterations. My continuous batcher steps through generation at the individual token level. At every forward pass, it evaluates the remaining token budget, evicts requests that reached an EOS token, and dynamically merges new incoming prompts into the active batch. This boosted aggregate token throughput by over 3x under dynamic real-world workloads."

F2: Paged KV-Cache Memory Allocator ​

Technical Description ​

Implements a virtual memory block allocator for Key-Value attention tensors. GPU KV cache is divided into fixed-size physical blocks (e.g. 16 tokens). Sequences dynamically allocate non-contiguous blocks on demand through a logical page table, eliminating external fragmentation and enabling prefix sharing.

  • Primary Source: backend/src/kv/paged.py
  • Key Methods: PagedKVAllocator.allocate(), PagedKVAllocator.free()
  • Memory Efficiency: Reduces memory waste from ~60% down to under 4%.

Say It Out Loud ​

"To prevent out-of-memory crashes during multi-user generation, I designed a Paged KV-Cache allocator modeled after operating system virtual memory paging. In standard self-attention, you have to pre-allocate contiguous GPU memory for the maximum possible sequence length—say, 4,096 tokens—even if the user only generates 50 tokens. My allocator divides GPU memory into fixed 16-token physical pages. As a request generates tokens, logical sequence offsets are mapped to physical pages via a page table. When generation completes, all pages are instantly returned to the free list. This eliminated external memory fragmentation and increased our maximum concurrent batch size by 400%."

F3: Chunked Prefill & Decode Interleaving ​

Technical Description ​

Decouples compute-bound prompt prefill from memory-bound autoregressive decoding. Long prompts are chunked into 256-token slices, allowing decode iterations to execute between chunks to prevent catastrophic spikes in Inter-Token Latency (ITL).

  • Primary Source: backend/src/batching/continuous.py, backend/src/scheduler/queue.py

Say It Out Loud ​

"One subtle bug in naive LLM serving is the 'prefill bubble': when a massive 2,000-token prompt arrives, it hogs the GPU for 200 milliseconds, causing existing streaming users to experience a noticeable pause. I fixed this by implementing chunked prefill. When a long prompt arrives, the scheduler splits it into 256-token slices. Between each prefill slice, the engine runs a decode step for all active streams. This bounded our p99 inter-token latency to under 30 milliseconds while smoothly ingesting large context windows."

F4: GPU Worker Registry & Multi-Replica Routing ​

Technical Description ​

Maintains a registry of GPU worker instances, tracking active KV-cache utilization, temperature, and heartbeat health. Routes incoming prompts to the replica with the highest available KV page headroom.

  • Primary Source: backend/src/coordination/workers.py, backend/src/routing/router.py

F5: Server-Sent Events (SSE) Token Streaming ​

Technical Description ​

Provides OpenAI-compatible SSE streaming (text/event-stream) endpoints. Yields tokens asynchronously to the client as they are produced by the continuous batcher iteration loop.

  • Primary Source: backend/src/api/app.py