1Why Mithril
A typical computer has many CPU cores and a GPU with thousands of arithmetic units, but an ordinary loop runs on only one of those cores. To use the others, a programmer usually splits the work into threads and protects shared data with locks, which allows a specific kind of error: two threads update the same value at the same moment, and the answer depends on which one wrote last. Running the work on a GPU usually means writing it a second time, as CUDA kernels[16].
In Mithril, a program is written once, in ordinary sequential form, using functions, loops, tuples and arrays in a subset of Python, with no threads, locks or kernels. The compiler finds the parts of the work that can run at the same time, such as independent function calls and independent loop iterations, and the same source then runs on one thread, on all cores, on a GPU, or on the CPU and the GPU together. In every case it returns the same answer, bit for bit.

What an interaction net is
This guarantee follows from the way Mithril represents a program. Most languages describe a computation as a sequence of instructions that run one after another and read and modify shared memory. An interaction net describes a computation as a graph instead, whose nodes are called agents and are connected by wires. A number is an agent, and so are an addition, a function call, and a copy of a value that two parts of the program need.
Running the program means rewriting the graph. Each agent has one main port, and when the main ports of two agents are connected, a rule says what replaces them. An addition agent connected to two numbers, for example, is replaced by one number, their sum, and a call connected to a function is replaced by the function's body. Each rewrite removes the two agents, inserts a small new piece of graph and reconnects the wires that led to them.
A rewrite changes only the two agents it replaces. Two rewrites on different pairs of agents do not touch the same data, so they can happen in either order, or at the same time, with the same result.
Two properties follow from this, and Mithril relies on both:
- ParallelPairs that are ready at the same moment are independent, so separate cores can rewrite them at the same time. No locks are needed, because the cores never update a shared variable.
- DeterministicEvery order of rewriting that finishes produces the same final graph, a property called confluence (chapter 3). The order in which the cores do their work cannot change the answer.
A closer look at interaction nets: ports, rules and a worked example
An agent has one principal port and a fixed number of auxiliary ports, and every wire connects exactly two ports. Most of Mithril's agents have two auxiliary ports. An addition agent, for example, receives its first operand on its principal port and uses its auxiliary ports for the second operand and the result.
Because a wire has exactly two ends, a value in a net has exactly one consumer. A program that uses a variable twice therefore needs a copy agent, written δ, whose two auxiliary ports lead to the two uses, and a variable that is never used is connected to an erasure agent, written ε. Copying and deleting a value are rewrite steps, carried out by rules in the same way as arithmetic.
Two agents form an active pair only when they are connected principal port to principal port. Mithril's rules fall into a few families:
- Compute. An arithmetic or comparison agent that meets a number stores it, and when it meets the second number it is replaced by the result.
- Unfold. A call agent is replaced by the body of the function it names, with the arguments connected to the parameters.
- Branch. An
iformatchagent that meets a value keeps the branch that the value selects and discards the others, which were never built. - Copy. A
δagent that meets a number, a tuple or a function produces two copies of it. Twoδagents that are the two halves of the same copy cancel each other, and their wires are joined directly. - Erase. An
εagent that meets another agent deletes it and places anεon each wire that led to it, so an unused structure is removed one agent at a time. - Apply. A function value meeting an application connects the argument to the parameter and the body to the result.
These rules are the reason the order of rewriting does not matter. Each agent has only one principal port, so it belongs to at most one active pair at a time, and the two agents of a pair determine which rule fires. Firing a rule changes only its own pair and the wires attached to it, so every other active pair is still present afterwards and still fires the same rule. Lafont showed that this property implies more than confluence: every order of rewriting that reaches the end takes the same number of steps[1].
A short example shows the rules working together. The program y = 2 + 3; return y * y becomes a net with an addition agent, a δ agent and a multiplication agent, and it reduces in five steps:
- The addition agent meets
2and stores it. - It meets
3and is replaced by5. - The
5now faces the principal port of theδagent, and the pair is replaced by two copies of5. - The multiplication agent meets the first copy and stores it.
- It meets the second copy and is replaced by
25.
In this small net the steps must happen in sequence, because each one produces the value the next one needs. A larger program contains many such chains that do not depend on each other, and the runtime spreads them across cores. Because every input of this example is written in the source, Mithril's compiler performs all five steps before the program runs (chapter 4).
No step needs information from outside its own pair, which is why the same rules can run on one core, on many cores, on a GPU, or inside the compiler. Lafont's papers on interaction nets[1] and interaction combinators[3] give the original definitions, and the HVM repository[4] describes a large implementation.
The idea developed over several decades:
- 1987Jean-Yves Girard's linear logic[2] treats every value as used exactly once.
- 1990Yves Lafont defines interaction nets[1], in which each rewrite involves only two connected agents.
- 1997Lafont shows that three kinds of agent, the interaction combinators[3], are enough to express any computation.
- HVM, BendVictor Taelin and HigherOrder Co. build working implementations: HVM[4] evaluates interaction combinators on CPU cores and GPUs, and Bend[5] shows that programs written in an ordinary style can run in parallel without annotations. Bend 2[6] later compiles programs to C instead of rewriting nets.
Rewriting at compile time
Rewriting a net has a cost. A single machine instruction can add two numbers, but adding them by rewriting takes several steps: allocating an agent, matching a rule and reconnecting wires. HVM performs these steps for every operation while the program runs, and Bend 2 avoids them by discarding the net and generating C.
Mithril keeps the net but changes when the rewriting happens. The same rules are applied at two different times (chapter 4):

