Paper 2025/1200

Tricycle: Private Transformer Inference with Tricyclic Encodings

Vikas Kalagi, University of California, Santa Barbara

Julia Novick, University of California, Santa Barbara

Jiaming Liu, University of California, Santa Barbara

Divyakant Agrawal, University of California, Santa Barbara

Amr El Abbadi, University of California, Santa Barbara

Abstract

The growing deployment of large language models (LLMs) in privacy-sensitive settings demands inference mechanisms that preserve data confidentiality. Homomorphic encryption (HE) offers a principled solution by enabling computation directly on encrypted data; however, existing solutions struggle to scale to full LLMs. We present Tricycle, a system for efficient private transformer inference. At its core, Tricycle introduces tricyclic encodings, a novel packing scheme that enables batch matrix multiplications with optimal multiplicative depth while naturally supporting multi-head attention. Building on this foundation, we develop a suite of optimizations, including Baby-Step Giant-Step optimizations, optimized block matrix multiplications, lazy relinearization, and free attention complexification, that collectively minimize key-switching operations and improve performance. We further introduce statistical max estimation, a lightweight method for stabilizing softmax under HE. We implement Tricycle end-to-end on a GPU-accelerated CKKS pipeline and evaluate it on BERT models. For BERT-Base with 128 tokens, Tricycle achieves 100.5 seconds latency on a single GPU, yielding $6\times$ and $3.4\times$ speedups over prior state-of-the-art systems, Thor and Powerformer, respectively. These results demonstrate that careful design of packing, algorithms, and systems can significantly reduce the cost of private LLM inference, bringing practical deployment closer to reality.

@misc{cryptoeprint:2025/1200,
      author = {Lawrence Lim and Vikas Kalagi and Julia Novick and Jiaming Liu and Divyakant Agrawal and Amr El Abbadi},
      title = {Tricycle: Private Transformer Inference with Tricyclic Encodings},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1200},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1200}
}