Static Bootstrap Placement for Encrypted Language Model Decoding

Static Bootstrap Placement for Encrypted Language Model Decoding Halil İbrahim Kanpak, Didem Unat*† October 6, 2026

arXiv:2610.04912v1 [cs.CR] 4 Oct 2026

Abstract

run whole models [12–14]. The three closest systems, NEXUS, Cerium and Cachemir [15–17], do not feed a selected token back into the encrypted state. Cachemir caches keys and values across decoding steps, but the tokens it decodes are supplied from outside the encrypted computation instead of being selected under encryption. Generating text with these systems requires keeping the client actively in the loop. At every step, the client must decrypt the server’s output logits, select the next token, and re-encrypt it back to the server. In our measurements, this client-assisted approach yields a negligible 2.2% savings in server runtime per token, yet forces the client to stay online for 4.72 hours just to generate 16 tokens of GPT-2 Small. This defeats the primary premise of homomorphic encryption, which is that the client offloads heavy computation to an untrusted server and goes offline. Running the whole generation loop on the server is more than calling the forward pass repeatedly. Three problems arise, and each one comes from the loop. First, the loop body grows. Step n attends over n positions, so each step holds more ciphertexts and needs more bootstraps than the step before it. Because bootstraps dominate the cost of a token, prior work uses a placement tool to decide where a program bootstraps. DaCapo, Orion, ReSBM and Orbit [18–21] search over a program graph whose size is fixed before the search. HALO [22] handles loops, but its body must use the same levels in every iteration. Neither fits a decode loop, whose body grows with every token. Second, the server must select the next token, retrieve its embedding and write it back into the state. Because the server may not learn which token it chose, all three operations run under encryption. Third, the cost of a run is not known before it starts. The usual approach bootstraps a ciphertext when it runs out of levels. The server then learns the level of a ciphertext only when it computes that ciphertext, and it cannot tell in advance which bootstraps a run needs or which of them could run in parallel. We present AR-HE, which runs the whole generation loop on the server. The client sends one encrypted prompt and receives encrypted tokens at the end of the run. AR-HE is a layer between the generation loop and the CKKS GPU library Phantom [12], which performs the ring arithmetic, the key switching and the bootstrapping. At each step, the server selects the next token with CutMax’s comparison-free argmax [23]. The argmax yields an encrypted one-hot vector. The server multiplies this vector by the plaintext embedding table to retrieve the token’s embedding, and writes the embedding into the block of the state reserved for the new token with a masked write. Because each of these operations processes every candidate token, the server

Language models increasingly serve prompts that carry private data, and secure inference under homomorphic encryption lets a client outsource the computation without revealing the prompt. Existing secure inference systems run a forward pass without consuming a token under encryption, and generating text with them requires a client round trip at every generated token. Keeping the loop on the server instead requires selecting and consuming a token under encryption, and placing bootstraps for a loop body that grows with the context. We build AR-HE, which runs the whole loop on the server, selects each token under encryption, retrieves its embedding, and writes it back into the encrypted state. The client sends one prompt and remains offline until the output. One rule places every bootstrap in the run, without search, so the bootstrap cost of a token is a formula in the context length that is known before the run starts. The schedule skips work whose result cannot reach the output, packs bootstraps that share an operand, and keeps the keys and values of past positions in an encrypted cache. With every optimization applied, generating a GPT-2 small token costs 544 seconds on one NVIDIA H100, down from 4715 seconds without optimization. The prompt step before it costs 4630 seconds. The cache alone takes a generated step from 11751 bootstraps to 1072. The formula predicts every step we measured, including steps of a model it was not derived from.

I

Introduction

Serving a language model is autoregressive generation, where each generated token is appended to the context and becomes the input of the next step. Under CKKS homomorphic encryption [1] this loop is expensive. On one NVIDIA H100, a generated token of GPT-2 small costs 4668.5 seconds under encryption without any optimization. A recent tutorial [2] and the authors of Hyperion [3] list encrypted autoregressive generation as an open research problem. Prior work on private transformer inference has focused on the forward pass, which is the body of the generation loop. It provides packing layouts [4–6], matrix multiplication kernels [7–9], polynomial replacements for the nonlinear stages [10, 11], and GPU libraries and systems fast enough to * Halil İbrahim Kanpak is with the Department of Computer Engineering, Koç University, İstanbul, Türkiye (e-mail: hkanpak21@ku.edu.tr). † Didem Unat is with the Department of Computer Engineering, Koç University, İstanbul, Türkiye (e-mail: dunat@ku.edu.tr).

1

completes the step without learning which token it selected. • We evaluate the full system on GPT-2 small and nanoGPT With the client offline, AR-HE computes the bootstrap schedon one NVIDIA H100, and sweep the device axis up to ule before the run starts. We place the bootstraps of the growfour H100s on nanoGPT. We measure the operator costs ing body with one rule and optimize the schedule that results. of Llama-3-8B, and project the cost of larger models such Because nothing is decrypted between steps, the level of every as Llama-3-70B. ciphertext follows from four public values, namely the model Section II states the threat model, introduces generation and architecture, the packing layout, the context length and the step CKKS, and measures the naive implementation of the loop. index. At the entry of each stage of a step, AR-HE bootstraps Section III presents AR-HE: the decode step, the rule that an operand whose level is below the level that stage needs. Evalplaces the bootstraps, the closed form it yields, and the four uating this rule over a step gives its bootstrap count as a closed optimizations. Section IV describes the experimental setup and form in the context length. evaluates the system. Section V discusses related work, and AR-HE rewrites the schedule before the run and applies four Section VI concludes. optimizations. Skipping dead work drops the bootstraps whose results cannot reach the output because the causal mask zeroes them or the context has not reached their state ciphertexts. PackII Background and Motivation ing sends operands with a few distinct values across thousands of slots through one ciphertext, so one bootstrap refreshes sev- In this section we give the threat model, the background on eral operands. The device axis runs independent bootstraps of autoregressive generation and CKKS that the rest of the paper the schedule on separate GPU devices. The cache keeps earlier uses, and the cost of the loop without optimization. keys and values encrypted at the level attention reads, and every cached step we measured reads the cache without bootstrapping it. A generated step then costs a fixed number of bootstraps un- II-A Secure inference and threat model til the context fills a new state ciphertext. We consider a client that outsources language model inference We measure AR-HE on NVIDIA H100 GPUs at 128 bits of to one server. The client holds the secret key. As in prior private classical security. On GPT-2 small with its full vocabulary, the inference frameworks under CKKS [15, 17], the server is semifour optimizations reduce a generated step from 11751 boot- honest and must not learn the prompt or any generated token. straps to 1072, and from 4715 seconds to 544. The prompt The client sends the prompt encrypted under CKKS together step, which the cache does not shorten, costs 4630 seconds. On with the evaluation keys, and it can stay offline until it retrieves nanoGPT, where the same three optimizations take a generated the encrypted output. The server holds the model weights in step to 187 seconds, two and four devices reduce it by a fur- plaintext, and it computes on ciphertexts, evaluation keys and ther 11% to 13%. The formula matches the measured bootstrap public parameters only. We leave timing and memory access count at every one of the 20 steps measured across 10 context side channels out of scope, because the operation sequence and lengths. We derived the formula from the circuit of nanoGPT, the memory addresses depend on public values only. and it also predicts the counts of GPT-2 small. For Llama-3-8B The server sees the public parameters, the evaluation keys, at a context of 32, the formula gives 9.53 hours of bootstrap the encrypted prompt and every intermediate ciphertext of the time for a generated step and 0.44 hours with the cache. run. Under the IND-CPA security of CKKS, this view is comThis paper makes the following contributions. putationally indistinguishable from the same public parameters • We present AR-HE, the first system to run the whole au- and keys together with encryptions of zero. The guarantee astoregressive generation loop under CKKS on a GPU server. sumes circular security, that an encryption of the secret key It selects the token, retrieves its embedding and writes it under itself is safe to publish [24], as every FHE deployment back under encryption, so the client stays offline between that bootstraps does. The model dimensions, the packing, the prompt length and the number of tokens to generate fix the operthe prompt and the output. ation sequence and the level of every ciphertext before the run, • We validate every encrypted decoding step against the so the sequence of operations is independent of the encrypted plaintext model over the generated sequence. We report values. The client decrypts only the final output and returns no the steps at which the polynomial approximations of the decryption result to the server, so the key-recovery attack on nonlinear operators preserve the output token and the steps approximate schemes [25], which needs such results, does not at which the argmax diverges. apply. Appendix B gives the security reduction in full. • We give a bootstrap placement rule for a loop whose body grows, and the closed-form cost model it yields, which predicts the bootstrap count of every step.

II-B

Language models and autoregressive generation

A decoder-only transformer generates text one token at a time. It processes the prompt once. Each later step runs the model over the context, which is the prompt and the tokens generated

• We build and evaluate four optimizations that the fixed schedule makes possible, skipping dead work, packing, an encrypted key and value cache, and running independent bootstraps on multiple GPUs. 2

fixed graph (DaCapo, Orion, ReSBM, Orbit) ↻

↻

↻

↻

↻

↻

↻

back into the encrypted state, and the client therefore stays online for the whole generation. The server runs the model up to the logits and sends them to the client. The client decrypts them, selects the token, encrypts its embedding and returns it, and the server starts the next step. This avoids running the argmax under encryption. Generating 16 tokens on GPT-2 small keeps the client online for hours and saves the server a small share of its runtime. To keep the client offline, the server itself needs to select each token and feed it back for the next generation step. A forward pass reads its input once. Generation feeds each output back as the next input, and under encryption that feedback is a ciphertext. Running this loop entirely under homomorphic encryption raises three problems. The first problem is the growth of a step. Step n attends over all n earlier positions, so each step holds more ciphertexts and needs more bootstraps than the step before it. The second problem is the selection of the next token. Under encryption the server cannot learn which token it selected, so selection, retrieval and write-back each process every vocabulary entry and every state ciphertext. The third problem is the cost of a run. In a naive implementation on one NVIDIA H100 GPU, one generated token takes 1437.3 seconds for nanoGPT and 4715 seconds for GPT-2 small. The bootstraps of a step set that time, since each costs three orders of magnitude more than a multiplication. The placement compilers take a program graph fixed before the search [18–21] or a loop body that consumes the same levels in every iteration [22] (Figure 1). Neither fits a decode loop, whose body grows with every generated token.

↻

repeated body (HALO) i

↻

i+1

↻

↻

↻

i+2

↻

↻

↻

↻

Adaptive body for iterations (ours) n

↻

n+1

↻

↻

n+2

↻

Figure 1: Each tile is a ciphertext and each circled arrow a bootstrap. DaCapo, Orion, ReSBM and Orbit schedule a graph that is fixed before the search, and HALO schedules a body that repeats unchanged. The body of a decode step grows with the context. so far, and turns the final hidden state into logits over the vocabulary. It then selects the token with the largest logit and appends its embedding to the context. Step n attends over all n positions, so its work grows with the context. Plaintext serving systems keep the attention keys and values of past positions in a key and value cache, so each step computes them only for the new position. We call the step that processes the prompt the prompt step and each later step a generated step. Under encryption, the server sees the prompt, the context and every generated token only as ciphertexts.

