How AI discovers better algorithms

Introduction

An algorithm is a recipe for computing an answer. Improving it can mean sharing calculations that were previously separate, choosing a better next action, or arranging the same work more effectively for a particular machine. Familiar ingredients can yield useful new arrangements.

This is how AI drawing on existing knowledge can help invent an algorithm: it proposes executable arrangements, experiments reveal their consequences, and those results influence what the system tries next. In AlphaEvolve, for example, language models modify programs; an evaluator runs and scores them; a database supplies earlier programs and their results to later prompts. Discovery happens across this developing experiment, rather than depending on a model producing the finished invention in its first answer. [1]

The resulting program can take two paths. It may itself be the improved routine, ready to make decisions or perform calculations. Or it may be a better search procedure that finds a separate object, such as a new multiplication scheme. In either case, people can inspect the result, extract a pattern, and use that understanding to redesign the next search. We will follow a changed packing decision, open up an arithmetic shortcut, and then see how an experimental pattern becomes mathematical knowledge. Together these explain both how new computational ideas emerge and what makes them useful.

A better rule changes a concrete decision

Imagine items arriving one at a time to be packed into bins. Each item must fit, and the aim is to use as few bins as possible. A familiar heuristic, best fit, places the next item into the bin that will have the least space remaining. It makes a sensible local choice without searching every possible future packing.

The released FunSearch bin-packing notebook makes that choice an editable function. Its fixed surrounding program first removes bins that cannot hold the item, asks priority to score the remaining bins, chooses the first maximum, and subtracts the item from that bin's available space. Here is the core of that caller, with packing-bookkeeping lines omitted: [2]

valid_bin_indices = get_valid_bin_indices(item, bins)
# Score each bin based on heuristic.
priorities = priority(item, bins[valid_bin_indices])
# Add item to bin with highest priority.
best_bin = valid_bin_indices[np.argmax(priorities)]
bins[best_bin] -= item

Here bins contains remaining capacities, not the items already packed. The initial best-fit function returns -(bins - item): because the caller chooses the largest score, the smallest nonnegative leftover wins. Changing priority can change the decision while leaving the feasibility check and capacity update intact. [2]

One rule labeled as discovered for the notebook's OR datasets gives very small gaps high scores, but then increases scores again for larger gaps. It uses fixed scores for successive gap ranges: a gap greater than 7 and at most 9 returns 0.9, while any gap greater than 21 returns 0.99. [2] Consider an item of size 20 and remaining capacities [28, 50, 150], where the last bin is unused. Applying the released formulas by hand gives this illustrative decision, not an executed benchmark trace: [2]

The displayed discovered-rule scores are the returned constants, not rounded values: both gaps of 30 and 130 take the same 0.99 branch. [2] Best fit chooses the first bin and leaves 8 units. The discovered rule chooses the second and leaves 30 because np.argmax selects the first occurrence of that shared maximum. This is an actual change in the computation. It does not establish that this particular decision will save a bin later, or that the function predicts future items. The notebook evaluates a rule by running complete item sequences and taking the negative mean number of bins used. That is where a sequence of unusual local choices must earn its value. [2]

The example also exposes an important distinction in invention. The fixed caller determines what counts as an allowed action; the evolved rule determines which allowed action to take. A small function can therefore express a consequential new policy without replacing the whole packing system.

Experiments become material for the next idea

How does a system arrive at such a rule? AlphaEvolve's June 2025 description begins with three human-supplied ingredients: a complete starting program, marked regions that may change, and an evaluation function returning numerical scores. The starting implementation can be rudimentary, but the surrounding program must already connect the editable pieces to the evaluator. [1]

For each proposal, the system assembles a prompt containing a program to modify and examples of earlier programs. Those examples can include outputs and evaluation scores, alongside problem descriptions, equations or other context. The language model returns code changes, usually as search-and-replace blocks. A controller applies them, and the evaluator assesses the resulting program. Promising evaluated programs return to the database, making their code and consequences available for subsequent prompts. The implementation runs many such operations asynchronously, so the process is a branching search rather than one uninterrupted chain. [1]

