TL;DR
This paper presents "Sylph," a novel framework for scaling Fully Homomorphic Encryption (FHE)-based inference of large language models (LLMs) like Llama-3-8B. Sylph achieves significant speedups and supports much longer input contexts than previous FHE methods by combining advanced FHE techniques with LLM-specific optimizations and a heterogeneous processing approach for public and private data.
What Problem Does This Paper Address?
As LLMs become increasingly integrated into applications, the privacy of user queries and generated outputs becomes a critical concern. Fully Homomorphic Encryption (FHE) offers a promising solution for confidential LLM inference, allowing computations on encrypted data without decryption. However, existing FHE-based LLM inference methods struggle with several key challenges:
- Scalability with Input Length: Current FHE solutions are inefficient for long input sequences, a common requirement for advanced LLM tasks.
- Computational Cost: FHE operations, especially for non-linear layers in LLMs, are computationally expensive, particularly when dealing with large outlier values in activations.
- Model Size: Applying FHE to large, modern LLMs like Llama-3-8B presents significant computational and memory hurdles.
- Heterogeneous Data: Many real-world LLM applications involve a mix of public (e.g., search results, system prompts) and private (e.g., user queries) data, requiring specialized handling.
This paper aims to overcome these limitations to enable practical, privacy-preserving inference for large LLMs.
Methods
Sylph employs a multi-pronged approach to accelerate FHE-based LLM inference:
- FHE-Aware Model Calibration: Techniques like "token prepending" and "orthogonal rotations" are used to mitigate the impact of activation outliers in LLMs. This reduces the dynamic range needed for FHE computations, improving efficiency and robustness without retraining the model.
- Heterogeneous Public/Private Prompt Processing: For long contexts, Sylph separates the prompt into public (cleartext) and private (encrypted) segments. This allows the public part to be processed efficiently in cleartext, while only the sensitive private part is handled under FHE. This leads to a new "PC-attention" mechanism for handling interactions between public and private data.
- Optimized FHE Circuits and Algorithms:
- Slim Polynomial Evaluation for SoftMax: A new method for evaluating SoftMax on sparsely-packed ciphertexts is introduced, leveraging unused message slots to speed up computation.
- Bootstrapping-Frugal PC-Attention: Specialized FHE algorithms are developed for PC-attention to minimize costly bootstrapping operations, crucial for handling wide public contexts. This includes a new "plaintext-ciphertext matrix multiplication" (PCMM) algorithm.
- FHE Circuit Design with Ciphertext Format Fusion: Sylph systematically fuses ciphertext format conversions into existing FHE operations like bootstrapping, reducing overhead.
- Scalable Distributed Execution: A distributed runtime for homomorphic Transformer inference is designed to scale across multiple GPUs, optimizing computation, communication, and ciphertext placement.
Datasets
Not discussed in the paper. The paper focuses on implementing and evaluating inference for the Llama-3-8B model.
Key Insights and Ideas
- Outlier Mitigation is Crucial for FHE: The paper strongly emphasizes that activation outliers in LLMs are a major bottleneck for FHE. Techniques that reduce these outliers significantly improve FHE efficiency and accuracy.
- Heterogeneous Processing is Key for Long Contexts: Processing public and private data separately is a game-changer for long-context FHE inference. It allows leveraging cleartext computation for the bulk of the data while protecting sensitive parts.
- Bootstrapping is the Enemy of Wide Computations: For operations like PC-attention that involve wide intermediate computations, minimizing bootstrapping is paramount. This drives the development of specialized, bootstrapping-light algorithms.
- FHE Algorithm Fusion is Essential: Combining and optimizing different FHE algorithms (e.g., for linear algebra, SoftMax) and systematically fusing format conversions is critical for building an efficient end-to-end system.
Key Results
- Significant Speedup for 128 Encrypted Tokens: On a cluster of 8 NVIDIA RTX PRO 6000 GPUs, Sylph achieves inference times of 20s for summarization and 18s per output token for generation. This is a substantial improvement over prior state-of-the-art solutions, which took 295s for summarization on more expensive H100 GPUs.
- Long Context Inference: For a heterogeneous input of 4096 tokens (last 128 encrypted), Sylph achieves summarization in 64s and generation in 22s per output token on the same hardware.
- Reduced Memory Footprint: The conversion of Llama-3-8B weights for Sylph results in a manageable expansion (around 4x) compared to the original 16-bit weights.
- Efficient GPU Scaling: The distributed runtime demonstrates strong scaling efficiency across 8 GPUs, with per-layer prefill latency reduced from 3.55s on one GPU to 0.55s on 8 GPUs.
Limitations and Future Work
- Focus on Prefill: The paper acknowledges that while decoding performance is improved, the most significant gains are in the prefill stage.
- Future Work: The authors suggest integrating speculative decoding techniques to further accelerate the decoding stage. They also mention the potential for further optimizations in machine learning for decoding.
Summary updated