- Compile timeThe parts of a program that the source itself fixes are rewritten before the program runs. Constants are computed, small functions are inlined, and
iftests with a known outcome are resolved[8]. These steps are not separate optimization passes but the program's own rules, applied early, so they cannot change its meaning. - Run timeThe parts that depend on input, such as the colour of each pixel in a ray tracer, become ordinary machine code, in which an addition is a single instruction. A net remains only where it is needed, to share a value that several parts of the program use and to give independent work to idle cores.
Mithril's speed is measured against a sequential C program for the same algorithm, as the number of cores Mithril needs to run faster than that program[7]. Mithril is a research language. Its core rules are proved confluent in Lean[9], and every backend is checked against a reference interpreter. Its open problems, described in chapter 10, include using vector instructions for independent work, keeping a GPU's arithmetic units occupied, and running irregular machine-learning workloads.
Mithril, Bend 1 and Bend 2
| Bend 1[5] | Bend 2[6] | Mithril | |
|---|---|---|---|
| What runs | The interaction net, rewritten on HVM[4] | One generated C file, no net | Native code for input-dependent work, plus a small net |
| When the net is rewritten | At run time, every step | Not at all | Mostly at compile time; at run time only to share values and hand out work |
Cost of a + b | A rewrite: allocate, match a rule, rewire | A machine instruction | A machine instruction |
| Where parallelism comes from | The net's rules, no annotations | The generated C, not the net's rules | The net's rules, no annotations |
In short: Bend 1 rewrites the net at every step while the program runs, Bend 2 discards the net and compiles to C, and Mithril keeps the net and does most of the rewriting at compile time. Mithril's mechanisms were developed independently, and Bend is the baseline it is compared against.
2Mithril in ten minutes
If you can read Python, you can read every program in this guide. Mithril uses Python's syntax but changes three things: a value never changes after it is created, two parts of a program never share a value by modifying it, and the programmer never writes a thread, a task or a device. The eight pieces below make up the whole syntax.
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)if c > 0:
return a
return bfor i in range(n):
s = s + f(i)p = (x, y, z)
a, b, c = pmatch.@data
class L:
Nil: ()
Cons: (h, t)def stage(c):
return lambda x: x * 3 + setup(c)array_set returns a new array and leaves the old one for its readers. If no other variable still refers to the old array, array_set writes into it directly instead of copying it.a = array_new(n, 0)
a = array_set(a, i, v)f32(x) makes a value single precision and the type spreads through the arithmetic.r = sqrt(f32(d))A first program
The black hole in the header is a program of about 800 lines of ordinary functions. They compute the equations of a light ray near a spinning black hole, perform a Runge-Kutta step, and follow one ray recursively until it falls in, crosses the disk or reaches the stars. The image is produced by a few loops that run one after another, and the first of them sends one ray through every pixel of a strip of frames.
def main():
...
m = width() * height() * frames()
base = array_new(m, 0)
for i in range(m):
base = array_set(base, i, first_ray(i, cams, tab))
...
No thread appears in this code. Each first_ray(i, cams, tab) call reads only the camera table, the colour table and its own i, so Mithril can compute the pixels in any order, on any core or on the GPU. The writes into base happen one after another, but each is a single store, and most of the time is spent inside first_ray. The device and the number of threads are chosen when the program runs.
The whole system
The map below follows one program from its source file to running code, from top to bottom. Each box names the crate that implements that step, and the § mark gives the chapter that explains it. The dashed boxes beside the main path are the checks: the reference interpreter that every run is compared with, the two Lean proofs, model checking of the CPU's lock-free handoffs, and the test gates. The copper dashed box is the command that shows what the compiler did to a program. The rule table appears only once, inside compile-time reduction, and a dotted line connects it to both runtimes, because the compiler, the CPU and the GPU all fire the same rules.
How Mithril reads a program
Mithril runs two calculations at the same time whenever neither needs the other's result. To find where a program can run in parallel, it helps to ask which calculations can start together, which must wait for an earlier answer, and what data they share. The six problems below each have a different structure. Each animation runs the actual problem and schedules it the way Mithril's runtime does, starting a task as soon as its inputs exist and a worker is free.
Rendering: every pixel is independent
A ray tracer computes the colour of a pixel by sending a ray from the camera through it, following the ray as it reflects off the mirror sphere or bends through the glass sphere, and adding up the light the ray collects. The calculation reads only the scene description and the pixel's own coordinates, so no pixel needs the result of another. The program loops over the image row by row, but Mithril detects that the pixel(x, y) calls are independent and gives each one to whichever worker is free.
Some pixels take longer than others. A ray that hits the back wall stops after one shadow test, while a ray that hits glass splits into a reflected ray and a refracted ray, and both are traced further. In the animation below, the tiles over the spheres take several times longer than the tiles over the walls. With one worker the frame fills in reading order. With several workers, a worker that finishes a tile takes the next one in the queue, so a slow tile over the glass sphere does not delay the wall tiles queued behind it.
Merge sort: split, solve, combine
Merge sort orders a list by halving it until each piece is small, sorting the pieces, and merging the sorted halves back together. Merging two sorted lists only ever compares their first elements. The two halves of any split have separate inputs, so they can be sorted at the same time, but a merge cannot start until both of its halves are sorted.
The amount of available work therefore grows and then shrinks. Each split doubles the number of pieces, so four workers are busy while the pieces are sorted, and each merge halves the number again until the last merge runs on a single worker. The trace of busy workers under the tree shows this rise and fall.
[8, 3, 6, 1, 7, 2, 5, 4]. A coloured tag shows which worker runs each step. Sorting example.Four queens: a search that grows as it runs
The puzzle asks for every way to place four queens on a 4 × 4 board so that no two share a row, column or diagonal. A backtracking search places one queen per row. Each legal placement opens a branch for the next row, and a board with no legal square left is a dead end.
The shape of this search tree is not known in advance, because a branch exists only after its parent board has been checked. A first queen in the corner leads to a dead end one or two rows later, while a first queen in the second column leads to a solution. Mithril starts each new board as a task as soon as it appears, so a worker that finishes checking a board immediately takes one of the boards the search has just produced. The search finds the puzzle's two solutions.
Nearest neighbours: many searches, one shared map
Given a set of stored points, the task is to find the closest one to each of many query locations. A k-d tree[13] speeds this up by dividing the plane in half repeatedly, alternating vertical and horizontal cuts, until each cell holds a few points. A query descends to the cell that contains it, then moves back up and checks a neighbouring cell only if that cell could hold a point closer than the best one found so far.
The tree is built once and only read afterwards. Every query walks the same tree and keeps its own best result so far, so queries run side by side without locks or copies. Within one query the visits happen in order, because each visit decides whether the next cell needs to be checked. Queries in crowded regions visit more cells, so the scheduler receives jobs of different sizes.
Collatz: a chain of dependent steps
The Collatz rule halves an even number and replaces an odd number with three times itself plus one. Applied repeatedly, it makes the number rise and fall until it reaches 1. Starting at 6 gives 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1.
def steps(n):
count = 0
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
count = count + 1
return count
Each step needs the number that the previous step produced, so the chain is strictly sequential: worker 1 computes the whole chain from 6 down to 1 while workers 2, 3 and 4 have nothing to do. A batch of different starting numbers behaves differently, because the chains for 6, 7, 8 and 9 do not depend on each other. They run side by side, and the longest chain determines when the batch finishes. A loop can have either structure, and its dependencies determine which one.
A spinning black hole: work done at compile time
The video at the top of this guide is a Mithril program of about 800 lines. For every pixel it follows a ray of light backward from the camera through the curved spacetime around a black hole that spins at 0.99 of the maximum possible rate. A Runge-Kutta step moves the ray forward again and again until it falls through the horizon, crosses the glowing disk of gas or escapes to the stars. The colour it brings back includes the Doppler and gravitational shifts of the light.
The program consists of ten loops that run one after another, each filling an array: the colour table, the camera path, a first ray per pixel, extra rays at sharp edges, four blur passes for the glare, and the final image. Inside a loop, pixel i reads only arrays made by earlier loops and writes only its own slot, so every pixel is an independent task. The work per pixel varies widely, as the map below shows. A ray that hits the near side of the disk stops after about ten steps, a ray that escapes to the stars takes a few hundred, and a ray that spirals into the shadow takes more than a thousand. Idle workers take the next pixels as they finish, so the long rays around the shadow do not delay the short ones.
main returning each ray's step count.Many of the black hole's inputs are written in the source, including the spin, the camera's path, the size of the disk and the image size. While compiling, Mithril fires every rule that depends only on these values. The radius of the innermost stable orbit, for example, is a formula with three cube roots and two square roots of the spin, and it becomes the single constant 1.4545 inside disk and march. The square of the spin, 0.9801, and the cosine and sine of the camera's tilt, 0.035 and 0.99939, appear as numbers in ray. The function cbrt runs a loop of Newton steps a fixed number of times, so it unrolls from 4 agents into 321 with no call left inside. None of this is done by a separate optimizer, because each step is one firing of the rules from chapter 3, the same rules the runtime fires (chapter 4). The code that reaches the processor contains only the physics that depends on the pixel, as straight-line native code.
3Why the answer never changes
The glass shader in the ray tracer traces a reflected ray and a transmitted ray, then blends their colours. Either ray may finish first, and the blend waits for both.
# From glass(); surface geometry and the total-reflection branch omitted.
mirror = trace(add(p, scale(n, eps())), reflect(d, n), depth - 1)
through = trace(sub(p, scale(n, eps())), rd, depth - 1)
return add(scale(mirror, f), scale(through, 1.0 - f))
The colour calculation needs both arguments. Either result may arrive first.
To see why the order cannot matter, consider the interaction net of this program, built from the agents and wires of chapter 1. Two of their parts have precise names: an agent's main port is its principal port, and two agents connected at their principal ports form an active pair. A rule replaces an active pair with a small new net and reconnects the wires that led to it, and one replacement is one step of computation.
Mithril has only a few rules. An erasure agent that meets a number deletes both, because nothing uses the number. Other rules apply a function, compute an arithmetic operation, select a branch or copy a shared value to two consumers. Because two active pairs never share an agent, firing one cannot affect another.
(2 × 3) + (4 × 5)two independent multiplications6 + (4 × 5)(2 × 3) + 206 + 20 → 26both orders meet at the same resultThis local guarantee is called the diamond property, and it implies confluence: every order of reduction that finishes ends at the same net. The scheduler can therefore fire any ready pair on any core at any moment. For Mithril's core rules the property is proved in Lean[9] (chapter 8).
One kind of change is not covered by reordering. Summing an array in chunks changes how the additions are grouped, so that (a + b) + c becomes a + (b + c). This is correct only when the operation is associative and has an identity element, so Mithril splits such a sum only after proving both facts for the numbers it actually uses. Integer addition meets both conditions, but floating-point addition does not, because its rounding depends on the grouping.
4One rule table at compile time and run time
A program's inputs become known at two different times. Some, such as constants, flags and helper functions, are written in the source, and others, such as n in the example below, are known only when the program runs. While compiling, Mithril fires every rule whose inputs are in the source and keeps the rules that need run-time input for later. The program that is left after compiling, which is the one that actually runs, is called the residual program.
In shade(n) below, only n comes from the program's input. The flag 1, the number 3 and the two helper functions are written in the source, so the compiler evaluates pick(1, square(3), n) to 9 before the program ever runs.
def square(x):
return x * x
def pick(c, a, b):
if c > 0:
return a
return b
def shade(n):
return square(n) + pick(1, square(3), n)
n. The program that actually runs is n * n + 9, the residual program. Example source.Inspect the residual and the generated Rust
MITHRIL_NET_CORE=1 target/release/mithril net examples/specialize.py
# shade = Op2(Add, Op2(Mul, Var(0), Var(0)), Num(9))
cargo run --release -p mithril-cli --example dump_gen -- \
examples/specialize.py /tmp/mithril-specialize.rsCore is the compiler’s internal expression format: Var(0) is the argument and Op2 an operation on two inputs. The example supplies 5 at run time and returns 34. The generated function:
fn s_2(fuel: &mut i64, v0: i64) -> i64 {
let fl: i64 = 1i64;
let s1: i64 = v0.wrapping_mul(v0);
let s2: i64 = s1.wrapping_add(9i64);
return s2;
}The residual n * n + 9 is two machine operations on a 64-bit register. Generated names change between compiler revisions.
Evaluating a program when part of its input is already known is called specialization[8]. The compiler does it within a work budget. If the budget runs out, the unfinished part stays in the residual program, and the program still means the same thing because the Lean proof also covers partly reduced nets.
For the astute reader
Folding square(3) and selecting the branch of pick are standard steps in an optimizing compiler, which folds constants, inlines small functions and removes branches whose outcome is known. Mithril performs the same optimizations on purpose, but by a different method.
A conventional compiler performs this work in separate passes, each written by hand and each needing its own argument that it preserves the program's meaning. The order of the passes also changes the resulting code, which compiler writers call the phase-ordering problem.
In Mithril, each of these optimizations is a firing of the same interaction rules that define what the program means. Because the rules are confluent, the compiler can apply them in any order and stop at any point, and the program still means the same thing. When reduction runs to completion, every order produces the same residual program. For the core rules this is proved in Lean[9]. The compiler also unfolds calls whose arguments are still unknown, a rule outside the proof, which is checked by comparing each program's answer before and after compile-time reduction.

