BOLT: Privacy-Preserving Transformer Inference with Two-Party MPC + BFV

0. At a Glance

One-line positioning: BOLT is a semi-honest two-party (2PC) system for privacy-preserving Transformer inference — server P1 holds the fine-tuned BERT weights and client P2 holds the input. It pushes all matrix multiplications into the BFV ciphertext domain (compact packing + BSGS to cut rotations + ciphertext-by-ciphertext multiplication), leaves only the nonlinear layers to 2-out-of-2 secret-sharing MPC, and uses the conversion between HE and MPC to incidentally reset the noise, thereby avoiding bootstrapping altogether.

The key tradeoff behind this positioning is: HE saves communication but costs computation, MPC saves computation but costs communication (§2.3 says exactly this). BOLT assumes compute will keep getting cheaper and that network bandwidth is the real bottleneck, so it moves as much cost as possible onto the compute side; it also optimizes overall (offline + online) cost rather than only online time (stated explicitly at the end of §3).

One-line reading: BOLT is not "a faster MPC"; it is the paper that moved MatMul out of MPC into HE and thereby rediscovered that the bottleneck now sits in the nonlinear layers.

1. Problem and Positioning

1.1 Why pure MPC is so expensive for Transformers

Earlier PPML systems (Gazelle, Delphi, Cheetah) optimized matrix-vector multiplication, because in a CNN the weight matrix times one activation vector is all that is needed. Transformers do not have this shape (§1 contributions, start of §4):

• Matrix-matrix multiplication is the main course. Each BERT-base layer has at least 7 MatMuls (the three Q/K/V projections, Q·Kᵀ, Softmax·V, and the two FFN stages; expanding over heads gives even more); activations are 128×768 and the FFN intermediate is 128×3072.
• Under 2PC, MatMul uses Beaver triples, and its communication volume grows with the number of matrix elements × the bit width; stacked over 12 layers this becomes an order-of-magnitude problem.
• Nonlinearities are just as expensive: Iron self-reports that over 75% of total runtime goes to the nonlinear layers, because it translates GELU/Softmax/Tanh directly into MPC protocols for trigonometric functions, exponentials and LUTs (start of §5).

Iron is the SOTA before BOLT and the only 2PC system that covers standard Transformer inference completely. Its problems can be quantified directly (Iron is not open source; BOLT reimplemented it and confirmed the implementation with the Iron authors, §7.1.4):

Iron end-to-end: 280.99 GB communication, 216 minutes (100 Mbps / 80 ms WAN), BERT-base 110M
Per-layer communication (Tab. 3): Linear 1 4844 MB + Softmax×V 4918 MB + Softmax 3596 MB
                                + GELU 7960 MB + LayerNorm 871 MB + rest ≈ 22449 MB

Summing Tab. 3, Iron's single layer is about 22.45 GB, and times 12 layers that is already about 269 GB, so the 280.99 GB end-to-end figure is self-consistent. Of this, the 4918 MB for Softmax×V exists because Iron performs ciphertext-by-ciphertext matrix multiplication in MPC — exactly the place BOLT most wants to change.

1.2 BOLT's positioning: optimizing only the "communication" cost term

BOLT's argument chain is (start of §1): compute can be parallelized and hardware-accelerated (the paper cites several works on FHE hardware acceleration), but network communication does not get faster by itself, so communication must be the primary optimization target. Its architectural choices follow from this:

• linear layers → entirely in HE (even ciphertext-by-ciphertext goes to HE), because HE is cheap in communication;
• nonlinear layers → entirely in MPC secret sharing, because doing complex nonlinearities in HE either explodes in depth or degenerates into table lookups;
• convert between the two representations along the way, incidentally "washing out" the HE noise, so that no bootstrapping is needed (§3).

One easily overlooked detail: BOLT states that it optimizes overall execution cost rather than online cost alone, on the grounds that compressing only online time introduces extra precomputation, memory and storage overheads (§3, citing [22]). This is also the watershed between BOLT and later pure-HE schemes (near-zero online communication but extremely heavy offline/compute cost) in terms of cost philosophy.

