CS Paper Radar

zkDuel: Characterizing SumCheck Prover Kernels across GPU Programming Models

Samarth Narang, Alhad Daftardar, Brandon Reagen

cs.AR ·submitted 2026-10-26 21:28 UTC · v1
publishedbenchmark

Abstract

SumCheck is a central prover primitive in zero-knowledge proofs, exposing table-parallel work that maps naturally to GPUs but becomes increasingly arithmetic-intensive as finite fields widen. We study how this shift affects the cost of programming SumCheck in Triton rather than CUDA. Our benchmark, zkDuel, provides matched implementations of 25 zkPHIRE-derived constraints alongside diagnostic polynomials, covering 32-, 64-, 128-, and 256-bit prime fields, with independent CPU-reference validation and cross-backend checksum gating. Of 800 configurations attempted on an NVIDIA H100, 758 complete with matching checksums. CUDA's median advantage over Triton falls from 3.5x at 32 bits to 1.4x at 256 bits, and Triton is faster on 19 large-table configurations; the same convergence appears on an A100, where the gap falls from 4.4x to 1.6x. Profiling shows that the small-field gap largely reflects host launch overhead and redundant modular additions in Triton's original block reduction, whose relative costs diminish as multi-limb Montgomery work grows. Replacing that reduction with tl.reduce brings Triton's median kernel time within 8% of CUDA on both GPUs, while specialized point interpolation improves 256-bit evaluation kernels by 1.55-1.75x. At cryptographic widths, these results show that a Python-embedded DSL can approach CUDA performance, although the largest fully unrolled constraints still expose compiler-scalability limits.

Comment
Accepted to HASP'26 at MICRO 2026
DOI
10.1145/3857307.3857312

Closest papers

Nearest neighbours by meaning across the whole index.

Performance Bottlenecks in Computing ZK Proofs on a GPU

cs.CR ·2026-11-06 ·Victor Carolino, Caleb Geren, Michael Kaufman, Maximilian Nussbaum, William Scott +1 more
similarity 0.71
Abstract · 8 pages

Zero-knowledge proofs allow one party to prove the correctness of a statement or execution of a computation while revealing no more than the statement of correctness itself. Recent use cases, such as AI datasets, suggest the need for faster proof generation over increasingly large constraint sets. This paper explores efforts in optimizing zero-knowledge proof generation, specifically PlonK, using GPUs, for applications that are not amenable to solution via incrementally verifiable computing (IVC). Our intention with this work is to improve ZK performance by introducing fundamental changes in the low-level architectural structure of proof generation. These changes affect performance curves for most current proof generation algorithms. In particular, this paper explores the trade-offs between increased parallelization on GPUs and the resultant memory management problems that occur due to this parallelization. We implement a parallelized PlonK in order to analyze these trade-offs and make arguments concerning the nature of data flows within the proving protocol. Our results lead us to consider multi-GPU environments to maximize performance for large circuit sizes. Such environments introduce issues of communication, efficient hardware management, data partition, and data transfers. This paper further discusses the use cases that motivate multi-GPU implementations, their cost models, and the use of remote direct memory access (RDMA) for data transfer among GPUs.

0.29

Sable: A Small-Field Sumcheck Argument for Bit-Exact Inference of Large Language Models

cs.CR cs.AIcs.LG ·2026-11-10 ·Tomer Solberg
code/data similarity 0.67
Abstract

We present Sable, an argument system and single-GPU prover for the statement that a committed, integer-quantized transformer produced a given token sequence from a given prompt, bit for bit. Sable fixes an integer function F_O with no floating-point step, in which every rounding, normalization, softmax and sampling decision is determined by its inputs, and proves it with a constraint system whose relations provably never wrap modulo the 31-bit KoalaBear prime. The proof batches zerochecks and LogUp-GKR lookups into one sumcheck per domain, and commits to every witness tensor and weight in one multilinear commitment built from Reed-Solomon codes, BLAKE3 Merkle trees and a mixed-length BaseFold opening. The prover streams the model layer by layer on one GPU. On one NVIDIA RTX PRO 6000 Blackwell GPU, Sable proves all 64 layers of Qwen2.5-32B in 92.5 s for 4,096 tokens and 398 s for 16,384 tokens, and covers Qwen3-32B and the mixture-of-experts Qwen3-30B-A3B (4,096 tokens in 121.8 and 84.7 s). A proof costs 41 to 50 times the serving time, or 6.4 cents per 4,096-token request at public GPU prices, and 40 to 64 times less time per parameter and token than zkLLM. On WikiText-2, F_O's greedy token matches the BF16 model's at 86.3% of positions; on Qwen3, F_O is within 1.6 points of BF16 on MMLU and 1.7 points on GSM8K. A verifier with a compiled core checks a proof on one CPU core in 19 to 56 s. In the random-oracle model, the interactive proof has round-by-round soundness error 2^-103. The proof is not zero-knowledge, so the system targets open-weight models. Code: https://github.com/moonmath-ai/Sable

