CS Paper Radar

Improved Tristate Multiplication With Formalization in Rocq

Nandakumar Edamana, Piyush P Kurur, Unnikrishnan Cheramangalath

cs.LO ·submitted 2026-09-30 05:18 UTC · v2
code/data

Abstract

We give a new multiplication algorithm for tristate numbers improving upon the state-of-the-art implementation from the Linux kernel in terms of precision. Our algorithm is significantly more precise as shown by experimental evaluation (at the peak, giving better results in 95.59% cases compared to the previous work for 31-bit samples). Importantly, we achieve this additional precision with performance comparable to the previous algorithm, as demonstrated by benchmarks. Our algorithm is now part of the upstream Linux kernel. We also provide the first machine-checked proofs for tnum arithmetic operations that work for all bit widths. Our proofs include the soundness of the new multiplication algorithm and the soundness and optimality of supporting operations.

Comment
- Related Rocq code can be found at https://github.com/nandedamana/trirocq - Related benchmark code can be found at https://github.com/nandedamana/improved-tnum-mul - v2 changelog: (1) reporting end-to-end verification, (2) updated presentation, (3) text updates following code updates

Closest papers

Nearest neighbours by meaning across the whole index.

Long rational and Gaussian integer multiplication

cs.DS math.NT ·2026-11-13 ·Yuval Spiizer, Raphael S. Steiner
similarity 0.63
Abstract · 38 pages

Long integer multiplication is a fundamental operation in computational algebra, heavily relying on Toom--Cook and related evaluation-interpolation algorithms. Conventional wisdom dictates that multiplication on the Gaussian integers $\mathbb{Z}[i]$ is reduced to standard rational integer multiplication, since $\mathbb{Z}[i]$ is a ring extension of $\mathbb{Z}$. We show that this approach is far from optimal and moreover inverting this established paradigm, that is reducing rational to Gaussian multiplication, leads to faster rational integer multiplication algorithms. We introduce a novel Toom--Cook framework that reduces rational long integer multiplication to Gaussian integer multiplication, yielding a strictly more efficient computational pipeline. By taking advantage of the special properties of the rational integer domain inside the Gaussian integers, we achieve a more favourable algebraic structure that reduces the overall arithmetic cost in every metric. To validate this theoretical shift, we provide a complete implementation of our algorithm. Benchmarks demonstrate that our approach outperforms the highly optimised GNU Multiple Precision Arithmetic Library (GMP) by up to 29\%, bridging a fundamental theoretical insight with significant practical improvements in high-performance computer algebra.

0.20

When Double Rounding is Correct

cs.PL ·2026-10-06 ·Brett Saiki, Bill Zorn, Cynthia Richey, Zachary Tatlock
similarity 0.62
Abstract

Number libraries, which implement number formats and their arithmetic in software, are used to simulate hardware, making hardware behavior reproducible and thus verifiable and easier to design. However, modern machine learning accelerators are difficult to simulate, as they increasingly use specialized number formats that existing number libraries do not support. It is costly to extend these libraries using traditional methods: each combination of operation, format, and rounding mode typically requires a bespoke implementation. An easier way is to double round - compute at higher precision, then re-round - so that one high-precision kernel serves many formats, but double rounding is only known to be correct in select cases. We give a precise, efficiently checkable characterization of when double rounding is correct across many formats and rounding modes. Our result rests on a novel abstract number format that unifies fixed- and floating-point representations, reducing the correctness of double rounding to format containment: whether every value of one format is representable in another. We mechanized these results in Lean 4. In addition, we introduce a format inference algorithm that, given a sequence of operations, bounds each expression by a number format guaranteed to contain its result. We apply these insights in two ways. First, we present MPFX, a correctly-rounded, multi-precision number library that exploits correct double rounding to efficiently simulate many number formats. MPFX's correctly-rounded operations are up to 11x (mean: 6.05x) faster than MPFR's, and competitive with SoftFloat's - between 0.46x and 1.63x as fast (mean: 0.94x) - at the same precision. Second, in a case study, we implement a software simulation of a hardware specification using both SoftFloat and MPFX's primitives; the MPFX version is up to 13.5x faster.

0.11

Taming Bitwise Behavior in GPU Kernels with Tensor Core: Black-Box Reconstruction, Compiler Enforcement, and Static Verification

cs.DC cs.PFcs.PL ·2026-09-10 ·Ziteng Yang, Nicholas J. Riasanovsky, Warren Deng, Vivek Sarkar
hot direction similarity 0.61
Abstract

