Skip to section
Foundationsfor rotation-free search
Section 16 of 5231% of course
Contents
Chapter 3 Section 3.3 60 min

Part II · The problem and its constraints

From one score to nearest neighbors

Turn repeated scores into a corpus-wide top-k search.

Repeat one trusted calculation

Let the corpus contain vectors v₀ through vM−1. We just compute one score for each index j:

sj = ∑i=0D−1 qivj,i

The index i walks coordinates inside one single vector. The index j chooses which corpus vector is currently being scored. Keeping those two jobs cleanly separated in your head prevents many packing errors later.

Before we even look at privacy or hardware, let's pause over this nested structure. An inner loop over i computes one score. An outer loop over j repeats that score for the whole corpus. This is the simple, plain algorithm whose meaning every later optimization has to preserve.

Interactive score table · edit any coordinate
rank 1v19
rank 2v20
rank 3v0-8

Scoring and ranking are entirely different computations

Scoring performs M independent dot products. Ranking compares those M results and retains only the k winners. A score calculation uses simple multiplications and additions in a rigidly fixed pattern. Ranking requires branches, state about current winners, and a tie-breaking policy. Those are radically different computational shapes, and under encryption, they have dramatically different costs.

Doolittle therefore draws a strict boundary: the scoring server computes encrypted scores; the client decrypts those scores and ranks them locally. This is not some minor implementation detail. It completely determines what the server can learn and exactly which encrypted operations the hot path must support.

Worked example

Ties absolutely need a policy

If v₂ and v₇ share the exact same score at the cutoff, the system needs a deterministic tie-breaker, such as “smaller corpus identifier wins.” This is an application-level contract, not something the dot product decides on its own.

Worked example

k changes the answer, not the scores

Suppose the scores are [0.72, 0.91, 0.91, 0.34]. The scoring stage is mathematically identical for k=1 and k=3. With the policy “smaller identifier first,” top-1 returns item 1; top-3 returns items 1, 2, and 0. Keeping this distinction crystal clear prevents a later design from accidentally claiming that polynomial multiplication performs the ranking.

Check your understanding

What exactly does index j identify in sⱼ?

Algorithm boundary

If M doubles while D and k stay fixed, which plain computation necessarily doubles?

Section summary

  • Private search requires M separate dot-product scores.
  • i chooses coordinates; j chooses corpus vectors.
  • Ranking is a completely distinct stage with its own policy.

Repository layer · second pass

How does one comparison become a nearest-neighbor search?

Nearest-neighbor search repeats the same score contract over a corpus, associates each score with an identifier, orders candidates, and returns the best k. The ranking stage must define tie behavior, stable identifiers, and whether larger or smaller scores are better.

Exact top-k and approximate nearest-neighbor indexing are separate design choices. This course first makes exact scoring private and correct. Index structures can later reduce the number of candidates, but they introduce their own leakage and recall tradeoffs.

Reasoning chain

  1. 1

    Score each candidate with the same metric.

  2. 2

    Carry the corpus identifier beside the score.

  3. 3

    Define deterministic tie-breaking.

  4. 4

    Sort or select the highest k.

  5. 5

    Measure recall if a prefilter removes candidates.

Worked trace

Ranking is more than sorting floats

  1. Scores are [(doc7,.81),(doc2,.81),(doc9,.73)].
  2. The top score is tied.
  3. Choose stable ascending identifier as the tie rule.
  4. The ordered result begins doc2, doc7.

Result. A reproducible API includes tie semantics, not merely k.

Executable lens · Python

Make the hidden state visible

def top_k(scores, k):
    # sort by descending score, then stable identifier
    return sorted(scores, key=lambda item: (-item[1], item[0]))[:k]
assert top_k([("d7",.81),("d2",.81),("d9",.73)], 2)[0][0] == "d2"

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

Misconception clinic

Tempting mistakes

  • Losing identifiers while batching scores.
  • Assuming approximation cannot change order when scores are close.

Retrieval and transfer

Close the book first

  1. Specify top-k behavior for NaN, ties, and k larger than the corpus.
  2. Compare full sorting with a size-k heap.
  3. Identify what an approximate prefilter may leak.