Skip to content

Change the Product, Keep the Parameters: Associative Algebra Layers for Transformers

Sep 2026 · 0 citations · 24 references
Computer Science

TL;DR

This work constructs a family with quadratic arithmetic in the matrix dimension when the physical block size remains fixed, and derive finite-shape constraints for GPU execution, and treats these results as a feasibility and trainability check for the proposed approach at small scale, leaving further investigation to future work.

Abstract

Fast matrix multiplication algorithms keep the product fixed and search for a cheaper way to evaluate it. We instead ask whether a Transformer's learned projections can use a different, cheaper product altogether. Building on an associative-algebra construction that replaces ordinary matrix multiplication with a sparser interaction table over the same weight blocks, we construct a family with quadratic arithmetic in the matrix dimension when the physical block size remains fixed, and derive finite-shape constraints for GPU execution. The construction is provably optimal for its bilinear rank by the Alder--Strassen bound and can be realized as row-typed rectangular projections compatible with causal masking and KV-cached decoding. We provide an empirical test of this approach by training two approximately 110M-parameter decoder-only Transformer LMs from the same recipe and 12.3B-token budget, differing only in their feed-forward layer: one uses ordinary dense matrix multiplication and the other uses the associative-algebra product. Across four prompt domains, the algebraic model achieves a 6.2--7.8\% increase in end-to-end generation throughput, while obtaining lower scores on all three reported downstream metrics. We treat these results as a feasibility and trainability check for the proposed approach at small scale, leaving further investigation to future work.

View source

Similar papers

Preprint Oct 2026

A faster matrix multiplication algorithm through structured optimization

We present a new asymptotic matrix multiplication construction yielding $\omega<2.37115924$, and therefore an algorithm that multiplies two $n\times n$ matrices in $O(n^{2.37115924})$ arithmetic operations over the rationals, reals, or complex numbers. The construction improves the bound $2.371177$ of Dupont et al. wit...

R. Zadeh · 0 citations
#natural language process... Preprint Aug 2026

All You Need Is Non-Commutative Words

It is shown that the noncommutativity of matrix product captures word order without positional encodings (PEs) and yields several capabilities, including antisymmetric self-attention with no query, key, or value projections, and parallel composition of variable-length text chunks at a reduced attention cost.

Carla Quispe Flores, Stanley Salvatierra, Renan Cabrera · 0 citations
#artificial intelligence Preprint Oct 2026

Cleave: Scaling Tensor Program Optimization via Decoupled Algebraic Search and Operator Scheduling

Optimized kernels such as FlashAttention and FlashDecoding are crucial for accelerating today's large models. Most of them are handwritten by experts because existing ML compilers cannot match their efficiency. Producing such kernels requires fusing computations with multiple reductions, which requires both algebraic t...

David Pissarra, Jinkun Lin, Hai-Tian Jiang et al. · 0 citations

Beyond Accuracy: Prefix-Invariant Realizations of Low-Precision Fast Matrix Multiplication

Fast matrix multiplication saves multiplications through exact cancellation, but rounding sums that mix token rows can leave contributions from later tokens in earlier language model outputs. This threatens prefix invariance, which multiple-choice likelihood scoring relies on: a scored likelihood must depend only on it...

Shu-Xiao Xie, Shu-Yang Xie, Yuan Cao et al. · 0 citations

Precision As You Need: Stochastic Computing Is a Dense Adaptive Quantizer

This work builds a GPU library that emulates SC matrix multiplication at scale, exposes stream lengths as first-class kernel arguments, and evaluates SC end-to-end on image classification, object detection and instance segmentation, class-conditional image generation, and visual world-model planning.

Hao-Ran Jin, Kang-Qi Zhang, Ji-Rong Yang et al. · 0 citations
Preprint Sep 2026

Compile-once operation graphs for reusable continuous unitary transformations

Continuous unitary transformations repeatedly evaluate the same operator algebra as the coefficients of a Hamiltonian and its observables evolve. We compile these algebraic relationships once into a numerical operation graph that can be saved and reused for new coefficient sets, additional operators, derivatives, and f...

Bo Peng, N. Govind · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.