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

Ilya Koziev; Ivan Oseledets

cs.LGSep 26, 2026

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

Authors: Ilya Koziev, Ivan Oseledets

Organizations: DAIMLD, Moscow, Russia · Artificial Intelligence Research Institute, Moscow, Russia

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.

Figures & tables

Model shape	$M$	$q_{\ast}$	Block $(m,k,n)$	Dense $\mu$ s	Q $\mu$ s	Speedup
Qwen3-1.7B	2048	$32$	$(64,64,192)$	75.7	24.9	$3.04\times$ / $2.84\times$
Qwen3-4B	2048	$32$	$(64,80,304)$	160.6	51.1	$3.14\times$ / $2.94\times$
Qwen3-8B	2048	$32$	$(64,128,384)$	320.7	63.6	$5.04\times$ / $4.52\times$
Qwen3-30B-A3B expert	2048	$16$	$(128,128,48)$	13.2	8.4	$1.57\times$ / $1.30\times$
DeepSeek-V3 expert	2048	$16$	$(128,448,128)$	82.3	28.3	$2.91\times$ / $2.47\times$
Qwen3-32B	2048	$32$	$(64,160,800)$	849.2	167.8	$5.06\times$ / $4.86\times$

Table 1: Pure expansion projections, BF16 on H200 NVL. The selected

q_{\ast}

has the lowest warm Q-kernel median in the tested grid:

\{4,8,16,32,64\}

for the first five shapes and

\{32,64,128,256\}

for Qwen3-32B. Block dimensions

(m,k,n)=(M/q_{\ast},K/q_{\ast},N/q_{\ast})

show where subdivision stops, before GPU-tile padding. Times are microseconds; speedups are kernel speedups (dense kernel / algebraic kernel), reported for warm / cache-flushed runs.

\dagger

marks the largest tested

q

Domain	Dense tok/s	Algebraic tok/s	Gain
Code	987.8	1054.5	6.8%
Math	991.4	1060.6	7.0%
QA	958.6	1033.1	7.8%
WMT ru–en	985.9	1047.1	6.2%

Table 2: Measured generation throughput. Gain is the relative increase over the dense model within each domain.

Task	Metric	Dense	Algebraic
GSM8K	EM, flexible	3.18	2.20
IFEval	Instance, loose	34.5	31.1
MBPP	pass@1	6.60	3.80

Table 3: Downstream scores in percent. Higher is better. The appendix reports the complete metric set and evaluation standard errors.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Quantity	Value
Decoder blocks	12
Model width	768
FFN width	1536
Attention heads	32
Context length	1536
Vocabulary size	50,257

Appendix

Table 4: Training configuration shared by both models.

Figure 1: Evaluation loss curves for the baseline and associative algebra LMs.

Domain	Mean prompt	Mean response	Measurements	Mean speed	95% CI margin
	tokens	tokens	tok/sec	tok/sec	of error
Code	42.9	195.5	987.5, 988.2, 987.6	987.8	1.0
Math	54.3	223.8	990.1, 993.7, 990.3	991.4	5.0
QA	17.1	92.6	954.0, 962.8, 959.0	958.6	11.0
WMT ru–en	263.8	190.0	988.0, 986.0, 983.7	985.9	5.2

Appendix

Table 5: Generation speed measurements for the baseline model. Each domain contains 100 unique prompts. The first of four measurement runs was excluded as a warm-up; the three retained runs are shown in the Measurements column.

Domain	Mean prompt	Mean response	Measurements	Mean speed	95% CI margin
	tokens	tokens	tok/sec	tok/sec	of error
Code	42.9	182.4	1055.5, 1053.7, 1054.2	1054.5	2.2
Math	54.3	227.8	1058.9, 1061.9, 1060.9	1060.6	3.8
QA	17.1	110.8	1031.9, 1034.6, 1032.6	1033.1	3.5
WMT ru–en	263.8	204.9	1047.3, 1048.0, 1046.0	1047.1	2.6

Appendix

Table 6: Generation speed measurements for the associative algebra model. Each domain contains 100 unique prompts. The first of four measurement runs was excluded as a warm-up; the three retained runs are shown in the Measurements column.

Domain	Relative speedup (%)
Code	6.8
Math	7.0
QA	7.8
WMT ru–en	6.2

Appendix

Table 7: Associative algebra model generation speed relative to the baseline model.

Task	Metric	Dense	Algebraic
GSM8K	EM, flexible-extract	0.0318 $\pm$ 0.0048	0.0220 $\pm$ 0.0040
MBPP	pass@1	0.0660 $\pm$ 0.0111	0.0380 $\pm$ 0.0086
IFEval	Instruction-level loose accuracy	0.3453	0.3106