II-C

CKKS

III

CKKS [1] encrypts a vector of real numbers into one ciphertext over a polynomial ring of degree N , which holds up to N/2 slots that each carry one number. Addition and multiplication act slot by slot, and a rotation moves the slots by a fixed offset using a rotation key. Every multiplication consumes one level of the modulus chain, so a ciphertext at level ℓ supports ℓ more multiplications. The depth of a circuit is the number of levels it consumes. When a ciphertext runs out of levels, a bootstrap raises it to the top of the chain. A bootstrap itself consumes a fixed number of levels, so a parameter set leaves a fixed number of usable levels between bootstraps. A bootstrap also costs far more than any other operation. We use ring degree 216 with 214 slots in use, and a modulus chain that leaves 13 usable levels after a bootstrap, at 128 bits of classical security. One bootstrap costs 368.4 ms on one H100. We build on Phantom [12], a GPU library for CKKS, and use NEXUS’s bootstrap configuration [15] unchanged.

II-D

System Design

AR-HE runs the transformer forward pass inside a decode loop and feeds the selected token back into the encrypted state, and in this section we present its design. Figure 2 shows one decode step, with its five stages above and one expanded layer below, and marks every bootstrap, the packed operands and the skipped dead work. The prompt arrives as a fixed set of ciphertexts that hold the residual stream of its positions, which we call the state, and the server writes each generated token into that set. We first describe the decode step, the work of producing one token, and its state layout, then the placement rule and the count it gives, then the four optimizations the fixed schedule makes possible.

III-A

The decode step

A decode step takes the encrypted state of n positions and produces one token in five stages (Figure 2). The forward pass runs the transformer layers over the state, and the projection turns the final hidden vector into logits. Selection produces an encrypted one-hot vector for the winning token, and retrieval turns it into the token’s embedding. Write-back places the embedding into the state for the next step. The server passes the encrypted onehot vector to retrieval and keeps a copy. The client receives the copies of all steps at the end of the run.

Motivation

To motivate AR-HE, we first look at how a client generates text with the systems that exist today. Prior private transformer frameworks run language model inference one forward pass at a time, and the client takes part between passes. Each pass ends at the client, because these systems cannot feed a selected token 3

server encrypted prompt client

×

state ↻ norm

Q

W

K

W

V

W

KV cache

↻ layer, ×L

encrypted result W ↻

projection

↻

selection logits

↻ scores

×

≡

softmax

↻

M

retrieval

write-back

one-hot

↻ ·V

E

fold

+

norm

W

↻

feed-forward, ×K

+

Figure 2: AR-HE runs one decode step, and the panel below expands one layer. Tags mark what the server reads in plaintext: weights (W), the embedding table (E), the write-back mask (M). The circled arrow marks a bootstrap, the triple bar marks packing, and the cross marks skipped dead work.

dead work, context n reached, ⌈n/b⌉ of C c0 c1 c2 0 1 2 × 3 × n−1 × ×

III-B

reserved c3

offset r

The state layout. The encrypted state of a run is the residual stream of all its positions. A state ciphertext holds b positions of it, one position per block of slots [26], so b is the slot count divided by the width of a block, and the layout fixes the cost of a stage. A trivial layout allocates one state ciphertext per generated token. Each stage loops over the state ciphertexts, so the cost of a step would grow with the number of generated tokens. Instead, a run serving at most nmax positions reserves C = ⌈nmax /b⌉ state ciphertexts before the first step. The reservation stays fixed for the run, so each step writes into a ciphertext that already exists. Once every b generated tokens, write-back starts the next reserved ciphertext, and at the other steps it writes into a ciphertext that already holds a generated token. Retrieval returns the embedding replicated across the blocks of one ciphertext. A plaintext mask keeps the copy in the block of the new position and zeroes the rest. Adding the result to the state ciphertext containing the block writes the token in place, so write-back has constant cost per step. The server selects the token under encryption with CutMax’s comparison-free argmax [23]. Retrieval multiplies the plaintext embedding table by the encrypted one-hot vector, and it processes all logit ciphertexts because the server must not learn which one holds the winner.

live

× dead, skipped

r = b(c+1)

Figure 3: Dead work on the state layout, at b = 2 positions per ciphertext and context n = 5. Attention scores each pair of a past position r and a state ciphertext c, and each pair costs ρatt bootstraps per layer. The reservation stops at the ⌈n/b⌉ state ciphertexts the context has reached, and causality zeroes each pair past r = b(c + 1), so the step skips those pairs.

B(n) = ρatt LCn + (ρlay + ρf f n K)LC − (C − W ) + (τ + S + Vct + w).

The placement rule

(1)

Here L is the layer count, K the number of pieces the feedforward layer is split into, S the number of bootstraps required by selection, and Vct the number of logit ciphertexts. The tail τ is the once-per-step cost outside the layers for the final norm, logit product, selection, and write-back. W is the number of state ciphertexts that already hold a generated token, and w is one when this step writes into such a ciphertext. The coefficients ρatt , ρlay and ρf f n count bootstrap sites in the attention path, in the part of a layer whose cost does not depend on the context, and in one piece of the feed-forward layer. We read each coefficient off the circuit.

We place every bootstrap with one rule. Each stage has a threshold, the depth its operators consume. A site is a point where an operand enters a stage. At each site, the server bootstraps the operand if its level is below the threshold of the stage and passes it unchanged otherwise. The level at which an operand arrives depends only on public values. The whole schedule is therefore known before the run, and the bootstrap count of a step is a formula in the context length.

4

III-C

Dead work

context needs another state ciphertext, and then it rises by the cost of that ciphertext. Operands that share a bootstrap also share the softmax denominator, and the unpacked circuit computes the same denominator, so packing preserves the value. We use the largest mc as the group width.

Equation 1 counts all the bootstraps of a step, including those whose results never reach the output, and we call such work dead (Figure 3). Attention computes a score for each pair of a position offset and a state ciphertext, and each pair has its own bootstraps. Two tests on public values determine whether a pair needs bootstraps. The reservation test stops the loop over the C reserved ciphertexts at the ⌈n/b⌉ the context has reached. The causality test skips pairs whose offsets lie past the last position in their ciphertext because the causal mask zeroes them. The server tests each pair before running its operations, so a dead pair is skipped before any of them run, and it bootstraps only the pairs on which the output depends. The two tests act on different sites, so their savings add when both are enabled. The reservation test saves the bootstraps of one ciphertext until the context first reaches the last reserved ciphertext.

III-E

The optimizations above lower the bootstrap count of a step, and the bootstraps that remain run one after another on one GPU. The third optimization spreads them over several GPUs, which shortens the critical path of a step and leaves its bootstrap count unchanged. The schedule determines which bootstraps are independent, and a barrier is a set of mutually independent bootstraps that the step completes before proceeding. All operands of a pair go through the same operation sequence, so the circuit executes each site for all pairs or omits it for all pairs. A barrier therefore contains one site across all pairs. The width of a barrier is the number of bootstraps in it. The schedule fixes the number of barriers and the width of each before the run, and the widths are set by the number of state ciphertexts C. Several devices can share the bootstraps of one barrier, or the other devices, the workers, can take a fixed set of bootstraps from the device that runs the step, the master. Sharing a barrier of width w across P devices leaves ⌈w/P ⌉ bootstraps on the critical path. Offloading assigns bootstraps whose operands lie in the reserved ciphertexts to worker devices, and the master device continues with the rest. Both placements follow from the schedule. Each barrier ends in a synchronization, after which the step continues on the master device. A wider model holds fewer positions in each ciphertext. The same context then needs more state ciphertexts, and each barrier is wider. The larger models we project later need several devices to hold their state at all, so the value of a second device grows with the model.

The cost of the mask. The mask costs one level on each pair, whether the output depends on it or not, and that level stays below all stage thresholds, so a cheaper mask would leave the bootstrap count unchanged.

III-D

Multiple GPUs

Packing

The second optimization packs the operands of several pairs into one ciphertext before a bootstrap, and one bootstrap then refreshes them all. The score of a pair is a sum over the dimensions of a head, and after that sum all slots of the head hold the same number. A ciphertext of attention weights therefore holds one distinct number per head in each block. A few dozen distinct values therefore occupy thousands of slots. The attentionvalue product requires replication, which we defer until after bootstrapping. We pack G operands in one ciphertext, bootstrap the group once, and unpack after the bootstrap. Within the slots of one head, each operand occupies one slot and the rest hold zero. The packed ciphertext keeps the block layout of the state, so the masks of the unpacked circuit apply to it unchanged. Packing reuses the mask of the sum, and unpacking costs one level. Both come right after a bootstrap the rule has already placed, so the bootstrap count is unchanged. One plaintext holds the causal mask of all operands in a group, so the number of mask multiplications falls as the group grows. The bootstrap count of a step then becomes X l mc m + γ Clive + τ ′ , (2) BG (n) = ρatt L G c

Saturation at three devices. For each barrier width w that occurs in a step of the measured model, ⌈w/3⌉ equals ⌈w/4⌉, so a third device is the last that shortens the critical path. A fourth device can remove only the master device’s share of work. Composition with packing. Packing saves most of the bootstraps that barrier sharing would spread across devices. Offloading takes a fixed set of bootstraps that packing leaves in place. The two gains therefore act on different bootstraps, and the evaluation measures them together.

III-F

where mc is the number of past positions that state ciphertext c attends over and Clive = ⌈n/b⌉ is the number of state ciphertexts the context has reached. Here γ and τ ′ are the perciphertext constant and the once-per-step constant of the formula, and the coefficients are those of Equation 1. Once G reaches the largest mc , each state ciphertext contributes one group and the sum becomes Clive . The packed count therefore stays the same as the context grows until the

Caching keys and values under encryption

The fourth optimization is an encrypted cache of keys and values. Without it, B(n) grows with the context because attention rebuilds the keys and values of all past positions at each step. The keys and values of a position do not change after the step that produces them, so the server keeps them as ciphertexts and later steps read them instead of rebuilding them. 5

the cache, one layer held c0 c1 K

open c2

V

Table 1: The constants of Eqn 1 for the two measured models and the five projected ones, under the CutMax argmax. Each model reads B(n) = sCn + cC + k with s = ρatt L and C = ⌈nmax /b⌉, and k is given for the prompt step and the generated step. The rows below the rule are derived from each model’s circuit.

reserved c3 held at level 6 held at level 4

read by each later step encrypted zeros M zero bootstraps mask to the block, drop to its level, then add fresh k, v, above its level

L, K, Vct

Figure 4: The cache on the state layout, one layer. One key and one value ciphertext for each state ciphertext, held at the levels attention consumes. Later steps read the held entries, and the reserved entry holds encrypted zeros.

b ρatt , ρlay , ρf f n

s

k

nanoGPT GPT-2 small

6, 3, 1 32 12, 4, 4 16

8, 21, 10 8, 21, 10

Llama-3-8B Mistral-7B Qwen3-8B Llama-3-70B Qwen2.5-72B

