Paper 2025/1200

Tricycle: Private Transformer Inference with Tricyclic Encodings

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.