PaperlayerView exact revision on arXiv

Source-linked AI summary

ROSETTA: Efficient and Accurate Privacy-Preserving LLM Decoding via Hybrid CKKS/TFHE Evaluation

Jiangrui Yu, Baosheng Zhang, Liang Kong, Lin Ding, Yi Chen, Ye Yu, Mingzhe Zhang, Meng Li

arXiv:2609.16915v1cs.CR

TL;DR

Sensitive prompts motivate private LLM inference, but nonlinear operations make FHE decoding inefficient and heterogeneous workloads complicate scheme choice. ROSETTA combines adaptive segmented lookup tables with joint CKKS/TFHE operator and level optimization. It reports speedups over CacheMir and PEGASUS alongside lower PPL degradation than PEGASUS.

  • Problem

    FHE-based LLM decoding faces costly nonlinear operations with heterogeneous workloads that make a one-size-fits-all scheme assignment suboptimal.

    Source: §1 · pp. 1–2

  • Method

    ROSETTA combines an adaptive segmented TFHE lookup-table protocol with shortest-path optimization of non-arithmetic operator schemes and CKKS-level allocation.

    Source: §1.1 · pp. 2–3

  • Results

    Up to 4.8× Softmax speedup and 1.5–2.1× end-to-end speedup over CacheMir; versus PEGASUS, 3–4× end-to-end speedup and average PPL degradation falls from +116% to +1.4%.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    ROSETTA takes a meaningful step toward practical secure LLM inference, with reported speedups over prior frameworks and negligible PPL degradation.

    Source: §6 · p. 13

    The security setting assumes a publicly known model architecture and honest-but-curious parties who follow the protocol.

    Source: §2.4 · p. 5

Abstract

from arXiv · show

Generative large language models (LLMs) have achieved state-of-the-art performance on many real-world tasks such as code generation and question answering. These models predominantly rely on an autoregressive decoding strategy that generates output tokens sequentially. However, their pervasive deployment raises serious privacy concerns, motivating private inference frameworks based on fully homomorphic encryption (FHE). A major limitation of existing FHE frameworks is their inefficiency in evaluating nonlinear operations, which incur substantial overhead and dominate the decode stage. In this paper, we propose ROSETTA, a hybrid CKKS/TFHE framework that overcomes this limitation. We first observe that nonlinear operations in the decode stage exhibit heterogeneous workload patterns, which can be handled effectively via a hybrid approach. We then realize this with two key contributions: 1) an adaptive segmented lookup-table protocol based on TFHE that enables efficient and accurate evaluation of nonlinear operations; and 2) a scheme-aware operator-selection framework that automatically assigns each nonlinear operator to CKKS or TFHE to minimize end-to-end decoding latency. We demonstrate that ROSETTA achieves up to $4.8\times$ Softmax speedup and $1.5$--$2.1\times$ end-to-end speedup over the SOTA framework CacheMir.

1 Introduction

Cloud LLM prompts can contain sensitive information, while nonlinear operators dominate decode latency and respond differently to CKKS and TFHE. ROSETTA addresses these challenges with adaptive segmented lookup tables and joint scheme-aware optimization, achieving speedups over CacheMir and PEGASUS.

1 Introduction

  • Cloud-hosted LLM prompts may contain sensitive information, and nonlinear operators account for more than 70% of decode runtime in CacheMir.FHE-based inference lets the server compute over encrypted inputs, protecting user inputs and proprietary model weights.Source: §1 · pp. 1–2
  • Decode nonlinear operators vary in element count and input range: CKKS handles batched exp efficiently but makes wide-range reciprocal costly, while TFHE limits batching and single-PBS precision.The introduction reports 44.1s for all-CKKS Softmax, 57.9s for all-TFHE, and 22.2s for a hybrid assignment.Source: §1 · p. 2

