Theodosian: A Deep Dive into Memory-Hierarchy-Centric FHE Acceleration

• URL: http://arxiv.org/abs/2512.18345v1
• Date: Sat, 20 Dec 2025 12:18:29 GMT
• Title: Theodosian: A Deep Dive into Memory-Hierarchy-Centric FHE Acceleration
• Authors: Wonseok Choi, Hyunah Yu, Jongmin Kim, Hyesung Ji, Jaiyoung Park, Jung Ho Ahn,
• Abstract summary: Fully homomorphic encryption (FHE) enables secure computation on encrypted data, mitigating privacy concerns in cloud and edge environments.<n>In this paper, we perform a microarchitectural analysis of CKKS, a popular FHE scheme, on modern GPUs.<n>We show that the dominant kernels remain bound by memory bandwidth despite a high-bandwidth L2 cache, exposing a persistent memory wall.<n>Motivated by these findings, we introduce Theodosian, a set of complementary, memory-aware optimizations that improve cache efficiency and reduce overheads.
• Score: 3.8153115302044296
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fully homomorphic encryption (FHE) enables secure computation on encrypted data, mitigating privacy concerns in cloud and edge environments. However, due to its high compute and memory demands, extensive acceleration research has been pursued across diverse hardware platforms, especially GPUs. In this paper, we perform a microarchitectural analysis of CKKS, a popular FHE scheme, on modern GPUs. We focus on on-chip cache behavior, and show that the dominant kernels remain bound by memory bandwidth despite a high-bandwidth L2 cache, exposing a persistent memory wall. We further discover that the overall CKKS pipeline throughput is constrained by low per-kernel hardware utilization, caused by insufficient intra-kernel parallelism. Motivated by these findings, we introduce Theodosian, a set of complementary, memory-aware optimizations that improve cache efficiency and reduce runtime overheads. Our approach delivers consistent speedups across various CKKS workloads. On an RTX 5090, we reduce the bootstrapping latency for 32,768 complex numbers to 15.2ms with Theodosian, and further to 12.8ms with additional algorithmic optimizations, establishing new state-of-the-art GPU performance to the best of our knowledge.

Related papers

• CLO: Efficient LLM Inference System with CPU-Light KVCache Offloading via Algorithm-System Co-Design [27.03446161229998]
  We propose CLO, a CPU-light KVCache offloading system via algorithm-system co-design.<n>CLO achieves comparable accuracy to state-of-the-art systems, while substantially minimizing CPU overhead.
  arXiv  Detail & Related papers  (2025-11-18T14:03:21Z)
• Accelerating LLM Inference Throughput via Asynchronous KV Cache Prefetching [16.6871758712011]
  Large Language Models (LLMs) exhibit pronounced memory-bound characteristics during inference due to High Bandwidth Memory (HBM) bandwidth constraints.<n>We propose an L2 Cache-oriented asynchronous KV Cache prefetching method to break through the memory bandwidth bottleneck in LLM inference through computation-load overlap.
  arXiv  Detail & Related papers  (2025-04-08T09:17:35Z)
• HeadInfer: Memory-Efficient LLM Inference by Head-wise Offloading [79.38548165722229]
  HEADINFER offloads the KV cache to CPU RAM while avoiding the need to fully store the KV cache for any transformer layer on the GPU.<n>We demonstrate HEADINFER maintains computational efficiency while significantly reducing memory footprint.
  arXiv  Detail & Related papers  (2025-02-18T06:26:05Z)
• vTensor: Flexible Virtual Tensor Management for Efficient LLM Serving [53.972175896814505]
  Large Language Models (LLMs) are widely used across various domains, processing millions of daily requests. Large Language Models (LLMs) are widely used across various domains, processing millions of daily requests.
  arXiv  Detail & Related papers  (2024-07-22T14:37:58Z)
• Cheddar: A Swift Fully Homomorphic Encryption Library Designed for GPU Architectures [2.613335121517245]
  Fully homomorphic encryption (FHE) frees cloud computing from privacy concerns by enabling secure computation on encrypted data.<n>We present Cheddar, a high-performance FHE library for GPU, achieving substantial speedups over previous GPU implementations.
  arXiv  Detail & Related papers  (2024-07-17T23:49:18Z)
• PyramidInfer: Pyramid KV Cache Compression for High-throughput LLM Inference [57.53291046180288]
  Large Language Models (LLMs) have shown remarkable comprehension abilities but face challenges in GPU memory usage during inference. We propose PyramidInfer, a method that compresses the KV cache by layer-wise retaining crucial context. PyramidInfer improves 2.2x throughput compared to Accelerate with over 54% GPU memory reduction in KV cache.
  arXiv  Detail & Related papers  (2024-05-21T06:46:37Z)
• FULL-W2V: Fully Exploiting Data Reuse for W2V on GPU-Accelerated Systems [5.572152653851948]
  FULL-W2V exploits the opportunities for data reuse in the W2V algorithm to reduce access to low memory levels and improve temporal locality. Our prototype implementation achieves 2.97X speedup when ported from Nvidia Pascal P100 to Volta V100 cards, and outperforms the state-of-the-art by 5.72X on V100 cards with the same embedding quality.
  arXiv  Detail & Related papers  (2023-12-12T21:22:07Z)
• GME: GPU-based Microarchitectural Extensions to Accelerate Homomorphic Encryption [33.87964584665433]
  Homomorphic Encryption (FHE) enables the processing of encrypted data without decrypting it. FHE introduces a slowdown of up to five orders of magnitude as compared to the same computation using plaintext data. We propose GME, which combines three key microarchitectural extensions along with a compile-time optimization to the current AMD CDNA GPU architecture.
  arXiv  Detail & Related papers  (2023-09-20T01:50:43Z)
• FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness [80.3586155104237]
  FlashAttention is an IO-aware exact attention algorithm for Transformers. It reduces the number of memory reads/writes between GPU high bandwidth memory (HBM) and GPU on-chip. FlashAttention and block-sparse FlashAttention enable longer context in Transformers.
  arXiv  Detail & Related papers  (2022-05-27T17:53:09Z)
• MCUNetV2: Memory-Efficient Patch-based Inference for Tiny Deep Learning [72.80896338009579]
  We find that the memory bottleneck is due to the imbalanced memory distribution in convolutional neural network (CNN) designs. We propose a generic patch-by-patch inference scheduling, which significantly cuts down the peak memory. We automate the process with neural architecture search to jointly optimize the neural architecture and inference scheduling, leading to MCUNetV2.
  arXiv  Detail & Related papers  (2021-10-28T17:58:45Z)
• FastFlowNet: A Lightweight Network for Fast Optical Flow Estimation [81.76975488010213]
  Dense optical flow estimation plays a key role in many robotic vision tasks. Current networks often occupy large number of parameters and require heavy computation costs. Our proposed FastFlowNet works in the well-known coarse-to-fine manner with following innovations.
  arXiv  Detail & Related papers  (2021-03-08T03:09:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.