This handoff gives feedback a concrete role. A later proposal can start from a useful modification, see an earlier failure, or borrow structure from a different successful candidate. The next prompt contains information about this particular experiment that was unavailable before the candidate ran. The system can develop its programs and search history without requiring an update to the language model's weights; AlphaEvolve describes this as test-time computation and treats distilling its gains into future base models as a subsequent possibility. [1]

Keeping promising candidates of different kinds creates more possible starting points. AlphaEvolve's database is designed to retain this variety. A program that excels on one metric may contain a useful structure absent from the overall winner. Resurfacing it can give the model something different to modify. That is the design's rationale, rather than a guarantee that a larger or more diverse archive always helps. [1]

The search rules themselves remain experimental choices. AlphaEvolve's authors compare their full system with a “No evolution” condition that repeatedly supplies the same initial program, and report benefits on their tensor-decomposition and kissing-number tasks. [1] A later study comparing 30 search configurations across 12 model–problem pairs finds no fixed configuration reliably superior across its suite. It matches candidate-generation counts within each model–problem pair, not token or floating-point-operation costs. Its simple baseline already modifies the best program found so far, so it tests more elaborate ways of directing feedback-based search, not feedback against independent proposals. [3]

What carries across these accounts is the operational idea: generated code becomes an experiment, and the result changes the material available for another proposal. Which material to retain and how to explore it are further algorithm-design problems.

An arithmetic shortcut changes what gets computed

A heuristic changes a choice. An algebraic algorithm can change the calculations needed to produce exactly the same answer.

To see the principle on a small scale, consider multiplying two complex numbers:

The direct expression uses four real multiplications: ac, bd, ad and bc. Instead, compute

The real part is still $p-q$, and the imaginary part is $r-p-q$. Expanding the last expression cancels ac and bd, leaving ad+bc. Three multiplications now suffice, at the cost of three additional additions or subtractions relative to the direct formula. This is a teaching identity, not a reported AI discovery or timing experiment; it assumes exact arithmetic.

The shortcut comes from changing relationships among operations. A product of sums initially creates more terms than we need, but those extra terms can be removed using products we already computed. The same intermediate work contributes to more than one part of the answer.

The identity also shows how weights specify a recipe. From the inputs (a, b) and (c, d), weights (1, 0) pick out a and c for p, while (0, 1) pick out b and d for q. For r, weights (1, 1) form a+b and c+d. Each pair is multiplied once. At the output, p contributes +1 to the real part and −1 to the imaginary part; q contributes −1 to both; and r contributes 0 and +1.

Matrix multiplication admits a much larger version of this search. A candidate scheme first forms linear combinations of entries from each input matrix, multiplies selected pairs of combinations, then distributes and adds those shared products into the output entries. Three coefficient arrays specify the same three roles: weights for the first input's combinations, weights for the second input's combinations, and signed weights for distributing each product to the outputs. The entire arrangement must reproduce the required matrix-product identity: wanted terms survive and unwanted terms cancel. This can be encoded as a tensor decomposition, whose number of terms—its rank—counts those shared products, just as the teaching identity uses three. [4]

AlphaEvolve did not simply generate the final coefficient arrays in one response. It evolved a numerical search program that starts with proposed coefficients, measures how far their construction is from the required multiplication identity, and adjusts them to reduce that mismatch. Candidate search programs ran from multiple random seeds on chosen matrix-multiplication targets. Evaluation rewarded the lowest rank they found and how often they reached it; the authors describe rounding coefficients to integers or half-integers when checking exact constructions. The evolving changes included initialization, optimization, loss and exploration choices. [1]

The paper reports that this search found a rank-48 scheme for multiplying two 4-by-4 matrices using complex-valued scalar multiplications, compared with 49 for recursively applying Strassen's method. The scheme can compute complex or real matrix products, but the count is not 48 real scalar multiplications. The evolved search program is the instrument; its coefficient decomposition is the multiplication recipe it discovers. This result concerns that algebraic representation, not a proof that every possible way to multiply these matrices needs at least 48 products. [1]

