CS Paper Radar

Formalizing $\mathsf{einsum}$ with Named Tensor Notation

Yafei Yang, Chung-chieh Shan

cs.PL ·submitted 2026-11-14 16:56 UTC · v1

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.

Comment
14 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Representing Tensors as Compositions for Efficient Computation on Sparse and Structured Data

cs.LG cs.MScs.PL ·2026-11-07 ·Valérian Rey, Praneth Paruchuri
code/data similarity 0.64
Abstract · 15 pages, 6 figures

We propose a new mathematical formalism in which all kinds of tensors and of operations on those tensors are represented as simple function compositions. Tensors are functions from indices to values. An element-wise operation (e.g. an activation function) is a composition with a function applied to values; re-indexing (e.g. reshape, transposition) is a composition with a function applied to indices; and a reduction is a composition with both an index function, mapping each index to several indices, and a reduction operation (e.g. product, sum, max). Combined with tensor stacking, these compositions can represent most interesting kinds of tensors (e.g. dense, jagged, all kinds of sparsity patterns, matrix factorizations), as well as lazy versions of almost every operation available in modern tensor computation frameworks, including einsums between tensors of any kind. Identities between compositions can then be used to rewrite such expressions into equivalent ones, without evaluating them. For instance, the product of two sparse matrices can be rewritten so that only products between non-zero values are computed, turning a sparse problem into a dense one. Using this algebra as the intermediate representation of a tensor computation engine would shift the focus from defining operations on tensors (e.g. einsum between sparse tensors) to defining an algebra on index functions. This should reduce the codebase complexity from $\mathcal{O}(mn^2)$, with $m$ the number of binary operations between tensors and $n$ the number of tensor types, to $\mathcal{O}(m + k^2)$, with $k$ the number of types of index functions. A draft implementation of a tensor computation framework based on this algebra is publicly available.

0.21

Mechanising Denotational Semantics in Agda

cs.PL ·2026-10-10 ·Peter D. Mosses, Jesper Cockx, Bernhard Reus
published similarity 0.60
Abstract · 23 pages, excl. references. To be published in Proceedings of MFPS 2026

Mechanisation of a mathematical definition (also referred to as formalisation) has many benefits. Here, we focus on mechanising denotational semantic definitions of programming languages by embedding them in the Agda language. The Agda type-checker detects and reports any issues with the wellformedness and type correctness of the embedded definitions. To minimise the effort required, and to facilitate correlation of the original definition with its Agda embedding, mechanisation should not involve significant reformulation or extension. Here, we show how to embed conventional Scott-Strachey denotational definitions in Agda with almost no changes to $λ$-notation or domain equations. Agda notation for definitions of types and functions corresponds closely to the conventional meta-notation of denotational semantics. We have developed a collection of Agda modules with postulated types for commonly used domain constructors and their associated operations. We illustrate our approach with mechanisations of three denotational definitions: a model of the untyped $λ$-calculus, Plotkin's denotational semantics of PCF, and a semantics of a sublanguage of Scheme. In previous work, similar mechanisations in Agda have revealed several unsuspected wellformedness issues in published denotational definitions. Some of the postulated properties of our definitions are inconsistent with a classical set-theoretic interpretation of Agda. We conjecture that they would be consistent with an interpretation of Agda in a higher-order intuititionistic logic, such as that used by Simpson in his work on synthetic domain theory. After recalling previous work on mechanising domain theory, we consider the possibility of mechanising synthetic domain theory in Agda.

0.30

Every Kernel Is a Join: Automatic Multi-GPU Parallelism for AI Computations in Einsummable

cs.DC ·2026-09-03 ·Zhimin Ding, Chen-Kuan Liao, Chima Adiole, Brianna Barrow, Fangzhou Du +5 more
similarity 0.58
Abstract

