MetaMuse: Algorithm Generation via Creative Ideation
Authors: Ruiying Ma
Chieh-Jan Mike Liang
Yanjie Gao
Francis Y. Yan
Venue: ICLR 2026 Poster (2026)
Keywords: system algorithm design
creativity
ideation
self-reflection
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: Designing system algorithms remains challenging, where the discontinuous nature of the solution space often forces system engineers to rely on generic heuristics at the expense of performance. We study whether LLMs can practically drive algorithm generation, and find that they are biased towards well-known generic designs, rather than making the creative leaps needed to navigate the discontinuous solution space. To address this limitation, we introduce MetaMuse, a framework for creative ideation built on three self-reflection principles: (1) quantifying solution diversity and usefulness in measurable performance space, rather than abstract idea space, (2) steering ideation through external stimuli, rather than internal randomness, and (3) constructing executable solutions using waypoint reasoning, rather than free-form chain-of-thought. Considering two critical online problems at a global cloud provider, extensive evaluations show that MetaMuse can generate high-performing solutions: it reduces cache misses by up to 35.76%
in cache replacement and reduces bin usage by up to 30.93% in online bin packing.

Published as a conference paper at ICLR 2026
METAMUSE: ALGORITHM GENERATION VIA CREATIVE IDEATION
Ruiying Ma University of California, Berkeley
Chieh-Jan Mike Liang
Microsoft Research
Yanjie Gao
Francis Y. Yan
Microsoft Research
University of Illinois Lirbana-hhappan
ABSTRACT
Designing system algorithms remains challenging, where the discontinuous nature of the solution space often forces system engineers to rely on generic heuristics at the expense of performance. We study whether LLMs can practically drive algorithm generation, and find that they are biased towards well-known generic designs, rather than making the creative leaps needed navigate the discontinuous solution space. To address this limitation, we introduce MetaMuse, a framework for creative ideation built on three self-reflection principles: (1) quantifying solution diversity and usefulness in measurable performance space, rather than abstract idea space, (2) steering ideation through external stimuli, rather than internal randomness, and (3) constructing executable solutions using waypoint reasoning, rather than free-form chain-of-ther -hthuughht Considering two critical online problems at global cloud provider, extensive evaluations show that MetaMuse can generate high-performin solutions: it reduces cache misses by up to 35.76% in cache replacement and reduces bin usage by up to 30.93% in online bin packing.
INTRODUCTION
Designing system algorithms continues to be a central challenge in computing systems. Traditionally, the development of such algorithms has been manual and labor-intensive process. Our experience at a global cloud provider indicates that even seemingly simple algorithms used in production such as cache replacement for data storage or bin packing for job scheduling can require tens of thousands of engineering hours to design. As a result, practitioners often resort to generic heuristics from the literature, e.g., least-recently used (LRU) and cast-freyuently used (LFU) for cache replacement, and first-fit for bin packing, which frequently result in suboptimal performance.
This paper asks whether large language models (LLMs) can practically drive algorithm generation, with an emphasis on principles to transform this task into systematic process. The core challenge in system algorithm design arises from the nature of its solution space: an inherently discontinuous space, where even small change in algorithm design (e.g., data structure or control flow) can lead to sharp and non-linear changes in performance. Although it is sometimes possible to estimate the upper-bound performance, searching for practical solutions that approach this bound remains non-trivial. Furthermore, the discontinuous solution space does not provide sufficiently predictable patterns or smooth landscape to guide the search.
Due to this discontinuity, we approach the algorithm generation task from different angle, framing it sampling process in the solution space where the LLM attempts to generate distinct solutions at each step. This generative process represents a sequence of leaps across the discontinuous solution space (Bubeck et al. 2023), which we formulate creative ideation for LLMs. In fact, the systems community has long hypothesized algorithm design as a discovery process of ideas (Kant 1985).
To study the algorithm generation task, focus high-impact problems global cloud provider: cache replacement and online bin packing. Our initial attempts of repeatedly sampling GPT-4o, Llama3.3-70BB. and DeepSeek- V3 show that L.LMs fundamentally hindered by availability bias (Terskky& & Kahneman] 1973) -LLMs are trained to output the most likely sequence of words, according training datasets. As result, solutions tend cluster around well-known heuristics in the literature, c.g., LRU and LFU for caching. Furthermore, we find that this bias cannot be practically addressed through LLM hyperparameters like temperature (Ackley et al. 1985).
This work was done when Ruiying Ma was an intern Microsoft Research.

---

Published as a conference paper at ICLR 2026
The key to creative ideation is exploiting knowledge that LLMs assume to be probabilistically irrelevant to the given problem. What is missing is a self-reflection process, which thinks how to generate subsequent solutions by inspecting what solutions have been generated so far. In realizing such a self-reflection framework, MetaMuse, we see three model-agnostic principles surfacing to best guide this self-reflection. First, evaluating diversity of generated solutions should be grounded in the measurable feedback space (c.g., simulation performance of system algorithms), rather than the abstract idea space (Sankar & Sen 2024). Second, steering the ideation achieved through external stimuli (e.g., keywords), rather than internal randomness (Chen & Ding 2023). Third, developing executable solutions from external stimuli takes structured checkpoint-bass steps. or waypoini reasoning, rather than free-form chain-of-thout of-thought (Wei et al. 2023 Mehrotra et al. 2024).
Our work makes the following contributions:
1. Empirical analysis of L.LMs' fundamental limitations in the algorithm generation task ($2 We shed light on the impracticality of relying on LLMs' internal randomness for ideation, based on two online problems at global cloud provider: cache replacement and online bin packing.
2. Principled framework for creative ideation, MetaMuse ($3) We systematically combine three self-reflection principles to guide the discontinuous leaps necessary to overcome LLMs' bias.
3. Practical evaluation of the online algorithm generation task ($44 We show that (1) MetaMuse generates better cache replacement and bin packing solutions, outperforming LLM- based baselines (by up 9,89% fewer cache misses, and up to 21.06% less bin usage) and human heuristics (by up to 35.76% fewer cache misses, and up to 30.93% less bin usage); (2) MetaMuse has up to 1.78x more distinct cache replacement solutions and 1.80x more distinet bin packing solutions, than LLM-based baselines; (3) MetaMuse has a low per-solution cost, up to 2. 16 cents with GPT-4o.
2
BACKGROUND AND MOTIVATION
2.1 SYSTEM ALGORITHM DESIGN
System algorithms define how computing systems behave. They are typically designed to optimize some performance objectives (e.g., cache hit ratio), for some scenarios or workloads (e.g., web servers). The difficulty of designing such algorithms arises from the nature of their solution space. is discontinuous, where even small change in algorithm design (e.g.. the use of data structures) can lead to sharp and non-linear changes in performance. In addition, the discontinuity does not provide sufficiently predictable patterns departure from prior efforts on auto-tuning system config parameters (Alipourfard et al. 2017 Cortez
smooth landscape guide the search. This is a significant
et al. 2017 Liang et al., 2020), which can be formulated as numerical optimization in most cases.
To this end, our work explores the use of LLMs to design heuristic algorithms, i.e., the algorithm generation task. Due the discontinuous solution space, formulate this task sampling process over the solution space, in which LLMs aim to generate distinct solutions at each step. Conceptually. solving such discontinuous task requires certain "Eureka" ideas that constitute leaps towards the final solution (Bubeck et al. 2023). Here, we refer to these leaps as creative ideation.
2.2 CREATIVE IDEATION
The goal of creative ideation is to discover useful solutions to a user-given problem, through a process of generating diverse solutions over time. The first requirement is usefulness- generated solution should be relevant to the problem. The second requirement is diversity generated solution should produce feedback (or an outcome) that is unseen in the current process (Boden) 1998). As we accumulate diverse and useful solutions, the process advances towards finding the optimal solution.
For the algorithm generation task, creative ideation can be formulated as the following iterative process. Each iteration takes in the problem statement of the algorithm, along with the set of functions to be implemented. For example, most caching algorithms can be abstracted into insert t and evict functions (Yang et al.] 2020). Optionally, we can also incorporate metadata and feedback from previously generated solutions. At iteration i, the output is an executable cache solution, C₁ with all functions coded. We can optionally provide feedback to iteration é + 1, by evaluating the hit ratios of previous solutions (c ..., chit ), on a user-given workload trace in an environment such as simulators. After cache solutions, select the best-performing one from (C), m. Cx).
2

---

Published as a conference paper at ICLR 2026
75%
75%
75%
Cluster Size (%)
60%
Repe atoc Sampinng lnio previcud salution)
60%
Rapeated Sampling (wro previous solutios)
Cluster Size (%)
60%
Repeated Sampling
(mlo previcus solutios)
Repested Sampling
Cluster Size
Repeated Sampling (wl previous solutions!
Repeated Sampling (ml previous solution)
45%
(ml previdus solutions)
45%
45%
30%
30%
30%
15%
15%
15%
fifo
tinyLFI LyU
clock
ard
sievel
siru-
s3fifo
fifo
tiny Fu
arc clock
sievel
siru
$3110
fifo
tiny LF
clock
arc
sieve-
sirul
s3fifo
(a) GPT-4o
(b) Llama3.3-70B
(c) DeepSeck- V3
Figure I: Repeatedly sampling LLMs can lead to biased solutions. In cache replacement, solutions
tend to cluster around well-known heuristics in the literature, such as LRU, LFU, and FIFO.
2.3 LLM LIMITATIONS IN CREATIVE IDEATION
Our work is motivated by the observation that the creative ideation capability of LLMs is funda- mentally constrained by the very mechanism that enables it next-token prediction. In cognitive terms, responses are shaped by what has been frequently or recently seen, a phenomenon known as availability bias. For L.Mss, this bias stems from the frequency distribution of data seen in training.
Impacts on algorithm generation. Due to this bias, LLMs tend to generate certain classical designs. We illustrate this phenomenon in the context of cache replacement, using GPT-4o (version: 1120), Llama3.3-709 (version: Instruct), and DeepSeek-Ve V3 (version: 0324).
Figure 1 shows our attempts with Repeated Sumpling (Brown et al. 2024 Snell et al. 2024). At iteration i, each I.IM prompted to generate new algorithm design 6; using a temperature of
1. To isolate creativity from coding ability, C; is then implemented in Python by the same model, GPT-4o. The resulting implementation is evaluated a simulator to measure hit ratios on 30 synthetic traces. We examine two variants of Repeated Sampling that differ in whether the prompt each iteration includes all previously generated solutions (i.e., solution descriptions and implementations). Figure cllustess 1,200 solutions by assigning them the nearest centroids of established human heuristics, based on the similarity of their hit-ratio vectors. We observe that LLM-generated solutions concentrate around well-known heuristics, such LRU, LFU, and first-in-frrs-ouu (FIFO). Moreover, making Repeated Sampling aware of previous solutions does not mitigate this bias.
Even if LLMs are instructed to generate new solutions by mutating previous solutions (Novikov et 2025; Sharma 2025), we observe a bias towards tweaking the solution's 's scoring function. LLMs tend to ignore other design dimensions such as data structure, hierarchical architecture, etc.
Is adjusting LLM hyperparameters all you need? One such parameter is temperature (Ackley al. 1985). which internally regulates randomness in the generative process. Temperature smooths the probability distribution of next-token candidates, as computed by the softmax of their logits. At higher temperatures, high probabilities are decreased, and low probabilities are increased.
Unfortunately, high temperatures only marginally mitigate availability bias without fundamentally addressing it. The reason is that increasing temperature smooths the probability distribution, which is monotonic transformation retaining the relative ranking of output token candidates. Even at extreme temperatures, the distribution would approach uniformity, resulting in incoherent LLM outputs.
2.4 RELATED WORK
The first category is automatic heuristic design (Liu al. 2024b Ye et 2024 Zheng al. 2025; Romera- Paredes et al., 2024 Novikov et al., 2025] Sharma 2025 D Dwivedula et al. 2025 Lange et al. 2025 Cheng et al., 2025). These efforts mostly rely on LLMs to evolve an initial population of candidate designs through mutations and crossovers. This dependence the initial population inherently constrains the reachable solution space. In addition, availability bias can influence how the population evolves. Our study reveals a bias towards frequently tweaking the cache algorithm's 's scoring function, rather than leaping to other design dimensions. MetaMuse addresses these limitations by making leaps in the solution space.
3