1.3 Four contributions (in the paper's order)

The paper's "Our contributions" formally lists three bullets; the fourth point is the closing combined-results paragraph. They are listed here as four points, and this is noted:

1. Communication-optimized and compute-efficient linear operations. Using "another reading of ciphertext-plaintext MatMul" it achieves compact packing (no empty slots left), then uses BSGS to move rotations from the input ciphertext onto the partial sums (rotations drop 2.33×–9.33× on BERT-base), and finally gives a low-multiplicative-depth ciphertext-by-ciphertext MatMul (§4).
2. Accurate and efficient nonlinear operations. GELU uses a 4th-order polynomial and Tanh a 5th-order one (both with piecewise splitting and symmetry exploitation); Softmax uses a LUT-free integer exponential protocol; and Motzkin polynomial preprocessing reduces the multiplication count of an order-n polynomial from n−1 to about ⌈n/2⌉ (§5).
3. Machine-learning-level optimizations. It uses attention scores for oblivious word elimination (obliviously sorting away low-contribution tokens, reducing m from 128 to 64), and secure-computation-aware fine-tuning (putting fixed-point quantization and the approximation functions into the training forward pass), holding the accuracy loss to about 1% (§6).
4. System-level results (the paper's closing paragraph, not a bullet): after combining the above optimizations, communication drops 10.91× and end-to-end speedup is 4.8×–9.5×; the code is open-sourced (github.com/Clive2312/BOLT).

Judgment: item 1 is the paper's "hard contribution" (later work can compare against it item by item as a baseline); items 2 and 3 are the necessary conditions that make item 1 usable — if the nonlinear accuracy collapses, low communication is meaningless. Iron's LayerNorm bug illustrates precisely this: in privacy-preserving inference, an algebraically correct simplification can fail completely because it breaks the model's structure.

2. Method Anatomy

2.1 Two-party architecture and threat model

• Roles: P1 = server (holds the model weights and the inference service), P2 = client (holds the text input). This is standard MLaaS turned into 2PC.
• Threat model: both parties are semi-honest (honest-but-curious); they follow the protocol but passively mine information from the transcript (§3). The paper gives two reasons for choosing semi-honest: the server is providing a service, so the two parties must trust each other to some degree anyway; and only semi-honest yields practically usable performance.
• Public information: the model architecture, the per-layer parameter counts and scales, and the tokenization are all public; tokenization is frozen during private fine-tuning (because BERT's tokenizer was trained on a large public corpus). Inference results are not hidden — that is part of the ideal functionality, and differential privacy can be layered on top if needed (§3).
• Cryptographic foundations:
  • MPC: 2-out-of-2 additive secret sharing, x = ⟨x⟩1 + ⟨x⟩2 mod 2^ℓ; addition is free locally, multiplication goes through OT (§2.3).
  • HE: leveled BFV, explicitly not FHE, because bootstrapping is still too expensive (§2.3).
  • Numerics: fully fixed-point. y = ⌊x·2^s⌋ mod 2^ℓ; MPC works over Z_2^ℓ and HE over Z_p, hence the need for conversion.
• The conversion actually runs in one direction only (§7.1.2): the MPC → HE step is omitted because the overflow probability of a shared value is only |x|/2^ℓ, negligible when ℓ=37 and the values are small; the implementation therefore keeps only the HE → MPC conversion. To reduce error, GELU results are first widened from 21 bits to 37 bits before conversion. Each conversion costs roughly one comparison plus one MUX.

2.2 Linear layers: putting all MatMul into BFV

2.2.1 Compact packing (§4.1.1)

Let C = A × B, where A ∈ Z_p^{m×d1} is ciphertext and B ∈ Z_p^{d1×d2} is plaintext. BOLT's key observation is not "inner products" but looking at it column-wise:

column j of C = Σ_i B[i,j] · column i of A

That is, every column of C is a linear combination of the columns of A, with scalar coefficients taken from B. Hence:

• A is packed by column (the m elements of one column go into one ciphertext; m is exactly BERT's token length 128, and since BFV's n is a power of 2, slot utilization is high);
• B follows Gazelle's diagonal packing, but each b_ij is replicated m times, so that a single SIMD multiplication multiplies an entire column of A by the same scalar;
• the output C is naturally column-packed with every slot occupied — "perfectly compact output packing".

By contrast: Gazelle must pad d=768 to 1024 (wasting 25% of the slots), and Iron's coefficient packing avoids rotations but produces a very sparse result whose coefficients are mostly useless, so communication actually grows (App. A). Tab. 1 gives hard numbers for the same dimensions (m=128, d1=768, d2=64, n=8192):

Reading the table: Iron's rotation count is 0, but its ciphertext count is 56 versus BOLT's 13 — Iron trades "more ciphertexts" for "zero rotations", and that trade loses when bandwidth is the constraint. This is the epitome of BOLT's "trade computation for communication" throughout the paper.

2.2.2 BSGS: moving rotations from the input onto the partial sums (§4.1.2)

Compact packing creates a new problem: one ciphertext now carries several columns, so partial sums land in the slots of the same ciphertext and must be summed via rotations; done naively this costs O(d1) rotations (hundreds of them when d1=768).

BOLT generalizes baby-step giant-step from matrix-vector to matrix-matrix:

• split the d1 columns into a baby-step group and a giant-step group;
• rotate the input ciphertext only a handful of times, with the remaining rotations acting on the partial sums;
• when the right-hand plaintext matrix is tall-and-skinny (large d1, small d2), additional partial sums can be formed along the row direction — an opportunity that the matrix-vector setting does not offer.

The paper's example: rotating the input ciphertext only 2 times brings the total rotation count from 6 down to 3. Overall, rotations on BERT-base drop 2.33×–9.33× (§1), and 756 → 43 (17.58×) at the single-head attention dimensions (Tab. 1, §4.1.2). Tab. 5 in App. F gives the concrete numbers for all four linear layers of the full model:

             Linear 1   Linear 2   Linear 3   Linear 4
w/o BSGS       756        756        756        3024
w/  BSGS       288        168        324         324

Note that Linear 4 (128×3072 → 128×768) saves the most (9.33×), while Linear 3 saves only 2.33× — the gain depends strongly on the matrix shape and on the factorization of d1, and there is no constant that holds for all layers.

2.2.3 Ciphertext by ciphertext: why 2D rotation is impossible, and the workaround (§4.1.3)

Two MatMuls in a Transformer have ciphertexts on both sides: Q·Kᵀ and Softmax·V. BOLT insists on doing them in HE (Iron uses MPC), at the price of handling two kinds of packing in BFV:

1. Column packing × row packing (Q·Kᵀ): taking the outer-product view C = Σ_i A_i ⊗ B_i, a direct multiplication produces a diagonal of C; obtaining the other diagonals requires rotations within the rows of B — for BERT-base attention, a 128×64 2D rotation.
2. Diagonal packing × column packing (Softmax·V): the left matrix is square and the right one is column-wise, so a different rearrangement is needed.

Why BFV cannot do 2D rotations (the key sentence in the paper): a BFV rotation is a Galois automorphism in the NTT domain, so it can only rotate by powers of a root of unity; a genuinely two-dimensional rotation (over rows and columns at the same time) is not supported — the paper even says that for n=8192 it is not known whether generators of orders 64 and 128 that span the whole space exist (p. 4758).

The workaround: synthesize the 2D rotation from partial rotations plus bit masks. The paper's example squeezes a 2×4 matrix into an 8-dimensional vector; shifting left by one column becomes "shift everything left by 1" and "shift everything right by 3", each multiplied by the masks ⟨1,1,1,0,1,1,1,0⟩ and ⟨0,0,0,1,0,0,0,1⟩ respectively and then added. Mask multiplication increases multiplicative depth (originally depth 4); BOLT merges the "rotation-correction mask" with the "compact-output mask", bringing depth from 4 down to 3 (the paper says 2 would be optimal), trading more multiplications/rotations for smaller BFV parameters. The second packing works the same way: rather than repacking (which would inflate the RHS by 128×), it rearranges the LHS in place with mask + rotation + addition.

The payoff shows up directly in Tab. 3: Linear 1 goes from 4844.14 MB to 7.06 MB (686.1×), and Softmax×V from 4918.38 MB to 9.88 MB (497.6×) — the two largest single-point improvements in relative terms (measured excluding W.E.).

2.3 Nonlinear layers: accuracy is "designed" in (§5)

Nonlinear layers are BOLT's second battleground. Its general recipe is: exploit the function's own linear tails and symmetry to halve the approximation interval, then use Remez to find minimax coefficients, and finally use Motzkin preprocessing to halve the multiplication count.

Motzkin preprocessing (§5.1, App. B): evaluating an order-n polynomial by Horner needs n−1 multiplications; when the coefficients are publicly known (always the case in inference), Motzkin restructuring reduces this to about ⌈n/2⌉ multiplications. Concretely in this paper: order 4 needs only 2 secret-shared multiplications, order 5 only 3.

GELU (§5.2): 4th order, three segments.

ApproxGELU(x) = x                                          if x > 2.7
              = a|x|⁴ + b|x|³ + c|x|² + d|x| + e + 0.5x    if |x| ≤ 2.7
              = 0                                          if x < −2.7

Three design points are worth recording:

• Linear tails: lim GELU(x) = x (at +∞) and = 0 (at −∞), so only [−2.7, 2.7] needs approximation, which already suffices to guarantee a mean absolute error of 1×10⁻³.
• Symmetry: g(x) = x·erf(x/√2) is even, so only the positive half-axis needs approximating.
• Approximating x·erf(x) instead of erf(x): this is the key change relative to I-BERT. If one follows I-BERT and first approximates erf(|x|) and then multiplies by x, Motzkin preprocessing cannot be fully exploited (the multiplication count is not optimal); approximating the product term directly is what buys 2 multiplications.
• The coefficients come from Remez (iteratively minimizing the maximum deviation) rather than from I-BERT's grid-search interpolation.

Accuracy: mean ULP error 4 (scale 12), corresponding to a floating-point error of 9.77×10⁻⁴, over the interval [−5, 5]. The implementation also saves one comparison: it only needs to test b = |x| > 2.7 and output b ? RELU(x) : GELUP1(x), where RELU(x) = (|x| + x) >> 1.

Tanh (§5.3): 5th order, three segments, breakpoint 2.855, odd symmetry so that only 2 comparisons are needed, and 3 multiplications after Motzkin. Accuracy ULP 27, corresponding to 6.59×10⁻³. Tanh is used only in the pooler/classifier and not in the 12-layer trunk, so its accuracy requirement can be one notch looser.

Softmax (§5.4): no LUT at all (Iron uses SIRNN's LUTs, and communication explodes at long input bit widths). The protocol has three steps:

1) Subtract the maximum: x̃ = x − x_max, making every entry non-positive
2) Decompose: x̃ = (−ln2)·z + p, where z is a non-negative integer and p ∈ (−ln2, 0]
3) Small-range polynomial: exp(p) ≈ 0.3585·(p + 1.353)² + 0.344
   then exp(x̃) = exp(p) >> z

Details: z is a secret-shared value, so "shift right by z bits" must be implemented with a chain of MUXes; since exp(p) ∈ (0, 0.7), z can safely be clipped to [0, s+1]; the range of p is small, so its bit width can be trimmed by another s+2. Accuracy ULP 0.0059, corresponding to 1×10⁻⁶, with input interval [−1000, −0.001]. The reciprocal is only invoked over the d dimension, directly reusing SIRNN's secure reciprocal.

LayerNorm: BOLT does not adopt Iron's fused simplification (see 2.4); instead it computes μ and σ in MPC, moves the multiplications by γ/β into HE, and precomputes the MSB of X − μ to reduce the communication of the subsequent multiplications (§7.1.3). This is a direct instance of "structural correctness over saving one multiplication".

Conversion overhead: the conversion between HE and MPC accounts for about 2%–9% of end-to-end runtime (§7.5.3); if "correct truncation" is used to reduce error further, the conversion cost doubles, at a performance cost of about 3%–7%.

2.4 ML optimizations: fixing Iron's LayerNorm error (§6, §7.1.4, App. G)

This is the passage most worth recording separately, because it is a textbook case of "algebraically correct but structurally wrong".

What Iron did: LayerNorm is

LayerNorm(X)[i,j] = γ_j·(X[i,j] − μ_i)/σ_i + β_j

To save one matrix multiplication, Iron fused γ_j/σ_i and β_j into the weights of the next linear layer, so that LayerNorm's output simplifies to LayerNorm′(X)[i,j] = X[i,j] − μ_i. Looking at that layer's algebra on its own, the two are entirely equivalent.

What went wrong: Transformers have residual connections — LayerNorm's output is added back to the residual branch, and the residual branch carries a tensor that was not scaled by γ/σ. Once the scaling is folded into the next layer, the values on the residual path are all wrong, the error accumulates layer by layer, and the model performs close to random guessing. The BOLT paper states this explicitly and notes that it was confirmed with the Iron authors (§7.1.4, App. G).

How BOLT fixes it: not by "repairing Iron's fusion" but by removing the optimization outright, keeping the explicit multiplications by γ/β, and then recovering the cost with two engineering measures:

1. move the multiplications by the model weights γ, β into HE (ciphertext-plaintext multiplication, cheap in communication);
2. precompute the MSB of X − μ, saving the communication of the subsequent sign/absolute-value computation.

Effect: LayerNorm's per-layer communication drops from 871.46 MB to 290.55 MB (3.0×, Tab. 3, incl. W.E.), while the round count stays essentially unchanged (218 → 220).

Fine-tuning (§6.2): the fixed-point representation creates a gap between the floating-point model and fixed-point inference, which BOLT closes with quantization-aware fine-tuning:

• symmetric, static quantization; during the forward pass the approximation functions are used directly (GELU/Softmax/Tanh all replaced by the §5 versions) before quantization;
• during backpropagation, "compute the true gradient, then quantize the gradient" (because quantization is non-differentiable);
• word elimination is part of the training forward pass, so that dynamic token dropping is covered by backpropagation;
• no distillation. The paper contrasts with MPCFormer: distillation loses more than 5% on small datasets (such as RTE), whereas BOLT's accuracy drop is about 1%.

Word elimination (§6.1): use Q·Kᵀ ∈ R^{m×m} summed along one axis to obtain a score vector s, find the median with bitonic sort, then use a second round of bitonic sort to move tokens below the median to the back, synchronously swapping the corresponding rows of X and Att — that is, "obliviously drop half the tokens". m goes from 128 to 64; communication for most components is about 2× lower, and Softmax, because its input is m×m, drops to 3.2×.

Accuracy results (Tab. 2, GLUE):

The largest loss appears on STS-B: 89.62 → 88.44, i.e. 1.18 percentage points (the paper calls this a "maximum accuracy loss of 1.3%"). Another anomalous point: SST-2 without W.E. is 1.04% lower than with W.E., which the authors attribute to the approximation in the fixed-point-to-prime-field conversion (§7.3) and say can be fixed by adding "correct truncation", at a performance cost of 3%–7%.

2.5 System implementation and evaluation setup (§7.1–§7.2)

• Libraries: EzPC's SCI (ring secret sharing) + SEAL (BFV).
• Parameters: secret sharing ℓ=37, s=12 (Softmax/LayerNorm); GELU uses ℓ=21, s=11. HE uniformly n=8192; Linear 1 and Softmax×V need a larger noise budget, taking log p ≈ 29 and log q ≈ 218; the remaining linear layers log p ≈ 19, log q ≈ 180; 128-bit security; the server performs noise flooding to guarantee circuit privacy; the implementation uses lazy relinearization and modulus switching to reduce communication.
• Hardware/network: two AWS c6i.16xlarge machines (64 vCPU, 128 GB), 32 threads; Linux tc is used to emulate LAN (3 Gbps, 0.8 ms) and four WAN settings (100/200 Mbps × 40/80 ms).
• Datasets: GLUE's MRPC, RTE, SST-2, STS-B; fine-tuned on the training set and evaluated on the official validation set.
• Iron baseline: implemented by the authors with ℓ=37, s=12, n=8192, log q ≈ 180, log p=37 (a larger p to leave room for noise flooding, since Iron did not do secure-computation-aware fine-tuning).

3. Key Numbers Table

Two observations derived from the table (computed here, not numbers from the paper):

• Nonlinearities are now the overwhelming majority. With W.E., a single layer's communication is about 3.18+2.82+2.26+4.50+6.77+450.74+776.84+290.55+16.64 ≈ 1554 MB, of which Softmax+GELU+LayerNorm+Tanh account for about 1534.77 MB (≈98.7%). Once BOLT squeezes a single layer's linear layers down to a total of about 19.5 MB, the end-to-end bill is almost entirely MPC nonlinearities — which is exactly why THOR/NEXUS had to counterattack from the pure-HE side.
• Rounds drop only 1.25×. At 80 ms RTT, 10901 rounds would be about 872 s if fully serialized, whereas the measured 100 Mbps/80 ms figure is 1744 s — so the round count is at least an important cost term of the same order, and BOLT does not really solve it (its optimization target is bandwidth, not latency).

4. Relation to the Rest of the Series

Relation to the survey (./01-private-transformer-inference-survey.mdx)

The survey classifies private Transformer inference by setup (execution structure) into three categories: full 2PC (Iron and others), 2PC+HE hybrid (BOLT, BumbleBee), and pure HE (NEXUS/THE-X/THOR). BOLT is the anchor of the hybrid route, and its numbers sit right between the two ends:

Iron       280.99 GB / 475 s     ← pure MPC (LAN)
BOLT        25.74 GB / 185 s     ← 2PC + BFV hybrid (LAN)
NEXUS        0.16 GB / 1125 s    ← pure HE (100 Mbps / 80 ms)

When reading the survey, BOLT should be treated as the intermediate state that "moves the cost from one pocket to another": communication is an order of magnitude below pure MPC and computation is below pure HE, but neither end is extreme. It is also the source of two reusable techniques named in the survey: the "LayerNorm simplification trap" and "split into a small interval first, then use low-order approximation".

Relation to THOR (./03-thor-ckks-inference.mdx)

THOR is a pure-HE, non-interactive scheme (the client participates only at the beginning and the end). It uses BOLT as its main baseline and claims PC-MM up to 5.3× faster and CC-MM 9.7×–36× faster on homomorphic matrix multiplication, with BERT-base at 128 tokens running end-to-end in about 10 minutes on a single GPU. But two points must be noted, or the comparison will be misread:

• THOR's "5.3×/36× faster" is an algorithmic-level comparison at the level of key-switching/rotation counts, not an end-to-end wall-clock number including MPC nonlinearities; BOLT's 25.74 GB is the communication of the whole network including nonlinearities.
• THOR itself admits that about 56% of the time within a layer is bootstrapping — precisely the cost that BOLT avoids by doing nonlinearities in MPC and resetting noise in the conversion.

The two are "two sides of the same coin": BOLT keeps nonlinearities in MPC in exchange for low computation, while THOR keeps everything in HE in exchange for zero interaction, paying for it with bootstrapping. The key-switch table in the THOR note (Q/K/V: THOR 192 vs BOLT 297; Q·Kᵀ: 460 vs 24468; αV: 492 vs 21420; output projection: 122 vs 177) shows that BOLT's HE MatMul still pays in rotations/key switches, and that THOR's DiagBlock + BSGS keeps pushing this down further.

Relation to Odin (./04-odin-themis-llama3-fhe.mdx)

Odin points at a different route: FHE LLMs (THEMIS in arXiv 2609.12378, an open-source end-to-end CKKS implementation of Llama-3-8B, GPU-accelerated, protecting only the input and not the weights, with single-party server computation and zero client interaction). Its difference from BOLT is not "faster or slower" but cost structure:

• BOLT's 2PC requires the client to participate online in every layer (otherwise it cannot hold its secret shares), which in long-context, multi-turn LLM settings is a deployment-level obstacle;
• the FHE route drives interaction down to 0 but pushes all cost into homomorphic computation (rotations, bootstrapping, large parameters), and the publicly available end-to-end implementations only reach the 8B scale (THEMIS runs Llama-3-8B); beyond that, both parameters and computation become hard to sustain.

So BOLT's value lies in the regime of "BERT-class encoder + strong privacy + acceptable interaction"; once the target becomes LLM generative inference, its 2PC assumption is itself the bottleneck, not merely its numbers.

5. Limitations and Open Questions

1. The interaction round count is not substantially improved (10901 vs 13663, only 1.25×). Bandwidth drops 10.91×, but the rounds barely move; on high-RTT networks this is a hard floor. Open question: can BOLT's rounds be pipelined? Can the 647 rounds per nonlinear layer be batched?
2. Semi-honest assumption + no formal security proof. The S&P meta-review explicitly lists "no formal security proof, only an argument that the protocol composes secure components" as a noteworthy concern (App. H). Malicious security would require ZK over HE (the MUSE route), and the authors themselves say the cost is high (§9).
3. Encoder only (BERT). The decoder can be adapted directly but word elimination must then be removed (§9); for the effect of word elimination on semantic tasks (especially long sentences and tasks that need all tokens) the paper only reports results on 4 GLUE tasks, which is a rather coarse granularity.
4. The accuracy cost of the nonlinear approximations is masked by the "mean ULP". ULP is a mean error; the worst-case error is not reported; the continuity of GELU around the |x|=2.7 breakpoint and the behaviour of Softmax at the z clip boundary are not analysed separately. Open question: what is the worst-case error bound?
5. The overflow probability of the conversion is only argued to be "negligible", with no bound tied to task accuracy; the authors also admit that the 1.04% SST-2 drop without W.E. is caused by the conversion approximation (§7.3).
6. Evaluation scope: batch=1, 128 tokens, pure CPU, 32 threads; the 4.8–9.5× depends strongly on the network setting and shrinks to 1.5–2.63× at 25 Gbps. The comparison against Iron uses a self-implemented baseline (Iron is not open source); although the authors confirmed it with the Iron authors, reproduction quality remains a link that outsiders cannot independently verify.
7. The "compute-efficient" claim deserves a discount. BOLT reports only runtime and communication, not CPU utilization, energy or peak memory; and HE rotations/NTTs are themselves heavy computation. In §9 the authors also concede that on extremely fast networks one should build a hybrid system that "adaptively selects the linear protocol per network" — which amounts to admitting that the compute side was not truly optimized to the limit.
8. Ciphertext-by-ciphertext depth is still 3 (optimal 2). The 2D rotation is simulated with masks, and mask multiplication brings extra depth and multiplications; this is an inherent constraint of BFV's packing layout, and a point that later work (THOR's DiagBlock) can keep improving.

