CS Paper Radar

Engineering Lightweight Burrows-Wheeler Transform Construction on the GPU via Prefix-Free Parsing

Florian Kurpicz, Maximilian Paris

cs.DS ·submitted 2026-10-24 19:58 UTC · v1

Abstract

The Burrows-Wheeler transform (BWT) is the core of many compressed full-text indexes and most read aligners. The fastest BWT constructions on GPUs need about $20$ bytes of device memory per character, which severely limits the texts that can be processed there. For example, on our GPU with 24 GB device memory, this is only about 1200 MiB. Prefix-free parsing (PFP) can be used to reduce the memory requirements of BWT construction algorithms in main memory. But, it uses hash tables and inverted lists which are not suited for GPUs. We show that PFP-based BWT construction can work with only sorting, scanning, and simple data-parallel procedures. This results in our GPU construction gpupfpbwt that on an NVIDIA RTX 3090, reduces the peak memory on an English text 11.9 bytes per character. There, it can processes 2108 MiB input files, which is 1.8 times larger than what the current state of the art libcubwt can handle. It is faster than or on par with libcubwt on eight of nine repetitive texts but 2.0 to 3.2 times slower on five of six non-repetitive ones, i.e., it provides a trade-off between required device memory and throughput.

Closest papers

Nearest neighbours by meaning across the whole index.

FastPair: GPU-Optimized String Decoding

cs.DB cs.ARcs.DC ·2026-09-14 ·Joseph Isaacs, Francesco Gargiulo, Peter Boncz, Robert Kruszewski, Nicholas Gates +3 more
similarity 0.76
Abstract

Modern data systems compress data at rest and decompress it only when needed to preserve interconnect bandwidth. This design is often inefficient on GPU-based compute platforms because many conventional compression techniques exhibit serial data dependencies that limit GPU parallelism, leaving resources idle. Recent NVIDIA GPUs address this decoding deficiency through the Decompression Engine (DE), an on-die, fixed-function decompression accelerator for general-purpose compression formats such as Deflate, LZ4, and Snappy. Recent work has proposed string codecs that replace frequent substrings with fixed-width codes from a small, trained dictionary, making each code's lookup independent. While these lookups can run in parallel, the resulting scattered reads and short output writes still do not align well with GPU hardware, which handles contiguous memory accesses more efficiently. We present FastPair, a GPU decoder that optimizes the existing dictionary decoding process by reorganizing lookups and assembling decoded substrings for contiguous output writes. On a B300, FastPair decodes ten real-world columns 2.4 to 4.2x faster than the DE, reaching up to 1.6 TB/s.

0.20

LLBPE: Linked-List Based GPU-Parallel BPE Tokenizer

cs.PF ·2026-10-04 ·Aditya Kovilur, Varun Chandra Shekar, Ariful Azad
similarity 0.73
Abstract

Every LLM inference begins with tokenization, which converts raw input bytes into the discrete token sequence the model consumes. For text, this step is often implemented using Byte Pair Encoding (BPE), an algorithm originally introduced for data compression. BPE has traditionally run on the CPU with extensive optimization, but recent work has moved it to the GPU for higher throughput. We show that these GPU implementations are bottlenecked not by computation but by data movement. We develop LLBPE that represents the token sequence as an array-based linked list so that each merge reduces to a constant- time pointer update. Furthermore, LLBPE fuses rank lookup, minimum selection, and merging into a single kernel to eliminate redundant hash map queries. LLBPE achieves up to 5.2x higher throughput than the best existing GPU implementation and 24.6x over optimized CPU implementations, at the cost of minor discrepancies in tokenized output.

0.43

Cascade: GPU-Accelerated Out-of-Core Suffix Array Construction for LLM Corpora

cs.DS ·2026-10-11 ·Jamshed Khan, Prashant Pandey
similarity 0.69
Abstract