32, 4, 8 32, 4, 3 36, 3, 10 80, 4, 8 80, 4, 10

8, 19, 10 256 1,887 68, 70 8, 19, 10 256 1,887 43, 45 8, 19, 10 288 1,763 78, 80 8, 19, 10 640 4,719 68, 70 8, 19, 10 640 4,719 78, 80

4 4 4 2 2

48 96

c

305 34, 36 731 52, 54

The cache holds one key ciphertext and one value ciphertext none of them. We will make the code publicly available. for each layer and state ciphertext, laid out like the state with one position per block. Figure 4 shows one layer of it on the state layout. Each step writes one key block and one value IV Evaluation block in each layer, then reads the remaining blocks. To add a position, the server masks the new key or value to the block In this section we compare each step’s bootstrap count with of that position, drops it to the level attention reads, and adds Equation 1, measure the bootstraps and runtime that each opit to that key or value ciphertext, using only evaluation keys timization saves, measure the step on one to four devices, and the run already holds. Each entry starts as an encrypted zero report the agreement of the decoded tokens with the plaintext at that level, so attention reads zeros for a state ciphertext the model. GPT-2 small and nanoGPT run end to end. We esticontext has just reached. The cached score computation repli- mate the cost of Llama-3-8B from measured operator costs and cates the query across blocks through the rotate-and-add that project larger models from the formula. already replicates the new token’s embedding across the blocks, at a cost of one level. IV-A Experimental setup The attention term loses its factor of n, and a generated step All runs we report pass a check that each of their bootstraps has a bootstrap count of Bcached = ρatt LC + constant. We hold keys at level six and values at level four, the levels at returned the number of levels the placement rule assumed. In which the attention path consumes them. The cache also lowers each run the program also evaluates the plaintext model on the the number of ciphertexts held in memory, because the loop same weights in double precision, in the same process, and a without the cache holds a score and a value ciphertext for all second, independently written implementation checks that evalpast positions. The cache produces the same values, because a uation. We run each configuration twice, once without the procached key is the ciphertext the loop would otherwise rebuild. filer and once under it. The profiled run counts the bootstraps All entries stay encrypted, and the cache does not change what independently and its count agrees with the program’s own, and profiling lengthens the runtime by about 1%, and all wall clocks the server learns. we report come from the run without the profiler.

III-G

Implementation

The parameter set. All measurements use the parameter set of Section II. At ring degree 215 the 128-bit security budget leaves the circuit without a usable level after a CKKS bootstrap [27–29]. Splitting the special modulus in two halves the size of each evaluation key and the number of key-switching digits [30], and the whole key set stays resident on one device for the run. The full parameter set is in Appendix A.

We implemented the decode loop and its five stages, the bootstrap schedule, retrieval and write-back, the key and value cache, the optimization configurations and the driver on NEXUS’s released evaluator over Phantom [12, 15]. Phantom allocates device memory, launches the kernels and performs the ring arithmetic, the key switching and the bootstrapping. The placement rule is one call at each site, which compares the operand’s level with the stage threshold and bootstraps below it, and the loop therefore keeps no schedule table. GELU is a Chebyshev polynomial of degree 47, since a power basis of that degree overflows CKKS precision. Stage markers time each stage under the profiler, and the run without the profiler carries

Models, metrics and checks. We report three models. GPT2 small [31] runs the whole loop, Llama-3-8B [32] is derived from operator costs measured on it, and nanoGPT carries the sweep over context lengths, the device measurements and the prompt-length check. nanoGPT is the character-level

6

model of the same architecture [33] with a 65-token vocabulary, and we report its agreement with the plaintext model. We project four more models with Equation 1 at the measured bootstrap cost, Mistral-7B, Qwen3-8B, Llama-3-70B and Qwen2.572B [32, 34–36], dense decoder-only transformers whose layer count, width, feed-forward width, heads and vocabulary we read from their reports. A projected runtime counts only the bootstraps of a step and is a lower bound on it. All measurements in this paper run on one machine with four NVIDIA H100 GPUs of 64 GB each. Unless stated otherwise, we use one device, and each run uses our parameters and random weights for each model’s vocabulary. We count the bootstraps of each step. The plaintext model on the same weights is the reference for correctness. Token agreement is whether the selected token equals the plaintext model’s token at that step, and we report the index of the first step at which they differ. Alignment is the cosine between the decrypted final hidden state and the plaintext model’s on the same token history, and it is 1 at exact agreement. CKKS latency is independent of the weight values because the operations, their order and each operand’s level are fixed before the run. The correctness check is exact at any weights. Alignment does not determine token agreement, since one measured step returned the right token at alignment 0.754 and another returned the wrong token at 0.9997.

Table 2: Bootstraps per step, predicted by Eqn 1 and measured, at a context of 32 for the prompt step and 33 for the generated step. At GPT-2 small the measured count is three bootstraps more than the formula predicts, the bootstraps of the selection stage at its vocabulary. The Llama-3-8B cells marked ‡ are derived, and the number in parentheses is the measured runtime of that step in seconds. Prompt step predicted nanoGPT GPT-2 small Llama-3-8B

Generated step

measured predicted

3716 3716 (1421) 11458 11461 (4622) 90,779 90,779‡

measured

3814 3814 (1456) 11748 11751 (4715) 93,085 93,085‡

Llama-3-8B bootstraps

100k GPT-2 small nanoGPT

10k

1k 16

32 48 context, tokens

measured 64

Determinism. Decoding is greedy, because selection returns the argmax of the logits at each step. One weight file serves all Figure 5: Bootstraps per prompt step against context, on one runs, and its generator reproduces that file byte for byte. We device. Each line is the closed form of one model, and a cross repeated the run at 2 prompt lengths, and each repetition re- inside a ring is a measurement that falls on the prediction. The turned the same tokens as the first run. A disagreement with the Llama-3-8B rings are empty because we did not run a step on plaintext model is therefore the encrypted circuit’s approxima- that model. tion error. We measure each optimization by running the same step with and without it in one process. Two runs of one con- which gives 192 at two ciphertexts and 288 at three. When the figuration return the same counts and tokens and differ only in context reaches a third ciphertext, the slope grows by 96 and the the encryption randomness, so we compare counts first, tokens count grows by the per-ciphertext constant c of Table 1. The second, and decrypted values against that spread. sweep stops at four reserved ciphertexts because five exceed one device’s memory. IV-B The cost of a token For Llama-3-8B, whose step exceeds the memory of one device, the closed form and a level-by-level simulation of the cirWe first compare the bootstrap counts Equation 1 predicts with cuit with our thirteen usable levels return the same counts. Tathe counts we measure on nanoGPT and GPT-2 small and deble 2 lists them beside the two measured models. rive for Llama-3-8B (Table 2, Figure 5), and then convert counts A bootstrap count becomes a wall clock through the duration into runtime with the measured cost of one bootstrap. Equaof one bootstrap, which is 368.4 ms on an idle device with our tion 1 specifies the bootstrap count for a run, and Table 1 gives parameter set and varies by at most 4.2% across different runs. its constants for the two measured models. At C = 2, it predicts 3716 bootstraps for the prompt step of a 32-position nanoGPT context and 3814 for the following generated step. When the IV-C Optimization results write-back of a step is the first write into a reserved state cipher- We measure what each optimization saves on GPT-2 small, over text, the constant of that generated step is one lower. Two gen- a two-step run and at the prompt step (Table 3), for one generated steps at the same n can therefore have different counts. erated step under each configuration on the three models (TaTable 2 reports the prediction and measurement for each model. ble 4), and as runtime against context (Figure 7). Table 3 gives Equation 1 is exact at every step we measured, 20 measure- the fraction of a step’s bootstraps and of its wall clock that each ments at 10 contexts on GPT-2 small (Figure 5) and each step optimization saves, over one prompt step and one generated of nanoGPT’s own sweep. Each added context token costs 96 step together and at the prompt step alone. The two fractions bootstraps for each reserved ciphertext, the slope s of Table 1, 7

Table 3: The share of a step each optimization saves at GPT-2 small. The two-step values come from a run of two steps at the shortest context we ran, one process for each pair, and count the bootstraps and the wall clock of both steps. The prompt step values come from the runs of Figure 7 at two contexts and read the wall clock. The rows are cumulative. The packing row measures packing with dead work skipping applied. Two steps

Table 4: One generated step at a context of 33 on one device. Each configuration adds its optimization to the one before it. The rows above the rule are measured, except the dead-work runtime of nanoGPT, which is that count times the measured bootstrap cost. The rows below the rule are derived: their counts are the closed form and their runtime is the count times the measured bootstrap cost, a lower bound on the step.

Prompt step

bootstraps wall clock context 32 context 48 Dead work + packing

30.4% 81.7%

29.7% 76.1%

bootstraps fraction of unpacked

nanoGPT GPT-2 small Llama-3-8B Mistral-7B

45.8% 80.6%

46.5% 83.9%

Qwen3-8B Llama-3-70B Qwen2.5-72B

1

0.5

0 150

closed form smooth packed form

4 16 packing factor

None

+ dead work

+ packing

+ cache

nanoGPT GPT-2 small

3814 11751

3766 10023

742 2535

436 1072

Llama-3-8B Mistral-7B Qwen3-8B Llama-3-70B Qwen2.5-72B

93,085 93,060 101,483 439,333 439,343

62,365 62,340 66,923 275,493 275,503

19,357 19,332 18,539 91,173 91,183

4,260 4,235 4,434 15,668 15,678

Runtime (s)

None

+ dead work

+ packing

+ cache

nanoGPT GPT-2 small

1456 4715

1387 4059

345 1331

187 544

Llama-3-8B Mistral-7B Qwen3-8B Llama-3-70B Qwen2.5-72B

34,293 34,283 37,386 161,850 161,854

22,975 22,966 24,654 101,492 101,495

7,131 7,122 6,830 33,588 33,592

1,569 1,560 1,634 5,772 5,776

of the bootstraps at all contexts we ran. Table 4 lists one generated step under each configuration for the three models. Of the four optimizations, the cache saves the most bootstraps. The cached form of Equation 1 gives the measured count at every cached step. Across the two cached steps of a run, the cached-step count is constant in context and increases by one ciphertext’s share at the boundary to 1168 bootstraps at four reserved ciphertexts. The prompt step costs 4630 seconds because it carries the whole context without the cache. On one device the first token arrives after 1.29 hours, and the loop then generates 6.6 tokens an hour. We compare the cached loop against the naive implementation in one process with one key set. Tokens are identical at all steps, and both configurations agree with the plaintext model. The two configurations are the None and Cache entries of the GPT-2 small row of Table 4. At both models each cached step reads the cache without bootstrapping it, and each added key or value arrives five levels above the level at which attention reads it. We measure prompt-step cost on the same runs. Figure 7, bottom, plots time to first token, the prompt step’s wall clock, against prompt length at GPT-2 small. The prompt step’s wall clock grows linearly with prompt length at a fixed reserved ciphertext count and jumps at each ciphertext boundary. The count of Equation 1 multiplied by the measured bootstrap cost falls 3.0 to 28.4% below the measured wall clock. The cache leaves the prompt step unchanged, and with and without it in one process the prompt step’s wall clock differs by less than the variation between two runs of one configuration.