2 × 3 + 4 × 5 is rewritten in three orders, all ending at 26. Then the compiler's optimizations are shown as rewrites: order A selects the branch first and order B inlines first, and both reach the residual n * n + 9, so the order of the steps does not matter.Next, the compiler translates the residual program into code for the hardware, a step called lowering. The residual n * n + 9 is straight-line arithmetic, so it becomes two machine instructions on a register, with no agents allocated and no rules dispatched. A call that starts independent work becomes a task that another core can take, and a value that its consumers are still waiting for stays in the net.
How the residual becomes native code, tasks and joins
When the program runs, a function that starts independent branches, such as msort with its two recursive calls, begins on one worker with a work budget. When the budget runs out at a safe point, the worker pauses and offers the unfinished branches to idle workers. It leaves behind a continuation, a record of what to do when the results come back, and a join collects the results, in the same way that the colour blend in chapter 3 waited for both rays. If compiled code needs a value that the net has not produced yet, a bridge makes it wait, and the results of compiled calls are delivered back into the waiting wires. The native code never computes anything the net would not compute, because it is a faster way to reduce the same part of the net.
Sharing work through closures
A data pipeline is built from stages. Each stage is configured once, with a setting c read at run time, and then applied to thousands of inputs. Preparing a stage takes much more work than applying it, because setup(c) builds a large table from the configuration.
def stage(c):
return lambda x: (x * 3 + setup(c)) & 1048575
Written this way, a strict language recomputes setup(c) in every call, because the expression is inside the body of the lambda, and a programmer would have to move it out by hand. In Mithril this is not necessary. setup(c) depends only on the captured configuration, so the sharing rules compute it once per stage and connect the result to every application. Nothing is cached by comparing expressions, because the value has one producer and many consumers.
setup(c), blue blocks the per-input work. Pipeline source.5What Mithril gives you
Deterministic
The same input gives the same output, bit for bit, on 1 thread, 16 threads, an NVIDIA or Apple GPU, x86-64 or arm64. Confluent rules and immutable values leave no room for a data race or a schedule-dependent result.Parallel by construction
Independent calls, independent loop iterations and sums proved safe to split become parallel work because of how the program is built, not because you asked. The source has no threads, locks, pragmas or kernels.CPU and GPU together
The CPU and the GPU can work on one computation at the same time. A loop or sum that the compiler has proved can be split is cut into chunks, and each device takes the next chunk when it becomes free, so the faster device does more of the work. The answer does not depend on which device computed which chunk.One source for CPU and GPU
The same file compiles to native code for CPU workers and to CUDA for an NVIDIA GPU, with one rule table and one runtime model on both. On Apple silicon the GPU can also take blocks of large proven loops beside the CPU threads, through Metal. You pick the device when the program runs.Work done once
Compile-time reduction removes everything the input does not decide, and sharing rules keep closures from repeating their setup.Rendering on 1 thread, 16 threads and a GPU
A spinning black hole
1280×720, 450 frames. Kerr light rays, extra rays at sharp edges, glare. GPU rate is device time in 40-frame strips. Measurements · source.
Path tracing[12]