6. Self-Test Questions

Q1. Why does BOLT put the linear layers in HE and the nonlinear layers in MPC? What is the cost of this division of labor?

A1. HE has low communication cost and high computation cost, which suits MatMul with a large data volume but only additions and multiplications; MPC (secret sharing) is cheap to compute but must communicate on every multiplication, which suits complex nonlinearities. The cost is that one must convert between the two representations (one comparison plus one MUX per round, 2%–9% of end-to-end time), and that only the one-way HE → MPC conversion is performed (the reverse overflow probability is negligible).

Q2. What is the key observation behind compact packing? Why is the output naturally compact?

A2. The observation is that "every column of C is a linear combination of the columns of A, with scalar coefficients taken from B", so packing A by column and replicating each element of B m times is enough to compute the multiply-accumulate of one column with SIMD. Every column of the output C exactly fills the m slots of one ciphertext, so the output is naturally compact by column, with 100% slot utilization.

Q3. Why can't BSGS be copied directly from the matrix-vector version? How many rotations does BOLT save on BERT-base?

A3. Because BOLT packs and rotates at the column level (one ciphertext holds multiple columns), whereas the classic BSGS is element-level; moreover, in the matrix-matrix setting, when the right-hand matrix is tall-and-skinny, additional partial sums can be formed along the row direction — an opportunity that matrix-vector does not have. The gain: 756 → 43 (17.58×) at the single-head dimensions, and 2.33×–9.33× over the full model (Linear 4 saves the most, 3024 → 324).