1.1 Contribution

  • The adaptive segmented LUT uses non-uniform segments with piecewise-linear interpolation to concentrate entries where a function varies rapidly, reaching 12–19-bit precision over wide ranges.The protocol uses homomorphic comparisons and PBS lookups, avoiding ciphertext–ciphertext fixed-point arithmetic.Source: §1.1 · p. 2
  • A shortest-path formulation jointly selects TFHE for non-arithmetic primitives and allocates CKKS multiplicative levels, accounting for scheme-conversion costs.The optimizer leaves arithmetic operations under CKKS and incorporates conversion costs as edge weights in an augmented DAG.Source: §1.1 · p. 3
  • Up to 4.8× Softmax speedup and 1.5–2.1× end-to-end speedup over CacheMir; versus PEGASUS, 3–4× end-to-end speedup and average PPL degradation falls from +116% to +1.4%.The reported comparisons evaluate ROSETTA against the pure-CKKS CacheMir and hybrid PEGASUS frameworks.Source: §1.1 · p. 3

2 Background

The background introduces CKKS and TFHE, the ciphertext conversions used to bridge them, and the Transformer operations relevant to decoding. It also specifies the private-inference setting and security model.

2.1 Notation

  • The notation uses bold lowercase letters for vectors, hatted lowercase letters for polynomials, and R_N,Q for the 2N-th cyclotomic ring modulo Q.Source: §2.1 · p. 3

2.2 FHE Schemes

  • The framework uses CKKS and TFHE, both of which can be instantiated over standard lattice hardness problems.Source: §2.2 · p. 3

2.2.1 The CKKS Scheme.

  • CKKS natively packs multiple data elements into an RLWE ciphertext polynomial and supports element-wise ciphertext addition and multiplication.Source: §2.2.1 · pp. 3–4

2.2.2 TFHE Scheme.

  • TFHE encrypts a single scalar in LWE form; PBS evaluates a lookup table homomorphically while refreshing ciphertext noise.Source: §2.2.2 · p. 4

2.2.3 Scheme Conversion and Other Primitives.

  • Scheme-conversion operators bridge packed RLWE and scalar LWE ciphertexts; ring switching changes ring degree, extraction and repacking convert formats, and trace isolates the constant term.Source: §2.2.3 · p. 4

2.3 Modern LLM Architecture

  • Transformer decoding uses self-attention with query, key, and value projections and a KV-cache, alongside an FFN with up and gate projections, SiLU, and a down projection.Source: §2.3 · pp. 4–5
  • The paper uses a max-free Softmax formulation that starts with exponentials on a small range and repeatedly applies Softmax(2x)_i = y_i^2 to recover Softmax(z).Source: §2.3 · p. 5

2.4 Threat Model

  • The server holds confidential model weights and the client holds sensitive inputs; both follow the protocol but may try to learn additional information, while the architecture is public.Source: §2.4 · p. 5

3 Segmented LUT Evaluation

ROSETTA uses adaptive segmented lookup tables to improve nonlinear-function accuracy, then realizes encrypted lookup through a construct-then-select protocol and CKKS/TFHE conversion. It also supports independent multi-value evaluations with shared conversions.

3.1 Adaptive Segmented LUT Construction

  • A single LUT uses equally spaced intervals and midpoint constants, producing large approximation errors when intervals are wide or inputs lie far from their midpoints.For x=0.22, the baseline returns 2.963 rather than the exact 4.545.Source: §3.1 · p. 5

3.1.1 Adaptive LUT Construction.

  • The adaptive construction divides the domain into non-uniform segments and stores a linear approximation for each interval, concentrating entries where the function varies most rapidly.The paper adopts the linear variant over higher-order alternatives as a sufficient-accuracy, minimal-cost choice.Source: §3.1.1 · pp. 5–6, Figure 5 · p. 5
  • 5.9% maximum error for the segmented linear variant, versus 70.4% for the single-LUT baseline; at x=0.22, relative error is 0.57% versus 34.8%.The input domain is partitioned non-uniformly, with more entries near zero where 1/x varies rapidly; each interval uses a precomputed linear approximation.Source: §3.1 · p. 5, §3.1.1 · p. 6, §3.1.2 · p. 6

3.1.2 Online Lookup Evaluation.

  • Online cleartext lookup finds the segment and local interval, then retrieves the corresponding coefficients and evaluates the linear approximation.For x=0.22, the reported approximation is 4.571 against the true value 4.545.Source: §3.1.2 · p. 6

