It’s slightly better for LLMs because FHE is really bad at branches (it ends up essentially having to try both branches), making sorts nearly the worst possible thing to try since it’s all branches. In the case of AI most things are just addition and multiplication which can make some things faster since there aren’t as many branches. But we’re still nowhere near viability.
The flip is also true: LLM inference is very nearly maximally optimal for FHE. Thee costly bit, multiplication of a bunch of compressed floating point numbers, translates 1:1. The only bit I’m not sure about is the softmax sampling at the end, but that’s just once per token.
On the other hand, each FHE step is a LOT more costly (e.g. elliptic curve exponentiation) than a vectorized BF8 multiply on GPU.
Unlike the sorting number case, it is probably same complexity. But no hardware support AND a massive slow down constant even if you were comparing apples to apples on hardware.
Disclaimer: I spent a decade working on crypto systems but I am not familiar with TFA’s research.
That's softmax dot-product attention. It's quadratic even without fully-homomorphic encryption, but at least it's not inherently branchy, so won't necessarily slow down much more than other floating point operations under encryption.
But softmax sampling, where you pick a single output token at the end and feed it back in to generate the next one, is branchy, so you need to do some extra encrypted computation to avoid leaking which token was sampled.
I found [1] which appears to offer state-of-the-art performance of ~1000s latency for a FHE GPT-2 transformer block, equating I think to 3.33h inter-token latency (0.00008 token/s) for GPT-2(small) which has 12 transformer blocks. This result is using optimised packed arithmetic operations on a GPU as well--so seemingly is unlikely to have much performance upside from further optimisation.
I'm not sure I've interpreted [1] correctly though, and would appreciate correction if necessary.
[1] https://arxiv.org/pdf/2604.04783 -- GPU Acceleration of TFHE-Based High-Precision Nonlinear Layers for Encrypted LLM Inference -- Guoci Chen, Xiurui Pan, Qiao Li, Bo Mao, Congming Gao, Chengying Huan, Mingzhe Zhang, Jie Zhang -- Apr 2026
Sorting doesn't need any branches. For FHE you need to think like a circuit designer without indexing operations. In that situation your default sort is a sorting network, made out of nlogn conditional swaps.
Once you calculate which value is smaller, the conditional swap itself is trivial. Let's say inputs A and B, comparison result is a boolean C. Outputs X and Y.
Bitwise: X = A&C | B&¬C, Y = A&¬C | B&C
Arithmetic: X = A*C + B*(1-C), Y = A*(1-C) + B*C
Edit: Or to put it another way, one of the most basic things you can make in a circuit is a multiplexer, and a conditional swap is two minimum size multiplexers next to each other.
I’m genuinely not an expert, but isn’t the beauty of MoE models the fact that we explicitly don’t evaluate every parameter on inference? We evaluate exactly the subset that are needed to evaluate a prompt. Seems like this will bring back data-dependent branches again.
It would also kill speculative decoding. You would have to run a full inference pass for every token instead of being able to generate multiple tokens with a single pass.
Pretty much, and this does a good job of illustrating the fundamental issue with branching. You could use an encryption scheme that allows the server to determine what MoE expert to load (the simplest would be to have the client decode the value and send it back to the server, though this can sometimes be possible to do without the round trip), but then it’s not fully homeomorphic because the server has some info about the computation that could be used to recover stuff about the original text.
Taking the above point to the extreme, a very simple yet mildly effective “homeomorphic encryption” scheme would be to run the first layer(s) of the ML model on-device, run the majority of the model in cloud, then run the remainder of the model on the device. But then you leak a lot of information that can essentially be used to get back the original text. (Usually in this type of scheme, to defend against this, the provider of cloud services doesn’t have access to the full model, it’s been used before on vision applications involving medical data)
