Skip to section
Foundationsfor rotation-free search
Section 21 of 5240% of course
Contents
Chapter 4 Section 4.2 64 min

Part III · Construction and proof

Choose the destination before choosing the layout

Turn “matching coordinates” into an index equation.

Design backward from the output you want

Natural storage failed us because we treated the physical position as sacred. It's really not! The logical vector is just an ordered collection of coordinates; where we actually place them in the physical coefficients is entirely up to us, as long as our encoding and extraction steps agree.

Let's choose one target position T where we want our finished score to appear. Our query coordinate i is already sitting at position i. Let's call p(i) the corpus position where we decide to store coordinate i. Now we have a classic software-design question, just framed algebraically: what mapping function p forces every desired pair to satisfy the multiplier’s destination rule?

i + p(i) = T

This simple equation is our entire design requirement. Every matching pair must land perfectly at the same target T. If we solve it for our unknown storage position, we get:

p(i) = T − i

This is a massive shift in how we look at the problem. We aren't trying to rewrite how multiplication works. Instead, we're arranging our data so that multiplication's native grouping rule accidentally does exactly the reduction we wanted all along. The burden of proof just moves into the layout function and its bounds.

Picking the smallest convenient target

If we have one length-D vector starting right at position 0, let's just pick T=D−1. That means p(0)=D−1, p(1)=D−2, all the way to p(D−1)=0. The beauty here is that every single storage position stays safely inside our D-wide region.

Worked example

Let's trace D=4

p(0)=3,  p(1)=2,  p(2)=1,  p(3)=0

Notice how the storage positions step down at the exact same rate our coordinate indices step up. Let's check the sums: 0+3=3, 1+2=3, 2+1=3, and 3+0=3. Perfect. All four matching products now happily share bucket 3.

Worked example

Why did we choose T=D−1?

If we had chosen a target T smaller than D−1, our last position p(D−1)=T−(D−1) would end up being a negative number, which isn't a valid position in our first block! Picking T=D−1 is the earliest target we can use that keeps all D of our storage positions neatly between 0 and D−1. We could use larger targets, but we'd have to deliberately shift our block over.

Check your understanding

If we have D=8 and pick target T=7, where do we have to store corpus coordinate 2?

Bounds check

Why is T=5 an invalid target if we want to place a length-8 vector entirely within positions 0 through 7?

Section summary

  • Always choose your target T first.
  • Set the rule: query position plus corpus storage position must equal T.
  • Solving that gives us our layout function: p(i)=T−i.

Repository layer · second pass

How does choosing the destination turn layout into an equation?

Choose a target coefficient T first. Keep query coordinate i at position i and let p(i) be the unknown corpus position. Requiring every matching product to reach T gives i+p(i)=T. The layout is no longer a guess; it is the solution p(i)=T−i.

The target must leave room for every p(i). For a D-wide block starting at zero, T=D−1 makes p range from D−1 down to 0. Other targets shift the same reversal into another block.

Reasoning chain

  1. 1

    Name the fixed destination T.

  2. 2

    Write the query position i.

  3. 3

    Represent the corpus position as unknown p(i).

  4. 4

    Impose i+p(i)=T.

  5. 5

    Solve and verify the full index range.

Worked trace

Solve positions one by one

  1. Let D=4 and T=3.
  2. p(0)=3, p(1)=2, p(2)=1, p(3)=0.
  3. Each sum i+p(i) equals 3.
  4. The corpus positions are exactly the original block in reverse order.

Result. Target selection derives reversal rather than assuming it.

Executable lens · Python

Make the hidden state visible

d, target = 4, 3
positions = [target - i for i in range(d)]
assert positions == [3, 2, 1, 0]
assert all(i + positions[i] == target for i in range(d))

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

Misconception clinic

Tempting mistakes

  • Choosing T without checking p(i) remains inside storage.
  • Reversing both query and corpus, which changes the solved equation.

Retrieval and transfer

Close the book first

  1. Solve p(i) for D=6,T=11 and identify the block.
  2. Choose an impossible target and show the out-of-range position.
  3. Generalize to query stored at offset Q.