3.2 Cryptographic Lookup Protocol

  • The encrypted protocol constructs candidate results before selecting the correct one with PBS, avoiding unsupported high-precision fixed-point arithmetic on LWE ciphertexts.It uses encrypted segment and interval indices to select the matching precomputed linear evaluation.Source: §3.2 · pp. 6–7

3.3.1 Input Preparation and Output Conversion.

  • Input preparation converts SIMD CKKS data into coefficient form, derives RLWE and LWE inputs for lookup, then converts the result back to CKKS.RingSwitch reduces the ring dimension for lookup; RingSwitch and ModRecover restore the result to the full ring and SIMD domain.Source: §3.3.1 · pp. 7–8, Figure 7 · p. 8

3.3.2 Multi-Value Batching.

  • For K independent nonlinear evaluations, ROSETTA performs SlotToCoeff once, prepares each value for lookup, then recombines outputs with one RingSwitch and one ModRecover.The method applies when multiple values, such as attention-head reciprocals in Softmax normalization, need separate evaluations.Source: §3.3.2 · p. 8

4 Scheme-Aware Operator Selection

ROSETTA selects schemes at the primitive level rather than assigning an entire nonlinear layer to TFHE. It extends level scheduling to jointly account for CKKS computation, TFHE evaluation, and conversion costs.

4.1 Operator Categorization

  • Only non-arithmetic primitives are TFHE candidates; arithmetic operations remain in CKKS, reducing the assignment search space.For example, RMSNorm’s reciprocal square root is its only non-arithmetic primitive, while its other six primitives remain in CKKS.Source: §4.1 · pp. 8–9, Figure 8 · p. 9

4.2 Scheme-Aware Placement

  • Scheme assignment cannot be optimized per primitive in isolation because it changes surrounding layers’ level requirements and CKKS–TFHE conversion costs.The LWE-to-CKKS target level affects conversion cost, so TFHE evaluation, conversion, and neighboring-layer costs must be considered together.Source: §4.2 · p. 9
  • The framework extends CacheMir’s level-management DAG by adding TFHE nodes at non-arithmetic primitives and encoding conversion costs in the path choices.The augmented DAG’s shortest path provides the minimum-latency schedule.Source: §4.2 · pp. 9–10, Figure 9 · p. 10
  • The scheme-aware shortest path jointly chooses TFHE or CKKS for non-arithmetic primitives and assigns layer input levels to minimize latency.TFHE nodes are injected at level 0, and the augmented graph accounts for conversion back to CKKS; its shortest path determines both scheme choices and the level schedule.Source: §4.2 · p. 10, Figure 9 · p. 10

5 Evaluation

ROSETTA is evaluated on nonlinear micro-benchmarks, end-to-end decode latency, and model perplexity across several models and settings. It outperforms the cited baselines on latency while keeping perplexity degradation low in the reported tests.

5.2 Micro-benchmarks

  • 2.2–4.8× faster than pure-CKKS baselines and 1.3–6.1× faster than PEGASUS on Softmax, with precision gains over PEGASUS of 4–9 bits.ROSETTA gains 2–5 bits over pure-CKKS baselines on wide ranges, where those methods degrade or fail to run.Source: Table 4 · p. 11, §5.2 · p. 11
  • 1.6× speedup over Cho on wide-range Softmax, with an 8–14-bit precision advantage in long-context settings.On [−128, 128], ROSETTA reaches 17–18 bits at n≥2k, while Cho drops to 9, 9, and 4 bits at n=2k, 4k, and 8k.Source: Table 5 · p. 11, §5.2 · p. 11

5.1 Experimental Setup

  • Experiments cover GPT-2 Base, TinyLlama-1.1B, and LLaMA-3-8B without fine-tuning; CacheMir is the directly comparable pure-CKKS decode baseline.The evaluation also integrates MOAI and NEXUS nonlinear methods and uses PEGASUS as a representative all-TFHE hybrid baseline.Source: §5.1 · p. 11

