Static Bootstrap Placement for Encrypted Language Model Decoding

Halil Ibrahim Kanpak; Didem Unat

cs.CROct 4, 2026

Static Bootstrap Placement for Encrypted Language Model Decoding

Authors: Halil Ibrahim Kanpak, Didem Unat

Organizations: Department of Computer Engineering, Koç University, Istanbul, Türkiye

Abstract

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.

Figures & tables

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.

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.

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

\rho_{att}

bootstraps per layer. The reservation stops at the

\lceil n/b\rceil

state ciphertexts the context has reached, and causality zeroes each pair past

r=b(c+1)

, so the step skips those pairs.

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.

	$L$ , $K$ , $V_{ct}$	$b$	$\rho_{att}$ , $\rho_{lay}$ , $\rho_{ffn}$	$s$	$c$	$k$
nanoGPT	6, 3, 1	32	8, 21, 10	48	305	34, 36
GPT-2 small	12, 4, 4	16	8, 21, 10	96	731	52, 54
Llama-3-8B	32, 4, 8	4	8, 19, 10	256	1,887	68, 70
Mistral-7B	32, 4, 3	4	8, 19, 10	256	1,887	43, 45
Qwen3-8B	36, 3, 10	4	8, 19, 10	288	1,763	78, 80
Llama-3-70B	80, 4, 8	2	8, 19, 10	640	4,719	68, 70

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=\rho_{att}L

and

C=\lceil n_{\max}/b\rceil

, and

k

is given for the prompt step and the generated step. The rows below the rule are derived from each model’s circuit.

	Prompt step		Generated step
	predicted	measured	predicted	measured
nanoGPT	3716	3716 (1421)	3814	3814 (1456)
GPT-2 small	11458	11461 (4622)	11748	11751 (4715)
Llama-3-8B	90,779	90,779 ‡	93,085	93,085 ‡

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

\ddagger

are derived, and the number in parentheses is the measured runtime of that step in seconds.

Figure 5: Bootstraps per prompt step against context, on one device. Each line is the closed form of one model, and a cross inside a ring is a measurement that falls on the prediction. The Llama-3-8B rings are empty because we did not run a step on that model.

	Two steps		Prompt step
	bootstraps	wall clock	context 32	context 48
Dead work	30.4 %	29.7 %	45.8 %	46.5 %
+ packing	81.7 %	76.1 %	80.6 %	83.9 %

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.

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.

Bootstraps	None	+ dead work	+ packing	+ cache
nanoGPT	3814	3766	742	436
GPT-2 small	11751	10023	2535	1072
Llama-3-8B	93,085	62,365	19,357	4,260
Mistral-7B	93,060	62,340	19,332	4,235
Qwen3-8B	101,483	66,923	18,539	4,434
Llama-3-70B	439,333	275,493	91,173	15,668

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.

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.

#GPUs	(bootstraps)	model	run1	run2	run1	run2
	Critical path	Generated step (s)			Speedup
1	227	342	337	336	1.00	1.00
2	114	300	300	295	1.12	1.14
3	102	296	300	306	1.12	1.10
4	102	296	292	297	1.15	1.13

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.

Operation	Ours	NEXUS
GELU	70.35 ms	69 ms
LayerNorm	43.74 ms	45 ms
Softmax	20.01 ms	20 ms
Matrix multiplication/column	0.2993 s	1.31 s

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.

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.

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.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

quantity	value
ring degree	$2^{16}$
slots used	$2^{14}$
secret	sparse ternary, $h=192$
ciphertext primes	$51+13\times 46$ bits
special primes	$2\times 51$ bits
positions per ciphertext, $b$	32

Appendix

Table 7: The parameter set of every measurement in the paper.

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.

The formula across the context, nanoGPT
		Prompt step		Generated step
Context	$C$	Predicted	Measured	Predicted	Measured
16	1	1107	1107	1157	1157
30	1	1779	1779	1829	1829
31 †	2	3620	3620	3717	3717
32	2	3716	3716	3814	3814

Appendix

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

\dagger

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.

Privacy-Preserving Language Models

Privacy-preserving language models protect sensitive data during training, inference, personalization, and information sharing.

See all 178 papers

HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation
Sep 1, 2026Alessandro Zirilli, Davide Marincione, Evgenios M. Kornaropoulos +2Privacy-Preserving Language Models Homomorphic Encryption
Sapienza University of Rome · George Mason University · Paradigma
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
Jun 8, 2026Yuhan Ma, Yong Li, Stefan SchmidSecure Multi-Party Computation Privacy-Preserving Language Models
Huawei Heisenberg Research Center, Huawei Technologies Düsseldorf GmbH, Düsseldorf, Germany · Technische Univer-sität Berlin, Berlin, Germany
Leaky Language Models: Stealing Architecture and Inference Optimizations via Per-Token Timing
Jul 22, 2026Sadegh Majidi, Niloofar Mireshghallah, Kazem TaramModel Extraction Attacks Language Model Fingerprinting
Purdue University West Lafayette, IN, USA · Carnegie Mellon University Pittsburgh, PA, USA

Sep 1, 2026J/K move · Enter open · S save

HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation

Alessandro Zirilli, Davide Marincione, Evgenios M. Kornaropoulos, Giuseppe Ateniese+1

Sapienza University of Rome · George Mason University · Paradigma

Privacy-Preserving Language Models Homomorphic Encryption Privacy-Preserving ML Efficient Language Model Inference

Open paper AskPDF arXiv

Fully homomorphic encryption (FHE) allows a server to run a language model directly on encrypted user prompts, but current approaches remain prohibitively slow. Ciphertexts natively support only addition, multiplication, and rotation, and multiplications may be composed only to a bounded depth before a costly bootstrapping operation is required to continue. Every nonlinearity must therefore be approximated by an iterative method; each iteration increasing the number of multiplications. A higher iteration count buys precision but exhausts the available depth more frequently and thus triggers more bootstraps, which dominate latency. We introduce Homomorphic Encryption-Aware Training (HEAT), a fine-tuning method that makes the per-nonlinearity iteration counts learnable, enabling them and the model weights to co-adapt during training. HEAT optimizes iterations with respect to the task objective, allowing the model to adapt to approximation errors encountered during inference without architectural changes or retraining from scratch. We further relate iteration count to quantization bit width and bound, at fixed weights, the gap between our objective and quantization-aware training. On encrypted GPT-2 decoding, HEAT reduces iterations by

3.1\times

, bootstraps by

1.6\times

, and end-to-end latency by

1.4\times

, while improving decode agreement over the calibrated encrypted baseline.

Abstract

Privacy-Preserving Language Models

Explore similar work

HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation

FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing

Leaky Language Models: Stealing Architecture and Inference Optimizations via Per-Token Timing