ROSETTA：基于混合 CKKS/TFHE 的高效准确隐私保护 LLM 解码框架

FHE 下自回归解码的非线性算子延迟高，且单一方案无法同时兼顾精度与效率。

• 场景：生成式 LLM 多部署在云端，提示词可能含敏感信息。作者称 FHE 方案通信更省、客户端负担更低：客户端上传加密输入，服务器在密文上计算，只返回加密输出（Figure 1(a)）。
• 现有不足：prefill 适合 CKKS 的 SIMD；decode 一次只处理一个 token，部分算子并行度低。作者称 CacheMir 优化了线性部分后，非线性仍占 decode 总时间 70% 以上（Figure 1(b) 中 GPT-2 Base、TinyLlama-1.1B、LLaMA-3-8B，非线性约 76.8%）。PEGASUS 把全部非线性层交给 TFHE，LOHEN 只卸载前 k 层，作者称这些启发式不是最优。
• 观察：decode 中非线性算子在元素个数和输入动态范围上不一致。以 softmax 为例，exp 处理 n 个有界元素，求和后的 1/x 只有一个标量且范围更宽。全 CKKS 时 1/x 的 Goldschmidt 迭代总延迟 44.1s；全 TFHE 时 exp 无法批处理且有两次转换，共 57.9s，单次 PBS 约 11 bit，作者称相对明文基线可使 softmax perplexity 升高超过 100%（Table 8）。
• 威胁模型：标准两方隐私推理。服务器持有机密模型权重，客户端持有敏感输入；架构对双方公开。honest-but-curious：双方遵守协议，但可能试图多学信息。保证客户端得到正确输出，权重与输入均保密。
• 提出的方法：ROSETTA，混合 CKKS/TFHE。一是基于 TFHE 的自适应分段查找表（segmented LUT），在宽范围上做高精度非线性求值；二是方案感知的算子选择，把每个非线性算子分给 CKKS 或 TFHE，并同时分配 CKKS 乘法层，以降低端到端解码延迟。

引言把隐私推理分成三类，Table 1 再按非线性求值对比四类 FHE 框架。

• 纯 CKKS：CKKS [11, 12] 把多个明文打包进一条 RLWE 密文，适合 prefill 的 SIMD。纯 CKKS 框架 [38, 41, 59, 60] 与 CacheMir [55] 用多项式逼近非线性；CacheMir 还用最短路做 CKKS 层分配。作者称其对宽范围的 1/x 要多轮迭代并频繁自举，精度高但代价大，且受限于宽 SIMD。

• 混合 CKKS/TFHE：TFHE [13] 用 programmable bootstrapping（PBS）按元素查表。PEGASUS [27] 把全部非线性层转到 TFHE，用单张 LUT。LOHEN [63] 只卸载前 k 层，同样是单张 LUT。作者称单次 PBS 精度低（约 11 bit），且粗粒度启发式忽略了转换开销和周围 CKKS 层数。

• MPC 与混合 FHE/MPC：MPC [2, 18, 23, 30, 34, 56–58] 与混合 FHE/MPC [24–26, 29, 37, 39, 47, 48, 50, 51, 54, 62, 64]。作者称相对这些设计，纯 FHE 通信更省、客户端计算更少。方案转换使用 Ring Switch [4, 20]、LWE Extract / RLWE Repack [8, 13] 与 RLWE Trace [8]；高精度比较用 HomComp [5]。max-free softmax 沿用 [38, 55, 59] 的 normalize-and-square。

• 基线与基准：作者把 ROSETTA 与纯 CKKS 的 CacheMir [55]、混合的 PEGASUS [27] 对比；延迟分解基于 CacheMir，模型为 GPT-2 Base、TinyLlama-1.1B、LLaMA-3-8B。指标含 Softmax 与端到端延迟，以及 perplexity（PPL）相对明文的退化。

作者把本文定位为：分段 LUT 加多项式，精度高于单次 PBS；选择策略是按算子、并与 CKKS 层分配联合优化，而不是全 CKKS、全 TFHE 或前 k 层。