0 1

Bootstraps

64

Figure 6: Bootstraps per prompt step at context 48, as a fraction of the count at group width G = 1 (top). The two blue models are measured and the five tan ones come from the closed form. Mistral-7B shares the layer count and positions per ciphertext of Llama-3-8B, and Qwen2.5-72B those of Llama-3-70B, so each pair’s curves coincide and the second of each pair is drawn slightly to the right. The measured count minus the closed form is zero at every width (bottom), and the smooth form without the ceiling falls under the measurement at the two widest. differ because a step spends part of its time outside bootstrapping. At the prompt step the reservation saves more than causality does, and together they save the sum of the two. At the generated step the reservation leaves the count unchanged, because the context has reached its last reserved ciphertext, and causality saves the same amount alone and with the reservation. The packed closed form, Equation 2, reproduces the measured count at each of the ten packed prompt steps across three context lengths and seven group widths (Figure 6). At the generated step, it reproduces five of ten. At group widths of eight or narrower, the form predicts 192 to 2880 bootstraps fewer than we measure. At the widest group, packing saves 85% or more 8

runtime (s)

no optimization dead work skipped packing per generated token

10k

cache formula at the price

Table 5: The device axis on nanoGPT, one generated step at a context of 33 with dead work skipped and packing at the widest group. The critical path is the number of offloaded bootstraps the step waits for. The model adds that path at the measured bootstrap cost to the master device’s 258 seconds. Run 2 repeats run 1 on a clean node, and the speedup is against one device within each run. Critical path Generated step (s) Speedup

3k 1k

runtime (s)

300 per prompt step

10k 3k 1k 300 0

16

32 48 context, tokens

#GPUs

(bootstraps)

model

run1

run2

run1

run2

1 2 3 4

227 114 102 102

342 300 296 296

337 300 300 292

336 295 306 297

1.00 1.12 1.12 1.15

1.00 1.14 1.10 1.13

up to the third device, and a fourth device does not shorten it further. The predicted step time lies within 1.5% of run 1 at each device count and within 3.4% of run 2. Two and four devices cut the generated step by 11 to 13% against one device in both runs. Three devices cut it by 11% in run 1 and 9% in run 2. In each configuration of run 1 the bootstrap count is the same at all device counts. Two terms set the lower bound of the generated step. The master device’s share of a generated step is 258 seconds at each device count, and the offloaded bootstraps take at least one bootstrap per barrier. The generated step therefore cannot fall below about 291 seconds, and one device is at most a factor of 1.16 above that floor. The measured steps at two to four devices stay 0.5 to 5.3% above it. The same runs also show how several devices interact with packing. Worker devices take a fixed set of bootstraps off the master device, and packing does not change that set. Packing shortens the rest of the step, so the offloaded set is a larger share of a packed step than of an unpacked one. At the same device count, a packed step speeds up by a factor of 1.09 and an unpacked step by 1.02. The two optimizations act on different bootstraps.

64

Figure 7: Runtime per generated token (top) and per prompt step (bottom) against context at GPT-2 small, on a logarithmic runtime axis. Points are measured. Each grey line is a configuration’s bootstrap count at the measured cost, and the cached line is the measured step at each reserved ciphertext count. The dotted vertical line marks the fifth reserved ciphertext, beyond which the naive and the cached configurations exceed the memory of one device. GPT-2 small and nanoGPT. Skipping dead work and packing cut a run of two steps on GPT-2 small by a factor of 4.2 in one process with one context and one key set, and the run costs 1086.1 seconds a token within one device’s memory. On nanoGPT the four optimizations together take a generated step from 3814 to 436 bootstraps and from 1456 to 187 seconds (Table 4). The two models differ in width and in vocabulary. Enlarging the vocabulary from 65 tokens to GPT-2’s adds 18 bootstraps to a step, under 0.5% of the step, at both step types and both models, and costs memory for the logit and retrieval ciphertexts.

IV-E

Correctness

We verify correctness against the plaintext model on the same Llama-3-8B. We measured each operator of Llama-3-8B unweights, by token agreement and by the alignment of the deder our parameter set and use the bootstrap cost measured on crypted final hidden state. We then confirm that a step’s cost the same GPU. The counts of Table 2 multiplied by the meadoes not depend on the token it returns, and state the security sured bootstrap cost give the bootstrap time of a step. Table 4 level of the parameter set. Each stage of the loop evaluates gives the four configurations on this model on the same basis. a polynomial approximation of the function it replaces. The encrypted loop follows the plaintext model closely and can difIV-D Multi-device setting fer from it at single tokens. At each prompt length we ran on nanoGPT, the alignment of the decrypted final hidden state with We measure the device axis on nanoGPT, whose generated step the plaintext model’s stays above 0.997. Where the plaintext with dead work skipped and packing at the widest group takes model’s two highest logits are close, encrypted selection can 337 seconds on one device. Table 5 gives, at one to four devices, return the second of them. the number of bootstraps on the critical path, the step time our model predicts from that number, and the measured step time. The number of offloaded bootstraps on the critical path falls

9

Operation GELU LayerNorm Softmax Matrix multiplication/column

Ours

NEXUS

70.35 ms 43.74 ms 20.01 ms 0.2993 s

69 ms 45 ms 20 ms 1.31 s

nanoGPT GPT-2 small Mistral-7B Llama-3-8B

1M seconds a token

Table 6: Four operations of our loop beside NEXUS’s, at NEXUS’s own parameters. For GELU, LayerNorm and softmax we run NEXUS’s released binary and ours on the same device and report medians over 30 calls. For the matrix multiplication we report three repetitions on our H100 next to the runtime NEXUS published for an A100, so the two numbers are not comparable.

100k

Qwen3-8B Llama-3-70B Qwen2.5-72B

10k 1k 100

32

128

context

512

2048

Figure 8: The cached generated step against the context for seven models, the closed form at 368.4 ms a bootstrap. Each curve counts the bootstraps of a step and is a lower bound on the step.

The context boundary. We ran one prompt of each length from 40 to 52 tokens on nanoGPT, generated two tokens from each and compared every token with the plaintext model’s. The loop returns the plaintext model’s tokens at every length except IV-F Comparison 48, where its first token differs, and it is exact again at the longer prompts. Exactness therefore does not degrade with the context Our end-to-end baseline is the naive implementation of the loop, inside this range. At the diverging step the selection stage is less the first row of Table 4. Table 6 compares our loop’s operators certain of its winner than at the exact lengths, while the hidden with NEXUS’s readings of the same operators at NEXUS’s pastate stays aligned with the plaintext model’s. Appendix F local- rameters, which differ from ours. Our GELU runs 2% slower izes the failure to one operation, the first inverse of the attention and our LayerNorm 3% faster than NEXUS’s on the same desoftmax, where the additive error of one bootstrap consumes an vice, and both differences lie within the variation between two operand that shrinks with the context, so the boundary sits at runs of one configuration. NEXUS measured its matrix multiplication on an A100, so the table lists the two numbers side by one site of the circuit. side and we do not compare them. The decoded output of each Cost against the token returned. A step costs the same what- operator passes its check against the reference computation. We also derive the cost of the interactive loop of Section II-D. ever token it returns. We ran three prompts under the same conEach assumption in that derivation favours the interactive loop. figuration, and their bootstrap counts were identical at all eight It saves 2.2% of server time per token, and the client must stay steps, from 3716 to 4390. Their wall clocks differed by at most online for 4.72 hours to receive sixteen tokens. At Llama-31.827% within the 2.32% spread between repeated runs. The 8B, the same derivation saves 64 bootstraps from the cached prompt whose selected token differs from the plaintext model’s generated step of 4,260, a saving of 1.5%, for 6.9 hours of client has the counts the formula predicts. The same holds inside one presence at sixteen tokens. operator, since the softmax microbenchmark’s time changed by 0.1% when its input changed. We repeat the check on GPT-2 small with its full vocabulary, IV-G Scaling in model and context size and the encrypted circuit returns the plaintext model’s token at the first step, as it does on nanoGPT. The disagreement rate The rows below the rule of Table 4 give the four configurations for the four projected models at a context of 33, and this subsecdoes not grow with the context. The parameter set of each run also fixes the security level. tion extends the projection to longer contexts, larger models and The lattice estimator [37] certifies our parameters at not less more devices. We estimate the cached generated step of seven than 128 bits of classical security. The cheapest attack the es- dense models from a context of 32 to 2048 with Equation 1 timator finds is a hybrid attack on bounded distance decoding and the measured bootstrap cost (Figure 8). Over that range the with a meet-in-the-middle step, and it costs 2140.8 operations cached token cost grows by a factor of 42 at Llama-3-70B and under the estimator’s default reduction cost model. We claim 31 at Mistral-7B. Figure 9 gives the memory one device needs against the conclassical security only. Appendix B proves the statement of text for the seven models. The evaluation keys take the largest Section II-A. A simulator that receives only the public descripshare, 49.63 GiB, and the rest is the state, the working set of tion of the request, the model, the packing, the prompt length a step and the cache. One device holds nanoGPT to a context and the token count, encrypts zeros in place of the prompt’s ciof 1024, GPT-2 small to 512 and the 8B models to 64, and the phertexts, and a hybrid argument over those ciphertexts reduces 70B models need more than one device at every context. On the any distinguisher of the two views to the IND-CPA security of two models we measure, the estimate is within five per cent of CKKS with the evaluation keys published, with a loss linear in the footprint. A projected model may need several devices to the number of prompt ciphertexts.

10

nanoGPT GPT-2 small Mistral-7B Llama-3-8B

GiB a device

10k

Qwen3-8B Llama-3-70B Qwen2.5-72B device memory

duces at every step. Because no published system selects a token under encryption and feeds it back into the encrypted state, we derive the nearest alternative, an interactive loop, and compare against it in the evaluation. A per-token ratio against a forward-pass system would credit our loop for the forward pass, which is their work.

1k

100 32

128

context

512

2048

Figure 9: Memory footprint of a run on one device against the context for seven models, with the cache, from unit prices measured on this parameter set. The dashed line is the memory of one device.

Scale-out inference and encrypted caches. Cerium is a scale-out CKKS framework for large models across GPUs, and its reported task covers only the first token [16]. Cerium reports its bootstrap time from a standalone benchmark, so it cannot be set beside ours, which we time inside the decode loop. Cachemir is the closest work to our cache, because it packs an encrypted key and value cache for CKKS transformer inference and reports end-to-end latency at fixed sequence lengths [17]. Cachemir reaches 128 bits of security with a sparse secret through sparse-secret encapsulation. Cachemir’s decoding step takes the most recent token as input and appends its key vector to the cache. Cachemir reports MRPC accuracy and F1 and Wikitext-2 perplexity for that pipeline. These metrics therefore measure a cache that a supplied token sequence fills.

