Medusa: Accelerating Serverless LLM Inference with Materialization

Serving a language model on demand means starting one from cold when traffic spikes, and most of that wait turns out to be two steps nobody had looked at — the server runs a fake maximum-sized request just to see how much GPU memory is left over for the key-value cache, then runs the model 35 more times to record its kernel launches into replayable graphs; Medusa (Tsinghua) does both once offline and restores them at startup, which requires solving the awkward part — the recorded graphs contain raw memory addresses that will be different next time — by noticing that while addresses vary, the order of allocations does not.

Why this problem is worth solving

The cold start problem is old, but language models moved where the time goes.

What makes the biggest single stage expensive is a technique adopted purely for speed.

What people did before, and where it broke

• Keep warm instances ready. Provision a pool of running servers so a burst finds something already alive. Where it broke. It wastes accelerators during quiet periods, and with many different models to serve, over-provisioning for each is unaffordable.
• Optimise runtime initialisation. Warm containers, snapshot restore, shared libraries — a rich literature. Where it broke. Nothing wrong with it; it simply finishes the job on 22% of the problem and leaves the other three quarters untouched.
• Speed up weight loading and model structure setup. Recent work does exactly this for language models. Where it broke. It targets two of the five loading stages and overlooks the two that are specific to these models. The paper points out that succeeding at this makes the remaining stages a larger fraction of what is left.
• Overlap the stages instead of shortening them. The obvious move: load weights from disk while doing processor and accelerator work concurrently. Where it broke. The dependencies forbid some orderings — recording the kernel graphs requires running the model, which requires the key-value cache to exist. And the overlap does not cover: for 6 of 10 models the weight loading is shorter than the work it would hide, leaving a gap. The two also interfere, because the profiling run blocks some of the asynchronous copies the weight loading issues.
• Defer the graph recording until requests arrive. Record each batch size only when a request of that size shows up. Where it broke. It does not remove the cost, it scatters it across the requests that arrive first.
• Skip the graphs entirely. Shorter start, and the paper evaluates this. Where it broke. Inference gets substantially slower, and the key-value cache profiling still remains, so the start is not even that much shorter.
• The gap. Nobody had asked whether these two stages need to be executed at all. Both are discovering a fact by running something, and neither fact changes between starts of the same model on the same accelerator.

How Medusa moves the work offline

The idea

Both expensive stages are discovering a fact by executing, and the fact does not change. This is the reframing, and once stated the rest is engineering. The memory reservation stage runs a maximum-sized fake request purely to observe how much memory is left over; the recording stage runs the model 35 times purely to observe which kernels fire in what order. Neither observation depends on anything that varies between starts of the same model on the same accelerator. So the answer can be computed once and looked up, which converts a computation into a read. The measured effect on the memory stage is stark — from 0.50 seconds to 0.02 — because that stage really is nothing but a measurement. Attacking the delay before a service can answer by moving work out of the startup path entirely, rather than making the startup path faster, is the same strategy as the layer-wise container cold start work covered elsewhere on this site.

Store the index into the allocation order, not the address. The reason recorded graphs cannot simply be written to a file is that they are ready to execute: each node holds the raw address of a kernel and raw pointers to the buffers it reads and writes, and neither survives a restart. But the paper draws a distinction that resolves this. The addresses are non-deterministic; the control flow that requests them is not. The same code allocates the same buffers in the same order every time, so the tenth allocation is always the tenth allocation even though it lands somewhere different. Storing a pointer as its position in that sequence, then replaying the sequence at startup and reading off the new address, restores the graph correctly. There is a subtlety the paper handles carefully: a freed address can be handed out again, so a naive search finds several candidates, and matching backwards from the kernel that used the buffer picks the live one. Replacing a value that varies with an index into a sequence that does not is exactly the manoeuvre behind the time variables in the hardware description work covered elsewhere on this site, applied to addresses rather than to clock cycles.

Not everything that was saved needs restoring, which is what makes it cheap. The obvious implementation would dump every buffer the graph points at and copy them all back, which would be expensive enough to defeat the purpose. Two categories can be skipped. Buffers holding model weights were populated before recording began, so the ordinary weight-loading stage already fills them. Scratch buffers holding intermediate results between kernels are managed by the graph itself, and are identifiable because they get freed once recording completes. What is left is startlingly small — only 9% of kernels need a persistent buffer, and each needs two of four bytes apiece. Recognising which state a restore genuinely has to carry, rather than snapshotting everything reachable, is the same discipline as the function compression work for serverless startup covered elsewhere on this site.

Walking one pointer through materialization

The discrimination is a heuristic and the paper says so — a constant can occasionally look like a pointer. The safeguard is a verification run that compares the output of the restored graph against a normally executed forward pass and reports a mismatch, which turns a rare misclassification into a detected error rather than silent corruption.

Why it works

