Q6HardPart Q · AI Infra Hardware & Memory Scheduling
LLM Gateway Anti-Cascade Load Shedding & KV Preemption Gate
Simulate high-watermark KV admission control, queue-wait SLA load shedding, and priority preemption to prevent continuous-batching OOM cascades.
⏱️ Time:
O(N)💾 Space:
O(N)🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
def kv_pressure_admission_gate(requests: list[dict], total_kv_blocks: int, watermark_ratio: float = 0.88, sla_ms: float = 1200.0) -> dict:
used_blocks = 0
queue_wait_ms = 0.0
admitted, preempted, rejected = [], [], []
limit =
for req in requests:
need = int(req["kv_blocks"])
prefill_ms = float(req["est_prefill_ms"])
prio = int(req.get("priority", 1))
if used_blocks + need <= limit and (queue_wait_ms + prefill_ms) <= sla_ms:
used_blocks += need
queue_wait_ms += prefill_ms
admitted.append(req["id"])
elif prio >= 2 and need <= total_kv_blocks and admitted:
evicted = admitted.pop()
preempted.append(evicted)
admitted.append(req["id"])
else:
rejected.append(req["id"])
return
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: Under KV starvation, when is stateless recomputation faster than swapping KV blocks to CPU RAM?
Q2: Why does standard HTTP QPS rate limiting fail to protect LLM serving clusters?
💡
Core Mental Anchor / Mnemonic
Reserve KV headroom for running decode; shed excess early rather than thrashing
📐 Mathematical Derivation & Core Formula
$$\text{Admit}(r) \iff U_{\text{KV}} + K(r) \le \tau_{\text{high}} \land \text{EstQueueWait} + T_{\text{prefill}}(r) \le \text{SLA}_{p99}$$
Without reserving KV headroom (~12%) for active decoding sequences to grow, full queues enter thrashing preemption loops that inflate P99 TTFT across all tenants. Enforcing KV watermark + SLA admission gates sheds excess low-priority load upfront with 429 backoff.
🔄 Tensor Dimensions & Shape Flow
requests queue + kv headroom + SLA -> admitted / preempted / shed decisions
🛡️ Numerical Stability & Pitfalls Checklist
- Reserve 10–15% KV headroom exclusively for in-flight autoregressive token expansion
- Decide carefully between CPU-swap vs stateless recomputation upon preemption
- Pair early 429 shedding with Retry-After headers so client retries do not amplify saturation
💻 Reference Code Implementation
def kv_pressure_admission_gate(requests: list[dict], total_kv_blocks: int, watermark_ratio: float = 0.88, sla_ms: float = 1200.0) -> dict:
used_blocks = 0
queue_wait_ms = 0.0
admitted, preempted, rejected = [], [], []
limit = int(total_kv_blocks * watermark_ratio)
for req in requests:
need = int(req["kv_blocks"])
prefill_ms = float(req["est_prefill_ms"])
prio = int(req.get("priority", 1))
if used_blocks + need <= limit and (queue_wait_ms + prefill_ms) <= sla_ms:
used_blocks += need
queue_wait_ms += prefill_ms
admitted.append(req["id"])
elif prio >= 2 and need <= total_kv_blocks and admitted:
evicted = admitted.pop()
preempted.append(evicted)
admitted.append(req["id"])
else:
rejected.append(req["id"])
return {"admitted": admitted, "preempted": preempted, "rejected": rejected, "kv_util": round(used_blocks / max(total_kv_blocks, 1), 3)}🧪 Runnable Assertions & Validation
Copy and run directly in Python / Jupyter:
reqs = [
{"id": "r1", "kv_blocks": 50, "est_prefill_ms": 400, "priority": 1},
{"id": "r2", "kv_blocks": 40, "est_prefill_ms": 400, "priority": 1},
{"id": "r3", "kv_blocks": 30, "est_prefill_ms": 400, "priority": 1},
{"id": "vip", "kv_blocks": 20, "est_prefill_ms": 200, "priority": 2},
]
out = kv_pressure_admission_gate(reqs, total_kv_blocks=100, watermark_ratio=0.90, sla_ms=1200)
assert out['rejected'] == ['r3'] and out['preempted'] == ['r2'] and 'vip' in out['admitted']
print('Q6 PASS')🎯 Core Follow-up Inquiries & Reference Answers
Q1:Under KV starvation, when is stateless recomputation faster than swapping KV blocks to CPU RAM?
When prompt length is moderate and GPU compute is abundant, a fast parallel prefill pass often beats slow PCIe host-to-device memory copies.
Q2:Why does standard HTTP QPS rate limiting fail to protect LLM serving clusters?
Request cost varies by 100x–1000x across prompt/output lengths and KV residency; admission must meter estimated KV blocks and tokens.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.