PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ilya Koziev, Ivan Oseledets

arXiv:2609.32814v1cs.LGcs.PF

TL;DR

The paper asks whether Transformer projections can use a cheaper product by changing the rule for activation–weight interactions. It develops a growing associative-algebra construction and tests it in small language models, finding higher generation throughput but lower downstream scores. The study presents this as a small-scale feasibility and trainability check.

  • Problem

    The paper asks whether learned Transformer projections can use a cheaper product than ordinary matrix multiplication while retaining structured interactions between activation and weight blocks.

    Source: §1 · p. 1

  • Method

    The paper replaces ordinary block multiplication with a sparse associative-algebra interaction rule and scales it through a graph family with rectangular Transformer projections.

    Source: §1 · p. 2, §3.2 · p. 4, §6.2 · p. 6

  • Results

    6.2–7.8% higher end-to-end generation throughput across four prompt domains, with lower scores on GSM8K, IFEval, and MBPP for the algebraic model.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The pilot identifies an arithmetic–latency trade-off on representative Transformer shapes and a generation-throughput gain accompanied by lower downstream scores.

    Source: §1 · p. 2, §10 · p. 9

    The experiment tests one recursive FFN law, one model scale, and one training run per model; larger algebras, algebraic attention, larger models, and repeated seeds remain untested.

    Source: §9 · p. 9

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper asks whether Transformer projections can use a cheaper product by changing how activation and weight blocks interact. It develops an associative-algebra construction and tests a small language-model version, finding higher generation throughput alongside lower downstream scores.

1 INTRODUCTION

  • The proposal changes the interaction rule between activation and learned weight blocks, rather than seeking a cheaper algorithm for ordinary matrix multiplication.Fast matrix multiplication work typically keeps the product fixed while changing its evaluation algorithm.Source: §1 · p. 1
  • Q2 removes two cycle-closing terms while retaining cross-group interactions and composition across layers.The resulting compatible linear maps compose into a map of the same form.Source: §1 · p. 2
  • Six products attain the bilinear-rank lower bound for Q2, making the displayed evaluation optimal for this multiplication table.For four slots and two vertices, the Alder–Strassen bound gives R(Q2) ≥ 2 · 4 − 2 = 6.Source: §1 · p. 2
  • The graph construction generalizes the algebraic design, with arithmetic fraction (2q −1)/q2 and quadratic arithmetic for square operands at fixed physical block size.The practical question is which group sizes preserve efficient GPU execution.Source: §1 · p. 2
  • Row-typed rectangular projections use all row types during training and evaluate only the new position’s row during decoding while retaining the standard KV cache.The construction is presented as a Transformer realization of the block interaction rule.Source: §1 · p. 2
  • 6.2–7.8% higher generation throughput across four prompt domains, while the algebraic model scores lower on GSM8K, IFEval, and MBPP.The comparison uses approximately 110M-parameter models trained for 12.3B tokens each.Source: §1 · p. 2

2 PRODUCTS AS ARCHITECTURAL CHOICES

The section treats multiplication as an architectural choice: a fixed table determines which activation and weight slots interact, while the weights are learned. It then defines bilinear rank and uses lower bounds to assess the number of products required by a chosen law.

2.1 A FIXED TABLE, LEARNED WEIGHTS

  • A fixed multiplication table specifies activation-slot and weight-slot interactions and where their results accumulate; the table is architectural, while the weights are learned.With compatible matrix blocks, each retained scalar product becomes a GEMM.Source: §2.1 · p. 3
  • Compatible maps compose within the same family, and a two-sided identity ensures every weight slot can affect an output.Transformer projections use one row of the table per token type, with the full weight bank exposed across row types.Source: §2.1 · p. 3

2.2 HOW MANY PRODUCTS ARE NECESSARY?

  • Bilinear rank is the minimum number of scalar multiplications in an exact bilinear algorithm; for compatible blocks, each multiplication lifts to one GEMM.Additions and fixed linear combinations are counted separately, and the graph construction supports unequal rectangular shapes.Source: §2.2 · p. 3
  • The Alder–Strassen bound applies to a specified multiplication law, so conventional block-product counts are not necessarily exact ranks.Coordinatewise multiplication has rank m but retains only within-slot interactions; the conventional 2 × 2 matrix product has rank 7, not 8.Source: §2.2 · p. 3