---

Published as a conference paper at ICLR 2026
Evaluating Diversity
Steoring with External Siimuli
Developing Stimull into Executable Solutions
traces
ratios
feedback space
flower
0.42
stimufi
flower
property extraction
0.26
RSDict RSDict-SF
a palals
problem mapping
weypoint reasoning
0.33
feedback
provious solutons:
stimull 1
solution
embedding
prodic
solution description
stimull
code generation
pylhon code
MetaMuse reflects previously generated solutions inform the creation of subsequent ones. Each iteration goes through three steps: evaluating the diversity of existing solutions ($3.T). steering ideation through external stimuli ($3.2. and developing executable solutions ($3.3)
Figure 2:
There are also efforts exploring Numan-LLNN, collaborations to produce diverse outputs (Liu et al. 2024c| Wan al., 2024 Vaccaro al. (2024). However, they require human involvement and be subject to human biases. In contrast, MetaMuse posits that LLMs themselves are capable of thinking "outside the box" (Mchrotra al. 2024), and proposes combining three self-reflection principles to achieve this capability ($3).
3 METAMUSE
In this work, we introduce MetaMuse, a creative idcation framework that addresses availability bias through principled self-reflection. The key is to enable LLMs think "outside the box," leveraging knowledge that otherwise seems probabilistically irrelevant to the user's problem.
Figure 2 illustrates single iteration of MetaMuse, which outputs executable solution. The first step evaluates the diversity of solutions generated so far ($..I) based on embedding vectors constructed from each solution's feedhack (e.g., cache hit ratios, shown in the figure). The second step steers ideation by selecting a set of stimuli (e.g., the keyword "flower" in the figure). $3.2 describes two stimuli selection strategies in the current implementation: RSDict and RSDict-SF. Finally, MetaMuse develops the stimuli into executable solutions ($3.3), through four waypoints of reasoning: property extraction, problem mapping, solution formulation, and code generation.
3.1 EVALUATING DIVERSITY
MetaMuse grounds diversity evaluation in feedback space rather than idea space. In our case study, the former refers to performance measurements such as cache hit ratios, whereas the latter refers to semantic embeddings of algorithm descriptions code implementations. MetaMuse represents each solution using a feedback embedding, which is a vector [P), ,P,,,,,... P2,... ......... ...-P4 PP.l containing performance
measurements across n workload traces. Ideally, these traces should be diverse, and one approach is to randomly synthesize them using tools from the systems community (e.g., libCacheSim (Yang al. 2020) for cache workloads).
This principle is motivated by the observation that semantic differences do not necessarily imply distinct solutions. Considering a case where GPT-4o generated functionally equivalent LFU-based solutions twice from different design descriptions: "The cache evicts the object that is least frequently accessed," and "The cache evicts the object with the lowest priority. Upon cache hit, the object's priority is incremented." Code semantics exhibit similar shortcomings, where solution implemented with linked list or a priority queue can yield the same hit ratio.
Furthermore, feedback embeddings have two desirable properties. First, because each dimension is quantitative metric conveying magnitude, the Euclidean distance between two embeddings is a direct indication of how different the corresponding solutions are. In the LFU example above, those two solutions would be considered equivalent as their distance is O. Second, feedback metrics typically lie within a fixed range, either by definition or through normalization (e.g., 0-100% for cache hit ratio). As a result, the n-dimensional embedding space is inherently structured and bounded, allowing us to compute well-defined steering direction 3.2
4

---

Published as a conference paper at ICLR 2026
3.2 STEERING WITH EXTERNAL STIMULI
The objective of steering is to guide LLMs to generate solutions, targeting regions of the feedback embedding space, Rather than relying on the model's internal randomness, MetaMuse introduces external stimuli the starting point for ideation. These stimuli may be unrelated the problem domain, forcing LLMs to associate with knowledge that appears probabilistically irrelevant. One domain-agnostic instantiation of such stimuli a set of keywords from an English dictionary.
Realizing this principle of steering presents practical challenges. The first is the source of stimuli. In the case of keywords, while large dictionary provides broad keyword coverage, it also includes many keywords of little value. An example is technical jargon, e.g., "prolamin" in biology. In our case study, if LLMs are forced to associate these keywords, they would frequently use them as variable names, rather than as inspiration to ideate new solutions. The second challenge is selecting stimuli each iteration.
$3.2.I next presents selection strategies in our current implementation.
3.2.1 STIMULI SELECTION STRATEGIES
Our current implementation of MetaMuse includes two strategies: RSDict and RSDict-SF.
RSDict is a stateless strategy that randomly selects keywords from the dictionary. Since RSDict does not rely on the evaluation results of previous solutions, is applicable in settings where evaluation is infeasible or costly (e.g., when human judges are required).
RSDict.
RSDict-SF. Based on RSDict, RSDict-SF further relies on self-feedback, leveraging the feedback embeddings of prior solutions to compute a steering direction. The steering direction is specified as a target feedback embedding. which serves as the objective that RSDict-SF should aim to achieve in subsequent solutions. In our case study, this mechanism supports both exploration (for diversity) and exploitation (for usefulness). For exploration, the steering direction defined as the point the embedding space that is farthest from all previous solutions, i.e., the embedding with the greatest Euclidean distance from the existing set. For exploitation, we define the target embedding by setting all dimensions to a high value (e.g., 100% cache hit ratios across all traces).
Given a steering-diree direction embedding. RSDict-SF computes a set of s stimuli that are likely to develop into solutions close to the target. Our current implementation formulates this step prediction problem and solves it with Gaussian Process Regression (GPR). Specifically, given s stimuli, we use their corresponding observations predict the solution's feedback embedding dimension by dimension, without generating the solution itself. Each observation is a natural- aatural-language sentence generated by LLMs after mapping one stimulus to the problem domain; we describe this process in detail in $3.3 We first compute the semantic embeddings (c.g.. by SBERT Reimers et al. (2019)) of the s observations, and use n GPR models, (M,,.... .... M,,). to predict each of the n dimensions in feedback embedding. These models allow RSDict-SF to predict the expected feedback embedding for any set of stimuli without generating the solution. The GPR models are refitted at each iteration with all previous solutions. We adopt a dot-product kernel for the GPR models. This kernel IC captures pairwise semantic similarity between all observations across two solutions and is invariant to their ordering. For two solutions c; and cj, their similarity under kernel K. is
K(c,,) c,)
ΣΣ (o...))) T((0).)) p=1 g=1
where or denotes the p-th observation generated from the p-th stimulus in the set of s stimuli for c,, and similarly for Oj.q- (d-) denotes the semantic embedding of an observation.
We highlight two implementation details. First, predicting for all possible sets of stimuli is not feasible in practice, and a dictionary with 3,000 common English words would already have 3,000 sets. To this end, MetaMuse exercises the power-of-two random choices (Mitzenmacher 2001). It randomizes two sets of stimuli from the dictionary, and predicts their expected feedback embeddings. Then, MetaMuse selects the one closest to the target embedding. Second, RSDict-SF is bootstrapped, with w solutions generated by RSDict, in order to start training GPR models.
al.)
3.3 DEVELOPING STIMULI INTO EXECUTABLE SOLUTIONS
Third, developing executable solutions from s stimuli requires structured waypoint reasoning. Waypoints serve as intermediate checkpoints that progressively transform seemingly unrelated stimuli
5

---