Determinism and numerical reproducibility are increasingly required of GPU kernels in machine learning systems, yet deterministic implementations of the same kernel can still differ bit for bit. Floating-point reduction order is the primary cause, alongside partial-sum precision, fused multiply-add operations, and rounding placement. These choices may be hand-coded, selected by a block-level language such as Triton, or hidden inside a closed-source library such as cuBLAS or rocBLAS. A tile shape chosen for performance therefore also determines the arithmetic, potentially breaking batch invariance. Preserving a fixed order can cost up to 20 percent, while an autotuner cannot identify which configurations are bitwise equivalent. We characterize the factors determining the bitwise behavior of reductions and general matrix multiplication (GEMM). First, we introduce a descriptor of GEMM reduction order, including the partitioning of K in split-K GEMM. Using it, we perform the first black-box reconstruction of a closed-source library's arithmetic for bit-level correctness. Our family of Triton GEMMs matches NVIDIA cuBLAS in all tested cases on Blackwell and Hopper. For realistic LLM shapes with fused epilogues, it matches or exceeds torch.compile performance. Second, we enforce balanced-tree reduction during Triton lowering and introduce a data-layout optimization that brings 19 of 27 kernels on GB300 and H100 within 10 percent of free-order performance. Third, we develop sound static checkers for bitwise equivalence between compiled GPU kernels, including the first checker spanning NVIDIA PTX and AMD GCN. Integrated into Triton's autotuner, the checker restricts search to a single bit-equivalence class.

0.53

Providing Accuracy Guarantees for the Fixed-Point Emulation of Matrix Multiplication

cs.MS cs.DC ·2026-11-13 ·Cole Brower, Peter Caday, John Gunnels
theory similarity 0.60
Abstract · We plan to submit to TOMS, but have not done so

Fixed-point methods such as Ozaki-II emulate double-precision matrix multiplication (GEMM) on fast low-precision hardware. Software that chooses the mantissa bit count automatically is numerically safe when the emulated product keeps the error guarantee of the floating-point GEMM it replaces. We analyze the worst-case and average-case error of fixed-point and floating-point dot products, define exponent span capacities that determine the extra mantissa bits an input requires, and approximate them with a low-precision GEMM. We prove that 53 bits plus such a capacity and a small constant preserve the classical worst-case error bound for a floating-point dot product, and we demonstrate this guarantee in software on several test cases. In a developer build of cuBLAS on an NVIDIA B200, each implemented bit-count rule earns grade~A on Test~2c of ``Grading the BLAS'' at every size and exponent range tested, falling back to double precision at the widest ranges; in exact arithmetic, the bound holds on every adversarial and random input tested.

0.32

FloatLib: Verified Floating-Point Arithmetic in Lean

cs.LO cs.PL ·2026-09-16 ·Robert Joseph George, Will Adkisson, Anima Anandkumar
code/data similarity 0.60
Abstract · 30 pages, 7 figures, 6 tables. Software and evaluation artifacts available at https://github.com/lean-dojo/FloatLib

We present FloatLib, a verified arbitrary-precision floating-point arithmetic library in Lean 4 that combines broad format coverage, machine-checked correctness, and efficient certified execution. To our knowledge, FloatLib is the first Lean library to unify IEEE binary and decimal arithmetic, arbitrary-width posits, P3109, and user-defined formats and rounding rules behind interchangeable certified software backends. Every certified backend is proved equal to a complete encoded specification, preserving signed zeros and exceptional values, while numerical theorems connect execution to real rounding, error bounds, and exactness. FloatLib combines exhaustive certified tables for small formats with verified word and limb kernels based on guard-and-sticky invariants and independently checked quotient candidates. Its posit development additionally proves standard rounding thresholds and exact quire accumulation within capacity for arbitrary widths. Across matched workloads, FloatLib achieves speedups of up to 1.46x over FLoPS and 116x over Universal, while remaining slower in some regimes such as binary arithmetic against MPFR. Independent conformance testing includes more than 102 million TestFloat evaluations with zero differences under the tested relation. We release the library, proofs, benchmarks, evaluation data, and guide as open source.

0.38

Deciding Scale Placement in MXFP4 Dot Products with Integer Arithmetic

cs.LO cs.ARcs.PL ·2026-10-21 ·Shreyas Vinayakumar
theory similarity 0.58
Abstract · 24 pages including references and two appendices, 1 figure, 5 tables