256×256 · 64 samples per pixel, up to 6 surface hits per path. Tracer source.
Ryzen 7 7800X3D and RTX 4090. Path tracing, 5 October 2026: FPS is warm throughput over a 24-frame batch, median of three runs. The GPU figure is device time plus reading back and writing the image, without the one-off CUDA setup; compilation excluded. All frame pixels match across CPU and GPU. Measurements and reproduction.
| One frame | Mithril 1 | Mithril 16 | GPU (warm) |
|---|---|---|---|
| Path tracing, 256×256 × 64 paths | 1.716 s | 0.175 s | 0.011 s |
| Black hole, one 1280×720 frame | 11.42 s | 1.25 s | 0.062 s |
Medians of three built-artifact runs after a warmup, same machine, 5 October 2026 (the black hole's 1-thread time is one run). Compilation excluded. Every lane writes its image with --image. GPU times are warm: device time plus reading back and writing the image, without the one-off CUDA context and memory setup (about 120 ms per process). Raw samples.
Read each row from left to right. The same unchanged source runs about nine times faster on sixteen threads than on one, and the GPU is about eleven times faster again on both scenes. Every lane returns identical pixels.
The CPU and the GPU on one computation
A GPU usually replaces the CPU for the length of a computation, so the CPU cores wait while the GPU works. Mithril can let both devices work on the same computation instead, because the compiler already knows which parts may be divided. A sum whose operation is proved associative (chapter 3) can be cut into chunks whose partial sums add up to the same total, and a loop whose iterations are independent can be cut into blocks of iterations. Each device takes the next chunk when it finishes the previous one, so the faster device ends up with more of the work and the two finish at about the same time. The result of a chunk depends only on its range, which is why the answer is the same whichever device computed which chunk.
On Linux the CPU program and the CUDA program run side by side as two processes, each computing the whole program, and they share the large sums through a table in a shared file (--coop). Because both compute the final answer, the run also checks the two devices against each other and fails if they disagree. On macOS the Apple GPU joins the CPU threads on large loops over independent iterations (--metal), and a cost model gives it a block only when it is predicted to finish the block no later than the CPU threads would.
| One computation, two devices | CPU alone | GPU alone | CPU + GPU | vs CPU |
|---|---|---|---|---|
| Subset-sum search · Ryzen 7800X3D + RTX 4090 | 1.649 s | 2.494 s | 1.138 s | 1.45× |
| Uniform binary32 fill · Apple M4 | 0.763 s | 0.846 s | 0.576 s | 1.32× |
Medians of three runs after a warmup, compilation excluded, 7 October 2026. CPU alone uses 16 threads on the Ryzen and 10 on the M4; the Ryzen's shared run uses 15 CPU threads beside the GPU. Times are wall clock for the whole process. Every run returns the same answer on every device. Runtime architecture.
Both programs are cases in which the two devices run at similar speeds. The subset-sum search splits into 1,024 sub-searches of very different sizes, and the uniform fill runs the same 256 floating-point steps for each of four million elements. When one device is several times faster than the other, as the RTX 4090 is on the ray tracers, sharing adds little, and the program is best run on the faster device alone.
Against a sequential C program
Chapter 1 measures Mithril by the number of cores it needs to run faster than a sequential C program for the same algorithm. Here is that comparison on a batch of nearest-neighbour queries over a shared k-d tree. On one thread Mithril runs level with C; on sixteen it is four times faster. The GPU is slower on this program, because the queries branch unpredictably and leave most lanes of each warp idle (chapter 10).
| k-d tree, 218 points and queries | Time | vs C |
|---|---|---|
| C, 1 thread | 0.372 s | 1.0× |
| Mithril, 1 thread | 0.375 s | 0.99× |
| Mithril, 16 threads | 0.089 s | 4.2× |
| Mithril, GPU (warm) | 0.617 s | 0.60× |
gcc -O2; minimum wall-clock time of five runs on 5 October 2026 (GPU: warm device time, median of three), builds excluded, outputs checked. A parallel C version has not been measured. Methods and samples.
Against Rust, on programs a general-purpose language must handle
| Program | Rust · 1 thread | Mithril 1 | Mithril 16 |
|---|---|---|---|
| Expression interpreter | 2.40 s | 1.72 s | 0.19 s |
| List merge sort and quicksort | 6.78 s | 1.58 s | 0.69 s |
| Heavily shared graph | 1.73 s | 2.54 s | 0.36 s |
| Depth-first search over adjacency lists | 0.90 s | 1.46 s | 0.27 s |
| Closures with shared setup | 0.30 s | 0.02 s | 0.02 s |
| Copy-on-write array versions | 1.01 s | 1.97 s | 1.96 s |
| Persistent map keeping old versions | 1.49 s | 1.66 s | 1.65 s |
| Serial mutual recursion | 0.30 s | 0.31 s | 0.32 s |
| Closures depending on every input | 0.01 s | 4.53 s | 4.49 s |
Exploratory corpus at e8441a9, 4 October 2026, one wall-clock sample per lane (the slower rows repeated within 0.02 s), checked against a Python oracle. The Rust twins follow the shape of the Mithril source (Rc lists, boxed closures); a hand-tuned Rust program could be faster. Design §11.1 · harness.
The wins come from two places. Recursive work spreads across cores without any code to arrange it, and sharing rules keep a closure from repeating setup that depends only on what it captured. The losses are chapter 7's subject.
On an Apple M4
The same sources run on a Mac mini with an Apple M4, which has 4 performance cores, 6 efficiency cores and a 10-core GPU. On macOS the compiler emits arm64 code for the CPU and Metal code for the GPU. The Metal GPU does not run the whole program. It joins the CPU threads on large loops whose iterations the compiler has proved independent, and it takes a block of iterations only when a cost model predicts that it will finish them no later than the CPU threads would.
| Apple M4 | C · 1 thread | Mithril 1 | Mithril 10 | CPU + GPU | GPU alone |
|---|---|---|---|---|---|
| Collatz sum | 0.330 s | 0.336 s | 0.051 s | 0.052 s | 0.223 s |
| Heat diffusion | 0.400 s | 0.531 s | 0.103 s | 0.124 s | 10.07 s |
| k-d tree queries | 0.158 s | 0.394 s | 0.131 s | 0.131 s | - |
| Path tracing, one frame | - | 1.115 s | 0.161 s | 0.212 s | 2.303 s |
| Whitted ray tracing, one frame | - | 0.106 s | 0.021 s | 0.022 s | 0.157 s |
| Uniform binary32 fill | - | 5.471 s | 0.763 s | 0.576 s | 0.846 s |
Mac mini, Apple M4, 7 October 2026. C compiled with Apple clang -O2. Ports: minimum of five runs (three for the GPU lanes); renders and the uniform fill: median of three after a warmup. Times are wall clock for the whole process, compilation excluded. "GPU alone" gives the GPU every loop it can take, and a dash marks a program with no such loop. Every lane returns the same bytes. All programs.
On the CPU, ten cores run these programs between 3.0 and 7.2 times faster than one core. The GPU speeds up the uniform binary32 fill, in which every element runs the same 256 steps: with the GPU sharing the work, the fill takes 0.576 s instead of 0.763 s on ten cores. On the ray tracers and on 64-bit integer loops such as the Collatz sum, the M4's GPU is slower than its ten CPU cores, so the cost model gives it little or no work. The model still misjudges some programs, and on the path tracer the shared run takes 0.212 s against 0.161 s on the CPU alone. Heat diffusion launches the GPU 502 times, and each launch waits several milliseconds before the GPU starts, which is why the GPU alone needs 10 s.
6Where to use it
To decide whether Mithril fits your problem, look at the shape of the computation rather than its domain. Mithril pays off when there is plenty of independent work, each piece big enough to be worth handing to another core, and most of all when that work is irregular: you cannot know a piece's size until it runs, or the pieces read shared data that would otherwise need locks.
- Rendering and simulation batches. Ray and path tracing, per-element simulation steps, Monte Carlo sampling with hashed random numbers that reproduce exactly on any device.
- Recursive search and divide and conquer. Game-tree and constraint search, branch-and-bound, sorting and tree algorithms, where branches appear at run time and differ in size.
- Many queries over shared read-only structures. Spatial indexes, lookup tables, rule sets checked against many inputs.
- Code that needs locks elsewhere. Five programs that require locks or atomics in C and Rust are written in Mithril without either, each with C and Rust versions for comparison. Lockless programs.
- Irregular planning in machine-learning systems. Mixture-of-experts routing[17,18] (top-k gating, capacity limits, overflow), sparsity patterns and graph traversals share the k-d tree's shape: a read-only structure, partitioning and data-dependent branching, balanced by the scheduler instead of by atomics and sorts.
- Executable specifications of distributed algorithms. Ring and tree all-reduce[19] or expert all-to-all exchange are local rules on a graph. Mithril runs such an algorithm with the same rules on CPU and GPU and checks it against the oracle, as a specification and schedule simulator.
- Compiler passes and planning. A rewrite system over an intermediate representation is a rule table, and the compile-time reducer runs it.
A saved computation: the compiler-planning demo
The compiler-planning demo expresses choices about fusion, vector width, tile size and placement as a Mithril program. It saves an unfinished net, then resumes it with different orders of ready work; the viewer shows the actual reduction traces, final plans and occupied net slots, and an independent exhaustive solver checks each answer. Costs are a synthetic contract, not device timings.
python3 demos/compiler_planning/demo.py --out target/compiler-planning/demo
# Open target/compiler-planning/demo/demo.html7Where not to use it
| If you need | Why Mithril is the wrong tool today | Use instead |
|---|---|---|
| Dense matrix multiplication or attention | Scalar execution with no tensors, layouts or tensor-core lowering. | A kernel compiler or an optimized numerical library. |
| Long serial dependency chains | Each step needs the previous step's result, so a second core has no work to take, yet every step still pays for the runtime's bookkeeping. | A direct C or Rust implementation. |
| Tiny closures applied many times | Copying and reducing a closure can cost more than its arithmetic when every part depends on the new input. | Benchmark the exact shape first. |
| Shared mutable state, I/O or systems integration | Values only; the language is a compute surface without general I/O. | C or Rust around a Mithril computation. |
| SIMD or other GPUs | CPU output is scalar: baseline x86-64, and arm64 on macOS (experimental). The full GPU engine targets one NVIDIA device, and on Apple silicon the GPU runs only large proven loops, through Metal. | Tools that expose those instruction sets and devices. |
You can see these limits in chapter 5's tables. Serial mutual recursion is a chain: extra threads have nothing to take, so sixteen threads run no faster than one. Copy-on-write array versions and the persistent map keep old versions of their data alive, which forces copies, so they trail Rust at any thread count. The closure interpreter builds new work for every input and loses by two orders of magnitude. And on one thread Mithril trails sequential C on four of the seven benchmark ports in the README, by up to 2.6× on the histogram, so on those its advantage appears only once there are cores to use.
On the GPU the picture is mixed. Warm, a black-hole frame and a path-traced frame each run about eleven times faster than on sixteen CPU threads, but the k-d tree, whose queries branch unpredictably, is about 1.6 times slower than on one CPU thread. On the Apple M4 the GPU is faster than the ten CPU cores only on uniform floating-point work. Today the GPU's sure benefit is running the same program with the same results; closing its speed gap on irregular work runs through the vectorization and per-lane work in chapter 10.
Memory needs watching too. Storage is reused when ownership allows, but keeping old versions of a value can force copies, and task records, net agents and queues all take space. A different reduction order can change peak memory even though the answer stays the same.
8Proved and checked
Some of this guide's claims are proved and some are checked by running programs. The three guarantees below are proved or model-checked. Each is stated in plain words first, then shown on an example, then bounded by what it does not cover. The compiler, the extra rules and both runtimes are checked by tests, listed at the end of the chapter.
Proof 1 · The order of rule firings cannot change the result
Take any net built from Mithril's core rules. Fire its active pairs in any order you like: one worker or sixteen, the left multiplication before the right one or after it. If one order reaches a final net, every order reaches the same final net, in the same number of steps.
Example. In (2 × 3) + (4 × 5), computing 2 × 3 first or 4 × 5 first both end at 26 after the same number of firings. The proof says this holds for every program, not just this one.
Two consequences. If one order finishes, no order runs forever. And stopping part-way is safe: a half-reduced net, such as the one the compiler leaves when its work budget runs out, still reaches the same final net. Compile-time reduction relies on this property.
How it is checked. A machine-checked proof in Lean 4[9], with no unproved steps and only Lean's standard axioms. Proof and its scope.
Scope. The proof assumes the program finishes. It covers the core rule table: erasing, copying, function application, arithmetic, branch and pattern selection, and calls. Three things sit outside it and are checked by tests: rules the implementation adds (copying a closure, arithmetic that reads an operand through a wire, and unfolding a call whose arguments are still unknown, which compile-time reduction uses); the translation from source to net, which decides whether the net's answer is the source program's answer; and the Rust and CUDA code that implements the rules. The proof says the answer is independent of order; those tests say it is the right answer.
Proof 2 · Splitting a loop into chunks gives the same total
Before the compiler splits a loop like total = total + steps(i) into chunks for different cores, it proves that the combining operation is associative and has an identity. Those two facts are what make summing the chunks and adding the partial sums equal the loop's own answer.
Example. The Collatz sum over 1 to 299,999 is split into ranges. Associativity means (a + b) + c = a + (b + c), so where the ranges are cut does not matter; the identity 0 makes an empty range harmless.
How it is checked. For each such loop the compiler writes Lean theorems for associativity and identity of that operation, and mithril prove has Lean check them. The final step, from those two facts to "independently folded chunks combine to the whole", is standard algebra and is not machine-checked here; the splitting code is checked by tests.
Not covered. Only operations the compiler can prove are split: wrapping integer addition, also elementwise over tuples. Floating-point addition is never split, because rounding depends on grouping. A loop whose operation cannot be proved stays sequential.
Check 3 · The CPU runtime's lock-free handoffs have no races
Workers hand results to each other without locks. For the small functions that do this, every possible interleaving of the threads involved was explored, and in each one a join fires exactly once and sees all its inputs, and a shared value is freed exactly once, after its last reader.
How it is checked. Model checking with loom[10], which runs the code under every thread schedule and memory ordering. It found two ordering bugs, both now fixed. Runtime protocol functions.
Not covered. This covers those protocol functions, not the whole runtime, and not the GPU engine.
Checked by running programs
The compiler, the extra rules and both runtimes are checked by comparing their answers with an independent reference interpreter that evaluates the source directly.
- Compiled code gives the interpreter's answer. Every test program runs at 1, 4 and 16 threads and with tiny work budgets that force pausing, on CPU and GPU. Parity checks.
- Compile-time reduction keeps the meaning. Each test program is evaluated before and after the compiler's reduction, and the answers must match. Specializer tests.
- The extra rules also agree in any order. 10,000 randomly generated programs, each reduced in five different orders using the production rules, all match the interpreter. Schedule test.
The GPU engine implements its rules separately from the CPU rule source, and these tests hold the two together. The verification notes list each property that is checked only by tests and not yet proved.
10Future work
The problems below are not specific to Mithril: any system that runs interaction nets has to solve them to scale. Mithril is built to make them measurable, so every change is run against a sequential C program, the reference interpreter and every backend.
Auto-vectorization of independent work
Mithril's CPU code is scalar (baseline x86-64 with no AVX or FMA, and arm64 on macOS), and independent calls such as neighbouring pixels run as separate scalar tasks. Yet the net has already proved those calls independent, which is the fact an ordinary vectorizer works hardest to establish. The next step is to group tasks that run the same function on different inputs into SIMD lanes. The same grouping matters on the GPU, where 32 lanes of a warp execute in lockstep: profiles show that on irregular programs most warp instructions run with only a few of their 32 lanes active, while regular ones such as bitonic sort fill far more.
Per-lane efficiency
On one thread Mithril still trails sequential C on most programs, so it needs several cores to pass it[7]. Closing that gap is a lowering problem: native code should use representations chosen from types instead of mirroring the net's cells, through general rules rather than per-program tuning.
One rule source for every device
The GPU engine's rules are a second implementation, held equal to the CPU's by tests. Generating both from one table, and linking that table to the Lean model, would turn a checked property into a constructed one. The Lean proof itself is still to be extended to Mithril's extended rules.
Machine-learning workloads
The planned probe is a mixture-of-experts router[17,18]: top-2 gating with capacity overflow over hashed logits, checked against a C twin on CPU and GPU, whose output is a dispatch plan of index buffers. Beyond it lies a division of labour with dense-kernel compilers, in which Mithril decides the irregular structure of a computation and the kernel compiler runs its dense math. Collective-communication algorithms as executable specifications and compiler passes as rule tables follow the same path.
Scaling the substrate
GPU startup spends tens of milliseconds creating a context, and rounds of global synchronization still serialize the device scheduler. Beyond one device, distributing a net across several GPUs or machines is an open research question; confluence says the answer will not change, and the work is to make it fast.
11Try it
Start with a computation you can check: render the tracer on one thread, sixteen threads and the GPU, and compare the images.
git clone https://github.com/maderix/mithril && cd mithril
# Drop --features gpu for a CPU-only build.
cargo build --release -p mithril-cli --features gpu
target/release/mithril run demos/cornell_whitted.py --threads 1 --image one.ppm
target/release/mithril run demos/cornell_whitted.py --threads 16 --image many.ppm
target/release/mithril run demos/cornell_whitted.py --gpu --image gpu.ppm
cmp one.ppm many.ppm && cmp one.ppm gpu.ppm
# On macOS, run the GPU lane with Metal instead:
target/release/mithril run demos/cornell_whitted.py --threads 10 --metal --image gpu.ppm
The build instructions cover the GPU requirements. The generality corpus has interpreters, persistent maps and closures to read, and the design notes record every mechanism and open obligation.
12References
- Y. Lafont. Interaction nets. Proc. 17th ACM Symposium on Principles of Programming Languages (POPL), 95–108, 1990. doi.org/10.1145/96709.96718
- J.-Y. Girard. Linear logic. Theoretical Computer Science 50(1):1–101, 1987. doi.org/10.1016/0304-3975(87)90045-4
- Y. Lafont. Interaction combinators. Information and Computation 137(1):69–101, 1997. doi.org/10.1006/inco.1997.2643
- V. Taelin and HigherOrder Co. HVM: a massively parallel evaluator for interaction combinators. github.com/HigherOrderCO/HVM
- HigherOrder Co. Bend: a massively parallel, high-level programming language (Bend 1, on HVM2). github.com/HigherOrderCO/Bend1
- HigherOrder Co. Bend 2. github.com/HigherOrderCO/bend
- F. McSherry, M. Isard and D. G. Murray. Scalability! But at what COST? 15th Workshop on Hot Topics in Operating Systems (HotOS), 2015. www.usenix.org/conference/hotos15/workshop-program/presentation/mcsherry
- N. D. Jones, C. K. Gomard and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice Hall, 1993.
- L. de Moura and S. Ullrich. The Lean 4 theorem prover and programming language. 28th International Conference on Automated Deduction (CADE), 2021. lean-lang.org
- Tokio project. loom: concurrency permutation testing for Rust. github.com/tokio-rs/loom
- T. Whitted. An improved illumination model for shaded display. Communications of the ACM 23(6):343–349, 1980.
- J. T. Kajiya. The rendering equation. Proc. SIGGRAPH, 143–150, 1986.
- J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM 18(9):509–517, 1975.
- S. Marlow, P. Maier, H.-W. Loidl, M. K. Aswad and P. Trinder. Seq no more: better strategies for parallel Haskell. Proc. Haskell Symposium, 2010. hackage-content.haskell.org/package/parallel-3.3.0.0/docs/Control-Parallel-Strategies.html
- K. C. Sivaramakrishnan, S. Dolan, L. White, T. Kelly, S. Jaffer and A. Madhavapeddy. Retrofitting parallelism onto OCaml. Proc. ACM on Programming Languages 4 (ICFP), 2020. ocaml.org/manual/5.5/parallelism.html
- NVIDIA. CUDA C++ Programming Guide: writing CUDA kernels. docs.nvidia.com/cuda/cuda-programming-guide/02-basics/writing-cuda-kernels.html
- N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. Le, G. Hinton and J. Dean. Outrageously large neural networks: the sparsely-gated mixture-of-experts layer. ICLR, 2017. arxiv.org/abs/1701.06538
- W. Fedus, B. Zoph and N. Shazeer. Switch Transformers: scaling to trillion parameter models with simple and efficient sparsity. Journal of Machine Learning Research 23(120):1–39, 2022. arxiv.org/abs/2101.03961
- P. Patarasuk and X. Yuan. Bandwidth optimal all-reduce algorithms for clusters of workstations. Journal of Parallel and Distributed Computing 69(2):117–124, 2009.