When query demand spikes on a fixed-size cluster, an inference-serving system cannot buy more GPUs — but it can quietly swap models for smaller siblings that answer faster and slightly less accurately; Proteus makes that trade precise by jointly optimizing which model variants to run, which heterogeneous device each one lives on, and what fraction of each application's queries goes where (a mixed integer linear program solved OFF the critical path), plus a batching algorithm that deliberately lets a device sit idle to accumulate fuller batches — cutting worst-case accuracy loss about 3× and deadline violations 2.8–10× against state-of-the-art serving systems, validated on a production enterprise cluster.
The argument in one glance
-
Problem
Demand moves; the cluster cannot
An inference-serving system runs trained models behind an API, promising each application a latency deadline (a service level objective, SLO) while trying to serve as many queries per second as possible. The standard answer to rising demand is hardware scaling — add devices, or buy faster ones. But an enterprise's private cloud and an edge site's rack are FIXED: provisioning for the daily peak means paying for hardware that idles most of the day, and not provisioning means the peak brings timeouts and dropped requests. Demand routinely swings by large factors within hours (diurnal patterns, bursts), and the hardware stands still.
-
What people did
Scale the model instead of the metal
Every model family ships in sizes: ResNet-18 through ResNet-152, EfficientNet b0 through b7, BERT-tiny through BERT-large. Smaller variants answer faster and slightly less accurately — on a GTX 1080 Ti, choosing among five EfficientNet variants spans a 3.3× throughput range against roughly 8 accuracy points. Accuracy scaling exploits this: under load, serve some queries with cheaper variants; when load ebbs, restore the accurate ones. Sommelier swaps variants on a single server; INFaaS selects and places models dynamically with greedy heuristics.
-
Why it fell short
Partial solutions leave most of the trade on the table
The configuration space is brutal: with M variants and N heterogeneous devices there are M-to-the-power-N ways to stock the cluster, each variant performs differently per device type, and multiple applications compete for the same pool. Sommelier scales accuracy but cannot move models across the cluster — 16% worst-case accuracy drop. INFaaS moves models but decides GREEDILY, because its allocation logic sits on the critical path of every query and has no time for anything better; the heuristic gets stuck in local optima and bleeds throughput exactly at the peaks. Static systems (Clipper, TensorFlow-Serving, Triton) split the impossible choice: pin accurate models and violate deadlines 10× more, or pin fast models and eat a permanent 20% accuracy loss.
-
This paper's idea
Solve the whole trade exactly — just never on the critical path
Proteus (UMass Amherst and Nokia Bell Labs) formulates the three coupled sub-problems — model selection, model placement on heterogeneous devices, and query assignment fractions — as one mixed integer linear program that maximizes average served accuracy subject to meeting demand. The trick that makes exact optimization affordable is timescale separation: the solver (4.2 seconds on average) runs asynchronously on MACRO-scale demand changes, every 30 seconds or on detected bursts, while the data path serves queries through a routing table lookup of less than a millisecond. MICRO-scale arrival jitter is absorbed per device by a proactive, non-work-conserving batching algorithm that waits until the last safe moment to execute, accumulating fuller batches. On a production enterprise cluster (20 CPU, 10 GTX 1080 Ti, 10 V100 workers) replaying a Twitter trace, Proteus holds worst-case accuracy drop to 4.85% — 2.8× better than INFaaS, 3.2× better than Sommelier — with 2.8–10× fewer SLO violations than every baseline, and 60% more throughput than serving without accuracy scaling.
Why this problem is worth solving
Inference serving is the checkout counter of machine
learning: applications send queries — classify this image,
translate this sentence — and expect answers both fast and
good. The operator promises each application an
a service level objective — here, a latency
deadline per query. A response arriving after its deadline
is often worthless (a recommendation for a page already
rendered, a perception result for a vehicle that has moved),
so systems count SLO violations — the fraction of queries
answered late or dropped — as a first-class failure metric,
alongside throughput in queries per second
The paper’s position is that the third option, done
carefully, dominates —
adapting the accuracy of the
models rather than the amount of hardware. Model families
provide the mechanism: variants built by architecture design,
quantization (using lower-precision numbers), or pruning
(removing weights) trade accuracy for speed along a smooth
curve. The system’s quality is then measured as EFFECTIVE
accuracy — the average accuracy of the variants that actually
served each query — which dips during peaks and recovers
after, instead of deadlines being missed
What people did before, and where it broke
- Static serving (Clipper; representative of TensorFlow-Serving and NVIDIA Triton). Load a fixed set of models and keep them. Pin the accurate variants (Clipper-HA) and peaks halve your throughput while violations soar; pin the fast variants (Clipper-HT) and you pay a permanent 20% accuracy drop for headroom you rarely need. The developer, not the system, owns the trade.
- Single-device accuracy scaling (Sommelier). Swap a model for a cheaper sibling when a server is overloaded — but no cluster-level view, so models never MOVE to where they would serve best. Worst-case accuracy drop: 16%.
- Dynamic heuristics (INFaaS). Selects and places models as demand shifts — but its allocation decisions execute on the critical path of query arrival, so they must be fast, so they are greedy. Greedy gets stuck: at demand peaks INFaaS loses throughput and multiplies violations, and its best-case accuracy drop (13.7%) is still nearly 3× worse than optimal.
- Prior batching algorithms. Clipper adapts batch size reactively (grow until timeouts happen, then back off) — it learns about a bad batch size from the users it just failed. Nexus proactively sizes batches but is work-conserving — the device fires the next batch the instant it is free, which under bursty arrivals means firing small, wasteful batches. Lazy Batching needs invasive changes to the ML framework itself.
How Proteus works
An exact optimizer upstairs, a millisecond router downstairs
-
Model registry & profiler
Developers register an application and its model variants (a model-less interface: the system, not the developer, picks variants). The profiler measures every (variant, device type, batch size) combination — latency and peak throughput — into an in-memory store with constant-time lookup, refreshed periodically against live workers.
-
Statistics collection
Per-application load balancers watch query demand and report to the controller. Under stable load the allocator runs every 30 seconds; a detected burst or worker overload triggers it immediately.
-
The MILP resource manager new
One mixed integer linear program decides three things at once: model selection (which variants, how many replicas), placement (which physical device hosts each — one variant per device, avoiding interference), and query assignment (what FRACTION of each application's queries goes to each device). Objective: maximize effective accuracy. Constraints: every application's demand fully served, no device beyond its profiled peak capacity. If demand exceeds even the all-cheapest-variants capacity, the program is infeasible — the solver shaves the demand target slightly and re-solves, degrading gracefully instead of thrashing.
-
Capacity estimation new
The peak throughput of a (device, variant, application) triple comes from a worst-case argument — a query arriving just after a batch starts waits one full batch, then executes, so batch processing latency must stay within HALF the SLO. The largest batch meeting that bound (and fitting device memory), divided by profiled latency, is the capacity the MILP trusts.
-
Data path: request routers new
Each application has its own load balancer whose router dispatches queries by the current assignment fractions — a table lookup measured under one millisecond. The expensive optimizer never touches a query in flight; new plans arrive asynchronously and swap in.
-
Per-device adaptive batching new
Workers absorb what the plan cannot see: micro-scale jitter in arrival times. The algorithm is proactive (it computes, from the first queued query's deadline, exactly how long it may keep waiting) and non-work-conserving (it deliberately leaves the device idle to accumulate a fuller batch, executing at the last safe moment). No ML-framework changes required.
The idea
The three sub-problems are one problem. Selection, placement, and assignment look separable and are not: which variant is worth hosting depends on which device would run it (the accuracy-throughput curve differs per device type), and both depend on how much of each application’s load lands there. The ablation makes the coupling concrete — remove dynamic selection and SLO violations hit their worst ratio (0.18) because the system cannot shed accuracy under load; remove placement and accuracy drop hits its worst (16%) because variants sit on the wrong silicon; remove optimized assignment (spread queries uniformly) and violations still triple. Proteus’s answer is to stop decomposing: one MILP over Boolean placement variables and fractional assignment variables, solved EXACTLY. Optimality is not a flourish — the gap between Proteus and the greedy INFaaS (2.8× in accuracy drop, 4.3× in violations) is precisely the price of local optima.
Exactness is affordable if you move it off the clock. The reason INFaaS settles for greedy is architectural, not mathematical: it allocates on query arrival, inside the latency budget. Proteus splits the timescales — the MILP answers MACRO-scale demand changes (minutes), asynchronously, in 4.2 seconds on average, while queries in flight see only a sub-millisecond routing table. The decoupling has an honest cost the paper shows plainly: when a burst begins, Proteus eats a brief spike of violations until the next re-solve, where INFaaS reacts instantly. It is the right trade — after both systems adapt, Proteus operates from the optimum and INFaaS from a local one — but it is a trade.
Idleness can be an optimization. The batching algorithm’s counterintuitive core: with q queries queued and the first expiring at a known time, the device may wait exactly until that query’s deadline minus the processing time of a (q+1)-sized batch. If another query arrives first, recompute with the shrunken budget; if not, fire at the boundary. A work-conserving device — never idle while work waits — fires early, small, and often; under bursty arrivals that wastes capacity the very moment it is scarce. Waiting converts idle moments into batch fullness precisely when arrivals cluster, and the isolation study prices the principle: on Poisson and bursty Gamma arrival traces, Proteus’s batching beats Nexus’s work-conserving approach 2–3× and Clipper’s reactive AIMD 3.8–4× on SLO violations — while on uniform arrivals all three tie, because with no jitter there is nothing to absorb.
A lunchtime peak, served
Fixed cluster, doubling demand
Nine applications (image classification through GPT-2 question answering) share 40 workers. Numbers from the paper's cluster testbed and simulator, which agree within about 1%.
Step 1 of 5
Quiet morning: maximum accuracy
Demand is low, so the MILP's optimum hosts the heavyweight variants — EfficientNet-b7, BERT-large — placed on the devices where their profiled throughput is best. Effective accuracy sits near 100% of the achievable maximum. Every 30 seconds the solver re-checks; nothing changes, nothing moves.
the routing table answers in under a millisecond per query profiler keeps (variant, device, batch size) measurements fresh in a constant-lookup store
Why it works
- Selection, placement, and assignment are coupled through per-device accuracy-throughput curves → optimizing them jointly reaches the Pareto frontier of the configuration space → the same cluster serves the same demand with a third of the accuracy loss of greedy or partial optimizers.
- The expensive solve runs off the critical path, on macro-scale demand signals → exactness costs seconds nobody is waiting on, while queries see a sub-millisecond table → Proteus affords the global optimum that critical-path systems must approximate.
- Capacity estimates bake the worst case in (batch latency within half the SLO, memory bounds respected) → the plan the MILP produces is servable, not aspirational → devices run at profiled peaks without silently overcommitting.
- Deadlines, not observed failures, drive batching → the device waits exactly as long as the first queued query can afford → bursty arrivals become fuller batches instead of violations, with zero changes to the ML framework.
- Infeasibility is a signal, not a crash → when demand exceeds even the cheapest-variant capacity, the solver shaves the target and re-solves → overload degrades gracefully instead of collapsing into indiscriminate drops.
What it costs
- Burst response lag. Decoupling means a burst is served under the stale plan until the next solve lands; the paper shows the initial violation spike that INFaaS’s critical-path (but greedy) allocation avoids.
- A solver in the loop. Gurobi solving MILP at 4.2 seconds average scales to roughly 160 devices, 450 variants, or 17 query types within a 60-second budget — comfortable for enterprise and edge clusters, not for hyperscale; beyond that, heuristics return.
- Users must accept variable accuracy. The premise — every query prefers accuracy but tolerates a timely, slightly worse answer — fits recommendations and real-time perception; it does not fit domains where accuracy is a hard constraint. Effective accuracy is also averaged SYSTEM-wide, so low-traffic applications carry less weight and fluctuate more (T5 swings most; the paper flags the fairness question openly).
- Modeling simplifications. One variant per device (to avoid interference), profiled fixed-size inputs — variable input lengths of language models are not in the MILP’s capacity estimates, only absorbed downstream by batching.
- Profiling debt. Every (variant, device type, batch size) triple must be measured and kept fresh; the plan is only as good as those numbers.
The evaluation
Production enterprise cluster (40 workers across three device types, real internal users) plus a validated simulator, replaying a month-long Twitter trace and synthetic macro- and micro-scale bursts, against a spectrum from static to fully dynamic baselines.
Four ways to serve a peak on fixed hardware
| Property | Static (Clipper / TF-Serving / Triton) | Dynamic heuristics (Sommelier, INFaaS) | Proteus |
|---|---|---|---|
| How a demand spike is absorbed | |||
| Worst-case accuracy drop (Twitter trace) | 20% (Clipper-HT); Clipper-HA drops none but violates SLOs most | 16% (Sommelier), 13.7% (INFaaS) | |
| SLO violations | Worst of all approaches; Proteus is over 10× lower | ||
| Where allocation decisions run | Nowhere — fixed at deployment | ||
| Batching | Clipper AIMD: reactive — grows batches until users time out, then backs off (3.8–4× more violations on bursty arrivals) | Nexus: proactive but work-conserving — fires the instant the device frees, small and often under bursts (2–3× more violations) |
Check yourself
Check your understanding
1. Sommelier already scales accuracy; INFaaS already selects and places models dynamically. Predict why solving selection, placement, and assignment JOINTLY — rather than any two — is where Proteus's advantage actually comes from.
2. INFaaS makes allocation decisions the moment a query arrives; Proteus makes them asynchronously, seconds later. The paper shows INFaaS actually reacts FASTER to bursts. Why is Proteus's architecture still the better choice?
3. Proteus's batching deliberately leaves a device IDLE while queries wait in its queue. Predict when this non-work-conserving choice wins, when it does nothing, and why the reactive alternative (Clipper's AIMD) is worst of all.
4. Proteus maximizes effective accuracy — the average over all served queries, system-wide. Predict which applications get the short end of that objective, and what the evaluation shows about it.