Source-linked AI summary
Product-Aware Deterministic Rounding for Quantized Matrix Multiplication
Piyush Sao, Narasinga Miniskar, Pedro Valero-Lara, Keita Teranishi, Sudip Seal
TL;DR
Scalar rounding choices can interact through matrix products, while entrywise rules ignore those interactions. The paper coordinates admissible adjacent-level choices through product-preserving reduction and conditional-expectation completion. It gives a rank-parameterized approximation scheme, while unrestricted rank rules out a polynomial-time guarantee for every fixed ε>0 unless P=NP.
Problem
Entrywise rounding ignores how scalar errors can cancel in matrix products, while exhaustive search for the best product choice requires exponentially many binary patterns.
Source: §1 · pp. 1–2Method
The dynamic construction preserves the relaxed product while reducing unresolved choices, then fixes remaining choices by conditional expected error.
Source: §3.2 · p. 6Results
A rank-parameterized approximation scheme is given, while unrestricted rank rules out a polynomial-time guarantee for every fixed ε>0 unless P=NP.
Source: §8 · p. 21Takeaways & Limitations
Retaining cancellation in one rounded activation copy shared across output blocks remains an open problem.
Source: §1 · p. 2The Digits study uses a small fitted linear model and one local-search start; model-wide accuracy and speed require experiments on frozen transformer projections and complete quantized networks.
Source: §8 · p. 21
Abstract
from arXiv · showhide
Scalar rounding decisions interact through matrix multiplication. We study deterministic product-aware rounding after scales, clipping bounds, and grids are fixed, with each active scalar choosing between adjacent levels. For dynamic activation rounding, null-space reduction preserves the relaxed product while leaving at most $r$ fractional decisions, where $r$ is the rank of the active gap-weighted weight block. Conditional-expectation completion gives a deterministic polynomial-time algorithm with squared product error at most $ \mathrm{OPT}_{\mathrm{dyn}}+r\nu_{\max}^2/4$, where $\mathrm{OPT}_{\mathrm{dyn}}$ is the best admissible error and $\nu_{\max}$ is the largest row norm of that block. For reusable static weights, the exact expected product-loss metric is the uncentered input second moment with fixed output bias; free bias recalibration yields the centered covariance. Exact optimization is NP-hard even at rank one. In balanced blocks with $K=1024$ and $r=16$, conditional- expectation completion attains a dither-normalized median error of $0.010$, compared with $0.899$ for round-to-nearest. Clipping-aware initialization reduces median normalized error by a factor of $43.4$ at ten-percent clipping. Held-out Digits experiments show that retaining the input mean or correcting the output bias improves median product error over round-to-nearest in all four tested bit-width and calibration-size settings.
1. Introduction
Scalar rounding decisions can interact through matrix multiplication, making product-aware choices different from independent entrywise rounding. The paper develops dynamic and static rounding analyses, complexity results, and empirical tests under fixed scales, clipping bounds, and grids.
1. Introduction
- Dynamic rounding uses product-preserving null-space moves and conditional-expectation completion to achieve squared error at most OPT_dyn + rν_max^2/4.Here r is the active gap-weighted block’s rank, and ν_max its largest row norm.Source: §1 · p. 2
- For reusable static weights, fixed output bias gives the uncentered input second moment as the exact loss metric, while free bias recalibration yields centered covariance.Exact optimization remains NP-hard even at rank one.Source: §1 · p. 2
- Balanced synthetic blocks show coordinated error decreasing as row count grows relative to rank, while concentrated row energy weakens the certified bound.Clipping-aware initialization cuts median normalized error by a factor of 43.4 at ten-percent clipping.Source: §1 · p. 2
- On Digits, centering without bias correction gives higher median held-out product error than round-to-nearest in every tested configuration.The fixed-bias metric retains the mean-error term that free bias recalibration absorbs.Source: §1 · p. 2
- Retaining product-aware cancellation in one rounded activation copy shared across output blocks remains an open problem.The stated next problem concerns reuse across blocks.Source: §1 · p. 2
2. Fixed-grid rounding choices
With grids and clipping bounds fixed, active scalars have adjacent-level choices, while fixed coordinates contribute forced errors. The section defines the resulting error representation and the independent-rounding references used to compare coordinated choices.
2.1 Adjacent-level feasible sets
- An active scalar between adjacent levels has an offset fraction θ, and choosing the lower or upper level gives error d(χ − θ); fixed and clipped coordinates contribute forced errors.The affine error representation accommodates unequal step sizes.Source: §2.1 · p. 3
- The same affine choices model dynamic errors for one observed activation row and weight block, or static errors for a reusable weight column across an input distribution.Squared Euclidean output error is the product MSE used for calibration.Source: §2.1 · p. 3
2.2 The independent-decision references
- Independent same-grid stochastic rounding chooses the upper level with probability θ, yielding unbiased active errors; uniformly averaged offsets on a common step give a variance factor of 1/6.The dither reference assumes no clipping and gives independent errors uniform on each step’s centered interval.Source: §2.2 · pp. 3–4
- For an unclipped subtractive-dither reference, independent zero-mean errors eliminate cross terms when the squared norm is expanded.The dithered errors are uniform on [−∆k/2, ∆k/2] and independent of the input.Source: §2.2 · p. 4
- The constructive guarantee is additive relative to the binary optimum; same-grid stochastic rounding has expected error at least that optimum, while dither is unordered with both.With clipping, the forced offset stays in the objective and dither serves only as a normalization.Source: §2.2 · p. 4, Figure 2 · p. 5
2.3 Notation
- Table 1 covers fixed-grid setup and dynamic-result notation; static and hardness symbols are defined where they first appear.The notation table’s stated scope distinguishes the later static and hardness sections.Source: Table 1 · p. 5
3. Dynamic product-aware rounding
Dynamic rounding coordinates scalar choices to reduce product error while respecting fixed grids and clipping. A low-rank reduction preserves the relaxed product, and deterministic completion yields an additive guarantee.
3.1 The binary least-squares objective
- Rounding choices form a binary least-squares problem because each admissible up/down decision contributes a weighted row error to the product.The choices are coordinated to exploit cancellation among those contributions.Source: §3 · p. 5, §3.1 · pp. 5–6
3.2 A deterministic additive approximation
- Null-space moves preserve the relaxed product and leave at most r fractional decisions, where r is the rank of the active block.The reduction proceeds along directions in the null space until coordinates reach endpoints.Source: §3.2 · p. 6
- Conditional-expectation completion is deterministic and polynomial-time, with squared error bounded by the binary optimum plus r times one quarter of the largest squared row norm.The bound follows by completing the at most r remaining fractional decisions.Source: §3.2 · p. 8
- Starting from the clipped target preserves its product image, while optimizing the continuous start can let active coordinates compensate for forced clipping error.The target-start guarantee includes the squared forced error plus an additive rank-dependent term.Source: §3.2 · p. 8
3.3 Comparing the certificate with independent-rounding scales
- The certificate is below the dither reference when row energy spans more than 3r effective rows, but this sufficient condition is not necessary.A heavy-row enumeration refinement trades additional running time for accuracy; reuse across multiple output blocks requires broader error control and remains open.Source: §3.3 · p. 9, Extensionstowardreusablerounding · p. 10
4. Static reusable rounding
Static rounding chooses one weight matrix for future inputs, so its product-loss metric depends on whether output bias can be recalibrated. The resulting objectives connect activation-weighted reconstruction to product-aware rounding.
4.1 The reusable objective
- Independent minimization by output column is valid when the feasible set factors by column, with shared scales, clipping bounds, or transforms fixed beforehand.The quadratic loss identity also holds when the second-moment matrix is singular.Source: §4.1 · p. 10
- With fixed or absent output bias, expected product loss uses the uncentered input second moment; free bias recalibration instead yields centered covariance.The two metrics coincide when the input mean is zero.Source: §4.1 · pp. 10–11, §4 · p. 10
4.2 Relation to activation-weighted reconstruction
- Activation-weighted reconstruction uses the empirical second moment, and factoring that moment reduces the static objective to the Euclidean form used by dynamic rounding.The paper gives a per-column conditional-expectation guarantee relative to the continuous relaxation; low-rank approximation can discard directions that still contribute to full product loss.Source: §4.2 · p. 11
5. Complexity of exact product-aware rounding
Exact product-aware rounding remains computationally hard despite low rank: even rank-one zero-error decision is NP-complete. Unrestricted positive-semidefinite quadratic loss is strongly NP-complete.
5.1 Weak NP-completeness at rank one
- Rank-one zero-error rounding is weakly NP-complete by reduction from PARTITION, including the static metric M = vv⊤.The reduction encodes equal-sum partitioning as a zero-error sign assignment.Source: §5.1 · p. 12
- Rank supports polynomial-time approximation guarantees, but exact zero-error decision with XP or fixed-parameter tractability in rank would imply P = NP.An additive guarantee avoids requiring zero error whenever the optimum is zero.Source: §5.1 · p. 12, §5.2 · p. 13
5.2 Strong NP-completeness of the PSD threshold problem
- Threshold minimization for a general positive-semidefinite quadratic loss is strongly NP-complete, and the same reduction gives strong hardness for dynamic blocks of unrestricted rank.The reduction maps an unweighted MAX-CUT instance to the rounding objective.Source: §5.2 · p. 13
6. Experiments
Controlled synthetic blocks test dynamic product cancellation, row-energy imbalance, and clipping compensation, while held-out Digits inputs test static rounding’s bias convention. Across these settings, coordinated completion reduces product error, but the Digits comparison depends on whether output bias is fixed or recalibrated.
6.1 Dynamic low-rank blocks
- In balanced blocks, CE error decreases as row count grows at fixed rank; for r = 16, its median ratio falls from 0.166 at K = 64 to 0.010 at K = 1024.For r = 4, the ratio falls from 0.042 at K = 64 to 0.003 at K = 1024, and measured errors lie below the certificate in the reported examples.Source: §6.1 · p. 14, Table 3 · p. 15, Figure 4 · p. 16
- At K = 1024 and r = 16, CE attains 0.010 dither units versus 0.899 for RTN in fixed-width balanced blocks.The measured cost is 75.916 ms per target in the Python/NumPy reference implementation, not an optimized-kernel throughput measure.Source: §6.1 · p. 14, Table 5 · p. 15
6.2 Row-norm imbalance
- For r = 4, increasing row-norm imbalance from α = 0 to α = 2 raises the CE certificate ratio from 0.047 to 11.087, while the realized ratio rises from 0.010 to 0.604.The certificate can fail to certify a gain that the measured solution attains; for r = 1, realized error first decreases and then increases as imbalance grows.Source: §6.2 · p. 16, Table 6 · p. 16, Figure 5 · p. 18
6.3 Fixed offsets from clipping
- At ten-percent clipping, QP initialization lowers median squared error from 9.597 to 0.208, or from 0.450 to 0.010 dither units.The continuous relaxation cancels the fixed offset to floating-point precision, leaving the rounding of at most four fractional coordinates as the remaining error.Source: §6.3 · p. 17, Table 7 · p. 17
6.4 A mean-term diagnostic on Digits
- Across all four tested bit-width and calibration-size settings, centered fixed-bias rounding has median held-out/RTN ratios above one, while the intervals contain one.Ratios are 1.264, 1.250, 1.148, and 1.260; the experiment is a diagnostic of the mean-term mechanism, not a population-level comparison.Source: §6.4 · p. 18
- With 128 calibration examples, centered-plus-bias versus RTN-plus-bias ratios are 0.869 at three bits and 0.667 at four bits.At four bits, split-median MSE is 0.0652 for RTN, 0.0447 for RTN-plus-bias, and 0.0307 for centered-plus-bias; the paired comparison gives both methods the same bias freedom.Source: §6.4 · pp. 17–18
7. Related work
The related work frames product-aware rounding through discrepancy, directional control, reusable-weight reconstruction, and alternative quantization geometries. The paper distinguishes its fixed-grid objectives and feasible sets from prior methods.
Balancing the product image
- Dynamic rounding is fixed-target Euclidean discrepancy, unlike linear discrepancy’s maximization over fractional targets; its reduction uses the linear-dependence geometry behind iterated rounding.Conditional expectation selects endpoints without increasing expected squared error, while dependent rounding studies prescribed marginals and negative correlation.Source: §7 · p. 20
Directional control
- Directional-control methods bound signed sums in convex bodies, whereas this work specializes directional control to product errors and tests the spectral-tail condition needed for reuse.Source: §7 · p. 20
Learning reusable weights
- AdaRound and GPTQ coordinate reusable weight decisions using calibration data [1] [2], while the static identity specifies the quadratic loss matching a linear layer’s bias convention.Babai-style lattice search addresses unrestricted closest-point distance [21, 12]; it does not by itself enforce the paper’s binary adjacent-level choices.Source: §7 · p. 20
8. Limitations and open problems
The paper identifies deployment cost, calibration transfer, and unresolved joint-rounding guarantees as boundaries on its product-aware rounding results.
Rounding cost and tile reuse
- The dynamic guarantee concerns accuracy, not throughput: null-space updates, rank computation, and clipping-aware initialization add work beyond the row–block product.For B blocks, charging the full rounding cost to each gives O(BCround) work; streaming reduces live storage to O(K) but retains repeated rounding and tile movement.Source: §8 · p. 21
Calibration and evaluation scope
- Digits tests isolate mean-error effects in a small fitted linear model with one local-search start, not model-wide accuracy or speed.The exact static loss identity assumes a known input distribution, while empirical calibration moments must transfer to future inputs; broader evaluation requires frozen transformer projections and complete quantized networks.Source: §8 · p. 21
Additive approximation
- For arbitrary fractional targets and fixed offsets, enumerating high-energy rows gives an additive approximation, but the sufficient effective-row condition is not necessary.The stated guarantee is OPTdyn + εD(V) + η in 2⌈3r/ε⌉ times polynomial work.Source: §8 · p. 21
Complexity barriers
- Unrestricted rank precludes polynomial-time additive approximation for every fixed ε > 0 unless P = NP, while exact zero-error decision is hard even at rank one.Rank-only XP or FPT exact algorithms would imply P = NP; the rank-one all-sign case is number partitioning, and the cited worst-case balancing results use a different feasible set.Source: §8 · pp. 21–22
Reusable dynamic rounding
- A reusable rounded activation tile must control multiple output blocks jointly; separate low ranks and large effective row counts are insufficient.The Hadamard example has rank-one blocks and effective row count K, yet at least one block exceeds its reference.Source: §8 · p. 22
Verifiable spectral tails
- A reusable-rounding theory still needs a population tail bound for the same output that satisfies the head guarantee.The diagnostic finds finite-draw Gram–Schmidt tail estimates above dither and exact independent same-grid references; the paper leaves a valid population scale open.Source: §8 · p. 22
9. Conclusion
The paper concludes that coordinated rounding can reduce product error while identifying reuse as the next practical challenge. It extends the analysis with randomized directional guarantees and a conditional head–tail estimate whose tail condition remains to be verified.
9. Conclusion
- The results identify when coordinated rounding can provably reduce product error, but a shared activation tile must preserve cancellation across blocks while accounting for rounding time and movement.The paper presents a randomized construction for directional concentration and a separate spectral-tail estimate; its diagnostic finds empirical operators above both independent-rounding references.Source: §9 · p. 22, Appendix A · p. 24
A.1 A randomized Gram–Schmidt guarantee
- A Gram–Schmidt walk rounds directly from a fractional start and gives sub-Gaussian control in specified directions, with a union bound scaling logarithmically in their count.This directional control is proposed toward shared rounding for output blocks; turning it into that shared rounding remains open.Source: §A.1 · p. 24
A.2 A conditional spectral head–tail estimate
- The conditional head–tail estimate combines a low-rank head bound with a separate tail hypothesis that must hold for the same Gram–Schmidt output.Independent zero-mean errors with per-coordinate second moment σ² satisfy the stated isotropy condition; the walk’s projected second moment needs a separate bound.Source: §A.2 · pp. 24–25
A.3 Spectral-tail diagnostic: estimates exceed the dither scale
In the tested full-rank metrics, Gram–Schmidt tail operators exceed both dither and exact same-grid independent-rounding references.
Design
- The diagnostic tests full-rank metrics because the exact-rank blocks have zero spectral tail.It uses K = 32, head ranks 2, 4, 8, and 16, and flat, polynomial, and geometric spectra.Source: §A.3 · p. 25
Results
- 4.391–8.942 is the four-instance median range of tail-operator ratios to dither variance across the tested configurations.The diagnostic uses four paired instances and 1,024 outputs per Gram–Schmidt estimate.Source: §A.3 · p. 25, Figure 7 · p. 26
- 1.471–3.077 is the four-instance median Gram–Schmidt ratio after division by the exact same-grid independent control.The independent control itself ranges from 2.855 to 2.999 times dither variance; the empirical Gram–Schmidt ratios exceed both references in every tested configuration.Source: §A.3 · p. 25, Figure 7 · p. 26
Appendix B. Algorithmic details and deferred proofs
The appendices detail the deterministic rounding steps, deferred proofs, and protocol used to test spectral tails.
Appendix B. Algorithmic details and deferred proofs
- Null-space reduction repeatedly moves along an active null direction until at least one more coordinate is integral, preserving V⊤x.It returns once at most rank(V) coordinates remain fractional; floating-point experiments substitute an SVD for row reduction and record the tolerance.Source: Appendix B · p. 26
- Conditional-expectation completion chooses each remaining endpoint by comparing conditional errors; affine-aware approximation starts from an approximately optimal feasible relaxation.The approximate relaxation contributes an additional η to the guarantee.Source: Appendix B · p. 27
- One-flip metric descent accepts the active coordinate flip with the most negative exact objective increment and stops when no increment is negative beyond tolerance.Each accepted step strictly decreases the objective over the finite feasible set, so the procedure terminates at a one-flip local optimum.Source: Appendix B · p. 27
B.1 Proof of the Gram–Schmidt corollary
- The Gram–Schmidt proof converts directional sub-Gaussian bounds into a Euclidean certificate using a net of the unit sphere and a union bound.The proof also derives an affine expected-error bound from a mean-zero walk displacement.Source: §B.1 · pp. 27–28
B.2 Proof of the conditional head–tail bound
- The head–tail proof applies the Gram–Schmidt bound in the head eigenspace and combines it with a bound on the orthogonal tail contribution.The tail contribution relies on the condition in the head–tail estimate.Source: §B.2 · p. 28
Appendix C. Gram–Schmidt spectral-tail protocol
- The spectral-tail protocol pairs fixed fractional targets across three spectra and compares 1,024 Gram–Schmidt draws with exact and draw-matched independent controls.Prefix estimates at 256, 512, and 1,024 draws assess draw-count sensitivity; four-instance interquartile ranges summarize variation.Source: Appendix C · p. 28
Appendix D. Dynamic implementation and numerical checks
The appendix details the reference implementation’s reduction and completion costs, then reports checks for numerical drift and conditioning. It also separates arithmetic drift from the modeling choice of numerical-rank threshold.
Appendix D. Dynamic implementation and numerical checks
- 1008 steps are required for K = 1024 and r = 16; each reduction step costs O(pr^2 + r^3) arithmetic operations.The reference implementation computes numerical rank once per target, then uses SVD to find a null direction and snaps near-endpoint coordinates.Source: Appendix D · p. 29
- With B output blocks, the reference code repeats reduction and completion B times per activation row, and charges this work to every fractional target.Reported timings separate reduction and completion; the run requests one BLAS/OpenMP thread and records hardware and runtime metadata.Source: Appendix D · p. 29
- The code checks final product drift and the largest relative null residual, and compares its computed objective with the conditional-expectation bound.Equation (25) relates drift to the a posteriori certificate, evaluated using recorded floating-point tolerances.Source: Appendix D · p. 29
- Nine 64 × 32 rank-four instances vary condition numbers and overall scales to measure fractional counts, null residuals, and product drift.Numerical-rank selection near its singular-value threshold remains a separate modeling decision.Source: Appendix D · p. 29
Appendix E. Static-study protocol
The static study evaluates rounded Digits model weights using calibration subsets and held-out product error. Its protocol compares uncentered and centered objectives, with and without bias correction, and reports the mean and covariance contributions alongside paired split summaries.
Appendix E. Static-study protocol
- Digits inputs are 8 × 8 grayscale pixels scaled by 1/16 without centering; five stratified splits fit a ten-class ridge model and reserve 20% each for calibration and held-out evaluation.Each split uses 1078 fit, 359 calibration, and 360 held-out examples; the ridge penalty is 10^-3 and there is no intercept.Source: Appendix E · p. 29
- Signed symmetric 3- or 4-bit grids leave 580–600 active weights and 40–60 exactly representable weights per fit, with no clipped entries among 640.Twenty class-stratified subsets of 128 calibration examples are sampled per pool, alongside the full pool of 359.Source: Appendix E · p. 29
- Best-improvement one-flip descent starts at round-to-nearest; centered methods share weights, and bias correction uses the calibration mean rather than the held-out mean.The correction for output column j is c_j = -μe_j; held-out product MSE is divided by split-matched round-to-nearest error at the same bit width.Source: Appendix E · p. 29
- Table 10 reports paired held-out product-MSE ratios, comparing corrected weights with corrected round-to-nearest weights where applicable.RI denotes a bootstrap resampling interval over five split-level median ratios.Source: Table 10 · p. 30
- 0.08949 MSE comes from the mean term and 0.02664 MSE from the covariance term, averaged over all ten outputs.Centering drops the larger contribution from the calibration objective, while fixed-bias evaluation retains both.Source: Appendix E · p. 30
- Paired summaries use subset-level held-out MSE-ratio medians within each split, then summarize the five split-level ratios; even five wins yield p = 0.0625.Because training and evaluation splits overlap, the intervals are descriptive and do not support an independence interpretation.Source: Appendix E · p. 30