The Open Compute Project's microscaling (MX) family includes MXFP4, which stores 32 four-bit elements with a shared power-of-two scale. When lowering a dot-product reduction, a compiler can apply these scales before the reduction, or defer scaling until afterwards. Although equivalent over real numbers, these formulations can produce different IEEE binary32 results through overflow or underflow, with equivalence also depending on the reduction tree. We study the legality of compiler rewrites in either direction by deriving conditions under which the two formulations are bitwise equivalent. To decide rewrite legality, we construct an integer state machine that exploits the finite element alphabet and shared power-of-two scales, modeling overflow, NaN, and subnormal rounding. We prove its faithfulness under bounded scale codes and integer coefficients, yielding an exact encoding of the equivalence query in quantifier-free linear integer arithmetic (QF_LIA). For MXFP4, we derive a closed-form sufficient upper bound on the sum of scale exponents for any fixed binary reduction tree within the supported coefficient range. This bound depends on the size of the largest proper subtree. For four tree shapes at block lengths $k\in\{2,3,4,8,16,32\}$ and two shapes at $k=64$, SMT finds counterexamples when this upper bound is increased by one exponent step. Against the standard direct encoding in quantifier-free floating-point arithmetic (QF_FP), on matched queries cvc5 proves the integer version in seconds but reaches a configured one-CPU-hour limit on the floating-point proof even at $k=2$. The implementation was cross-checked using an independent floating-point encoding, exhaustive and stratified binary32 execution, and GPU replay of counterexamples. An MLIR lowering prototype demonstrates selection between the two formulations using the certified conditions as static or runtime guards.

0.24

FIGFLEX: A Mixed-Precision FP-INT GEMM Accelerator Co-Designed with Low-Bit LLM Quantization

cs.AR cs.LG ·2026-10-21 ·Faraz Tahmasebi, Haocheng Xu, Andrew Trauger, Yomal Perera, Zhenyu Tang +2 more
similarity 0.56
Abstract · 15 pages, 12 Figures

Weight-only quantization keeps LLM activations in floating point and stores weights as low-bit integers, turning the dominant workload into floating-point-integer (FP-INT) general matrix multiplication. Recent quantizers reach a 2-3-bit average with mixed precision, but hardware has not kept pace: GPUs dequantize weights to FP16 before the tensor-core multiply-accumulate, and bit-parallel FP-INT accelerators run at a single weight precision, so fewer bits save memory but not computation. In this paper, we present FIGFLEX, an algorithm-hardware co-designed mixed-precision accelerator whose bit-parallel datapath scales throughput as precision falls. FIGFLEX contributes (1) a shift-add, radix-4 reformulation of FP-INT multiplication that fuses the multiply-accumulate into a unified, precision-flexible partial-product reduction and roughly halves the partial products, together with a novel INT3 optimization that reclaims the idle datapath radix-4 leaves at that precision; and (2) a mixed-precision quantizer that assigns each channel group its bit-width according to the error GPTQ cannot compensate, with a per-input-channel column scaling whose power-of-two normalization keeps the scaled activations out of the FP16 subnormal range, so that the quantized model maps directly onto FIGFLEX's datapath with the same accuracy as on a GPU. On LLaMA-2-7B, FIGFLEX attains 5.85 and 8.77 WikiText-2 perplexity at 3- and 2-bit average precision, lower than GPTQ, AWQ, SliM-LLM, AMQ, and QuIP# (without fine-tuning), while delivering 1.56x and 1.42x higher whole-chip throughput per area on the linear GEMMs of a 3-bit mixed-precision model than AxCore and FIGLUT, respectively.

0.13

TRACE: Traversal and Reasoning Algebraic Computing Engine for Formal Hardware Verification

cs.AR ·2026-08-17 ·Jan Kleinekathöfer, Lennart Weingarten, Kamalika Datta, Rolf Drechsler
hot direction similarity 0.56
Abstract

Modern hardware verification of complex circuits relies heavily on the efficiency of formal methods. For complex arithmetic circuits in particular Symbolic Computer Algebra (SCA) engines which represent pseudo-boolean functions using polynomials are crucial. As circuit complexity grows in the age of AI, verification of arithmetic primitives, including Multiplication, Addition, Multiply-Accumulate (MAC), becomes a computational bottleneck. To address this, we introduce TRACE (Traversal and Reasoning Algebraic Computing Engine), a highly efficient framework designed to investigate the intersection of traversal strategies and proof efficiency. Unlike existing SCA tools which are mainly limited to multipliers, TRACE offers a flexible framework for researchers to analyze memory usage and verification time across a wide range of arithmetic circuits (adder, multiplier and MAC). To overcome the state-explosion problem inherent in polynomial expansion, the engine incorporates advanced reduction techniques, including optimized traversal strategies, conflict removal, and polarity-based optimization for compact symbolic representations. Our experimental results show that for optimized MAC, for the first time, TRACE was able to verify previously unverifiable circuits

0.35