hold its state, and we split its layers across devices in a pipeline, as plaintext serving does for a model larger than one device. The split divides the cache among the devices, leaves the bootstraps and the critical path unchanged, adds one state transfer at each layer boundary, and raises throughput by the device count over independent requests. Within one device’s share, a wider Forward-pass building blocks. Matrix multiplication kermodel holds fewer positions in each ciphertext, so its barriers nels [7–9] and packing layouts [4–6] cover the linear are wider and offloading removes a larger share of the step than stages. Polynomial approximations [10, 11, 38] and on nanoGPT. Models in use today add modules and methods be- encryption-friendly architectures [39] cover the nonlinear yond the dense transformer, such as mixtures of experts, linear stages. ROSETTA extends Cachemir with TFHE lookup taattention and sparse attention, which bring new nonlinear oper- bles for the nonlinear operators of a decode step, and a cost ators and change the terms of the formula. The methodology model assigns each operator to TFHE or to CKKS [40]. Listays as it is, since the placement rule fixes the bootstraps of the braries [12, 41–43], GPU kernels [44], and GPU systems for new operators before the run, and the count of a step follows whole models [13, 14] execute these stages, and hardware acfrom the same ledger of sites. celerators, real or simulated, scale the same stages out [45–47]. Faster operators from this work would also shorten our step, Scope. By design the framework does not depend on pretrain- because we use these operators and change the computation ing. Each run uses random weights, since the schedule and around them. Encrypted inference for other model families uses the bootstrap count depend on the architecture and not on the the packing and bootstrap machinery and stops at the forward weight values, and we make no claim about language quality. pass [48]. Surveys [49–51] and a tutorial [2] map the area. The The number of tokens to generate is fixed before the run, be- tutorial states that “fully end-to-end private text generation uncause the server cannot see whether the model has produced an der HE remains an open challenge” [2]. Hyperion’s authors end-of-sequence token. We measure two models and derive the write that they “plan to integrate this into a larger private LLM rest from two untested assumptions. Where we have both a pro- system and enable full private LLM token generation under hojection and a measurement, the projection is 3.5 to 27.4% below momorphic encryption” [3]. the measurement, and the gap is widest at the cached step. We use one device for the operator comparison. Hybrid protocols. A separate body of work reaches trans-

V

Related work

Non-interactive inference. Prior systems optimize private transformer forward passes under CKKS, and NEXUS made this setting non-interactive [15]. Its client sends one encrypted input and receives one encrypted output, and the server computes everything between them, the final selection vector included, under encryption. NEXUS’s final output is an encrypted one-hot vector, the same object our selection stage pro-

11

former inference [52–54] and generative models [55, 56] by combining homomorphic encryption with multi-party computation, or by secret sharing alone [57]. The client stays online for every nonlinearity in these protocols, so their threat model differs from ours. Bootstrap placement. The systems above run a forward pass, and another body of work places program bootstraps. DaCapo [18], Orion [19], ReSBM [20], Orbit [21], and HEIR [58] search for a bootstrap schedule over the graph of a program,

and HALO [22] extends that search to a loop with one repeated body. These systems find a cheaper placement inside a fixed graph. Our rule fixes the bootstrap count of a growing body before the run, so the two act on different terms of one step. When a step is spread across several devices, the schedule must also decide which device runs each bootstrap. Concurrent work on multi-GPU CKKS transformer inference reports that distributing a key switch across devices at the granularity of its digits is bound by communication [59]. We distribute whole bootstraps instead, in the groups the schedule fixes before the run, and the evaluation gives the device count at which the gain stops. Encrypted control also runs a feedback loop over encrypted state, with a controller in place of a language model [60–62]. Selection under encryption. Prior work studies token selection under encryption, and we build on it. We use CutMax’s comparison-free argmax, which converts an encrypted logit vector into a one-hot vector by repeated sharpening [23]. We add the stage that consumes that one-hot vector inside the decode loop. Three other constructions provide the same primitive, an encrypted argmax that returns a one-hot vector at small class counts [63], probabilistic selection over encrypted logits [64], and inverse-transform sampling at full vocabulary [3]. We decode greedily, which makes the plaintext model an exact comparator, and the loop is independent of the sampling policy. One paper studies how tokens are ordered when the feedback is encrypted, and it does so in plaintext simulation [65]. Our correctness results measure that failure class on the encrypted circuit itself.

VI

Conclusion

We presented AR-HE, the first system to run autoregressive generation under CKKS with the client offline between the prompt and the output. One placement rule fixes the bootstraps of a step before the run and gives their count as a formula in the context length, which held at every step we measured. Skipping dead work, packing and an encrypted key and value cache reduce a GPT-2 small generated step from 11751 bootstraps to 1072, and a second device cuts the wall clock of a nanoGPT step by a further 11%. Each operator inside the loop is a published one and the loop is where the cost now lies.

Acknowledgments Authors from Koç University have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 949587). We acknowledge the EuroHPC Joint Undertaking for awarding access to the MareNostrum5 supercomputer in Spain, where the experiments reported in this paper were partially performed.

12

References [1] J. H. Cheon, A. Kim, M. Kim, and Y. Song, “Homomorphic encryption for arithmetic of approximate numbers,” in ASIACRYPT, 2017. [2] L. Lim, D. Agrawal, and A. El Abbadi, “Private LLM inference with homomorphic encryption (tutorial),” in EDBT, 2026. [3] L. Lim, J. Liu, V. Kalagi, D. Agrawal, and A. El Abbadi, “Hyperion: Private token sampling with homomorphic encryption,” in ACL, 2026. [4] L. Zhang, X. Wang, J. J. Sim, Z. Huang, J. Zhong, H. Wang, P. Duan, and K.-Y. Lam, “MOAI: Moduleoptimizing architecture for non-interactive secure transformer inference,” Cryptology ePrint Archive, Paper 2025/991, 2025. [5] Z. Wang, R. Chen, X. Gao, Y. Wang, L. Liu, Z. Lan, Z. Wang, S. Fu, Q. Wang, and X. Huang, “STIP: Efficient and secure non-interactive transformer inference via compact packing,” Cryptology ePrint Archive, Paper 2026/174, 2026. [6] S. N. Guzelhan, L. Daksha, C. Agulló Domingo, G. Jonatan, J. Kim, J. L. Abellan, D. Kaeli, and A. Joshi, “ELLMo: Packing- and depth-aware encrypted transformer inference,” Cryptology ePrint Archive, Paper 2026/198, 2026. [7] X. Jiang, M. Kim, K. Lauter, and Y. Song, “Secure outsourced matrix computation and application to neural networks,” in ACM CCS, 2018. [8] J. Moon, D. Yoo, X. Jiang, and M. Kim, “THOR: Secure transformer inference with homomorphic encryption,” in ACM CCS, 2025. [9] L. Lim, V. Kalagi, J. Novick, J. Liu, D. Agrawal, and A. El Abbadi, “Tricycle: Private transformer inference with tricyclic encodings,” Cryptology ePrint Archive, Paper 2025/1200, 2025. [10] D. Park, E. Lee, and J.-W. Lee, “Powerformer: Efficient and high-accuracy privacy-preserving language model with homomorphic encryption,” in ACL, 2025. [11] L. Zhang, X. Wang, X. Lu, H. Wang, and K.-Y. Lam, “LEAF: A low-latency evaluation architecture for feedforward block in privacy-preserving transformer inference,” Cryptology ePrint Archive, Paper 2025/956, 2025. [12] H. Yang, S. Shen, W. Dai, L. Zhou, Z. Liu, and Y. Zhao, “Phantom: A CUDA-accelerated word-wise homomorphic encryption library,” IEEE Transactions on Dependable and Secure Computing, vol. 21, no. 5, pp. 4895–4906, 2024.

[13] L. de Castro, D. Escudero, A. Agrawal, A. Polychroniadou, and M. Veloso, “EncryptedLLM: Privacypreserving large language model inference via GPUaccelerated fully homomorphic encryption,” in ICML, 2025. [14] J. Park, S. Park, J. H. Park, J. H. Ahn, J. H. Cheon, G. Hanrot, J. W. Kim, M. Park, and D. Stehlé, “Scaling up FHEbased privacy-preserving ML: Higher throughput, longer inputs for LLama-3-8B,” arXiv:2601.18511, 2026. [15] J. Zhang, X. Yang, L. He, K. Chen, W.-j. Lu, Y. Wang, X. Hou, J. Liu, K. Ren, and X. Yang, “Secure transformer inference made non-interactive,” in Network and Distributed System Security Symposium (NDSS), 2025. [16] S. Jayashankar, J. Kim, M. B. Sullivan, W. Zheng, and D. Skarlatos, “A scalable multi-GPU framework for encrypted large-model inference,” arXiv:2512.11269, 2025. [17] Y. Yu, Y. Zhou, Y. Chen, P. Soto, W. Xiong, and M. Li, “Cachemir: Fully homomorphic encrypted inference of generative large language model with KV cache,” arXiv:2602.11470, 2026.

[26] S. Halevi and V. Shoup, “Algorithms in HElib,” in CRYPTO, 2014. [27] M. Albrecht, M. Chase, H. Chen, J. Ding, S. Goldwasser, S. Gorbunov, S. Halevi, J. Hoffstein, K. Laine, K. Lauter, S. Lokam, D. Micciancio, D. Moody, T. Morrison, A. Sahai, and V. Vaikuntanathan, “Homomorphic encryption standard,” HomomorphicEncryption.org standard, Cryptology ePrint Archive, Paper 2019/939, 2018. [28] B. R. Curtis and R. Player, “On the feasibility and impact of standardising sparse-secret LWE parameter sets for homomorphic encryption,” in WAHC, 2019. [29] J. H. Cheon, K. Han, A. Kim, M. Kim, and Y. Song, “Bootstrapping for approximate homomorphic encryption,” in EUROCRYPT, 2018. [30] K. Han and D. Ki, “Better bootstrapping for approximate homomorphic encryption,” in CT-RSA, 2020. [31] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever, “Language models are unsupervised multitask learners,” OpenAI technical report, 2019.

[18] S. Cheon, Y. Lee, D. Kim, J. M. Lee, S. Jung, T. Kim, D. Lee, and H. Kim, “DaCapo: Automatic bootstrapping management for efficient fully homomorphic encryption,” in USENIX Security, 2024.

[32] A. Grattafiori et al., “The Llama 3 herd of models,” arXiv:2407.21783, 2024.

[19] A. Ebel, K. Garimella, and B. Reagen, “Orion: A fully homomorphic encryption framework for deep learning,” in ASPLOS, 2025.

[34] A. Q. Jiang et al., “Mistral 7B,” arXiv:2310.06825, with the configuration of the v0.3 model card, 2023.

[20] Y. Liu, J. Lai, L. Li, T. Sui, L. Xiao, P. Yuan, X. Zhang, Q. Zhu, W. Chen, and J. Xue, “ReSBM: Region-based scale and minimal-level bootstrapping management for FHE via min-cut,” in ASPLOS, 2025.

[33] A. Karpathy, “nanoGPT,” Open-source repository karpathy/nanoGPT, 2022.

[35] Qwen Team, “Qwen3-8B,” Model card and configuration, Hugging Face, accessed 5 September 2026, 2025. [36] ——, “Qwen2.5 technical report,” arXiv:2412.15115, 2024. [37] M. R. Albrecht, R. Player, and S. Scott, “On the concrete hardness of learning with errors,” Journal of Mathematical Cryptology, vol. 9, no. 3, pp. 169–203, 2015.

