Formalizing $\mathsf{einsum}$ with Named Tensor Notation
Yafei Yang, Chung-chieh Shan
cs.PL
Nov 14, 2026 · v1
TL;DR
Mechanizes a named-tensor language's denotational semantics and einsum/expand rewriting rules in Lean 4 using Mathlib's semiring and summation lemmas, with a partial Agda port.
Abstract
Einstein notation ($\mathsf{einsum}$) is a widely adopted tensor operation that has proven useful in areas such as machine learning and quantum computing. But it had no formal semantics until recently, and its properties had no mechanized verification. We formalize the denotational semantics of a language of tensors (multi-dimensional arrays) that supports $\mathsf{einsum}$ and repeated tensors ($\mathsf{expand}$). With this semantics, we verify equational rewriting rules about $\mathsf{einsum}$ and $\mathsf{expand}$ that improve the performance of tensor computation. Whereas typical languages use unnamed tensors, whose shape is a sequence of natural numbers, we found it advantageous for mechanization to use named tensors, whose shape is a finite map from names to natural numbers. To our knowledge, this is the first time that the semantics and rewriting rules of $\mathsf{einsum}$ are mechanized in a proof assistant. Our solution is agnostic to proof assistants; we have implemented it in Lean and partially in Agda.
Problem
Einstein summation (einsum) is widely implemented, but libraries disagree on which expressions are valid. Its semantics and rewriting rules had never been mechanized in a proof assistant.
Approach
The authors define a tensor language with scalars, zero tensors, sums, let-bindings, expand, and einsum. They give an unnamed version on paper and mechanize a named version, in which shapes are finite maps from names to sizes; this avoids bookkeeping for renaming and permuting dimensions. A semantics-preserving translation from unnamed to named tensors is proved. Equational rewriting rules are verified in Lean 4 over an arbitrary semiring using Mathlib, with a partial development in Agda.
Results
The work is described as the first mechanization of einsum semantics and of its rewriting rules, including expand fusion and rules that interchange einsum and expand to improve performance. All theorems are proved in Lean; one theorem (6.2) is not proved in Agda.