ROSETTA 只把适合 TFHE 的非算术原语卸下去，并用分段 LUT 补上单次 PBS 的精度上限；方案分配与 CKKS 层数在同一张 DAG 上一次求最短路。

问题设定

• 计算范围：只做 decode。一个 Transformer 块含 self-attention 与 SwiGLU FFN（Figure 4）。隐藏维 d_model（例 4096）、头数 h（例 32）、每头维 d、FFN 中间维 d_ffn（例 11008）、上下文长度 n。
• 注意力：单 token 输入经 Q/K/V 投影，K、V 追加到 KV-cache，再按式 (6) 做缩放点积 softmax 与输出投影。
• FFN：式 (7)，SiLU(x W_up) 与门控支路逐元素相乘后再 down 投影。标准 max 减法在 FHE 中昂贵，故沿用 normalize-and-square：从小范围上的 y_i = e^{z_i/2^k} 出发，把 Softmax(2x) 的恒等关系用 k 次，恢复 Softmax(z)。

自适应分段 LUT

• 单表问题：以 f(x)=1/x、域 [0.1, 2.0]、N_br=4 为例（Figure 5）。等间隔、区间中点常数逼近时，x=0.22 得到 2.963，精确值为 4.545，该点相对误差 34.8%，全域最大误差 70.4%。
• 构造：域分成 N_seg 段，边界按函数局部变化加密集（1/x 在近 0 处更密）。例中 N_seg=2，段为 [0.1, 0.5] 与 [0.5, 2.0]，作者称最大误差降到 33.3%。段内用线性 f(x)≈a_si·x+b_si；同一例子得到 4.571，相对误差 0.57%，最大误差 5.9%。二次逼近更准（Figure 5(e)），作者采用线性，称精度够且代价更小。
• 在线三步：1) 与各段边界比较并求和得到段号 S；2) 段内线性映射得到区间号 I；3) 取 (a_SI, b_SI) 做线性求值。明文例子 x=0.22 落入 S=0、I=1。

密文查找协议

• 障碍：S、I 也是密文，不能直接取系数。先用 PBS 取出系数再做 LWE 密文乘密文，需要 TFHE 不原生支持的高精度定点运算。
• 策略：online-construct-then-select（Figure 6）。先用 RLWE 明文–密文乘法，把所有候选 a_si·x+b_si 放进测试多项式，再用 PBS 按加密下标选出正确项。输入同时准备 JxK_RLWE（常数项编码）和 JxK_LWE。
• Step 1：每个 x≥τ_j 用 HomComp [5]（内部多步 PBS），再同态相加，共 N_seg−1 次比较。例中一次比较得到 S=0。
• Step 2–3：区间号与线性求值都走“先构造全部候选、再 PBS 选取”。协议只用 RLWE 明文–密文乘法与 PBS，作者称在宽范围上达到 12–19 bit，比单次 PBS 的约 11 bit 高 6–10 bit，并比 CKKS 迭代快 8–9×（§3）。

方案感知的算子选择

• 缩小搜索：一层里只有非算术原语（如 exp、1/x）才考虑 TFHE；算术运算留在 CKKS。
• 联合优化：每次 CKKS–TFHE 转换记成 CacheMir 层分配 DAG 上的边权；在每个非算术原语旁插入 level-0 的 TFHE 节点。最短路同时给出卸载哪些原语、以及每层的 CKKS 层数。作者称这避免了先比单算子延迟、再单独调层数的次优启发式（§4）。
• 转换原语：Ring Switch 在大环与小环之间拆并；LWE Extract / RLWE Repack 在打包 RLWE 与标量 LWE 之间转换；RLWE Trace 取出常数项。非线性求值前后用这些原语接回后续线性层。

实验设置

