Reversed physical positions make every matching logical coordinate arrive at the same coefficient.
Reversal is just the equation we solved
For our target T=D−1, the layout p(i)=D−1−i places coordinate 0 at the far right edge, coordinate 1 one step to the left, and coordinate D−1 all the way at the left edge. If we read the physical storage from left to right, we see:
The word reverse is a handy way to describe it, but the index equation is the real reason it works. So, "reverse the vector" shouldn't be the rule you memorize. The real, reusable engineering principle is: choose a target, and solve the constant-sum equation. If we stored the query at an offset, or if we changed the target, just blindly reversing around zero could give you completely wrong answers.
Look at that! The +i and −i perfectly cancel each other out. That elegant little cancellation is the heart of the inner-product trick. Polynomial multiplication will now automatically add up all the products that land at D−1, so our coefficient naturally becomes ∑qivi. Notice we didn't say anything about what the coordinate values actually are; this whole trick is purely positional.
Worked example
Let's plug in some actual values
Let's say q=[2,−1,3,1] and v=[3,0,1,−1]. Our layout says we store v as [−1,1,0,3]. Look at coefficient 3: the contributing products are 2×3, (−1)×0, 3×1, and 1×(−1). That totals 8, which is the exact same dot product we calculated by hand back in Chapter 1.
Worked example
A zero value doesn't delete its position
What if v₁=0? The product q₁v₁ contributes zero to the sum, sure, but coordinate 1 still strictly occupies its physical position at D−2. Having sparse numerical values doesn't change our layout equation at all. This is a crucial distinction: our algorithm's correctness can't depend on which specific values happen to be zero during a given request.
So what happens to all the nonmatching products?
They certainly aren't deleted! A pair like qivr (where i≠r) lands at position i+(D−1−r), which isn't D−1. The full polynomial still contains all these cross-coordinate products, scattered in the neighboring coefficients. Our construction simply assigns meaning to one specific score tap; we aren't claiming the other coefficients magically vanish.
Check your understanding
What mathematical event ensures that every single matching product shares the same coefficient?
Failure-mode check
What goes wrong if we reverse both the query AND the corpus inside the block?
Section summary
- Reverse storage is exactly p(i)=D−1−i.
- Every matching product lands neatly at D−1.
- The other convolution outputs still exist, but we just don't interpret them as our score.
Solve the index equation, inspect contributor bounds, and probe the proof with small exact examples.
Runs entirely in this browser. Python executes in Pyodide WebAssembly with no remote kernel. The construction code stays visible while reactive dependents recompute whenever you change an input.
Repository layer · second pass
Why does reversal make the logical index cancel?
With T=D−1, corpus coordinate i is stored at D−1−i. Polynomial multiplication adds physical positions, so the matching product travels to i+(D−1−i)=D−1. The logical index appears once positively and once negatively; cancellation makes the destination constant.
This is the heart of the trick, but it is not magic. It is a representation transform chosen to convert logical equality into the constant-sum relation that multiplication already groups. Nonmatching pairs remain elsewhere and need not vanish.
Reasoning chain
- 1
Store qᵢ at i.
- 2
Store vᵢ at D−1−i.
- 3
Add the two physical positions.
- 4
Cancel +i and −i.
- 5
Read the target coefficient; ignore unrelated coefficients.
Worked trace
Separate matching from incidental products
- Use q=[a,b,c] and reversed v=[z,y,x].
- Coefficient 2 receives az+by+cx.
- Interpreting z=v₂,y=v₁,x=v₀ gives av₂+bv₁+cv₀ only if labels are assigned incorrectly.
- Correct packing is [v₂,v₁,v₀], so q positions multiply as q₀v₀ at 2, q₁v₁ at 2, q₂v₂ at 2.
Result. Track logical labels separately from array display to avoid reversing the meaning twice.
Executable lens · Python
Make the hidden state visible
q, v = [2,-1,3], [4,5,-2]
packed_v = list(reversed(v))
target = len(q) - 1
score = sum(q[i] * packed_v[target-i] for i in range(len(q)))
assert score == sum(a*b for a,b in zip(q,v))Retype this example, predict each intermediate value, and then change one input that touches a boundary.
Misconception clinic
Tempting mistakes
- Expecting non-target coefficients to be zero.
- Reversing values but continuing to label packed positions as natural coordinates.
Retrieval and transfer
Close the book first
- Expand the symbolic D=4 target coefficient.
- Identify where q₀v₁ lands.
- Explain the construction as relation conversion, not array reversal.