WorksComputer Science
Formalizing with Named Tensor Notation
Abstract
Einstein notation () 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 and repeated tensors (). With this semantics, we verify equational rewriting rules about and 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 are mechanized in a proof assistant. Our solution is agnostic to proof assistants; we have implemented it in Lean and partially in Agda.
Introduction
Originating from physics as a shorthand on paper, Einstein notation has since been implemented in libraries for practical computation and found expanded use in popular domains such as machine learning [2, 17, 24], probabilistic programming [9, 11], and quantum computing [4, 16]. Also known as einsum, it can be thought of as a generalized multiplication that produces a tensor (a multi-dimensional array) from a list of tensors. It is versatile: for instance, it subsumes elementwise, matrix, and vector inner and outer product. Indeed, it can operate on any number of tensors, each with any number of dimensions. These dimensions are named in order to specify which sum-product, indexing, or broadcasting operations to perform [29]. For example, given an input matrix , we can compute the matrix product by specifying einsum() using the names .
Unfortunately, the many implementations of einsum do not agree entirely with each other. For instance, only some implementations allow multiple dimensions of the same input tensor to receive the same name. In PyTorch [2], we can extract the diagonal of a square matrix by writing einsum(), but the same expression causes a runtime error in another library Semiring Einsum [11]. Similarly, only some implementations allow multiple output dimensions with the same name. According to Weng et al. [29], we can make a diagonal matrix from a vector by writing einsum(), but this expression is rejected by many implementations. These inconsistencies arise because library implementers follow an intuitive understanding of what einsum does, but there was no formal definition of what counts as a valid einsum expression.
To address these inconsistencies, researchers recently proposed a formal semantics for einsum [29]. They specify how to treat multiple dimensions with the same name. Furthermore, they use their semantics to prove a couple of rewriting rules for einsum, making it possible for future implementers to optimize einsum computations. But their formalization is not mechanized. Moreover, they do not discuss how einsum interacts with other common tensor operations.
In the present work, we mechanize the syntax and semantics of einsum. In doing so, we face challenges presented by the semantics of tensors and the syntax of names. Traditionally, the dimensions of a tensor are ordered and unnamed. Thus, the shape of a tensor and an index into a tensor are both lists of numbers. To operate on such a tensor, each einsum would introduce arbitrary names and associate them with the ordered dimensions. It is in each einsum—not in each tensor—that names like above are associated with dimensions. In order to specify well-formed einsum expressions, our mechanization would need to track these associations. And because the output dimensions are ordered, it would need to express the permutation of names.
To avoid these complications, we use named tensors [10] instead. The dimensions of a named tensor are unordered, and named independently of any operation. Thus, the shape of a tensor and an index into a tensor are both finite maps from names to numbers. Thanks to this representation, dimension names become intrinsic to tensors, so the syntax of einsum doesn’t need to associate names to dimensions separately. And because dimensions are unordered, names do not need to be permuted: a tensor of shape is as good as a tensor of shape , because these two shapes are simply the same finite map.
Based on this idea, we design a core tensor language with einsum. To show that named tensors are just as expressive as
Authors’ Contact Information: Yafei Yang, [email protected]; Chung-chieh Shan, [email protected], Indiana University, Bloomington, Indiana, USA. unnamed tensors, we translate unnamed tensor expressions to named ones. To study how to optimize einsum when it interacts with other tensor operations, we include another widely implemented operation expand, which repeats the contents of a tensor along new dimensions. We mechanize the semantics of our language and prove rewriting rules about einsum and expand. Our contributions are as follows.
We mechanize a language with named tensors, einsum, and expand, as well as its denotational semantics.
We show how the language we mechanize preserves the expressivity of a language with unnamed tensors.
We prove rewriting rules about einsum and expand.
We identify key definitions and properties needed to mechanize named tensors and their einsum.
We carry out our mechanization in Lean and partially in Agda, demonstrating that our technique is not limited to a specific proof assistant.
In § 2, we give motivating examples of tensor operations. In § 3, we define a language of unnamed tensors and mechanize a language of named tensors. In § 4, we give the denotational semantics and demonstrate that it is preserved by a translation from the unnamed tensor language to the named tensor language. In § 5, we describe the definitions and properties of named shapes and indices that underpin our mechanization. In § 6, we state and prove the rewriting rules about einsum and expand. We conclude with related work in § 7.
Motivating Examples
We give a series of examples to illustrate the tensor operations we mechanize and their interactions. For each example, we write down an equation between the operation and the expected result. If necessary, we write down an intermediate step to explain the operation in the equation.
In our terms, an unnamed tensor is an array whose shape is a list of natural numbers . The length of this list is the rank of the tensor. Each number in the list is the size of a dimension. An index into the tensor is a list of numbers such that . A rank-0 tensor is a scalar. A rank-1 tensor is a vector. A rank-2 tensor is a matrix.
einsum
The einsum operation expresses a wide range of multiplications in linear algebra [8, 29]: inner product of two vectors, outer product of two vectors, matrix product, matrix transposition, Hadamard product, Kronecker product, etc.
This operation takes a list of tensors, specifies a name for each of their dimensions, and picks output dimensions from the specified names. We use the form einsum, where each input pairs an unnamed tensor with a corresponding list of dimension names , and is the list of dimension names corresponding to the output. For example, scaling a vector by 5 can be written as:
Here, the vector has one dimension, which we name . The scalar 5 has no dimension to name.
We can also express the inner product between and by eliminating output dimension names:
Here we use the subscript to mean indexing a tensor by . The dimension is eliminated from the output and thus summed out. If we keep the output dimension instead, we get elementwise multiplication:
The output of einsum cannot introduce new dimensions. For example, the einsum below is invalid, since its output uses a name that doesn’t occur as any input dimension:
If we use as the dimension name of , we get a valid einsum operation:
The dimension name is again eliminated from the output, so elements along this dimension are summed up. In contrast, when we use both and in the output dimensions, we get the outer product of and :
Returning to the opening example, given any matrix , the expression computes a square matrix , of which each element is the sum-of-product . The first dimension of is named both and by the einsum operation, even though itself does not come with dimension names.
expand
The expand operation adds dimensions to a tensor by repeating its contents. It is implemented either by making multiple elements point to the same memory location [2, 17] or by copying existing elements to new memory locations [24].
This operation takes a tensor, specifies a distinct name for each of its dimensions, and adds new dimensions to it. We use the form expand, where is an unnamed tensor, and are the input and output lists of dimension names. For example, a scalar 4 can be expanded to a vector:
The size 2 of the new dimension, indicated by the superscript , is actually part of every dimension name but often elided. A vector can be expanded to a matrix in various ways:
The different results in (8) and (9) show that order matters. The expanded matrix (10) can be further expanded:
We can merge the two nested expands above into one:
Nesting einsum and expand
Let be the result of (6). We can use einsum to combine it with the result of (12):
This result, a tensor of shape , can also be obtained by applying einsum and expand in the opposite order:
The reordering is possible because the einsum in (13) doesn’t need any summation. We say this einsum is summation-free. This swap makes einsum operate on a smaller tensor, which improves the performance of the whole operation.
The general case of einsum computes a sum product. To illustrate this, change the output dimensions in (13) to :
Again let us apply einsum and expand in the opposite order:
The results in (15) and (16) differ by a factor of 2, which is the size of the dimension. We need to make up for the factor to preserve the result when swapping einsum with expand. Based on this idea, we prove the general commutativity rule between einsum and expand.
The Syntax of a Tensor Language
We give the syntax of our tensor language, in two versions. In the first version, expressions denote tensors with unnamed dimensions, as conceived usually in tensor libraries and illustrated in Section 2. In the second version, expressions denote tensors with named dimensions. We mechanize the second version, and we specify the necessary conditions to guarantee well-formedness in a dependently typed proof assistant.
To show the correspondence between the two versions, we give a translation in Section 4.3.
An Unnamed Tensor Language
The syntax of an unnamed tensor language is shown in Figure 1. A tensor expression can be a literal scalar , a zero tensor of a specified shape , a tensor scaled by a natural number, a sum of two tensors, a tensor variable, a binding, an expand, or an einsum. To specify the input and output of expand and einsum, we use index variable sequences, which are lists of index variables. Below we explain each construct in turn.