3 GRAPH PRODUCTS WITH EXACT COST

The graph construction defines an associative, unital product from vertices and directed edges, then extends it to a family with adjustable size. Larger instances trade arithmetic for feature-group interactions.

3.1 THE GRAPH SPECIFIES THE PRODUCT

  • Each vertex slot contributes one product, while each edge slot combines two cross-slot products under the graph-defined rule.The two-vertex complete graph recovers the earlier rule by omitting the terms that multiply two edge slots.Source: §3.1 · p. 3
  • The graph algebra is associative and unital, has dimension |V| + |E|, and has an edge-element ideal J satisfying J² = 0.Its quotient by J is isomorphic to F^|V|.Source: §3.1 · p. 4

3.2 A FAMILY WITH ADJUSTABLE SIZE

  • The complete directed graph on q vertices retains all q² slots and defines a systematic arithmetic–interaction trade-off as q grows.The two-group example is the smallest instance.Source: §3.2 · p. 4
  • The pilot uses a tensor square of the two-group law, whose exact rank lies in [28, 36], whereas the direct four-group law attains 28.These are distinct interaction rules.Source: §3.2 · p. 4

4 TRANSFORMER PROJECTIONS

The algebraic projection applies a fixed row type to each token and uses the same block product to compose compatible projections. The design preserves independent weight parameters while restricting each token’s feature interactions.

4 TRANSFORMER PROJECTIONS

  • A token selects a row type by a fixed deterministic position schedule, and its output combines the selected input group with the corresponding weight blocks.The schedule can cycle through row types by position.Source: §4 · p. 4
  • The block bank stores KN independent scalars, and compatible projections compose using the same block product with a diagonal identity bank.Across all row types, the weight bank acts injectively.Source: §4 · p. 4
  • More groups reduce active computation while restricting each position’s linear map; the map can still have full rank when its diagonal blocks are invertible.A token’s local weight gradient reaches all diagonal blocks and its source row of off-diagonal blocks; other token types update the remaining rows.Source: §4 · p. 5
  • The pilot replaces only the feed-forward projections, while attention projections retain their usual shapes and gates, activations, normalization, and residual connections keep their usual definitions.The same row law applies to each listed attention projection shape.Source: §4 · p. 5

5 SCALING AND PRACTICAL IMPLEMENTATION

The section separates algebra size, which controls arithmetic reduction, from physical block sizes, which affect execution efficiency. It derives fixed-block scaling, finite-shape screening constraints, and kernel schedules.

5 SCALING AND PRACTICAL IMPLEMENTATION

  • Algebra size controls how much arithmetic is removed, while physical block sizes determine how efficiently the remaining products run.A fixed small algebra gives a constant-factor reduction; allowing its size to grow changes asymptotic cost.Source: §5 · p. 5

5.1 GROWING THE ALGEBRA

  • With fixed physical block size b and q = n/b, the construction has quadratic arithmetic order without requiring scalar-size leaves.At fixed q the count remains cubic, while q = Θ(n^α) gives Θ(n^(3−α)); scaling alone does not establish quality preservation.Source: §5.1 · p. 5

5.2 FINITE RECTANGULAR SHAPES

  • The admissible q must divide feature widths and preserve minimum leaf-GEMM dimensions; a 128-element minimum permits q ≤ 16 at side 2048 and q ≤ 32 at side 4096.Decode needs a separate matrix–vector implementation, and masked tiles at non-aligned sizes can exceed the active arithmetic count substantially.Source: §5.2 · p. 5

5.3 KERNELS

  • The implementation extends endpoint-product schedules to arbitrary q and rectangular widths, with separate forward, decode, and gradient kernels.Tile selection is calibrated per shape, and schedules can adapt to workload while q remains fixed across training, prefill, and decoding.Source: §5.3 · p. 6

6 TRAINING AND INFERENCE

