Skip to content

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.

NameSummary
SATURATIONThe limits the engine runs at until they are measured (§6.6).
AlgebraReportWhat 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).
DerivedA 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).
ReductionA 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.
RefusedA declaration the derivation cannot express as monoids along its walked axis, and why.
RewriteA 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.
SaturationThe 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.
ScanA 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.
costThe 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).
derivedeclaration’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.
errorError-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.
formsWhat 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).
passesWithin 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).
programThe 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.
program_ofprogram.program_of at SATURATION: a jit’s own trace of a program, rewritten.
rewrittenprogram.rewritten at SATURATION: a function with its program rewritten.
rulesThe 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.
scanA 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).
termsThe 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.

attribute source

SATURATION = Saturation(growth=64, depth=4)

The limits the engine runs at until they are measured (§6.6).

dataclass source

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).

class source

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=, accumulate=, outputs=) takes a mainloop’s own matrix product (evaluator) and its own accumulator for a sum a rule stepped as state * factor + weights @ values (accumulate(state, factor, weights, values), the factor a row’s, the parts the rule states, derive.rescaled_by), 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=) 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).

dataclass source

class Reduction(
function: Callable,
operands: Mapping[str, Axes],
walked: str,
exponent: Literal[2, 'e'],
ranges: Mapping[str, float] = dict(),
exact: bool = False,
)

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).

class source

class Refused(ValueError)

A declaration the derivation cannot express as monoids along its walked axis, and why.

dataclass source

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.

dataclass source

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.

def limits(region: terms.Region) -> tuple[int, int]

The nodes and iterations region may take.

dataclass source

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.

module

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).

function source

def derive(
declaration: Reduction,
*,
accurate: bool,
saturation: program.Saturation,
) -> Derived

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.

module

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.

module

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).

function source

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.

module

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).

attribute source

program_of = functools.partial(program.program_of, saturation=SATURATION)

program.program_of at SATURATION: a jit’s own trace of a program, rewritten.

attribute source

rewritten = functools.partial(program.rewritten, saturation=SATURATION)

program.rewritten at SATURATION: a function with its program rewritten.

module

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.

module

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.

module

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.