The Double-Headed Stack Allocator and the Memory Bill AI Still Hasn't Paid

Casey Muratori wrote up the double-headed stack allocator on October 3, a technique he picked up from James Anhalt at Blizzard during StarCraft 2 development. The idea is old, unglamorous, and about as far from a frontier-model paper as you can get. It is also the cleanest explanation available of a problem that now costs AI operators real money: two subsystems competing for one pool of memory, each with its own allocation timeline, and neither able to predict the other.

The post is worth reading on its own terms. Muratori traces the plain stack allocator (a bump allocator) back to animation work at Surreal Software on the cancelled Midway open-world game This is Vegas, where per-frame blend allocations were showing up as a profiler hotspot. The fix was an integer add on allocation and a single assignment to free everything: set tos = 0 when the frame’s transient work is done. He notes it composes with atomics for multithreaded fork/join, and supports partial deallocations by saving and restoring the top-of-stack index at each recursion level.

The fragmentation example, precisely

Then comes the actual double-headed part. Picture a streaming world where level geometry allocates and frees on one schedule, and a shape-shifting player character allocates and frees on another. Muratori’s worked example uses 100MB total. The level takes 20MB, the character takes 30MB, the level takes another 20MB, the character takes the final 30MB. Now the player runs to a new section. The old level data frees. The new level data needs a single contiguous 30MB block. There is 40MB free, but it is split into two 20MB fragments. The allocation fails anyway.

The fix: one memory block, two top-of-stack pointers. Level data grows upward from 0. Character data grows downward from the end. You are out of memory when the two indices cross. When the level changes, reset its tos to 0 and reallocate from scratch. No fragmentation, because neither side ever leaves holes behind it.

Muratori is honest about the tradeoff. Two separate stack allocators would work too. The double-headed version wins only when you are memory constrained and know that one stack’s capacity can serve both systems, but the split between them is flexible. On a level that needs more geometry memory, the character gets less. That is a real constraint, not a free lunch, and he says so.

Why an AI newsroom is reading a game-dev blog

Because the shape of the problem is identical to what is happening in inference serving right now, and the industry’s default answer has been to throw capacity at it rather than restructure the allocator.

Consider a single GPU serving a batch of requests. Two things want the same HBM. First, the weights, which are static and huge. Second, the KV cache, which is dynamic, per-request, grows token by token, and gets freed when a sequence finishes. Add a third: scratch memory for attention kernels and communication buffers, which spikes during prefill and mostly idles during decode.

These are separate allocators on separate timelines. A long-context request can hold a large contiguous KV block while a burst of short requests fragments the remaining space. The serving stack either reserves worst-case headroom, which wastes capacity, or it fragments, which drops throughput. This is exactly the This is Vegas animation problem with a bigger electricity bill attached.

The systems world has already been reaching for this class of answer. PagedAttention in vLLM is the most-cited case: it stops pretending the KV cache is one contiguous tensor and manages it in fixed-size blocks with an indirection table. That is structurally the same move as the offset-table variation Muratori describes at the end of his post, where one stack holds variable-sized payloads and the other holds an array of integer offsets into them. His version even supports removing and relocating items, with the offset table updated to match.

{/* TODO: verify vLLM PagedAttention implementation details and any 2026 changes before publishing — searched “vLLM PagedAttention KV cache block table”, found the original 2023 paper reference but did not confirm current implementation state */}

The part AI builders keep relearning

Muratori’s post has one line that ought to be printed on the wall of every inference team: allocation is an integer addition, and freeing everything is a single integer assignment. It does not get faster than that.

The reason this matters now is not that AI infrastructure engineers have never heard of bump allocators. It is that the industry’s instinct when memory pressure appears is to buy more HBM, or quantize harder, or shard across more devices. All three are legitimate. None of them address fragmentation, and fragmentation is what turns a 40MB free pool into a failed 30MB allocation.

The double-headed trick is a reminder that the constraint is often structural, not budgetary. If two subsystems share one memory region and their lifetimes are independent, a single allocator will fragment. Two allocators growing toward each other from opposite ends will not, as long as you can tolerate the flexible split. The cost is that you must be able to reset an entire side at once, which requires the system to be designed so that one side’s memory genuinely is transient. That is a design decision, and it has to be made early.

Fragmentation is what turns a 40MB free pool into a failed 30MB allocation, and no amount of extra HBM fixes a layout problem.

For AI builders, the actionable read is narrower than “use bump allocators.” It is: identify which of your memory consumers have independent lifetimes, and check whether your serving stack is treating them as one pool when they should be two. Prefill scratch and decode KV cache are the obvious candidates. So are activation buffers during training and the optimizer state that persists across steps. Muratori’s post will not tell you how to restructure a transformer’s memory layout. It will tell you, in about 1,400 words and a handful of diagrams, why the layout question is worth asking before the next capacity purchase.

The post also links the AMD Vulkan Memory Allocator’s linear-algorithm documentation, which is the graphics-industry version of the same idea. That is the other thing worth noting: this technique has been public in game and graphics circles for over a decade. It is not new. It is just under-read by the people now paying the largest memory bills in the industry.