8.4 Extract, unscale, and rank on the client

Peeling the onion backward

When data pops out of the accelerator, it's not a list of scores yet. It's a jumbled mess of transformed residue limbs broken into ciphertext components. We have to run the whole process in reverse: reconstruct the limbs, run inverse transforms, and decrypt it back into an approximate coefficient polynomial. Only then can we lean on our index proof from Chapter 4 and read the target score sitting at the right edge of the block.

Back to the host for the finale

host/doolittle_host.py:497

def decrypt_scores(self, products):
    scores = []
    for comps in products:
        if len(comps) == 2:
            msg = self.ctx.decrypt_ntt(comps[0], comps[1])
        else:
            msg = self.ctx.decrypt3_ntt(comps[0], comps[1], comps[2])
        for v in range(VECS_PER_POLY):
            scores.append(msg[D * v + D - 1] / (DELTA * DELTA))
    return scores

If we see two components, we know we just scored a plaintext corpus. If we see three, we know it was an encrypted corpus (and it's unrelinearized). Once we decrypt the polynomial, we loop through each local vector v, pluck the score from the right edge of its block, and divide by Δ² to restore the real-world scale.

local_target(v)=Dv+D−1 global_item(product,v)=product·(N/D)+v

Don't lose track of the global index

Inside a single polynomial, the local vector index v runs from 0 to N/D − 1. But to figure out which global corpus item you just scored, you also need to know which polynomial you're currently decoding, and you need to watch out for padded junk at the end of the final polynomial. You have to actively throw away padded scores, otherwise they'll pollute your rankings.

Worked example

Example: D=128

If VECS_PER_POLY=32, our local score taps land at 127, 255, 383, and so on up to 4095. If we want to find global corpus item 45, we look in product polynomial 1 (since 45 // 32 = 1). Its local vector index is 13, so the score is sitting at coefficient 128 × 13 + 127 = 1791.

Worked example

Handling the awkward final polynomial

Imagine our corpus only has 45 items at D=128. The first product polynomial holds items 0–31. The second polynomial holds items 32–44... plus 19 empty, padded blocks. The extraction code will happily hand you 64 decoded taps, but only the first 45 are real. If you rank all 64, you're going to show the user search results based on empty padding zeros.

def score_locations(corpus_count: int, N: int, D: int):
    per_poly = N // D
    for global_id in range(corpus_count):
        product = global_id // per_poly
        local = global_id % per_poly
        coefficient = D * local + D - 1
        yield global_id, product, coefficient

assert list(score_locations(33, 4096, 128))[-1] == (32, 1, 127)

Check your understanding

Why do we have to divide the final score by DELTA * DELTA?

Section summary

The number of components tells you which decryption math to use.
The local target for vector v is always at index Dv + D − 1.
You need metadata to translate that local target back to a global corpus identity.
Don't forget to divide by Δ² to fix your fixed-point math.

Repository layer · second pass

How does the client recover scores without interpreting every coefficient?

After inverse transform and decryption, the client reads taps tⱼ=Dj+D−1. Each stored integer score carries scale Δ² because both input coordinates were scaled by Δ before multiplication. Dividing by Δ² returns an approximate real score, which is then paired with its corpus identifier and ranked.

Extraction should validate batch length and use the same tap generator as packing tests. Non-target coefficients are not errors; they contain other convolution buckets and can be discarded for this API.

Reasoning chain

1
Confirm coefficient-domain decrypted form.
2
Generate taps from N,D,batch count.
3
Read only valid batch taps.
4
Convert centered modular integers.
5
Divide by Δ².
6
Attach identifiers and apply deterministic ranking.

Worked trace

Extract an underfilled batch

Capacity is 8 but batch contains 3 vectors.
Valid taps are 511,1023,1535.
Do not interpret the five unused block taps as results.
Associate three decoded scores with the original three IDs.

Result. Capacity and logical batch length remain distinct.

Executable lens · Python

Make the hidden state visible

def extract(coeffs,d,count,scale):
    taps=[d*j+d-1 for j in range(count)]
    return [coeffs[t]/(scale*scale) for t in taps]

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

Misconception clinic

Tempting mistakes

Dividing by Δ instead of Δ².
Returning capacity-sized output without validity metadata.

Retrieval and transfer

Close the book first

Add centered residue conversion.
Define behavior for partial final corpus batch.
Prove identifier order matches block order.