0.59

Annotation-Driven Migration of CUDA Programs to Tenstorrent Blackhole

cs.DC ·2026-10-02 ·Ayumi Ohno, Shinya Takamaeda-Yamazaki
similarity 0.67
Abstract · Accepted at the Thirteenth Workshop on Accelerator Programming and Directives (WACCPD 2026)

Tenstorrent Blackhole combines distributed local memories, explicit inter-core communication, and Tensix cores decoupling data movement from computation. CUDA offers a substantial HPC software base but leaves physical data placement and scheduling largely implicit. Migrating CUDA HPC kernels to Blackhole requires spatial mapping across cores and per-core coordination of compute and data-movement kernels. We present an MLIR-based compiler deriving data placement, inter-core communication, and tile computation from a statically shaped affine CUDA subset. Declarative annotations express choices not fixed by the source, including compute/DM operation placement and streaming granularity. We evaluate it on Gaussian elimination, five-point stencil, and symmetric rank-k update. Relative to our compiler's default realizations, the best measured configurations achieve a 4.2x speedup for BF16 Gaussian and 2.1-2.2x for FP32 Gaussian and Jacobi. A choice's performance impact can reverse with surrounding policies, precision, and loop schedule, motivating comparison of alternative per-core realizations rather than independent policy selection.

0.24

Performance-Portable Exact Gaussian Process Regression in Python via SYCL and oneMath

cs.DC cs.LGcs.PF ·2026-11-12 ·Alexander Strack, Marcel Graf, Alexander Van Craen, Dirk Pflüger
publishedcode/datahot direction similarity 0.67
Abstract · 12 pages, 6 figures, 2 tables. Accepted at the WACCPD 2026 workshop (SC26 Workshops), November 15-20, 2026, Chicago, Illinois, USA

Modern multi-vendor GPU environments force a choice between portable code and native performance. GPRat is an open-source Python library for exact Gaussian process regression built on the HPX asynchronous many-task runtime, tiled algorithms, and CPU/CUDA BLAS backends. We contribute a UXL Foundation oneMath backend with a hybrid HPX/SYCL design, extending GPRat to AMD and Intel GPUs. The new SYCL backend comes within 3% of native CUDA on an NVIDIA A30 at the largest problem size and outperforms the GPflow and GPyTorch libraries by up to 1.75x and 2.17x on the A30 and up to 1.79x and 4.62x on an AMD Instinct MI210. On an Intel Arc B580, a consumer-class card with FP64 throughput below our CPUs, the unmodified SYCL backend trails GPRat's CPU backend. Overall, oneMath's dispatch to vendor-native BLAS lets a single SYCL codebase match CUDA on NVIDIA and outperform established Python GP frameworks on AMD, without vendor-specific code.

0.50

Hierarchical Rule Auditing with Exact Ternary GPU Correlation

cs.DC cs.CR ·2026-10-18 ·shengwei wang
theory similarity 0.66
Abstract

Auditing firewall logs against requirements mapped to controls and frameworks must retain overlapping obligations, preserve uncertainty from missing attributes and count distinct affected records. Direct, bitmap and relational methods can express this audit; a correlation implementation must preserve distinctions that ordinary match counts and rule-hit totals discard. We present an exact ternary correlation algorithm that compiles categorical conjunctions into one bounded-integer matrix product. A dominating false-predicate penalty separates known mismatches from missing evidence, while per-record hierarchy unions prevent duplicate counting. We prove their composition and handle high-cardinality endpoints through exact address classes and versioned labels. Evaluation compares eight CPU/GPU implementations, includes public traffic and 133 published source-address ACLs with generated observations, and measures hierarchy and policy-rebuild costs. On an NVIDIA L4, matched fused execution reduces latency by 8.8 to 11.2 percent relative to two-product correlation across five tested shapes. At 100,000 records and 1,024 requirements, it takes 12.28 ms versus 13.82 ms for two products and 12.29 ms for GPU bitmaps. Bitmaps remain faster in most regimes, with hierarchy operations and reductions dominating the measured fused-correlation stage intervals.

0.16

A Per-Step Load-Balancing Engine for Expert-Parallel MoE Serving

cs.AR cs.DC ·2026-11-08 ·Jingyuan Li, Maolin Wang, Hayden So
code/data similarity 0.66
Abstract · An anonymous version of this manuscript was submitted to HPCA 2027 on August 1, 2026. The original submission PDF and its SHA-256 checksum a…