Figure 1. The syntax of an unnamed tensor language
Constants
3.1.1 Constants. Constant tensors include scalars and zero tensors. We require that a scalar range over a semiring . A scalar always has the shape (). Therefore, the scalar 0 can either be written as a scalar 0 or a zero tensor .
A zero tensor is specified by a shape , a list of natural numbers. All of its elements are 0 in the semiring. A zero tensor can also be expressed by expanding a scalar:
Scaling
3.1.2 Scaling. A scaling expression multiplies each element in by the natural number . Here multiplication means repeated addition, so we can express it by using + repeatedly. We can also express it using einsum and expand:
where is a name that doesn’t occur in .
Addition
3.1.3 Addition. The expression performs semiring addition elementwise. and must have the same shape.
Tensor variables and let
3.1.4 Tensor variables and let. A tensor variable is introduced by a let expression. As explained in Section 4.1, a tensor variable denotes an unnamed tensor, whose shape is a list of natural numbers. To use the variable, we simply name it, but we assume that its shape is correct and known. For example, in a tensor expression , we assume that and have the same shape, which can be looked up from the let expressions where and are bound.
expand
As shown in Section 2.2, an expand expression transforms a tensor to a higher rank by repeating its contents. In the general form , the input index variables in must be distinct, the output index variables in must be distinct, and every index variable occurring in must also occur in .
einsum
As shown in Section 2.1, einsum defines each output element as a sum of products of input elements. To specify which dimensions to sum over and which to multiply together, einsum uses index variables to relate the input tensors’ dimensions to the output tensor’s dimensions.
In the general form , variables in each input variable sequence must be distinct, but one index variable can occur in multiple input index variable sequences. The output index variables in , if any, must be distinct and must each appear at least once among the input sequences. These restrictions rule out the problematic sequence in Section 1.
Index variables
Index variables. An index variable is a name together with an upper bound . It tells expand and einsum which tensor dimensions to operate on. For instance, in from (10), the variable specifies the only dimension of the input tensor to be of size 2 and names it as . The variable specifies where to add the new dimension and its size 3. It is an error to operate on a tensor whose shape does not match the upper bound of the index variable, as in .
The index variable iterates over integers between 0 and . We write for the upper bound .
We write or or for an index variable sequence. We notate concatenation of sequences by juxtaposition: . We define the union sequence to be the concatenation with duplicates removed (leaving the first occurrence of each index variable, say, so ). We write for the number of index variables in . We write for the list of upper bounds of the index variables in .
Index variables in different operations are interpreted in separate scopes. For instance, the nested expand from Eq. (11) can be rewritten as
The underlined is interpreted as a new dimension added to the input of the outer expand, rather than referring to the one without underline from the inner expand.
Thus, when nesting one expand inside another, the index variable sequences for the inner output and the outer input may use different names. In (19) for example, the inner output and the outer input specify the same shape but have different names. For two index variable sequences and , as long as , we can rename index variables between and . This idea is used in Section 4.3 to translate the unnamed tensor language to a named version and eliminate alpha-conversion.
A Named Tensor Language
The syntax of a named tensor language in Lean is shown in Figure 2. In this definition, a TExpr is an inductive type parameterized by a value type and indexed by a Context and an Is. It represents a well-formed tensor whose dimensions are named. We require that be an instance of Semiring.
Vector (PDF)inductive TExpr {S : Type} [Semiring S] :
Context → Is → Type where
| scalar {Γ : Context} : S → TExpr Γ empty
| zero {Γ : Context} (xs : Is) → TExpr Γ xs
| scale {Γ : Context} {xs : Is} :
ℕ → TExpr Γ xs → TExpr Γ xs
| add {Γ : Context} {xs ys : Is} :
TExpr Γ xs → TExpr Γ ys → xs ⊎ ys →
TExpr Γ xs
| let {Γ : Context} {xs : Is} :
(dims : List IVar) → (neq : Unique dims) →
(rhs : TExpr Γ (fromList dims neq) →
body : TExpr Γ (, (dims.map Prod.snd)) xs) →
TExpr Γ xs
| var {Γ : Context} :
(dims : List IVar) → (neq : Unique dims) →
(dims.map Prod.snd ∈ᵘ Γ) →
TExpr Γ (fromList dims neq) →
| expand {Γ : Context} {xs zs : Is} :
TExpr Γ xs → xs ⊆ zs → TExpr Γ zs
| einsum {Γ : Context} {xss : List Is} {zs : Is} :
TExpr Γ xss →
(xssCompat : IssCompat xss) →
zs ⊆ ⋃ xssCompat →
TExpr Γ zsFigure 2. The syntax of a named tensor language
A Context stores the shapes of tensor variables in de Bruijn style. It is defined as the following inductive data type:
inductive Context : Type where
| nil : Context
| snoc : Context → List UpperBound → Context
infixl:55 " ∙ " => Context.snoc
As List UpperBound above indicates, a shape in a Context is a list of unnamed dimension sizes. Here UpperBound is an alias for natural numbers that store a dimension size:
abbrev UpperBound := ℕ
An Is is a finite map that represents the shape of a tensor whose dimensions are named. Therefore, we use named shape to mean an Is for TExpr below. For example, the named shape of (12) in the named tensor language can be written as
We leave the details of Is to Section 5. Because a TExpr is indexed by an Is, we always have the dimension names and sizes for any given tensor. Thus, the type of (12) in the empty Context nil can be written as
TExpr (S := ℕ) nil {w ↦ 3, x ↦ 2, z ↦ 2}
The constructors of TExpr correspond to each case of tensor expressions in Figure 1. We explain the constraints introduced by each constructor below.
Constants
The constructor scalar takes a value of type S. Its named shape is the empty map. The constructor zero simply takes a named shape xs.
Scaling
The constructor scale takes a factor n and a tensor of named shape xs. The result also has shape xs.
Addition
The constructor add takes two tensors, of named shapes xs and ys. Here we require that xs and ys be equivalent, written : for any index variable name x, if x is in xs and has the size up, then x is in ys and also has the size up, and vice versa. For example,
{w ↦ 3, x ↦ 2, z ↦ 2} ≈ {z ↦ 2, x ↦ 2, w ↦ 3}
This definition makes it possible to avoid explicit permutations between different Ises. Since xs and ys are equivalent, we can pick either as the result shape. Here we choose xs.
Tensor variables
The way tensor variables are introduced and used reflects the fact that, whereas a tensor denoted by an expression has named dimensions, a tensor associated with a variable has unnamed dimensions. This distinction is that between R-values and L-values [13].
Tensor variables are introduced by the constructor let. Since tensor variables are encoded with de Bruijn indices, let doesn’t need to take a tensor variable name to bind. Instead, it takes a list of index variables, which are defined as a product of an index variable name and a dimension size:
abbrev IVar := Id × UpperBound
We encode index variable names as Strings:
abbrev Id := String
The next argument neq is a proof that names in dims have no duplicates. We can construct an Is with fromList dims neq, which is the named shape of the right hand side tensor of let. The body of let is a tensor in a larger Context with the named shape xs.
To refer to a tensor variable, we use var, which takes three explicit arguments. First, dims lists the index variables with which to index the tensor. Second, neq requires the names in dims to be unique. Finally, the argument of type dims.map Prod.snd ∈ᵘ Γ specifies which tensor variable to use, and requires the upper bounds in dims to match. The relation specifies the lookup of a de Bruijn-style variable:
inductive CtxMem : List UpperBound → Context →
Type where
| here {Γ : Context} {dims : List UpperBound} :
CtxMem dims (Γ ↝, dims)
| there {Γ : Context} {dims dims' : List UpperBound} :
CtxMem dims Γ → CtxMem dims (Γ ↝, dims')
Note that the index variable names in let and in var can differ, so a tensor variable can be used multiple times with different index variable sequences. For example, suppose M is a matrix introduced by a let whose dims is [("a", 2), ("b", 3)]. Then, to compute by einsum as in Section 1, we can refer to M twice by var, with the dims [("i", 2), ("j", 3)] and [("k", 2), ("j", 3)] respectively.
expand
The constructor expand takes a tensor of named shape xs and returns a tensor of named shape zs. We require that xs be a subset of zs, written : for any index variable name x, if x is in xs and has the size up, then x is in zs and also has the size up. For example,
{x ↦ 2, z ↦ 2} ⊆ {z ↦ 2, x ↦ 2, w ↦ 3}
einsum
The constructor einsum takes a sequence of tensor expressions of named shapes xss and returns a tensor of named shape zs. A sequence of tensor expressions is defined as an inductive data type TExprSeq indexed by a Context and a list of Is:
inductive TExprSeq {S : Type} [Semiring S] :
Context → List Is → Type where
| nil {Γ : Context} : TExprSeq Γ []
| cons {Γ : Context} {xs : Is} {xss : List Is} :
TExpr Γ xs → TExprSeq Γ xss →
TExprSeq Γ (xs :: xss)
We require the Ises in xss to be pairwise compatible. Two Ises xs and ys are compatible, written , if every index variable name x occurs either in xs or ys, or in only one of xs and ys, or in both xs and ys with the same size. So
{x ↦ 2, z ↦ 2} ∼ {z ↦ 2, x ↦ 2, w ↦ 3}
but
{x ↦ 2, z ↦ 2} ≁ {z ↦ 3, x ↦ 2, w ↦ 3}
We also require the result shape zs to be a subset of the union of xss. The union of a list of compatible Ises, written , is defined recursively using the union of two Ises xs and ys, written : for any index variable name x, if x occurs in xs ∪ ys, then x occurs either in xs or ys with the same size, and vice versa. For example,
{x ↦ 2, y ↦ 4, z ↦ 2} ∪ {z ↦ 2, x ↦ 2, w ↦ 3} ≈ {z ↦ 2, y ↦ 4, x ↦ 2, w ↦ 3}
Denotational Semantics
In this section, we give the denotational semantics of the two versions of our tensor language. The semantics of the unnamed version is given in Section 4.1. The semantics of the named version is given in Section 4.2. We give a semantics-preserving translation between the unnamed version and the named version in Section 4.3.
The Semantics of the Unnamed Tensor Language
The denotational semantics of the unnamed tensor language is shown in Figure 3. The denotation of an unnamed tensor expression in an environment is an unnamed tensor. An environment is a function from tensor variable names to unnamed tensors. An unnamed tensor is a function that takes an index and returns a value from the semiring . An index is a list of natural numbers.

Figure 3. The denotations of unnamed tensor expressions
The first four cases of Figure 3 are simple. (21) says that a literal scalar has value . (22) says that a zero tensor has value 0 for any index . (23) says that the denotation of is the denotation of multiplied by . (24) requires that the two tensors have the same shape and adds the elements at the location specified by .
(25) says that we get the denotation of the right hand side of the let expression in , extend with bound to the denotation of , and then get the denotation of in the extended environment. (26) says that we look up a tensor variable in and pass to its tensor value.
To define the denotation of expand and einsum, we first introduce named indices. A named index is a function from some index variables to non-negative integers, such that for each in the domain of . Let be a sequence of index variables, not necessarily distinct. If is a named index whose domain includes , then we write for the index , which can be used to index a tensor of shape . Conversely, if is , then we write for the named index ; here we do require the index variables in to be distinct. We also define the set to consist of all named indices whose domain is .
(27) says, to look up an element of an expanded tensor, we look up the corresponding element of the original tensor, by removing from the index the new dimensions introduced by expand. For instance, the element of at is the element of at .
def denote {S : Type} [Semiring S]
{Γ : Context} {xs : Is}
(t : TExpr (S := S) Γ xs)
(env : Env (S := S) Γ)
(idx : NIndex xs) : S :=
match t with
| .scalar r => r
| .zero => 0
| .scale n t => n * denote t env idx
| .add t₁ t₂ xs_ys =>
(denote t₁ env idx) +
(denote t₂ env (idx →ᵢ xs_ys))
| .let dims neq rhs body =>
let rhsNamed := denote rhs env
let rhsUnnamed idx' :=
rhsNamed (NIndex.fromUnnamed dims neq idx')
denote body (env, rhsUnnamed) idx
| .var dims neq v =>
lookupUnnamed v env
(NIndex.toUnnamed dims neq idx)
| .expand t xs_zs => denote t env (idx ↓ᵢ xs_zs)
| .einsum t xs_zs => sts xsComp zss xs_zs
have zs_disjoint : zs ⟂ (⋃ xssComp \ zs) :=
minusIs_disjoint
have zs_union :
zs ∪ (⋃ xssComp \ zs) ≈ ⋃ xssComp :=
minusIs_union eq_zs_xss
sum (⋃ xssComp \ zs)
(fun idx' =>
denotes ts xssComp
(ISubset_refl (xs := ⋃ xssComp)) env
((⋃ᵢ zs_disjoint id idx') →ᵢ zs_union))
Equation (28) defines the denotation of an einsum expression by iterating over all indices and summing out those index variables that do not appear in the output . (Recall that our syntax requires to be a subset of .) For instance, multiplying two matrices and is denoted by , because (28) amounts to
The Semantics of the Named Tensor Language
The denotational semantics of the named tensor language is shown in Figure 4. In this definition, the function denote is parameterized by a Semiring , a Context , and a named shape xs. It then takes a tensor expression t, an environment env, and a named index idx of type NIndex xs, before returning a value of type S. Therefore, the denotation of a named tensor expression is a named tensor, which is a function that takes a named index and returns a value from the semiring S. We explain the arguments and definition of denote below.
Figure 4. The denotations of named tensor expressions
Environment
The environment env has type Env (S := S) Γ, which depends on the Context Γ. Each unnamed shape dims in Γ calls for an unnamed tensor in env, whose type UnnamedTensor dims we define shortly.
def Env {S : Type} [Semiring S] : Context → Type
| .nil => Unit
| Γ `, dims =>
Env (S := S) Γ × UnnamedTensor (S := S) dims
An UnnamedTensor of unnamed shape dims is a function from an index of type UIndex dims to a value of type S:
abbrev UnnamedTensor {S : Type} [Semiring S]
(dims : List UpperBound) :=
UIndex dims → S
An (unnamed) index, or UIndex, of shape dims is a sequence of natural numbers, each bounded by the corresponding element d of dims:
def UIndex (dims : List UpperBound) : Type :=
match dims with
| [] => Unit
| d :: ds => Fin d × UIndex ds
Named indices
Conceptually, a named index is a finite map from names to numbers that are bounded by a named shape. For example, if xs is the named shape {z ↦ 2, x ↦ 2, w ↦ 3}, then the argument idx : NIndex xs in Figure 4 can be the named index {z ↦ 1, x ↦ 0, w ↦ 2}ᵢ. The type NIndex xs is defined as a structure with a field get. This field is a function that takes an index variable name x and a dimension size u. If get looks up x in xs and finds the value u, it returns a number bounded by u:
structure NIndex (xs : Is) where
get : ∀ {x : Id} {u : UpperBound},
lookup xs x = some u → Fin u
Here, lookup is a function that takes a named shape xs and an index variable name x. It returns an Option UpperBound to indicate if x is found in xs:
def lookup (xs : Is) (x : Id) : Option UpperBound
The definition of denote
The definition of denote in Figure 4 closely follows the definition of ⟦⟧ in Figure 3. The first three cases are simple. A scalar always has the value r. A zero tensor always has the value 0. The denotation of a scaled tensor is the denotation of the tensor multiplied by a natural number.
The denotation of add t₁ t₂ xs_ys at a named index idx depends on the denotations of t₁ and t₂. For t₁, we simply use the index idx, which is of t₁’s shape. For t₂, since its shape is equivalent to t₁’s, we use →ᵢ to convert idx from t₁’s shape to t₂’s shape. Since this conversion is based on the equivalence of two shapes, we do not need to explicitly define permutation between indices.
The key to tensor variable binding and reference is a pair of functions that converts between a named index and an unnamed index, NIndex.fromUnnamed and NIndex.toUnnamed. For example, given an unnamed shape (2, 2, 3) and a corresponding unnamed index (1, 0, 2), if we know the three dimensions are named as z, x, w, then we can get a named index {z ↦ 1, x ↦ 0, w ↦ 2}ᵢ. Similarly, given a named shape {w ↦ 3, x ↦ 2, z ↦ 2} and a named index {w ↦ 2, x ↦ 0, z ↦ 1}ᵢ, if we know the dimension order is (z, x, w), we can construct an unnamed index (1, 0, 2).
The let case first gets the denotation of rhs in env, which is a named tensor rhsNamed. Then it constructs an unnamed tensor rhsUnnamed from rhsNamed by converting an unnamed index idx′ to a named index with NIndex.fromUnnamed. Finally, it evaluates body in env extended with rhsUnnamed.
The var case first invokes lookupUnnamed to retrieve the value stored for v in env, which is an unnamed tensor. Then it converts the given named index idx to unnamed with NIndex.toUnnamed. Finally, it passes the unnamed index to the unnamed tensor.
The expand case uses ↓ᵢ to remove from the named index idx the dimensions that are not in t₁’s shape, then gets the denotation of t₁.
Finally, the einsum case performs summation using a helper function sum, which has the following type:
def sum {S : Type} [Semiring S]
(xs : Is) (f : NIndex xs → S) : S
Given a named shape xs, it enumerates all possible indices of xs and passes them to f, a function that takes a named index of xs and returns a value. Then it sums up all values returned by f together.
In denote, the first argument to sum is the named shape returned by a function ∨, which removes zs from ⋃ xss, the union of all input shapes. The second argument to sum is a function that computes the product of all input tensors, using the helper function denotes, whose type is below:
def denotes {S : Type} [Semiring S]
{Γ : Context} {xss : List Is} {ys : Is}
(ts : TExp Γ (⋃ xss) Γ ys)
(xssCompat : IssCompat xss)
(h : ⋃ xssCompat ⊆ ys)
(env : Env (S := S) Γ) (idx : NIndex ys) : S
The function denotes takes a sequence of tensor expressions ts of named shapes xss, a named index idx of shape ys, and a proof that the union of xss is a subset of ys. When doing recursion on ts, we keep the invariant that the union of xss is a subset of ys. For each tensor in the sequence, it gets the denotation of the tensor at the subset of idx that matches the tensor’s shape. It multiplies the denotations of all tensors together.
On the last line of Figure 4, the index that denote passes to denotes is the union (written ) of idx (whose shape is zs) and idx′ (whose shape is xss zs). Note that these two shapes are disjoint (written ), meaning they share no index variable name. Hence they are compatible, and that is why it makes sense to take the union of the two shapes and of the two indices. Since the shape zs ( xss zs) is equivalent to the shape xss, we can convert idx idx′ from the former shape to the latter. With the proper indices, denotes can find values in each input tensor and complete the multiplication.
Translating from Unnamed to Named
The unnamed tensor language models what tensor libraries implement, but the named tensor language is what we mechanize. It is thus reasonable to ask, as with all language mechanizations, whether our TExpr type faithfully captures the expressivity, complexity, and interaction of tensor operations. To address this question, we translate the unnamed language to the named language. Our translation takes an unnamed tensor expression , say of shape , and also takes a sequence of distinct names . It produces a named tensor expression , of shape dims , such that for any environment and index we have
where env consists of the unnamed tensors in stored in de Bruijn style, and idx = NIndex.fromUnnamed dims neq , where neq is the proof of Unique dims.
Consider how the translation should work on the expression from Section 1. Say that has shape , so has shape , and the given sequence of distinct names (that is, the domain of idx in (30)) is ["x","w"]. We will translate to a TExpr of the form
einsum (cons (var [("x",2), ("y",3)] _ _)
(cons (var [("w",2), ("y",3)] _ _) nil)) _ _
in which the var subexpressions are produced by recursively translating the tensor variable expression at two different sequences of distinct names, ["x","y"] and ["w","y"]. Producing this result requires mapping from to "x", from to "w", as well as from the summed-over to a fresh name "y". Thus, the translation operates on name maps using the helpers create_dict to create mappings, freshen to extend mappings, and rename to apply mappings. In particular,
where we abbreviate the name maps
"y" is a fresh name, and we omit the sizes and uniqueness proofs of dimensions. Fresh names also need to be generated at the top level and for the rhs of each let expression, so we introduce one more helper gendim, which can generate fresh names like ["x",2], ("w",2)] from a shape .
Figure 5 defines the translation more formally. See Appendix A for the definitions of the helper functions shape, gendim, create_dict, freshen, and rename.
Vector (PDF)trans(E) = (dims, comp_T(E, dims))
where dims = gendim(shape_r(E))
comp_T(α, []) = scalar α
comp_T(0^(s_...), dims) = zero (fromList dims _)
comp_T(n · E, dims) = scale n comp_T(E, dims)
comp_T(E₁ + E₂, dims) =
add comp_T(E₁, dims) comp_T(E₂, dims)
comp_T(let t = E′ in E, dims) =
let d′ _ comp_T(E′, d′) comp_T_{t,d′}.map Prod.snd(E, dims)
where d′ = gendim(shape_r(E′))
comp_T(t, dims) = var dims _ Γ(t)
comp_T(expand(E[⃗x] → ⃗z), dims) =
expand comp_T(E, rename(⃗x, dict)) _
where dict = create_dict(⃗z, dims)
comp_T(einsum(E₁[⃗x₁],..., → ⃗z), dims) =
einsum [comp_T(E₁, rename(⃗x₁, dict)),...] _ _
where dict = freshen(⃗x₁ ∪ ···, create_dict(⃗z, dims))Figure 5. The translator from the unnamed tensor language to the named tensor language
The main function trans takes a tensor expression . It first generates a list dims of IVAr corresponding to 's shape. Then it invokes comp to recursively translate . The expand and einsum cases use name maps to consistently replace the names in an index variable sequence with names in dims as described above. We omit the lengthy proofs of Unique and subset relations between Ises.
If we let in (30) be , then we can prove the equation by induction on .
Representing Shapes and Indices
In this section, we give the details of representations of named shapes. We first introduce the representation of named shapes and the operations on them in Section 5.1. Then we introduce the operations on named indices in Section 5.2. Finally we give the properties of these operations in Section 5.3. These properties are key to the proofs in Section 6.
Representing Named Shapes
The definition of Is.
As explained in § 3.2, an Is represents a finite map from index variable names to dimension sizes. It can be encoded in many ways, such as as a function or a data structure [13]. A proper encoding of Is should satisfy the following two requirements. First, we need an Is to have the behavior of a finite map: when we look up any index variable name, there should be only one possible dimension size. Second, since einsum needs to enumerate indices corresponding to those dimensions that occur in the input but not in the output, we should be able to enumerate all the dimensions from a given Is. Based on the two requirements, we define Is as a structure with two fields: an association list pairs of IVar and a proof noDup that index variable names in pairs have no duplicates:
structure Is where
pairs : List IVar
noDup : (pairs.map Prod.fst).Nodup
We also define the lookup operation of Is:
def lookupPairs (pairs : List IVar) (x : Id) :
Option UpperBound :=
(pairs.find? fun dim => dim.1 == x).map Prod.snd
def lookup (xs : Is) (x : Id) : Option UpperBound :=
lookupPairs xs.pairs x
Based on lookup, we can define relations and operations on Is.
Equivalence, subset, compatibility, and disjointness.
Once we define lookup, we can define the equivalence, subset, and compatibility of two Ises:
def IsEq (xs ys : Is) : Prop :=
∀ i , lookup xs i = lookup ys i
notation xs " ≈ " ys => IsEq xs ys
def IsSubset (xs ys : Is) : Prop :=
∀ i , ∀ u , lookup xs i = some u →
lookup ys i = some u
notation xs " ⊑ " ys => IsSubset xs ys
def IsCompat (xs ys : Is) : Prop :=
∀ i, (lookup xs i) ∼ᵢ (lookup ys i)
notation xs " ∼ " ys => IsCompat xs ys
We define the compatibility of Option UpperBound as follows. Two Option UpperBounds are compatible if they are the same or one of them is none:
inductive CompatVal : Option UpperBound →
Option UpperBound → Prop where
| nn : CompatVal none none
| vv (v : UpperBound) : CompatVal (some v) (some v)
| nv (v : UpperBound) : CompatVal none (some v)
| vn (v : UpperBound) : CompatVal (some v) none
notation v₁ " ∼ᵢ " v₂ => CompatVal v₁ v₂
Two Ises are disjoint if no index variable name can be found in both of them:
def disjointIs (xs ys : Is) : Prop := (i : Id) →
(lookup xs i = none) ∨ (lookup ys i = none)
notation xs " ⊥ " ys => disjointIs xs ys
It is easy to see that xs ∼ ys if xs ⊥ ys.
Union, intersection, and difference.
We can define the union ∪, intersection ∩, and difference \ of two Ises. Their type declarations are as follows:
def unionIs (xs ys : Is) (h : xs ∼ ys) : Is
def intersectIs (xs ys : Is) (h : xs ∼ ys) : Is
def minusIs (xs ys : Is) : Is
All three functions can be defined by recursion on xs.pairs, following the usual definitions of union, intersection, and difference. For ∪ and ∩, two Ises should be compatible to avoid the case where one index variable name is associated with two different sizes. For xs \ ys, we simply remove an IVar from xs if its index variable name is found in ys.
Union, intersection, and difference of dimension sizes.
We can also define the union, intersection, and difference of two Option UpperBounds. Their types follow the same pattern of the operations on Is: union and intersection require a proof that their arguments are compatible, while difference does not. The union of v₁ and v₂ is some v if either is some v, or none otherwise. The intersection is some v if both are some v, or none otherwise. The difference is none if v₂ is some v, or v₁ otherwise. We give their types and notations here. These operations make it possible to prove the distributivity of lookup, as can be seen in Theorem 5.4.
def unionVal (v₁ v₂ : Option UpperBound)
(h : v₁ ∼ᵢ v₂) : Option UpperBound
notation v₁ " ⊔ᵤ " v₂ => unionVal v₁ v₂
def intersectVal (v₁ v₂ : Option UpperBound)
(h : v₁ ∼ᵢ v₂) : Option UpperBound
notation v₁ " ⊓ᵤ " v₂ => intersectVal v₁ v₂
def minusVal (v₁ v₂ : Option UpperBound) :
Option UpperBound
notation v₁ " \ᵤ " v₂ => minusVal v₁ v₂
Representing Named Indices
Equivalence of named indices.
As introduced in § 4.2, named indices are represented as a structure with a function field. Two named indices are equivalent if they are equal pointwise:
def NIndex.Compat {xs : Is} (idx₁ idx₂ : NIndex xs) :
Prop := ∀ {x : Id} {v : UpperBound}
(hx : lookup xs x = some v),
idx1.get hx = idx2.get hx
notation idx1 " ≈ᵢ " idx2 => NIndex.Compat idx1 idx2
Conversion between named indices
Given xs, ys : Is and idx : NIndex xs, if xs ≈ ys, we can convert idx to an NIndex ys:
def NIndex.eq_cast {xs ys : Is} (idx : NIndex xs)
(xs_ys : xs ≈ ys) : NIndex ys
notation idx " →ᵢ " xy => NIndex.eq_cast idx xy
If ys ⊑ xs, we can also convert idx to an NIndex ys by removing all dimensions that occur in xs but not in ys:
def NIndex.subst_cast {xs ys : Is} (idx : NIndex xs)
(ys_xs : ys ⊑ xs) : NIndex ys
notation idx " ↓ᵢ " yx => NIndex.subst_cast idx yx
Conversion between named and unnamed indices
In Section 4.2, we already know that UIndex is a sequence of natural numbers in terms of an unnamed shape dims. Given the order of dimensions, we can convert between named and unnamed indices:
def NIndex.fromUnnamed
(xs : List Dim) (neq : Unique xs)
UIndex (xs.map Prod.snd) :
NIndex (fromList xs neq)
def NIndex.toUnnamed
(xs : List Dim) (neq : Unique xs)
NIndex (fromList xs neq) :
UIndex (xs.map Prod.snd)
These two functions can be defined by recursion on xs.
Properties of Named Shapes and Indices
It is easy to see that named shapes have the following properties by the definitions of , , and :
Theorem 5.1. The equivalence relation of two named shapes is reflexive, symmetric, and transitive.
Theorem 5.2. The subset relation of two named shapes is reflexive and transitive.
Theorem 5.3. The compatibility relation of two named shapes is reflexive and symmetric.
We can also prove that looking up in the results of , , and can be obtained by combining the results of looking up in the operands of , , and :
Theorem 5.4. The operation lookup distributes over union, intersection, and difference of named shapes.
This theorem can be proved by induction on xs.pairs. It is key to proving Theorem 6.2 without explicitly defining permutation of index variable sequences.
An important property of named indices is their equality:
Theorem 5.5. Given a named shape xs and two indices idx₁, idx₂ of xs, idx₁ = idx₂ if idx₁ ≈ᵢ idx₂.
To prove this property, we use the functional definitions of idx₁, idx₂ and function extensionality. With this property, when we pass a tensor of shape xs and two equivalent indices of xs to denote respectively, we can rewrite one index to the other and thus prove that the two sides are equal to each other:
theorem denote_congr {S : Type} [Semiring S]
{Γ : Context} {xs : Is}
(t : TExpr Γ xs) (env : Env (S := S) Γ)
(idx₁ idx₂ : NIndex xs) (h : idx₁ ≈ᵢ idx₂) :
denote t env idx₁ = denote t env idx₂Optimization by Rewriting
Having defined the named tensor language and proved the properties of named shapes and indices, we can finally prove some rewriting rules of expand and einsum correct. In Sections 6.1 and 6.2, we present the informal statements of our theorems and sketch their mechanized proofs. We discuss some details about the mechanized proofs in Section 6.3.
Thanks to the fact that all shapes are named and satisfy the necessary equivalence, subset, or compatibility relations, these theorems can be stated and proven mostly using set-theoretical properties of the operations of named shapes. There is no need to rename or explicitly permute dimensions.
The Fusion of expand
Theorem 6.1. Two expands can be merged into one:
Named tensors help us avoid the bookkeeping of renaming and permutation in the statement and proof of this theorem. The informal statement (39) contains the operand
but unnamed tensors would call for the more general
where and are renamed to and respectively. To prove the theorem in the unnamed language, we would need to do the bookkeeping of renaming. In the named version, since names are intrinsic to shapes and we define an equivalence relation between named shapes, we do not need to worry about dimension renaming.
Similarly, the output shape in (39) is chosen as a representative, but the actual output shape can be , , or any other permutation of . Since the shape of an unnamed tensor is an ordered list of numbers, we have to encode permutation if we want to prove the theorem about unnamed tensors. In the named version, since shapes are finite maps from names to dimension sizes, we can avoid permutation.
Proof sketch. Following the denotational semantics, the equation reduces to the form
For the left hand side, we first convert from a named index of to , then to . For the right hand side, we convert directly from to . Both conversions remove the same dimensions from , so they leave the same dimensions in . Therefore, both sides have the same index. Since , , and named indices are the same, the two sides are equal. □
The mechanized theorem statement adds the necessary side conditions.
theorem expand_fuse {S : Type} [Semiring S]
{Γ : Context} {xs ys zs : Is}
(t : TExpr Γ xs) (xy : xs ⊑ ys) (yz : ys ⊑ zs)
(env : Env (S := S) Γ) (idx : NIndex zs) :
denote (.expand (.expand t xy) yz) env idx =
denote (.expand t (IsSubset_trans xy yz)) env idx
Since the subset relation between input and output shapes of expand is guaranteed by the well-formedness of named tensor expressions, we can specify the output shape of expand directly rather than using the juxtaposition . We do not need to worry about the dimension renaming allowed by the unnamed tensor language when nesting expressions, such as expand(expand(E[ $\vec{x}$] → $\vec{x}\vec{y}$) [$\vec{x}\vec{y}'$] → $\vec{x}\vec{y}\vec{z}$), where . In a sense, the translator in § 4.3 consistently renames the index variables ahead of time.
The Commutativity of expand and einsum
Theorem 6.2. The operations einsum and expand commute up to a factor:
where
As with Theorem 6.1, names intrinsic to tensors help us state and prove this theorem without renaming and permutation bookkeeping. When einsum and expand meet in the unnamed tensor language, the two occurrences of in (40) may not match, nor the two occurrences of . Also, the concatenation may be permuted. To prove the more general theorem in the unnamed language, we would need to interleave bookkeeping with reasoning about sums and products. In contrast, our named shapes can be thought of as unordered sets; we visualize them as such in Appendix § 11.
Proof sketch. The denotation on the left hand side of (40) is a summation over indices of shape . This shape turns out to be the disjoint union of § 5.1 of two shapes: consists of the dimensions that are not used to index any input tensor, and consists of the dimensions that are used to index some input tensors. The main argument, then, is to split the summation into two nested summations. One of them ranges over indices of shape , and reduces to the constant factor because is unused.
Specifically, using the conditions and , the two sides of (40) separately reduce to
Since doesn’t contain dimensions from or , we know is not used to index the denotations of and . Thus, the named index , whose domain is , is not used in the first summation in (42). Therefore, that summation reduces to the constant factor on the right hand side. □
The mechanized version of Theorem 6.2 follows the informal statement and proof above. Since it requires a lot of side conditions, we use a helper function EinsumExpandCommEq to produce the desired equation between two denotations.
theorem einsum_expand_comm_two
{S : Type} [Semiring S]
{Γ : Context} {xs ys zs ws : Is}
(t₁ : TExpr Γ xs) (t₂ : TExpr Γ zs)
(xy : xs ⊥ ys)
(xyz : unionIs xs ys (disjointIs_compat xy) ~ zs)
(w_xys : ws ⊑ ⋃ (IsCompat_two xyz))
(env : Env (S := S) Γ) (idx : NIndex ws) :
EinsumExpandCommEq t₁ t₂ xy xyz w_xys env idx
Corollary 6.3. Summation-free einsum and expand commute:
Proof sketch. Since the einsum expression is summation-free, . Therefore, and . By Theorem 6.2, the two sides are equal. □
Notes on the Mechanization
We mechanized the proofs in Lean 4.27.0 and Agda 2.7.0.1. For Lean, we used Mathlib’s Semiring infrastructure. For Agda, we used as the scalar value type. The Lean proof uses helper theorems provided by Mathlib about summation; we have not proven Theorem 6.2 in Agda. Both versions follow the same design as described above. We took advantage of Agda’s customized syntax and hole system to explore the design of the tensor language. Then we ported the proof to Lean and generalized it to an arbitrary semiring. We also used Codex to search for related theorems from Mathlib.
Despite the fact that Codex can give proofs of lemmas, it often generated dense proofs that did not take advantage of lemmas we have proven. For Agda, it tended to generate large equational reasoning expressions that used a lot of transitivity and symmetry without extracting intermediate steps. Occasionally it did generate very concise proofs. When we split the proof into multiple steps, the proofs it generated became more readable.
Related Work
Both einsum and tensor description languages have a large number of implementations and applications. We discuss the implementation, optimization, and formalization of einsum. We also briefly introduce the work on named tensor notation, and on verifying tensor description languages.
Implementation and Optimization of einsum
Different forms of einsum have been implemented in various languages and libraries. Matrix multiplication, arguably the most common case of einsum, is fundamental to scientific computing [7] and thus has been implemented in many tensor libraries, including the well-known NumPy [17], PyTorch [2], and TensorFlow [24]. Because matrix multiplication is so fundamental, these libraries also optimize its performance targeting specific hardware or even specific matrix sizes [18, 19]. We refer readers to Golub and Loan [15] for a more detailed introduction to this topic.
For the general form of einsum, many languages have their own implementations [1, 6, 26, 30]. There are also implementations that focus more on the algebraic properties of tensors [5, 28]. It is well-known that finding the most efficient way (contraction path) of computing einsum is NP-hard [20]. Therefore, many libraries for optimizing the performance of einsum are implemented [4, 8, 11, 14, 31]. In the context of quantum computing, einsum is often expressed as tensor network contraction. There are also a lot of efforts to optimize the performance of tensor network contraction [12, 16].
Formalization of einsum
Even though einsum has been used by physicists for over a century and adopted by the machine learning community for over a decade, its formalization is pretty recent work.
Wenig et al. [29] give a clear semantics for einsum. Their formalization, unlike ours, allows repeated index names for both inputs and outputs. However, they don’t consider the interaction between einsum and other tensor operations or provide a mechanized proof.
Mahathevan et al. [23] use einsum expressions for fuzzing sparse tensor compilers, but they don’t consider the formalization of einsum per se.
Tooby-Smith [28] formalizes the tensor notation used in physics, where the Lean syntax is used to represent index names. But their formalization does not consider the form of einsum based on multi-dimensional arrays. They also provide no rewriting rules for einsum.
Named Tensor Notation
It is not new to name dimensions of tensors. For example, the definition of einsum inherently requires names for tensor dimensions. In tensor network libraries like Quimb [16], tensors can be constructed with dimension names. As discussed by Chiang et al. [10], several tensor libraries have implemented this notation. Chiang et al. [10] formalize the idea with semantics and working examples, but their concern is not mechanization.
The mechanization of Tooby-Smith [28] does support named dimensions. But tensor contraction is done by pairing dimensions. Only a pair of dimensions can be contracted at one time. If we want to express einsum that sums over multiple dimensions, we have to manually choose the contraction order and write einsum as a nested sequence of contractions.
Verification of Tensor Languages
As discussed above, based on what “tensor” means, the formalization of einsum can also have different meanings. Therefore, the formalization of einsum always follows a formalization of a tensor description language, which has a much richer literature [3, 21, 22, 25, 27, 28]. It is possible to translate einsum into these formalized tensor languages by composing the operations in them. There are two reasons why we do not formalize einsum this way. First, most mechanized tensor languages use unnamed tensor notation, which means we still need to find a way to guarantee the correctness of naming dimensions. Second, translating einsum into existing operations makes it less obvious to find the rewriting rules.
Conclusion
We mechanize a tensor language that supports einsum and expand with named tensor notation. We give the syntax and the denotational semantics of the unnamed version of the language on paper and the named version mechanized in a proof assistant. We provide a translation from the unnamed tensor language to the named tensor language. We prove that the translation preserves the semantics of the unnamed language. We discuss the techniques required to support named tensors and how they are used to mechanize einsum. We prove the rewriting rules about einsum and expand that can improve the efficiency of einsum calculation.
References
Translation Helper Functions
shape
The shape of an unnamed tensor is returned by , which takes a context and an unnamed tensor expression . It returns a list of upper bounds. The definition is shown below.
gendim
To generate an IVar list and a proof that names in have no duplicates, we invoke . It takes a list of upper bounds and returns a pair consisting of an IVar list and a no-duplicate proof. Here, we rely on a function to generate a fresh name and a proof that the name doesn’t occur in .
where is a fresh name
create_dict
We represent a name map as an association list. To construct a name map, takes an index variable sequence and a corresponding IVar list . It zips the names of and to get a map from names in the former to the latter. Here, we use to represent the list of names in . The definition of is shown below.
freshen
The function takes an index variable sequence and a name map. It returns a name map.
where is a fresh name
rename
The function takes an index variable sequence and a name map . It returns an IVar list. Since it is guaranteed that every name in occurs in , simply looks up the name and replaces it with the associated name.
Visualizing Named Shapes in thm:einsum-expand
The reader may find the picture below useful for tracking named shapes and their relations in Theorem 6.2.

Figure 1 (PDF p. 14).
References
- [1]Constantin Ahlmann-Eltze and Koki Tsuyuzaki. 2026. Einstein Summation. https://cran.r-project.org/web/packages/einsum/index.html
- [2]Jason Ansel, Edward Yang, Horace He, Natalia Gimelshein, Animesh Jain, Michael Voznesensky, Bin Bao, Peter Bell, David Berard, Evgeni Burkovski, Geeta Chauhan, Anjali Choudia, Will Constable, Alban Desmaison, Zachary DeVito, Elias Ellison, Will Feng, Jiong Gong, Michael Gschwind, Brian Hirsh, Sherlock Huang, Kshiteej Kalambarkar, Laurent Kirsch, Michael Lazos, Mario Lezcano, Yanbo Liang, Jason Liang, Yinghai Lu, CK Luk, Bert Maher, Yunjie Pan, Christian Puh́rsch, Matthias Reso, Mark Saroufim, Marcos Yukio Siraichi, Helen Suk, Michael Suo, Phil Tillet, Eikan Wang, Xiaodong Wang, William Wen, Shunting Zhang, Xu Zhao, Keren Zhou, Richard Zou, Ajit Mathews, Gregory Chanan, Peng Wu, and Soumith Chintala. 2024. PyTorch 2: Fast Machine Learning through Dynamic Python Bytecode Transformation and Graph Compilation. In 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (ASPLOS ’24). ACM. doi:10.1145/3620665.3640366DOI
- [3]Jai Arora, Sirui Lu, Devansh Jain, Tianfan Xu, Farzin Houshmand, Phitchaya Mangpo Phothilimthana, Mohsen Lesani, Praveen Narayanan, Karthik Srinivasa Murthy, Rastislav Bodik, Amit Sabne, and Charith Mendis. 2025. TensorRight: Automated Verification of Tensor Graph Rewrites. Artifact for “TensorRight: Automated Verification of Tensor Graph Rewrites” 9, POPL (Jan. 2025), 29:832–29:863. doi:10.1145/3704865DOI
- [4]Harun Bayraktar, Ali Charrara, David Clark, Saul Cohen, Timothy Costa, Yao-Lung L. Fang, Yang Gao, Jack Guan, John Gunnells, Azzam Haidar, Andreas Hehn, Markus Hohnerbach, Matthew Jones, Tom Lubowe, Dmitry Lyakh, Shinya Morino, Paul Springer, Sam Stanwyck, Igor Terentyev, Satya Varadhan, Jonathan Wong, and Takuma Yamaguchi. 2023. cuQuantum SDK: A High-Performance Library for Accelerating Quantum Science. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, Bellevue, WA, USA, 1050–1061. doi:10.1109/QCE57702.2023.00119
- [5]Jean-Philippe Bernardy and Patrik Jansson. 2025. Domain-Specific Tensor Languages. Journal of Functional Programming 35 (2025), e9. doi:10.1017/S0956796825000048DOI
- [6]Mark Blacher, Julien Klaus, Christoph Staudt, Sören Laue, Viktor Leis, and Joachim Giesen. 2023. Efficient and Portable Einstein Summation in SQL. Proceedings of the ACM on Management of Data 1, 2 (June 2023), 121:1–121:19. doi:10.1145/3589266DOI
- [7]L. Susan Blackford, James Demmel, Dongarra Dongarra, Duff Duff, Sven Hammarling, Greg Henry, Michael Heroux, Linda Kaufman, Andrew Lumsdaine, Antoine Petitet, Roldan Pozo, Karin Remington, and R. Clint Whaley. 2002. An Updated Set of Basic Linear Algebra Subprograms (BLAS). ACM Transactions on Mathematical Software (TOMS) 28, 2 (June 2002), 135–151. doi:10.1145/567806.567807
- [8]Alexander Breuer, Mark Blacher, Max Engel, Joachim Giesen, Alexander Heinecke, Julien Klaus, and Stefan Remke. 2025. Einsum Trees: An Abstraction for Optimizing the Execution of Tensor Expressions. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (ASPLOS ’25). Association for Computing Machinery, New York, NY, USA, 275–292. doi:10.1145/3676641.3716254DOI
- [9]David Chang, David Riley, Grant Exley, Kenneth Sible, Yafei Yang, and Chung-chieh Shan. 2024. Factor Graph Grammars in Python. https://github.com/diprispm/fgs
- [10]Dingyong Chiang, Alexander M Rush, and Boaz Barak. 2023. Named Tensor Notation. Transactions on Machine Learning Research (2023). https://openreview.net/forum?id=hVT7Shlix
- [11]Brian DuSell. 2026. Semiring Einsum. https://github.com/bdusell/semiring-einsum
- [12]E. Schuyler Fried, Nicolas P. D. Sawaya, Yudong Cao, Ian D. Kivlichan, Jonathan Romero, and Alán Aspuru-Guzik. 2018. QTorch: The Quantum Tensor Contraction Handler. PLOS ONE 13, 12 (Dec. 2018), e0208510. doi:10.1371/journal.pone.0208510DOI
- [13]Daniel P. Friedman and Mitchell Wand. 2008. Essentials of Programming Languages (3rd ed.). MIT Press, Cambridge, MA.
- [14]Daniel G. A. Smith and Johnnie Gray. 2018. Opt_einsum - A Python Package for Optimizing Contraction Order in Einsum-like Expressions. Journal of Open Source Software 3, 26 (June 2018), 753. doi:10.21105/joss.00753DOI
- [15]Gene H. Golub and Charles F. Van Loan. 2013. Matrix Computations (4th ed.). Johns Hopkins University Press. doi:10.56021/9781421407944DOI
- [16]Johnnie Gray. 2018. Quimb: A Python Package for Quantum Information and Many-Body Calculations. Journal of Open Source Software 3, 29 (Sept. 2018), 819. doi:10.21105/joss.00819DOI
- [17]Charles R. Harris, K. Jarrod Millman, Stefan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. 2020. Array Programming with NumPy. Nature 585, 7825 (Sept. 2020), 357–362. doi:10.1038/s41586-020-2649-2DOI
- [18]Chetan Jhurani and Paul Mullowney. 2013. A GEMM Interface and Implementation on NVIDIA GPUs for Multiple Small Matrices. arXiv:1304.7053. doi:10.48550/arXiv.1304.7053arxiv.org/abs/1304.7053
- [19]Fredrik Kjolstad, Shoaib Kamil, Stephen Chou, David Lugato, and Saman Amarasinghe. 2017. The Tensor Algebra Compiler. Proceedings of the ACM on Programming Languages 1, OOPSLA (Oct. 2017), 1–29. doi:10.1145/3133901DOI
- [20]Chi-Chung Lam, P. Sadayappan, and Rephael Wenger. 1997. On Optimizing a Class of Multi-Dimensional Loops with Reduction for Parallel Execution. Parallel Processing Letters 07, 02 (1997), 157–168. doi:10.1142/S0129626497000176DOI
- [21]Amanda Liu, Gilbert Bernstein, Adam Chlipala, and Jonathan Ragan-Kelley. 2024. A Verified Compiler for a Functional Tensor Language. Proceedings of the ACM on Programming Languages 8, PLDI (June 2024), 320–342. doi:10.1145/3656390DOI
- [22]Amanda Liu, Gilbert Louis Bernstein, Adam Chlipala, and Jonathan Ragan-Kelley. 2022. Verified Tensor-Program Optimization via High-Level Scheduling Rewrites. Proceedings of the ACM on Programming Languages 6, POPL (Jan. 2022), 55:1–55:28. doi:10.1145/3498717DOI
- [23]Kabilan Mahathevan, Yining Zhang, Muhammad Ali Gulzar, and Kirshanthan Sundararajah. 2026. TENSURE: Fuzzing Sparse Tensor Compilers (Registered Report). CoRR abs/2603.18372 (2026). arXiv:2603.18372 doi:10.48550/ARXIV.2603.18372DOI
- [24]Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Végas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Yuan Yu, and Xiaoqiang Zheng. 2015. TensorFlow: Large-scale Machine Learning on Heterogeneous Systems. https://www.tensorflow.org/arxiv.org/abs/1603.04467
- [25]Daniel Nezamabadi, Magnus O. Myreen, and Yong Kiam Tan. 2026. Verified VCG and Verified Compiler for Dafny. In Proceedings of the 15th ACM SIGPLAN International Conference on Certified Programs and Proofs. ACM, Rennes France, 171–186. doi:10.1145/3779031.3779092DOI
- [26]Le Niu. 2026. Hhlo. https://github.com/overshiki/hhlo
- [27]Artjoms Sinkarovs and Troels Henriksen. 2025. Correctness Meets Performance: From Agda to Futhark. Proc. ACM Program. Lang. 9, ICFP, Article 255 (Aug. 2025). doi:10.1145/3474752DOI
- [28]Joseph Tooby-Smith. 2024. Formalization of Physics Index Notation in Lean 4. arXiv:2411.07667 [cs.LO] doi:10.48550/arXiv.2411.07667
- [29]Maurice Wenig, Paul G. Rump, Mark Blacher, and Joachim Giesen. 2025. The Syntax and Semantics of Einsum. arXiv:2509.20020 [cs] doi:10.48550/arXiv.2509.20020DOI
- [30]Alex Williams. 2026. Einsum.Jl. https://github.com/ahwillia/Einsum.jl
- [31]Alexandros Nikolaos Ziogas, Grzegorz Kwasniewski, Tal Ben-Nun, Timo Schneider, and Torsten Hoefler. 2022. Einsum: Practically I/O Optimal Multi-Linear Algebra. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis (SC ’22). IEEE Press, Dallas, Texas, 1–15. https://dl.acm.org/doi/10.5555/3571885.3571918DOI