[21] Z. Zhou, W. Seo, E. Chen, A. Ozdemir, F. Brown, and W. Zheng, “Orbit: Optimizing rescale and bootstrap placement with integer linear programming techniques for secure inference,” Cryptology ePrint Archive, Paper 2026/213, 2026. [22] S. Cheon, Y. Lee, H. Youm, D. Kim, S. Yun, K. Jeong, D. Lee, and H. Kim, “HALO: Loop-aware bootstrapping management for fully homomorphic encryption,” in ASPLOS, 2025. [23] M. Avitan, M. Baruch, N. Drucker, I. Zimerman, and Y. Goldberg, “Efficient decoding methods for language models on encrypted data,” in Findings of IJCNLP-AACL, 2025. [24] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in STOC, 2009. [25] B. Li and D. Micciancio, “On the security of homomorphic encryption on approximate numbers,” in EUROCRYPT, 2021. 13

[38] O. Chakraborty and M. Zuber, “Efficient and accurate homomorphic comparisons,” Cryptology ePrint Archive, Paper 2022/622, 2022. [39] D. Rho, T. Kim, M. Park, J. W. Kim, H. Chae, E. K. Ryu, and J. H. Cheon, “Encryption-friendly LLM architecture,” arXiv:2410.02486, 2024. [40] J. Yu, B. Zhang, L. Kong, L. Ding, Y. Chen, Y. Yu, M. Zhang, and M. Li, “ROSETTA: Efficient and accurate privacy-preserving LLM decoding via hybrid CKKS/TFHE evaluation,” arXiv:2609.16915, 2026, to appear in ACM CCS 2026. [41] A. Al Badawi, J. Bates, F. Bergamaschi, D. B. Cousins, S. Erabelli, N. Genise, S. Halevi, H. Hunt, A. Kim, Y. Lee et al., “OpenFHE: Open-source fully homomorphic encryption library,” in WAHC, 2022.

[42] C. Agulló-Domingo, Ó. Vera-López, S. Guzelhan, L. Daksha, A. El Jerari, K. Shivdikar, R. Agrawal, D. Kaeli, A. Joshi, and J. L. Abellán, “FIDESlib: A fully-fledged open-source FHE library for efficient CKKS on GPUs,” in IEEE ISPASS, 2025. [43] W. Choi, J. Kim, and J. H. Ahn, “Cheddar: A swift fully homomorphic encryption library designed for GPU architectures,” arXiv preprint, accepted at ASPLOS 2026, 2024. [44] S. Seo and C. Min, “Zephyr: GPU-efficient homomorphic encryption for privacy-preserving transformer inference,” Cryptology ePrint Archive, Paper 2026/932, 2026. [45] S. Jayashankar, E. Chen, T. Tang, W. Zheng, and D. Skarlatos, “Cinnamon: A framework for scale-out encrypted AI,” in ASPLOS, 2025. [46] N. Samardzic, A. Feldmann, A. Krastev, N. Manohar, N. Genise, S. Devadas, K. Eldefrawy, C. Peikert, and D. Sanchez, “CraterLake: A hardware accelerator for efficient unbounded computation on encrypted data,” in ISCA, 2022. [47] J. Kim, G. Lee, S. Kim, G. Sohn, M. Rhu, J. Kim, and J. H. Ahn, “ARK: Fully homomorphic encryption accelerator with runtime data generation and inter-operation key reuse,” in MICRO, 2022. [48] K. Garimella, A. Ebel, G. De Micheli, and B. Reagen, “HE-LRM: Encrypted deep learning recommendation models using fully homomorphic encryption,” arXiv:2506.18150, 2025. [49] A. Al Badawi, A. Alexandru, Y. Polyakov, and V. Vaikuntanathan, “SoK: Private LLM inference using approximate homomorphic encryption,” Cryptology ePrint Archive, Paper 2026/935, 2026. [50] Z. Pindado, T. Spendlhofer, M. Allam, P. Mehta, L. Martens, and A. J. Peña, “SoK of private deep neural network inference with approximate fully homomorphic encryption,” Cryptology ePrint Archive, Paper 2026/047, 2026.

[54] W.-j. Lu et al., “Bumblebee: Secure two-party inference framework for large transformers,” in Network and Distributed System Security Symposium (NDSS), 2025. [55] X. Hou et al., “CipherGPT: Secure two-party GPT inference,” Cryptology ePrint Archive, 2023. [56] Z. Li, Y. Guan, K. Yang, Y. Feng, N. Liu, Y. Yu, J. Leng, and M. Guo, “An efficient private GPT never autoregressively decodes,” in ICML, 2025. [57] Y. Dong et al., “PUMA: Secure inference of LLaMA-7B in five minutes,” arXiv preprint, 2023. [58] A. Ali, J. Choi, B. Gipson, S. Gorantala, J. Kun, W. Legiest, L. Lim, A. Viand, M. Z. Demissie, and H. Zheng, “HEIR: A universal compiler for homomorphic encryption,” arXiv:2508.11095, 2025. [59] Z. Gong, R. Ran, F. Yao, and W. Wen, “AEGIS: Scaling long-sequence homomorphic encrypted transformer inference via hybrid parallelism on multi-GPU systems,” arXiv:2604.03425, 2026. [60] K. Kogiso and T. Fujita, “Cyber-security enhancement of networked control systems using homomorphic encryption,” in IEEE CDC, 2015, pp. 6836–6843. [61] F. Farokhi, I. Shames, and N. Batterham, “Secure and private control using semi-homomorphic encryption,” Control Engineering Practice, vol. 67, pp. 13–20, 2017. [62] M. Schulze Darup, A. B. Alexandru, D. E. Quevedo, and G. J. Pappas, “Encrypted control for networked systems: An illustrative introduction and current challenges,” IEEE Control Systems Magazine, vol. 41, no. 3, pp. 58–78, 2021. [63] N. Jovanovic, M. Fischer, S. Steffen, and M. T. Vechev, “Private and reliable neural network inference,” in ACM CCS, 2022. [64] L. Folkerts and N. G. Tsoutsos, “Tyche: Probabilistic selection over encrypted data for generative language models,” ACM Transactions on Internet Technology, vol. 26, no. 2, pp. 18:1–18:28, 2026.

[51] D. Andreoletti, A. Rudi, E. Carpanzano, F. Lelli, and T. Leidi, “Privacy-preserving LLM inference in practice: A comparative survey of techniques, trade-offs, and deployability,” Cryptology ePrint Archive, Paper 2026/105, 2026.

[65] D. Rho, S. Seo, H. Sung, C. Min, and E. K. Ryu, “Traveling salesman-based token ordering improves stability in homomorphically encrypted language models,” arXiv:2510.12343, 2025.

[52] M. Hao, H. Li, H. Chen, P. Xing, G. Xu, and T. Zhang, “Iron: Private inference on transformers,” in Advances in Neural Information Processing Systems (NeurIPS), 2022.

[66] B. Li, D. Micciancio, M. Schultz-Wu, and J. Sorrell, “Securing approximate homomorphic encryption using differential privacy,” in CRYPTO, ser. LNCS, vol. 13507, 2022, pp. 560–589.

[53] Q. Pang et al., “BOLT: Privacy-preserving, accurate and efficient inference for transformers,” in IEEE S&P, 2024.

14

A

The parameter set

Table 7 lists the parameter set of every measurement in the paper. The lattice estimator [37] certifies it at not less than 128 bits of classical security. The evaluation names the cheapest attack the estimator finds and its cost under the estimator’s default reduction cost model. We claim classical security only. Table 7: The parameter set of every measurement in the paper.

B

quantity

value

ring degree slots used secret ciphertext primes special primes positions per ciphertext, b usable levels bootstrap depth scale bootstrap primes modulus, log QP evaluation keys

216 214 sparse ternary, h = 192 51 + 13 × 46 bits 2 × 51 bits 32 13 14 246 14 × 51 bits 1465 bits 19.7 GiB

The leakage. The leakage L(g) is g together with every object the run derives from g by a public function. These objects are the parameter set, the number c(g) of prompt ciphertexts, the sequence of homomorphic operations with the level of every operand, the position and the count of every bootstrap, and the rotation set Kg of the run, which includes the conjugation. These are functions of g alone for two reasons. A level is metadata that only the operation sequence changes. The placement rule places a bootstrap when an operand’s level is below the threshold of the stage it enters, and it depends on nothing else. The dead-work tests depend on the context length and the reservation, both of which are in g. The prompt occupies c(g) = ⌈nmax /b⌉ state ciphertexts, and every position at or past n0 encodes zero. Because n0 is in g, the padding reveals nothing beyond g. Through L(g) the server learns n0 , T and the schedule they fix. The keys and the assumption. The client is honest. It runs the key generation of CKKS and obtains a sparse ternary secret key s and a public key pk. It also generates the evaluation keys evkg , the relinearization key and one rotation key for every element of Kg . Bootstrapping uses keys of this family and no other [29], and the key set of the run contains no second secret. Each of these keys is a key-switching key. It consists of one or more RLWE encryptions under s of a public integer multiple of f (s) for one function f in the class

The security reduction

The threat model of the paper states that the server’s view is simulatable from public values. This appendix defines the view, the leakage and the assumption, states the theorem and proves it.

Kg = { s 7→ s2 } ∪ { s 7→ σk (s) | k ∈ Kg },

where σk is the automorphism that the rotation by k applies. is the IND-CPA game of CKKS with The game CPAevk g one change, in which the challenger hands the adversary pk and evkg together. The adversary submits two plaintext vecThe request and the functionality. We write g for the public tors of one state ciphertext and receives the encryption of one description of a request, the model architecture, the packing, of them under pk at the level and scale of a prompt ciphertext. the prompt length n0 and the number of tokens requested T . It outputs a bit, and its advantage is the absolute difference beThe packing consists of the reservation nmax , the number of tween the probabilities that it outputs one on the two challenges. positions the run reserves, the positions per ciphertext b and Advevk g (t) is the largest advantage of an adversary that runs in the group width G. The parameter set is fixed and public. We time t. We assume that Advevk (t) is negligible at every g the g write W for the server’s input, the weights and the embedding paper runs. This is a key-dependent-message assumption on table in plaintext, and x for the client’s input, a prompt of n0 RLWE for the class K under a sparse secret, the circular seg tokens. The ideal functionality Fg takes x from the client and curity that every CKKS deployment that multiplies or rotates W from the server and runs greedy decoding of the plaintext makes. No reduction from decisional RLWE to it is known. model with weights W from x for T steps. It returns the T The lattice estimator certifies the RLWE instance without the tokens to the client and the leakage L(g), defined below, to the key-switching keys, and the assumption includes that publishserver. The end-of-sequence token is an ordinary token, the ing them does not lower that level. run does not stop at it, and the client truncates after decryption, because a stop test would need a decryption. A sampling policy The view and the two experiments. The server is honest but is a different functionality, and the theorem does not cover it. curious, and its view consists of its input W , its random tape The protocol computes an approximation of Fg . Its client r and the messages it receives. The tape supplies the coins of output is T encrypted one-hot vectors, whose tokens agree with the encryptions of zero under pk with which the server initialFg on the runs the evaluation reports as exact and differ on the izes the cache entries, and no other operation of the server uses run it reports as divergent. We prove no bound on that error. coins. The messages are pk, evkg and the prompt ciphertexts The theorem compares the server’s view with a simulation of it. ct1 , . . . , ctc(g) , each the encryption under pk of one state ciIt says nothing about the joint distribution of the view and the phertext’s share of the encoded prompt, so client’s output, since that would need a correctness bound. view = (W, r, pk, evkg , ct1 , . . . , ctc(g) ). 15

