Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Primitive Set — ML Architecture Notation
- Version 0.4 — Draft
- ---
- ## Overview
- This notation is a term rewriting system for describing ML architectures. Every
- construct in the language is either an **irreducible primitive** or a
- **composition of primitives** that itself satisfies the definition of a node.
- Primitives are divided into two categories:
- - **Topology primitives** describe the structure of the dataflow graph — how
- nodes are connected. They carry no data and perform no computation. They are
- not nodes. They ARE the graph.
- - **Node primitives** describe irreducible operations that map tensors to
- tensors. Every node in the graph is either a primitive node or a complex
- node (a subgraph that satisfies the node definition).
- Everything else — linear layers, attention, convolution, normalization,
- residual blocks, entire architectures — is a complex node: a subgraph with
- named inputs and a single output, which can be expanded into or collapsed
- from its constituent parts.
- ---
- ## Core Definitions
- ### Tensor
- The unit of data in the graph. A tensor is always either an external input to
- the system or the single output of a node. Every tensor has a shape: an
- ordered list of named dimensions, each with a symbolic or concrete size.
- ### Node
- A node is anything that maps a set of input tensors to a single output tensor.
- This definition is satisfied by two kinds of things:
- - **Primitive nodes** — the 8 irreducible operations defined in this spec.
- They cannot be expanded further.
- - **Complex nodes** — any subgraph that has a defined set of inputs and
- exactly one output. A complex node can always be expanded into its
- constituent subgraph, and any qualifying subgraph can always be collapsed
- into a complex node.
- **Composition is closed.** Nodes compose into nodes. If you connect primitive
- or complex nodes together such that the result has defined inputs and a single
- output, the result is itself a node. This holds at every scale: a two-node
- pipeline is a node, a transformer block is a node, the entire architecture is
- a node.
- **The entire graph is a node.** Any complete architecture description — taking
- external inputs (e.g. token indices) and producing a single output (e.g.
- logits) — satisfies the node definition. It is a complex node composed of
- smaller complex and primitive nodes, all the way down.
- ### Node inputs
- Each input to a node is one of three kinds:
- - **Wired** — the tensor arrives from upstream via a pipe.
- - **Parameter** — a learnable tensor, declared with a name, shape, and
- optional constraints. Two nodes whose inputs reference the same parameter
- name share the same learnable tensor.
- - **Constant** — a fixed, non-learnable tensor (e.g. a mask, positional
- encoding, scalar).
- Parameters and constants are properties of node inputs, not standalone graph
- elements. A `matmul(x, W)` node has one wired input (`x`) and one parameter
- input (`W`). There is no separate "parameter node" in the graph.
- **Consequence: parameterized vs. non-parameterized topologies.** A graph
- composed purely of nodes with only wired inputs describes a fixed computation
- with no learnable state. Marking some node inputs as parameters introduces
- learnable state. The same topology can describe different architectures
- depending on which inputs are parameterized and which are shared.
- ### Router nodes
- A **router node** is any node — primitive or complex — that contains
- conditional dispatch.
- At the primitive level, `router(A, condition)` is the only primitive with two
- output ports. It dispatches its input to one of two destinations based on a
- condition.
- At the complex level: **any complex node that contains a router node is itself
- a router node.** The router property propagates upward through composition. A
- complex node containing a router is mutable — it represents a family of
- possible computations, not a single fixed one. The router property is part of
- the node's interface; you do not need to look inside a node to know whether
- it is mutable.
- ### Fixed vs. mutable topologies
- A graph containing no router nodes (at any level of expansion) is a **fixed
- topology** — a single, deterministic DAG. Data flows along one path.
- A graph containing one or more router nodes is a **mutable topology** — a
- family of concrete topologies. Each router is a branch point: data goes to
- one output port or the other depending on a condition evaluated at runtime.
- The set of all possible resolutions of all router conditions defines the
- complete set of concrete topologies the mutable graph can produce.
- Every form of topological variability in neural networks — dropout,
- train/test branching, early exit, dynamic computation depth, convergence-based
- iteration, stochastic depth — is an instance of routing.
- ### The topology lattice
- A mutable topology is a higher-order graph over topologies.
- Start with any fixed topology (a DAG with no routers). Insert a single router
- node. This creates a mutable topology that can produce multiple fixed
- topologies — one for each resolution of the router's condition. The original
- mutable topology becomes the **root** of a higher-order graph. Each fixed
- topology reachable by resolving the router is a **leaf**. The edges between
- root and leaves are defined by the router's possible resolutions.
- With n binary routers, this structure generalizes to a **lattice**:
- - The **root** has all n routers unresolved. It is maximally mutable.
- - The **leaves** have all n routers resolved. They are fixed DAGs — the
- concrete topologies that actually execute.
- - **Interior nodes** are partially-resolved topologies: some routers resolved,
- others still live. These are themselves mutable topologies over a smaller
- set of routers.
- - Each **edge** is the resolution of exactly one router.
- With n independent binary routers, the lattice is an n-dimensional hypercube
- with 2^n leaves. Coupled routers (where resolving one constrains another)
- collapse dimensions, reducing the leaf count.
- ```
- Example: a graph with 2 binary routers (R1, R2)
- [R1 unresolved, R2 unresolved] ← root (mutable)
- / | \
- [R1=true, R2 unresolved] [R1=false, R2 unresolved] ← partial (still mutable)
- / \ / \
- [R1=T, R2=T] [R1=T, R2=F] [R1=F, R2=T] [R1=F, R2=F] ← leaves (fixed DAGs)
- ```
- This structure provides:
- **Distance.** The distance between two topologies is the number of router
- resolutions that separate them. A training topology and its inference
- counterpart that differ only in dropout routers being resolved are "close."
- **Partial evaluation.** Resolving some routers but not others is descending
- partway through the lattice. "Freeze train/test routers to inference mode but
- leave stochastic depth routers live" picks a specific sublattice.
- **Independence vs. coupling.** Routers whose resolutions do not constrain each
- other are independent — they contribute orthogonal dimensions to the lattice.
- Routers whose resolutions are linked (e.g. all dropout routers resolve the
- same way at inference) are coupled — they collapse into a single effective
- dimension.
- **Rewrite rules target lattice edges.** A rewrite rule that eliminates a
- fixed-count `router(passes < n)` by unrolling into n copies of the loop body
- is a traversal of one edge in the lattice: it resolves that router, descending
- one level. The fully-expanded, router-free DAG at a leaf is the final
- compilation target. Every intermediate level is also a valid representation.
- ---
- ## Rewrite Rules
- There are exactly **two structural rewrite rules**. Both are consequences of
- the definitions above, not arbitrary conventions.
- ### Rule 1: Composition (collapse / expand)
- **Any subgraph with a defined set of inputs and a single output is a node,
- and may be collapsed into one.** The inverse operation — expanding a complex
- node into its subgraph — is equally valid.
- ```
- Collapse:
- [A → B → C] becomes [N] where N is a complex node
- Expand:
- [N] becomes [A → B → C]
- ```
- This is the entire rewrite system. Collapsing is abstraction — hiding
- internal structure behind a name. Expanding is elaboration — revealing the
- internal structure. Every level of expansion is a valid description of the
- same computation.
- A compact description of an architecture is a deeply collapsed graph: most
- structure is hidden inside named complex nodes. A fully expanded description
- is a flat graph of primitive nodes and topology primitives only. Every
- intermediate level is also valid.
- ### Rule 2: Router propagation
- **Any complex node that contains a router node is itself a router node.**
- This is a consequence of the node definition combined with the router
- definition: if a subgraph contains conditional dispatch, the subgraph as a
- whole has conditional behavior. It represents a family of computations, not
- a single fixed one.
- Router propagation means you can determine mutability at any level of
- abstraction without expanding. If a node is labeled as a router, it is
- mutable. If not, it is fixed. This holds regardless of how deeply the node
- is collapsed.
- ```
- If:
- N contains [... → router(cond) → ...]
- Then:
- N is itself a router node.
- ```
- ### Naming conventions
- The two structural rules above are the only rules that follow from the
- definitions. All other "rules" in the system are **naming conventions**:
- agreements that a particular subgraph pattern, when encountered, should be
- called by a recognized name.
- For example:
- - A specific composition of `matmul`, `elementwise(exp)`, `reduce(sum)`, and
- `elementwise(/)` is conventionally called `softmax`.
- - A specific composition of `fork`, `parallel`, `join`, and `elementwise(+)`
- is conventionally called a `residual` connection.
- - A specific composition involving query/key/value projections, scaled dot
- products, and concatenation is conventionally called `multi_head_attention`.
- - A specific repeated composition of attention and feedforward blocks is
- conventionally called a `transformer`.
- These names carry no structural meaning. They are labels that help humans
- read and communicate about architectures. The notation does not require them
- — an unnamed complex node is equally valid. But a standard library of
- conventional names enables interoperability: if two people both call a node
- `softmax`, they can verify that the underlying subgraphs match.
- **The standard library is a separate document.** It defines conventional
- names, their expected subgraph expansions, and any constraints on their use.
- New names are added as the field invents new architectural patterns.
- ---
- ## Topology Primitives
- Topology primitives describe the structure of the dataflow graph. They are not
- nodes. They do not appear in the graph as computational elements. They define
- the edges and the structure.
- ### 1. `pipe(A, B)`
- One output connects to one input.
- ```
- A → B
- ```
- The output of A is consumed as an input of B. All sequential computation is
- built from chains of pipe. A backward pipe (from a node to an earlier node)
- creates a cycle; this is valid only when the cycle passes through a `router`
- node that governs termination.
- ### 2. `fork(A, n)`
- One output is copied to n consumers.
- ```
- ┌→ B
- A → ┤→ C
- └→ D
- ```
- The same tensor is made available at n downstream points. No transformation
- occurs — every consumer receives the same tensor. Fork is always copy.
- Dividing a tensor along a dimension is the `slice` node, not a topology
- operation.
- ### 3. `join(A, B, ..., → Z)`
- Multiple outputs converge at a single node.
- ```
- A → ┐
- B → ┤ → Z
- C → ┘
- ```
- Join asserts that multiple tensors arrive as inputs to the same destination
- node Z. It says nothing about HOW they are combined — that is determined
- entirely by what node Z is (e.g. `elementwise(+)` for a residual,
- `concatenate` for a skip connection).
- Join is pure topology. It has no strategy parameter.
- ### 4. `parallel(A, B, ...)`
- Two or more subgraphs proceed independently with no interaction.
- ```
- A → A'
- B → B'
- ```
- No edges exist between parallel tracks. Parallel is the formal assertion of
- independence. Tracks are ordered — they carry positional identity so that
- downstream join or swap operations can reference them.
- ### 5. `swap(perm)`
- Permute the identity of parallel tracks.
- ```
- (A, B, C) → (C, A, B) given perm = [2, 0, 1]
- ```
- Reorders parallel tracks without transforming any data. Needed when a
- downstream consumer expects inputs in a different order than the upstream
- producer emits them (e.g. routing encoder output to a specific argument
- position in cross-attention).
- ---
- ## Node Primitives
- Node primitives are the irreducible operations that map tensors to tensors.
- Every node in the graph is either one of these, or a complex node composed
- from these. Each node input is wired, parameter, or constant. Each node
- produces exactly one output tensor, except `router`.
- ### Arithmetic
- #### `matmul(A, B)`
- Matrix multiplication with broadcasting rules.
- Inputs: two tensors (any combination of wired / parameter / constant).
- Output: one tensor. Inner dimensions of A and B must match.
- #### `elementwise(fn, A)` or `elementwise(fn, A, B)`
- Apply a function element-wise across tensor(s).
- **`elementwise` is defined by its type signature, not by an enumeration of
- functions.** Any function that satisfies one of these signatures is a valid
- instance:
- - Unary: `fn: Scalar → Scalar`, applied independently to every element.
- `elementwise(fn, A)` produces a tensor of the same shape as A.
- - Binary: `fn: Scalar × Scalar → Scalar`, applied element-wise to
- corresponding elements. `elementwise(fn, A, B)` requires A and B to be
- shape-compatible (with broadcasting). Output shape follows broadcast rules.
- Common instances include `+`, `-`, `*`, `/`, `pow`, `exp`, `log`, `sqrt`,
- `abs`, `neg`, `tanh`, `sigmoid`, `relu`, `max`, `min`. The set is open: any
- scalar function satisfying the type signature is valid.
- Whether a given compiler backend can emit code for a particular `fn` is a
- property of the compiler, not of the notation. An `fn` is either
- **implemented** (the compiler knows how to emit it) or **unimplemented** (the
- notation is valid but compilation fails with a clear error). The implemented
- set grows over time without changing the spec.
- #### `reduce(fn, A, dim)`
- Collapse a tensor along one named dimension.
- **`reduce` is defined by its type signature, not by an enumeration of
- functions.** Any function that satisfies this signature is a valid instance:
- - `fn: Tensor[..., dim, ...] → Tensor[..., ...]` — maps a tensor of n
- dimensions to a tensor of n-1 dimensions by removing exactly the named
- dimension `dim`.
- Common instances include `sum`, `mean`, `max`, `min`, `prod`. The set is
- open, with the same implemented/unimplemented distinction as `elementwise`.
- ### Structural
- #### `reshape(A, shape)`
- Reinterpret the dimensions of a tensor. Total element count is preserved.
- Inputs: one tensor.
- Output: one tensor with new dimension structure.
- #### `transpose(A, dim1, dim2)`
- Swap two named dimensions.
- Inputs: one tensor.
- Output: one tensor with the two dimensions exchanged.
- #### `slice(A, start, end, dim)`
- Extract a contiguous sub-tensor along a named dimension.
- Inputs: one tensor.
- Output: one tensor, smaller along the sliced dimension.
- #### `concatenate(A, B, ..., dim)`
- Join multiple tensors along a named dimension.
- Inputs: two or more tensors. All dimensions must match except `dim`.
- Output: one tensor.
- ### Control Flow
- #### `router(A, condition) → (port_true, port_false)`
- Conditional dispatch. Routes an input tensor to one of two output ports based
- on a condition.
- ```
- ┌─ port_true (condition met)
- A → router ──┤
- └─ port_false (condition not met)
- ```
- Router is unique in two ways:
- 1. **It is the only primitive node with two output ports.** This is dispatch,
- not fan-out. The input tensor goes to one port OR the other — never both
- simultaneously. (Fan-out is `fork`, which copies to all consumers.)
- 2. **It is the sole primitive source of topological mutability.** Its property
- propagates upward: any complex node containing a router is itself a router
- (Rule 2).
- The condition is a **parameter of the router node**, not an input tensor. It
- is a predicate. Common forms:
- - **Iteration count:** `passes < n` — for fixed-count loops. This form is
- eliminable: unroll the loop into n copies of the body piped sequentially,
- removing the router and producing a pure DAG.
- - **Convergence test:** `delta(A_prev, A_curr) < epsilon` — for equilibrium
- models and iterative refinement. This form is irreducible.
- - **Stochastic predicate:** `random() < p` — for dropout, stochastic depth.
- At inference time, typically resolves to a constant, collapsing the mutable
- topology to a fixed one.
- - **Mode flag:** `training == true` — for train/test branching.
- The set of valid condition forms is open, following the same principle as
- `elementwise` and `reduce`: any predicate is valid if it can be evaluated
- when data reaches the router. Whether a compiler can handle a given condition
- is an implementation concern.
- ---
- ## Shape Constraints
- Shape constraints are **derived, not declared**. They emerge from the type
- signatures of node primitives under composition.
- Each node primitive implies constraints on the shapes of its inputs:
- - `matmul(A, B)`: the last dimension of A must equal the second-to-last
- dimension of B.
- - `elementwise(fn, A, B)`: A and B must be shape-compatible under
- broadcasting rules.
- - `reduce(fn, A, dim)`: `dim` must be a named dimension present in A.
- - `reshape(A, shape)`: the product of dimensions in `shape` must equal the
- total element count of A.
- - `concatenate(A, B, ..., dim)`: all inputs must match on every dimension
- except `dim`.
- - `transpose(A, dim1, dim2)`: both dimensions must be present in A.
- - `slice(A, start, end, dim)`: `dim` must be present in A; `start` and `end`
- must be valid indices.
- - `router(A, cond)`: both output ports carry tensors of the same shape as A.
- When nodes are composed via `pipe`, constraints propagate: the output shape of
- the upstream node becomes the input shape of the downstream node, and the
- downstream node's constraints apply.
- A tool that expands complex nodes can check shape constraints at each
- expansion step. No separate constraint sublanguage is needed — the
- constraints ARE the type signatures of the primitives, composed.
- **Symbolic dimensions** (e.g. `d_model`, `heads`, `d_k`) and arithmetic
- relationships between them (e.g. `d_k = d_model / heads`) are properties of
- the naming conventions and complex node definitions, not of the primitive
- layer. At the primitive level, every dimension is either a concrete integer
- or a symbolic name that must be resolved before compilation.
- ---
- ## Primitive Census
- | Category | Primitives | Count |
- | ------------ | -------------------------------------------------------- | ----- |
- | **Topology** | `pipe`, `fork`, `join`, `parallel`, `swap` | 5 |
- | **Nodes** | `matmul`, `elementwise(fn)`, `reduce(fn, dim)`, | 8 |
- | | `reshape`, `transpose`, `slice`, `concatenate`, | |
- | | `router(condition)` | |
- **Total: 13 irreducible primitives.**
- **2 structural rewrite rules** (collapse/expand, router propagation).
- All other rules are naming conventions defined in the standard library.
- Parameters and constants are properties of node inputs.
- Shape constraints are derived from primitive type signatures.
- Topological mutability is introduced solely by `router` and propagates upward.
- ---
- ## Design Principles (summary)
- 1. **Nodes compose into nodes.** Any subgraph with defined inputs and a single
- output is a node. The entire architecture is a node. This closure property
- is the foundation of the rewrite system.
- 2. **Two structural rewrite rules.** Collapse (subgraph → named node) and
- expand (named node → subgraph) are inverses. Router propagation (a node
- containing a router is a router) is the only other structural rule. All
- further rules are naming conventions.
- 3. **Two primitive categories, strict boundary.** Topology primitives define
- edges and structure. Node primitives define computation at vertices.
- Topology primitives never appear as nodes. Nodes never define connectivity.
- 4. **Open function sets.** `elementwise` and `reduce` accept any function
- matching their type signature. The notation's expressiveness is not bounded
- by a fixed function list. Compiler support is a separate, growing concern.
- 5. **Parameters are input properties.** Learnable state is not a graph
- element — it is a declaration on a node's input. This cleanly separates
- topology from parameterization.
- 6. **Router is the sole source of mutability.** Fixed topologies are DAGs
- with no routers. Mutable topologies contain routers. Every form of
- architectural variability (dropout, train/test branching, dynamic depth,
- iteration, stochastic depth) is expressible as routing. The router property
- propagates upward through composition.
- 7. **Mutable topologies form a lattice.** A graph with n routers defines a
- higher-order graph over topologies. The root is the fully-mutable graph.
- Leaves are fully-resolved fixed DAGs. Interior nodes are partially-resolved
- graphs. Edges are single router resolutions. Expansion and partial
- evaluation are navigation through this lattice.
- 8. **Shape constraints are derived.** No constraint sublanguage. Constraints
- emerge from primitive type signatures under composition and are checkable
- at each expansion step.
- 9. **Completeness is empirical.** The claim that these 13 primitives suffice
- is tested by attempting to describe real architectures. If one is found
- that cannot be expressed, a new primitive is needed and this document is
- revised.
Advertisement
Add Comment
Please, Sign In to add comment