Distributing an AI computation across the GPUs of a multi-GPU server is one of the central problems in systems-for-AI. We present Einsummable, a prototype system that accepts a PyTorch-like description of an AI computation and automatically distributes it across a multi-GPU server, with no device assignments, sharding annotations, or communication operations written by the programmer. Einsummable models every operation as a relational join followed by an aggregation over tensor relations, in which the tuples contain sub-tensors. Each operation exposes its possible decompositions through what we call "join-agg specs". An optimizer then selects decompositions across the whole computation to minimize a communication-cost proxy. Because it searches decompositions rather than a menu of named strategies, Einsummable discovers plans that mesh-based auto-parallelizers cannot. Each decomposed operation is implemented by synthesizing an exchange program, which is a topology-aware generalization of Volcano's exchange operator. Einsummable invokes no canned collectives: all communication and aggregation is special-purpose, derived at compile time. Despite being fully automatic, Einsummable can outperform custom-designed implementations. For example, on LLaMA transformer blocks on an eight-GPU A100 server, Einsummable achieves a geometric-mean runtime of 8.97 ms, versus 13.80 ms for hand-tuned PyTorch and 15.90 ms for vLLM.

0.11

Verifiable LLM-Guided Focal SMT Solving for Quantified Arrays

cs.AI ·2026-10-29 ·Kunhang Lv, Rui Han, Fuqi Jia, Yuhang Dong, Feifei Ma +1 more
similarity 0.55
Abstract

Large language models can often identify useful semantic structure in formal artifacts, but their outputs cannot be trusted as proofs or solver decisions. We study whether LLMs can instead guide formal reasoning systems through a narrow, solver-verifiable interface. We instantiate this idea in quantified array SMT solving, where modern instantiation-based techniques can fail when key ground terms and equalities are hidden by auxiliary variables, axiom guards, and nested array terms. We observe that many instances are largely driven by a small set of focal ground terms or constraints, similar to the backdoor sets in SAT solving. Building on this, we present LinguaArray, a framework where an LLM proposes a small Semantic Focus Set (ground terms/constraints), while a conventional SMT solver remains the sole proof engine and certifies all results. LinguaArray uses these LLM-suggested, solver-validated finite sets to significantly enhance solver capability, solving additional satisfiable and unsatisfiable instances that the backend alone fails to solve. It interacts within a finite time and then falls back to the backend solver to mitigate potential regressions. Evaluation on 1015 SMT-LIB instances across five logics under 1200s timeout (including LLM latency) shows that LinguaArray solves up to 69.1% of instances and increases solved-instance counts by 105%--397% over the corresponding backends.

0.22

TensorBound: Characterizing Tensor Binding Failures in AI Compiler and Runtime Stacks

cs.CR ·2026-10-27 ·Wen Li, Yongxi Sha, Baihong Chen
similarity 0.54
Abstract

AI compiler and runtime stacks must preserve bindings between tensor values and their operations, storage, and execution state. These bindings can fail while the underlying objects remain present, with symptoms appearing in another layer. We present TensorBound, an empirical study of tensor binding failures in IREE and the XLA and PyTorch ecosystems. The study analyzes 264 reports and reconstructs 149 distinct repaired causes through source tracing and comparisons of pre-fix and repaired revisions. Each reconstruction connects the first invalid decision to its violated condition, physical effect, and repair. Missing eligibility checks, incorrect mappings or translations, and lost or omitted relations account for 69.1% of repaired causes. These patterns highlight the need to preserve binding facts and check the conditions for their use. The 101 first invalid decisions in compiler code identify candidate checking points before execution. Four archived IREE diagnostic attempts distinguish effect localization from source-based cause explanation. Together, these findings motivate transition-specific checks that preserve binding facts across representations and enforce the required conditions at consuming decisions.

0.26

The Future of AI-assisted Physics: Discovering, Verifying and Organizing Results via Formalization

cs.AI hep-phcs.LOhep-th ·2026-10-06 ·Sven Krippendorf, Leopoldo Sarra, Joseph Tooby-Smith
survey similarity 0.54
Abstract · 19 pages, 2 figures