Appendix

Table 8: Complete downstream results on the original

[0,1]

scale. EM denotes exact match.

Model shape	$D$	$F$	$M$	Dense $\mu$ s	Algebra $\mu$ s	Speedup (warm / flushed)
Qwen3-1.7B	2048	6144	1	30.2	8.7	$3.45\times$ / $2.46\times$
Qwen3-1.7B	2048	6144	2048	273.7	107.4	$2.55\times$ / $2.45\times$
Qwen3-4B	2560	9728	1	49.1	10.4	$4.74\times$ / $3.21\times$
Qwen3-4B	2560	9728	2048	539.3	193.8	$2.78\times$ / $2.68\times$
Qwen3-8B	4096	12288	1	83.6	12.6	$6.64\times$ / $4.12\times$
Qwen3-8B	4096	12288	2048	1031.9	247.3	$4.17\times$ / $3.92\times$

Appendix

Table 9: Complete SwiGLU forward at fixed

q=32

, BF16 on H200 NVL. Both implementations merge gate/up. Times are warm-replay medians in microseconds. The last column reports the separately measured cache-flushed speedup. These are isolated FFNs on public model shapes.

Model shape	Direction	Dense	Algebra	Speedup
Qwen3-1.7B	up	225.6	177.0	$1.27\times$
Qwen3-1.7B	down	223.8	127.0	$1.76\times$
Qwen3-4B	up	455.9	341.6	$1.33\times$
Qwen3-4B	down	465.9	280.2	$1.66\times$
Qwen3-8B	up	912.0	465.0	$1.96\times$
Qwen3-8B	down	954.0	372.6	$2.56\times$

Appendix

Table 10: Forward plus activation and weight gradients,

M=2048

q=32

, warm replay. The dense library preference is calibrated separately for each of its three GEMMs. Times are microseconds.

Model shape	$D$	$F$	$M$	Dense $\mu$ s	Algebra $\mu$ s	Speedup (warm / flushed)
Qwen3-1.7B	2048	6144	1	9.5	3.8	$2.51\times$ / $1.89\times$
Qwen3-1.7B	2048	6144	2048	75.7	24.9	$3.04\times$ / $2.84\times$
Qwen3-4B	2560	9728	1	14.0	4.1	$3.43\times$ / $2.72\times$
Qwen3-4B	2560	9728	2048	160.6	51.1	$3.14\times$ / $2.94\times$
Qwen3-8B	4096	12288	1	30.7	4.4	$7.07\times$ / $4.14\times$
Qwen3-8B	4096	12288	2048	320.7	63.6	$5.04\times$ / $4.52\times$

Appendix

Table 11: Pure

D\to F

projection: optimized dense GEMM versus the algebraic product at fixed

q=32

, BF16 on H200 NVL. Times are warm-replay medians in microseconds. The last column gives warm / cache-flushed speedup. No activation or FFN fusion is included.

$K\to N$	$M$	$q$	Block $(m,k,n)$	Dense ms	Q ms	Speedup
$5120\to 25600$	2048	32	$(64,160,800)$	0.849	0.168	$5.06\times$ / $4.86\times$
		64	$(32,80,400)$	0.829	0.232	$3.58\times$ / $3.75\times$
		128	$(16,40,200)$	0.779	0.248	$3.15\times$ / $3.25\times$
		256	$(8,20,100)$	0.789	0.266	$2.97\times$ / $3.19\times$
$5120\to 25600$	8192	32	$(256,160,800)$	3.290	0.583	$5.65\times$ / $5.88\times$
		64	$(128,80,400)$	3.290	0.523	$6.30\times$ / $6.68\times$

Appendix

Table 12: Qwen3-32B projection shapes at four subdivision sizes. Block dimensions

(m,k,n)=(M/q,K/q,N/q)

precede GPU-tile padding. Times are warm medians in milliseconds; bold Q times are the lowest among the four tested

q

values for that shape. The last column gives warm / cache-flushed speedup.

$n$	$b$	$q$	Dense ms	Q ms	Speedup (warm / flushed)
4096	128	32	0.210	0.044	$4.81\times$ / $4.47\times$
4096	256	16	0.205	0.058	$3.56\times$ / $3.19\times$
8192	128	64	1.773	0.166	$10.69\times$ / $10.63\times$
8192	256	32	1.729	0.225	$7.70\times$ / $7.42\times$
16384	128	128	13.881	0.689	$20.15\times$ / $19.95\times$
16384	256	64	13.999	0.991	$14.13\times$ / $14.08\times$

Appendix

Table 13: Fixed-block-size square products. Subdivision stops at

b\times b

blocks; algebra size grows as