Published as a conference paper at ICLR 2026
($3.2.1) into solutions for the problem hand. Unlike free-form thain-of-thoughhe (Wei et al. 2023 Mchrotra et al.] 2024), we observe that waypoints prevent LLMs from superficially developing solutions, e.g., simply turning stimuli into variable names in code.
MetaMuse currently defines the following waypoints. The first is property extraction, where the LLM associates the given stimuli with related concepts and properties. For example, given the keyword "flower," one associated property might be "a ring of petals." These outputs are then passed to the second waypoint, problem mapping, where the LLM connects the extracted properties to problem-related observations. Continuing the example, "a ring of petals" may remind the LLM of a circular structure, which can be mapped to circular buffer in algorithm design. These observations are then fed to the third waypoint, solution formulation,, where the LLM combines observations and synthesizes the complete description of a new solution. The final waypoint is code generation, where the LLM translates the solution description into executable Python code. The waypoint prompts are included in the appendix
4 EMPIRICAL RESULTS
Baselines. We evaluate MetaMuse against 21 baselines. The LLM-based heuristic design baselines
include MCTS-AHD (Zheng et al. 2025), ReEvo (Ye et al. 2024), OpenEvolve (Sharma 2025),
PlanSearch (Wang al. 2025), and Repeated Sampling (Brown et al. 2024). We also include human- crafted state-of-the heuristics for cache replacement, including
LFU, FIFO, Sieve (Zhang
al.] 2024), S3FIFO (Yang et al.) 2023). LFn (Einziger et al. 2017). SLRU (Huang et al. 2013
Clock (Corbato 1968), and ARC (Megiddo et al. 2003). For the online bin packing problem, we include Next Fit, Worst Fit, Almost Worst Fit (AWF) (Johnson 1973). First Fit (Dósa Sgall 2013).
Best Fit (Dósa & Sgall, 2014), Harmonic-k (Lee & Leee, 1985), and Refined First Fit (RFF) (Yao) 1980). For Harmonic-k, we set k=4 to align its number of bin categories with RFF.
MetaMuse. We take dictionary of common English words and remove stop-words to get 2,899 keywords. Each solution is ideated from ==4 keywords. The feedback embedding consists of performance measurements libCacheSim (Yang et al., (022). from different Zipfian distributions. For bin packing, n traces are from various Weibull distributions. The number of RSDict-SF warmup solutions is w=100, roughly one-third of the total solutions in one experiment. Finally, prompts are included in SC
n==0 traces. For cache replacement, these n traces are generated by
Experiment setup. We focus on two high-impact problems global cloud provider: cache replacement and bin packing. In each experiment, all methods aim to ideate and generate 350 executable solutions. To the best of our ability, we configure PlanSearch to output at least 15, 11, and 12 observations, while ideating with GPT-4o, Llama3.3 3-00B, and DeepSeek-V3. V3,, respectively. Many baselines such as MCTS-AHD can tune parameters in their solutions. diddssusesss safeguards against unsafe solutions, and environments are instrumented to catch errors, e.g., long-running execution. Unsafe solutions are re-implemented.
To evaluate cache replacement solutions, we use 96 real-world workload traces from four data access scenarios (Table Ip: RetrievalAAtention (Liu et al. 2024a) (24 "ra-fwe" and 24 "ra-multikey" traces), Tencent block storage (Zhang et al., |020 201 8) (24 "lencent-storage" traces), and Alibaba cloud storage (ali 2022 Li et al. 2020 Wang et al. 2022) (24 "alibaba-storage" traces). The cache capacity is set to 10% of the number of distinct objects in each trace.
To evaluate online bin packing solutions, we use 288 workload traces: BPPLIB library (Delorme et al.) 2018) (72 "Falkenauer-U" and 72 "Scholl-1" traces), Weibull distribution with parameter (shape=3, scale=45) (Castinciras et al. (012)) (72 "Weibull"), and Gaussian distribution with parameter (mean=0.3662, std=0.1416) Yan et al.
2022 (72 "Gaussian").
4.1 METAMUSE GENERATES HIGHH-PERFORIE
SOLUTIONS
compares top solutions, as selected by the average cache miss ratio over all 96 workload traces. Box plots show their miss ratio reduction with respect to FIFO.
Cache replacement. Figure 3
We first delve into results from GPT-4o. At the -prc-eeeet trace, MetaMuse achieves 5.17% 9.89% lower miss ratio than LLMdbased baselines, and 1755-13.03$2 lower than human heuristics. At the 75th -pereentee trace, MetaMuse achieves 3.62% 6.39% lower miss ratio than L-LM-based

---

Published as a conference paper at ICLR 2026
Mis Ratio Reduction
40
Mics Ratio Reduction from FIFO (86)
40
Miss Ratio Reduction from FIFO (56)
40
Miss Rakio Reducctoon
from FIFO (16
RIFO
22*
20
20
tiny InyssU
10
10
E
Repeeated
Sampling
Rebvv
MCTS-AHD
Opei Opan Evolve
Menkearch
MecaMose
Repeated
NCTS-AHD
OpenErohe
PlanSerrds
MectaMzee
Dupaatod
Opendvable
ManSaadd
rifo
Inu
sieve
sin
(a) GPT-4o
(b) Llama3,3-70B
(c) DeepSeek-V V3
(d) Human Heuristics
Figure 3: Comparison of top cache solutions generated by MetaMuse and the baselines. Each box plot represents the best solution from each model and shows the miss ratio reduction (relative to FIFO) across 96 traces. MetaMuse achieves higher reductions across nearly all percentiles and across different LLMs.
Usage Reduction (36)
12
Bin Usage Redurtion from first nit (36)
12
Bin Usage Reduction from first Rt (36) ne.
Bin Usarge Reduction from Rest FR (96)
24
first 4
Represted
Sampling
RiEvo
MCTS.MD-
OpenExolve
PanScarch
MataMuse:
Sampling
RoEvo
NCTS
Opentvolve,
PanSearch
Metallus
fwEvo
MCTS-HD
PanSearch
harmanic
moxt mi
wost
AWF
best de
(a) GPT-4o
(b) Llama3.3-70B
(c) DeepSeck-Ve V3
(d) Human Heuristics
Figure 4: Comparison of top online bin packing solutions generated MetaMuse and the baselines. Each box plot represents the best solution from each model and shows the bin usage reduction (relative First Fit) across 288 traces. MetaMuse achieves higher reductions across nearly all percentiles and across different L.Mss. We note that some human-designed heuristics are not visible because they perform worse than First Fit.
baselines, and 15.2%-55.76% lower than human heuristics. We also see improvement with Llama3.3 70B-at the 90th -percentte trace, MetaMuse achieves 2.41% %-7.20%% lower miss ratio than LLM- based baselines, and 1.94%-10.3444 lower than human heuristics; at the -eec-eeeee trace, MetaMuse achieves 3.67%-5.... 9-5.17% lower miss ratio than LLM-based baselines, and 5.48%-33.62%% lower than human heuristics. On DeepSeek-V3, at the perceeecee trace, MetaMuse achieves up to 6.05% lower miss ratio than LLM-based baselines, and up to 9.14% lower than human heuristics.
Online bin packing, Figure 4 compares top solutions, selected by the average bin usage all 96 workload traces. Box plots show their bin usage reduction, with respect to First Fit.
We first delve into results from GPT-4o. At the perceentee trace, MetaMuse achieves 9.25% 9.42% lower bin usage than LLM-based baselines, and 12.55%22.595 lower than human heuristics. At the 75th -peceeenet trace, MetaMuse achieves 6.94% 1.94%-7.75% lower bin usage than LLM-bbseed baselines, and 7. 7.56%--18... 18.36% lower than human heuristics. With Llama3-7B, at the 90th -percentile trace, MetaMuse achieves up to 0.19% less bin usage than LLM-based baselines, and up 12.50% lower bin usage than human heuristics. With DeepSeck-Ve V3, at the thth -pereeenee trace, MetaMuse achieves up 21. 1..6% less bin usage than LLM L-aee baselines, and up to 30.93% lower bin usage than human heuristics.
4.2 METAMUSE GENERATES THE MOST DIVERSE SET OF SOLUTIONS
Cache replacement. The discovery of useful solutions depends on having diverse solutions. We evaluate diversity by the number of solutions with distinct feedback embedding. Across all LLMs. MetaMuse consistently achieves higher diversity over LLMM-aseed baselines. From analyzing 350 solutions generated by each method GPT-40, MetaMuse has 1.47 more distinct solutions
7

---

Published as a conference paper at ICLR 2026
Repested Sampling presicus Repeated Sampling be! solutions]
Spper
7.5%
GPT-4o
Liama3,3-708
DecoSeek-V3
6056
S26
30%6-
15%
04
25000
33000
110
33800
Figure 5: MetaMuse generates a more diverse set of solutions. Using human- human-designed heuristics as cluster centroids, we find that the cluster sizes of SeetaMMus--geerateee solutions exhibit lower standard deviation. In contrast, baselines tend to concentrate on a subset of centroids.
average. On DeepSeek- V3, MetaMuse has 1.57 more distinct solutions on average. On Llama3.3- 70B, results show that MetaMuse can have 1.78 more distinct solutions on average.
Furthermore, we observe that having higher diversity translates into lower availability bias. We recall that Repeated Sampling tends to generate solutions that tightly cluster to well- human heuristics such as LRU, LFU, and FIFO, due availability bias (2.3). Using the nine human heuristics as centroids, empirical results show that MetaMuse reduces the cluster density (computed by num points in cluster ), for nearly all centroids. In other words, MetaMuse solutions are less moz_ prazzeuclidean. ceriiiddanddsstnnee tightly clustered than Repeated Sampling. For example, MetaMuse reduces the LRU cluster density by 35.28% (i.e., 6.15 down to 3.98). We see cluster density reduction even on the less common heuristics, e.g., the ARC cluster density reduces by 77.45% (i.e., 1.02 down to 0.23).
Finally, Figure Jsess human heuristics as centroids, and evaluate whether generated solutions tend to cluster to subset of centroids. Ideally, the cluster sizes should be uniform. The standard deviation of cluster size percentages for MetaMuse is 0.08/0.06/0.06 for H.PT-Ao/DeepSeek-V//// V3/Llamaa-7700 This is much lower than baselines: Repeated Sampling (0. 14/0. 110.11/0.111 1)), Repeated Sampling with previous solutions (0.11/0.11 1/0. ReEvo (0.14/0.10/) 1..00.0/0.10). 10), MCTS-AHD (0. (0.17/0.08/0.08) OpenEvolve (0. (0.19/0.19//
and PlanSearch (0. 10/.0.0/0//.99..
Online bin packing. We evaluate diversity by the number of solutions with a distinct feedback embedding. Across all LLMs, MetaMuse consistently achieves a higher diversity over LLM-based baselines. From analyzing 350 solutions generated by each method on GPT-40,, MetaMuse has 1.44x more distinct solutions average. On DeepSeek-V35 it has 1.80 more distinct solutions average. On Llama3-70B, it has 1.31 x more distinct solutions on average.
4.3 METAMUSE INCURS A Low PER-SOLUTION COST
We view a low per-solution cost as an important factor for driving the adoption of LLMs for creative ideation tasks. In the cache replacement case study, the average cost for MetaMuse to generate one full solution is 2.16 cents with GPT-4o, 2.11 cents with DeepSeek- V3, and 2.35 cents with Llama3.3. 3- These costs include using GPT-4o for code generation. For reference, running the Repeated Sampling baseline (with previous solutions) costs an average of 3.38 cents per solution.
Specifically, property extraction and problem mapping consume an average of 589.39/141. 1.55 in- put/output tokens per solution with GPT-4o, 982.60/233.77 6052 input/output tokens with DeepSeek-V V3, and 768. 2068.20/07..3 .50 input/output tokens with Llama3.3- 3-BB. Solution formulation consumes an av- erage of 934.04/230.2) 1 input/output tokens per solution with GPT-4o, 473.01/425.77 7.77 input/output tokens with DeepSeek- V3, and 409. 409.53/353.1 10 input/output tokens with eration consumes average of 1463.92/1190.0 2223.72/1937.29 input/output tokens with DeepSeek-V V3, and 2259.62/197 190.62/1999.89 input/output tokens with Llama3.3-700 We note that if an implementation is considered unsafe (55).
Code gen- input/output tokens per solution with GPT-4o,
). it is re-implemented.
8

---

Published as a conference paper at ICLR 2026
200
200
#Distinct Solutions
R5Sict
#Distinct Solutions
RSDK
Distingg G Salutions 15
RSSect
150
R52kckndthh
R50kk-nchh
1.4
140
140
RSBick3F-moi
RADiCE-F
120
120
120
1.00
100
40
20
Solutions
Salutions
Solutions
(a) GPT-4o
(b) Llama3.3-700
(c) DeepSeek-V V3
Figure 6: Comparison of the diversity of cache replacement solutions generated by different stimuli selection strategies: RSDict and RSDict-SF. "-noWR" denotes the removal of waypoint reasoning. Ideation is performed with different LLMs, while code generation is handled by GPT-4o. RSDict-SF (dashed lines) outperforms RSDict (solid lines). Removing waypoint reasoning (blue lines) reduces solution diversity compared with the full approaches (red lines).
4.4 SURPRISING DESIGNS FROM METAMUSE
In addition to quantitative evaluations, highlight MetaMuse-generatte designs that not im- mediately obvious to engineers. To do so, we look at top-performing cache replacement solution: MetaMuse-533 DDI. and MetaMuse-488 (+D.2).
One is the counter named NSE in MetaMuse-533. NSE deviates from the common belief of favoring newly admitted objects. Instead, it tracks the number of times that cached object has witnessed eviction events. It is used in the score calculation, along with recent access time and frequency counter. Effectively, MetaMuse-5555 (up to some thresholds). Our engineers hypothesize that NSE helps to learn objects' access patterns and prevent thrashing (Denning 1968).
behaves favor objects that have remained longer in the cache
Another is the use of hashing functions to segment the cache space in MetaMuse-488, which differs from the more common multi-tiere architecture. MetaMuse-488 tries maintain different groups of cache objects (as identified by their key hashes), and exercises per-group replacement policies in different segments. In contrast, engineers tend to use multi-tiered architecture, as a way to differentiate the importance of cache objects.
Finally, we highlight the use of saturating counters in MetaMuse-533, They increment until reaching pre-defined threshold. MetaMuse- deviates from conventional usage scenarios. which are to reduce storage overhead by capping the maximum value of a counter (Yang et al.) 2023) Corbato 1968). Instead, MetaMuse-533 seems use saturating counters to accumulate meaningful usage history, but not so much as to mislead eviction decisions. For example, a saturating frequency counter allows -33 to identify bursty objects, while preventing their counts from growing too large during the burst.
4.5 ABLATION STUDY
We test key components in MetaMuse using the case study of cache replacement algorithms.
Stimuli selection strategies. We test RSDict and RSDict-SF by running experiments on GPT-4o. First, the majority of RSDict and RSDict-SF solutions outperform Repeated Sampling solutions, and this demonstrates the value of having stimuli for steering ideation. Comparing solutions for the workload trace, 67.20% of RSDict solutions and 75.60% of RSDict-SF solutions have a higher cache hit ratio than Repeated Sampling. In addition, these hit ratios can up to 13.13% and 27.07% higher, respectively. Similarly, for the 75th -percentee workload trace, RSDict solutions and 72.40% of RSDict-SF solutions outperform Repeated Sampling. In addition, these hit ratios can be up 15.43% and 21. 21.93% higher, respectively.
66.80% of
Second, compared with RSDict, RSDict-SF has a greater number of solutions that can outperform Repeated Sampling. Empirical results show 12.50% and 8.38% more solutions, with respect to the 90th percentile and thth percentile of workload traces, respectively. Furthermore, looking at solution diversity, RSDict-SF results in 13.17% more distinct solutions than RSDiet.