• 模型：延迟分解覆盖 GPT-2 Base、TinyLlama-1.1B、LLaMA-3-8B（Figure 1(b)）。架构例子给出 d_model=4096、h=32、d_ffn=11008，对应文中 LLaMA 块的举例，论文未在已读正文里逐模型列出全部超参。
• 基线：纯 CKKS 的 CacheMir [55]（作者称 SOTA），以及混合 CKKS/TFHE 的 PEGASUS [27]。LOHEN [63] 出现在 Table 1 的特性对比中，摘要中的数值对比对象是 CacheMir 与 PEGASUS。
• 算子微基准：softmax，n=1024。Figure 2(b) 给出 exp 与 Inv 在 CKKS、TFHE 及转换上的延迟；exp 输入范围 [-3, 3]，Inv 输入范围 [1, 403]。
• 指标：模块与端到端延迟（秒或小时）、加速比、PPL 相对明文基线的退化。精度用 bit 与相对误差描述分段 LUT。
• 评审方式：论文未说明用哪个模型计算 PPL，也未报告重复次数。Table 8 被引用为单次 PBS 使 softmax perplexity 相对明文升高超过 100%，表体未附在已读正文中。

主结果

设置	延迟或精度	出处
全 CKKS softmax，n=1024	44.1s（Inv 42.7s + exp 1.4s）	Figure 2(c)
全 TFHE softmax，n=1024	57.9s	Figure 2(d)
混合：exp 留 CKKS，1/x 交 TFHE	22.2s	Figure 2(e)
ROSETTA vs CacheMir	Softmax 最高 4.8×；端到端 1.5–2.1×	摘要、§1.1
ROSETTA vs PEGASUS	端到端 3–4×；平均 PPL 退化 +116% → +1.4%	§1.1

• 作者解读：Figure 2(b) 中 exp 在 CKKS 为 1.4s、TFHE 为 17.1s；Inv 在 CKKS 为 42.7s、TFHE 为 0.8s，转换 20.0s。作者称只把 1/x 交给 TFHE 能把两者的长处合在一起，总延迟到 22.2s。
• 端到端：作者称相对 CacheMir 端到端 1.5–2.1×，相对 PEGASUS 为 3–4×，同时把平均 PPL 退化从 +116% 降到 +1.4%。已读正文没有按模型拆开的端到端表。
• 精度：分段 LUT 作者称 12–19 bit，超出单次 PBS 约 11 bit 上限 6–10 bit，并比 CKKS 迭代快 8–9×（§3）。Figure 5 的示意点上，常数 LUT 相对误差 34.8%（最大 70.4%），线性分段后该点 0.57%（最大 5.9%）。

算子级延迟分解

• 测了什么：同一 softmax（n=1024）在全 CKKS、全 TFHE、混合三种赋值下的模块延迟（Figure 2）。
• 结果：全 CKKS 的大头是 Inv 的 42.7s；全 TFHE 的大头是 exp 的 17.1s 加上两次转换（图中 Lat.=20 出现多次），总计 57.9s；混合路径上 TFHE 的 Inv 为 0.8s、CKKS 的 exp 为 1.4s，总计 22.2s。
• 作者的解读：元素多、范围有界的 exp 适合 CKKS 低次多项式与 SIMD；标量、宽范围的 1/x 适合 TFHE。只比较单算子自身延迟不够，因为转换和相邻 CKKS 层数会改变总代价。

decode 阶段占比

• 测了什么：基于 CacheMir 的 GPT-2 Base、TinyLlama-1.1B、LLaMA-3-8B 延迟分解（Figure 1(b)），横轴为 Latency (hours)，范围约 0 到 5。
• 结果：图中非线性一块标为 76.8%。作者称非线性占 decode 总运行时间 70% 以上。
• 作者的解读：线性部分已被 CacheMir 优化后，decode 的主要开销在非线性算子，因此混合卸载有收益空间。

其他消融与分析

