Source-linked AI summary
Decode Late, Multiply Once: Rethinking the Dot Product for Quantized Weights
Jonathan Tapson
TL;DR
Low-bit weights repeat only a few values, but conventional dot products still decode and multiply each weight separately. The paper accumulates activations by code before a fused decode-and-multiply step; multiplications fall by n/2^k, while hardware savings depend on sharing the reduction multiplier.
Problem
Low-bit weights in large neural networks reduce memory demand, but dot products still multiply each weight by a higher-resolution activation, repeating multiplications across the small set of weight values.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
The method is most attractive when multipliers and decoders are expensive and accumulators can be made wide cheaply.
Source: §12 · p. 11
Abstract
from arXiv · showhide
Large neural networks are increasingly deployed with 1-4 bit weights and 16- or 32-bit activations, yet their dot products still use one multiplier per element. We show that a length-n dot product with k-bit weight codes can be computed with n+2^k additions and at most 2^k decodes and 2^k multiplications. Each weight code is used directly as an address offset that selects one of 2^k accumulators; each activation is added into the selected accumulator; and the accumulated sums are decoded and multiplied only once, at the end, in a fused decode-and-multiply step. The decoded weight vector is never formed. The refactoring is exact for integer arithmetic, works with integer or floating-point operands and with arbitrary, including nonlinear, decoders, and extends to group-wise scales and to matrix and tensor products. The multiplier count falls by n/2^k, while total arithmetic energy improves by a smaller, bounded factor that we quantify with a cost model. We describe a scatter-accumulate processing element (SA-PE) that replaces the MAC unit in a weight-stationary systolic array, with a load/stream/reduce/drain schedule in which a small, time-shareable multiplier runs only 2^k times per tile. Because decoded weights are not stored, local weight memory shrinks by up to w_d/k for w_d-bit decoded weights. An RTL implementation synthesized for FPGA and compared with a matched MAC array shows that an unshared SA-PE is larger than a MAC PE, and that the saving appears when the reduction multiplier is shared across PEs. Software models confirm exact integer equivalence and floating-point error no worse than the conventional pipeline. We do not claim the underlying identity is new, and we discuss related work on weight sharing and lookup-based kernels.
1 Introduction
Low-bit weights repeat a small set of values, yet conventional dot products decode and multiply each weight separately. The paper instead sums activations by weight code before decoding and multiplication, reducing per-element work while retaining the additions.
1 Introduction
- Multipliers are costly, and k-bit weights repeat only 2^k values across long dot products with higher-resolution activations.The introduction situates this workload in large neural networks using 1–4-bit weights and 16- or 32-bit activations.Source: §1 · p. 1
- The method sums activations by weight code, then fuses decoding and multiplication once per bin instead of performing n multiply-accumulates.It applies to integer or floating-point weights and data variables.Source: §1 · pp. 1–2
- For k-bit codes, the method uses at most 2^k decodes and multiplications and n+2^k additions, reducing multiplications by n/2^k, potentially over 100×.Because the n activation additions remain, energy gains are bounded by the cost ratio of decode–multiply–accumulate to plain accumulation.Source: §1 · p. 2
- The paper extends the identity beyond prior weight-sharing and lookup approaches, while noting that the identity itself is not new.Its stated contributions include floating-point operands, group-scaled decoders, matrix and tensor products, a systolic-array processing element, and validation.Source: §1 · p. 2
2 Background and Notation
- The conventional pipeline decodes each code into a precise weight, multiplies it by its paired activation, and accumulates the products.The code-to-weight mapping may be linear, nonlinear, or an arbitrary table; the paper denotes it with a decoding vector.Source: §2 · p. 2
3 The Add-Before-Multiply Method
The add-before-multiply method partitions activations by their weight codes, accumulating each group before applying its decoded coefficient. Direct code-addressed bins and delayed decoding avoid forming the decoded weight vector, with extensions to group-wise scales and a redundant-bin optimization.
3.1 Refactoring
- Grouping activations by code lets each group be summed first and multiplied once by its shared decoded coefficient.The bin sums reconstruct the original dot product by the distributive law.Source: §3.1 · pp. 2–3
- Decodes and multiplications fall from n to at most 2^k, while additions remain n plus at most 2^k−1; empty bins can be skipped.The trade-off is classifying activations by their corresponding weight code.Source: §3.1 · p. 3
3.2 Weight codes as addresses
- Using each k-bit code as an accumulator address selects its bin directly, avoiding one-hot mask generation and a classifier.For k=2, four codes select four bin registers; Figure 1(b) shows that only the bin sums are held, not the n decoded weights or products.Source: §3.2 · p. 3, Figure 1 · p. 3
3.3 Delayed decoding, and two corollaries
- Decoding is delayed until after accumulation, so the high-precision weight vector is never stored and linear, nonlinear, or table decoders remain compatible.With group-wise decode vectors, the multiplication advantage requires 2^k ≪ g; one bin can also be recovered from the total activation sum when that total is shared across weight rows.Source: §3.3 · p. 4
4 Cost Model
The cost model distinguishes the reduction in operation count from the total arithmetic-energy gain. Although multiplication count falls by n/2^k, energy gain saturates at 1+ρ.
4 Cost Model
- The energy ratio is evaluated assuming bin additions cost the same as conventional accumulation.The model also identifies address-offset formation as a cost, though it is often absorbed in addressing hardware.Source: §4 · p. 4
- The multiplication count falls by exactly n/2^k, but total arithmetic gain saturates at 1+ρ.The energy gain approaches that bound as n grows; larger gains occur when multipliers or lookups are comparatively expensive.Source: §4 · p. 4
- At n = 1024 and k = 2, the model gives G ≈3.0 for ρ = 2 and G ≈8.7 for ρ = 8.For floating-point operands, the passage describes ρ between 2 and 8 as a reasonable exploration range because a multiplier typically costs several times an adder.Source: §4 · p. 4
5 Worked Example
The worked example compares a conventional decoded-weight dot product with add-before-multiply using four code-addressed bins. The example illustrates fewer decodes and multiplications, while Figure 2 gives the broader energy-gain saturation behavior.
5 Worked Example
- The example uses ten activations, four weight codes, and a nonlinear decode vector.The conventional route forms ten decoded FP16 values before multiplying and summing.Source: §5 · pp. 4–5
- Figure 2’s arithmetic-energy-gain curves saturate at 1+ρ once n ≫2^k(1+ρ).The caption specifies Eo = 0 for the plotted curves.Source: Figure 2 · p. 5
- For n = 10 and k = 2, add-before-multiply uses four decodes and four multiplications, versus ten lookups and ten multiplications conventionally.It performs ten bin updates, four further additions, and holds four values; the two results agree.Source: Table 2 · p. 5, §5 · p. 5
6 Matrix and Tensor Products
The refactoring extends from individual dot products to matrix products and tensor contractions by accumulating values by code for each output. The decoded weight matrix is not formed, while bin storage scales with concurrently processed outputs.
6 Matrix and Tensor Products
- For each matrix output, activation values are accumulated into code-indexed bins, then decoded and multiplied after the K-element accumulation; the decoded matrix is never formed.The resulting Y = AQ′ equals the product using decoded weights Q′κ,d = cQκ,d.Source: §6 · p. 5
- The same per-output accumulation by code applies to tensor contractions.The selected numerical values and codes participating in one output element are accumulated together.Source: §6 · p. 5
- Each output element needs 2^k bin accumulators, so total bin storage grows with the number of outputs processed concurrently.The passage identifies this as the design trade-off addressed by the weight-stationary schedule.Source: §6 · p. 5
7 Hardware Realization
The hardware design replaces MAC units with scatter-accumulate PEs in a weight-stationary array. Its phased schedule amortizes a short reduction over streaming, with bin capacity and software scatter behavior shaping the trade-offs.
7.1 The scatter-accumulate processing element
- The SA-PE stores weight codes, routes each activation to its code-selected bin, and multiplies decoded bin sums only during reduction.Its bin bank has 2^k locations, and the reduction unit fuses decoding and multiplication.Source: §7.1 · p. 6
7.2 Weight-stationary systolic array
- Each weight-stationary array row computes one output from C PE slices of length L, with n = CL, then combines their partial dot products.The gain needs L ≫2^k so each bin accumulates enough terms to amortize reduction.Source: §7.2 · p. 6, Figure 4 · p. 7
7.3 Schedule
- The load, stream, reduce, and drain phases add 2^k reduce cycles, a 6% period increase for k = 2, L = 64, or 25% for k = 4.Double-buffered bins can overlap reduction with the next tile’s stream; the reduction multiplier runs only 2^k times per L cycles and can be time-shared.Source: §7.3 · pp. 6–7
7.4 Accumulator width and multi-precision design
- A fixed-point bin needs wact +⌈log2 nmax⌉ bits in the worst case, while the bin bank is the PE’s dominant area and sets much of the design trade-off.The design can parameterize k and gate unused bins; FP32 bins are given as an option for FP16 inputs.Source: §7.4 · p. 7
7.5 Software and vector processors
- On vector hardware with indexed stores, overwrite semantics add zeros during reduction, limiting the gain to decode and multiplication unless scatter-accumulate is available.A code-addressed accumulator file recovers the full operation count; Table 3 covers per-PE resources and Table 4 the multiplication reduction factor.Source: §7.5 · p. 7, Table 3 · p. 8, Table 4 · p. 8
8 Local Memory Reduction
Delayed decoding reduces local weight memory when the baseline stores decoded weights, with the reduction depending on tile length and configuration. Against a code-storing baseline, bins can instead increase memory use.
8 Local Memory Reduction
- The comparison models a PE holding L stationary weights, with decoded-weight width w_d, bin width w_b, and P PEs sharing a decode table.Activation buffers are excluded.Source: §8 · p. 8
- For a 32-PE row with 1024-weight slices, 64 KiB of decoded weights becomes 8.8 KiB at k = 2 or 19 KiB at k = 4.Using fixed-point rather than FP32 bins, or sharing the decode table across 32 PEs, changes the reduction ratio by at most about 5%.Source: §8 · p. 8
- The memory comparison assumes the conventional design stores decoded weights; against a code-storing baseline, scatter-accumulate uses 6–12% more memory for bins.The saving also vanishes at k = 4 when L = 64.Source: §8 · p. 8
9 RTL Implementation and Sizing
The RTL sizing comparison finds that SA-PEs cost more when their multipliers remain local, while sharing the reduction multiplier yields projected savings. Results also expose k-dependent bin and scheduling costs and are bounded to an open-source FPGA flow.
9 RTL Implementation and Sizing
- Each SA-PE stores weight codes and accumulates activations in 2^k signed bins; one decode LUT is shared across the array, and a registered adder chain sums row partial sums.The RTL uses a six-state controller; bins need at least w_act + ceil(log2 L) bits, with one additional guard bit in the implementation.Source: §9 · p. 8
- The self-checking testbench found no mismatches across eight random tiles, but sizing results are from an open-source FPGA flow, not ASIC area, power, or Vivado results.Shared-engine figures are projections from synthesized components, not a complete shared-design synthesis.Source: §9 · pp. 9–10
- A 4×3 array with 12 PEs needs 2368 LUTs, 1807 FFs, and 12 DSP48 for SA, versus 1335 LUTs, 719 FFs, and 12 DSP48 for MAC.The unshared SA-PE is larger because of its bin bank, partial-sum register, and bin-select multiplexer, while still containing a multiplier.Source: §9 · p. 9
- Multiplier sharing serves at most L/2^k PEs—16 at k = 2 or 4 at k = 4 for L = 64—and overlapping reduction with the next tile's stream requires double-buffered bins.Without that overlap, the reduce phase grows to σ2^k cycles; double-buffering adds about 92 flip-flops per PE.Source: §9 · p. 9
- At k = 4, an SA-PE needs 359 LUTs and 412 FFs versus 119 LUTs and 39 FFs for a MAC PE; serial reduction takes 25% of a 64-cycle stream, versus 6% at k = 2.The bin bank grows with 2^k.Source: §9 · p. 9
- With fabric multipliers shared across 16 PEs, per-PE cost falls from 819 LUTs (MAC) to 179, a factor of 4.6.The projected shared engine adds about 3 LUTs per PE; DSP use falls from one per PE to 1/16.Source: §9 · p. 9, Table 6 · p. 10
10 Evaluation by Software Models
Software models report integer exactness and floating-point error no worse than the conventional pipeline at equal accumulator width. Tiled GEMV emulations also show near-reference numerical agreement, but are not silicon or trained-network measurements.
10 Evaluation by Software Models
- At equal accumulator width, the new method is no less accurate than the conventional method and is more accurate in the FP16 setting.With FP32 bins, error is roughly an order of magnitude below the FP32 conventional pipeline; the model attributes this to about n+2^k rather than 3n roundings.Source: §10 · p. 10
- Across 30 random GEMV configurations, the maximum FP64 absolute difference from the reference was 4.3×10^-14, and an INT64 test was integer-exact.A 4096×4096 GEMV with k = 4 and 1024-element slices used 64× fewer multiplications.Source: §10 · p. 10
- The reported evaluations are software emulations on synthetic data, not measurements on silicon or trained networks; end-to-end accuracy and energy remain to be confirmed on real hardware and models.Source: §10 · p. 10
11 Discussion
The discussion situates the method among prior approaches that exploit repeated weights, while emphasizing its generality and deployment conditions. Its benefits depend on the workload, hardware costs, and memory baseline.
11 Discussion
- Weight-sharing accelerators and UCNN already exploit repeated weights, while LUT-GEMM, T-MAC, and BitNet b1.58 provide other low-bit multiplication alternatives; the paper does not claim the identity is new.The formulation supports integer or floating-point operands, linear or nonlinear decoders, direct code-addressed accumulation, and a weight-stationary PE implementation.Source: §11 · p. 11
- The method helps when 2^k is much smaller than n (or group size g), multiplication and decoding matter to cost, and address-selected accumulation is cheap.For memory-bandwidth-bound inference, reduced arithmetic alone does not raise throughput; saved area and switching power may instead be spent on larger buffers or more PEs.Source: §11 · p. 11
- The bin bank is the dominant PE area cost, and consecutive activations with the same code can cause a read-after-write hazard that requires forwarding or interleaved bins.For large k, returns diminish as 2^k approaches n; local-memory savings apply only against a baseline storing decoded weights.Source: §11 · p. 11
- For linearly coded weights, bit-plane decomposition uses k conditional passes over activations instead of one pass, and it does not handle nonlinear decoders without an extra step.Source: §11 · p. 11
12 Conclusion
The refactoring reduces multiplier and decode counts while preserving n+2^k additions, and the SA-PE exposes hardware trade-offs whose benefits depend on the relative costs of multipliers, decoders, and accumulators.
12 Conclusion
- The refactoring reduces multipliers and decodes from n to at most 2^k, eliminates the decoded weight vector, and uses n+2^k additions.Activations are added into code-addressed accumulators before multiplication.Source: §12 · p. 11
- The SA-PE uses a 2^k-cycle tile reduction and a small time-shared multiplier, with benefits strongest when multipliers and decoders are expensive and wide accumulators are cheap.The arithmetic gain is bounded by the cost ratio of a decode–multiply–accumulate to a plain accumulate.Source: §12 · p. 11
- Further work includes ASIC synthesis of the SA-PE and shared reduction engine, plus end-to-end accuracy evaluation on quantized models.Source: §12 · p. 11