Q4. Why can't BFV do 2D rotations? How does BOLT get around it, and at what cost?

A4. A BFV rotation is a Galois automorphism in the NTT domain and can only rotate by powers of a root of unity, so it cannot perform a two-dimensional rotation (within rows and across columns) at the same time; for n=8192 it is also unknown whether generators of orders 64/128 that span the whole space exist. BOLT simulates the 2D rotation with "two partial rotations + bit masks + summation", and merges the correction mask with the compact-output mask, bringing the multiplicative depth from 4 down to 3 (the optimum is 2), at the cost of more multiplications/rotations.

Q5. What exactly was wrong with Iron's LayerNorm optimization? How does BOLT correct it?

A5. Iron fuses γ_j/σ_i and β_j into the weights of the next linear layer, so that LayerNorm's output becomes X − μ; this is algebraically correct per layer, but the residual connection requires adding back the unscaled LN output, so the residual branch's values are all wrong, the error accumulates, and the model approaches random guessing. BOLT removes the fusion outright, keeps the explicit multiplications by γ/β, moves the multiplications by the weights into HE and precomputes the MSB of X − μ to recover the cost, and LayerNorm communication still drops 3.0×.

Q6. Can BOLT's 10.91× be compared directly with THOR's claimed 5.3× for PC-MM / 9.7–36× for CC-MM?

A6. No. BOLT's 10.91× is whole-network end-to-end communication (including MPC nonlinearities); THOR's factors are key-switching/rotation counts of homomorphic matrix multiplication (algorithmic level). The two are measured on different bases. To compare, one must align to the same metric (end-to-end communication, end-to-end wall clock, or the same network setting), and one must remember that THOR is zero-interaction pure HE while BOLT is 2PC with interaction in every layer.

7. Locator Index for the Original Paper