• A measurement whose answer never changes is a constant. The memory profiling stage exists only to observe how much is free, and that is fixed by the model and accelerator → so it can be observed once and read thereafter → half a second becomes two hundredths.
• Control flow is deterministic even when addresses are not. The same code allocates the same buffers in the same order on every start → so an allocation index is a stable name for something whose address is not → replaying the sequence re-derives every pointer correctly.
• Searching backwards from the use disambiguates recycled addresses. A freed address can reappear, giving several candidate matches → but a kernel always uses a buffer while it is live, so the nearest preceding allocation is the right one → which is why intercepting kernel launches alongside allocations is necessary rather than merely convenient.
• Most saved state does not need restoring. Weight buffers are refilled by the ordinary loading stage and scratch buffers are managed by the graph itself → so only genuinely persistent state must be carried → which is 9% of kernels holding four bytes apiece, rather than gigabytes.
• Repetitive model structure gives a free lever for loading hidden code. Language models are stacks of identical layers, and the driver loads kernels a module at a time → so running just the first layer loads every module the whole model needs → the kernels that cannot be looked up by name become enumerable at a fortieth of the cost.

What it costs (trade-offs and scope)

• Single GPU only. Models must fit on one accelerator. The authors note a 40 GB card covers a 13-billion-parameter model and smaller, argue the core ideas carry over, and leave building the allocation-index table across multiple accelerators to future work. For a paper about serving language models at scale that is a real boundary.
• The graph recording is reduced, not eliminated. The stage falls from 0.90 seconds to 0.57, because the first layer must still be warmed up and recorded to force the hidden modules to load. Roughly 63% of the recording cost survives.
• Part of the gain is scheduling rather than materialization. Shortening the memory stage lets the remaining warm-up overlap with weight loading, and the stages are reordered to enable it. The paper describes this openly; it does mean the headline is a combination of removing work and rearranging what is left.
• The offline phase costs about 39 seconds per model and accelerator pairing. Amortised over many cold starts this is small, and it must be redone whenever the model, the accelerator, or presumably the framework version changes.
• Two mechanisms are heuristics with a safety net rather than guarantees. Telling pointers from constants relies on eight-byte width and a high address prefix, and the backwards search relies on buffers being used while live. Both are backed by a verification run comparing restored output against a normal forward pass, which converts a wrong guess into a detected error.
• Two cases are unhandled and assumed absent. Allocations made from inside kernels, and pointers to arrays of pointers, would both break the scheme. The authors examined 10 models comprising 139,364 graph nodes and found neither, keep the validation as a guard, and sketch a compiler pass as a future fix.
• The improvement varies by nearly a factor of two across models. Best case 42.9% of the loading phase, worst case 21.1%, with smaller models gaining least because their fixed costs dominate.
• Trace evaluation is two models and one dataset. The end-to-end tail latency results use two of the ten models on one conversational dataset with synthetic arrival times at two request rates.
• It assumes a single inference framework’s design. Everything is built on one open-source serving system, including its choice of 35 batch sizes and its block-based cache management. The approach depends on that framework doing profiling and recording the way it does.

The evaluation

Check yourself

Sources

The paper is “Medusa: Accelerating Serverless LLM Inference with Materialization” by Shaoxun Zeng, Minhui Xie, Shiwei Gao, Youmin Chen and Youyou Lu, published at ASPLOS 2025 Volume 1, pages 653-668, DOI 10.1145/3669940.3707285. All authors are at Tsinghua University. The paper carries an artifact appendix.

This explainer is written from the full text, read through a proxy of the ACM Digital Library copy. Everything above comes from the paper’s own sections 2 through 8: the three-part cold start breakdown at 22%, 76% and 2%, and the five-stage decomposition of the loading phase placing key-value cache initialisation at 18% and graph recording at 32%; the explanation of why graphs are built by recording a forward pass rather than by explicit construction, and the measurement of up to 2.4 times inference acceleration from using them; the analysis of why warm-up is required before recording and why one graph is needed per batch size, with 35 sizes following the baseline framework; the rejection of hot spares, of naive overlapping — which leaves a gap for 6 of 10 models and causes the profiling run to block asynchronous copies — and of deferring the recording; the two challenges of non-deterministic buffer pointers and randomised or hidden kernel addresses; the indirect index pointer scheme with its backwards trace-based search to avoid matching reused addresses; the copy-free content restoration identifying weight buffers as pre-populated and scratch buffers as graph-managed, leaving 9% of kernels needing two four-byte persistent buffers each; the kernel name resolution covering 69.2% of kernels in one model and the triggering-kernel technique using the first layer to force module loading; the invariance assumption underlying memory materialization; the evaluation across ten models on A100 accelerators giving 42.5% and 34.4% loading phase reductions, 34.9% overall cold start reduction, a range from 21.1% to 42.9% across models, the stage-level breakdown showing 0.50 to 0.02 seconds and 0.90 to 0.57 seconds, the roughly 39 second offline cost, and tail latency reductions of 53.0% and 50.5% under synthetic arrivals; and the discussion section acknowledging unhandled device-side allocations and indirect pointers, and the single-accelerator limitation.