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.