The Newsvendor Problem Under a Heavy Tail
The Provisioning Problem
A number nobody has tested and a number that’s actually safe look identical. Right up until the day they don’t.
Every system that commits to a capacity figure before it knows real demand eventually meets the demand that tests it. That’s not bad planning: it’s what committing in advance means.
Case Study: A Pool Sized by What Usually Happens. Picture a model-serving node running thirty-two concurrent generation slots: fixed by GPU memory, not by choice, since every request in flight needs its own slice of VRAM for its KV cache, and the card only has so much of it. Most traffic is cheap: a classification, a short rewrite, a few hundred tokens, done in under a second. About one call in two thousand is different, an open-ended reasoning trace with no natural stopping point, indistinguishable from the cheap case until it either finishes fast or doesn’t. Thirty-two slots handles the ordinary traffic with room to spare. It has for months. Every load test that mattered passed, because every load test ran the traffic that was easy to generate, the ordinary case, repeated.
That’s the trap a long tail sets. The rare event’s absence from the sample so far isn’t evidence it won’t happen: only that it hasn’t happened yet. And when it lands, the gap isn’t a modest overrun; it scales with whatever “ordinary” already was. A process whose typical call finishes in milliseconds can have a tail that runs minutes. A process whose typical job takes hours can have a tail that runs days. The units change. The shape (vastly rare, vastly long relative to its own median) doesn’t.
On some unremarkable day, three or four reasoning traces land close together. Slots don’t get preempted mid-generation: evicting one means discarding its KV cache, and resuming later costs exactly what starting over costs, so nothing pauses the long ones to let the short ones through. Occupancy drifts rather than jumps: a short completion cycles through its slot in under a second, a long reasoning trace holds its slot for minutes, and the pool skews further toward slow traffic than the arriving mix would suggest. Every other node is running the same traffic mix through its own full pool, so there’s nowhere to send the overflow. The short, cheap, everyday calls (the actual bulk of the traffic) start queuing behind generations that are each, individually, doing exactly what they were asked to do.
No request was malformed. No bug shipped. The pool filled correctly, one legitimate admission at a time, until nothing else could get in. Call it provisioning by precedent: trusting a number because it has always worked, which is exactly the property that stops being informative the day the traffic finally tests the assumption underneath it.
Provisioning by precedent is what happens when nobody runs the actual computation. That computation has a name and a complete, textbook answer: the newsvendor problem [1] : seventy years old, closed-form, taught in the first weeks of any operations course. Given a demand distribution , choose a capacity that balances two costs: underage (provisioning too little) against overage (provisioning too much). The optimal is a single closed-form quantile:
where:
- - the optimal capacity to provision
- - the true demand distribution, with inverse (quantile function)
- - the underage cost of one unit of unmet demand
- - the overage cost of one unit of unused capacity
The folklore version stops there: compute , deploy it, remeasure occasionally, done. That version is wrong, not everywhere, but for a specific, checkable, unremarkable-looking class of demand. The 32-slot pool above is exactly what the failure looks like when it arrives. Proposition 0, below, proves precisely where the stability the folklore version leans on stops holding.
Mathematical proof: how the fractile formula actually falls out
Arrow, Harris & Marschak’s derivation is a single first-order condition, not a black box worth taking on faith. Expected total cost at capacity is , where is the random demand. Differentiate with respect to and set the result to zero:
Inverting gives the formula above. The whole result rests on one property of : the second derivative of expected cost is wherever a density exists, so expected cost is convex and the first-order condition characterizes an actual minimum, not just a critical point. That’s true for essentially any demand distribution encountered in practice, light- or heavy-tailed alike.
The formula itself never assumed light tails. What breaks under heavy tails, per Proposition 0, isn’t this derivation. It’s the habit of plugging in an estimated from a finite sample as if it were the true one.
Definition 0 -- The Provisioning Achievable Region: every capacity choice is a point in a two-cost tradeoff space, and only one point is optimal for a given cost ratio
Definition 0 (Provisioning Achievable Region). Given a true demand distribution , every choice of capacity maps to a point . The expected cost of provisioning too little, and the expected cost of provisioning too much, at that . Varying traces a Pareto frontier: lowering decreases expected overage cost and increases expected underage cost, and no choice of improves one without worsening the other. Given a fixed cost ratio , exactly one point on that frontier minimizes the weighted objective . That point is , the critical fractile.
Physical translation. This is the actual object the newsvendor formula is computing a point on, not just a formula in isolation. There’s a whole curve of feasible tradeoffs between under-provisioning and over-provisioning, and isn’t “the answer” in the abstract: it’s the specific point on that curve that matches how much you actually care about each kind of failure, expressed as a ratio.
The chart above uses a single, simple exponential demand to show what an achievable region is, in general, and what it means to be at the wrong point on it. Definition 0 holds for any , so a clean illustrative distribution is enough there. What follows is a different, sharper exercise: not one distribution’s frontier, but a real comparison between two, built to make Proposition 0’s dominance claim checkable rather than merely plausible.
Trace example A. The capacity number. This example runs on illustrative units ( ), deliberately not the case study’s own seconds. It exists to make Proposition 0’s dominance claim checkable in isolation, before Trace Example B (below) applies the same machinery to the case study’s real numbers.
Proposition 0’s claim, made concrete rather than asserted. Let the true demand be Pareto-distributed: for , with , , a real heavy tail, not an exotic one, with finite mean . An operator who has only ever seen the ordinary case fits a light-tailed exponential model instead, using the correct mean, the most generous version of the mistake possible, since even a perfectly-estimated mean doesn’t save you if the shape is wrong. At a 999:1 underage-to-overage cost ratio , the same asymmetry that made the case study’s outage expensive, where a sedimented pool refusing every admission cost far more than one idle slot ever would. The correctly-specified Pareto model gives = 115.5. The exponential model, same mean, same ratio, gives only = 63.3, a 45% capacity shortfall from the shape mistake alone. Evaluating against the true Pareto cost function, using the Pareto mean-residual-life identity for the underage term, gives a weighted cost 24.5% higher than achieves. sits exactly on the frontier for the exponential world it was computed against. On the frontier of the real one it’s still a reachable point, just the wrong one for this ratio: the 24.5% figure above is exactly the price of sitting at that wrong point instead of . That is Proposition 0’s dominance claim, verified with numbers, not asserted.
| Quantity | Value | What it means |
|---|---|---|
| 9.17 | the true mean, used identically by both models | |
| 115.5 | optimal capacity under the correctly-specified Pareto | |
| 63.3 | optimal capacity under the misspecified exponential, same mean | |
| Capacity shortfall | 45% | how much smaller the wrong answer is |
| Weighted-cost overpayment | 24.5% | the actual price of the shape mistake, evaluated against the true cost function |
The measured cost of fitting an exponential to Pareto-distributed demand: a 45% capacity shortfall and a 24.5% weighted-cost overpayment against the true optimum.
Exponential isn’t the wrong model here because light-tailed workloads are always exponential: they aren’t. It’s chosen because it’s the maximum-entropy distribution on given only a known mean: the least additional structure assumable beyond “I know the average.” An operator who correctly measures the mean and adds no further assumption defaults, whether they realize it or not, to exactly this distribution. That’s why using the correct mean above is the most generous version of the mistake, not a strawman. The failure isn’t sloppy estimation. It’s that the single most information-conservative distribution consistent with what was actually measured is still the wrong one, whenever what’s measured is a mean and nothing about the shape.
Scheduling has its own version of the same problem, one layer down. Not how much capacity to provision, but which arriving units of work to admit into a shared, finite pool, when each unit’s true cost (how long it will actually run) is unknown until it finishes or reveals itself in flight. Where the newsvendor problem asks “how much capacity,” this version asks “admit or hold,” repeatedly, under the same underage/overage cost structure. It inherits every fragility Proposition 0 proves for the parent problem, plus a second one: a capacity number can be recomputed after a bad day. A concurrency pool cannot un-admit a task already running inside it.
Proposition 0 -- Fragility of Misspecified Capacity Targets: a correct answer exists under heavy tails, but not the one most operators compute
Proposition 0 (Fragility of Misspecified Capacity Targets). Das, Dhara & Natarajan [2] prove that a distributionally-robust order quantity (computed explicitly against a heavy-tailed ambiguity set rather than an assumed-light-tailed demand curve) is itself heavy-tail-optimal. A correct answer exists; the fractile concept is not broken. What their results show instead is where the fragility actually lives: an order quantity optimized under a misspecified light-tailed assumption degrades sharply once the true demand carries even a modest heavy-tailed contamination, and computing the correct robust alternative requires exactly the moment information (tail index, higher moments) that is hardest to estimate reliably from finite historical data.
Physical translation. The fractile formula was never the problem. Given the true demand distribution, ’s closed form is exactly correct, heavy tail or not: the formula doesn’t care how demand is shaped. What breaks is a specific, ordinary, easy-to-miss habit: fitting a light-tailed family to historical data because it’s the default, without checking whether the tail was estimated or merely assumed. That habit costs nothing when the assumption happens to be right. Proposition 0 makes precise how much it costs when it’s wrong, not a vague “instability,” a specific, checkable overpayment, computed below against this post’s own numbers.
How the robust order quantity is actually built. Das, Dhara & Natarajan don’t estimate a single demand distribution and hedge around it. They define an ambiguity set: every distribution consistent with a small amount of known information, the mean and one higher moment tied to tail weight, and solve for the order quantity that minimizes the worst-case expected cost over that entire set: a minimax problem, not a point estimate. Their result is what makes this post’s claim precise: the distribution that actually realizes the worst case inside that ambiguity set is regularly varying, heavy-tailed, and the minimax-optimal quantity coincides exactly with the classical fractile computed against that worst-case distribution. The robust method isn’t a hedge against heavy tails as one risk among many. It’s provably defending against exactly the heavy-tailed case, which is why a quantity built to survive the worst case in the ambiguity set is automatically heavy-tail-optimal, not heavy-tail-robust as a separate property bolted on.
That’s a narrower, more defensible claim than “fractiles are unstable under heavy tails,” and Definition 0 makes it precise. A capacity computed under a misspecified light-tailed isn’t merely unstable: it fails to minimize , the operator’s actual weighted objective evaluated against the true distribution , even while sitting exactly on the frontier for the distribution it was mistakenly computed against. It’s Pareto-efficient for a world that doesn’t exist, and merely the wrong point on the frontier for the one that does: efficient for a preference weighting nobody actually holds. The classical solution most operators actually compute (a fractile fit to recent observed demand, under an implicit light-tailed assumption nobody examined) is a light-tailed guess wearing the robust answer’s clothing. The two only look the same until the tail event the guess was never built for.
Back to the pool from the opening. Its 32 generation slots are exactly : a capacity number, computed once, from a demand distribution nobody re-examined for tail weight. The generation-length cost that produced the pileup is heavy-tailed: dominated by rare, long reasoning traces, not the millisecond-short-completion case the pool was sized against. was computed correctly, against the distribution that existed the day it was set. The pool filling until nothing else could get in isn’t a separate incident from Proposition 0. It’s the theorem, watched happen: a capacity number, misspecified against a tail nobody measured, failing in exactly the expensive direction the theorem predicts.
Where the Scheduling Version Gets Strictly Harder
The capacity version can always be fixed after the fact: remeasure , recompute , redeploy. The scheduling version can’t. Once a long generation is admitted into a slot, nothing in the story just told takes that slot back. Recomputing more carefully, or picking a better fractile, doesn’t touch that: the binding constraint isn’t the capacity number anymore, it’s a structurally different one sitting downstream of it. This is the Constraint Sequence Framework ’s core invariant, not a narrative complication: you cannot solve a downstream constraint by working harder on the upstream one that exposed it. Whether that downstream constraint is fixable at all, and what secures it if a better can’t, is the question the rest of this post answers formally.
Physical translation. A capacity number lives at the level of “how many,” and every failure at that level has the same fix: measure again, recompute, redeploy. A running task lives at a different level entirely (“which one, right now, holding what”) and no amount of skill at the first level reaches the second. An operator who responds to a sedimented pool by tuning again, more carefully this time, isn’t wrong about the math. They’re solving the wrong layer’s problem: the way re-tuning a thermostat does nothing for a stuck valve.
Definition 1 -- The Blood Oath Constraint: a workload that denies visibility, denies preemption, and denies horizontal escape simultaneously
Definition 1 (Blood Oath Constraint). A workload exhibits the Blood Oath Constraint when three properties hold simultaneously:
- Ingress blindness. Task cost (its true execution duration) is unknown at admission and remains formally unknown until the task completes. What is available in-flight is not a fact but a probabilistic signal. Because task duration is Pareto-shaped, a single, genuinely heavy-tailed population rather than a mixture (Model Scope, below, checks that assumption), a task’s expected remaining duration grows, not shrinks, the longer it has already run: a decreasing-hazard-rate property real for this specific shape, not a property every heavy-tailed distribution shares automatically. This is established for exactly this kind of workload by Harchol-Balter & Downey [3] , who showed UNIX process lifetimes are Pareto-distributed and that elapsed runtime alone predicts remaining runtime well enough to schedule on, without ever needing a job’s true size in advance. Elapsed time is therefore an increasingly reliable, never certain, heavy-task signal, a physical quantity a system can act on directly, unlike the true cost itself, which stays unknown until completion (acting on it means adjusting the task’s resource-accounting class for the system’s own capacity math, not touching the task itself, which Property 2 already rules out).
- Execution immortality. Once admitted, a task cannot be preempted, yielded, or retried. It runs to completion or the node dies with it.
- Locality lock. The workload requires shared-memory cache locality, which forecloses the standard escape hatch of horizontal sharding: you cannot route the problem away from a single node’s boundary. In the case study’s own terms: a generation’s KV cache lives in the accelerator’s own high-bandwidth memory, built incrementally, one token at a time, as the reasoning trace grows. Moving it means moving the entire accumulated cache across a network link that is, categorically, slower than the memory bus that built it. That’s true for standard networking, and true in kind even as RDMA and CXL memory-pooling fabrics narrow the bandwidth gap for tightly-coupled intra-rack configurations, since moving accumulated state across any inter-device link costs strictly more than never having moved it at all. That relocation cost grows with the same elapsed time that made the task worth relocating in the first place. Horizontal sharding is the standard answer to “one node is out of room” precisely because most workloads carry no state worth the move: a stateless request retried against a different replica costs nothing beyond the retry itself. A Blood Oath task inverts that economics by construction. The longer it runs, the more expensive relocating it becomes, at exactly the moment its duration would make relocation most tempting. This describes a real, non-empty category of systems, genuinely locked to a single node’s memory bus with no swap or checkpoint infrastructure behind it. It’s the category this series is built around, not a claim that every LLM-serving deployment necessarily works this way. Real serving engines increasingly ship infrastructure specifically to make mid-generation relocation survivable rather than catastrophic, swapping paged KV-cache blocks to host memory or recomputing them on resumption [4] , at a real, non-trivial cost, but a finite one, not the effectively-infinite one property 3 describes. A workload running on that kind of infrastructure isn’t Blood Oath, and the two shouldn’t be priced with the same formula: relocation that costs real money is a fundamentally different economic object than relocation that’s ruled out by construction.
Any one of these alone is a familiar, solvable scheduling problem. Together, they remove every lever a scheduler normally has. No admission control on cost: you don’t know it, and won’t until completion. No correcting a bad admission after the fact: nothing can be evicted. No spreading the risk across more machines: the data doesn’t move. “Immortal task” is this post’s own term for property 2, it doesn’t appear in the scheduling literature under that name; the formal name for the underlying model is non-clairvoyant, non-preemptive scheduling, addressed directly below.
A natural follow-up: if locality lock somehow didn’t hold (if the KV cache could move for free) would spreading the same traffic across more nodes fix the sedimentation problem? No, and it’s worth showing why rather than asserting it. The heavy-occupancy fraction, normalized to a share, where is the fraction of arrivals that are heavy and their respective mean holding times, the same Little’s-Law occupancy ratio this post computes with real numbers later in this section, has no arrival-rate term in it at all. Double the number of nodes while splitting the identical traffic mix proportionally across them, and every node still faces the same , the same , the same . That’s the same expected occupancy fraction, independently, on every single node. Horizontal scaling multiplies the number of pools sedimenting to roughly 23% heavy occupancy. It doesn’t reduce that 23% on any one of them. This is the quantitative version of what property 3 already rules out by fiat: even in a hypothetical world where locality lock didn’t hold, adding capacity in the wrong shape (more nodes, same per-node traffic ratio) isn’t the same lever as adding capacity in the right shape (more slots per node, fewer heavy tasks per node). Blood Oath’s fragility lives specifically in the second shape, the one horizontal scaling never touches.
What Harchol-Balter & Downey actually measured. The decreasing-hazard-rate claim in property 1 isn’t a theoretical convenience: it’s an empirical finding about real systems. Their study analyzed UNIX process lifetime traces across multiple production and workstation environments and found the lifetime distribution consistently follows a Pareto shape, not the exponential shape classical M/M/1-style queueing models assume by default. The consequence is exactly the property Definition 1 leans on: because the distribution is heavy-tailed, a process’s expected remaining lifetime, given it’s survived this long, grows rather than shrinks with elapsed time, the opposite of the memoryless behavior an exponential assumption predicts. That’s what makes scheduling policies favoring freshly-arrived work over long-running work provably better under real process-lifetime data than policies treating every running task as equally likely to finish soon, the same asymmetry Definition 1b’s crossover time formalizes below. It’s also why shortest-remaining-processing-time-style intuitions generalize so well from the classical, fully-clairvoyant literature to a world with no true job sizes at all. SRPT wants to run whatever finishes soonest, and under a decreasing-hazard-rate distribution, elapsed time alone already tells you which class a task is drawing from, even with the actual remaining time still unknown. The intuition survives losing clairvoyance because the ranking it needs (which task is more likely to finish first) doesn’t require the exact number, only the direction the posterior is moving. Property 1 hands it that for free.
Worth being precise about what a 1997 measurement can and can’t carry into a 2026 claim. Harchol-Balter & Downey measured UNIX process lifetimes: a different generative mechanism entirely from autoregressive token generation. The shape matching doesn’t, by itself, mean the underlying cause matches. What the citation actually earns is the general scheduling argument: for any decreasing-hazard-rate distribution, however it arises, elapsed time predicts remaining time well enough to schedule on, and that argument doesn’t depend on the domain the distribution came from. It doesn’t, on its own, earn the empirical claim that LLM reasoning-trace duration specifically is heavy-tailed. That claim needs its own, more recent evidence, and it exists. A 2025 study fitting extreme value theory directly to LLM response lengths, across 14,301 real completions from GPT-4o and cross-validated against Qwen and DeepSeek, found response-length tails follow a Weibull-type generalized extreme value distribution, heavier under stochastic decoding [5] . Worth being exact about what that does and doesn’t confirm: Weibull-type is the bounded domain in extreme value theory, a finite upper endpoint, not the unbounded Fréchet-type domain an unbounded Pareto tail belongs to. It doesn’t independently confirm this series’ own untruncated Pareto as the exactly-correct functional form. It does independently confirm, from real, model-diverse 2025 data rather than a 1997 analogy, that LLM response lengths are genuinely heavy-tailed and that a bounded ceiling is the empirically right way to model where that tail actually ends, not an untruncated one. The two findings, reached independently, point the same direction.
| Property removed | What it normally lets a scheduler do | Why Blood Oath removes it |
|---|---|---|
| Admission control on cost | Reject expensive work before it starts | Cost is unknown until completion (property 1) |
| Mid-flight correction | Kill or reschedule a bad admission | Nothing can be preempted or evicted (property 2) |
| Horizontal escape | Shard risk across more machines | Shared-memory locality forecloses sharding (property 3) |
The three scheduling levers Blood Oath removes simultaneously, and which of Definition 1’s three properties removes each one.
Physical translation. Most scheduling problems give you one axis to pull: reject expensive work at the door, kill it mid-flight if it turns out expensive, or shard it away from anything else that matters. The Blood Oath Constraint is what’s left when a workload takes all three axes off the table at once, not a harder version of a normal scheduling problem, but a different problem that looks identical from the outside.
Watch out for: treating two-out-of-three as most of the way there. It isn’t: the three properties don’t degrade the achievable region additively, they intersect it. A workload with ingress blindness and locality lock, but where preemption is available, still has an escape hatch: evict the task that turns out heavy, eat the sunk cost, let something else through. A workload with ingress blindness and non-preemption, but where sharding is available, still has an escape hatch: spread the risk thin enough that no single node’s pool sediments even if some of them do. Removing any two of the three still leaves a lever. Proposition A, below, is a claim about all three at once. It says nothing about workloads that only satisfy two, which is exactly why “Compute it,” at the end of this post, asks which of the three actually hold for your system, not whether any do.
Definition 1b -- Prior Confidence and the Crossover Time: pre-classification is a fixed signal, elapsed time is not
Definition 1b (Prior Confidence and the Crossover Time). Suppose ingress is not entirely blind after all. A pre-admission classifier exists, using whatever features are available before execution starts (endpoint, payload shape, caller identity), producing a fixed confidence that a given task is heavy. This does not contradict Definition 1’s blindness property; it refines it. Two signals are now available, and they behave differently over time:
- is fixed at admission. It cannot improve by waiting. It is whatever it is the instant the task is accepted, and no amount of elapsed execution time makes it a better classifier than it already was.
- The elapsed-time posterior is monotonically increasing in , a direct consequence of Definition 1’s decreasing-hazard-rate property, and approaches certainty as grows relative to the light-task timescale.
Because one signal is fixed and the other is unbounded and monotonic, there exists a crossover time such that for all , the elapsed-time-only posterior exceeds : regardless of how good the pre-classifier is. This holds for any fixed .
This is a claim about what happens eventually, not always. Near , right after admission, the elapsed-time signal carries almost no information, and a well-built pre-classifier with strong admission-time features (a reliable payload-size header, a caller known to only submit heavy jobs) can and should beat it outright. The correct reading isn’t “elapsed time is always the better signal.” It’s “elapsed time is the only signal that keeps improving without bound, so no fixed pre-classifier (however good) stays the better one forever.”
Trace example B. The reasoning trace. This is the case study’s own workload, followed through the rest of this post in real seconds: a heavy task drawn from Pareto , competing against light calls that finish in about half a second. Proposition A’s own worked example, further below, resumes exactly this trace.
Worked example. The elapsed-time posterior isn’t an arbitrary curve: it falls out of Bayes’ rule applied to the two task classes already in use throughout this post. Let heavy tasks be the same Pareto used in Proposition 0, and let light tasks be exponential with mean , fast, and memoryless, the wrong model for heavy tasks but the right one for light ones. Let be the population base rate of heavy tasks among all arrivals: a deliberately less extreme here, not the case study’s actual one-in-two-thousand. It’s chosen so the crossover shows up on a readable timescale, rather than requiring the reader to squint at values close to zero. is the same kind of convenience: reused directly from Proposition 0’s demand-quantity example for continuity, not calibrated against the case study’s own heavy-task duration. The case study’s real numbers are worked separately below, not read off this graph’s axis. The mechanism is identical either way; only the numbers on the axis change. Then:
where , and is piecewise to respect the Pareto minimum: a survival probability can’t exceed 1, so it can’t be for below :
where:
- - the probability a task is heavy given it’s still running at
- - the population base rate of heavy tasks among all arrivals
- - the mean duration of a light task
- , - the Pareto minimum and tail index of the heavy class
This is genuinely not exponential-shaped, and it shouldn’t be. That would smuggle a light-tailed assumption into the one signal this post is building specifically to survive heavy tails. Because decays exponentially and decays only polynomially, the ratio inverts sharply, not smoothly: near-zero while both classes look equally likely to still be running, then a fast swing to near-certainty once the light-task timescale is behind it. Solving numerically for gives . A few points along the way:
| Elapsed time | Elapsed-time posterior | Fixed | Which one’s ahead |
|---|---|---|---|
| 0 | 0.020 | 0.30 | : no elapsed-time signal yet |
| 1 | 0.053 | 0.30 | : still well ahead |
| 2 | 0.131 | 0.30 | : closing fast |
| 3 | 0.291 | 0.30 | : barely ahead, crossover imminent |
| 4 | 0.527 | 0.30 | elapsed time, decisively (crossover was at ) |
| 8 | 0.956 | 0.30 | elapsed time, nearly certain |
The elapsed-time posterior overtaking a fixed pre-classifier at : the worked numbers behind the crossover graph above.
A moderate buys three time units of lead before the clock alone would have flagged anything: real value, earned faster than a smooth exponential curve would suggest, because the true transition is a sharp one. Push to 0.6 and moves out to about 4.3; push it to 0.9 and it moves to about 6.75. Lead time scales with classifier quality. It never becomes infinite.
Physical translation. A pre-classifier’s real value isn’t that it out-predicts watching the clock: past the crossover point, it can’t. Its value is lead time: it lets the system act before , during exactly the window where elapsed time hasn’t said anything useful yet. The right design isn’t “pick one signal.” It’s Bayesian combination: start from at admission, update continuously as elapsed time accrues, let the elapsed-time term take over the posterior on its own schedule as it strengthens. A system that trusts only forever throws away the one signal in this problem guaranteed to become arbitrarily reliable. A system that ignores entirely gives up free, immediate signal for no reason, during the exact window it would have mattered most.
In real terms. The graph above uses illustrative parameters chosen for readability, not the case study’s own scale: its values shouldn’t be read as real seconds. Recompute against the case study’s actual numbers: heavy tasks arriving at one in two thousand, light calls averaging s, the same applied to a heavy-task duration with mean s (implying s, this series’ real scale, not the borrowed above for the graph). The crossover lands at s for , s for , s for . All three land well below s. The heavy-task Pareto’s own tail shape isn’t even doing the work yet, since identically for . The crossover here is driven entirely by how fast the light-task exponential decays away, not by anything heavy-tailed. It’s still a fast trigger relative to a five-minute heavy task and any conventional dashboard latency alert: the bare fact that a call hasn’t finished yet becomes a more reliable heavy-task signal than a decent pre-admission classifier within single-digit seconds of execution, for a request whose eventual heavy-classified duration will be measured in minutes.
This crossover argument sits inside a broader, active research area, not a first foray into the question. Learning-augmented non-clairvoyant scheduling studies exactly this shape of problem formally: a fixed or partial prediction combined with an online algorithm that falls back on classical worst-case guarantees when the prediction turns out wrong [6] . That line of work develops the consistency-robustness tradeoff (how much a good prediction helps, how little a bad one costs) with more formal machinery than the worked Bayesian crossover above. Worth being precise about what does and doesn’t survive that context: the argument above is a correctly-derived, concretely-numbered instance of a known pattern, useful for grounding this series’ own specimen, not a claim to be charting new territory in the scheduling-theory literature. It doesn’t change Proposition A below, which targets the strictly non-preemptive case this predictions literature, as far as this post is aware, doesn’t claim to rescue.
Proposition A -- No Competitive Algorithm Exists Without Preemption: this is not a hard instance, it's a formally impossible one
Proposition A (Non-Clairvoyant Impossibility). This is not rhetorical framing. Motwani, Phillips & Torng [7] formalize exactly Definition 1’s first two properties. An algorithm that “only becomes aware of the processing time of a job when the job completes,” under a no-preemption constraint: and prove that no algorithm can achieve any non-trivial competitive-ratio guarantee under these conditions. Allow preemption and the picture changes completely: round-robin recovers a 2-competitive deterministic bound (a result this same paper establishes) and the broader line of work it opened adds a further result on top, preemptive scheduling with randomization reaching -competitiveness. Preemption is not an optimization here. It is the one assumption every worst-case guarantee in this literature depends on, and Definition 1 explicitly removes it.
Proof sketch (adversary argument). The impossibility isn’t shown by exhaustively checking every algorithm: it’s shown by constructing a single adaptive adversary that defeats any deterministic non-preemptive algorithm, whatever it does. The adversary doesn’t fix a job sequence in advance. It watches which job the algorithm is currently running and continuously extends that job’s true length, withholding the information that it’s still growing, for as long as the algorithm keeps running it. Because the algorithm can’t preempt, it has no way to abandon a job that turns out to be a bad bet, every job the adversary chooses to extend is a commitment the algorithm made and cannot revoke. The optimal clairvoyant schedule, by contrast, would have run the genuinely short jobs first and deferred the one the adversary is inflating. The gap between the two grows without bound as the adversary keeps extending, which is exactly what “no non-trivial competitive ratio” means: not merely worse, but arbitrarily worse, for any fixed algorithm the adversary is built to target.
This is the reasoning trace from the case study, run to its logical extreme. The adversary isn’t a hypothetical attacker: it’s what “no natural stopping point” means when nothing bounds how much longer a running task can decide to keep going, and nothing exists to cut it off. The slot the algorithm committed to is exactly the slot in the opening’s pool that filled and stayed filled.
Why one contested slot is enough to condemn a 32-slot pool. The theorem is proven against a single point of contention. One job the algorithm is currently, irrevocably running. A 32-slot pool doesn’t dilute that; it hands the adversary 32 independent targets instead of one, and the adversary only needs to win against a single one to make the algorithm’s worst-case guarantee unbounded. Confine the construction to slot : feed it the ten-short-jobs-behind-one-extending-job pattern above, and feed every other slot only arrivals so trivial they resolve immediately, however the algorithm handles them. The algorithm’s performance restricted to slot ’s own sub-stream is exactly the single-resource instance the cited theorem already rules out. Competitive ratio is a worst-case guarantee over the whole algorithm: the other 31 slots running perfectly doesn’t rescue a guarantee that one arbitrarily bad slot has already broken. This is a standard move in competitive analysis: embed a hard instance of a smaller problem inside a larger one to inherit its lower bound. It’s the actual reason the pool’s own concurrency doesn’t buy safety in numbers.
Trace example B, continued. The reasoning trace from Definition 1b is what the adversary is inflating below: the “job the algorithm has already committed to running” is exactly a heavy task the pool can’t preempt, and the ten short jobs behind it are the ordinary, sub-second calls from the same case study.
Mathematical proof: the adversary's construction, in numbers
Put numbers on the adversary’s construction rather than leaving “grows without bound” as a phrase to trust. Ten short jobs, true length 1 each, sit queued behind a job the algorithm has already committed to running: non-preemptively, because Definition 1 rules out anything else. The adversary, instead of letting that job finish, extends its true length to . Unable to abandon it, the algorithm finishes it at time , then runs the ten short jobs in sequence, completing at :
The clairvoyant optimum, seeing the true length in advance, runs the short jobs first (provably the total-completion-time-minimizing order on a single server, by a standard exchange argument) then the long one last:
| Algorithm | Optimal | Ratio | |
|---|---|---|---|
| 1,000 | 11,055 | 1,065 | 10.4 |
| 10,000 | 110,055 | 10,065 | 10.9 |
| n/a | n/a | 11 (exactly for waiting jobs) |
The adversary’s competitive-ratio gap against ten waiting jobs, growing without bound as the inflated job length increases, converging to exactly 11.
Ten isn’t special. Queue twenty short jobs behind the same trick and the ceiling moves to 21. Fifty, and it moves to 51. Whatever competitive ratio an algorithm claims to guarantee, the adversary picks a number of waiting jobs greater than and an extension large enough to realize it. That’s what “no non-trivial competitive ratio” cashes out to in numbers: not a bad ratio, a ratio with no ceiling, because the adversary picks the ceiling after seeing what the algorithm is trying to promise.
Why preemption changes the bound, not just the difficulty. The worked example’s trick has one specific mechanical requirement: the algorithm must be unable to interrupt whatever job it’s currently running. Round-robin defeats that requirement directly. Give every active job a small time slice and cycle through all of them, and no single job (however long the adversary tries to make it) can hold the server for more than its fair share of any window. The ten short jobs above never wait behind the full length of the extended one; they wait behind, at most, a bounded number of round-robin slices: exactly the mechanism that caps round-robin’s competitive ratio at 2 for total completion time, no matter how large gets. Randomization does better still. Algorithms in this space reach -competitiveness by spreading their choices across possible job orderings instead of committing to one fixed rotation, which makes it structurally harder for even an adaptive adversary to reliably target whatever the algorithm is about to do next. Both results depend on the one ingredient Definition 1 rules out: neither bound exists without the ability to stop running a job before it finishes.
Physical translation. There is no clever admission policy waiting to be discovered here, because the theory that would house it proves none exists. Preemption doesn’t just make the impossibility more expensive to overcome. It removes an entire face from the achievable region, the same way CAP and FLP remove faces rather than draw threshold cuts. Every point corresponding to a non-trivial competitive-ratio guarantee isn’t merely hard to reach without preemption: it’s not in the achievable region at all. The impossibility isn’t a rhetorical flourish. It’s the actual reason the fix has to be structural (change what you’re allowed to do to a running task, change what backpressure is allowed to look at) rather than algorithmic (find a smarter rule for which tasks to admit).
Where This Sits Against Familiar Mitigations
Three tools get reached for before anyone accepts that Proposition 0 and Proposition A actually apply. Worth naming precisely why each one misses.
Finding. All three assume a failure can be caught before it’s expensive, or undone after. Blood Oath removes both assumptions by construction, so none of the three ever had traction here.
| Mitigation | What it actually does | Why it misses |
|---|---|---|
| Circuit breaker | Rejects new admissions once tripped | Detects the pool filling; can’t evict what’s already running |
| Rate limiter | Throttles all traffic by a fraction | Can’t selectively throttle heavy traffic: cost is unknown at ingress |
| Retry budget | Counts failed attempts | Blood Oath tasks never fail and retry: the counter never moves |
Why the three most-reached-for mitigations each fail against a Blood Oath workload, despite working correctly on their own terms.
Circuit breakers classically trip on an error signal: a rising failure rate past a threshold. Production systems worth trusting also trip on latency degradation and queue dwell time: CoDel-style active queue management, p99-based load shedding. That distinction matters here, and it would be wrong to pretend otherwise. A 32-slot pool pinned by reasoning traces absolutely degrades admission latency, and a well-instrumented latency-based breaker would trip on it sooner than an error-based one ever could. Even at the case study’s own ordinary baseline (the roughly 23% heavy occupancy this post derives from Little’s Law [8] later in this post, not the surge that turned it into an incident), a latency-based breaker watching admission wait times has a real, standing signal to calibrate against, where an error-based one has nothing to see until the pool is already saturated. But what tripping buys is narrower than it sounds. Tripping means rejecting new admissions, failing fast instead of queueing silently. It doesn’t free a slot. Nothing in Definition 1 gives a breaker, however well-instrumented, a way to evict a reasoning trace already running. The pool stays pinned until those traces finish on their own, breaker tripped or not. And “the queue just absorbs the load” was never really an escape either: queue depth is bounded by physical resources whether anyone declares a limit or not, so the failure a breaker exists to catch happens somewhere regardless, cleanly, at the breaker, or one layer down, once the queue exhausts file descriptors, ephemeral ports, or physical memory. The honest version of this claim isn’t “no failure is ever observable.” It’s that detecting the problem, however early, doesn’t undo the admission that caused it. Thirty-two successful, entirely healthy admissions are still holding a resource nothing can take back.
Rate limiters cap arrival rate, on the theory that slowing admission protects whatever’s downstream. But the case study’s problem was never arrival volume: 99.95% of what arrived was cheap and harmless. A rate limiter admits at ingress, before cost is known (Definition 1, property 1), so it can’t selectively throttle heavy traffic, only all traffic, uniformly, by some admitted fraction . Suppose heavy-task arrivals surge by a factor (the case study’s own “three or four reasoning traces landing close together,” generalized) while light-task arrivals hold steady. To keep heavy occupancy at its pre-surge baseline, the limiter needs , i.e. . At a 10x heavy surge, that means admitting only 10% of all offered traffic, rejecting 90%, the overwhelming majority of it harmless load the pool was never in danger from. At a 20x surge: admit 5%, reject 95%. The limiter can hold the line, but only by treating nearly everything as guilty to catch the rare guilty party it can’t actually identify. Loosened enough to let the healthy majority through, it no longer holds the line at all. It only delays the moment the pool sediments, since the underlying dynamic doesn’t care about absolute arrival rate, only the ratio of offered heavy load to capacity. And a rate limit is, structurally, just another . It inherits Proposition 0’s exact fragility, computed against a distribution nobody re-examined for tail weight.
Retry budgets cap how many times a failed request gets retried, to stop retry storms from amplifying an outage: reject the 11th retry in a rolling window, say, rather than let every client keep hammering a struggling downstream. Blood Oath’s tasks don’t fail and get retried. Property 2 rules retry out entirely. A task runs once, to completion, or the node goes down with it, and there’s no failed attempt for a budget to count against. Point a retry budget at the case study’s incident and watch what it does. The thirty-two reasoning traces holding their slots never fail, so the counter never increments, so the budget never trips, so nothing happens, not because the mitigation was configured wrong, but because the event it watches for structurally cannot occur here. A retry budget is solving a real problem that simply isn’t this one. Applying it here doesn’t fail loudly. It just does nothing: a worse failure mode than an error, because nothing signals the tool never had traction to begin with. An on-call engineer checking dashboards mid-incident sees a healthy, zero-triggered retry budget and reasonably concludes that layer is fine. Exactly backwards: a layer that structurally cannot see the problem is not the same thing as a layer confirming there isn’t one.
All three assume either that failure is observable before it’s expensive, or that a bad admission can be undone. Definition 1 rules out both assumptions by construction. This isn’t a case for better tuning any of the three. None of them were ever the right category of tool.
Would a Centralized Scheduler Change Any of This?
Worth answering before this series builds a single mechanism, because the answer draws a line the rest of the series has to respect. Give the admission decision to one logically-central authority, with a perfect, real-time, zero-staleness view of every task and every node: does Proposition A’s impossibility bound move?
It doesn’t, and the reason matters. Proposition A’s adversary exploits a specific fact: a task’s true execution duration is unknown at admission and stays unknown until completion: Definition 1’s own first property, ingress blindness. That’s an information problem about the future. A centralized scheduler, however perfectly it knows current state (every queue depth, every slot, every headroom fraction, zero lag) still doesn’t know how long a task about to be admitted will actually run. The adversary’s construction (extend whichever job the algorithm is currently running, since the algorithm can’t abandon it) works identically whether the algorithm computing “which job is currently running” lives on one central machine with a global view or is smeared across a fleet with stale local views. Centralizing the observation of present state does nothing to the prediction of future state. Proposition A’s bound is a statement about prediction, not observation.
Centralized-versus-decentralized architecture is worth comparing for exactly the class of problem where the distinction matters, because most of what this series builds is an observation problem, not a prediction one: how much headroom does a node have right now, which of N nodes is closest to its own limit right now, has a redline been crossed right now. Those are staleness problems, and architecture genuinely changes the answer to them. Proposition A is not one of those, and no such comparison should be read as bearing on it. The two failure modes this series calls “imperfect information” aren’t the same failure mode. Conflating them is the single easiest way to overclaim what any architectural fix (centralized, decentralized, or hybrid) actually buys.
Model Scope and Failure Envelope
Five assumptions are doing work in this post that deserve to be named rather than left implicit.
| Assumption | What could break it | Status |
|---|---|---|
| Cost is a single scalar (duration) | A task cheap in duration but expensive on a different, uninstrumented resource | Named gap: the vector-valued generalization this would need isn’t built here |
| The true demand distribution is stationary | A regime change, a seasonal shift, a genuine drift in the workload | A different failure mode than the one this post proves, left open |
| Proposition A rules out the worst case | The statistically ordinary case that reaches saturation without any adversary | Real: 23% baseline occupancy, formalizing exactly where it tips into an incident is a distinct, unresolved question |
| Arrivals are independent enough for rate-and-duration quantities to be well-defined | A correlated upstream trigger driving many arrivals at once | Named gap, not resolved |
| The heavy class is one clean Pareto population | A real mixture of distinct workload types, each with its own characteristic duration | Checked directly: the crossover claim survives, the finer-grained machinery downstream of it does not |
Five assumption boundaries this post depends on, in the order the paragraphs below name them.
Cost is treated as a single scalar. Definition 1’s “true cost” is duration, and Proposition 0’s newsvendor framing collapses underage/overage into two dollar figures. Real workloads often spend multiple resources at once (CPU time, memory, network) and a task cheap on one axis can be expensive on another. The case study’s own 32-slot pool is already a mild simplification here: what actually binds is VRAM, and duration is a proxy for VRAM occupancy: accurate in this case because a generation never releases any of its KV cache early, so time-in-slot and time-holding-memory are the same clock. That proxy relationship isn’t guaranteed for every workload. A task could be short in duration but memory-hungry throughout, or long-running but nearly idle on the resource that’s actually scarce, and Definition 1’s single scalar has no vocabulary for that mismatch. This post’s model is the single-resource simplification on purpose, named here as exactly that: a task cheap in duration but expensive on a different, uninstrumented resource is invisible to everything this post builds. The vector-valued generalization that vocabulary would need (“heavy” as more than a scalar, the binding resource shifting depending on what else runs concurrently) is a real gap, not a hedge.
Proposition 0 assumes a stationary true distribution, misspecified or not. It says nothing about itself drifting over time: a regime change, a seasonal shift, a genuine change in the underlying workload. A capacity number can be exactly right for a stationary and still go stale the moment the world it was fit to stops holding still. That’s a different failure mode from the one this post proves, not a smaller version of it. Proposition 0 and Proposition A both reason about a fixed ; neither re-checks whether is still the distribution actually in effect. A capacity number computed once and defended forever inherits that blind spot by construction.
Proposition A rules out worst-case guarantees, not average-case ones. Easy to blur, and it matters. No non-preemptive algorithm can guarantee good performance against an adversary free to construct the worst possible input: a contrived, per-task adaptive construction, more extreme than anything the case study needed. That’s not the same claim as “every non-preemptive system fails on every real workload.” But the case study’s failure isn’t luck either: once offered load from heavy tasks alone (arrival rate times mean holding time) approaches the pool’s capacity, sedimentation is the expected steady-state outcome of Little’s Law, not a rare coincidence of timing. Put numbers to the case study’s own description, heavy tasks arriving at roughly one in two thousand, light tasks finishing in about half a second, heavy ones holding a slot for about five minutes, and Little’s Law gives an expected steady-state heavy occupancy of about 23%: real, persistent sedimentation, but not yet an incident on its own. What turns an ordinary day into an incident is a rate increase pushing that occupancy toward saturation, not an adversary and not bad luck. Proposition A explains why no algorithm can promise safety in the worst case. Formalizing exactly where that threshold sits (not the adversarial case, the statistically ordinary one that gets there anyway) is a distinct, narrower question this post leaves open.
Task arrivals are treated as regular enough for the underlying rate-and-duration quantities to be well-defined. Nothing here examines whether a surge like the case study’s is itself correlated with something upstream. The same upstream trigger (a new agentic workflow rollout, a batch of related requests) driving many correlated reasoning traces at once isn’t obviously the same statistical object as independent arrivals at an elevated rate, and this post doesn’t distinguish between them. A real, named gap, not resolved by assuming it away.
The heavy class is treated as a single Pareto population, and a real fleet’s own “heavy” traffic is rarely that clean. Harchol-Balter & Downey’s finding, grounding property 1, is real and specific to what they measured: UNIX process lifetimes, one population, genuinely Pareto-shaped. A production fleet’s heavy traffic is more often a mixture of distinct workload types stacked together (a different tenant’s batch job, an automated report generator, a multi-step agentic loop) each with its own comparatively narrow characteristic duration, not a single smooth tail. That matters because a mixture of well-separated, low-variance sub-populations doesn’t, in general, inherit a single population’s clean decreasing-hazard shape. Worked concretely: mixing three quasi-deterministic sub-populations at characteristic lifetimes of 200s, 800s, and 2000s (weights 0.5/0.3/0.2, each with a modest 15% coefficient of variation around its own mean) produces a population hazard rate that rises, falls, rises again, and falls again before finally settling: four genuine reversals, not the single smooth decline a pure Pareto gives.
Finding. Definition 1b’s own crossover claim survives this intact. The finer-grained machinery built downstream of it does not.
Why the crossover claim survives. only has to resolve a coarse, two-class distinction (heavy versus light) and light decays on a sub-second timescale here, so the posterior saturates toward certainty well before any internal structure in the heavy class’s own hazard has a chance to matter. Checked directly against the three-component mixture above, at this post’s own , worked-example parameters: the posterior crosses exactly once, at , and never dips back below it: regardless of the heavy class’s own internal wiggling three hundred seconds later.
What does not survive. Computing how much longer a task already known to be heavy is expected to run operates inside the heavy class, and that quantity is exactly what a mixture’s internal structure can make genuinely non-monotonic:
| Elapsed time | Mean residual life |
|---|---|
| 50s | ≈690s |
| 150s | ≈602s |
| 300s | ≈978s |
| 700s | ≈671s |
| 1,000s | ≈928s |
Mean residual life under the three-component mixture model: four non-monotonic reversals a single, pure Pareto tail wouldn’t produce.
Four reversals in a quantity a real system would use to decide whether a task is still worth waiting on. Whether a real fleet’s own heavy traffic is close enough to unimodal for that kind of machinery to apply as stated, or genuinely splintered enough that it needs measuring (a multimodal check on the empirical duration distribution, not just a tail-index estimate), is named here as the assumption this post’s own property 1 rests on. It is not resolved here.
flowchart TD
A["Does the workload have
ingress blindness?
(cost unknown until completion)"] -->|No| Z1["Ordinary scheduling problem:
admission control on cost works"]
A -->|Yes| B["Can a running task
be preempted or evicted?"]
B -->|Yes| Z2["Ingress blindness alone:
known mitigations apply, no need
for this series' own machinery"]
B -->|No| C["Does the workload need
shared-memory locality?
(no horizontal escape)"]
C -->|No| Z3["Ingress blindness + non-preemption:
Proposition A's territory,
but sharding can spread the risk"]
C -->|Yes| D["All three Blood Oath properties hold."]
D --> E["Proposition A applies: no admission
algorithm can bound the loss.
Stop looking for a smarter rule.
The fix has to be structural."]
Four questions to check against a real workload: whether it hits all three Blood Oath properties at once, or drops out early into a cheaper, conventional fix.
Compute it. Nothing here is a scheduling tip. Proposition 0 is a theorem about capacity, Proposition A is a theorem about algorithms, and together they rule out both answers an experienced engineer reaches for first: a better-tuned number, and a cleverer rule. Before trusting either on a real system, run the actual checks this post derived, not the intuitions that usually stand in for them.
- Was fit against the real tail? Pull the distribution your current was fit against. Was tail weight, not just mean and variance, ever estimated, or was implicitly fit under a light-tailed assumption nobody stated out loud? If nobody can answer that, assume the light-tailed case and treat the current as a guess wearing the robust answer’s clothing.
- Does the workload actually have all three Blood Oath properties, or only some? Ingress blindness alone is an ordinary scheduling problem with known mitigations. Ingress blindness plus non-preemption is Proposition A’s territory. All three together, including the locality lock ruling out horizontal escape, is the specific combination this post’s entire argument turns on.
- If all three hold: stop looking for a smarter admission rule. Proposition A already proved none exists; a structural fix (changing what’s allowed to happen to a running task, not computing a better threshold) is the only category left.
- If only one or two hold: the fix may be cheaper than this series’ full machinery. A workload with ingress blindness, but where preemption is available and the task’s own accumulated state can genuinely be relocated rather than only discarded, doesn’t need Proposition A’s response at all. Pricing that cheaper fix properly is a different, strictly easier problem than the one this post’s own non-preemptive machinery solves.
Exactly where this post’s case study crossed from ordinary sedimentation into an incident, and what a structural response actually costs to run, are questions this post leaves open. Knowing which of these four checks your own system fails is something to establish before those questions matter, not after.
What This Post Actually Proved
Two theorems, not one, and it matters that they’re separate. Proposition 0 is about a number: given a demand distribution, however it behaves, there is a single correct capacity, and the classical machinery for finding it has never been broken. What breaks is the finite-sample habit of fitting the wrong family to it. A mistake ordinary sampling noise makes for free and heavy tails punish specifically. Nothing about that theorem is new; Arrow, Harris & Marschak closed it in 1951. What’s new here is showing exactly how much a light-tailed guess costs when the world underneath it is heavier than assumed, not “unstable,” a number: checkable at 24.5% over the true optimum, on a structural shape error rather than a magnitude one. Even a perfectly-estimated mean cannot save you from it.
Proposition A is about something the first theorem cannot see. Once “how much capacity” becomes “which arriving task gets the capacity,” a workload can acquire three properties (ingress blindness, execution immortality, locality lock) that together aren’t a harder instance of the same problem. They’re a different problem, one where no admission algorithm, however clever, can promise a bounded loss against the worst case. Not a weak guarantee. No guarantee: the gap unbounded, verified above with an adversary that needs nothing but the freedom to keep extending whichever job is currently running.
The Constraint Sequence Framework is why both theorems had to be proven, not just one. A team that only knew Proposition 0 would respond to the case study’s incident by re-fitting , watch the pool sediment again on the next reasoning-trace surge, and conclude the fractile needs even more margin: chasing a capacity number that was never the binding constraint once a task got admitted. A team that only knew Proposition A would conclude no algorithm can help and stop looking for structural responses too, missing that Definition 1b’s crossover time is itself a real, physical signal a non-algorithmic response could act on, not just a proof of impossibility. Both theorems are required before “add backpressure, not a smarter admission rule” is a conclusion rather than an assertion. That’s the Constraint Sequence Framework’s own point, applied to itself: neither result, alone, would have sequenced correctly to the fix.
What this post proves is where the number stops being enough, and where no algorithm can rescue what’s left. No safe number exists for a workload with all three Blood Oath properties. That claim is proven, not asserted: an adversary construction and a closed-form fractile, both checked against real numbers rather than left symbolic.
Cognitive Map
- Provisioning by precedent (trusting a number because it has always worked) is exactly the property that stops being informative the day a heavy tail finally tests it. Proposition 0 proves precisely where the stability ends: a light-tailed can run 24.5% over the true robust optimum, not from bad luck but from fitting the wrong distributional family to begin with.
- Definition 1 names three properties (ingress blindness, execution immortality, locality lock) that, together, remove every lever a scheduler normally has: no admission control on unknown cost, no correcting a bad admission after the fact, no spreading the risk across more machines.
- Definition 1b shows a fixed pre-admission classifier is real, useful lead time, not a permanent edge: an elapsed-time posterior overtakes any fixed confidence eventually, because one signal keeps improving without bound and the other doesn’t.
- Proposition A proves the three Blood Oath properties together aren’t a harder version of ordinary scheduling. They’re a different problem: no admission algorithm, however clever, can promise a bounded loss against the worst case: verified with an adversary that needs nothing but the freedom to keep extending whichever job is currently running.
- The Constraint Sequence Framework is why both theorems had to be proven, not just one: a team that only knew Proposition 0 keeps re-fitting a number that was never the binding constraint; a team that only knew Proposition A stops looking for the structural response that’s actually available.
- No safe number exists for a workload with all three properties. What replaces the number is a structural response, not a smarter admission rule: a category of fix, not a specific mechanism this post itself derives.
- Property 1’s decreasing-hazard-rate claim leans on two separate pieces of evidence for two separate jobs. A 1997 UNIX process-lifetime study earns the general scheduling argument: elapsed time predicts remaining time, for any decreasing-hazard-rate distribution. A 2025 extreme-value-theory study fitting real LLM response lengths earns the domain-specific one: this workload’s own duration is genuinely heavy-tailed, not by analogy to a different generative process.
[1] Arrow, K.J., Harris, T. & Marschak, J. (1951). Optimal Inventory Policy. Econometrica, 19(3), 250–272.
[2] Das, B., Dhara, A. & Natarajan, K. (2021). On the Heavy-Tail Behavior of the Distributionally Robust Newsvendor. Operations Research, 69(4), 1077–1099.
[3] Harchol-Balter, M. & Downey, A. (1997). Exploiting Process Lifetime Distributions for Dynamic Load Balancing. ACM Transactions on Computer Systems, 15(3), 253–285.
[4] Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C.H., Gonzalez, J.E., Zhang, H. & Stoica, I. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention. Proceedings of the 29th Symposium on Operating Systems Principles (SOSP 2023).
[5] Jiao, L., Gao, C., Yang, Y., Zhou, C., Huang, Y., Chen, X. & Li, Y. (2025). Analyzing and Modeling LLM Response Lengths with Extreme Value Theory: Anchoring Effects and Hybrid Distributions. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing (EMNLP), 32992–33002.
[6] Lindermayr, A. & Megow, N. (2022). Permutation Predictions for Non-Clairvoyant Scheduling. arXiv preprint.
[7] Motwani, R., Phillips, S. & Torng, E. (1994). Nonclairvoyant scheduling. Theoretical Computer Science, 130(1), 17–47.
[8] Little, J.D.C. (1961). A Proof for the Queuing Formula: L = λW. Operations Research, 9(3), 383–387.