The cost of waiting for the slowest sequence

ProofAdvanced⏱ 1 hourLLM Opsorder statisticsbatchingutilisation

Problem

Let $S_1,\dots,S_B$ be i.i.d. output lengths.

Prove that static-batching utilisation $U_B = \E[\bar S]/\E[\max_i S_i]$ satisfies $U_B \le 1$ , with equality only if the lengths are almost surely equal.
For $S_i$ i.i.d. exponential, prove $U_B = 1/H_B$ .
For $S_i$ i.i.d. uniform on $[0, M]$ , compute $U_B$ and compare the decay with the exponential case.

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints — 0 of 3 revealed

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
KV cache sizing with MHA and GQA	LLM Ops	Numerical	Beginner	30 min
Ridge point and the batch size needed to saturate	LLM Ops	Numerical	Beginner	15 min
Apply Little's law to a serving target	LLM Ops	Proof	Intermediate	30 min
Derive the M/M/1 queue from detailed balance	AI Systems	Proof	Intermediate	1 hour
How many users fit on one GPU	LLM Ops	Numerical	Intermediate	30 min