The same row-type schedule governs batched training and one-token decoding, while the usual triangular attention mask preserves autoregressive causality. The algebraic feed-forward projections reduce their counted MACs, but attention and other costs remain.

6.1 ONE ROW ACTION IN BOTH REGIMES

  • The complete-graph row action uses support B(i, j) = {i, j}, and Algorithm 1 applies in both batched training and one-token decoding.Training evaluates all token rows in parallel; decoding evaluates one new row per sequence with the same weights and position-type schedule.Source: §6.1 · p. 6, §6 · p. 6

6.2 TRAINING

  • With the usual triangular attention mask, fixed position types and row-local algebraic projections preserve autoregressive causality.The stated proof is induction over layers.Source: §6.2 · pp. 6–7
  • For a gated MLP with widths D and F, training projection cost falls from 9BDF to 9ρBDF MACs across B token rows.Activations, gates, normalization, and residual operations add costs beyond these projection MACs.Source: §6.2 · p. 6

6.3 ONE-TOKEN INFERENCE

  • The decoder-block cost includes dense attention contractions and algebraic FFN projections, with the dense baseline setting ρ = 1.Attention contractions and the language-model head further dilute FFN savings; the counts exclude memory traffic and elementwise operations.Source: §6.3 · p. 7

7 EXPERIMENTS

The experiments measure algebraic projection kernels on representative Transformer shapes and compare two small language models that differ only in their FFN multiplication law. The pilot model generates faster across four prompt domains but scores lower on all three reported downstream metrics.

7.1 KERNEL SCALING ON TRANSFORMER SHAPES

  • The kernel study benchmarks both FFN projection directions across five representative model and expert shapes, varying token rows M and subdivision q.It uses synthetic BF16 tensors on one H200 NVL, without activation or FFN fusion; reported speedups are kernel-level, not end-to-end Transformer results.Source: §7.1 · p. 7, Table 1 · p. 8

7.2 SMALL PRETRAINING STUDY

  • Both pilot models share the same architecture, training recipe, and data budget; only the FFN projection multiplication law differs.The algebraic model uses the recursive Q⊗2 action, while attention, embeddings, and the language-model head remain dense.Source: §7.2 · p. 8
  • Under CUDA-graph single-token decoding, the algebraic model delivered 6.2–7.8% higher end-to-end throughput than dense across four prompt domains (mean ratio 1.070), while scoring lower on all three reported metrics.The GSM8K gap was 0.98 points, the loose instance-level IFEval gap was 3.4 points, and the MBPP pass@1 gap was 2.8 points.Source: §7.2 · p. 8
  • Generation lengths differ between models, so the throughput measurements describe realized workloads rather than fixed-length generation.For code responses, the mean length is 195.5 tokens for dense and 182.4 for algebraic.Source: §7.2 · p. 8
  • The algebraic model trails by 0.98 points on GSM8K, 3.4 points on loose instance-level IFEval, and 2.8 points on MBPP pass@1.GSM8K uses five-shot prompting; IFEval and MBPP use zero-shot evaluation.Source: §7.2 · p. 8, Table 3 · p. 9

8 RELATED WORK

The paper distinguishes changing the multiplication product from making the same product cheaper, and positions its approach among algebraic layers, structured factorizations, and other efficient Transformer designs.

Fast matrix multiplication

  • Fast matrix multiplication lowers evaluation cost while retaining the target product; this work instead changes the product itself.The passage cites Strassen (1969), Alder & Strassen (1981), Bürgisser et al. (1997), Bläser (2000), and Dupont et al. (2026) in describing that context.Source: §8 · p. 9

Alternative algebras and structured layers

  • Unlike approaches that alter multiplication laws or factorize parameters, this method keeps d_in d_out learned scalars and changes only the multiplication table, selected by certified scalar bilinear rank.The passage groups AlgebraNets and algebraic neural networks with alternative algebra laws, and Hypercomplex, Tensor Train, Monarch, and Block Tensor-Train methods with parameter structure or reduction.Source: §8 · p. 9

