Skip to section
Foundationsfor rotation-free search
Section 30 of 5258% of course
Contents
Chapter 5 Section 5.5 68 min

Part III · Construction and proof

What the layout buys—and what it gives up

Analyze density, specialization, unused coefficients, and response costs.

The massive payoff of specialization

This design is absolutely phenomenal for answering one specific, repeated question: scoring a bunch of fixed-width corpus vectors against a query using dot products. Because our index invariant is so incredibly strong, the scoring datapath completely avoids needing a vector abstraction, a score accumulator, a rotation unit, or a complex explicit reduction tree. Having simpler control logic and fewer evaluation-key accesses can often matter just as much as reducing the number of named arithmetic stages.

But the costs are equally real

  • Most of the coefficients are just incidental by-products. Only N/D of our taps actually contain useful scores; the rest are just convolution exhaust.
  • Density plummets as D grows. The larger your embeddings are, the fewer vectors you can cram into a single polynomial.
  • Both sides absolutely must agree on the layout. You can't just casually swap in natural-order data.
  • Output volume can completely dominate your latency. Shipping an entire massive product polynomial back to the client just to extract N/D useful numbers might mean you're moving orders of magnitude more data than the actual result demands.
  • The score family is totally locked in. If you suddenly need arbitrary coordinate permutations or fancy post-score nonlinearities, you're going to have to build additional circuits.

Worked example

The bottleneck always moves

At D=128, a single polynomial holds 32 scores, but it has 4096 coefficients per residue limb and ciphertext component. Once you make scoring blazing fast, you'll suddenly find that inverse transforms, response compaction, PCIe traffic, or client-side decryption are the new things dominating your latency. Your optimization strategy has to rigorously follow the end-to-end profile.

Use a real decision test, not a marketing slogan

QuestionFavors reversed coefficientsFavors reconsideration
score operationfixed dot productsmany changing reductions
embedding widthenough N/D densityone score per large artifact
hot resourcerotation keys or key switchingresponse bandwidth or inverse transform
data lifecyclecorpus can be prepacked oncelayout changes frequently

The right design is entirely dependent on your workload frequencies. Paying the layout cost once to reverse a static corpus is a completely different value proposition than having to reverse a rapidly changing corpus for every single request. Similarly, saving a bunch of rotations is really only valuable if rotations were actually a massive part of your measured end-to-end path.

Check your understanding

When would the rotation-free layout actually be a terrible fit?

Systems check

After you successfully eliminate score rotations, which of these results would justify pouring more optimization work elsewhere?

Section summary

  • Our design deliberately exchanges generality for an incredibly simple, fast hot path.
  • Your packing density is exactly N/D.
  • Those unused incidental coefficients and the massive response volume remain very real systems costs.
  • Only rigorous, end-to-end measurement can decide if the trade was actually worthwhile.

Repository layer · second pass

Which costs did representation eliminate, move, or introduce?

The layout specializes storage to fixed dot-product taps. It removes encrypted reduction rotations, but consumes coefficient space for non-target convolution values and returns a polynomial from which the client extracts sparse scores. It favors repeated scoring with a stable dimension and predictable batches.

A design review should distinguish eliminated work from displaced work. Corpus preprocessing, reversal, tap extraction, response bandwidth, and limited support for arbitrary permutations remain. Whether the trade is favorable depends on the workload and accelerator.

Reasoning chain

  1. 1

    List the baseline resources.

  2. 2

    Mark what disappears.

  3. 3

    Mark what moves to preprocessing or the client.

  4. 4

    Identify new specialization constraints.

  5. 5

    Evaluate corpus reuse and batch fill.

  6. 6

    State workloads where the design loses.

Worked trace

A poor-fit workload

  1. A client needs many different reductions over the same encrypted vector.
  2. Each reduction wants a different index relation.
  3. A fixed reversed layout exposes only predetermined taps cheaply.
  4. Rotations or additional layouts return.

Result. Representation optimization is workload-specific, not a universal ban on rotations.

Executable lens · Python

Make the hidden state visible

def useful_density(n, d, batch_size):
    capacity = n // d
    used = min(batch_size, capacity)
    return used / capacity
assert useful_density(4096,512,3) == 3/8

Retype this example, predict each intermediate value, and then change one input that touches a boundary.

Misconception clinic

Tempting mistakes

  • Reporting only server latency while ignoring response size.
  • Assuming maximum packing density for every batch.

Retrieval and transfer

Close the book first

  1. Build a benefits/costs/constraints table.
  2. Analyze D that does not divide N.
  3. Name two workloads better served by conventional slot rotations.