8.1. Tensors and Graphs
TorchLean starts with shape-indexed tensors and then offers three ways to describe a computation.
GraphSpec.Chain is typed sequential syntax, GraphSpec.DAG adds sharing, and NN.IR.Graph is
the ordinary op-tagged graph used at runtime boundaries. Keeping those representations distinct
makes the claims attached to each one easier to read.
Context α collects the arithmetic, order, constants, natural-number casts, and transcendental
operations needed by scalar-polymorphic model code. It carries no laws.
Lean code for Definition8.1.1●1 definition
Associated Lean declarations
-
Context[complete]
-
Context[complete]
-
classdefined in NN/Spec/Core/Context.leancomplete
class Context (α : Type) : Type
class Context (α : Type) : Type
The full scalar interface required by spec-level tensors and models.
Extends
-
Inhabited α -
One α -
Zero α -
Add α -
Sub α -
Mul α -
Div α -
Neg α -
Pow α α -
Max α -
Min α -
BEq α -
LT α -
LE α -
MathFunctions α -
NatCast α -
RatCast α -
TorchLean.Numeric.QuotientArithmetic α
Methods
default : α
Inherited from-
Inhabited
one : α
Inherited from-
One
zero : α
Inherited from-
Zero
add : α → α → α
Inherited from-
Add
sub : α → α → α
Inherited from-
Sub
mul : α → α → α
Inherited from-
Mul
div : α → α → α
Inherited from-
Div
neg : α → α
Inherited from-
Neg
pow : α → α → α
Inherited from-
Pow
max : α → α → α
Inherited from-
Max
min : α → α → α
Inherited from-
Min
beq : α → α → Bool
Inherited from-
BEq
lt : α → α → Prop
Inherited from-
LT
le : α → α → Prop
Inherited from-
LE
exp : α → α
Inherited from-
FloatLib.Numerics.MathFunctions
tanh : α → α
Inherited from-
FloatLib.Numerics.MathFunctions
cosh : α → α
Inherited from-
FloatLib.Numerics.MathFunctions
sqrt : α → α
Inherited from-
FloatLib.Numerics.MathFunctions
abs : α → α
Inherited from-
FloatLib.Numerics.MathFunctions
log : α → α
Inherited from-
FloatLib.Numerics.MathFunctions
pi : α
Inherited from-
FloatLib.Numerics.MathFunctions
cos : α → α
Inherited from-
FloatLib.Numerics.MathFunctions
sin : α → α
Inherited from-
FloatLib.Numerics.MathFunctions
sinh : α → α
Inherited from-
FloatLib.Numerics.MathFunctions
natCast : ℕ → α
Inherited from-
NatCast
ratCast : ℚ → α
Inherited from-
RatCast
supported : Bool
Inherited from-
TorchLean.Numeric.QuotientArithmetic
depth : ℕ
Inherited from-
TorchLean.Numeric.QuotientArithmetic
addWithFlags : α → α → α × UInt8
Inherited from-
TorchLean.Numeric.QuotientArithmetic
subWithFlags : α → α → α × UInt8
Inherited from-
TorchLean.Numeric.QuotientArithmetic
mulWithFlags : α → α → α × UInt8
Inherited from-
TorchLean.Numeric.QuotientArithmetic
divWithFlags : α → α → α × UInt8
Inherited from-
TorchLean.Numeric.QuotientArithmetic
encode : α → Option (TorchLean.Numeric.QuotientCoefficients (TorchLean.Numeric.QuotientArithmetic.depth α))
Inherited from-
TorchLean.Numeric.QuotientArithmetic
decode : TorchLean.Numeric.QuotientCoefficients (TorchLean.Numeric.QuotientArithmetic.depth α) → Option α
Inherited from-
TorchLean.Numeric.QuotientArithmetic
copyPrimal : α → α → α
Inherited from-
TorchLean.Numeric.QuotientArithmetic
defaultEpsilon : α
Backend-selected safeguard used by default in guarded formulas; not machine epsilon.
decidableGT : DecidableRel fun x1 x2 => x1 > x2
Decision procedure for the scalar type's strict order.
stopGradient? : Option (α → α)
Remove differentiation metadata from a scalar at a `detach` boundary. Ordinary numeric carriers leave this as `none`, so detaching a tensor can reuse its storage. A carrier such as `Dual α` supplies a map that keeps the primal value and clears its tangents. This is needed when a reverse pass runs over dual numbers: cutting the tape edge alone would leave the detached value's forward tangent available to later operations.
-
LawfulContext α records, for a scalar type that also carries a Mathlib linearly ordered field
structure, that the Context dictionary computes the same addition,
multiplication, subtraction, division, negation, order, maximum, minimum, absolute value, and
small numeric constants as the field, and that its epsilon is positive. The instance for ℝ is
proved; transcendental constants and the total power operation stay unconstrained.
This separation lets executable scalar types provide operations without claiming field laws that
rounded arithmetic cannot satisfy. A theorem using LawfulContext can transfer the listed
operations to Mathlib's field structure. It still needs any further hypotheses about logarithms,
exponentials, or powers explicitly; the class does not supply those analytic facts.
Lean code for Definition8.1.2●1 definition
Associated Lean declarations
-
LawfulContext[complete]
-
LawfulContext[complete]
-
classdefined in NN/Spec/Core/Context.leancomplete
class LawfulContext (α : Type) [Context α] [Field α] [LinearOrder α] [IsStrictOrderedRing α] : Prop
class LawfulContext (α : Type) [Context α] [Field α] [LinearOrder α] [IsStrictOrderedRing α] : Prop
Compatibility of a `Context` dictionary with a linearly ordered field structure on the same type. Each field equates a `Context` projection (written with the explicit instance path `Context.to*`) with the corresponding Mathlib operation.
Methods
add_eq : ∀ (x y : α), x + y = x + y
Dictionary addition is ring addition.
mul_eq : ∀ (x y : α), x * y = x * y
Dictionary multiplication is ring multiplication.
sub_eq : ∀ (x y : α), x - y = x - y
Dictionary subtraction is ring subtraction.
div_eq : ∀ (x y : α), x / y = x / y
Dictionary division is field division.
neg_eq : ∀ (x : α), -x = -x
Dictionary negation is ring negation.
zero_eq : Zero.zero = Zero.zero
The dictionary zero is the ring zero.
one_eq : One.one = One.one
The dictionary one is the ring one.
lt_iff : ∀ (x y : α), x < y ↔ x < y
The dictionary strict order is the field order.
le_iff : ∀ (x y : α), x ≤ y ↔ x ≤ y
The dictionary order is the field order.
max_eq : ∀ (x y : α), x ⊔ y = max x y
Dictionary `max` is the lattice maximum.
min_eq : ∀ (x y : α), x ⊓ y = min x y
Dictionary `min` is the lattice minimum.
beq_iff : ∀ (x y : α), (x == y) = true ↔ x = y
Boolean equality decides propositional equality.
natCast_eq : ∀ (n : ℕ), ↑n = ↑n
The natural-number cast is the semiring cast.
ratCast_eq : ∀ (value : ℚ), ↑value = ↑value
The rational-number cast is the field cast.
abs_eq : ∀ (x : α), MathFunctions.abs x = |x|
The dictionary absolute value is the lattice absolute value.
defaultEpsilon_pos : 0 < Context.defaultEpsilon
The backend tolerance is strictly positive.
Spec.Shape is List Nat, the dimensions outermost first, and it indexes TorchLean.Tensor α s,
so tensor dimensions are present in the type. Each value stores one contiguous row-major buffer
with a proof that its length equals the shape's element count. Storage α selects packed
FloatArray storage for Float, ByteArray for UInt8, and ordinary arrays for other scalars.
Proofs observe this same value through coordinate lookup; the storage invariant does not prove
the correctness of native C or CUDA implementations.
Lean code for Definition8.1.3●1 definition
Associated Lean declarations
-
TorchLean.Tensor[complete]
-
TorchLean.Tensor[complete]
-
abbrevdefined in NN/Spec/Core/Tensor/Core.leancomplete
abbrev TorchLean.Tensor (α : Type) (shape : Spec.Shape) [TorchLean.Storage α] : Type
abbrev TorchLean.Tensor (α : Type) (shape : Spec.Shape) [TorchLean.Storage α] : Type
The single tensor representation used by TorchLean proofs and execution. The public shape is `Spec.Shape`, which is the same type as the shape carried by the buffer, so this alias only reorders arguments. The implementation is one certified contiguous row-major buffer selected by `Storage`.
A shape is well formed when every one of its dimensions is positive.
The empty list of dimensions satisfies this condition and describes one scalar coordinate. A shape with a zero axis instead has no elements and fails the condition. This distinction is why positivity of total size is a useful hypothesis for a mean or a normalization denominator.
Lean code for Definition8.1.4●1 definition
Associated Lean declarations
-
Spec.Shape.wellFormed[complete]
-
Spec.Shape.wellFormed[complete]
-
defdefined in NN/Spec/Core/Shape.leancomplete
def Spec.Shape.wellFormed : Spec.Shape → Prop
def Spec.Shape.wellFormed : Spec.Shape → Prop
`well_formed s` means "all dimensions of `s` are positive" (recursively).
CanBroadcastTo s₁ s₂ records when values with shape s₁ can be expanded to shape s₂.
Lean code for Definition8.1.5●1 definition
Associated Lean declarations
-
Spec.Shape.CanBroadcastTo[complete]
-
Spec.Shape.CanBroadcastTo[complete]
-
defdefined in NN/Spec/Core/Shape.leancomplete
def Spec.Shape.CanBroadcastTo : Spec.Shape → Spec.Shape → Prop
def Spec.Shape.CanBroadcastTo : Spec.Shape → Spec.Shape → Prop
`CanBroadcastTo source target` holds when `source` broadcasts to `target` with right-aligned axes: after prepending singleton axes to reach the target rank, every source extent equals the target extent or is one.
A well-formed shape has positive total size.
Lean code for Theorem8.1.6●1 theorem
Associated Lean declarations
-
Spec.Shape.size_pos_of_well_formed[complete]
-
Spec.Shape.size_pos_of_well_formed[complete]
-
theoremdefined in NN/Spec/Core/Shape.leancomplete
theorem Spec.Shape.size_pos_of_well_formed {s : Spec.Shape} : s.wellFormed → 0 < s.size
theorem Spec.Shape.size_pos_of_well_formed {s : Spec.Shape} : s.wellFormed → 0 < s.size
If `s.wellFormed`, then `Spec.Shape.size s > 0`.
The proof recurses over the list of axes and uses positivity of every dimension.
Rebuilding a flattened shape-indexed tensor at its original shape returns that tensor.
Lean code for Theorem8.1.7●1 theorem
Associated Lean declarations
-
theoremdefined in NN/Spec/Core/TensorReductionShape/ShapeChange.leancomplete
theorem TorchLean.Tensor.unflattenSpec_flattenSpec {α : Type} [TorchLean.Storage α] {shape : Spec.Shape} (tensor : TorchLean.Tensor α shape) : TorchLean.Tensor.unflattenSpec shape tensor.flattenSpec = tensor
theorem TorchLean.Tensor.unflattenSpec_flattenSpec {α : Type} [TorchLean.Storage α] {shape : Spec.Shape} (tensor : TorchLean.Tensor α shape) : TorchLean.Tensor.unflattenSpec shape tensor.flattenSpec = tensor
Unflattening a flattened tensor returns the original tensor.
Flattening and rebuilding preserve the same certified row-major scalar sequence; the proof reduces to the inverse laws for the tensor representation's zero-copy reshape.
toEuclidean is a linear equivalence between the real tensor representation at a shape and the
Euclidean space indexed by its coordinates. The NormedAddCommGroup and InnerProductSpace ℝ
instances on real tensors are induced along it, so a real tensor is
a finite-dimensional inner-product space without a second representation.
Coordinates give the connection: each tensor entry becomes the corresponding coordinate of the Euclidean vector, and the inverse reconstructs those entries. The induced norm is therefore about the same values used by tensor operations. Analytic statements can use Mathlib's normed-space API without introducing a separate tensor conversion into every theorem.
Lean code for Definition8.1.8●1 definition
Associated Lean declarations
-
TorchLean.Tensor.toEuclidean[complete]
-
TorchLean.Tensor.toEuclidean[complete]
-
defdefined in NN/Proofs/Tensor/Euclidean.leancomplete
def TorchLean.Tensor.toEuclidean (s : TorchLean.Tensor.Internal.Shape) : TorchLean.Tensor.Internal.Rep ℝ s ≃ₗ[ℝ] EuclideanSpace ℝ (TorchLean.Tensor.Internal.Coord s)
def TorchLean.Tensor.toEuclidean (s : TorchLean.Tensor.Internal.Shape) : TorchLean.Tensor.Internal.Rep ℝ s ≃ₗ[ℝ] EuclideanSpace ℝ (TorchLean.Tensor.Internal.Coord s)
The coordinate view of a real tensor as a point of Euclidean space.
Under the induced structure, the inner product of two real tensors is the sum of their coordinatewise products; the norm lemmas of the tensor library follow from this formula.
Lean code for Theorem8.1.9●1 theorem
Associated Lean declarations
-
TorchLean.Tensor.inner_eq_sum[complete]
-
TorchLean.Tensor.inner_eq_sum[complete]
-
theoremdefined in NN/Proofs/Tensor/Euclidean.leancomplete
theorem TorchLean.Tensor.inner_eq_sum {s : TorchLean.Tensor.Internal.Shape} (x y : TorchLean.Tensor.Internal.Rep ℝ s) : inner ℝ x y = ∑ i, x.get i * y.get i
theorem TorchLean.Tensor.inner_eq_sum {s : TorchLean.Tensor.Internal.Shape} (x y : TorchLean.Tensor.Internal.Rep ℝ s) : inner ℝ x y = ∑ i, x.get i * y.get i
The inner product of two real tensors is the sum of coordinatewise products.
The inner product is transported along toEuclidean, where it
is the Euclidean sum.
Matrix-vector multiplication satisfies the dot-product adjoint identity used by the linear-layer gradient rule for typed tensors over a commutative semiring.
Lean code for Theorem8.1.10●1 theorem
Associated Lean declarations
-
theoremdefined in NN/Proofs/Tensor/Algebra.leancomplete
theorem Proofs.TensorAlgebra.dot_mat_linear_adjoint {α : Type} [TorchLean.Storage α] [CommSemiring α] {inDim outDim : ℕ} (W : TorchLean.Tensor α [outDim, inDim]) (dLdy : TorchLean.Tensor α [outDim]) (dx : TorchLean.Tensor α [inDim]) : Proofs.TensorAlgebra.dot dLdy (Spec.matVecMulSpec W dx) = Proofs.TensorAlgebra.dot (Spec.vecMatMulSpec dLdy W) dx
theorem Proofs.TensorAlgebra.dot_mat_linear_adjoint {α : Type} [TorchLean.Storage α] [CommSemiring α] {inDim outDim : ℕ} (W : TorchLean.Tensor α [outDim, inDim]) (dLdy : TorchLean.Tensor α [outDim]) (dx : TorchLean.Tensor α [inDim]) : Proofs.TensorAlgebra.dot dLdy (Spec.matVecMulSpec W dx) = Proofs.TensorAlgebra.dot (Spec.vecMatMulSpec dLdy W) dx
Matrix-vector and vector-matrix multiplication are adjoint under `dot`.
The proof expands the typed tensor operations into finite sums and rearranges those sums.
For an input perturbation dx and output cotangent dLdy, this moves the linear map from one side
of the dot product to the other. The resulting input cotangent has the input width. The semiring
hypotheses justify rearranging exact sums; this identity alone does not bound rounded reductions.
A sequential GraphSpec records its parameter shapes, input shape, and output shape in its type.
Graphs are built from identity, primitive, and sequential-composition nodes.
Lean code for Definition8.1.11●1 definition
Associated Lean declarations
-
NN.GraphSpec.Chain[complete]
-
NN.GraphSpec.Chain[complete]
-
inductivedefined in NN/GraphSpec/Chain/Syntax.leancomplete
inductive NN.GraphSpec.Chain : List Spec.Shape → Spec.Shape → Spec.Shape → Type 2
inductive NN.GraphSpec.Chain : List Spec.Shape → Spec.Shape → Spec.Shape → Type 2
`Chain ps σ τ` is a sequential model from shape `σ` to shape `τ` whose parameters have shapes `ps`, in order. Composition concatenates parameter ABIs; use `NN.GraphSpec.DAG` when explicit sharing or multi-input nodes are required.
Constructors
NN.GraphSpec.Chain.id (s : Spec.Shape) : NN.GraphSpec.Chain [] s s
Identity chain: passes the input through unchanged and requires no parameters.
NN.GraphSpec.Chain.seq {ps₁ ps₂ : List Spec.Shape} {σ τ υ : Spec.Shape} : NN.GraphSpec.Chain ps₁ σ τ → NN.GraphSpec.Chain ps₂ τ υ → NN.GraphSpec.Chain (ps₁ ++ ps₂) σ υ
Sequential composition. Parameter lists concatenate.
NN.GraphSpec.Chain.prim {ps : List Spec.Shape} {σ τ : Spec.Shape} : NN.GraphSpec.Primitive ps σ τ → NN.GraphSpec.Chain ps σ τ
Embed a single primitive node in a chain.
The pure interpreter evaluates a sequential graph on typed parameter and input tensors using scalar-polymorphic operations.
Lean code for Definition8.1.12●1 definition
Associated Lean declarations
-
NN.GraphSpec.Interp.spec[complete]
-
NN.GraphSpec.Interp.spec[complete]
-
defdefined in NN/GraphSpec/Chain/Semantics.leancomplete
def NN.GraphSpec.Interp.spec {ps : List Spec.Shape} {σ τ : Spec.Shape} (g : NN.GraphSpec.Chain ps σ τ) {α : Type} [TorchLean.Storage α] [Context α] : TorchLean.TensorPack α ps → TorchLean.Tensor α σ → TorchLean.Tensor α τ
def NN.GraphSpec.Interp.spec {ps : List Spec.Shape} {σ τ : Spec.Shape} (g : NN.GraphSpec.Chain ps σ τ) {α : Type} [TorchLean.Storage α] [Context α] : TorchLean.TensorPack α ps → TorchLean.Tensor α σ → TorchLean.Tensor α τ
Pure tensor semantics of a sequential `Chain`.
The runtime translation turns a sequential graph into an execution-polymorphic TorchLean program over the same scalar operations.
Lean code for Definition8.1.13●1 definition
Associated Lean declarations
-
NN.GraphSpec.Chain.toProgram[complete]
-
NN.GraphSpec.Chain.toProgram[complete]
-
defdefined in NN/GraphSpec/Chain/Lowering.leancomplete
def NN.GraphSpec.Chain.toProgram {ps : List Spec.Shape} {σ τ : Spec.Shape} (g : NN.GraphSpec.Chain ps σ τ) {α : Type} [TorchLean.Storage α] [Context α] : Runtime.Autograd.Model.Program α (ps ++ [σ]) τ
def NN.GraphSpec.Chain.toProgram {ps : List Spec.Shape} {σ τ : Spec.Shape} (g : NN.GraphSpec.Chain ps σ τ) {α : Type} [TorchLean.Storage α] [Context α] : Runtime.Autograd.Model.Program α (ps ++ [σ]) τ
Lower a sequential `Chain` to an execution-polymorphic TorchLean program.
A typed DAG model pairs initialized parameters with a term whose environment contains the parameter and input shapes. Terms may name arguments and share intermediate results.
Sharing is represented by a typed reference into that environment. Two later operations can use one previously computed value without copying its defining term. The reference's shape determines which operations may consume it, while the environment records where the value came from.
Lean code for Definition8.1.14●1 definition
Associated Lean declarations
-
NN.GraphSpec.DAG.Model[complete]
-
NN.GraphSpec.DAG.Model[complete]
-
structuredefined in NN/GraphSpec/DAG/Model.leancomplete
structure NN.GraphSpec.DAG.Model (ps ins : List Spec.Shape) (τ : Spec.Shape) : Type 1
structure NN.GraphSpec.DAG.Model (ps ins : List Spec.Shape) (τ : Spec.Shape) : Type 1
A small “model” wrapper around DAG terms. This mirrors the sequential `Chain` surface: - `ps` are parameter tensor shapes (tracked at the type level), - `ins` are the shapes of *non-parameter inputs* (e.g. data tensors), - `τ` is the output shape. The model body is a `Term (ps ++ ins) τ`, i.e. it expects an environment that starts with parameters and then contains the actual inputs.
Fields
initParams : TorchLean.TensorPack Float ps
Initial parameter values, one tensor per shape in `ps`. Shipping the initialization with the model means a `Model` is runnable on its own, with no separate setup step.
body : NN.GraphSpec.DAG.Term (ps ++ ins) τ
The computation itself, as a term over the environment `ps ++ ins`: parameters first, then data inputs. That fixed ordering is what lets `initParams` be typed by `ps` alone.
The DAG interpreter evaluates the model body from typed parameter and input lists under the scalar context.
Lean code for Definition8.1.15●1 definition
Associated Lean declarations
-
NN.GraphSpec.DAG.Model.specFwd[complete]
-
NN.GraphSpec.DAG.Model.specFwd[complete]
-
defdefined in NN/GraphSpec/DAG/Model.leancomplete
def NN.GraphSpec.DAG.Model.specFwd {ps ins : List Spec.Shape} {τ : Spec.Shape} (m : NN.GraphSpec.DAG.Model ps ins τ) {α : Type} [TorchLean.Storage α] [Context α] (params : TorchLean.TensorPack α ps) (xs : TorchLean.TensorPack α ins) : TorchLean.Tensor α τ
def NN.GraphSpec.DAG.Model.specFwd {ps ins : List Spec.Shape} {τ : Spec.Shape} (m : NN.GraphSpec.DAG.Model ps ins τ) {α : Type} [TorchLean.Storage α] [Context α] (params : TorchLean.TensorPack α ps) (xs : TorchLean.TensorPack α ins) : TorchLean.Tensor α τ
Pure forward semantics of a DAG model. We build the full environment `Γ = ps ++ ins` by appending the parameter list and the input list, then evaluate the body using `Term.eval`.
The DAG lowering pass turns the same model body into an execution-polymorphic TorchLean program over the same scalar operations.
Lean code for Definition8.1.16●1 definition
Associated Lean declarations
-
NN.GraphSpec.DAG.Model.toProgram[complete]
-
NN.GraphSpec.DAG.Model.toProgram[complete]
-
defdefined in NN/GraphSpec/DAG/Model.leancomplete
def NN.GraphSpec.DAG.Model.toProgram {ps ins : List Spec.Shape} {τ : Spec.Shape} (m : NN.GraphSpec.DAG.Model ps ins τ) {α : Type} [TorchLean.Storage α] [Context α] : Runtime.Autograd.Model.Program α (ps ++ ins) τ
def NN.GraphSpec.DAG.Model.toProgram {ps ins : List Spec.Shape} {τ : Spec.Shape} (m : NN.GraphSpec.DAG.Model ps ins τ) {α : Type} [TorchLean.Storage α] [Context α] : Runtime.Autograd.Model.Program α (ps ++ ins) τ
Lower a DAG model to an execution-polymorphic TorchLean program. The resulting program expects arguments in the order `ps ++ ins` (parameters first, then inputs), matching the environment discipline used by `specFwd`.
The sequential GraphSpec MLP composes two linear maps with an intervening ReLU. Its type fixes the order and shapes of both weights and biases.
Lean code for Definition8.1.17●1 definition
Associated Lean declarations
-
NN.GraphSpec.Models.mlp[complete]
-
NN.GraphSpec.Models.mlp[complete]
-
defdefined in NN/GraphSpec/Models/Mlp.leancomplete
def NN.GraphSpec.Models.mlp (inputWidth hiddenWidth outputWidth : ℕ) : NN.GraphSpec.Chain [[hiddenWidth, inputWidth], [hiddenWidth], [outputWidth, hiddenWidth], [outputWidth]] [inputWidth] [outputWidth]
def NN.GraphSpec.Models.mlp (inputWidth hiddenWidth outputWidth : ℕ) : NN.GraphSpec.Chain [[hiddenWidth, inputWidth], [hiddenWidth], [outputWidth, hiddenWidth], [outputWidth]] [inputWidth] [outputWidth]
2-layer MLP: `Linear(input, hidden) → ReLU → Linear(hidden, output)`. Notice how the parameter interface is explicit in the type: - the first linear layer contributes tensors `W₁ : Tensor α [hiddenWidth, inputWidth]` and `b₁ : Tensor α [hiddenWidth]`, - the second linear layer contributes tensors `W₂ : Tensor α [outputWidth, hiddenWidth]` and `b₂ : Tensor α [outputWidth]`, - and `ReLU` contributes no parameters. So the overall parameter list is exactly: `[[hiddenWidth, inputWidth], [hiddenWidth], [outputWidth, hiddenWidth], [outputWidth]]`.
Interpreting the GraphSpec MLP gives the same tensor as the hand-written two-layer MLP specification.
Both sides receive the same parameter tensors and input. The result identifies two descriptions of that forward computation; it does not compare separately trained models or establish that an optimizer reaches particular weights. Initialization alignment below addresses the distinct question of how the initial parameter pack is assembled.
Lean code for Theorem8.1.18●1 theorem
Associated Lean declarations
-
theoremdefined in NN/GraphSpec/Models/MlpSpecEquivalence.leancomplete
theorem NN.GraphSpec.Models.mlp_interp_eq_spec_mlp_forward {α : Type} [TorchLean.Storage α] [Context α] {inputWidth hiddenWidth outputWidth : ℕ} (params : TorchLean.TensorPack α (NN.GraphSpec.Models.MLPParams inputWidth hiddenWidth outputWidth)) (x : TorchLean.Tensor α [inputWidth]) : NN.GraphSpec.Interp.spec (NN.GraphSpec.Models.mlp inputWidth hiddenWidth outputWidth) params x = match match params with | TorchLean.TensorPack.cons w1 (TorchLean.TensorPack.cons b1 (TorchLean.TensorPack.cons w2 (TorchLean.TensorPack.cons b2 TorchLean.TensorPack.nil))) => (w1, b1, w2, b2) with | (w1, b1, w2, b2) => have l1 := { weights := w1, bias := b1 }; have l2 := { weights := w2, bias := b2 }; Examples.mlpForward l1 l2 x
theorem NN.GraphSpec.Models.mlp_interp_eq_spec_mlp_forward {α : Type} [TorchLean.Storage α] [Context α] {inputWidth hiddenWidth outputWidth : ℕ} (params : TorchLean.TensorPack α (NN.GraphSpec.Models.MLPParams inputWidth hiddenWidth outputWidth)) (x : TorchLean.Tensor α [inputWidth]) : NN.GraphSpec.Interp.spec (NN.GraphSpec.Models.mlp inputWidth hiddenWidth outputWidth) params x = match match params with | TorchLean.TensorPack.cons w1 (TorchLean.TensorPack.cons b1 (TorchLean.TensorPack.cons w2 (TorchLean.TensorPack.cons b2 TorchLean.TensorPack.nil))) => (w1, b1, w2, b2) with | (w1, b1, w2, b2) => have l1 := { weights := w1, bias := b1 }; have l2 := { weights := w2, bias := b2 }; Examples.mlpForward l1 l2 x
**Theorem (GraphSpec MLP agrees with Spec reference).** Fix widths `inputWidth → hiddenWidth → outputWidth`. Let `params` be the 4-tensor parameter list `(W₁, b₁, W₂, b₂)` and `x` an input vector. Then the GraphSpec interpreter applied to the GraphSpec MLP graph computes exactly the same tensor as the reference `Examples.mlpForward` from `NN.Spec.Models.Mlp`, after interpreting the parameter list as two `LinearSpec`s. Informally, both sides compute the same explicit formula: $$ \begin{aligned} z_1 &= W_1x+b_1,\\ a_1 &= \operatorname{ReLU}(z_1),\\ \mathrm{out} &= W_2a_1+b_2. \end{aligned} $$ where the dot/plus are the `Spec.linearSpec` and `Activation.reluSpec` operations already used by the Spec model.
The proof unpacks the four-tensor parameter list, unfolds the pure interpreter for the MLP, and reduces both sides to the same two linear maps with an intervening ReLU.
Deterministic initialization for the GraphSpec MLP produces the same typed parameter list, in the same order, as the two TorchLean linear-layer initializers.
Lean code for Theorem8.1.19●1 theorem
Associated Lean declarations
-
theoremdefined in NN/GraphSpec/Models/MlpDeterministicInit.leancomplete
theorem NN.GraphSpec.Models.mlp_detInitParams_eq_torchlean_linear_inits (inputWidth hiddenWidth outputWidth : ℕ) : NN.GraphSpec.LowerToDAG.Chain.detInitParams? (NN.GraphSpec.Models.mlp inputWidth hiddenWidth outputWidth) = Except.ok ((Runtime.Autograd.Model.Layers.linear inputWidth hiddenWidth).initState.append (Runtime.Autograd.Model.Layers.linear hiddenWidth outputWidth 1).initState)
theorem NN.GraphSpec.Models.mlp_detInitParams_eq_torchlean_linear_inits (inputWidth hiddenWidth outputWidth : ℕ) : NN.GraphSpec.LowerToDAG.Chain.detInitParams? (NN.GraphSpec.Models.mlp inputWidth hiddenWidth outputWidth) = Except.ok ((Runtime.Autograd.Model.Layers.linear inputWidth hiddenWidth).initState.append (Runtime.Autograd.Model.Layers.linear hiddenWidth outputWidth 1).initState)
Deterministic init for `Models.mlp` is exactly the concatenation of the two TorchLean `Linear` initializers. Seed discipline: - the first linear weight uses occurrence index `0`, - the second linear weight uses occurrence index `1`, - both biases are initialized exactly to zero.
For the two-layer graph, the occurrence-indexed seed calculation
reduces to seeds 0, 1 for the first layer and 2, 3 for the second.
The Boolean structural predicate checks that node identifiers match their array positions, operation arities are valid, and every parent points to an earlier node.
Lean code for Definition8.1.20●1 definition
Associated Lean declarations
-
NN.IR.Graph.wellFormed[complete]
-
NN.IR.Graph.wellFormed[complete]
-
defdefined in NN/IR/Graph.leancomplete
def NN.IR.Graph.wellFormed (g : NN.IR.Graph) : Bool
def NN.IR.Graph.wellFormed (g : NN.IR.Graph) : Bool
Basic well-formedness check used by verifier code paths. This checks: - node ids match array indices (common construction invariant), - each node respects its op arity convention, and - all parent ids are strictly smaller than the node id (topological order). We keep this as a boolean predicate because some passes want a fast “yes/no” filter. If you need a human-facing error, use `checkWellFormed`.
The diagnostic checker enforces the same conditions as the
Boolean structural predicate, but returns the first useful error
message instead of a bare false. The two implementations are kept separate; no equivalence
theorem currently connects them.
Lean code for Definition8.1.21●1 definition
Associated Lean declarations
-
NN.IR.Graph.checkWellFormed[complete]
-
NN.IR.Graph.checkWellFormed[complete]
-
defdefined in NN/IR/Graph.leancomplete
def NN.IR.Graph.checkWellFormed (g : NN.IR.Graph) : Except String Unit
def NN.IR.Graph.checkWellFormed (g : NN.IR.Graph) : Except String Unit
Like `wellFormed`, but returns a helpful error message on failure. This is useful when you want a *clean* user error rather than a silent `false`.
After the structural check, shape validation infers every node's output shape and compares it with the shape stored in the graph.
Lean code for Definition8.1.22●1 definition
Associated Lean declarations
-
NN.IR.Graph.checkShapes[complete]
-
NN.IR.Graph.checkShapes[complete]
-
defdefined in NN/IR/Infer.leancomplete
def NN.IR.Graph.checkShapes (g : NN.IR.Graph) : Except String Unit
def NN.IR.Graph.checkShapes (g : NN.IR.Graph) : Except String Unit
Infer shapes for every node (in topo/id order) and check that `Node.outShape` matches. This is meant as a lowering/backend consistency check and as a clean IR invariant for the docs: well-formed graphs have *self-consistent declared shapes*. `NN.IR.ShapeSoundness` proves that on a graph accepted here the reference semantics computes exactly the declared shapes.
After the structural check, IR denotation evaluates every node into a table of shape-tagged tensor values using scalar-polymorphic operations and the supplied external payload.
Lean code for Definition8.1.23●1 definition
Associated Lean declarations
-
NN.IR.Graph.denoteAll[complete]
-
NN.IR.Graph.denoteAll[complete]
-
defdefined in NN/IR/Semantics.leancomplete
def NN.IR.Graph.denoteAll {α : Type} [TorchLean.Storage α] [Context α] (g : NN.IR.Graph) (payload : NN.IR.Payload α) (input : Spec.SomeTensor α) : Except String (Array (Spec.SomeTensor α))
def NN.IR.Graph.denoteAll {α : Type} [TorchLean.Storage α] [Context α] (g : NN.IR.Graph) (payload : NN.IR.Payload α) (input : Spec.SomeTensor α) : Except String (Array (Spec.SomeTensor α))
Evaluate a graph to a table of node values. This returns an array `vals` of length `g.size` where `vals[i]` is the value of node `i`. We do a structural well-formedness check once up front (ids/arity/topology). For lowering-produced graphs, the boolean `Graph.wellFormed` check is a fast path; if it fails we fall back to the exception-producing `Graph.checkWellFormed` so callers get a readable error message. The evaluator always returns either: - `.ok vals` (all nodes evaluated successfully), or - `.error msg` describing the first failure (malformed IR, missing payload, a local shape error, or a `.log` of a nonpositive entry). `Graph.checkShapes` is not run here: the per-node checks reject the same ill-shaped graphs, and the existing lowering-correctness proofs unfold `denoteAll` with only the structural check in place. `NN.IR.ShapeSoundness.denoteAllRaw_eq_denoteAll` shows that on a `checkShapes`-accepted graph the per-node declared-shape normalization is redundant.
If a graph passes shape validation and denotation succeeds, then every value in the resulting table has exactly the output shape declared by its node. Shape inference and the reference semantics are two matches over the operation kinds; this theorem says they agree.
The two success hypotheses serve different purposes. Shape validation checks the declared graph against its operators; successful denotation supplies the actual value table to which the conclusion applies. The theorem does not turn a passed shape check into a guarantee that evaluation succeeds for every external payload or scalar input.
Lean code for Theorem8.1.24●1 theorem
Associated Lean declarations
-
NN.IR.Graph.checkShapes_sound[complete]
-
NN.IR.Graph.checkShapes_sound[complete]
-
theoremdefined in NN/IR/ShapeSoundness.leancomplete
theorem NN.IR.Graph.checkShapes_sound {α : Type} [TorchLean.Storage α] [Context α] (g : NN.IR.Graph) (payload : NN.IR.Payload α) (input : Spec.SomeTensor α) (vals : Array (Spec.SomeTensor α)) (hShapes : g.checkShapes = Except.ok ()) (hEval : g.denoteAll payload input = Except.ok vals) (i : ℕ) (hi : i < g.nodes.size) (hiv : i < vals.size) : vals[i].shape = g.nodes[i].outShape
theorem NN.IR.Graph.checkShapes_sound {α : Type} [TorchLean.Storage α] [Context α] (g : NN.IR.Graph) (payload : NN.IR.Payload α) (input : Spec.SomeTensor α) (vals : Array (Spec.SomeTensor α)) (hShapes : g.checkShapes = Except.ok ()) (hEval : g.denoteAll payload input = Except.ok vals) (i : ℕ) (hi : i < g.nodes.size) (hiv : i < vals.size) : vals[i].shape = g.nodes[i].outShape
Shape inference is sound for the reference semantics: if `checkShapes` accepts a graph and the graph evaluates, every node value has the shape inference assigned to it, namely the declared one.
One lemma per operator family shows that the raw node evaluator returns the inferred shape when its parents have the inferred shapes. An induction over the node array then runs inference and evaluation in lockstep.
Whenever denotation succeeds, the value table has one entry per node and each entry carries its node's declared shape. This holds without a prior shape check because the evaluator normalizes each result against the declared shape and fails otherwise.
Lean code for Theorem8.1.25●1 theorem
Associated Lean declarations
-
NN.IR.Graph.denoteAll_shape[complete]
-
NN.IR.Graph.denoteAll_shape[complete]
-
theoremdefined in NN/IR/ShapeSoundness.leancomplete
theorem NN.IR.Graph.denoteAll_shape {α : Type} [TorchLean.Storage α] [Context α] (g : NN.IR.Graph) (payload : NN.IR.Payload α) (input : Spec.SomeTensor α) (vals : Array (Spec.SomeTensor α)) (h : g.denoteAll payload input = Except.ok vals) : vals.size = g.nodes.size ∧ ∀ (i : ℕ) (hi : i < g.nodes.size) (hiv : i < vals.size), vals[i].shape = g.nodes[i].outShape
theorem NN.IR.Graph.denoteAll_shape {α : Type} [TorchLean.Storage α] [Context α] (g : NN.IR.Graph) (payload : NN.IR.Payload α) (input : Spec.SomeTensor α) (vals : Array (Spec.SomeTensor α)) (h : g.denoteAll payload input = Except.ok vals) : vals.size = g.nodes.size ∧ ∀ (i : ℕ) (hi : i < g.nodes.size) (hiv : i < vals.size), vals[i].shape = g.nodes[i].outShape
The literal soundness statement: on a well-shaped graph, every evaluated node value has its declared shape. Note that `hShapes` is not needed for the conclusion, because `evalNode` normalizes each value to the declared shape (`denoteAll_shape`); its role is documented by `denoteAllRaw_eq_denoteAll`, which shows that on a `checkShapes`-accepted graph the normalization never changes anything.