---

Published as a conference paper at ICLR 2026
Waypoint reasoning. Figure 6/shows that waypoint reasoning enables MetaMuse to generate more diverse solutions. We fix the coding agents to GPT-4o. At each iteration, we instrument MetaMuse to generate solutions with and without waypoint reasoning. When ideating with GPT-4o (Figure 6ap. waypoint reasoning improves the number of distinct solutions from 149 to 175 for RSDict, and from 152 to 197 for RSDict-SF. When ideating with DeepSeek-V -3 (Figure 6c), waypoint reasoning improves the number of distinct solutions from 113 to 144 for RSDict, and from 1 119 to 140 for RSDict-SF. When ideating with Llama3.3 Figure 6b). waypoint reasoning improves the number of distinct solutions from 124 to 148 for RSDict, and from 129 to 154 for RSDict-SF.
DISCUSSION
Safeguards against unsafe solutions. In the case of system algorithms, three main errors can result in unsafe implementations: (!) long-running executions (e.g., exceeding 5 seconds), (2) excessive memory usage beyond user-specified limits, and (3) illegal behaviors (e.g., falsely claiming a cache hit when the requested object is absent). Our benchmarking environments monitor the per-run execution time and peak memory usage when evaluating each solution. Both can collected from the GNU time command. To detect illegal behaviors, we validate the returned object value against the expected value in the trace. From our experience, ~..88% of solutions generated by MetaMuse are classified as unsafe and subsequently discarded.
Finally, with Python scripts as the output, it is possible to leverage libraries in the Python ecosystem. We discuss ongoing efforts. One is performing unit tests, with libraries such as unittest (uni] 2025). Another is the design-code equivalence; we are exploring the use of LLMs to generate state machines from design descriptions and code implementations for the equivalence check.
Limitations and future discussion. First, our implementation explores an instantiation of external stimuli (33.2). which is specifically chosen for its generality and problem- aggossic nature. However, the MetaMuse framework is extensible to take in other instantiations, and future work will explore possibilities such as long-term reskerelated memories. Second, while our work currently focuses on fully automated ideation, an interesting direction is to explore whether subjective human guidance (e.g.. human expertise) could further improve the solution usefulness. Third, although we evaluate on real-world workload traces ($ deploying LLM-generated algorithms in business-critich production environments remains an ongoing collaboration with engineers at global cloud provider. We anticipate that lessons from this deployment effort will inform deeper practical impact.
Algorithm benchmarking costs. The RSDict-SF strategy considers the feedback embeddings of previous solutions (33.2T). which requires benchmarking each solution n workload traces. Such benchmarking can take a significant amount time and resources, especially they involve running an end-to-end system with long workload traces. If costs are prohibitively high, RSDict-SF may impact the practicality of MetaMuse. We note, however, that reducing benchmarking overhead is an active area of research in the systems community Akram & Sawalha (2019), with techniques such as discrete-event simulations, hardware acceleration, and parallelization. At the same time, we are exploring stimuli selection strategies that reduce reliance on extensive benchmarking.
Synergy with existing approaches. Although MetaMuse emphasizes creative leaps in the solution space, we recognize the value in related approaches that iteratively refine algorithm designs (Liu
et al. 2024b Ye et al., 2024 Zheng et al. 2025 Camnera-Paredes et al. 20244] Novikov et al. 2025 Sharma (025).. The two paradigms are complementary, in a way similar to human's 's divergent and
Novikov
convergent thinking processes. MetaMuse can provide the initial population of solution candidates, which can then be further improved by the iterative refinement approach.
6 CONCLUSION
To practically drive algorithm generation, MetaMuse is framework of creative ideation that mitigates availability bias in LLMs. MetaMuse combines three self-reflection principles, guiding the stages of creative ideation. Evaluations show that it can generate seghhherformin solutions for two high-impact problems at a global cloud provider: cache replacement and bin packing algorithms. Furthermore, observe surprising design considerations not immediately obvious to human engineers.
10

---

Published as a conference paper at ICLR 2026
Reproducibility statement. Key prompts are included in the appendix ($C are publicly available at htttss://githiii com/illinois www.liooossnnnnaetaaaaaaaa
The code and datasets
Ethics statement. This work poses ethical issues.
Acknowledgments. We thank Encheng Xie (University Illinois )hamma-Caamm)inn) for his valuable diseussions and contributions to the experiments.
REFERENCES
Alibaba Block Traces, 2022. URL
unittest - Python Unit Testing Framework, 2025. URL https::/doos..yvtoooor/// uni unittest.hhml
David H. Ackley, Geoffrey E. Hinton, and Terrence Sejnowski. A Learning Algorithm for Boltzmann Machines. Cognitive Science, 9(1, 1985.
Ayaz Akram and Lina Sawalha. A Survey of Computer Architecture Simulation Techniques and Tools. IEEE Access, 2019.
Omid Alipourfard, Hongqiang Harry Liu, Jianshu Chen, Shivaram Venkataraman, Minlan Yu, and Ming Zhang. CherryPick: Adaptively Unearthing the Best Cloud Configurations for Big Data Analytics. In NSDI. USENIX, 2017.
Margaret A. Boden. Creativity and Artificial Intelligence. Artificial Intelligence, 1(2), 1998.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher R, and Azalia Mirhoseini. Large Language Monkey: Scaling Inference Compute with Repeated Sampling. 2407 21787 2024.
https://doi http:///ooooorg//////// wwg.
48550/arXiv orgg//0..355//ariii
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, Harsha Nori, Hamid Palangi, Marco Tulio Ribeiro, and Yi Zhang. Sparks of Artificial General Intelligence: Early experiments with GPT-4. https://doi.orr//e 48550/ 2303. 12712 2023.
Ignacio Castineiras, Milan de Cauwer, and Barry O' S'Slliia... Weibull-Based Benchmarks for Bin Packing. In International Conference Principles and Practice of Constraint Programming, 2012.
Honghua Chen and Nai Ding. Probing the Creativity of Large Language Models: Can Models Produce Divergent Semantic Association. In EMNLP, 2023.
Audrey Cheng, Shu Liu, Melissa Pan, Zhifei Li, Bowen Wang, Alex Krentsel, Tian Xia, Mert Cemri, Jongseok Park, Shuo Yang, et al. Barbarians at the Gate: How Al Upending Systems Researc. arXiv preprint arX1v:2510.06189, 2025.
Fernando J Corbato. A Paging Experiment with the Multics System, 1968.
Cortez, Eli, Bonde, Anand, Muzio, Alexandre, Russinovich, Mark, Fontoura, Mareus, Bianchini, and Ricardo. Resource Central: Understanding and Predicting Workloads for Improved Resource Management Large Cloud Platforms. SOSP. ACM, 2017.
Maxence Delorme, Manuel lori, and Silvano Martello. BPPLIB: A Library for Bin Packing and Cutting Stock Problems. Optimization Letters, 2018.
Peter J. Denning. Thrashing: Its Causes and Prevention. In AFIPS. 1968.
György Dósa and Jirí Sgall. First Fit Bin Packing: A Tight Analysis. In STACS, 2013.
György Dósa and Jifí Sgall. Optimal Analysis of Best Fit Bin Packing, In ICALP, 2014.
Rohit Dwivedula, Divyanshu Saxena, Aditya Akella, Swarat Chaudhuri, and Dachyeok Kim. Man- Made Heuristics Are Dead. Long Live Code Generators! Proceedings of the 24th ACM Workshop Hot Topics in Networks, pp. 51-60, 2025.

---

Published as a conference paper at ICLR 2026
Gil Einziger, Roy Friedman, and Ben Manes. TinyLFU: A Highly Efficient Cache Admission Policy. ACM TOS, 2017.
Huang, Qi, Birman, Ken, van Renesse, Robbert, Lloyd. Wyatt, Kumar, Sanjeev, Li, and Harry C. An Analysis of Facebook Photo Caching. In SOSP. ACM, 2013.
David S. Johnson. Near-Optimal Bin Packing Algorithms. PhD thesis, Massachusetts Institute of Technology, 1973.
Elaine Kant. Understand and Automating Algorithm Design. IEEE TSE, 1985.
Robert Tjarko Lange, Yuki Imajuku, and Edoardo Cetin. Shinkaevolve: Towards Open-Ended and Sample-Efficient Program Evolution. arXiv preprint arXiv:2509. 2025.
Chan C. Lee and Der-Tssai Lee. A Simple On-Line Bin-Packing Algorithm. Journal of ACM, 1985.
Li, Jinhong, Wang, Qiuping, Lee, Patrick P. C., Shi, and Chao. An In-Depth Analysis of Cloud Block Storage Workloads in Large-Seuurr Scale Production. In IISWC. IEEE, 2020.
Chieh-Jan Mike Liang, Hui Xue, Mao Yang. Lidong Zhou, Lifei Zhu, Zhao Lucis Li, Zibo Wang. Qi Chen, Quanlu Zhang, Chuanjie Liu, and Wenjun Dai. AutoSys: The Design and Operation of Learning-Aummented Systems. In ATC. USENIX, 2020.
Di Liu, Meng Chen, Baotong Lu, Huiqiang Jiang, Zhenhua Han, Qianxi Zhang, Qi Chen, Chen- gruidong Zhang, Bailu Ding, Kai Zhang, Chen Chen, Fan Yang. Yuqing Yang, and Lili Qiu. RetrievalAAteention: Accelerating Long-Context LLM Inference via Vector Retrieval. In NeurlPS Workshop Efficient Natural Language and Speech Processing, 2024a.
Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang. Zhichao Lu, and Qingfu Zhang. Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model. https:://di..rrg/// www.:////..../////////
2481.
2024b.
Yiren Liu, Pranav Sharma, Mehul Jitendra Oswal, Hajjun Xia, and Yun Huang. PersonaFlow: Boosting Research Ideation with -imuullee Expert Personas. https://doi. http://ooo.orgg//// org/10. 48550/
arXiv.2409. 12538 2024c.
Megiddo, Nimrod, Modha, and Dharmendra S. ARC: A Self-Tuning and Low Overhead Replacement Cache. In FAST. USENIX, 2003.
Pronita Mehrotra, Aishni Parab, and Sumit Gulwani. Enhancing Creativity in Large Language Models Through Associative Thinking Strategies. https://doi. org/10. 48t11...88///iiiii 2485.06715 2024.
Michael Mitzenmacher, Andrea W. Richa, and Ramesh Sitaraman. The Power of Two Random Choices: A Survey of Techniques and Results, 2001.
Alexander Novikov, Ngan Vu, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wag- ner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Push- meet Kohli. and Matej Balog. AlphaEvolve: A Coding Agent for Scientific and Algorithmic Discovery. Technical report, DeepMind, 2025.
Reimers, Nils, Gurevych, and Iryna. Sentence-BERT: Sentence Embeddings using Siamese BERT-
Networks. In ACL. ACL, 2019.
Bernardino Pomera-Paredes. Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, and Alhussein Fawzi. Mathematical Discoveries from Program Search with Large Language Models. Nature, 2024.
B. Sankar and Dibakar Sen. Novel Mathematical Framework for Objective Characterization of Ideas through Vector Embeddings in LLM. https://doi. 4055//000.445///// 48550/arXiv 2409 07578 2024.
Asankhaya Sharma. OpenEvolve: An Open-Source Evolutionary Coding Agent, 2025. URL
https://gg a htt.:///....oo...ooeeeeeeeeeeeee
12

---

Published as a conference paper at ICLR 2026
Charlie Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters. https:///6i.orr/// / arXiv.2408.0 03314, 2024.
Amos Tversky and Daniel Kahneman. Availability: A Heuristic for Judging Frequency and Probabil- ity. Cognitive Psychology, 1973.
Vaccaro, Michelle, Almaatouq, Abdullah, Malone, and Thomas. When Combinations of Humans and Al are Useful: Systematic Review and Meta-analysis. Nature Human Behaviour, 2024.
Wan, Qian, Hu, Siying, Zhang, Yu, Wang, Piaohong, Wen, Bo, Lu, and Zhicong. It Felt Like Having Second Mind: Investigating Human-AI Co-creativity in Prewriting with Large Language Models. HCI, 2024.
Evan Z Wang. Federico Cassano, Catherine Wu, Yunfeng Bai, William Song, Vaskar Nath, Ziwen Han, Sean M. Hendryx, Summer Yue, and Hugh Zhang. Planning in Natural Language Improves LLM Search for Code Generation. In ICLR, 2025.
Qiuping Wang, Jinhong Li, Patrick P. C. Lee, Tao Ouyang, Chao Shi, and Lilong Huang. Separating Data via Block Invalidation Time Inference for Write Amplification Reduction Log-Structured Storage. In FAST. USENIX, 2022.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Thain-of-Thought Prompting Elicits Reasoning in Large Language Models.
https://doi.org/// 48550//r5...
arviv. 2201. 11903 2023.
Jie Yan, Yunlei Lu, Liting Chen, Qin, Yixin Fang, Qingwei Lin, Thomas Moscibroda, Saravan Rajmohan, and Dongmei Zhang. Solving the Batch Stochastic Bin Packing Problem in Cloud: A Chance-constrained Optimization Approach. In KDD. ACM, 2022.
Yang, Juncheng, Zhang, Yazhuo, Qiu, Ziyue, Yue, Yao, Vinayak, and Rashmi. FIFO queues are all you need for cache eviction. In SOSP. ACM, 2023.
Juncheng Yang, Yao Yue, and K. V. Rashmi. A Large Scale Analysis of Hundreds of In-memory Cache Clusters at Twitter. In OSDI. USENIX, 2020.
Andrew Chi-Chih Yao. New Algorithms for Bin Packing. Journal of ACM, 1980.
Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. Reevo: Large Language Models as Hyper-Heuristics with Reflective Evolution. In NIPS, 2024.
Yazhuo Zhang, Juncheng Yang, Yao Yue, Ymir Vigfusson, and K.V. Rashmi. SIEVE Is Simpler Than LRU: An Efficient Turn-Key Eviction Algorithm For Web Caches. In NSDI. USENIX, 2024.
Yu Zhang, Ping Huang, Ke Zhou, Hua Wang. Jianying Hu, Yongguang Ji, and Bin Cheng, Tencent 2018.
Block Storage Traces.
Yu Zhang, Ping Huang, Ke Zhou, Hua Wang. Jianying Hu, Yongguang Ji, and Bin Cheng. OSCA: An Online-Model Based Cache Allocation Scheme in Cloud Block Storage Systems. In ATC. USENIX, 2020.
Zhi Zheng, Zhuoliang Xie, Zhenkun Wang, and Bryan Hooi. Monte Carlo Tree Search for Compre- hensive Exploration in LLM-Based Automatic Heuristic Design. https://doi. 008550. arXiv. 2501. 08603 2025.
13

---

Published as a conference paper at ICLR 2026
A LLM USAGE STATEMENT
LLMs did play significant role in the research ideation or writing process (beyond grammar checking) and are therefore not considered contributors.
B CACHE WORKLOAD TRACES
To show their access patterns, we plot one trace from each data access scenario (Figure 7). The z-axis denotes a virtual timestamp, which is the number of cache accesses thus far. The y-axis denotes the accessed objects. Their IDs are sequentially assigned, following the chronological order of the time they appear for the first time. The intervals between the gray vertical lines equal the cache capacity, which is set 10% of the trace footprint (i.e., the number of distinct object IDs).
We detail the traces for evaluation cache replacement in Table ($4).
scenario
ra-fwe
ra-multikey
tencent-storage
alibaba-storage
release year
2024
2024
2020 53503.79 225.125
2024
avg #cache accesses
10598.42
27390.71 1092.29
7582.08
avg #distinct objects
938.54
4108.83
Table 1: The data access scenarios of cache replacement used in this work. Each scenario consists of 24 cache traces.
Object ID
Object
Time
Time ra-multikey
(a) ra-fwe
Object ID
Object
Time
Time
(c) snscentsttorge
(d) alibaba-storage
Figure 7: The access pattern of cache trace from each data access scenario.
C PROMPTS
C.1
IDEATION PROMPTS
Repeated Sampling uses the following prompt for solution formulation, generating its natural language description:
The Idcation Prompt for Repeated Sampling
You are an expert in computer systems. Your task is to create an innovative cache replacement policy.
Provide your creative policy using the following JSON structure:
"metadata":
"use few sentences to summarize the metadata specifically maintained by the policy here",
14

---

Published as a conference paper at ICLR 2026
"evict"; "use few sentences to summarize how the policy chooses the eviction victim here",
"update_after after hit": "use few sentences to summarize how the policy updates **each** of the metadata it maintains immediately after a cache hit here",
"update_afted insert":
"use a few sentences to summarize how the policy updates **aach** the metadata it maintains immediately after inserting new object into the cache here",
"update lupdate_after, after
evict": after_evict":
"use few sentences to summarize how the policy updates **each** of the metadata it maintains immediately after evicting the victim here"
}
Do not include any additional text explanation in your response.
We use PlanSearch's 's original prompts (Wang al. 2025) generate observations. These observations are then inserted into the placeholder [[hints]] of the following prompt for solution formulation:
The Ideation Prompt for PlanSearch
You are an expert in computer systems. Create an innovative cache replacement policy using the following hints:
[[hints]]
Provide your creative policy using the following JSON structure:
"metadata"; "use few sentences to summarize the metadata specifically maintained by the policy here", "evict": "use a few sentences to aummarize how the policy chooses the eviction victim here",
"update_after_hie aat_aafttter_itee "use few sentences to summarize how the policy updates **each** of the metadata maintains immediately after cache hit here",
lupdate_afters insert": "use few
the policy updates **each** the metadata it maintains immediately after inserting new object into the cache here",
summarize
"update "update_after, evict": aftetterietttt:;
"use few sentences to summarize how the policy updates **each** of the metadata it maintains immediately after evicting the victim here"
Do not include any additional text or explanation in your response.
MetaMuse uses the following prompt for property extraction and problem mapping. They are the first two waypoints ($3.3)
The Waypoint Reasoning Prompt for MetaMuse
You are an expert in computer systems. Your task to use the concepts inspired by the given word phrase to design creative ideas for cache replacement policies.
Answer the following format:
<The given word phrase> relates to the concept of <concept 1>, <Concept 1> relates to <Concept 2>.
<Concept n-1> relates to <Concept n>
Inspired by <Concept n>, <your creative ideas for cache replacement policies in few sentences>. Example 1:
The given word or phrase: angular momentum.
Answer:
"Angular momentum" relates to the concept of "rotation".
"Rotation" relates to "cycle".
Inspired by "cycle", a cyclic pointer can be maintained track cached objects and determine eviction victims.
15

