RL for Scientific Discovery: AlphaTensor, AlphaChip, and AlphaDev

TL;DR

The techniques covered throughout this site — MCTS-guided self-play (companion article), model-based planning, distributed training — aren’t limited to games. Reframed as single-player games against an abstract combinatorial problem, the same machinery has produced genuinely new results in domains humans have studied for decades. AlphaTensor discovered matrix multiplication algorithms using fewer scalar multiplications than any previously known method for certain matrix sizes, by treating algorithm discovery itself as a game. AlphaChip frames computer chip component placement — traditionally weeks of expert engineering effort — as a sequential placement game, solved with the same actor-critic and self-play techniques used elsewhere on this site. AlphaDev discovered faster sorting and hashing routines at the assembly-instruction level. These aren’t new algorithms so much as a demonstration of how far the existing RL toolkit reaches once the “game” is redefined.

The Same Pattern, Three Domains

graph TD
    A[Reframe the Problem as a Single-Player Game] --> B[AlphaTensor: matrix multiplication algorithms]
    A --> C[AlphaChip: chip component placement]
    A --> D[AlphaDev: assembly-level algorithm discovery]
    B --> E[MCTS-Guided Self-Play]
    C --> E
    D --> E

    style E fill:#6366f1,color:#fff

Problem Statement

Some of the hardest open problems in computer science and engineering are, at their core, search problems over an enormous combinatorial space with a well-defined success metric — exactly the structure MCTS and self-play (covered in the companion article) were built to handle, just not originally aimed at board games. The insight behind this entire line of work is recognizing that “find a faster algorithm,” “place these chip components well,” and “win at Go” share the same underlying shape: a sequence of discrete decisions, evaluated only once the full sequence is complete, in a space too large to search exhaustively.

AlphaTensor: Algorithm Discovery as a Single-Player Game

AlphaTensor (Fawzi et al., 2022) frames matrix multiplication algorithm discovery as TensorGame: the state is a tensor representing the remaining computation needed, an action decomposes part of that tensor (corresponding to one scalar multiplication in the resulting algorithm), and the game ends when the tensor is fully decomposed — with the reward being negative the number of moves taken, directly rewarding algorithms that use fewer multiplications.

def tensor_game_step(current_tensor, decomposition_action):
    # Each action proposes a rank-1 decomposition (u, v, w) reducing the target tensor
    u, v, w = decomposition_action
    rank_one_term = torch.einsum("i,j,k->ijk", u, v, w)
    next_tensor = current_tensor - rank_one_term

    reward = -1   # constant per-move penalty: rewards algorithms using fewer total multiplications
    done = torch.all(next_tensor == 0)
    return next_tensor, reward, done

This is solved with the same AlphaZero-style architecture covered in the companion MCTS article: a neural network provides value and policy priors, MCTS searches over candidate decompositions guided by those priors, and self-play against increasingly difficult matrix sizes provides the training data — for certain matrix sizes, this discovered algorithms provably using fewer scalar multiplications than the best previously known methods, including ones that had stood for decades.

AlphaChip: Chip Floorplanning as Sequential Placement

AlphaChip (Mirhoseini et al., 2021) frames the placement of a chip’s macro components (memory blocks, logic units) onto a physical floorplan as a sequential decision problem: at each step, the agent places one component onto the chip canvas, and the episode’s reward is a weighted combination of the final layout’s wirelength, congestion, and timing — metrics that can only be evaluated once placement is complete.

def chip_placement_step(policy, current_canvas_state, remaining_components):
    component = remaining_components.pop(0)
    placement_action = policy(current_canvas_state, component)   # where to place this component

    updated_canvas = place_component(current_canvas_state, component, placement_action)
    reward = 0 if remaining_components else evaluate_final_layout(updated_canvas)  # reward only at the end
    return updated_canvas, reward, len(remaining_components) == 0

The policy is trained across a large distribution of different chip designs (rather than just one), so it transfers what it learns about good placement principles across designs — a direct application of the transfer and generalization ideas covered in a companion article, letting a new chip design benefit from placement experience on previous, different designs rather than starting from nothing.

AlphaDev: Discovering Algorithms at the Assembly Level

AlphaDev (Mankowitz et al., 2023) pushes the same idea further down the stack: instead of discovering algorithms in a mathematical abstraction like AlphaTensor’s tensor decomposition, it searches directly over sequences of CPU assembly instructions, framing algorithm construction (for tasks like sorting small fixed-size lists) as a single-player game where actions are individual assembly instructions and the reward combines correctness (does it actually sort correctly) with latency (how fast does it run).

def assembly_game_step(current_program, instruction_action, test_inputs):
    candidate_program = current_program + [instruction_action]

    correctness_reward = evaluate_correctness(candidate_program, test_inputs)  # must sort correctly
    latency_penalty = -estimate_cycle_count(candidate_program)                  # fewer cycles is better

    return candidate_program, correctness_reward + latency_penalty

This discovered new short sorting routines that were subsequently incorporated into a widely-used C++ standard library implementation — a rare, concrete instance of RL-discovered code shipping into infrastructure used at massive scale, rather than remaining a research result.

Comparison Table

Applications

• Algorithm and hardware design research — these systems demonstrate RL as a genuine tool for discovering, not just optimizing within, well-studied technical domains.
• Electronic design automation (EDA) — AlphaChip-style placement has direct commercial relevance to chip design turnaround time, a traditionally weeks-long expert-driven process.
• Compiler and systems optimization — AlphaDev’s assembly-level search generalizes to other low-level code optimization problems beyond sorting, wherever correctness and performance can both be evaluated automatically.
• Any well-specified, evaluable combinatorial design problem — the general pattern (frame construction as a sequential game, evaluate only at completion, apply MCTS-guided self-play) is reusable well beyond the three specific systems covered here.

Key Learnings

1. None of these systems required inventing new RL algorithms — they required reframing old problems as games the existing toolkit already handles. The core machinery (MCTS-guided self-play from the companion article, transfer across problem instances) is unchanged; the contribution is the problem formulation.
2. A precisely evaluable, automatically computable reward is what made these problems tractable for RL at all. Matrix multiplication correctness, chip layout metrics, and code correctness/latency can all be checked programmatically and objectively — domains without that property (most open scientific questions) aren’t yet amenable to this exact recipe.
3. These results are a genuine existence proof, not a general solution to scientific discovery. They show RL can find results humans hadn’t, in specific, narrow, precisely-specified combinatorial domains — extrapolating that to open-ended scientific discovery broadly remains a substantially harder, unsolved problem.

References

• Fawzi, A. et al. (2022). Discovering Faster Matrix Multiplication Algorithms with Reinforcement Learning. Nature, 610.
• Mirhoseini, A. et al. (2021). Chip Placement with Deep Reinforcement Learning.
• Mankowitz, D. et al. (2023). Faster Sorting Algorithms Discovered Using Deep Reinforcement Learning. Nature, 618.