Many advances in ML systems came from breaking an assumption that earlier methods took for granted: speculative decoding dropped the assumption that a model needs one forward pass per token. Yet algorithms rarely state their assumptions, so experts and discovery harnesses search over programs, where one edit changes several design choices and gains are difficult to attribute. Searching over the assumptions themselves remains largely unexplored. Writing algorithms as proofs makes their assumptions explicit and turns algorithm design into a search over a small, structured space that an LLM can explore and a proof checker can audit. We formalize 89 algorithms from KV-cache eviction, weight pruning and speculative decoding as proof graphs with explicit assumptions, checked in Lean. Our harness, AutoAssumption, relaxes one assumption of a published method, re-derives and re-proves it, and generates its code. In KV-cache eviction and weight pruning, this search improved on every published algorithm we ran and produced state-of-the-art algorithms. The eviction algorithm has the highest RULER-4K score of the published methods we ran, and the pruning algorithm the lowest perplexity of thirteen on four LLaMA models. At equal budget, the harness scores within a point of OpenEvolve, an open-source implementation of AlphaEvolve, with a lower standard deviation across repeats. Future work will formalize more fields and combine them through the principal assumptions they share.
Figures & tables
Figure 1: AutoAssumption turns published algorithms into Lean-checked proofs and discovers new ones by changing one assumption at a time. (a) An agent writes each published algorithm as a proof graph of assumptions, definitions and theorems, checked in Lean. (b) The assumptions of all proofs form one pool. (c) A variant changes one assumption of its parent and re-proves only the statements that depend on it; Lean rejects a proof that fails (dashed red). (d) Variants that pass are benchmarked, here on RULER-4K and WikiText-2 perplexity, and the scores guide the next change.
Figure 2: Records in KV-cache eviction coincide with new assumptions. Top: mean RULER-4K score of published algorithms by release date (KVPress, Llama-3.1-8B-Instruct and Qwen3-8B, 2× – 64× compression, subsampled questions). The step line is the best score so far, bold labels name records, and squares mark query-aware algorithms. Bottom: one row per assumption shared by at least two algorithms; a dot marks an algorithm that makes it, and a ring the first algorithm to do so. The Foundational row holds the assumptions of H2O.
Figure 3: The exactness proof of speculative sampling ( Leviathan et al., 2023 ) can be represented as a proof graph. The graph contains every node of Appendix H . Its columns hold the assumptions A , the definitions D and the theorems T ; open discs are lemmas L . Each call-out paraphrases the highlighted node of the same colour, and the badge marks that the proof compiles in Lean.
Figure 4: Algorithms from three fields of ML systems can be written as proof graphs that answer the problem P shared within each field. Each card is one algorithm’s graph, drawn as in Figure 3 ; a line takes the colour of the node at its left end, and P is the problem of the card’s field. The quarter after each name is the algorithm’s first public release. Rows, left to right: StreamingLLM ( Xiao et al., 2024 ) , KVzip ( Kim et al., 2025 ) , RestoreKV ( Baek et al., 2026 ) ; SparseGPT ( Frantar & Alistarh, 2023 ) , Wanda ( Sun et al., 2024 ) , Z-Pruner ( Bhuiyan et al., 2025 ) ; SpS ( Leviathan et al., 2023 ) , SVIP ( Zhang et al., 2025 ) , MARS ( Song et al., 2026 ) . Appendix F lists every algorithm we analyze.
Figure 5: A search chain in KV-cache eviction: each accepted variant changes one assumption of the current best and becomes the next parent. The best of the three repeats of Figure 8 , starting from RestoreKV, on a fixed draw of 200 RULER-4K questions. Above: the proof graphs of variants 1, 4 and 9. The line is the best variant score so far (RestoreKV itself, 72.9, is not plotted); filled triangles mark variants that set a new best and became the next parent, hollow ones variants that did not. Error bars ( ±1 SD over question bootstraps, about 0.5 ; Appendix G.1 ) barely extend beyond the markers.
KV-cache eviction
LLM weight pruning
Speculative decoding
Benchmark
KVPress RULER-4K (13 tasks, 6,500 questions)
WikiText-2 test perplexity, SparseGPT and Wanda protocol (128 C4 calibration windows)
Spec-Bench (480 questions, 1,024 new tokens)
Model
Llama-3.1-8B-Instruct ( Grattafiori et al., 2024 ) and Qwen3-8B ( Yang et al., 2025 )
LLaMA-7B ( Touvron et al., 2023a )
Vicuna-7B-v1.3 ( Chiang et al., 2023 ) target with the vicuna-68m drafter
Main metric
RULER-4K score (mean task accuracy), averaged over compression ratios 2× – 64× and over the two models
WikiText-2 perplexity divided by the dense model’s, at 50 % unstructured sparsity
speedup over autoregressive decoding at batch size 1, at sampling temperatures T=0 to 1
Error bars
±1 SD over 10,000 paired bootstrap resamples of the questions
±1 paired bootstrap SE over the 166 WikiText-2 windows
±1 SD over three paired timing runs
Table 1: We evaluate our designs on established benchmarks in each field. The benchmark, model, metric and error bars behind Figure 7 ; Section 3 gives the other settings, Appendices A and G the versions, hardware and error bars in full.
Figure 6: For every parent algorithm, AutoAssumption generates a variant that scores higher than the parent on its field’s search benchmark. Across three fields, we selected 26 published algorithms as parents, and for each of them our harness found a better variant. Shown: the seven parents with the largest gain per field; Appendix Table 13 gives the results for the others. Triangles: gains beyond the axis; light bars: gains under 1 %.
Figure 7: Our three variants rank at or near the top of their fields, hold up across each field’s sweep and remain practical to run. AutoAssumption pushes the state of the art in KV-cache eviction and LLM weight pruning and creates a competitive speculative decoding algorithm (A, D, G). The three variants match or outperform the published algorithms shown at every point of the sweep each field reports, except at 64× KV-cache compression on Llama, where KVGrad leads by 0.8 points (B, E, H). Our variants take about as much time as their parents in all three fields (C, F, I). Error bars as in Table 1 ; in D, a paired bootstrap SE over the WikiText-2 windows.
Algorithm
Changed assumption
Code
RestoreKV GM
a cached pair is kept when the query heads that share its KV head attend to it on average, not when any single head does
Alg. 1
Pruner-Zero LG
weight scores are compared within a whole matrix instead of within each output row
Alg. 2
SVIP LK
when the entropy test ends a draft, tokens copied from an earlier occurrence in the prompt are appended instead
Alg. 3
Table 2: We propose three new algorithms, each one assumption away from a published parent. Names in the colour of their field; pseudocode in Appendix C .
RULER
LongBench
Llama-3.1-8B
Qwen3-8B
Llama-3.1-8B
KV-cache eviction
4K
8K
16K
4K
2.6K–30K
RestoreKV
73.9
74.8
73.3
72.1
37.8
RestoreKV GM (ours)
77.0
77.9
76.5
74.5
39.2
Δ
+3.1 ± 0.16
+3.1 ± 0.17
+3.3 ± 0.17
+2.4 ± 0.17
+1.5 ± 0.29
LLaMA
LLaMA-2
Table 3: The two best discovered variants hold beyond the search setting. Top: RestoreKV GM (ours) against its parent, score averaged over 2× – 64× ; the search used 200 RULER-4K questions, and 8K and 16K contexts and LongBench are settings it never saw. Δ : variant minus parent, computed from unrounded means, ±1 SD from bootstrapping the questions. Bottom: WikiText-2 perplexity at 50 % sparsity divided by the dense model’s, lower is better; the search used only LLaMA-7B. The ranking holds across all thirteen pruning algorithms we ran; the table shows a selection, and Appendix Table 9 gives every algorithm.
Figure 8: AutoAssumption finishes level with the code-level LLM harnesses and improves more steadily, with a smaller spread across repeats. OpenEvolve and AIDE jump early and then gain little; AutoAssumption, changing one assumption per step, rises at almost every step and ends at 79.3, against 79.7 and 78.5. All three start from RestoreKV; Fable from scratch has no parent. Scores average 200 RULER-4K questions, Llama-3.1-8B-Instruct and Qwen3-8B, and 2× – 64× compression. Lines: mean of three repeats; error bars: minimum to maximum.
Table 4: GPU, NVIDIA driver, CPU, Python, PyTorch, libraries and precision of the machine behind each field’s experiments (KV-cache eviction, weight pruning, speculative decoding). One GPU per job. Driver column: highest CUDA version the driver supports; brackets: CUDA runtime PyTorch was built against.
Figure 9: Our runs reproduce the published leaderboards. Each point is one published algorithm, in (a) at one model and compression ratio ( 2× – 32× ). (a) Horizontal bars: ±1 bootstrap standard deviation of our score over questions (the leaderboard publishes no per-question data); inset: the boxed region, enlarged. (b) Vicuna-7B-v1.3 target, greedy decoding ( T=0 ); each published value is a mean of three runs.
Figure 10: Stage 1 selects a field’s reproducible algorithms and finds one problem that all of them can be proved to solve. Black discs number the steps, and boxes with a blue border are outputs. Red marks the algorithms dropped at a step and the request for a new formulation when the Lean file of a sampled algorithm does not build.
Figure 11: Formalizing a published algorithm with two agents. Top: the files each agent reads and writes for one algorithm, and the pool merged over all algorithms. Bottom: each agent box expanded into the workflow of its prompt (Appendices D.1 and D.2 ), with steps numbered as in the prompt. Grey: files a step starts from; blue: files it writes; red: checks, with arrows to the step a failure returns to.
Figure 12: Making one variant. Top: the files the agent with Prompt 3 (Appendix D.3 ) reads and writes. Bottom: the agent box opened into the workflow of Prompt 3, numbered as in the prompt. Grey: files a step starts from; blue: files it writes and the scores returning to the agent; red: checks and the step a failure returns to, as in Figure A.2.2 .
Figure 13: KVGrad EA (ours) lies above every prior design at 16× – 64× compression, where it gains 6.9 points on average over its parent KVGrad (3.7 points over 2× – 64× ). RULER-4K, mean of Llama-3.1-8B-Instruct and Qwen3-8B. The 33 query-agnostic prior designs (grey unless the legend names them) are each drawn at the largest number of questions both models finished (300 or 6,500); KVGrad EA (ours) and KVGrad use 6,500. Table 5 lists the named prior algorithms per model.
Llama-3.1-8B-Instruct
Qwen3-8B
Mean
Questions
2×
4×
8×
16×
32×
64×
2×
4×
8×
16×
32×
64×
H2O
300
54.6 ± 2.1
35.6 ± 1.6
25.5 ± 1.4
14.7 ± 1.3
10.4 ± 1.4
4.2 ± 1.0
52.7 ± 2.0
31.0 ± 1.7
23.5 ± 1.4
17.5 ± 1.3
12.2 ± 1.2
7.7 ± 1.1
24.13 ± 0.43
SnapKV
300
70.0 ± 1.9
42.3 ± 2.0
25.7 ± 1.8
15.9 ± 1.6
8.9 ± 1.3
0.0 ± 0.0
53.7 ± 2.0
32.9 ± 1.9
21.7 ± 1.6
15.4 ± 1.5
8.3 ± 1.2
1.4 ± 0.7
24.68 ± 0.45
StreamingLLM
300
63.4 ± 2.4
39.4 ± 2.2
28.0 ± 1.9
16.4 ± 1.6
8.4 ± 1.4
5.5 ± 1.2
64.8 ± 2.4
41.6 ± 2.2
27.8 ± 2.0
14.1 ± 1.6
6.4 ± 1.3
5.2 ± 1.1
26.75 ± 0.52
KeyDiff
300
86.7 ± 1.4
73.5 ± 1.4
62.8 ± 1.1
52.4 ± 1.2
33.3 ± 1.4
17.8 ± 1.5
77.3 ± 1.6
63.1 ± 1.4
46.4 ± 1.8
24.3 ± 1.5
14.7 ± 1.1
8.7 ± 0.4
46.75 ± 0.40
KVzip
6,500
95.5 ± 0.2
95.3 ± 0.2
92.8 ± 0.2
74.6 ± 0.4
29.1 ± 0.4
17.7 ± 0.2
95.2 ± 0.2
95.1 ± 0.2
92.1 ± 0.3
58.8 ± 0.5
19.8 ± 0.2
18.6 ± 0.2
65.38 ± 0.08
Appendix
Table 5: RULER-4K scores of the published algorithms named in Figure 13 and of RestoreKV GM (ours), per model and compression ratio. Each algorithm at the largest number of questions both models finished (Questions; 300 is nested in the 6,500); Mean covers the 12 cells. ± : one bootstrap SD over the question draw. Bold: best in the column; underlined: second best, at the printed precision.
KV cache eviction
Llama-3.1-8B-Instruct
Qwen3-8B
Mean
2×
4×
8×
16×
32×
64×
2×
4×
8×
16×
32×
64×
KVzip
95.5
95.3
92.8
74.6
29.1
17.7
95.2
95.1
92.1
58.8
19.8
18.6
65.38
KVzip+
95.5
95.2
93.3
74.0
35.6
18.2
95.3
95.2
93.9
76.4
31.5
19.8
68.66
RestoreKV
95.6
95.3
94.5
85.9
52.8
19.4
95.1
95.3
94.2
81.8
43.5
22.7
73.01
RestoreKV GM (ours)
95.5 -0.1
95.4 +0.1
94.4 -0.1
86.6 +0.7
64.8 +12.0
25.2 +5.8
95.2 +0.1
95.3 0.0
94.1 -0.1
84.7 +2.9
54.0 +10.5
23.7 +1.0
75.74 +2.73
Appendix
Table 6: Full RULER-4K scores (6,500 questions) of KVzip, KVzip+, RestoreKV and RestoreKV GM (ours), per model and compression ratio. Small figures: RestoreKV GM minus RestoreKV, green where a two-sided z -test gives p<0.05 , grey otherwise (Appendix G ). Table 5 gives the error bars.
Setting
Questions
Design
2×
4×
8×
16×
32×
64×
Mean
RULER 4K Llama
6,500
RestoreKV
95.6 ± 0.2
95.3 ± 0.2
94.5 ± 0.2
85.9 ± 0.3
52.8 ± 0.5
19.4 ± 0.2
73.9 ± 0.11
RestoreKV GM (ours)
95.5 ± 0.2
95.4 ± 0.2
94.4 ± 0.2
86.6 ± 0.2
64.8 ± 0.4
25.2 ± 0.3
77.0 ± 0.12
RULER 8K Llama
6,500
RestoreKV
94.6 ± 0.2
93.9 ± 0.2
92.9 ± 0.2
84.1 ± 0.3
61.1 ± 0.4
22.4 ± 0.3
74.8 ± 0.12
RestoreKV GM (ours)
94.5 ± 0.2
93.9 ± 0.2
92.8 ± 0.2
84.6 ± 0.3
68.1 ± 0.4
33.5 ± 0.4
77.9 ± 0.12
RULER 16K Llama
6,500
RestoreKV
93.2 ± 0.2
92.9 ± 0.2
90.0 ± 0.3
82.1 ± 0.3
59.2 ± 0.4
22.1 ± 0.3
73.3 ± 0.12
RestoreKV GM (ours)
93.2 ± 0.2
92.9 ± 0.2
89.7 ± 0.3
83.5 ± 0.3
66.4 ± 0.4
33.5 ± 0.4
76.5 ± 0.13
Appendix
Table 7: Scores of RestoreKV and RestoreKV GM (ours) at 8K and 16K contexts, on Qwen3-8B and on LongBench, per compression ratio. Mean is the value in the top of Table 3 . ± : one bootstrap SD over the question draw. Bold: the higher of the two.
Context
4K
8K
16K
32K
64K
KV-cache size reduction (GB)
0.46
0.97
1.95
3.99
8.03
No eviction (no compression)
0.23 ± 0.11
0.40 ± 0.13
0.75 ± 0.04
3.48 ± 2.06
5.94 ± 0.90
KVGrad
3.93 ± 1.29
11.7 ± 4.36
35.1 ± 3.15
175.4 ± 0.89
814.3 ± 1.97
RestoreKV
1.81 ± 0.69
3.51 ± 1.62
5.16 ± 2.04
12.2 ± 1.27
33.0 ± 0.38
KVzip
1.87 ± 0.79
3.36 ± 1.20
5.13 ± 1.36
11.4 ± 1.10
32.7 ± 0.31
KVzip+
2.54 ± 1.33
3.73 ± 1.27
6.49 ± 1.88
13.3 ± 0.74
36.6 ± 0.51
Appendix
Table 8: Time to first token of no eviction, KVGrad, RestoreKV, KVzip, KVzip+ and RestoreKV GM (ours) at 4K to 64K tokens. Seconds, mean ± SD over seven timing passes of two fixed RULER prompts, Llama-3.1-8B-Instruct on one H100, no eviction at full cache and every other method at 16× compression; the first row is the KV-cache size reduction of the compressing methods. Ours in bold.
Designs evaluated
1
2
3
4
5
6
7
8
9
10
Fable, from scratch
49.3
54.1
62.5
63.1
64.7
66.4
68.2
69.4
71.4
71.4
44.0–58.8
44.0–59.2
58.6–65.8
59.0–67.2
60.3–67.2
63.4–68.1
67.6–68.8
67.6–71.9
68.8–73.0
68.8–73.0
AIDE
72.8
75.4
76.3
76.6
76.9
77.1
78.2
78.2
78.2
78.5
70.4–77.7
70.4–78.2
72.7–78.2
73.0–78.8
73.2–79.2
73.2–79.9
73.6–80.8
73.6–80.8
73.6–80.8
73.8–80.9
OpenEvolve
70.7
76.1
76.6
76.6
77.3
78.7
78.8
79.5
79.7
79.7
Appendix
Table 12: Running best RULER-4k score after 1 to 10 algorithms of Fable from scratch, AIDE, OpenEvolve and our harness (the numbers of Figure 8 ). Score: the mean of the 12 cells, Llama-3.1-8B-Instruct and Qwen3-8B at 2× – 64× (200 questions); each cell is the mean over three repeats per search, with the minimum and maximum across the repeats beneath it in small grey print. OpenEvolve, AIDE and ours start from RestoreKV, whose own score is excluded. Per column, bold: the highest mean; underlined: the second highest, ranked before rounding. ⋆ : found by our harness.
Parent
Best variant
Variants
Better
Gain
Gain (%)
KV-cache eviction (gain in RULER points)
PyramidKV
PyramidKV lastquery
6
4
+12.43
+54.8
KNorm
KNorm value norm
6
5
+8.41
+44.0
TOVA
TOVA pooling
6
2
+5.16
+15.5
SnapKV
SnapKV head mean
6
6
+2.99
+12.3
KVzip+
KVzip+ residual norm
40
22
+4.45
+6.5
Appendix
Table 13: The best variant of each of the 26 parent algorithms on its field’s search benchmark. Variants: how many the harness derived from the parent; Better: how many score above it. Gain: best variant minus parent, in RULER-4K points (200 questions, mean of both models and six compression ratios), WikiText-2 perplexity of LLaMA-7B at 50 % sparsity (sign flipped, so positive is better) and speedup over autoregressive decoding (Vicuna-7B, mean of five temperatures); Gain (%): relative to the parent.
Figure 3: The proof graph of this appendix, repeated from Figure 3 . Lines are drawn after transitive reduction, so indirect citations are omitted; the arrows into P come from the claims that answer the problem. Enlarged discs mark Assumption A 5 , which SVIP relaxes, and the exactness and token-count claims; the dark curve along the bottom is the only citation of Assumption A 5 , by Theorem T 2 .
Figure 14: Lean flags every mutant; the benchmark flags about half. An evaluation is one design at one setting, Llama-3.1-8B-Instruct or Qwen3-8B at 16× or 64× compression, so each design counts four times. Lean gives one verdict per design, shared by its four settings; the benchmark flags any score below the parent’s, the rule most favourable to it. Blue cells are correct decisions and red cells wrong ones, shaded by their share of the row.
LLMs now prove hard theorems in Lean. Can they also design algorithms and prove their correctness and efficiency? LLM-guided design of optimisation heuristics (such as AlphaEvolve) is purely empirical. Automated theorem provers with LLMs prove given statements. So far, there has been little evidence that LLMs can do both: design an algorithm and guarantee its efficiency by a mathematical proof. We present a staged pipeline modelled after research methodology in design and analysis of evolutionary algorithms. The agent proposes black-box optimisation algorithms, and Lean guards filter out flawed designs. The agent then defines a potential function and proves drift bounds that guarantee an expected runtime improvement over the baseline algorithm. At no point in the pipeline are the algorithms compared empirically. The agent generates a black-box optimisation algorithm with expected runtime O(n2) on a CycleUncover problem, where the classical (1+1) EA needs runtime eΩ(n). The pipeline also designs and analyses a black-box optimisation algorithm for integer-valued submodular minimisation with expected runtime O(n2+2c), and it matches the classical runtime O(n2) on LeadingOnes. Across 8 problem classes, 12 of 15 runs with frontier models complete the pipeline with a machine-checked expected-runtime bound. An ablation study shows that removing the staging and asking the agent to zero-shot an algorithmic design with a runtime guarantee leads to a copy of the seeded baseline algorithm (random search) or to incomplete proofs. Our study suggests that machine-checked specifications in Lean can replace empirical evaluation in open-ended algorithm discovery. To the best of our knowledge, this is the first example of an automated pipeline that designs efficient black-box optimisation algorithms with machine-checked runtime bounds in Lean.
Per Kristian Lehre
School of Computer Science, University of Birmingham, UK
AlphaEvolve and FunSearch have demonstrated the potential of combining large language models (LLMs) with evolutionary search for automated algorithm discovery. However, discovery success is shaped not only by model capability but also significantly by the design of the execution infrastructure, i.e., the harness. This paper investigates effective harness design through three questions: under a fixed token budget, is it better to produce many algorithms with brief thought or fewer algorithms with deeper thought? How should the harness handle evaluation hacks, where generated programs exploit the scoring function? And how can agents that require full filesystem access execute safely in parallel? Using Vesper, an algorithm discovery framework that incorporates harness improvements addressing these questions, we evaluate on Circle Packing under the same token budget. Interestingly, generating fewer algorithms while thinking more deeply about each one achieved higher scores. That is, scaling the quality of each individual is more budget-efficient than scaling the number of evolutionary generations. Surprisingly, more capable models produced evaluation hacks at higher rates, making hack detection increasingly necessary as models scale.
Large Language Model (LLM)-guided evolutionary search is increasingly used for automated algorithm discovery, yet most current methods track search progress primarily through executable programs and scalar fitness. Even when natural-language reasoning is used through heuristic descriptions or reflection, it typically remains transient mutation context or unstructured memory, rather than organized as persistent population-level state over strategic directions. As a result, evolutionary search can struggle to distinguish syntactically different implementations of the same idea, preserve lower-fitness but strategically promising directions, or detect when an entire family of strategies has saturated. We introduce \model, a modular strategy-space layer that turns language-level strategic reasoning into first-class population-level evolutionary state in LLM-driven program search. \model represents each candidate program with an explicit natural-language strategy, clusters the archive by strategy semantics, retrieves behaviorally complementary inspirations, and periodically navigates the strategy landscape to avoid saturated directions. Without modifying the underlying evolutionary algorithms, \model improves existing evolutionary backbones across algorithm discovery, systems optimization, and agent-scaffold design tasks in most settings. Across four systems benchmarks, \model achieves a 20.6% average relative improvement, with the best single run on Prism scoring 3× higher. These results suggest that persistent strategy representations provide a practical mechanism for improving the effectiveness and cost-efficiency of LLM-guided evolutionary search, pointing toward compound AI systems whose search capabilities benefit from the structured accumulation and reuse of algorithmic strategies.
Sichun Luo, Yi Huang, Haochen Luo +7
1The University of Hong Kong · 2JIUTIAN Research, China Mobile · 3City University of Hong Kong