Suffix arrays power deduplication, contamination testing, and training data attribution over the corpora used to train large language models, and must be rebuilt for every new corpus or tokenizer. However, constructing them at scale is slow. infini-gram's indexing pipeline takes about two days to process 1.4 trillion tokens on its authors' 128-core CPU server. GPU-accelerated constructors are an order of magnitude faster, but their working sets must fit in GPU memory. Partitioning the corpus only moves this limit to host memory. Sorting the suffixes of one partition needs the ranks of suffixes in other partitions, which existing designs keep in a corpus-wide rank table that must stay in memory. We present Cascade, a GPU-accelerated out-of-core suffix-array constructor. Its partitions each own a fixed, contiguous range of the final suffix array, so the GPU sorts them independently and never merges them. Cascade then replaces the rank table with streamed rank exchange. Ranks are sent directly to the partitions that need them, and an invariant makes partition-local ranks sufficient for every comparison. With no rank table, intermediate data spills across GPU memory, host memory, and SSD as the corpus grows, and host memory only needs to hold the text. On seven corpora of 8-238 billion tokens, Cascade builds suffix arrays on a single GPU server 3.0-8.2x faster end to end than infini-gram's pipeline, and its construction is 6.3-11.4x faster than libsais's. It indexes the 198-billion-token C4 corpus and the 238-billion-token Pile in 23 and 37 minutes end to end, both of which exceed libsais's host-memory capacity on the same server. A batched query engine over the index reproduces infini-gram's counts at median speedups of 10.8-32.6x, with the index in GPU memory, host memory, or on SSD.

0.21

Tile-Based Decompression in Compiled GPU Engines

cs.DB cs.DC ·2026-10-23 ·Antonio Boffa, Ananya Gupta, Hamish Nicholson, Anastasia Ailamaki
top venue similarity 0.68
Abstract · 15 pages, 6 figures, 3 tables. Accepted to PVLDB Vol. 20

Modern GPUs reach record analytical performance only when a query's working set fits within its GPU memory budget, and that budget is under growing pressure: GPUs are partitioned and shared, working sets are outgrowing high-bandwidth memory (HBM), and HBM is a fixed on-device resource whose per-dollar capacity has stagnated across generations. Lightweight compression can relieve this pressure by shrinking both footprint and bandwidth demand, but existing GPU compressed-execution techniques either bind decompression to a specific execution model or materialize decompressed columns in HBM before query execution. We present a compression subsystem for compiled GPU query engines that treats decompression as a first-class physical operator. Compression-specific logic is isolated behind a narrow backend interface, so new GPU-oriented encodings can be added without rewriting downstream operators. We implement the design in Proteus and study where decompressed values should be materialized in the GPU memory hierarchy. Our compiler-integrated shared-memory strategy fuses cooperative tile decompression with tuple-at-a-time query execution inside a single generated GPU kernel, avoiding decompressed-column materialization in HBM. Compared with HeavyDB and Sirius on GPU-resident data, fused on-chip decompression achieves competitive query times while reducing the resident memory footprint by up to 4x and memory-bandwidth consumption by up to 6x.

0.33

ZipFusion: Fusing Lossless KV Decompression with Attention for Efficient LLM Decoding

cs.AR cs.DC ·2026-10-24 ·Yuetao Chen, Peng Wang, Hong Xu
similarity 0.67
Abstract

The key-value (KV) cache places growing demands on GPU memory capacity and bandwidth as large language models serve longer contexts and more concurrent requests. Its footprint limits concurrency, while repeated KV reads during attention can make decoding memory-bandwidth bound. Prior lossless KV cache compression methods reduce transfers between devices but restore the uncompressed KV cache in GPU memory before attention. They therefore leave these repeated KV reads unchanged and require additional work and memory for decompression. We present ZipFusion, which enables attention to consume the losslessly compressed KV cache directly. ZipFusion co-designs the compression format and attention kernel to reduce the bytes read from GPU memory during attention. The kernel reconstructs the original values directly in registers using simple bit operations, avoiding a separate decompression pass and easing the memory-bandwidth bound. ZipFusion also reassigns memory freed by compression across layers to store additional KV cache. Its memory manager reserves space for ongoing generation and makes the remaining capacity available to new requests. We implement ZipFusion on top of FlashInfer and integrate it with SGLang. On an NVIDIA H100, ZipFusion achieves about 1.25x speedup over FlashInfer in decode attention. With 8K context, it improves model decode throughput by up to 26.3% over uncompressed SGLang under the same GPU memory budget. At each method's largest supported batch, it also delivers up to 2.76x the throughput of the best-performing lossless KV cache compression baseline.

0.09

Batched Paillier-Based Hamming-Distance Computation over Binary Embeddings

cs.CR ·2026-09-18 ·Yavor Litchev, Liwen Ouyang
similarity 0.65
Abstract