Rapid advances in AI have opened a new era for physics, enabling unprecedented capabilities in research and discovery. However, these advances also bring challenges in verifying, trusting, and reusing the results they so rapidly produce. Formalization is a necessary part of the solution to these challenges. In this paper, as well as giving an overview of the role of AI and formalization in physics, we make the case that: (1) formalization is an essential layer for AI-driven discoveries in both computational and theoretical physics; (2) AI is lowering the barrier to, and increasing the efficiency of, formalization in physics, though it remains weaker at choosing definitions and designing libraries than at writing proofs; (3) the speed AI brings to formalization in physics currently comes at the cost of trust, credit, and community; (4) shared, community-reviewed formal libraries such as Physlib should be central in making progress in this field, both as a trusted, reusable foundation for physics results and as the environment in which AI systems can reason about physics; (5) formalizing physics raises challenges beyond those in mathematics, most importantly that a checked proof does not establish that its definitions faithfully capture the intended physics. We also give our perspectives on near-term and long-term directions in these areas.

0.25

Tensor Methods for Language Models: From Token Representation to Training, Adaptation, Inference, Compression, and Interpretability

cs.LG cs.AI ·2026-08-31 ·Matvei Tarasov, Salman Ahmadi-Asl, Andre L. F. de Almeida, Andrzej Cichocki
surveycode/data similarity 0.53
Abstract

Large language models (LLMs) are built from structured high-dimensional objects such as token representations, weights, adaptation updates, caches, and activations, whose multilinear structure is underexploited by the conventional matrix-centric view. Tensor decompositions and tensor networks provide a principled algebraic language for this structure, yet the literature often treats them as isolated compression mechanisms. This survey organizes tensor methods for LLMs through two complementary views: a seven-stage lifecycle taxonomy covering tokenization, embeddings, pre-training, adaptation, compression, inference, and interpretability, and a component view covering embeddings, attention, and feed-forward networks. We provide unified notation and theoretical foundations, analyze tensorization strategies for individual Transformer components, and compare methods at each lifecycle stage while making differences in evaluation protocols and model scales explicit. We further connect tensor methods to neighboring efficiency techniques and probabilistic tensor networks. Finally, we synthesize open challenges and introduce $ρ_{\rm gap}$, a metric for the compression-realization gap between theoretical memory reduction and measured system-level speedup. By treating tensorization as a common structural principle, the survey provides a structured entry point to tensorized language models and clarifies when parameter savings can plausibly translate into memory efficiency, computational efficiency, or interpretability. The GitHub page dedicated to this paper is accessible at \href{https://github.com/ma-tt-a/awesome-tensor-methods-for-llms}{this https URL}.

0.54

Logical Relations on Display

cs.PL cs.LO ·2026-11-16 ·Steven Schaefer, Johnson He, Max S. New
top venue similarity 0.52
Abstract · 31 pages, 3 figures, to appear at POPL 2027

The metatheory of programming languages suffers from a lack of reuse. Researchers develop individual calculi and prove standard properties, but very few results are truly reused across papers. The problem is worse in proof assistants, where developments routinely duplicate code from prior work or rebuild it from scratch. Category theory provides the most promising path toward reusable programming language semantics. Universal properties capture the type connectives---products, functions, sums---together with their $β$/$η$ laws. Free categorical structures identify syntactic calculi. \emph{Displayed} categories provide a uniform language for specifying logical relations, and general theorems about fibrations allow their structure to be assembled compositionally. In this work we develop a library of formalized category theory in the Cubical Agda proof assistant directly applicable to programming language metatheory. We develop theories of universal properties and free categorical structures, apply them to define denotational semantics and logical relations for simply typed calculi, and identify encodings of the categorical constructions that make typechecking them tractable. From the same categorical components, we construct several familiar results via a logical relations construction---canonicity,parametricity,conservativity---and provide a proof of coherence for monoidal categories.

0.48