Other efficient Transformers

  • Unlike matmul-free representations or content-routed MoE, the method uses fixed type-dependent sparsity with the full weight bank; its runtime experiment keeps attention dense.The passage notes that memory traffic also affects wall-clock attention time (Dao et al., 2022b).Source: §8 · p. 9

9 DISCUSSION AND LIMITATIONS

The discussion limits the evidence to a small, single-run pilot and cautions that throughput gains do not isolate the layer’s effect or establish an equal-quality advantage.

9 DISCUSSION AND LIMITATIONS

  • The experiment covers one recursive FFN law, one model scale, and one training run per model; larger algebras, algebraic attention, larger models, and repeated seeds remain untested.Projection benchmarks use synthetic tensors, and evaluation standard errors quantify task-example uncertainty rather than training-run variation.Source: §9 · p. 9
  • Throughput gains are smaller than the FFN arithmetic reduction because attention, the LM head, sampling, tokenization, and memory traffic also contribute.Generation lengths differ, so fixed-length repeated full-model timings are needed to isolate the layer effect.Source: §9 · p. 9
  • Equal parameter storage and associativity do not establish equal quality or an advantage at equal quality or training time.Associativity guarantees composition, not quality preservation.Source: §9 · p. 9

10 CONCLUSION

The conclusion presents associative multiplication as an architectural choice that can reduce square-product arithmetic while retaining a dense-sized weight bank. The appendices give supporting algebra, gradient, product-count, and evaluation-protocol details.

10 CONCLUSION

  • A growing graph family retains the dense-sized weight bank and reduces square-product arithmetic to quadratic order at fixed physical block size; kernel measurements show an arithmetic–latency trade-off, while the pilot pairs throughput gains with lower downstream scores.The pilot is a separate empirical result from the projection-kernel measurements.Source: §10 · p. 9

A DIRECT ASSOCIATIVITY CHECK

  • The direct associativity check concludes that the product law is associative and that (1, 0) is its unit.The calculation is presented as complementing the basis-element argument in theorem 3.1.Source: A DIRECT ASSOCIATIVITY CHECK · p. 12

B VECTOR–JACOBIAN PRODUCTS

  • Summing vector–Jacobian products over token types gives gradients for every block while preserving the forward multiplication table’s block support.Each of dX and dW has the same matrix-product MAC count as the forward projection.Source: B VECTOR–JACOBIAN PRODUCTS · p. 12

C THE TENSOR-SQUARE CANDIDATE

  • The tensor-square candidate allows some two-step radical interactions that strict Q4 removes, so the two products on the same number of coordinates are not isomorphic.The passage identifies the comparison as 36 versus 28.Source: C THE TENSOR-SQUARE CANDIDATE · p. 12

C.1 RECTANGULAR COUNTS FOR RECURSIVE PRODUCTS

  • For equal group widths, the recursive product uses 36 block products at L = 2 and 6L products generally, with a product ratio of (3/4)^L relative to a dense projection.The rectangular-count discussion also describes block occurrence probabilities using Hamming distance.Source: §C.1 · pp. 12–13

D.1 TRAINING CONFIGURATION

  • Both models were trained from scratch for 100,000 steps on two H100 GPUs, using the same recipe and approximately 12.3B consumed tokens; each has 110,631,168 trainable parameters.Both use BF16 autocast for forward and backward computation, with trainable parameters stored in FP32.Source: §D.1 · p. 13

D.2 GENERATION SPEED MEASUREMENT PROTOCOL

  • Generation speed is measured on four domains with 100 unique prompts each, excluding the first of four runs as warm-up and reporting complete workloads including tokenization and sampling.The retained means use three measurements, with 95% confidence intervals computed using Student’s t-distribution.Source: §D.2 · p. 14

D.3 DOWNSTREAM TASKS EVALUATION PROTOCOL

  • Downstream tasks are evaluated with lm-eval-harness==0.4.9.1 using batch size 1 and up to 512 generated tokens in BF16.The tasks are GSM8K, MBPP, and IFEval; other generation parameters use the harness defaults.Source: §D.3 · p. 14

D.4 COMPLETE DOWNSTREAM RESULTS

