Formal Definition of Einsum Enables Systematic Optimization of Tensor Expressions in NumPy and Beyond

The concise notation known as einsum has become a cornerstone of modern numerical computation, underpinning operations in fields ranging from machine learning to circuit simulation, yet it currently lacks a rigorous theoretical foundation. Maurice Wenig, Paul G. Rump, Mark Blacher, and Joachim Giesen from the Institute of Computer Science at Friedrich-Schiller-University Jena now address this gap, providing a formal definition of the einsum language and establishing a solid theoretical basis for its use. This work clarifies the terminology of tensor expressions and rigorously proves key equivalence rules, which unlocks opportunities for formal reasoning and systematic optimisation of numerical computations across diverse software frameworks. By establishing a unified and formal understanding of einsum, the team significantly advances the reliability and efficiency of numerical algorithms used in a wide range of scientific and engineering applications.

Researchers began by meticulously defining the terminology of tensor expressions, creating a rigorous language to describe complex mathematical operations. This foundational step enabled the formal definition of the einsum language itself, moving beyond its practical implementation to a precise theoretical framework. The study then focused on formalizing and proving key equivalence rules for tensor expressions, demonstrating that different einsum formulations can yield identical results.

Researchers leveraged this framework to highlight the relevance of these equivalence rules in practical applications, demonstrating how they can be used to optimize performance and simplify complex calculations. Building on this foundation, the team investigated the computational complexity of tensor network contraction ordering, revealing its NP-hardness, a significant theoretical result. This discovery underscores the inherent difficulty in finding optimal contraction orders for large tensor networks, informing the development of efficient approximation algorithms. Furthermore, the study explored the use of tensor networks to represent quantum circuits, developing a decision diagram approach that offers a compact and efficient representation.

Einsum Semantics Formally Defined and Proven

This work provides a rigorous definition of einsum, a widely used notation for tensor operations, and proves key equivalence rules. While einsum has become a practical tool in fields like circuit simulation and machine learning frameworks, a solid theoretical basis has been absent, hindering formal reasoning and optimization. Researchers have addressed this gap by defining the semantics of einsum expressions as a sum of products within a chosen semiring, enabling a precise understanding of how these expressions are evaluated. The team defines an einsum expression as aggregating over all possible assignments of values to index symbols, projecting these assignments onto a desired output position.

This formalization allows for the exploration of algebraic properties, demonstrating that einsum is commutative and associative, allowing for flexible grouping of operations without altering the outcome. These properties are proven through mathematical theorems, establishing a robust framework for manipulating and optimizing einsum expressions. Furthermore, the research demonstrates that einsum is distributive with respect to elementwise aggregation of tensors, expanding its versatility. The team also clarifies how einsum relates to standard linear algebra operations, noting that while einsum is commutative, this does not imply that matrix-matrix multiplication is commutative, as the einsum representation differs depending on the order of matrices. Importantly, the work establishes that einsum expressions, when combined with elementwise aggregation, remain closed under differentiation, a crucial property for machine learning applications, and can be infinitely differentiated. This breakthrough delivers a powerful tool for both theoretical analysis and practical optimization of tensor computations.

Einsum Equivalence and Expression Simplification Rules

This work establishes a formal foundation for the einsum notation, a widely used language for expressing tensor operations in fields like machine learning and circuit simulation. Researchers developed a unified syntax and semantics for einsum, clarifying its meaning and enabling rigorous analysis. Crucially, they proved key equivalence rules for tensor expressions, demonstrating that einsum operations are commutative, associative, and distributive over arbitrary commutative semirings. The team also created general rules for restructuring einsum expressions through nesting and denesting, alongside simplification rules that allow for the removal or introduction of constant and delta tensors without altering the underlying meaning. These results bridge a gap between the practical application of einsum in various computational frameworks and a complete theoretical understanding, providing a framework for principled reasoning about equivalence, differentiation, and optimization of tensor expressions. Future research could explore how these formal rules can be leveraged to automatically optimize einsum expressions for specific hardware or software platforms, further enhancing the efficiency of tensor computations.