---

Published as a conference paper at ICLR 2026
Example 2:
The given word or phrase: zebra. Answer:
"Zebra" relates to the concept of "stripe".
"Stripe" relates to "segmentation". Inspired by "segmentation", a cache can be divided into segments with different eviction priorities, and each segment can use distinet eviction policy.
The given word or phrase: [[word]]
Do not include any additional text or explanation your answer.
For solution formulation, MetaMuse uses the same ideation prompt as PlanSearch. The placeholder [[hints]] will be replaced with the observations derived from the first two waypoints.
C.2 CODING PROMPTS
All methods use the following prompt to implement a solution in Python. The place- holders, [[metadata]], [[evict]]. [[update_ [[update_after_hin aftlt heppdate_afte_evve
sattaate__fte__isssseee will be filled in with the corresponding fields in the JSON-formatted output of the ideation prompts. [[design]] will be filled with concatenation of these fields.
and
The Coding Prompt
You are an expert in Python. Your task is to implement deterministic cache replacement policy in Python without any randomness. You only reference the attributes provided below. You have read-only access to these attributes and no access to any functions.
Accessible attributes:
"object" represents the unit of a request, such as inserting an object into the cache or retrieving an object from the cache. Each object 'bj'' provides the following read-only attributes that you can reference:
koyj.key' (str): A string that uniquely identifies the object.
'obj.size' (int): positive integer representing the size the object bytes.
You also reference the following read-only attributes provided by cache snapshots 'cache :aathshot'
'cache_ snapshot.cam cache' (dict): dictionary containing the cached objects, where the keys the bogjects'keys, and the values are the corresponding objects themselves. stache_snapsher in bytes.
(int): non-negative integer representing the current total size of the cache
"cachh_snapshotteee www.ssoo..caaccitt........ (int): positive integer representing the maximum allowed size of the
cache in bytes.
'cache srss_ssapsshtttee access
accces_cconn' count' (int): The current total number of cache accesses. You can also
use this to represent current time.
"cache_ saache_snapshothhee couuti''_t' (int): The current total number of cache hits.
'cache snapshot.miss mistticcsssuuutii (int): The current total number of cache misses.
The eache replacement policy you need to implement is described below:
Cache replacement policy: [[design]]
Implement this policy using the Python code framework below. Your implementation must strictly follow the comments in this Python code framework.
Code framework:
You must not alter the provided code framework. Also, keep the two comments "# Put tun- able constant parameters below" and "# Put the metadata specifically maintained by the policy below" unchanged. Wrap your code with "python and and include nothing else in your answer.
The code framework is shown below:
Import anything you need below. must not use any randomness.
# For example, you cannot "import random". Also, you cannot use any # function in "numpy" that uses randomness, such as the functions in "ummyy random'. Put tunable constant parameters below
Put the metadata specifically maintained by the policy below. [[netadata]]
16

---

Published as a conference paper at ICLR 2026
def evict baacceesnapsho,, obj):
This function deei how the policy chooses the eviction victim. [[evict]]
Args:
"acche jaacheeeapshht enapshot the current cache state.
oobj": The new object that needs to be inserted into the cache.
Return:
"'aaniid obj _oo_ The key of the cached object that will be evicted make for "bbj".
...
candid_obj_kee None
# Your code below
return candid_obj
def podate_aftess teatter_hitttt (cache_ (cache_snapshot, obj):
This function defines how the policy update the metadata it maintains immediately after a cache hit.
[[update_aften Bittaate_aftr_hiee [it]]]
Args:
"cache snapshot": snapshot of the current cache state.
:obj": The object accessed during the cache hit. 'None"
Return:
# Your code below
def podate_after saattte__trr___serttteee insert (cache_ baraache_sapphht.. obj):
This function defines how the policy updates the metadata it maintains immediately after inserting popdatte_afte_iinsee
object into the cache.
Args:
cache_ saache_amapshtt: : A anapshot of the current cache state.
- "obj": The object that was just inserted into the cache. Return: "None'
...
# Your code below
def update_after (erttee_ericttcccc____e.ee smapshot, obj, evicted_obj):
This function defines how the policy updates the metadata it maintains inmediately after evicting the victim.
[[update_after_evi]
Args:
cache "rache_saappppeeeeeee snapshot": : snapshot the current cache state.
=objj" The object to be inserted into the cache.
"evicted_oby obj": The object that was just evicted from the cache.
Return: "None"
Your code below
D CASE STUDIES
D.1 METAMUSE-533
Import anything you need below. must not use any randomness.
# For example, you cannot "import random", Also, you cannot use any function
# in "numpy" that uses randomness, such as the functions in numpy.random.
Put tunable constant parameters below
17

---

Published as a conference paper at ICLR 2026
MAX PREDICTIVE, SCCREE 100
MAX MAX_ENTIN ENTROPY 100
100
MAX_ACCESE FREQUENCY
ACCESS_FREQUENCY
100
MAX_ LAX_REENCY 100
MAX MAX_ DIFFERENTIAL BAEEAAALPRRVA_ALEEEA NOISE 100
# Put the metadata specifically maintained by the policy below.
# The policy maintains predictive likelihood scores, stochastic model outputs,
data entropy values, neural alignment scores, access frequency, recency, correction codes,
differential privacy noise factors, quantum and deep reinforcement learning model state-action values.
metadata =
prrdeltoive_likkeliooddd www.eihooeeeeeeeeee : 0,
"stochastic_model_ outputs': O, wut.uoodallotuuuaas....
cestt__entroy__vallee
O
"noural__ligmment_ee" scores': 0,
"access_frequenqe" O,
'recency': O,,
'differential_priveen moise factors': O,
"quantuummee _arpaam_errrrr__e wtw.eerrrroooorttiontt codes': O,
Baap____state__atte values': +
}
def evict (cache (cachhessaasphhot obj):
This function defines how the policy chooses the eviction victim. The policy chooses the eviction victim by combining predictive likelihood scores, stochastic model outputs, data entropy values, neural alignment scores, access frequency, recency, and differential privacy noise factors, adjusted by the deep reinforcement learning model's recommendations to balance performance, privacy, and future access predictions. Args:
"'cache ssteesssappssspsse snapshot the current cache state.
='obj" The new object that needs to be inserted into the cache.
Return:
'candid :ey" The key of the cached object that will be evicted make for "obj".
...
candid _ondid__bj___e = None min_ score float A'ooa('inff ('inf')
for key, cached_obj cache_snapshot. www.esssspshttcccheeee cache. ittmss)
score
metadata peeeeeiitieeliieeleeeeee sccoressssesseeeeee '] get (key, 0)
metadata staabatadssttchaattc_mddddll outputsssluuutssteeeeeeee '] get (key, 0) +
l (.eettteeeeeeeeeeeeeee (key, 0)
sccrreeeettttteeeeeeeeeeeeeeeeet get (key,
metadatal' aaacccess_rreuuuccy""... (key, 0)
metadata "reeency')
Setadata("recoccy")..o g.e (key, 0)
metadata l
factors ] gettkky, 0)
if score < min__scre:
min_score score score
candid_ bondid_obj_aee obj_key key
return candid_obj_key
def update_afted hit (cache ciitcchc__esapshht snapshot, obj):
This function defines how the policy updates the metadata maintains immediately after a cache hit. After cache hit, the policy increases the predictive likelihood score, updates the stochastic model, recaleulates data entropy, adjusts the neural aligument score, updates access frequency
18

---

Published as a conference paper at ICLR 2026
and recency, recalculates the differential privacy noise factor, and updates the state-action values the deep reinforcement learning model.
Args:
""cache_saaphheee A snapshot of the current cache state.
oobj The object accessed during the cache hit.
Return: "None'
...
key obj.key
metadatal metadata["pretictive ood sccorre '] [key] min(
predictive metadata("prredcctive likelihood, scooodsdsssssseeseo ' get (key, 0) +
metadata
MAX [M__PREDICTIVE_SCOS
[key] min( -get 0) +
MAX_ Sw__PPRDICTIVE__SOUI
netadata'' ettpalddtaaaettr___aaaaa entroeyn "vtrooyy_aluus]) [key] min(
metadata['data wttpdddttaettyyaallllaeee '] JJgettteeyyy 0) 1,
MAX_ENTIN MAX_ENTROPY)
metadatal neurral waa.aaalllgnnntoooonoooe
[key] min(
metadata('neural wwwaaaaletttttooreeeeeeeeeoeeeee
get (key, 0) 1,
MAX MAK_NEURALLAALIGWWAA
metadata acceessreccceeeeereuueeeee"""""" [key] min(
metadatal'accees___o "etadattt"access__rreeenng"" get (key, 0) + 1, MAX_ MAX_ACCESS_ BLL_AACCC_ERUUUEEESS FREQUENCY)
metadata["reccnnqy" [key] cache cache_ www.shot...coooooccooo.... access, count
metadata detadataa wwwpeeettttiaippiiiiceeeeeaeeeee wwweelooooe____eeeeeeeeeeeeeeeee factors'' [key] min(
matadataa[cdiffeernniaaaa privacy. wtwivvcyccniiseeeeeeeeeeee moise
sarraccy_oiieffcttorrreee factors g.geet (key, 0) 1,
MAK_DIFFEARNTIAA.PRRVACS
metadata detpaattaaeeeeeee__stteeeeeeee aat_tintion_o casoon_aalleslllla [key] min(
('eaadata''deep__ee r1_ irtaateaction___ee values' '] get (key, 0) 1,
MAX SAM_PREDICTIVE_SCORE
def apdate_after_iiee ceteerinneerttee (caacheeaaaphhpeeeeeeea obj):
This function defines how the policy updates the metadata it maintains immediately after inserting a new object into the cache,
After inserting new object, the policy initializes the predictive likelihood acore, updates the stochastic model, calculates initial data entropy, sets the neural alignment score, initializes access frequency and recency, assigns differential privacy noise factor, generates quantum error correction codes, and updates deep reinforcement learning model to include the new state.
Args:
"'cache_ Saach__sapshoot: A snapshot of the current cache state. "obj : object that was just inserted into the cache.
Return: "None"
key obj.key
htwpiihoooddccrrseeeeeeeee '] [key]
setacatta"stoccastiic
httpemmmmoouuuttteeeeeeesessesee outputs '] [key]
betaaatta(ddataaenttoo... values' [key]
metadata[[neural_aliggn _sorrtssssrsssssss [key] =
betccata((access_freqeanyyy [key] =
m [key] sacche_smpphott.. cacces__cuuas
factors' '] [key]
eotadatal'quantummmmmm metadata shep_rl_statee
metadatal quantum error prrror_correction_ccmm codes' ]] [key] 1
values [key] = 1
def wwt.arreeeeictcaccceeeeeeeeeeeee
obj, evicted_obj):
This function defines how the policy updates the metadata it maintains immediately after evicting the victim.
After evicting victim, the policy removes metadata, updates the stochastic model, recalculates data entropy for remaining entries, adjuste neural alignment scores, adjusts differential privacy noise factors, updates quantum error correction codes, and retrains the deep reinforcement learning model to adapt to the cache state.
19

---

Published as a conference paper at ICLR 2026
Args:
cachee seteeesssapshotste snapshot current cache state.
"obj": The object to be inserted into the cache. "ovicted_obj": The object that was just evicted from the cache.
Return: "None"
evicted key evicted_ o
if key in metadata (aaindataapppdiiiccii pepeeeiitieelleeelllll saaiiihood_scoress del metadatal petadatal ppredictive_lie preddcttiv__lleelthood httpeeeeeeeeeeeooeooooooooeeeeee if evicted_kep key in metadata["stoccarst socoooddssssssseeooo [evicted_ key]
model_ outputs :]
del
[evicted_ke]] key]
if evicted_ked in metaadata""datteennrtpoo del metadata hataaaaaaaaatttoppaaaaaaeeeeeeee if evicted_ key in mettabatt("Teeuraaalaaageeeeneee _ccorssssssssssse ]]:
del | [evicted if evicted_key in setaaaatt(ssccees__frruuueall""" del metadata ) [evicted_key 1f evicted_key in metadatta["reccnny"]] del metadata[ (aaaaatarrrcconooooeeecceeeeeee if evicted_ken in mataalatal(difffeeettiiaappppp httpl/vacyooisseacttteee factors del metadata ataeraaaee..eerrrriaapparrraaaar factore factors [evicted_key])
if evicted_kee key in metadata Siciadattllqqnannmmeerrea hatpinttu__errrrreeeeeeeee cor.rrcoorreeiionnnncoooo coo_codee del pooodatal'quantiiin if evicted key in metadata Srradatal'dee__11 state.ttee__..eeeeeeeeeeee action values']
error_ ctror_correction_cooo codes [evicted_
del metadata[" ['deep_rr] rl_.rrrstttee_eee staassatttttttnnnnttas action, values [evicted key]
# Recalculate data entropy for remaining entries for key in cache_snaye saatheessassho..ceeee cache:
metadata data dattaaatttopy__ao_eaaaaaaaaa_lee "ettrop_values'') [key] min(
metadata ['data_eddeleeeae catttaeenttop__vlliaee values get (key, 0) 1, MAX_ MAX_ENTROPY)
Adjust neural alignment scores
for key in cache sacchesnapshot.... cache:
metadata sitadatta'nneural m'nuurall al aeliinnnn__aeet scores [key] min( metadata (needaa neural Lalllaalggga awwgamenttacooeeeeeeeeeeeeeaeeee acores 'I get (key, 0) 1,
MAX MEEURAALALTIGMENTT
Adjust differential privacy noise factors
for key in cache cacheaasaapaaaeeeeeeeaa wwwpssat..saaaaaaeoooeooo cache:
metadata[ differential seliferrntiall_pivacc.... wwrrvacy_noiis___. factorss 'I .get (key, 0) 1,
factors' [key] min( metadata I differential ptt.ffrrrrrtiilllppiiaayyye
Update quantum error correction codes
for key in cache wateeessasshhtccceeeeee cache:
metadata quantumm error weweerrrerrreeeeeeeeeeeeeeeeeeee metadata [' quantum,
correction, codeal/ooooooe__o [key] min(
] gete (key, 0)
SAX_PPREDICTIVE_SCMR
# Retrain the deep reinforcement learning model
for key cache_ sertheessapshottcom cache:
cache:
metadata (deetaadd''ee_eeee d'ed_er__stat_, iattataaationn values [key] min(
metadata deep_rl_edd__eeeeeeeeeeddeeeeeee state_actteee ceatte_cctinn__oee values') .ee (key, 0) 1,
MAX, MAX_PREDICTIVE_SCORE
D.2 METAMUSE-488
PARTITION COUNT INITIAL_PRIORITY
Number partitions based on usage patterns
NITTAL_RAARTT, -
metadata
20

---

Published as a conference paper at ICLR 2026
# List of dictionaries for 'partitions:: IO for range (PARTITION_COUTTT)
each partition
priority_scores O, # Dictionary mapping obj key to priority score
'rarity_scores',
scores': O, # Dictionary mapping obj key to rarity score
'timestamps': O # Dictionary mapping obj key to access timestamps
def (vichecache, ( obj);
candid _oddiddobj__i key None
for partition metadatal partitions
Find the least priority and rarity score item in the partition candidates sorted(
partition.items())
key=lambda item:
metadata petadata priority_scores [i]em[O]],
metadata (aaiiattarrrrty..... "arrrrrrtsooreeee [item[O]], metadata (wtpatttattmmmtttaaaaaa tttmmestamps' ] [item [0]]
if candidates:
candid_obj _aadd__b_keeee_eee candidates [0] [o]
break
return candid_obj_kee
def update_after -cattrrhhhcc saaccchcsssapphhot, obj):
metadata["timestann [ob] keyl cache_sne facheessapshott.o accessttcccsssssccc count
metadata("rarityyssaa frequency
[ob] key] += 1 Increase rarity score based on access
Reevaluate priority within the partition Here we aasume a simple priority adjustment baaed on acceas frequency
metadatal' ponoddtttppriortty.... sariority_scorees [ob]. key] max(
metadata[" motadata("prioortyy.coo
[ob] key], metadata Saaritysscrees '] [obj kke])
aateerfissettteeeeeeee def update_ _ateeerffr_r__ee ii_iininetttc (cache srtachh_enapshot. obj):
partition_inan index hash (ash(objkeey) % PARTITIOO_COOIS
metadata partitions') p [partition_inann ind_i]]d]]]]]__ [obj key] = obj
metadata wawpilaaaappiiooot__eaeeeee
[obj key] INITIAL_ PRIDRITY
metadata(' saaicccrrrrrrtt_sooooree metadata[ ttinestaapsm [obj key]
[obj key] INITIAL RARITY
cache www.spatt.accees_coomm. access_count
def gogaat_affte_eeee partition_indes hash(evicted_ key) PARTITION COUNT
saaaccht___ashhtt,, obj, evicted_obj). COUUT
if evicted_ob] kke in metadata ('raaa(pppaa'i ('partitiinns del metadata uetadatal"partitiions" l'partitions'' [partition intertitionnindexlll [evicted_ob] objj key]
[partition_inded
[eviccce del metadata "aseadattlpriorityy_ee periority_scorres [evicted_oot _obieeeddddoooooee key]
del metadata "raritt_scorree [evicted_ooe key] del metadata 'timestamps" [evicted_ob] obj.ttee
# Rebalance partitions based on current usage patterns for partition in metadata[' paarttttaoattiiioons] for key partition:
Simplistic strategy to adjust priority and rarity scores detadatal'priority.ee periority_sccrre'' [key] max(
INITIAL PRIORIT,, pettaata metadata[' scores [key] max(
'] [key] 1)
INITIAL_RARITY, metadata seaddaal'rartty_eee 'rarity_scores [key]
D.3 COMPARE RSDICT RSDICT-NOWR USING AN EXAMPLE
We compare RSDict and RSDiet-noWFl with a concrete example on cache replacement to illustrate waypoint reasoning.
21

---

Published as a conference paper at ICLR 2026
RSDict and RSDict-noWR both use the stimuli set (best, impose, extra, pale) generate cache replacement policies.
D.3.1
PROPERTY EXTRACTION
RSDict reasons about the problem-relate property of each stimulus:
best - comparison + ranking
impose + authority + hierarchy
extra - surplus + overflow
pale + fading- - decay
D.3.2 PROBLEM MAPPING
RSDict maps the extracted properties the problem domain generate observations:
ranking - objects in the cache can be ranked based on access frequency or recency, with the lowest-ranked objects being evicted first
hierarchy - a hierarchical cache replacement policy can be developed where objects are ranked based on importance, and lower-ranked objects evicted first
overflow + cache replacement policy can focus on evicting the least valuable entries to make room for critical ones that exceed the cache's immediate capacity, essentially creating priority- based overflow management system
decay - a cache replacement policy can use a decay function to gradually decrease the priority of cache entries, selecting the least 'bright' or least relevant items for eviction
D.3.3 SOLUTION FORMULATION
RSDict designs solution using the observations:
The policy maintains metadata including access frequency, recency of access, hierarchical importance, and a decay score for each cache entry. A dual ranking system assigns composite score based these factors.
metadata:
update_ _ater__httta hit: The policy calculates a composite score using access frequency, recency, impor- tance rank, and decay values to identify the lowest scored entries for eviction, prioritizing those near threshold in the hierarchical cache structure.
update after insert: After cache hit, the access frequency and recency values are incremented, the decay function is reset or slowed, and hierarchical importance may be updated to reflect improved relevance.
update_afted after_evict, Post eviction, the metadata recalibrates the hierarchical importance thresholds, updates decay dynamics, and modifies frequency/recenny metrics for remaining entries to ensure balanced prioritization.
RSDict-noWR directly uses the given stimuli to generate solution:
The policy maintains metadata including a "Pale Access Frequency" score for each entry, representing its likelihood of future accesses, and "Extra Usage Counter" to track rare intense usage patterns. Additionally, it includes 'Best Recent Utilization' timestamps, recording the time since the last access.
metadata:
evict: The policy chooses the eviction victim by identifying the entry with the lowest "Pale Access Frequency" score, the lowest 'Extra Usage Counter', and the oldest 'Best Recent Utilization' timestamp, focusing on entries least likely to be used in the near future.
update_after after hit: Upon cache hit, the policy increases the 'Pale Access Frequency' score and "Extra Usage Counter" for the accessed entry, boosting its likelihood to stay, and updates the 'Best Recent Utilization' timestamp to the current time.
object, the policy initializes its "Pale Access Frequency" score and "Extra Usage Counter" to default low values, indicating an unbiased entry yet to prove its importance, and sets the 'Best Recent Utilization' timestamp the current time.
update after insert: After inserting
22

---

Published as a conference paper at ICLR 2026
Miss Ratio Reduction
40
from FIFO (%)
20
MetaMuse
MetaMuse (cache-reletad stimuli)
Figure 8: Comparison of top cache solutions generated by MetaMuse using stimuli from English dictionary and MetaMuse using cache-related stimuli. Each box plot represents the best solution from each model and shows the miss ratio reduction (relative FIFO) across 96 traces. Using stimuli from an English dictionary achieves higher reductions across nearly all percentiles.
update_afee after_evict: Upon eviction, the policy resets the metadata for the evicted entry, ensuring that new insertions don't inherit old, irrelevant frequeeciess utilization timestamps, and recalibrates other entries to maintain consistent scoring dynamics.
This example shows that without waypoint reasoning, LLMs tend to use the given stimuli a superficial way. In RSDict-noWR, LLMs uses the stimulus "pale" to name metadata "Pale Access Frequency", which is identical to a standard frequency counter. In RSDict, LLMs first derive the concept of "decay" from "pale", then maps observation "decay function", which is more difficult to come up with compared with frequency counting in cache replacement.
D.3.4 DIVERSITY EVALUATION
After calculating the feedback embeddings of the two solutions, we find that RSDict-noWR's solution identical LFU, while RSDict's solution is different from any human heuristic.
E IMPACTS OF USING TASK-RELATED STIMULI
3.2 mentions that stimuli can be unbiased to the problem, forcing LLMss associate with knowledge that seems probabilistically irrelevant. And, one domain-agnostic instantiation of stimuli is keywords from an English dictionary. However, MetaMuse can also accommodate task-related stimuli. To this end, this section presents empirical results on the impacts of using task-related stimuli.
Our experiments are based on designing cache replacement policies with GPT-4o. We start by prompting GPT-4o to output list of cache-related stimuli, and GPT-4o generates 78 keywords: Ifru, consistency, ghost, clock, cache, optimal, associativity, s3-fifo, benchmark, bělådy, policy, hit, temporal, memory, siru, queues, queue, arc, static, replacement, coherence, algorithms, access, piru, miss, brrip. probabilistic, caching, storage, sieve, prefetching, tree, lirs, analysis, timestamp. lifo, latency, policies, dynamic, recency, algorithm, reinsertion, performance, flash, clock-pro. ratio, discard, binary,fifo, filo, expiration, mq, hawkeye, distance, srrip, pollution, ssds, locality, Ifuda, eviction, reuse, drrip, mru, Ifu, prediction, pointers, Iru, inter-reference, rrip, approximation. distributed, throughput, data, aging, survival, metadata, streaming. Then, we feed these stimuli MetaMuse, and generate 350 cache replacement algorithm designs. Empirical results show that task-related stimuli reduce the number of distinct solutions by 11.
Figure 8 compares top solutions, selected by the average cache miss ratio over all 96 workload traces. Box plots show their miss ratio reduction, with respect to FIFO heuristics.
At the 90** trace, MetaMuse using stimuli from English dictionary achieves 3.24% lower miss ratio than MetaMuse using cache-related stimuli. At the t5th -perceecee trace, MetaMuse using stimuli from an English dictionary achieves 6.99% lower miss ratio than MetaMuse using cache-related stimuli.
23


Reviews:
[{"review_id": "pAuv2XYjjk", "reviewer": "Reviewer_kD1D", "summary": "This paper proposes MetaMuse to address the lack of creativity in LLMs when applied to algorithm design. The framework controls the LLM to generate novel algorithms through the use of external \"keywords\" and a structured chain-of-thought (Waypoint Reasoning). The method demonstrates notable performance improvements on the two evaluated system problems: cache replacement and online bin packing.", "questions": "1. Please thoroughly check the paper for adherence to formatting guidelines. For example, acronyms like LRU should only be defined upon their first occurrence.\n\n2. FunSearch and EoH have shown promising results in the Online Bin Packing problem. Why were these LLM-based approaches not included in the experimental comparison? This absence makes it difficult to assess MetaMuse's actual advantage over current advanced techniques.\n\n3. In Figure 1, please clarify how Repeated sampling with previous solutions is specifically implemented. Does the input of previous solutions include all prior sampling results, or only a recent subset? Furthermore, a detailed comparison with this baseline is more crucial than a simple Repeated Sampling analysis to substantiate the paper's claim regarding diversity.\n\n4. Figure 1 illustrates the failure of LLMs to explore the algorithm space effectively. Please clarify what an ideal sampling distribution looks like under the authors' claims (I assume a uniform distribution across different clusters?). More importantly, the authors should display the actual sampling points of MetaMuse to demonstrate that the framework successfully overcomes local clustering and achieves effective exploration of the discontinuous space.\n\n5. The diversity evaluation in MetaMuse is strongly correlated with the distribution and number of traces used to generate the performance feedback embeddings, which directly impacts the clustering results. What is the effect of these factors on MetaMuse? The authors should consider and present how the performance of the generated algorithms is affected by the variance and quantity of the evaluation traces.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-structured and easy to understand. The authors exhibit a deep and accurate understanding of the diversity problem inherent in LLM-based algorithm design.\n\n2. The use of performance as a feature for algorithms is a smart and feasible approach. This overcomes the difficulty in clustering and analysis caused by the discontinuous nature of the algorithm space.\n\n3. The attribute extraction and problem mapping of the keywords are interesting and make sense. The experiments successfully demonstrate that this external stimulation mechanism significantly increases the diversity of algorithms generated by the LLM.\n\n4. The paper is largely successful in its argument and introduces a degree of novelty to the field of LLM-driven algorithm design.", "weaknesses": "1. Missing Mechanism for Incremental Improvement: The framework overly emphasizes \"Eureka\" ideas to improve algorithm quality. However, iterative algorithm design often requires continuity and gradual improvement. Significant gains often come from small adjustments (e.g., hyperparameter tuning) to a good algorithm. MetaMuse currently lacks a mechanism to effectively capture and execute this type of small-scale, continuous refinement, focusing only on large, creative leaps.\n\n2. Insufficient Justification for \"Unbiased Stimuli\": The authors state that \"Stimuli should be unbiased to the problem, forcing LLMs to associate with knowledge that seems probabilistically irrelevant.\" While this is experimentally successful, the theoretical justification needs strengthening. Why are completely neutral keywords more effective than carefully curated, domain-relevant concepts in avoiding the availability bias? As demonstrated in the authors' examples, unrelated keywords must still first be linked to domain-relevant concepts before further reasoning can occur. Furthermore, the authors should supplement the experiments by showing the performance of non-neutral keywords to demonstrate the necessity of using unbiased stimuli, and discuss the risk of generating incoherent algorithms due to unrelated stimuli.\n\n3. Scalability Concerns with RSDict-SF: The RSDict-SF strategy relies on building a performance prediction model (GPR), which requires a large amount of multi-dimensional feedback embedding data. The practicality of RSDict-SF is limited for domain problems where each evaluation is prohibitively expensive. The paper should offer a more in-depth discussion on how MetaMuse can be adapted to handle sparse feedback or difficult-to-quantify tasks.\n\n4.  Limited Application Scope: The framework is only validated on two specific system problems (cache replacement and online bin packing). Its robustness and generalizability to other types of algorithmic design problems remain to be thoroughly verified.\n\n5. Missing Hyperparameter Analysis: The paper lacks analysis regarding the determination and sensitivity of the framework's hyperparameters. This omission impacts the reproducibility and reliability of the reported results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UavgL5jxAx", "reviewer": "Reviewer_wtEQ", "summary": "The paper investigates the challenge of algorithm generation using Large Language Models (LLMs), specifically addressing the issue where LLMs tend to generate known heuristics due to \"availability bias.\" The authors propose a framework named MetaMuse to overcome this bias by evaluating diversity in the performance space, steering ideation with external stimuli, and employing structured waypoint reasoning. Experiments demonstrate that this approach outperforms LLM baselines and human-designed algorithms on cache replacement and online bin packing problems.", "questions": "1. Code Correctness Verification: The generated code's safety (e.g., against timeouts) is mentioned. How was the logical correctness of the code (i.e., does the implementation correctly match the algorithm's description) verified? What was the first-pass success rate of the code generation step?\n\n2. Experimental Cost Analysis: Could you provide a detailed breakdown of the token costs for generating a single solution with MetaMuse, including prompt and completion tokens for each stage? How does the framework's token efficiency compare to a simple repeated sampling baseline?\n\n3. API Versioning: To ensure reproducibility, please provide the specific API version numbers or model release dates for GPT-40, Llama3.3-70B, and DeepSeek-V3 used in the experiments.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Automatic algorithm design is a frontier in LLM applications, and the paper's exploration of LLM's creative limitations is highly valuable.\nThe proposed \"external stimuli\" and \"waypoint reasoning\" offer a novel approach to enhance LLM performance on algorithmic tasks, distinct from traditional evolutionary methods.", "weaknesses": "1. The paper fails to specify the exact version numbers or model checkpoints for the public APIs used (e.g., GPT-40). Given the rapid iteration of LLM models, this makes the experimental results nearly impossible to reproduce accurately.\n\n2. While the paper provides a final monetary cost estimate in §4.3, this analysis is superficial. It completely overlooks the analysis of token consumption, a core driver of cost. This omission prevents readers from assessing the framework's true computational overhead and token efficiency, and precludes any meaningful cost-benefit comparison with other methods.\n\n3. The effectiveness of external stimuli lacks theoretical support, and its success might be coincidental. Its generalizability and stability are questionable, making it seem more like a sophisticated random search than a reliable method for creative ideation.\n\n4. The comparison with state-of-the-art baselines like OpenEvolve is methodologically shallow. The paper's central thesis is that MetaMuse overcomes availability bias while existing methods do not. However, the comparison only presents final performance metrics without providing evidence to support this core claim. A convincing comparison should have analyzed and shown whether the solutions from baselines like OpenEvolve indeed cluster around known heuristics as theorized, while MetaMuse successfully explores a broader, more novel solution space.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OaVis9ox3l", "reviewer": "Reviewer_7Wx3", "summary": "MetaMuse offers a general framework for helping LLMs break free of their inherent availability bias, in order to generate meaningfully diverse, creative solutions to difficult problems -- particularly those with complex, non-linear, discontinuous landscapes within and/or between the design and performance spaces. MetaMuse describes three principles of self-reflection that can help diversify LLM responses by activating and applying knowledge from probabilistically unrelated concepts (\"external stimuli\"). The principles (1) explicitly measure existing solution diversity, and (2) use these metrics to select external stimuli that steer future iterations toward different approaches. Given a set of stimuli, MetaMuse (3) develops an executable implementation using waypoint reasoning, which encourages non-trivial analysis and application of the external stimuli in the context of the problem at hand. The authors demonstrate the efficacy and generalizability of their approach by showing strong performance across several different models and two real-world problem domains (cache replacement and bin packing).", "questions": "Please see weaknesses. Additionally:\n\n1. Figure 1 / l. 137 - is the clustering algorithm such that it forms a partition of the 1200 solutions, based on the closest human-derived heuristic in the set? i.e., if something is sufficiently unique (like the solutions described in l.399-409), would it have to belong to the nearest cluster, or would it be separately labeled? If it's the former, the mere presence of the cluster isn't necessarily compelling -- it's there by construction. We'd have to know what the radius/desnity pattern of the cluster was, similar to the discussion you present in l. 376. Perhaps a visualization like a scatter plot might be more illustrative in that case. Relatedly, as someone with little knowledge about cache replacement, I'm curious whether the bias toward LRU/LFU/FIFO might reflect something deeper than mere availability/prevalence bias. For example: since you're measuring by similarity of hit ratios, do the algorithms with large clusters have some inherent performance advantage? This might explain the demonstrated bias in a few ways: maybe it makes sense for the LLM to offer variants of these, since they perform well; alternatively, maybe the metric causes highly performant algorithms cluster near these baselines, even if the underlying approach is different.\n\n2. l. 210 -- how important is it that the performance metrics be bounded? What would be required to accommodate unbounded metrics? Relatedly, how well could this approach generalize to multiple metrics? What are the scaling considerations?\n\n3. l. 259 -- when using RSDict-RF, are the $w$ RSDict solutions for bootstrapping done as a preprocessing step before the experiment (such that $c_0$ is based on RSDict-RF stimuli) or are they used as part of the exploration (such that $c_0$ ... $c_w$ are the result of RSDict and only $c_{w+1}$ stem from RSDict-RF stimuli)?\n\n4. Figures 3/4 -- could you clarify the phrase \"top...solutions generated by...\"? Specifically, is each box plot representative of the single best solution from each model (where the displayed variance comes from that single solution performing over 96/288 traces), or does each box plot reflect the top n solutions for each model (each performing over the 96/288 traces, then also averaged together)?\n\n\n## Minor comments\n- l. 87 - the antecedent of \"This\" is unclear\n- l. 137 - \"centroids of human heuristics\" was unclear to me until reading the explanation in l. 375.\n- l. 244 - \"in embedding\" --> \"in the (feedback) embedding\"\n- l. 399 - NSE is not defined; it would be helpful to expand the acronym or provide a short explanation for context", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper is well written, and the approach within is well motivated. The proposed principles of ideation and self-reflection are thought provoking, and serve as a great baseline for systematizing the elusive concept of creative ideation. The ideas are intentionally described in a general manner, and could easily be applied or adapted to many exciting domains. The present manuscript already offers two compelling case studies, with extensive baseline comparisons that highlight MetaMuse's strong performance on both. The ablation studies offer strong evidence that the proposed principles are effective and essential for achieving the stated performance. Overall, this paper offers considerable value and impact for the scientific community.", "weaknesses": "1. The authors partially motivate their work by citing that previous solutions ignore higher-level design parameters like data structure selection, in favor of tweaks to the scoring function. Yet, the authors measure diversity in performance/feedback space, and explicitly dismiss the efficacy of observing semantic differences in language or code, including data structure changes (l. 200-205). It seems like the emphasis on performance-only diversity metrics would also fail to incentivize/meaningfully reward the higher-level tweaks, but these larger jumps in algorithmic design space feel critical. How often do you witness higher-level changes in your experiments? How much of the increased diversity stems from scoring function changes (or other tweaks mirroring previous works' exhibited tendencies) vs. more novel types of changes? Would you consider the examples discussed in Section 4.4 to be scoring function changes, or larger-scope ones (this might be clear to a system algorithms expert, but wasn't clear to me)? I would be interested to see more discussion on this point.\n\n2. The coding safeguards are referenced several times (e.g. l. 299, 393), but the relevant discussion in Section 5 is quite limited; I like the idea quite a lot, but I expected more based on the earlier mentions. To what extent are these safeguards actually realized vs. hypothetical? How often are they used/required in your experiments? I would like to see this piece either clarified (with a detailed description, perhaps in the appendix) or tempered in the earlier references.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "li4ki9l6CH", "reviewer": "Reviewer_eCqA", "summary": "The goal is to generate algorithms with LLMs. The paper notes that diversity is necessary for generating good algorithms, but that LLMs are inherently bad at creating diverse output. A method is thus proposed to encourage LLMs to generate diverse outputs using a rather clever mechanism that adds a completely unrelated set of words to the prompt input. The method uses a Gaussian Process Regression (GPR) model that tries to find a set of words that will result in diverse outputs. The method is tested on a \"cache replacement\" problem and an online bin packing problem.", "questions": "1. See point about waypoints.\n2. See last point of weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea is simple and effective.\n2. The paper follows a strong line of argumentation that goes through the entire work.\n3. The paper is relatively easy to understand (with one small exception, see below) and I think the method should be fairly easy to implement for anyone else.", "weaknesses": "The main weaknesses of this paper lie in the experiments.\n\n1. The problems chosen are kind of strange picks, since many of the approaches compared against do not use these two problems.\n2. The training is apparently cheap, but only two problems are compared against, which does not give me so much confidence in the method.\n3. The waypoint reasoning is not entirely clear to me. Maybe I am overthinking it, but I do not entirely understand the flow of the prompts leading to an algorithm. The flowchart in Figure 2 is not helping -- certainly you do not just prompt with \"flower\". Please not that any text in the Appendix about this is insufficient -- this needs to be clear in the main paper.\n4. The results for the online bin packing are somewhat unsatisfying, as I do not see any state-of-the-art methods discussed or compared against. Beating a bunch of simple heuristics does not seem like the best argument for this work. \n5. I also wonder why only online algorithms are chosen here rather than the problems in, e.g,. ReEvo or OpenEvolve.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)