5.2 Micro-benchmarks

  • 2.4–7.4× faster than pure-CKKS baselines on RMSNorm and LayerNorm, and 3–11 bits more precise than PEGASUS across configurations.ROSETTA achieves comparable latency to PEGASUS for inverse square root on a single scalar.Source: Table 6 · p. 12, §5.2 · p. 12

5.3 End-to-End Performance

  • 1.5–2.1× end-to-end speedup over CacheMir across models and context lengths; on GPU, ROSETTA achieves 1.4–2.0× speedup over CacheMir.Latency measures one-token generation, excluding prefill; all methods share identical linear-layer implementations and differ only in nonlinear operators.Source: Table 7 · p. 12, §5.3 · p. 13

5.4 End-to-end Model Perplexity Evaluation

  • ROSETTA keeps PPL degradation below +4.3% on every evaluated model–dataset pair (average +1.4%), while PEGASUS ranges from +8% to +360% (average +116%).The ciphertext-aligned plaintext test replaces every nonlinear operation with its FHE counterpart.Source: Table 8 · p. 12, §5.4 · p. 13

5.2 Micro-benchmarks

  • 8–9× faster than Goldschmidt for 1/x and 1/√x, with 12.5–16.9 bits of precision versus PEGASUS’s 5–7 bits.Goldschmidt requires many iterations, consumes multiple multiplicative levels, and triggers frequent bootstraps.Source: Table 9 · p. 13, §5.2 · p. 13
  • 2.7–2.9× faster than a degree-59 Chebyshev approximation on SiLU and GELU, with comparable precision of 15.5–16.8 bits versus 12.4–15.2 bits.PEGASUS achieves only 5.8–6.5 bits on these benchmarks.Source: Table 10 · p. 13, §5.2 · p. 13

6 Conclusion

ROSETTA combines hybrid CKKS/TFHE decoding with adaptive segmented lookup tables and scheme-aware operator selection. Experiments show speedups over prior frameworks with negligible PPL degradation.

6 Conclusion

  • ROSETTA combines an adaptive segmented LUT protocol with a scheme-aware operator selector that jointly optimizes per-operator scheme assignment and CKKS-level allocation via shortest-path search.The paper reports significant speedup over prior frameworks with negligible PPL degradation.Source: §6 · p. 13

A Open Science

The authors report public access to the models and WikiText-2 corpus used, along with publicly available code and experiment-replication materials.

A Open Science

  • The pre-trained models, WikiText-2 corpus, source code, and experiment-replication materials are publicly accessible through the cited original sources and artifact repository.The paper invites feedback and contributions to the implementation and research.Source: A Open Science · p. 15

B Ethical Considerations

The authors state that their experiments use publicly accessible models and datasets and do not intentionally process sensitive personal information. They report no added privacy risk beyond the underlying FHE primitives and assumed threat model.

B Ethical Considerations

  • ROSETTA runs entirely under FHE on ciphertext-aligned activations and weights, with no additional privacy risk beyond the underlying CKKS and TFHE primitives or prior FHE-LLM threat models.The paper states that its experiments do not intentionally collect or process proprietary, sensitive, or personally identifiable information.Source: B Ethical Considerations · p. 15
  • The authors state that the work follows ACM ethics principles of respecting user privacy and avoiding harm.The paper describes its models and datasets as publicly accessible.Source: B Ethical Considerations · p. 15
  • The authors identify no need for formal human-subject review because the research involves no human subjects and intentionally collects or processes no sensitive personal information.The stated rationale also includes the absence of proprietary information.Source: B Ethical Considerations · p. 15

C Generative AI Disclosure

Generative AI tools supported implementation, benchmarking, typesetting, and manuscript editing. The authors say they thoroughly inspected, validated, and revised all AI-assisted content and assume full responsibility for the work.

C Generative AI Disclosure

  • Generative AI tools supported code implementation, benchmark configuration, LaTeX typesetting, and editing and polishing parts of the manuscript.Source: C Generative AI Disclosure · p. 15
  • The authors say they thoroughly inspected, validated, and revised all AI-assisted content and assume full responsibility for the work’s accuracy, originality, and integrity.Source: C Generative AI Disclosure · p. 15

Related papers

Loading 2609.16915v1…