The program Pg that maps the view to the run is public and the server holds no value in the clear. Every branch, ciphertext and bootstrap of the run is therefore a function of the view and of L(g). The measurement program holds the secret key in the same process and decrypts probes for validation. Pg is that program with every probe removed, since no probe adds a homomorphic operation or affects a ciphertext, a branch of Pg or the step count. The real experiment Real(g, x, W ) runs the client’s key generation, encrypts the state ciphertexts of x under pk, samples r and outputs the view. The ideal experiment Ideal(g, x, W ) runs Fg , which hands the server L(g), and outputs S(L(g), W ). The simulator S receives the server’s input and the leakage and never receives x. The theorem quantifies over every g, x and W , so an adversary who chooses the prompt gains nothing by the choice. Theorem. Let tenc be the time of one public-key encryption of one state ciphertext. There is a simulator S that runs in the time of one key generation plus c(g) tenc . For every g, every prompt x of length n0 , every W and every distinguisher D running in time t, Pr[D(Real(g, x, W )) = 1] − Pr[D(Ideal(g, x, W )) = 1]
≤ c(g) · Advevk t + c(g) tenc . g

What the theorem does not cover. The view contains no decryption, so IND-CPA in the presence of the keys is the notion the theorem needs, and the decryption-aware notion for approximate schemes [25] does not enter. The theorem covers one run. It extends to several runs under one key set when every continuation is a function of the client’s own inputs. The same hybrid then runs over all prompt ciphertexts with the keys of the union of the rotation sets. The bound sums the c(gj ) times the advantage of that larger instance of the assumption. A continuation, a retry or a published token that depends on a decrypted value is a function of the decryption error. The reduction cannot compute that error, so the theorem does not cover such a use. Rounding to a token gives no protection, because the encrypted argmax can differ from the plaintext argmax at near ties. Noise flooding at the output is the known repair [66]. It needs a certified bound on the noise of the output ciphertext under our parameters, which we do not measure. The threat model therefore assumes that the client acts on no decrypted value where the server observes it, retries included. The wall clock of a run is not in the view, and a public schedule fixes the count of every operation and not the time each one takes. The theorem therefore covers neither timing nor memory access, both of which the threat model places out of scope. It does not cover integrity, since a server that deviates from Pg may return arbitrary ciphertexts that the client cannot detect. It also does not cover model confidentiality against a client with query access, availability, or session metadata such as when a request arrives.

Proof. The simulator S(L(g), W ) runs the client’s key generation and obtains a fresh pair (pk′ , evk′g ), with Kg read from L(g). It encrypts the zero vector c(g) times under pk′ , samples C The sites behind the cost law r, and outputs (W, r, pk′ , evk′g , ct′1 , . . . , ct′c(g) ). It uses W only The coefficients of the cost law count the bootstrap sites of the as a component of the tuple. For 0 ≤ i ≤ c(g) let Hi be the distribution of the real decode step, where a site is a point at which an operand enters a view with ct1 , . . . , cti replaced by encryptions of the zero vec- stage. This appendix lists the sites behind each coefficient and tor under the real pk. Then H0 is Real(g, x, W ), and Hc(g) and states the three rules the implementation follows at the input of Ideal(g, x, W ) are identically distributed. Key generation is in- every homomorphic inverse. It then gives the two implementadependent of x, so the real key pair and the fresh one have the tion checks that the experimental setup mentions. same distribution. Both tuples are the same function of a key pair, c(g) encryptions of zero and r. C.1 The site ledger For a fixed i with 1 ≤ i ≤ c(g) we build an adversary Bi against CPAevk that has x, W and D as fixed internal in- The law has three coefficients, ρatt , ρlay and ρffn , and a fourth g puts. Bi receives (pk, evkg ), submits as its two messages the quantity ρnrm that enters through ρlay . ρatt counts the bootplaintext of the ith prompt ciphertext and the zero vector, and straps of one pair of a position offset and a state ciphertext on receives the challenge ct∗ . It encrypts the zero vector under the attention path of one layer. The pair has one bootstrap at the pk for the positions before i and the prompt’s own plaintexts entry of the exponential, one at the normalization of stage 0, one for the positions after i, and it samples r. It hands D the at each of the five square-and-normalize rounds of the softmax, tuple (W, r, pk, evkg , ct1 , . . . , cti−1 , ct∗ , cti+1 , . . . , ctc(g) ) and and one on the attention-value path before the product. The outputs what D outputs. When ct∗ encrypts the prompt’s plain- normalization of stage 0 is a site that this parameter set adds, text the tuple is distributed as Hi−1 , and when it encrypts zero because the exponential consumes nine levels and the causal mask one more. The operand therefore reaches the threshold as Hi . Bi runs in time at most t + c(g) tenc , so under a longer modulus chain and falls below it under this one.
evk A softmax approximation with another number of rounds gives Pr[D(Hi−1 ) = 1]−Pr[D(Hi ) = 1] ≤ Advg t+c(g) tenc . another ρatt , and the coefficient then follows the layer count Summing over i gives the bound, and the computed ciphertexts without further change. ρlay counts the bootstraps that a layer places once per state ciand the bootstraps add no hybrid, because they are functions of phertext. These are two normalizations, three entry bootstraps the tuple that D may compute itself.

16

for the query, key and value projections, the entries of the out- number of key-switching digits is the chain length divided by put projection and of the first feed-forward chunk, six for the de- the number of special primes. Two divisibility checks reject a nominator inverses of the softmax at stage 0 and at each of the chain that the primes do not divide, because such a chain drops five rounds, and two for the linear renormalization, one guard primes from the decomposition and produces a wrong result. and one inverse entry. ρnrm counts the bootstraps of one normal- The second check concerns the transfer of the keys to the workization, one at its entry, three inside the Newton iteration for the ers of the device axis. Each worker holds forty nine keys, 20.10 inverse standard deviation and one at its exit. The exit is a site GiB, and receives them in 4.2 to 4.3 seconds with one worker this parameter set adds, and it occurs at both normalizations of and in about 4.1 seconds per worker with two and three. a layer and once more in the tail. ρffn counts the bootstraps of one feed-forward chunk, one before the GELU, one after it and eight inside the Chebyshev evaluation of the GELU poly- D The Llama-3-8B column nomial. The lowest arrival level of that evaluation falls below the threshold on this parameter set, so the chunk term is linear The Llama-3-8B column of the evaluation is derived, and this appendix gives the derivation. The model has d = 4096, in K. One site does not occur uniformly, and the −(C − W ) term L = 32 and a vocabulary of 128,256 tokens, with RMSNorm, of the law accounts for it. A state ciphertext not written during SwiGLU, rotary position embeddings and grouped-query attenthe run retains the level at which it was encrypted, so the entry tion. At the parameter set of Appendix A it fills nine state cibootstrap of the first normalization is skipped on it. That entry phertexts at a context of 32. The cost law evaluated on this occurs at every state ciphertext in the layers above layer 0 and model gives 90,779 bootstraps for a prompt step and 93,085 for only at the written ones in layer 0, which gives (L − 1)C + a generated step. A level-by-level simulation of the circuit proW bootstraps against LC. The constant term counts what a duces the same two counts. The cached form gives 4,260 bootstep places once, the final normalization and the entry of the straps for a cached generated step, which is the generated count projection after the last layer. S counts the selection stage under divided by 21.9. The bootstrap duration measured on this parameter set is 368.4 ms. One device therefore needs 9.29 hours CutMax’s argmax. of bootstraps for a prompt step, 9.53 hours for a generated step and 0.44 hours for a cached generated step. Because no LlamaC.2 The rules at a homomorphic inverse 3-8B step was measured, each figure is a derived count times The implementation guards against distribution shift at the in- a measured duration, and the column has no wall clock of its put of a homomorphic inverse with three rules. The first rule own. puts a floor or a validity guard on every homomorphic inverse over all the slots the computation can reach, including the slots E The device axis in detail beyond those the designer expects. The second rule keeps every intermediate that a bootstrap sees within a fixed range of The evaluation reports the device axis as a result and as a lower about [0.1, 2] by constant scaling before and after the operation. bound. This appendix gives the two runs behind it and the barThe third rule sets the margins from the worst input the circuit riers on which the axis acts. In the first run the summed wall can receive. Where that input and the typical benchmark input clock of the barriers is 42251.7, 40121.6 and 38333.0 ms from differ by orders of magnitude, the rule re-parameterizes the cir- two to four devices. In the second it is 41410.1, 43670.3 and cuit. The shift appeared at seven sites, and the rules closed each 38265.7 ms. Two and four devices replicate within 2.0% and of them. The sites are the scale at the entry of selection, the 0.2%, whereas three devices do not, because the repetition is floors of the round sums, the pad denominators of the softmax, 8.8% above the first run and above two devices. The two runs the fill of the empty blocks in LayerNorm, the validity guard of therefore do not determine the wall-clock order of two and three the softmax, the coupling of the winner’s share and the mass in devices. In the repetition the width-two barriers account for the the final renormalization, and the basin of LayerNorm at valid excess at three devices. Their mean is 426.3 ms against 363.5 but tiny write-backs. The eighth site, the first inverse of the at two devices and 373.2 at four, and the excess grows as the attention softmax, remains open, and Appendix F gives its mea- step proceeds. The first 51 of these barriers take 376 to 430 ms. surement. From the fourth layer on, the last 26 take 449 to 514 ms, against 381 to 406 ms for the same barriers in the first run. In the repeC.3 Two implementation checks tition the generated step at three devices exceeds the step at two devices by 11 seconds. Of that excess, 8.7 seconds fall outside Splitting the special modulus in two halves the size of each the barriers, where the master device runs alone. The prompt evaluation key, and we checked that it leaves the error of a step has no barrier and takes 178 seconds at three devices in bootstrap unchanged. Three arms of twenty isolated calls at both runs, against 174 to 175 seconds elsewhere. We do not ring degree 215 , with the same usable levels, returned a postidentify a cause for that difference. bootstrap error of 2.164240 × 10−6 with two special primes The barrier model of the evaluation predicts ratios of 1.886, against 2.164191 × 10−6 with one. The error is the same to 1.062 and 1.000 for the summed barrier wall clock from two six digits, and the key set is 240.0 MiB against 465.0 MiB. The to four devices. The measured ratios are 1.1022, 1.0467 and 17