Additively homomorphic encryption supports outsourced computation on encrypted binary embeddings, but large-integer arithmetic and data movement can limit throughput. We describe a Paillier-based client that combines a carry-separated binary encoding, table-based encryption, reduced-exponent decryption, CUDA/CGBN arithmetic, persistent device state, and batched retrieval integration. We establish the encoding's correctness and characterize four CPU and GPU client configurations. The lookup configuration uses a 280-bit exponent-size parameter. Across 3 warm-state trials on batches of 10,000 random 512-bit embeddings, the lookup GPU configuration achieved median-batch throughputs of 43,091 encryptions/s and 28,983 Hamming- distance decodes/s. Its amortized costs were 0.0232 ms and 0.0345 ms per vector, corresponding to factors of 453.8 and 200.9 relative to the measured CPU baseline. These implementation- specific results demonstrate the throughput benefits of combining cryptographic precomputation, batched accelerator execution, and persistent runtime state. The study distinguishes warm-batch performance from isolated-request latency and identifies the remaining costs of initialization, transport, and retrieval integration.

0.24

Memory Bandwidth, Not FLOPs: Profiling and Accelerating Query-Based Segmentation Decoders on Edge GPUs

cs.AR cs.LGcs.PFeess.IV ·2026-09-29 ·Oliver Busemann, Torben Töniges, Martin Atzmueller
published similarity 0.64
Abstract · Accepted at the British Machine Vision Conference (BMVC) 2026. Supplementary material included

Query-based segmentation models achieve strong performance even under real-time inference on workstation GPUs. On edge devices, however, we show their transformer decoders are deeply memory-bandwidth-bound, a bottleneck invisible to standard FLOP analysis that worsens with input resolution and limited DRAM bandwidth. An FP16 roofline analysis with tensor-core GEMMs active and hardware DRAM counters shows that the non-tensor-core aggregates of FastInst and Mask2Former reach only $2.5\%$ to $6\%$ of the CUDA-core ridge yet account for $53\%$ to $70\%$ of decoder time and $61\%$ to $71\%$ of decoder bytes. The largest individual kernels sustain up to $90\%$ of nominal peak DRAM bandwidth, effectively saturating the memory bus. The bottleneck is therefore not primarily low GEMM intensity, but cross-kernel activation traffic. CompactInst addresses this bottleneck using parameter-free spatial pooling at $4{\times}$, which reduces the bytes moved within the transformer decoder, while a two-convolution refinement head recovers spatial detail. Under TensorRT FP16 on Jetson Orin Nano, CompactInst delivers decoder speedups from $2.35{\times}$ to $4.74{\times}$ and model speedups from $1.57{\times}$ to $2.62{\times}$ as input resolution grows, while closely matching accuracy ($-0.4$ AP on COCO val2017, $+0.2$ AP on Cityscapes test). A heavier variant with $2.57{\times}$ more decoder FLOPs still runs its decoder $1.74{\times}$ faster on the most bandwidth-constrained device, confirming at the deployment level that decoder bytes, not FLOPs, govern latency.

0.31

Memory-Efficient Designs for Word-Wise Universal Fully Homomorphic Encryption

cs.CR ·2026-09-04 ·Ardhi Wiratama Baskara Yudha, Erwin Eko Wahyudi, Rian Adam Rajagede, Qian Lou, Yan Solihin
published similarity 0.63
Abstract · Accepted at ICCD 2026

Fully Homomorphic Encryption (FHE) enables computation on encrypted data, preserving privacy throughout analysis. While its privacy is very strong, FHE is much slower to execute than the original computation. In particular, due to the recent success in accelerating its compute, the performance bottleneck shifts to the memory, especially considering that FHE magnifies the data size by orders of magnitude, resulting in a low arithmetic intensity. We propose BXT, an FHE optimization framework that mitigates the memory bottleneck through four techniques: (1) ciphertext compression, which regenerates ciphertext components from seeds during execution; (2) ciphertext serialization, which packs coefficients as bit arrays and unpacks them during L2-to-L1 transfer; (3) delayed seed generation, which defers PRNG-heavy offline work across aggregated operations; and (4) ciphertext digit pruning guided by fault-aware training tailored for Universal FHE. On CNN inference, the BXT-CSO50 configuration effectively achieves up to 3.8$\times$ speedup over the 100x GPU baseline with less than 1% accuracy loss at 50% comparison precision.

0.28