dew.algebra
Dew’s algebraic rewrite of its own programs (docs/design/algebra.md): a jaxpr held as an e-graph of terms
(terms), rules applied in named sets (rules), and each value’s cheapest form under a device’s prices
(cost) evaluated in place of the program’s (program.rewritten).
Every outer program and the resident training step jit their function rewritten (rewritten, §6.7), under
the switch the gate opens per arm (passes); each rewrite joins the one kernel report
(dew.nn.kernels.templates.report.rewrites). Its saturation stops at SATURATION’s limits (§6.6).
Its derivation of a template’s walk forms from its declaration (derive: a Reduction to its Derived
init, step, merge, finish and mapped outputs) and of a recurrence’s chunk forms and adjoint from its token
update (scan), each shared piece in forms.
| Name | Summary |
|---|---|
SATURATION | The limits the engine runs at (§6.6), above every compile-time fixpoint measured: none of the 756 windows of a UNet’s fsdp2 x tensor2 matrix cell and benchmark_step’s cpu-smoke steps reached either, the largest using under a quarter of each, and none gained at four times both (row 4010). |
AlgebraReport | What one region’s rewrite did: the equations it read, the sets admitted and the matches each fired, its limits, its iterations and nodes, whether a limit stopped it, the region’s price before and after in seconds (cost.model), the seconds this program’s rewrite of it took, the roots whose cheaper form the program took (spliced, _splices: a picked form that does not land, a value another window’s form made or a form of another type, is none), and whether an earlier window of its structure derived its forms (reused, _derived: its seconds a lookup’s). |
Derived | A declaration’s forms (derive): init(shapes) the empty state for operands of shapes (by name, their walked axis a tile’s), step(state, tiles) the state after one tile of each walked operand (and the whole of each other), merge(a, b, operands) two states of disjoint walks joined (its unwalked operands whole beside them), finish(state, operands) the declaration’s outputs that the walk reduces, mapped(tiles) its outputs along the walked axis, a tile’s own (each reads no walked reduction: a backward’s dQ, walking queries), each form None in the other’s outputs’ places; report what the derivation decoupled and its rounding class; prepare(tiles) a tile’s values that read no state, which a walk computes for every tile at once (a reduction’s tiles as they are). |
Reduction | A walk whose state is monoids’ (attention): function(**operands) on whole operands in plain JAX, each operand’s axes by name (operands), the axis the kernel walks in tiles (walked), and the exponent’s base the template takes (exponent: 2 where it folds log2(e) into its logits, "e" otherwise), which the derivation keeps; ranges bounds operands’ magnitudes by name, the range facts a reordering’s new intermediates are held under (docs/design/algebra.md §6.3), an operand it names none of unbounded. |
Refused | A declaration the derivation cannot express as monoids along its walked axis, and why. |
Rewrite | A region’s terms (terms.region), each root’s cheapest form by its key (terms.key; picked, empty where none is cheaper than the region as traced), and the report of the rewrite that chose them. |
Saturation | The limits a region’s saturation stops at, from its size (limits): nodes at growth per equation, iterations at depth per level of its longest chain of the language’s equations. |
Scan | A recurrence over its walked axis (time): update(h, **token) the state after one token, readout(h, **token) that token’s output from the state after it, each in plain JAX on one token’s operands (operands’ axes by name, the walked one dropped), the state of state’s shape and dtype. |
cost | The price of a form (docs/design/algebra.md §6.5): each term’s work in the one cost vocabulary (templates.cost.Work, work), from its operands’ shapes (rules.shape) and its parameters, turned into seconds by a schedule over a GPU target’s facts (generation.GpuTarget, their one owner): XLA’s fusion for the compile-time pass over a program (fused), or a template’s tile walk for a form a template’s algebra takes (walk). |
derive | declaration’s monoid forms along its walked axis (the module’s account), saturated beside the engine’s sets accurate admits under saturation’s limits, each tile shape’s rewrite in the kernel report (report.rewrites); refused (Refused) where a form keeps a reading no rule rewrites. |
error | Error-aware extraction (docs/design/algebra.md §1.5), at dev time: a function’s equal forms the e-graph holds under every rule set, the stable ones among them (rules.admitted(dev=True)), proposed as candidates (the form as written, the cheapest by time, the one the stable proposal prices cheapest), each admitted by the accuracy gate its caller holds (admits, check 1 over its draws, the one owner of the policy), and the cheapest admitted chosen. |
forms | What every derivation shares (derive, scan, carry): the forms a declaration derives (Derived), those forms with their math rewritten by the engine (rewritten), its refusal (Refused), the reading of a declaration’s jaxpr (what a value reads, an equation’s evaluation, a value’s array type), a declaration traced with Dew’s products as one each (inlined), an extracted form’s value (evaluated, evaluator), and the one switch the templates take their derived forms behind (derived). |
passes | Within the block, the programs Dew compiles are rewritten (on) or not, priced for the GPU target names (None: the process’s own): a context of JAX’s trace, so a program held across the switch traces afresh (dew._cache.ALGEBRA). |
program | The program pass (docs/design/algebra.md §6.7): a function’s jaxpr held as terms (terms.region), the admitted rule sets run to their fixpoint or the region’s limits, and its roots’ cheapest forms under the cost model extracted together and evaluated in place of the program’s own. |
rewritten | program.rewritten at SATURATION: a function with its program rewritten. |
rewritten_program | program.rewritten_program at SATURATION: a jit’s own trace of a program, rewritten. |
rules | The rules Dew’s rewrite applies (docs/design/algebra.md §6.4), in named sets, and the facts they read (§6.3): each set an egglog ruleset with its rounding class, registered by name. |
scan | A recurrence’s chunk forms derived from its token update (docs/design/algebra.md §6.9, Scan): a state h updated token by token, h = update(h, x_t), read out each token, o_t = readout(h, x_t). |
terms | The term language Dew’s rewrite holds a program in (docs/design/algebra.md §6.2): one egglog sort, Term, a constructor for each kind of equation of the language, and the conversion of a jaxpr’s equations into terms and of an extracted term back into equations. |
SATURATION
Section titled “SATURATION”SATURATION = Saturation(growth=64, depth=4)The limits the engine runs at (§6.6), above every compile-time fixpoint measured: none of the 756 windows of a UNet’s fsdp2 x tensor2 matrix cell and benchmark_step’s cpu-smoke steps reached either, the largest using under a quarter of each, and none gained at four times both (row 4010).
AlgebraReport
Section titled “AlgebraReport”class AlgebraReport( equations: int, admitted: tuple[str, ...], fired: Mapping[str, int], limits: tuple[int, int], iterations: int, nodes: int, limited: bool, before: float, after: float, seconds: float, spliced: int = 0, reused: bool = False,)What one region’s rewrite did: the equations it read, the sets admitted and the matches each fired,
its limits, its iterations and nodes, whether a limit stopped it, the region’s price before and after in
seconds (cost.model), the seconds this program’s rewrite of it took, the roots whose cheaper form the
program took (spliced, _splices: a picked form that does not land, a value another window’s form made
or a form of another type, is none), and whether an earlier window of its structure derived its forms
(reused, _derived: its seconds a lookup’s).
Derived
Section titled “Derived”class Derived(NamedTuple)A declaration’s forms (derive): init(shapes) the empty state for operands of shapes (by name,
their walked axis a tile’s), step(state, tiles) the state after one tile of each walked operand (and the
whole of each other), merge(a, b, operands) two states of disjoint walks joined (its unwalked operands
whole beside them), finish(state, operands) the declaration’s outputs that the walk reduces,
mapped(tiles) its outputs along the walked axis, a tile’s own (each reads no walked reduction: a
backward’s dQ, walking queries), each form None in the other’s outputs’ places; report what the
derivation decoupled and its rounding class; prepare(tiles) a tile’s values that read no state, which a
walk computes for every tile at once (a reduction’s tiles as they are). A scan’s (scan.derive_scan)
step(state, prepared) and mapped(prepared, state) read a chunk’s prepared values and the state alone
(the carry, and a chunk’s outputs from the state entering it); its backward(tiles, state, d_state, d_outputs) is a chunk’s adjoint: the cotangent of the state entering it and of each of its operands, from
the state entering it and the cotangents of the state leaving it and of its outputs (a reduction’s
backward is a declaration of its own, None here). A reduction’s slots(shapes) names each carried state’s
role (max, sum, contraction: the reduction that made it) and shape in the state’s order, so a
template holds each where its mainloop holds that value; its step(state, tiles, product=, stepped=, outputs=) takes a mainloop’s own matrix product (evaluator) and its own step (stepped(states, parts), called once a step with each carried state’s parts in the slots’ order: Accumulated for a sum
a rule stepped as state * factor + weights @ values, Added for one stepped as state * factor + sum(terms), None for any other; it returns each new state it takes, None for one it leaves to the
forms: a mainloop’s accumulator, a compensated walk’s running sums, a guard’s shifted ones), the factor a
row’s, the parts the rules state (derive.rescaled_by, summand), each evaluated once), and with
outputs (places) returns those of the tile’s outputs along the walked axis beside the state, by the
same evaluation; its merge(a, b, operands=None, shapes=, merged=) (a mainloop’s own merge,
merged(firsts, seconds, parts), called once with each state’s Merged factors or None, as stepped)
and finish(state, operands=None, shapes=) read the state (and the unwalked operands given) by the forms
of the walk whose tiles were of shapes (init’s), named, as a state’s values alone name no walk (a
bfloat16 walk’s float32 sums are a float32 walk’s too).
Reduction
Section titled “Reduction”class Reduction( function: Callable, operands: Mapping[str, Axes], walked: str, exponent: Literal[2, 'e'], ranges: Mapping[str, float] = dict(), exact: bool = False, exponential: Callable[..., jax.Array] | None = None, rescale: Callable[[jax.Array, jax.Array], jax.Array] | None = None,)A walk whose state is monoids’ (attention): function(**operands) on whole operands in plain JAX,
each operand’s axes by name (operands), the axis the kernel walks in tiles (walked), and the
exponent’s base the template takes (exponent: 2 where it folds log2(e) into its logits, "e"
otherwise), which the derivation keeps; ranges bounds operands’ magnitudes by name, the range facts a
reordering’s new intermediates are held under (docs/design/algebra.md §6.3), an operand it names none
of unbounded.
exact: bool-
Whether its forms are extracted exactly (
extract.cheapest): a declaration whose greedy extraction the test suite’s oracle finds dearer than the optimum (dew._cache.Passes.checked). exponential: Callable[..., jax.Array] | None-
The implementation of its exponential (
exponent’s base),exponential(x, scale=1.0),exp(x scale)in the reals, which its walk’s every exponential of that base evaluates by, an exponential of a difference times a literal taking the literal as itsscale(raw logits’,forms._scaled): a numerics choice of the declaration’s (attention’s accurate form’snatural_exp, as exact as the reference’s on every backend), equal to the plain one in the reals; None for JAX’s. rescale: Callable[[jax.Array, jax.Array], jax.Array] | None-
The factor a carried state takes from its anchor
carriedto the walk’s new onenow, the walk’s weights’ exponential of their difference:exp(carried - now)in the reals, orexp((carried - now) c)where the weights areexp((x - b) c)(raw logits,cthe declaration’s literal, which the rescale carries itself: only a declaration that states its rescale walks scaled weights,WALKING_SCALED), which the walk’s rescale evaluates by where given (attention’s accurate form’scarried, its exponent’s rounding compensated); None for the plain exponential of the difference.
Refused
Section titled “Refused”class Refused(ValueError)A declaration the derivation cannot express as monoids along its walked axis, and why.
Rewrite
Section titled “Rewrite”class Rewrite( region: terms.Region, picked: Mapping[Hashable, terms.Term], report: AlgebraReport,)A region’s terms (terms.region), each root’s cheapest form by its key (terms.key; picked, empty
where none is cheaper than the region as traced), and the report of the rewrite that chose them.
Saturation
Section titled “Saturation”class Saturation(growth: int, depth: int)The limits a region’s saturation stops at, from its size (limits): nodes at growth per equation,
iterations at depth per level of its longest chain of the language’s equations.
Saturation.limits
Section titled “Saturation.limits”def limits(region: terms.Region) -> tuple[int, int]The nodes and iterations region may take.
class Scan( update: Callable, readout: Callable, operands: Mapping[str, Axes], walked: str, state: tuple[tuple[int, ...], jnp.dtype], reset: str | None = None, ranges: Mapping[str, float | tuple[float, float]] = dict(),)A recurrence over its walked axis (time): update(h, **token) the state after one token,
readout(h, **token) that token’s output from the state after it, each in plain JAX on one token’s
operands (operands’ axes by name, the walked one dropped), the state of state’s shape and dtype.
reset, where given, names an operand of operands, booleans along the walked axis alone that neither
reads, marking each token a zero state enters (a packed document’s first). ranges bounds operands by
name, a magnitude, each element’s (a sigmoid’s gate 1, keys 1) or an interval (a log decay’s (-inf, 0)),
the range facts a reordering’s new intermediates are held under (docs/design/algebra.md §6.3); an operand
it names none of is unbounded, the state is where it names “state” (a bound on its entering value), and
“overlap” bounds two tokens’ corrections’ overlap, |s_i C_i . B_j|, a vector bound the elementwise ones
do not state (keys of unit norm under a write gate at most b: b, by Cauchy-Schwarz; else the
elementwise bounds’ product times the keys’ count).
Its decays (the exponentials of its update’s exponents) are at most 1: its
exponents are at most zero, as a gated recurrence’s log decays are.
The price of a form (docs/design/algebra.md §6.5): each term’s work in the one cost vocabulary
(templates.cost.Work, work), from its operands’ shapes (rules.shape) and its parameters, turned into
seconds by a schedule over a GPU target’s facts (generation.GpuTarget, their one owner): XLA’s fusion for
the compile-time pass over a program (fused), or a template’s tile walk for a form a template’s algebra
takes (walk). Each shared value is priced once over the extracted DAG (egglog’s DagCostModel, extracted
exactly: dew.algebra.extract).
derive
Section titled “derive”def derive( declaration: Reduction, *, accurate: bool, saturation: program.Saturation,) -> Deriveddeclaration’s monoid forms along its walked axis (the module’s account), saturated beside the
engine’s sets accurate admits under saturation’s limits, each tile shape’s rewrite in the kernel
report (report.rewrites); refused (Refused) where a form keeps a reading no rule rewrites.
Error-aware extraction (docs/design/algebra.md §1.5), at dev time: a function’s equal forms the e-graph
holds under every rule set, the stable ones among them (rules.admitted(dev=True)), proposed as candidates
(the form as written, the cheapest by time, the one the stable proposal prices cheapest), each admitted by the
accuracy gate its caller holds (admits, check 1 over its draws, the one owner of the policy), and the
cheapest admitted chosen. Error is a candidate’s, never an e-class fact: the forms of one class are equal in
the reals and differ in error, which depends on every operand form a candidate reads.
What every derivation shares (derive, scan, carry): the forms a declaration derives (Derived),
those forms with their math rewritten by the engine (rewritten), its refusal (Refused), the reading of a
declaration’s jaxpr (what a value reads, an equation’s evaluation, a value’s array type), a declaration
traced with Dew’s products as one each (inlined), an extracted form’s value (evaluated, evaluator), and
the one switch the templates take their derived forms behind (derived).
passes
Section titled “passes”def passes(on: bool = True, target: str | None = None) -> Iterator[None]Within the block, the programs Dew compiles are rewritten (on) or not, priced for the GPU target
names (None: the process’s own): a context of JAX’s trace, so a program held across the switch traces
afresh (dew._cache.ALGEBRA). The accuracy gate holds it off for a reference arm and the float64
truth.
program
Section titled “program”The program pass (docs/design/algebra.md §6.7): a function’s jaxpr held as terms (terms.region), the
admitted rule sets run to their fixpoint or the region’s limits, and its roots’ cheapest forms under the cost
model extracted together and evaluated in place of the program’s own. The bodies of its nested programs,
scans, loops, conditionals, checkpoints and custom derivatives’ primal calls are rewritten in place, each a
region of its own, and kept bodies, never unrolled. Each rewrite is recorded in the one kernel report
(dew.nn.kernels.templates.report.rewrites).
rewritten
Section titled “rewritten”rewritten = functools.partial(program.rewritten, saturation=SATURATION)program.rewritten at SATURATION: a function with its program rewritten.
rewritten_program
Section titled “rewritten_program”rewritten_program = functools.partial(program.rewritten_program, saturation=SATURATION)program.rewritten_program at SATURATION: a jit’s own trace of a program, rewritten.
The rules Dew’s rewrite applies (docs/design/algebra.md §6.4), in named sets, and the facts they read (§6.3): each set an egglog ruleset with its rounding class, registered by name.
shape(t) is each value’s shape, as the equation that made it states it (terms.region), carried to every
form the rules make: a rule joins or moves values only where their shapes say the result is the program’s.
along(params, axis) holds where a broadcast lays its operand along every axis of its result but axis: a
value it makes is constant along axis, so a sum along that axis may take it out.
A recurrence’s chunk forms derived from its token update (docs/design/algebra.md §6.9, Scan): a state h
updated token by token, h = update(h, x_t), read out each token, o_t = readout(h, x_t).
The derivation reads the update’s and the readout’s jaxprs at one token as an affine map of the state by
rules (linear_scan.parts): a decay D_t = exp(z_t) (or exp2) on the state, a scalar or each row’s own
(a per-key vector); one input B_t (x) u_t free of it; and corrections along the input’s own vector,
reading the decayed state, -s_t B_t (c_t^T D_t h). So h_t = (I - s_t B_t c_t^T) D_t h_{t-1} + B_t u_t^T:
the gated delta rule (a scalar decay, s = beta, B = c = k, u = beta v), Kimi’s delta attention (a
per-key decay), or with no correction Mamba-2’s state space. The readout must contract the
state with a vector q_t along B_t’s axis, plus a part free of it. Over a chunk, with G the decay
exponents’ inclusive prefix (per key), Gamma[i, j, k] = exp(G_ik - G_jk) for j <= i and
gamma = exp(G), the inputs each token’s correction leaves, w, solve the unit lower-triangular system
(the compact WY form, its inverse by doubling, products alone), each overlap a decayed contraction over keys
(a scalar decay’s the keys’ product decayed after it):
(I + diag(s) strictly_lower(sum_k C_ik B_jk Gamma_ijk)) w = U - diag(s) (C * gamma) h_in,o = (Q * gamma) h_in + lower(sum_k Q_ik B_jk Gamma_ijk) w + r,h_out = gamma_last h_in + sum_j (B_j * exp(G_last - G_j)) w_j^T,Mamba-2’s state-space dual where no token corrects (w = U), derived from the token update rather than
written. The prefix is taken compensated (each partial a float and its rounding error, two_sum), and every
difference of two partials from both parts: a plain prefix loses about 1e-6 of a deep decay (ledger 2098). A
chunk’s adjoint (backward) is its forms’ derivative, each exponent’s from the decays whose sums hold it,
summed without one term added and taken away again (_decays_backward). A token a reset marks (Scan.reset,
a packed document’s first) takes the exponent RESET_DECAY in place of its own, so every decay spanning it is
zero and every other its own: the forms, their merge and their adjoint unchanged, the exponent its reset
replaced given no gradient.
Every other update or readout is refused, named.
The term language Dew’s rewrite holds a program in (docs/design/algebra.md §6.2): one egglog sort, Term,
a constructor for each kind of equation of the language, and the conversion of a jaxpr’s equations into terms
and of an extracted term back into equations.
A term names its equation’s primitive and refers to the primitive’s other parameters by an index into the
region’s table of them (Region.params), and a literal to its exact value in the region’s table of literals,
so a rule rewrites the math and keeps each parameter and constant as the program wrote it. Every term made
from an equation states its shape (rules.shape), which rules read before they join or move values.