Start by counting concrete operations
A direct, unencrypted plaintext score requires exactly D scalar multiplications and D−1 scalar additions. So, M vectors need MD coordinate multiplications and M(D−1) coordinate additions. These counts describe the sheer mathematical workload, but they don't describe the implementation yet. The moment we try to hide the data, we completely change how those logical operations are built and what kind of heavy auxiliary work we have to drag around with them.
Worked example
A small baseline
If M=1000 and D=128, the basic plain algorithm is doing 128,000 coordinate products and 127,000 additions. An encrypted design still has to embody all of those contributions somehow! The advantage of an encrypted design has to come from batching, parallelism, or aggressively eliminating expensive auxiliary operations—it doesn't magically make the mathematical products disappear.
The conventional packed reduction tree
If you use a standard lane-wise multiplication, a tree reduction is going to demand log₂D rotation-and-add stages (assuming D is a power of two). At D=128, that's 7 brutal stages; at D=4096, it's 12. Every single stage demands one rotation and one ciphertext addition. The additions are actually fine; the real nightmare is the rotations, which drag in automorphism/key-switch work, massive evaluation-key storage, and tons of extra memory traffic.
The coefficient-layout path
Our reversed layout needs exactly zero rotations and zero explicit coordinate-reduction stages during scoring. The polynomial product still computes a massive convolution (or its transform equivalent), but the reduction isn't completely free: it's fused directly into the coefficient collection. We didn't eliminate the underlying coordinate products; we eliminated a completely separate, horribly expensive sequence of encrypted operations.
In a transform-based implementation, you also have to ask which operands are already transformed. If you have a static corpus, you can store it in an evaluation-friendly domain forever, while you still have to prepare each new incoming query. To get a credible latency estimate, you have to count up forward transforms, pointwise modular products, inverse transforms, residue limbs, ciphertext components, and memory passes.
N ÷ D
log₂D
reduction is in coefficient multiplication
Worked example
Same asymptotic class, completely different system
You could have two pipelines that are both perfectly accurately described as O(N log N) because they both use polynomial transforms. But if pipeline A also executes seven key-switched rotations, loads massive rotation keys, and writes out intermediate ciphertexts seven times, its actual wall-clock cost and hardware footprint will look completely different from pipeline B. Big-O notation is designed to deliberately discard exactly those constants and resources.
Check your understanding
What specific work did our layout actually eliminate?
Cost-model check
Why on earth could two O(N log N) implementations have completely different latency?
Section summary
- Always count concrete operations before you try to compress them into big-O notation.
- Our layout successfully fuses the reduction step straight into the multiplication.
- Having zero score rotations is amazing, but it definitely does not mean zero total computation.
Repository layer · second pass
What should the cost model count before claiming improvement?
Count the full path: packing, forward transforms, ciphertext component products, modular limbs, inverse transforms, response coefficients, and client extraction. The layout removes hot-path encrypted rotations for score reduction; it does not remove D logical products per score or the polynomial multiplication that realizes them.
Use separate columns for asymptotic growth and concrete constants. N log N may hide lane count, modulus count, word width, memory passes, and batch occupancy. A useful model can predict a benchmark and explain deviations.
Reasoning chain
- 1
Define workload variables N,D,B,L.
- 2
Count each primitive per batch.
- 3
Convert counts to bytes and cycles.
- 4
Include keys and setup amortization.
- 5
Compare equal output contracts.
- 6
Validate the model against measurements.
Worked trace
Density versus reduction
- N=4096,D=512 packs 8 vectors.
- Baseline slot reduction needs 9 rotation stages per packed score group.
- Layout method extracts 8 fixed coefficient taps after one product path.
- Both still perform transforms and modular multiplications.
Result. The claimed saving is specific: reduction rotations and associated key/data motion.
Executable lens · Python
Make the hidden state visible
def model(n, d, limbs, components=3):
return {
"vectors": n // d,
"rotation_stages": (d.bit_length()-1),
"residue_products": n * limbs * components,
}Retype this example, predict each intermediate value, and then change one input that touches a boundary.
Misconception clinic
Tempting mistakes
- Comparing different batching or security parameters.
- Calling rotations zero-cost because they are absent from Python source.
Retrieval and transfer
Close the book first
- Add bandwidth estimates to the model.
- Model underfilled final batches.
- List measurements needed to calibrate one modular multiplier.