In expert-parallel Mixture-of-Experts serving, a layer finishes only when the most loaded GPU of its group does. Token routing shifts at every decode step and concentrates on a few experts, so most of the group's reserved GPU time waits on stragglers. Recovering that time means re-deciding, at every layer of every decode step, how each replicated expert's tokens divide between its copies. The exact linear-program solvers that make this decision optimally take longer than many of the layers they serve, and their working set outgrows GPU shared memory at deployment scale. We introduce Relief, a bidirectional pairwise relaxation that makes the linear program unnecessary, coming within a fraction of a point of the per-step optimum in a few passes of integer halving over the token counts. We build and measure three deployments, CUDA kernels on the serving GPU, the same verified engine on an FPGA over PCIe, and a fixed-function block beside the accelerator. On decode routing from three open MoE families, Relief holds the balance near the per-step optimum at every group size and layer time measured. Scored as effective utilization relative to that optimum, the kernel alone matches or exceeds every deployable scheme at every group size, from the hundred-microsecond layer on. The on-die engine widens that lead at every point, recovering up to 37.3 percentage points over the deployed static placement, while adding 0.02% of a current accelerator's transistors.

0.33

Accelerating the Mitigation of LLM Inference Nondeterminism Across GPU Architectures

cs.AR cs.LG ·2026-09-22 ·Liam Cooper, Shinnung Jeong, Hyeran Jeon, Jeffrey Young, Hyesoon Kim
similarity 0.66
Abstract · 14 pages, 5 figures

Large language model (LLM) outputs are expected to be reproducible under greedy decoding, yet in practice the same model, prompt, and software stack produce different outputs on different GPUs. The root cause is floating-point non-associativity combined with hardware-dependent kernel selection. Inference frameworks select different matrix-multiplication kernels on each architecture, with different parallel reduction orders and unspecified tensor-core arithmetic, and the resulting rounding differences can flip output tokens. Existing solutions have imperfect cross-architecture reproducibility and incur a significant performance penalty. We present a solution employing a set of fixed-configuration fused-upcast GEMM kernels that load 16-bit weights from memory, upcast them to FP32 in registers, and accumulate with IEEE-754 arithmetic in a reduction order that is a pure function of the problem shape and is therefore independent of the device, its SM count, or kernel scheduling. By fixing the floating-point reduction order as a function of problem shape alone, every GPU runs the same operation sequence, so cross-architecture reproducibility of the linear layers reduces to correct IEEE-754 arithmetic rather than to rounding differences staying below a tie-flip threshold. We confirm our solution's linear-layer outputs are bitwise identical across NVIDIA Ampere, Ada, and Hopper GPUs, while running $1.17$ to $3.1\times$ faster end-to-end than the state-of-the-art solution and cutting weight-memory traffic in half.

0.33

Xtrace: High-Fidelity GPU Intra-Kernel Tracing via Binary-Level Instruction Splicing

cs.AR ·2026-09-23 ·Zhuobin Huang, Kai Zhang, Weihao Cui, Hongshi Tan, Liang Luo +3 more
code/data similarity 0.66
Abstract · 13 pages of main text plus an appendix (24 pages in total), 16 figures, 5 tables. Xtrace is publicly available at https://g-watch.github.io

Modern GPU kernels fuse increasingly more work into a single kernel, and intra-kernel tracing has become the mainstream method to profile them. Tracing inserts probes into the kernel to record its runtime states, and the fidelity of the trace determines the efficiency of performance optimization. Unfortunately, existing tools insert probes before compilation. These tools interfere with the compiler's optimizations, so they trace a different binary from the one the GPU executes. They also add significant runtime overhead. Xtrace is the first GPU kernel tracing system with near-zero compile-time interference and minimized runtime overhead. Xtrace inserts probes directly into the compiled kernel binary. It reuses only the registers that hold dead values at the insertion address and resolves all hazards with the compiler's hazard tables. It further schedules the instruction order, register allocation, and control bits to minimize the runtime overhead the probe introduces. Xtrace supports 19 NVIDIA and AMD GPU architectures, and is publicly available for use at https://g-watch.github.io. We evaluate Xtrace on major production large language model (LLM) kernels against the state-of-the-art tracers Neutrino and IKET from NVIDIA. On H100, B300, and MI300X GPUs, Xtrace preserves 94-98% of the instructions of the kernel, while existing tools preserve only 8-48%. Xtrace adds only 0.9-2.8% overhead, while existing tools add 3.8-75.6%. Xtrace guides a coding agent to reach the same FlashAttention-3 performance with 3.9x fewer iterations than existing traces do. Thanks to our binary-level instrumentation, Xtrace also traces the faster closed-source cuDNN kernel, which guides the agent to lift the open-source FlashAttention-4 by 5.2-13.3% in throughput.

0.64