The supplied downstream results report metric outputs for GSM8K, MBPP, and IFEval; the remaining passages cover reproducibility, kernel benchmarks, larger products, and attention extensions.

D.4 COMPLETE DOWNSTREAM RESULTS

  • GSM8K outputs were 0.0318423 and 0.0219864, MBPP outputs were 0.066 and 0.038, and IFEval outputs were 0.345324 and 0.310552.The passages do not identify which value in each pair belongs to which model.Source: §D.4 · p. 14, Table 8 · p. 15

D.5 REPRODUCIBILITY STATUS

  • Both models shared the architecture, optimization, data pipeline, and 12.3B-token training budget, differing only in the multiplication law for FFN projections.Training used two NVIDIA H100 GPUs and 100,000 optimizer steps.Source: §D.5 · p. 15

E KERNEL BENCHMARK DETAILS

  • The primary benchmark isolates the product using synthetic BF16 tensors with FP32 accumulation and compares against the faster calibrated cuBLAS/cuBLASLt preference.Measurements use H200 NVL; the report makes no counter-based bottleneck attribution because performance counters were unavailable.Source: E KERNEL BENCHMARK DETAILS · p. 15, Table 10 · p. 16, Table 9 · p. 16

F LARGER PURE PRODUCTS

  • At fixed block size, the larger-product measurements do not establish a quality-preserving model scaling law because q changes across family members.Across the tested eightfold increase in n, the b = 128 Q latency has endpoint log–log slope 2.01.Source: F LARGER PURE PRODUCTS · p. 16, Table 11 · p. 17, Table 12 · p. 17

G ATTENTION EXTENSION AND DETAILED COST ACCOUNTING

  • Autoregressive attention retains triangular masking while using algebraic feature-group selection; cached keys and values are reused for later queries.The provided passages describe the computation but do not report end-to-end decoder measurements.Source: G ATTENTION EXTENSION AND DETAILED… · pp. 17–18

G.1 TRAINING

The paper extends algebraic products to attention and cached decoding, then establishes graph-algebra rank and scaling properties, causality, and data-preparation procedures.

G.1 TRAINING

  • Algebraic attention scores select feature groups by query and key types, with scaling matched to the number of selected coordinates; masked aggregation preserves causal dependence.Proposition G.1 states that algebraic projections, the score, and masked aggregation preserve the property that each hidden state depends only on positions at most p.Source: §G.1 · pp. 18–19

G.2 INFERENCE

  • With equal groups, Q4 reduces the score contraction to 7NpHq/16, while dense value aggregation leaves total attention at 23/32 of dense arithmetic, or 32/23 ≈1.39 speedup.Decode arithmetic and KV-cache storage remain linear in NpHq and NpHkv, respectively; the lower arithmetic count need not yield the same relative speedup because decode can be bandwidth-limited.Source: §G.2 · pp. 20–21

H.1 GRAPH ALGEBRA

  • The graph algebra is associative and unital, and its rank lower bound matches the construction’s upper bound.The proof identifies the edge span as a nilpotent ideal and the quotient as a product of one field per vertex; the Alder–Strassen bound then yields the matching rank.Source: §H.1 · pp. 21–22

H.2 QUADRATIC SCALING

  • For fixed block size, the construction uses 2q2 − q block products, each costing b3 MACs, with n = qb.The edge ideal tensored with Mb(F) is nilpotent and the quotient is a direct product of q copies of Mb(F), giving t(Aq,b) = q for the Alder–Strassen bound.Source: §H.2 · p. 22

H.3 CAUSALITY

  • The causality proof combines row-independent projections with attention restricted to keys and values at positions u ≤ p, then applies induction over layers.The argument concludes that each position depends only on input positions at most p.Source: §H.3 · p. 22

I TRAINING DATA SOURCES

  • Training data use only source-dataset training splits; exact duplicate query–response pairs are reduced to their first occurrence.Near-duplicate benchmark queries and coding responses are screened, and samples above Jaccard similarity 0.80 are removed.Source: I TRAINING DATA SOURCES · p. 23
Loading 2609.32814v1…