Guest User

Untitled

a guest
Oct 30th, 2026
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 22.33 KB | None | 0 0
  1. # Primitive Set — ML Architecture Notation
  2.  
  3. Version 0.4 — Draft
  4.  
  5. ---
  6.  
  7. ## Overview
  8.  
  9. This notation is a term rewriting system for describing ML architectures. Every
  10. construct in the language is either an **irreducible primitive** or a
  11. **composition of primitives** that itself satisfies the definition of a node.
  12.  
  13. Primitives are divided into two categories:
  14.  
  15. - **Topology primitives** describe the structure of the dataflow graph — how
  16. nodes are connected. They carry no data and perform no computation. They are
  17. not nodes. They ARE the graph.
  18. - **Node primitives** describe irreducible operations that map tensors to
  19. tensors. Every node in the graph is either a primitive node or a complex
  20. node (a subgraph that satisfies the node definition).
  21.  
  22. Everything else — linear layers, attention, convolution, normalization,
  23. residual blocks, entire architectures — is a complex node: a subgraph with
  24. named inputs and a single output, which can be expanded into or collapsed
  25. from its constituent parts.
  26.  
  27. ---
  28.  
  29. ## Core Definitions
  30.  
  31. ### Tensor
  32.  
  33. The unit of data in the graph. A tensor is always either an external input to
  34. the system or the single output of a node. Every tensor has a shape: an
  35. ordered list of named dimensions, each with a symbolic or concrete size.
  36.  
  37. ### Node
  38.  
  39. A node is anything that maps a set of input tensors to a single output tensor.
  40.  
  41. This definition is satisfied by two kinds of things:
  42.  
  43. - **Primitive nodes** — the 8 irreducible operations defined in this spec.
  44. They cannot be expanded further.
  45. - **Complex nodes** — any subgraph that has a defined set of inputs and
  46. exactly one output. A complex node can always be expanded into its
  47. constituent subgraph, and any qualifying subgraph can always be collapsed
  48. into a complex node.
  49.  
  50. **Composition is closed.** Nodes compose into nodes. If you connect primitive
  51. or complex nodes together such that the result has defined inputs and a single
  52. output, the result is itself a node. This holds at every scale: a two-node
  53. pipeline is a node, a transformer block is a node, the entire architecture is
  54. a node.
  55.  
  56. **The entire graph is a node.** Any complete architecture description — taking
  57. external inputs (e.g. token indices) and producing a single output (e.g.
  58. logits) — satisfies the node definition. It is a complex node composed of
  59. smaller complex and primitive nodes, all the way down.
  60.  
  61. ### Node inputs
  62.  
  63. Each input to a node is one of three kinds:
  64.  
  65. - **Wired** — the tensor arrives from upstream via a pipe.
  66. - **Parameter** — a learnable tensor, declared with a name, shape, and
  67. optional constraints. Two nodes whose inputs reference the same parameter
  68. name share the same learnable tensor.
  69. - **Constant** — a fixed, non-learnable tensor (e.g. a mask, positional
  70. encoding, scalar).
  71.  
  72. Parameters and constants are properties of node inputs, not standalone graph
  73. elements. A `matmul(x, W)` node has one wired input (`x`) and one parameter
  74. input (`W`). There is no separate "parameter node" in the graph.
  75.  
  76. **Consequence: parameterized vs. non-parameterized topologies.** A graph
  77. composed purely of nodes with only wired inputs describes a fixed computation
  78. with no learnable state. Marking some node inputs as parameters introduces
  79. learnable state. The same topology can describe different architectures
  80. depending on which inputs are parameterized and which are shared.
  81.  
  82. ### Router nodes
  83.  
  84. A **router node** is any node — primitive or complex — that contains
  85. conditional dispatch.
  86.  
  87. At the primitive level, `router(A, condition)` is the only primitive with two
  88. output ports. It dispatches its input to one of two destinations based on a
  89. condition.
  90.  
  91. At the complex level: **any complex node that contains a router node is itself
  92. a router node.** The router property propagates upward through composition. A
  93. complex node containing a router is mutable — it represents a family of
  94. possible computations, not a single fixed one. The router property is part of
  95. the node's interface; you do not need to look inside a node to know whether
  96. it is mutable.
  97.  
  98. ### Fixed vs. mutable topologies
  99.  
  100. A graph containing no router nodes (at any level of expansion) is a **fixed
  101. topology** — a single, deterministic DAG. Data flows along one path.
  102.  
  103. A graph containing one or more router nodes is a **mutable topology** — a
  104. family of concrete topologies. Each router is a branch point: data goes to
  105. one output port or the other depending on a condition evaluated at runtime.
  106. The set of all possible resolutions of all router conditions defines the
  107. complete set of concrete topologies the mutable graph can produce.
  108.  
  109. Every form of topological variability in neural networks — dropout,
  110. train/test branching, early exit, dynamic computation depth, convergence-based
  111. iteration, stochastic depth — is an instance of routing.
  112.  
  113. ### The topology lattice
  114.  
  115. A mutable topology is a higher-order graph over topologies.
  116.  
  117. Start with any fixed topology (a DAG with no routers). Insert a single router
  118. node. This creates a mutable topology that can produce multiple fixed
  119. topologies — one for each resolution of the router's condition. The original
  120. mutable topology becomes the **root** of a higher-order graph. Each fixed
  121. topology reachable by resolving the router is a **leaf**. The edges between
  122. root and leaves are defined by the router's possible resolutions.
  123.  
  124. With n binary routers, this structure generalizes to a **lattice**:
  125.  
  126. - The **root** has all n routers unresolved. It is maximally mutable.
  127. - The **leaves** have all n routers resolved. They are fixed DAGs — the
  128. concrete topologies that actually execute.
  129. - **Interior nodes** are partially-resolved topologies: some routers resolved,
  130. others still live. These are themselves mutable topologies over a smaller
  131. set of routers.
  132. - Each **edge** is the resolution of exactly one router.
  133.  
  134. With n independent binary routers, the lattice is an n-dimensional hypercube
  135. with 2^n leaves. Coupled routers (where resolving one constrains another)
  136. collapse dimensions, reducing the leaf count.
  137.  
  138. ```
  139. Example: a graph with 2 binary routers (R1, R2)
  140.  
  141. [R1 unresolved, R2 unresolved] ← root (mutable)
  142. / | \
  143. [R1=true, R2 unresolved] [R1=false, R2 unresolved] ← partial (still mutable)
  144. / \ / \
  145. [R1=T, R2=T] [R1=T, R2=F] [R1=F, R2=T] [R1=F, R2=F] ← leaves (fixed DAGs)
  146. ```
  147.  
  148. This structure provides:
  149.  
  150. **Distance.** The distance between two topologies is the number of router
  151. resolutions that separate them. A training topology and its inference
  152. counterpart that differ only in dropout routers being resolved are "close."
  153.  
  154. **Partial evaluation.** Resolving some routers but not others is descending
  155. partway through the lattice. "Freeze train/test routers to inference mode but
  156. leave stochastic depth routers live" picks a specific sublattice.
  157.  
  158. **Independence vs. coupling.** Routers whose resolutions do not constrain each
  159. other are independent — they contribute orthogonal dimensions to the lattice.
  160. Routers whose resolutions are linked (e.g. all dropout routers resolve the
  161. same way at inference) are coupled — they collapse into a single effective
  162. dimension.
  163.  
  164. **Rewrite rules target lattice edges.** A rewrite rule that eliminates a
  165. fixed-count `router(passes < n)` by unrolling into n copies of the loop body
  166. is a traversal of one edge in the lattice: it resolves that router, descending
  167. one level. The fully-expanded, router-free DAG at a leaf is the final
  168. compilation target. Every intermediate level is also a valid representation.
  169.  
  170. ---
  171.  
  172. ## Rewrite Rules
  173.  
  174. There are exactly **two structural rewrite rules**. Both are consequences of
  175. the definitions above, not arbitrary conventions.
  176.  
  177. ### Rule 1: Composition (collapse / expand)
  178.  
  179. **Any subgraph with a defined set of inputs and a single output is a node,
  180. and may be collapsed into one.** The inverse operation — expanding a complex
  181. node into its subgraph — is equally valid.
  182.  
  183. ```
  184. Collapse:
  185. [A → B → C] becomes [N] where N is a complex node
  186.  
  187. Expand:
  188. [N] becomes [A → B → C]
  189. ```
  190.  
  191. This is the entire rewrite system. Collapsing is abstraction — hiding
  192. internal structure behind a name. Expanding is elaboration — revealing the
  193. internal structure. Every level of expansion is a valid description of the
  194. same computation.
  195.  
  196. A compact description of an architecture is a deeply collapsed graph: most
  197. structure is hidden inside named complex nodes. A fully expanded description
  198. is a flat graph of primitive nodes and topology primitives only. Every
  199. intermediate level is also valid.
  200.  
  201. ### Rule 2: Router propagation
  202.  
  203. **Any complex node that contains a router node is itself a router node.**
  204.  
  205. This is a consequence of the node definition combined with the router
  206. definition: if a subgraph contains conditional dispatch, the subgraph as a
  207. whole has conditional behavior. It represents a family of computations, not
  208. a single fixed one.
  209.  
  210. Router propagation means you can determine mutability at any level of
  211. abstraction without expanding. If a node is labeled as a router, it is
  212. mutable. If not, it is fixed. This holds regardless of how deeply the node
  213. is collapsed.
  214.  
  215. ```
  216. If:
  217. N contains [... → router(cond) → ...]
  218.  
  219. Then:
  220. N is itself a router node.
  221. ```
  222.  
  223. ### Naming conventions
  224.  
  225. The two structural rules above are the only rules that follow from the
  226. definitions. All other "rules" in the system are **naming conventions**:
  227. agreements that a particular subgraph pattern, when encountered, should be
  228. called by a recognized name.
  229.  
  230. For example:
  231.  
  232. - A specific composition of `matmul`, `elementwise(exp)`, `reduce(sum)`, and
  233. `elementwise(/)` is conventionally called `softmax`.
  234. - A specific composition of `fork`, `parallel`, `join`, and `elementwise(+)`
  235. is conventionally called a `residual` connection.
  236. - A specific composition involving query/key/value projections, scaled dot
  237. products, and concatenation is conventionally called `multi_head_attention`.
  238. - A specific repeated composition of attention and feedforward blocks is
  239. conventionally called a `transformer`.
  240.  
  241. These names carry no structural meaning. They are labels that help humans
  242. read and communicate about architectures. The notation does not require them
  243. — an unnamed complex node is equally valid. But a standard library of
  244. conventional names enables interoperability: if two people both call a node
  245. `softmax`, they can verify that the underlying subgraphs match.
  246.  
  247. **The standard library is a separate document.** It defines conventional
  248. names, their expected subgraph expansions, and any constraints on their use.
  249. New names are added as the field invents new architectural patterns.
  250.  
  251. ---
  252.  
  253. ## Topology Primitives
  254.  
  255. Topology primitives describe the structure of the dataflow graph. They are not
  256. nodes. They do not appear in the graph as computational elements. They define
  257. the edges and the structure.
  258.  
  259. ### 1. `pipe(A, B)`
  260.  
  261. One output connects to one input.
  262.  
  263. ```
  264. A → B
  265. ```
  266.  
  267. The output of A is consumed as an input of B. All sequential computation is
  268. built from chains of pipe. A backward pipe (from a node to an earlier node)
  269. creates a cycle; this is valid only when the cycle passes through a `router`
  270. node that governs termination.
  271.  
  272. ### 2. `fork(A, n)`
  273.  
  274. One output is copied to n consumers.
  275.  
  276. ```
  277. ┌→ B
  278. A → ┤→ C
  279. └→ D
  280. ```
  281.  
  282. The same tensor is made available at n downstream points. No transformation
  283. occurs — every consumer receives the same tensor. Fork is always copy.
  284. Dividing a tensor along a dimension is the `slice` node, not a topology
  285. operation.
  286.  
  287. ### 3. `join(A, B, ..., → Z)`
  288.  
  289. Multiple outputs converge at a single node.
  290.  
  291. ```
  292. A → ┐
  293. B → ┤ → Z
  294. C → ┘
  295. ```
  296.  
  297. Join asserts that multiple tensors arrive as inputs to the same destination
  298. node Z. It says nothing about HOW they are combined — that is determined
  299. entirely by what node Z is (e.g. `elementwise(+)` for a residual,
  300. `concatenate` for a skip connection).
  301.  
  302. Join is pure topology. It has no strategy parameter.
  303.  
  304. ### 4. `parallel(A, B, ...)`
  305.  
  306. Two or more subgraphs proceed independently with no interaction.
  307.  
  308. ```
  309. A → A'
  310. B → B'
  311. ```
  312.  
  313. No edges exist between parallel tracks. Parallel is the formal assertion of
  314. independence. Tracks are ordered — they carry positional identity so that
  315. downstream join or swap operations can reference them.
  316.  
  317. ### 5. `swap(perm)`
  318.  
  319. Permute the identity of parallel tracks.
  320.  
  321. ```
  322. (A, B, C) → (C, A, B) given perm = [2, 0, 1]
  323. ```
  324.  
  325. Reorders parallel tracks without transforming any data. Needed when a
  326. downstream consumer expects inputs in a different order than the upstream
  327. producer emits them (e.g. routing encoder output to a specific argument
  328. position in cross-attention).
  329.  
  330. ---
  331.  
  332. ## Node Primitives
  333.  
  334. Node primitives are the irreducible operations that map tensors to tensors.
  335. Every node in the graph is either one of these, or a complex node composed
  336. from these. Each node input is wired, parameter, or constant. Each node
  337. produces exactly one output tensor, except `router`.
  338.  
  339. ### Arithmetic
  340.  
  341. #### `matmul(A, B)`
  342.  
  343. Matrix multiplication with broadcasting rules.
  344.  
  345. Inputs: two tensors (any combination of wired / parameter / constant).
  346. Output: one tensor. Inner dimensions of A and B must match.
  347.  
  348. #### `elementwise(fn, A)` or `elementwise(fn, A, B)`
  349.  
  350. Apply a function element-wise across tensor(s).
  351.  
  352. **`elementwise` is defined by its type signature, not by an enumeration of
  353. functions.** Any function that satisfies one of these signatures is a valid
  354. instance:
  355.  
  356. - Unary: `fn: Scalar → Scalar`, applied independently to every element.
  357. `elementwise(fn, A)` produces a tensor of the same shape as A.
  358. - Binary: `fn: Scalar × Scalar → Scalar`, applied element-wise to
  359. corresponding elements. `elementwise(fn, A, B)` requires A and B to be
  360. shape-compatible (with broadcasting). Output shape follows broadcast rules.
  361.  
  362. Common instances include `+`, `-`, `*`, `/`, `pow`, `exp`, `log`, `sqrt`,
  363. `abs`, `neg`, `tanh`, `sigmoid`, `relu`, `max`, `min`. The set is open: any
  364. scalar function satisfying the type signature is valid.
  365.  
  366. Whether a given compiler backend can emit code for a particular `fn` is a
  367. property of the compiler, not of the notation. An `fn` is either
  368. **implemented** (the compiler knows how to emit it) or **unimplemented** (the
  369. notation is valid but compilation fails with a clear error). The implemented
  370. set grows over time without changing the spec.
  371.  
  372. #### `reduce(fn, A, dim)`
  373.  
  374. Collapse a tensor along one named dimension.
  375.  
  376. **`reduce` is defined by its type signature, not by an enumeration of
  377. functions.** Any function that satisfies this signature is a valid instance:
  378.  
  379. - `fn: Tensor[..., dim, ...] → Tensor[..., ...]` — maps a tensor of n
  380. dimensions to a tensor of n-1 dimensions by removing exactly the named
  381. dimension `dim`.
  382.  
  383. Common instances include `sum`, `mean`, `max`, `min`, `prod`. The set is
  384. open, with the same implemented/unimplemented distinction as `elementwise`.
  385.  
  386. ### Structural
  387.  
  388. #### `reshape(A, shape)`
  389.  
  390. Reinterpret the dimensions of a tensor. Total element count is preserved.
  391.  
  392. Inputs: one tensor.
  393. Output: one tensor with new dimension structure.
  394.  
  395. #### `transpose(A, dim1, dim2)`
  396.  
  397. Swap two named dimensions.
  398.  
  399. Inputs: one tensor.
  400. Output: one tensor with the two dimensions exchanged.
  401.  
  402. #### `slice(A, start, end, dim)`
  403.  
  404. Extract a contiguous sub-tensor along a named dimension.
  405.  
  406. Inputs: one tensor.
  407. Output: one tensor, smaller along the sliced dimension.
  408.  
  409. #### `concatenate(A, B, ..., dim)`
  410.  
  411. Join multiple tensors along a named dimension.
  412.  
  413. Inputs: two or more tensors. All dimensions must match except `dim`.
  414. Output: one tensor.
  415.  
  416. ### Control Flow
  417.  
  418. #### `router(A, condition) → (port_true, port_false)`
  419.  
  420. Conditional dispatch. Routes an input tensor to one of two output ports based
  421. on a condition.
  422.  
  423. ```
  424. ┌─ port_true (condition met)
  425. A → router ──┤
  426. └─ port_false (condition not met)
  427. ```
  428.  
  429. Router is unique in two ways:
  430.  
  431. 1. **It is the only primitive node with two output ports.** This is dispatch,
  432. not fan-out. The input tensor goes to one port OR the other — never both
  433. simultaneously. (Fan-out is `fork`, which copies to all consumers.)
  434.  
  435. 2. **It is the sole primitive source of topological mutability.** Its property
  436. propagates upward: any complex node containing a router is itself a router
  437. (Rule 2).
  438.  
  439. The condition is a **parameter of the router node**, not an input tensor. It
  440. is a predicate. Common forms:
  441.  
  442. - **Iteration count:** `passes < n` — for fixed-count loops. This form is
  443. eliminable: unroll the loop into n copies of the body piped sequentially,
  444. removing the router and producing a pure DAG.
  445. - **Convergence test:** `delta(A_prev, A_curr) < epsilon` — for equilibrium
  446. models and iterative refinement. This form is irreducible.
  447. - **Stochastic predicate:** `random() < p` — for dropout, stochastic depth.
  448. At inference time, typically resolves to a constant, collapsing the mutable
  449. topology to a fixed one.
  450. - **Mode flag:** `training == true` — for train/test branching.
  451.  
  452. The set of valid condition forms is open, following the same principle as
  453. `elementwise` and `reduce`: any predicate is valid if it can be evaluated
  454. when data reaches the router. Whether a compiler can handle a given condition
  455. is an implementation concern.
  456.  
  457. ---
  458.  
  459. ## Shape Constraints
  460.  
  461. Shape constraints are **derived, not declared**. They emerge from the type
  462. signatures of node primitives under composition.
  463.  
  464. Each node primitive implies constraints on the shapes of its inputs:
  465.  
  466. - `matmul(A, B)`: the last dimension of A must equal the second-to-last
  467. dimension of B.
  468. - `elementwise(fn, A, B)`: A and B must be shape-compatible under
  469. broadcasting rules.
  470. - `reduce(fn, A, dim)`: `dim` must be a named dimension present in A.
  471. - `reshape(A, shape)`: the product of dimensions in `shape` must equal the
  472. total element count of A.
  473. - `concatenate(A, B, ..., dim)`: all inputs must match on every dimension
  474. except `dim`.
  475. - `transpose(A, dim1, dim2)`: both dimensions must be present in A.
  476. - `slice(A, start, end, dim)`: `dim` must be present in A; `start` and `end`
  477. must be valid indices.
  478. - `router(A, cond)`: both output ports carry tensors of the same shape as A.
  479.  
  480. When nodes are composed via `pipe`, constraints propagate: the output shape of
  481. the upstream node becomes the input shape of the downstream node, and the
  482. downstream node's constraints apply.
  483.  
  484. A tool that expands complex nodes can check shape constraints at each
  485. expansion step. No separate constraint sublanguage is needed — the
  486. constraints ARE the type signatures of the primitives, composed.
  487.  
  488. **Symbolic dimensions** (e.g. `d_model`, `heads`, `d_k`) and arithmetic
  489. relationships between them (e.g. `d_k = d_model / heads`) are properties of
  490. the naming conventions and complex node definitions, not of the primitive
  491. layer. At the primitive level, every dimension is either a concrete integer
  492. or a symbolic name that must be resolved before compilation.
  493.  
  494. ---
  495.  
  496. ## Primitive Census
  497.  
  498. | Category | Primitives | Count |
  499. | ------------ | -------------------------------------------------------- | ----- |
  500. | **Topology** | `pipe`, `fork`, `join`, `parallel`, `swap` | 5 |
  501. | **Nodes** | `matmul`, `elementwise(fn)`, `reduce(fn, dim)`, | 8 |
  502. | | `reshape`, `transpose`, `slice`, `concatenate`, | |
  503. | | `router(condition)` | |
  504.  
  505. **Total: 13 irreducible primitives.**
  506.  
  507. **2 structural rewrite rules** (collapse/expand, router propagation).
  508.  
  509. All other rules are naming conventions defined in the standard library.
  510.  
  511. Parameters and constants are properties of node inputs.
  512. Shape constraints are derived from primitive type signatures.
  513. Topological mutability is introduced solely by `router` and propagates upward.
  514.  
  515. ---
  516.  
  517. ## Design Principles (summary)
  518.  
  519. 1. **Nodes compose into nodes.** Any subgraph with defined inputs and a single
  520. output is a node. The entire architecture is a node. This closure property
  521. is the foundation of the rewrite system.
  522.  
  523. 2. **Two structural rewrite rules.** Collapse (subgraph → named node) and
  524. expand (named node → subgraph) are inverses. Router propagation (a node
  525. containing a router is a router) is the only other structural rule. All
  526. further rules are naming conventions.
  527.  
  528. 3. **Two primitive categories, strict boundary.** Topology primitives define
  529. edges and structure. Node primitives define computation at vertices.
  530. Topology primitives never appear as nodes. Nodes never define connectivity.
  531.  
  532. 4. **Open function sets.** `elementwise` and `reduce` accept any function
  533. matching their type signature. The notation's expressiveness is not bounded
  534. by a fixed function list. Compiler support is a separate, growing concern.
  535.  
  536. 5. **Parameters are input properties.** Learnable state is not a graph
  537. element — it is a declaration on a node's input. This cleanly separates
  538. topology from parameterization.
  539.  
  540. 6. **Router is the sole source of mutability.** Fixed topologies are DAGs
  541. with no routers. Mutable topologies contain routers. Every form of
  542. architectural variability (dropout, train/test branching, dynamic depth,
  543. iteration, stochastic depth) is expressible as routing. The router property
  544. propagates upward through composition.
  545.  
  546. 7. **Mutable topologies form a lattice.** A graph with n routers defines a
  547. higher-order graph over topologies. The root is the fully-mutable graph.
  548. Leaves are fully-resolved fixed DAGs. Interior nodes are partially-resolved
  549. graphs. Edges are single router resolutions. Expansion and partial
  550. evaluation are navigation through this lattice.
  551.  
  552. 8. **Shape constraints are derived.** No constraint sublanguage. Constraints
  553. emerge from primitive type signatures under composition and are checkable
  554. at each expansion step.
  555.  
  556. 9. **Completeness is empirical.** The claim that these 13 primitives suffice
  557. is tested by attempting to describe real architectures. If one is found
  558. that cannot be expressed, a new primitive is needed and this document is
  559. revised.
Advertisement
Add Comment
Please, Sign In to add comment