q=n/b

. Warm medians are milliseconds; bold Q times are the lower of the two tested block sizes for that

n

. The final column includes the separate cache-flushed measurement.

Law	$\rho$	Forward	Training
$\mathcal{Q}_{2}^{\otimes 2}$	$9/16$	$1.280\times$	$1.333\times$
$\mathcal{Q}_{4}$	$7/16$	$1.391\times$	$1.474\times$

Appendix

Table 14: Balanced-sequence arithmetic ceilings for structured

QK^{\top}

and dense

PV

Quantity	Dense	$\mathcal{Q}_{q}$
KV cache scalars	$2N_{p}H_{kv}$	$2N_{p}H_{kv}$
Projection MACs	$C_{\rm proj,dense}^{\rm dec}$	$\rho_{q}C_{\rm proj,dense}^{\rm dec}$
Score MACs	$N_{p}H_{q}$	$\rho_{{\rm score},{\rm dec}}^{(i)}N_{p}H_{q}$
Value MACs	$N_{p}H_{q}$	$N_{p}H_{q}$

Appendix

Table 15: One-token decode at one layer. Projection entries assume equal algebra groups; attention entries hold for the current cache composition.

Dataset	Records
GSAI-ML/ReFusion	2881860
openbmb/UltraData-SFT-2605	2651052
MBZUAI/LaMini-instruction	2540109
OLMo-Coding/starcoder-python-instruct	1087321
nvidia/Nemotron-Post-Training-Dataset-v2	1145725
nvidia/Nemotron-RL-knowledge-mcqa	611930

Appendix

Table 16: Imported records by dataset, as recorded for the training mixture.

Transformer

Transformers are neural architectures that use attention to model relationships among sequence elements in language, vision, and scientific data.

See all 528 papers

Reduced Matrix Multiplication: Input-Adaptive Matrix-Product Reduction for LLM Inference
Aug 13, 2026Zixuan Lan, Yanhong Li, Jiawei ZhouInference-Time Optimization LLM Inference Acceleration
University of Chicago · Independent Researcher · Stony Brook University
CODA: Rewriting Transformer Blocks as GEMM-Epilogue Programs
May 19, 2026Han Guo, Jack Zhang, Arjun Menon +4GPU Kernel Optimization GPU Acceleration
1Massachusetts Institute of Technology · *Part of this work was done at Together AI. · 2Princeton University +2
Compressing Transformer Language Models via Matrix Product Operator Decomposition: A Case Study on PicoGPT
Mar 30, 2026Younes Javanmard, Tanmoy Pandit, Masoud MardaniModel Compression Tensor Decomposition
Institut für Theoretische Physik, Leibniz Universität Hannover, Appelstraße 2, 30167 Hannover, Germany · VTT Technical Research Centre of Finland, Tietotie 3, Espoo, Finland · National High Magnetic Field Laboratory, Tallahassee, FL 32310, USA

Aug 13, 2026J/K move · Enter open · S save

Reduced Matrix Multiplication: Input-Adaptive Matrix-Product Reduction for LLM Inference

Zixuan Lan, Yanhong Li, Jiawei Zhou

University of Chicago · Independent Researcher · Stony Brook University

Inference-Time Optimization LLM Inference Acceleration Adaptive Computation

Open paper AskPDF arXiv

Transformer-based language models achieve strong performance but incur substantial inference cost due to repeated high-dimensional matrix multiplications. We propose Reduced Matrix Multiplication (RMM), a training-free, input-adaptive inference method that reduces Transformer matrix products by selecting informative slices along their contraction dimensions, without modifying model weights. Under a simple retention-ratio control, RMM provides a smooth and predictable accuracy-efficiency trade-off. Across language models ranging from 1B to 70B parameters, we find that reduction tolerance depends on the model family, task, component, and retention ratio, although it often improves with model scale. Under moderate reduction, RMM remains robust across the evaluated discriminative, autoregressive generation, and long-context settings. We further show that the same principle extends to multimodal vision-language inference. Mechanistic ablations reveal a structural asymmetry within Transformers: attention-side computations are substantially more reducible than MLP components. Finally, wall-clock benchmarks with custom kernels on an NVIDIA A100 show that these computational savings can translate into practical runtime gains, especially at longer sequence lengths. Together, these results position RMM as a scalable direction for input-adaptive inference-time optimization.

Abstract

Transformer

Explore similar work

Reduced Matrix Multiplication: Input-Adaptive Matrix-Product Reduction for LLM Inference

CODA: Rewriting Transformer Blocks as GEMM-Epilogue Programs

Compressing Transformer Language Models via Matrix Product Operator Decomposition: A Case Study on PicoGPT