• 单段等间隔常数 LUT，域 [0.1, 2.0]、N_br=4：x=0.22 处相对误差 34.8%，全域最大误差 70.4%（Figure 5(a)(b)，§3.1）。
• 两段但常数逼近：作者称最大误差降到 33.3%（§3.1.1）。
• 两段加线性：该点相对误差 0.57%，最大误差 5.9%（Figure 5(d)(f)）。
• 二次逼近：Figure 5(e) 给出，作者称可再提高精度，但采用线性。
• 分段 LUT vs 单次 PBS：精度 12–19 bit 对约 11 bit，高 6–10 bit；相对 CKKS 迭代快 8–9×（§1.1、§3）。
• Table 1 为特性对比（多项式 / 单 LUT / 分段 LUT+多项式，全 CKKS / 全 TFHE / 前 k 层 / 按算子），没有额外数值。

作者指出的局限与后续方向

已读正文没有单独的 Limitations 或 Future Work 节。作者在引言把两件事写成混合方案落地前必须解决的挑战，而不是写成已完成工作之外的计划。

• 宽范围精度：TFHE 侧仍继承 PBS 对宽范围算子（如 1/x）的精度限制；单次 PBS 只编码小 LUT（例 2048 项），精度上限约 11 bit，作者称不足以覆盖宽动态范围（§1）。分段 LUT 是针对这一挑战的设计。
• 分配本身非平凡：把算子交给 TFHE 会改变该算子延迟，并引入方案转换，周围 CKKS 层的 level 也要一起设；只比较两个方案上各算子自身延迟不够（§1）。最短路配方是针对这一挑战的设计。
• 单方案不够：作者称 CKKS 精度高但贵、且受限于宽 SIMD；TFHE 适合逐元素、但给不出高精度（§1）。这是动机，不是单独列出的未完成项。

实验覆盖范围

• 延迟分解的模型为 GPT-2 Base、TinyLlama-1.1B、LLaMA-3-8B，基于 CacheMir（Figure 1(b)）。
• softmax 微基准为 n=1024，对比全 CKKS、全 TFHE 与“exp 在 CKKS、1/x 在 TFHE”（Figure 2）。
• 数值对比的框架为 CacheMir 与 PEGASUS；LOHEN 只出现在 Table 1 的策略对照（前 k 层、单 LUT、低精度）。
• 精度证据包括 Figure 5 的 1/x 示意误差，以及作者报告的 12–19 bit、PPL 退化从 +116% 到 +1.4%（相对 PEGASUS 的平均）。
• 威胁模型为 honest-but-curious 两方，架构公开；论文未在已读正文报告恶意敌手下的实验、通信字节数或重复次数。

ROSETTA 是面向 LLM decode 的混合 CKKS/TFHE 隐私推理框架，目标是在 honest-but-curious 两方设定下，让服务器在密文上完成解码，同时保住权重和用户输入。

• 问题：decode 一次一个 token，非线性算子占 CacheMir 分解中 70% 以上（Figure 1(b) 标 76.8%）。全 CKKS 对宽范围 1/x 要多轮迭代（n=1024 时 softmax 44.1s）；全 TFHE 不能批处理 exp，还有转换，共 57.9s，且单次 PBS 约 11 bit。
• 方法：自适应分段 LUT 按函数曲率切非均匀段，段内线性插值；密文侧先做全部候选的明文–密文乘法，再用 PBS 选出，避开 TFHE 不支持的密文乘密文定点运算。只对 exp、1/x 这类非算术原语做方案选择，把转换代价写进层分配 DAG，一次最短路决定卸载对象和 CKKS level。
• 结果：Figure 2(e) 的混合赋值把 softmax 降到 22.2s。作者称相对 CacheMir，Softmax 最高 4.8×，端到端 1.5–2.1×；相对 PEGASUS，端到端 3–4×，平均 PPL 退化从 +116% 降到 +1.4%。分段 LUT 作者称 12–19 bit，比单次 PBS 高 6–10 bit，并比 CKKS 迭代快 8–9×。示意例子里，线性分段把 1/x 在 x=0.22 的相对误差从 34.8% 降到 0.57%。
• 作者的结论：非线性算子负载不均，应按算子而不是按整层选方案；分段 LUT 用来补 PBS 的精度上限，联合最短路用来计入转换与层数，从而同时要效率和精度。