Koi: Evidence-Guided, Self-Calibrating Planning for Multi-Cloud, Heterogeneous LLM Inference Fleets
Mankeerat Sidhu, Gangmuk Lim, Hetarth Chopra, Maximillian Eisenberg, Quan Hao Ng, Aryan Gosaliya, Shu Liu, Luka Govedič, Jiaxin Shan, Hongkuan Zhou, Vikram Sharma Mailthody, P. Brighten Godfrey, Ion Stoica
cs.DC, cs.AI
2026-10-17
Koi plans heterogeneous LLM inference with a causal graph and deterministic scoring. On 104 GPUs it delivers 1.18× the best baseline's goodput and 20% lower cost per token.
An inference provider mixes online chat and batch jobs on accelerators spread across clouds, hardware generations, and reserved, on-demand, or spot markets. Each job has about 140 knobs. The per-job floor is 2^140 configurations, and a cluster plan must pick one deployment per job under a shared pool, then recompute it as jobs come and go.
The spread is already large for one job. Llama 3 70B on AWS A10G GPUs, with 2,048 input tokens and 512 output tokens, has five feasible tensor- and pipeline-parallel layouts. They differ by 4.4× in throughput and 7.5× in cost per token. TP4/PP2 across two four-GPU machines serves that run at 180 tok/s for $0.97. TP8/PP1 on one eight-GPU machine reaches 162 tok/s for $2.16. Prefill-heavy traffic stresses compute. Decode-heavy traffic stresses memory bandwidth and the KV-cache. An engine update moves throughput again, so a profile taken once goes stale.
Giving each arrival the best free device wastes scarce GPUs. A batch job that can still hit its deadline on A100s may take the only H100, and the next online job misses latency. Engines, multi-cloud placers, single-model tuners, and request routers each own one layer. No layer both chooses the deployment and splits capacity across every online and batch job.
Predictors do not close that gap. A roofline model calibrated with measured peak compute and bandwidth misses by up to 4.7×. Claude Opus 4.8 and GPT-5.6 Sol over-predict throughput by 4× and 9×. Bayesian optimization and evolutionary search see only an end-to-end score, so they cannot separate a pipeline bubble from KV-cache pressure, and every trial occupies production GPUs.
Koi is a deployment control plane. It does not retune how requests are batched. A deployment change loads weights, warms caches, and drains in-flight work, so the number of live trials is small. The serving deployment is the experiment: it tests the causal edges it actually exercises, and search does not get a private GPU pool.
The graph is fixed at startup. Decisions point only at mediators, and mediators point at outcomes. Decisions cover accelerator, parallelism, quantization, and batch size. Mediators cover KV-cache pressure, pipeline bubbles, communication, and memory pressure. Outcomes are latency, throughput, and cost. The same throughput drop calls for a different knob if the cause is bubbles or a full cache. The mediator is what tells the planner which knob to move.
Each edge keeps a Beta belief. Support increments alpha, contradictions increment beta, and confidence is alpha/(alpha+beta). A separate uncertainty score sends poorly observed edges to the front of the queue. A mechanism is one registered path plus a scope over model, hardware, and traffic shape. An update revises the mechanism, so another job inside that scope can reuse the evidence.
Every five minutes a budget book limits which GPU pools a job may consider. A per-job sub-agent walks the graph back from the latency or deadline target and proposes a few candidates. A profile surrogate predicts latency and throughput. Missing profiles borrow the nearest measured architecture and rescale by prefill and decode speed ratios. The plan score is exploitation minus breach risk and switching cost, plus exploration. Exploitation penalizes the worst weighted gap among five objectives, so a healthy average cannot hide one broken target. Candidates above the risk threshold are dropped, and only a capped number of live jobs may change deployment in one tick. The language model may propose again. It cannot rewrite scores or override memory fit, parallelism constraints, or quota. Residuals have to accumulate in one direction before the exploration weight and the error band move.
The mix is 25 online and batch workloads across ten models, from 1B to 235B parameters, dense and MoE. The real run is three hours on 104 GPUs in three GCP regions: H100-80GB, A100-80GB, A100-40GB, and RTX PRO 6000. Simulations use a 400-GPU cluster for three hours and an 800-GPU cluster for twelve hours. LLMServingSim 2.0 executes the simulations and is separate from the planner's internal surrogate. Language-model policies all use GPT-5.6-Luna. The composite score is the geometric mean of quality, coverage, and efficiency. Goodput counts only tokens that meet the SLO, and idle GPUs still count as cost.
Cost kept the real cluster to three baselines. OpenEvolve is the strongest.
| Method | goodput (tok/s) | $/token (×10⁻⁴) | TTFT met | TPOT met | score |
| Contextual bandit | 2291.03 | 0.45 | 22.23% | 33.66% | 51.05 |
| Rolling EvoX | 2348.15 | 0.44 | 28.08% | 35.48% | 54.90 |
| OpenEvolve | 3497.43 | 0.30 | 65.66% | 91.41% | 84.44 |
| Koi | 4119.51 | 0.24 | 79.05% | 99.11% | 94.50 |
4119.51 versus 3497.43 tok/s is 1.18× OpenEvolve. Cost falls from 0.30 to 0.24, a 20% cut. Koi admits every online and batch job, and batch progress is 100% versus 75%. TTFT attainment is 13.4 points higher, TPOT 7.7 points higher.
On the three-hour, 400-GPU simulation the strongest baseline is Rolling EvoX. Goodput is 2,911 versus 2,004 tok/s, up 45%. Cost per token is 1.85×10⁻⁴ versus 2.69×10⁻⁴, down 31%. Batch progress is 84.6% versus 57.7%. TTFT attainment is 28.8% versus 9.9%. The composite score is 70.8 versus 54.3.
Over twelve hours on 800 GPUs, goodput is 3,184 versus 3,012, up 5.7%. Cost is 3.39 versus 3.37 (×10⁻⁴), 0.59% higher. Batch progress is 49.6% versus 50.7%. Online admission is 95.7% and batch admission is 100%. TTFT and TPOT attainment stay ahead by 16.0 and 11.8 points. The composite score is 63.1 versus 50.0. On that trace Koi swaps 201 times and keeps a placement 2,076 times; EvoX swaps 1,464 times and the bandit 1,928. Median causal uncertainty falls from 0.0215 to 0.00053.
Ablations on the three-hour simulation score a bare language model at 35.3, the same model plus deterministic tools at 51.6, and full Koi at 70.8. Tools move goodput from 856 to 1,827 tok/s. Removing the causal graph leaves 1,770. Freezing online updates leaves 1,621.
Opportunity cost shows up only when configuration and placement are one decision. At tick 18 on the real cluster a Qwen3-235B job is waiting. The only reclaim would cut a Phi-4 service from two TP2 replicas on RTX PRO 6000s to one, dropping modeled throughput from 1,572 to 786 tok/s against a need of 834, while p99 TTFT is already 645 ms versus a 500 ms target. Koi refuses the reclaim and admits the waiting job at tick 20, after capacity frees on its own.
The same model moves from 35.3 to 70.8, with 51.6 once deterministic tools are added. A different backbone can still swing the trace. Cohere and GPT-5.6 Sol differ by one 7,200-request Llama-70B batch job that accounts for 99.3% of their goodput gap, about 8.64 million tokens. Cohere finishes on one eight-GPU MI300 TP8 chain with 82 minutes of slack. Sol runs four TP4 A100 replicas on 16 GPUs and is 85 requests short at the deadline. Online tokens differ by 57,921. Validation rejects illegal plans. It does not make every legal plan equally useful.
The 1.18× goodput and 20% cost cut are the 104-GPU, three-hour run against OpenEvolve. The 45% and 31% figures are the three-hour simulation against EvoX. Online jobs run under Nvidia Dynamo, with Koi setting the replica cap.
On the twelve-hour simulation the goodput lead shrinks to 5.7%, cost is 0.59% worse, and batch progress trails EvoX by 1.1 points. Simulated TTFT attainment for Koi is about 28%, against 79% on the real cluster. Hardware and workloads differ, and the paper does not split that gap out.
Near-optimal proposal coverage, and convergence once conditions stay stable, are assumptions. Search is budgeted, so the committed plan is the best one found in that tick. Edges are frozen at startup, and the model cannot add a mechanism outside the graph. On the longer run, the share of decisive tests that support the predicted path rises from 1.9% to 19.1%, and invariant causal prediction acceptance rises from 11.0% to 63.3%. The evidence gets thicker. Most tests still miss the mechanism they were meant to check.
The real cluster did not run FCFS, CP-SAT, Prism, or GPT-only. The backbone comparison is a single run in which accelerator, parallelism, and replication change together, so the 99.3% cannot be pinned on one factor. Planner language-model spend is described as reported separately, and no dollar figure is given.