Fewer products also leaves work for implementation. The input combinations, output combinations and temporary values cost additions, storage and data movement. FalconGEMM, a later matrix-multiplication implementation study, makes the tradeoff concrete: its execution strategy keeps shared products on chip while adding their contributions to the outputs, but still stores the combined inputs separately because keeping every stage together would demand too many on-chip resources. Its selection model chooses ordinary matrix multiplication where moving the data costs more than reducing the arithmetic saves. A shorter algebraic recipe creates an opportunity for speed; the hardware implementation must realize it. [5]

A successful program can start a second discovery

An experimental winner is something people can run. To turn it into an idea they can generalize, researchers may need to remove incidental details, identify a family of related objects, and explain why the pattern works.

Co-FunSearch provides a particularly clear example using bin packing again, but with a different objective. Instead of discovering a better packing heuristic, its generated programs produce difficult inputs for the familiar Best-Fit heuristic. The evaluator computes an optimum packing with a solver, runs Best Fit on 10,000 random shuffles of the generated items, and scores the ratio between the mean number of bins Best Fit uses and the optimum. [6] The program is now an instrument for discovering where an existing algorithm fails. [6]

One generated program contains repeated groups of small items mixed with leftover constants. Researchers simplify it into two groups: a copies of 1/a, followed by b copies of 1/b, for unit-capacity bins. Each group can fill a bin exactly on its own. That simple description reveals a family to study, rather than just one troublesome numerical list. The paper identifies this simplification as a human intermediate step, not the final proof. [6]

To obtain the proof-friendly family, choose $a=m$ and $b=m+1$, then multiply the unit capacity and all item sizes by $m(m+1)$. The capacity becomes $m(m+1)$, with $m$ items of size $m+1$ and $m+1$ items of size $m$. An optimum packing separates the two sizes and fills exactly two bins. For a small illustration derived from the family, take $m=3$: three items of size 4 fill one capacity-12 bin, and four items of size 3 fill the other. [6]

Mixing the sizes creates the difficulty. If a full bin contains $x$ items of size $m+1$ and $y$ of size $m$, then

Take the remainder of each side after division by $m$, an operation called reducing modulo $m$. The terms $xm$, $ym$ and $m(m+1)$ are all divisible by $m$, leaving $x$ with remainder zero: $x$ must be a multiple of $m$. With only $m$ such items available, a full bin must therefore contain either all of them or none of them. A mixed bin cannot be exactly full. Because the total item volume equals two full bins, once the packing mixes sizes it must use at least three bins. This is the structural reason behind the bad examples. [6]

The authors separately establish that, as $m$ grows, randomly ordered Best Fit mixes the two sizes with probability tending to one. They thereby prove a lower bound of 1.5 on its absolute random-order ratio: on this family, its expected bin count approaches at least three while the optimum stays two. [6] The finite shuffle score helped locate the pattern; the parameterized construction and probability argument support the general statement. [6]

This changes what the discovery enables. A hard input shows one failure. A family with an explanation identifies a persistent weakness that algorithm designers can reason about. The authors also report that some generated programs remain dominated by hard-coded constants and offer little insight. Inspectable code supplies material for understanding; simplification and proof are additional achievements. [6]

The experiment determines which improvements survive

The same feedback that develops a useful idea can favor a shortcut that works only inside the experiment. To understand the discovery, we therefore need to know what the evaluator makes visible.

In an AlphaEvolve adaptation for fully homomorphic encryption—computation on encrypted data—the researchers let the system modify low-level computational routines on TPUs, seeking better scheduling and layout rather than a new encryption protocol. Optimizing isolated polynomial multiplication failed to improve the full execution. Broader editable scope and scoring the complete bootstrapping computation, including the operations around that multiplication, exposed improvements that the smaller target missed. The relevant computational unit was determined partly by the cost the researchers needed to reduce. [7]

That project also records a more direct repair. An initial evaluator failed to cover every value of a three-input lookup table. Researchers changed it to check all values. The feedback could guide the search toward the desired behavior only after the desired behavior was represented adequately in the test. Human review remained part of integration. [7]