1.0000 in the first run and 1.0822, 1.1412 and 1.0000 in the second. The model therefore overstates the gain of the second device in both runs. In the first run a token takes 255.6, 236.7, 239.2 and 233.8 seconds from one to four devices. In the second it takes 255.1, 234.5, 242.4 and 235.4 seconds, and the share of the work that stays on the master device is 8.13% measured against 7.9% predicted. We judge the axis by the summed barrier wall clock because the axis changes that term. The wall clock of the whole step separates two, three and four devices by at most 3.7% across the two runs, against a within-process bound of 1.7%. The axis removes a fixed set of bootstraps from the critical path whatever their share of the step.

F

The context boundary and the cache counters

F.1

The context boundary

The loop returns the plaintext model’s tokens at every prompt length the evaluation ran on nanoGPT except one, and the failure at that length occurs at a single operation. We localized it on the development parameter set, at ring degree 215 , where the same failure appeared at a prompt of 49 tokens. We decrypted every intermediate value of the diverging step and of a healthy step under the secret key that the measurement program holds. On the paper’s parameter set the sweep of the evaluation places the boundary at a prompt of 48 tokens, and we did not repeat the localization there. The failure occurs at the inverse of the first round of the attention softmax. The inputs of the two steps to that inverse agree to 6% while their outputs differ by a factor of 56. The magnitude of the operand is therefore not the cause. What separates the two steps is the bootstrap before the inverse. Each probed block contains 128 pad slots that the validity fill sets to 1.0, so every inversion also inverts a known input. Those slots give the additive error of that bootstrap, −1.7 × 10−4 at the healthy step and −5.554 × 10−3 at the diverging one. The error is coherent across the slots of a block. The magnitude is specific to the individual bootstrap, because the two readings at the same operation differ by a factor of 32. The operand of that inverse is confined to a range with a bound at each end. The Goldschmidt iteration D 7→ D(2 − D) converges only below u = 2 and diverges past it. The error β of the bootstrap must stay a small fraction f of the operand, which requires u ≥ β/f . Together the two bounds give u ∈ [β/f, 1.4] ,

1.4 f umax = = 12.6 umin β

(3)

at the measured β = 5.55 × 10−3 and f = 0.05. Under the deployed scaling the operand of layer 0 decreases as 1/n and reaches β near n = 45 on that parameter set, against the collapse observed at 49. A single scaling constant is admissible only if it maps the denominator of every round in every layer into the range. The spread of those denominators grows with the context, at least as 0.25 n, so it exceeds the width of the 18

range near n = 51. Raising the scale to restore the margin of layer 0 sends the peaked rows of layer 1 past u = 2, so the two ends of the range fail together. A floor that masks the error must be comparable to the operand. A floor of that size perturbs the round by an order-one factor that the four later squarings of the softmax raise to the sixteenth power.

F.2

How far a generation stays exact

On the prompt that generated the most tokens, the loop returned the plaintext model’s token 24 times out of 24 and reached a context of 55. On a second prompt it returned 16 of 16 and reached a context of 47. On a third it returned 5 of 8, with the first loss at the fifth token. The first of these prompts was the joint best of a screen of twenty prompts, and the other two were not selected. A repetition of the 16-token run under a second secret key returned the same 16 tokens, with 71006 bootstraps in both runs and wall clocks 0.30% apart.

F.3

The cache counters

We read two counters on every run to check the cache. At both measured models the bootstrap count of the cache was zero on every cached step. Every appended key or value arrived five levels above the level at which its entry is held. A separate run appended to one entry 384 times, and its bootstrap count stayed at zero against five bootstraps in the comparison run. The drift after 64 appends was four orders of magnitude below its budget. The error of the appended terms grows with age at an exponent of 0.814, where independent terms would give 0.5, so the terms are coherent. An extrapolation to older entries has to use the measured exponent.

G

The projections

The last subsection of the evaluation projects the cost of models we did not run as a bootstrap count from a closed form times the bootstrap duration we measure. This appendix gives the form, the check it passes before we project any model, the memory model, the layer split, the stages of a step and the assumptions.

G.1

The cached form

The cost law is B(n) = ρatt LCn + (ρlay + ρffn K)LC − (C − W ) + τ, (4) in the bootstrap counts per attention site, per layer and per feedforward chunk, the layer count L, the chunk count K, the state ciphertext count C, the written-back count W and the tail τ of the step. Caching the keys and values changes two terms of it, Bcached = ρatt LC + (ρlay + ρffn K)L + τ0 .

(5)

The attention term loses its factor of n, because a cached step attends over the stored keys and computes the key and value of

one position only. The per-layer term loses its factor of C, because a cached step runs the layers over the new position alone. The tail τ0 is the tail of the step without the write-back bootstrap, which a cached step does not need.

G.2

100k

10

We project a model only after Equation 5 has returned both measured cached counts, 436 at nanoGPT and 1072 at GPT-2 small. The two models differ in width, in layer count, in vocabulary and in state ciphertext count, so the check exercises every factor of the form. The count check of the evaluation covers the uncached law over the whole context sweep.

10k 1k 100 10 1

Memory on one device

The memory footprint of a run on one device consists of five terms. The evaluation keys are the largest, at 49.63 GiB for the key count we measure. The runtime holds the context, the tables, the key pair and one bootstrap in flight. The weights take almost no memory, because the forward pass encodes each diagonal when it uses it. The working set consists of the operands a step keeps live, and the cache takes 12.0 MiB for the key and the value of one position in one layer. A layer split divides only the cache, because each device stores the entries of its own layers. The key term is a lower bound, since it is the count measured at nanoGPT and a wider model needs at least as many rotation keys. Every device count the model returns is therefore a lower bound. Against the two models whose whole-loop footprint we measure, the memory model is within about five per cent, low at one and high at the other.

G.4

The layer split

A layer split changes no bootstrap site and therefore keeps the bootstrap count, and sequential layers keep the per-token critical path. At each device boundary the split adds one transfer of the state ciphertexts. That transfer takes 26.3 ms at the 4.67 GiB per second measured for the key transfer, against a bootstrap of 368.4 ms. Throughput then scales by up to the device count over independent requests in flight. The device axis that the evaluation measures is the other placement, and its lower bound remains as measured.

G.5

The stages of a step

Figure 10 divides a step into its five stages for each projected model, without the cache and with it. The forward pass accounts for most of the step at every model, and a cached step has no write-back.

G.6

selection retrieval

write-back

1k

The check against the measured models

G.3

forward pass projection no cache

cached

nano GPT-2 Llama-3 Qwen3 Llama Qwen GPT small 8B 8B 3-70B 2.5-72B

Figure 10: Bootstraps of one step, split into five stages at a context of 32, without the cache (top) and with it (bottom). The figure omits Mistral-7B, whose step agrees with Llama-3-8B’s to three hundredths of a percent. correction. At a model whose selector runs the multi-ciphertext path they are therefore about three bootstraps low out of thousands. The coefficients are read at a context of 32 and applied at every context. The closed form agrees with the simulator at 64 and at 128, beyond which no run tests it. The key count at every model is the count measured at nanoGPT, a lower bound, so every device count is a lower bound. The fixed cost of the runtime is read once from the budget of the parameter set and is not measured per model. The cached working set is counted at nine operands per state ciphertext, which is conservative, because the query side of a cached step is one position wide. The layers divide evenly across the devices, only the state ciphertexts cross a device boundary and requests in flight do not contend, so the device count is an upper bound. The bootstrap duration is measured on this parameter set and does not depend on the model. Because a second reading of it differs from the first, we defend no second significant figure of a projected time. The projections cover dense models with full attention.

H

The results at row level

Table 8 lists the predicted and measured bootstrap counts of the evaluation at row level. The comparison record below gives the readings behind the comparison against NEXUS and against the client-interactive alternative.

H.1

The packed count across the context

At the widest group the measured packed count is 387 at a context of 32 and 740 at contexts of 40, 48 and 64. At half that group width it is 788 at contexts of 40 and 48. Each block of counts is constant over the contexts it covers, and the difference between the blocks is the state ciphertext count.

The assumptions

Each projection rests on the following assumptions, and each assumption fixes the direction of its error. The projected counts include the selection term of the level simulator and no further

19

Table 8: Predicted and measured bootstrap counts on nanoGPT under CutMax’s argmax, and at the two models that played no part in deriving the formula. The upper block lists eight of the twelve contexts of the sweep. These are the two crossings marked † with the context before each, where the state ciphertext count rises by one, the anchor pair at contexts 32 and 33, read at least 60 times on at least six nodes, and the two ends of the sweep. The generated step of each row is at the context one greater than the prompt step’s. No measured count differed from its prediction at any of the 24 combinations of context and step type, over 136 readings. The Llama-3-8B row is derived, since no Llama-3-8B step was measured. Prompt step Context

Generated step

C Predicted Measured Predicted Measured

The formula across the context, nanoGPT 16 1 1107 1107 30 1 1779 1779 31† 2 3620 3620 32 2 3716 3716 33 2 3812 3812 62 2 6596 6596 63† 3 10021 10021 64 3 10165 10165

1157 1829 3717 3814 3910 6694 10166 10311

1157 1829 3717 3814 3910 6694 10166 10311

Models outside the derivation, at n = 32 GPT-2, 65 tokens 3 11443 11443 GPT-2, full vocab. 3 11458 11461 Llama-3-8B 9 90,779

11733 11748 93,085

11733 11751

H.2

The comparison record

The comparison uses NEXUS’s own parameters, so its numbers belong in no cost column of this paper. Our GELU takes 70.35 ms, 1.020 of NEXUS’s reading, and our LayerNorm 43.74 ms, 0.972 of it, each over 30 calls with a deviation under 0.5%. Our matrix multiplication takes 0.2993 s per column on an H100 against the 1.31 s per column NEXUS reports for an A100. Our softmax microbenchmark takes NEXUS’s own input, and its decoded output equals NEXUS’s up to one common scalar of 1.10. After that scalar is divided out, its error is 0.63 of NEXUS’s own error against its calibration, and the origin of the scalar remains unidentified. An earlier measurement of the matrix multiplication was taken before the output check existed, so we withdraw it, and we compute no difference against the figure we withdrew. The multi-device variant of the matrix multiplication fails that check on the current build, at 1.0e+01 against a tolerance of 5e-02. The single-device path passes at 1.3e-07, so the paper reports the single-device figure. The interactive loop is the alternative in which the server sends the encrypted logits to the client, who decrypts them, selects the token and returns its embedding encrypted. We derive its cost on our own implementation with every assumption in the alternative’s favour, and every input to the derivation is a measurement of our own. The alternative takes 1062.0 seconds per generated token against our measured 1086.1, a saving of 2.216 percent. It requires 4.72 hours of client presence at sixteen tokens against two transfers for our loop.

20

Related documents

• Static Bootstrap Placement for Encrypted Language Model Decoding#1200563
• Watermarking Diffusion Language Models#1014549
• Demystifying the Privacy-Utility Trade-off in LLM Interactions#1069950
• Selective Disclosure Watermarking for Large Language Models#343356
• Residual Sparsification via Output Importance for Compressing Mixture-of-Experts LLMs#822036