Microsoft's MetaMuse Beats Human Cache Algorithms by 35% Using Random Words
A Microsoft Research and UIUC team shows that random dictionary words can push LLMs past their bias toward LRU and first-fit, producing genuinely novel system algorithms.
Takeaways
- MetaMuse reduces cache misses by up to 35.76% and bin usage by up to 30.93% vs human heuristics (paper).
- LLMs suffer availability bias, clustering solutions around LRU, LFU, and FIFO regardless of temperature.
- Framework uses random English dictionary keywords as external stimuli to force novel associations.
- Diversity measured in performance space, not semantic space, because equivalent code can look different.
- Waypoint reasoning through property extraction, problem mapping, solution formulation, and code generation.
- Open source at github.com/illinois-nsai/MetaMuse, costs about 2.16 cents per generated solution with GPT-4o.
Ask GPT-4o to invent a cache replacement policy and it will hand you back something that looks suspiciously like LRU, LFU, or FIFO. Ask it a thousand times, crank the temperature up, and you still get variations on the same three textbook heuristics. A new paper from Microsoft Research, UC Berkeley, and UIUC tackles this exact failure mode, and their fix is stranger than you might expect: feed the model random English words like flower or zebra and force it to reason its way from petals to circular buffers.
The framework, called MetaMuse, reports up to 35.76% fewer cache misses in cache replacement and up to 30.93% less bin usage in online bin packing compared with the best human-designed heuristics. Code is on GitHub.
Why LLMs Keep Reinventing LRU
System algorithms live in what the authors call a discontinuous solution space. Even a small change in algorithm design, like swapping a data structure or altering control flow, can produce sharp, non-linear shifts in performance. That makes the space impossible to navigate with smooth gradient-style search, so engineers fall back on generic heuristics. At the cloud provider where this work was done, even seemingly simple algorithms like cache replacement or bin packing can require tens of thousands of engineering hours to design.
Handing the problem to an LLM is the natural next step, and the natural next result is disappointing. The team sampled GPT-4o, Llama 3.3-70B, and DeepSeek-V3 repeatedly, generated 1,200 cache solutions, and clustered them by hit-ratio similarity. Outputs concentrate around well-known heuristics such as LRU, LFU, and FIFO. Making repeated sampling aware of previous solutions does not mitigate this bias.