A separate study, Metal-Sci, shows how a genuine measured speedup can stop being useful on unseen inputs. On one M1 Pro benchmark, a GPT-5.5-generated three-dimensional Fourier-transform kernel achieved a 2.95-fold geometric-mean speedup over its seed on the sizes visible during search. [8] On a held-out cube of size $256^3$, it achieved only 0.23 times the seed's speed. [8] Its fast branches handled lengths 32, 64 and 128; other lengths took a much slower direct-transform fallback. [8] The held-out configuration was assessed only after search and never returned as feedback, so it could reveal a weakness the optimized score had not exposed. This is one hardware- and workload-specific experiment, not a general ranking of models. [8]

These failures teach something about the invention itself. The search can exploit a layout, an input restriction or a local objective just as effectively as it can exploit an algebraic identity. A useful result needs the experiment's boundary to match the computation that will actually consume it. Changing that boundary can change which idea looks better.

Reuse makes small discoveries consequential

Once a gain applies to the computation that will consume it, a further question follows: can repeated savings justify the cost of finding it? The cost of finding an algorithm and the cost of using it are different. Thousands of experiments can leave behind a tiny rule that runs repeatedly. In a simplified accounting model, if discovery costs $C$ units of a resource and each use saves a constant $s\gt 0$ units of the same resource, savings exceed discovery cost after more than $C/s$ uses. This is conditional arithmetic: it excludes integration and maintenance and does not supply a measured break-even point.

AlphaEvolve's authors report two concrete production consumers. In Google's Borg scheduler, a generated heuristic ranks machines already judged feasible for a job. Historical simulation, an unseen recent-workload test and fleet deployment are separate stages. The authors report that post-deployment measurements recovered an average 0.7% of fleet-wide compute resources that would otherwise be stranded by imbalanced resource use. [1] That is recovered capacity, not a measured 0.7% reduction in energy or expenditure. [1]

In Gemini kernel engineering, another generated heuristic selects tile shapes for an existing matrix-multiplication kernel. The underlying mathematical operation stays fixed while the shape of its execution changes. The paper reports an average 23% kernel speedup over the expert-designed heuristic and a corresponding 1% reduction in overall training time, using real TPU runtimes and a held-out half of user-derived input shapes. [1] The authors say the heuristic was deployed in production. These are first-party reports. [1]

The promising frontier follows from these mechanisms. A useful change must be expressible through the editable programs or arithmetic combinations the search can construct; experiments must distinguish its consequences; and the output must be valuable enough to study or reuse. Sometimes that value is repeated execution of a small routine. Sometimes it is a new construction or a clearer explanation of an algorithm's weakness. Human work in choosing the representation and building the experiment determines which of those possibilities the search can reach.

Conclusion

AI can find a better algorithm by making computational proposals whose consequences are tested, retained and developed. Existing knowledge supplies ingredients and possible moves; execution reveals which new arrangements work in the chosen problem. A discovered rule can change a decision, while a discovered search procedure can uncover a new arrangement of arithmetic.

The process need not end at the winning program. Researchers can turn its repeated structure into a general construction, explain its advantage or failure, and make that insight the starting point for another experiment. The resulting opportunity is broader than automatic code improvement: search can produce both useful computation and new objects of human understanding. The next question is which representations and experiments will expose valuable ideas that our current methods have not yet made easy to find.

Limitations

This account develops selected program-search cases, not a success-rate estimate for arbitrary algorithmic problems or a survey of every AI discovery method. AlphaEvolve's reported architecture and results refer to its June 2025 v1 paper; the later studies have their own tasks, models and evaluation conditions. Their findings do not establish one universally superior search strategy.

The source-code example is a static reading and hand-derived decision, not a newly executed benchmark. The rank-48 coefficient arrays were not independently reconstructed here, and the reported product count does not establish practical speed or floating-point stability for that scheme. Deployment figures are the AlphaEvolve authors' reports rather than independent fleet audits. Complete cost accounting and the eventual reach of the selected discoveries remain unestablished.