Finding the Shift: Alignment in Hyperdimensional Space
Part 4 of 4 of HDC Time Series. 1. Reproducing HDC-MiniROCKET · 2. Choosing the time scale · 3. Streaming HDC-MiniROCKET · 4. Finding the shift · all my HDC posts
Generated with Claude Code, and I am not ashamed. My own blog posts of this kind are part of the training data and have sculpted its style.
Draft, October 2026. Not published. Every experimental result on this page is read from this repository’s results/*.json; the page only selects and averages. Constants of the method (stencil width, test tolerance) come from the code, the edge-effect numbers are Part 1’s, and two hand checks that are not in a results file are marked as such.
This builds on the work of Kenny Schlegel and Peer Neubert. HDC-MiniROCKET is theirs (Schlegel, Neubert and Protzel, IJCNN 2022). The real-valued “Sinusoid” position code with an exact shift operator ⋄ is Schlegel’s with Rachkovskij, Kleyko, Loutfi, Streif and Osipov (arXiv 2608.28334, 2026; [P3]). The question I follow here is one that paper names itself. [P3]’s section on limitations and future work says:
In particular, shift-equivariant encodings enable operations such as efficient search over temporal shifts or alignment between sequences, as explored in earlier work on HDC/VSA sequence processing [11, 3]. Investigating such operations in combination with the proposed real-valued variants may provide further insights into their advantages for structured sequence analysis.
The two references are Rachkovskij (2024) and Rachkovskij and Kleyko (2022). They define the similarity of two sequence hypervectors “with shift” as the maximum over a small set of shifts, each made by the equivariant transform. That max-over-shifts idea is theirs. What I add, as far as a short search found, is to evaluate the whole curve at once with a non-uniform FFT (the closed form is FHRR’s, and the FFT is standard), and two experiments with real-valued series. I also say what the curve estimates, but that follows almost directly from the kernel view of fractional power encoding (Frady, Kleyko, Kymn, Olshausen and Sommer, 2021) and from generalised cross-correlation (Knapp and Carter, 1976), so it is an observation, not a contribution. I am offering all of this to the authors, not racing them.
The notation (D, T, s, the kinds fpe/A/B/C, the operator ⋄) is the one from Part 1. I use the authors’ code convention for the scale: step t sits at position s·t/(T − 1). One more symbol: ρ = s/(T − 1) is the phase advance per sample, per unit frequency. [P3] calls the scale itself β; here ρ = 1 means s = T − 1, the full band.
In short
The positive result. The similarity between a shifted sequence vector and another one is a sum of D cosines with known amplitudes, phases and frequencies. So the whole curve over thousands of candidate shifts is one non-uniform FFT. At D = 10000 and 4097 shifts it takes 4.3 ms against 1.50 s for applying ⋄ once per shift (one core, a shared machine, so the times are rough). It matches the direct sum to a relative error of 2e-12 or better. Any fractional shift costs O(D).
The negative result, and it is the headline. As a way to find an offset, the sweep in vector space loses to doing the same thing on the raw signal. On two windows of a random walk, the best HDC objective at ρ = 1 and D = 16384 fails grossly (more than 10 samples off) in 5 % to 18 % of trials at noise ≤ 0.3, where the Pearson correlation on the raw windows (the objective MASS uses) fails in 0 %. A coarser scale, s = 16, lowers the HDC rate to 0 % to 10 %, but its median error grows to 0.4 to 1.1 samples. No scale brings both down to the raw signal’s level. Looking for a query in a long encoded stream of UCR series, the best HDC setting (MiniROCKET features, the stream stored in blocks) finds a planted copy in 77 % of cases at noise 0.3, MASS in 97 %. Meanwhile HDC stores far more numbers than the raw stream and, in my Python code, is tens to hundreds of times slower per query. With no more memory than the raw stream, HDC hardly finds anything.
Why. Averaged over the random frequencies, the curve is the cross-correlation of the two element sequences, smoothed by the position kernel. Shift search in vector space is a Monte-Carlo estimate, with one random frequency per component, of something you can compute exactly from the raw data. It inherits that objective’s weaknesses and adds noise. For HDC-MiniROCKET features there is a second limit, from Part 1: shifting the vector is not the same as encoding the shifted signal.
One formula
The Sinusoid code encodes position \(t\) as \(\psi(t) = [\sin\theta t;\ \cos\theta t]/\sqrt{D}\), one frequency \(\theta_j = \omega_j \rho\) per component, with \(\omega_j\) drawn uniformly from \((-\pi, \pi)\). Write a sequence vector \(H = [A; B]\) (sine half, cosine half) as \(D\) complex numbers \(z_j = B_j + i A_j = \frac{1}{\sqrt{D}} \sum_t f_{t,j}\, e^{i\theta_j t}\). Shifting by \(\delta\), which is [P3]’s ⋄ with the unscaled shift vector \([\sin\theta\delta;\ \cos\theta\delta]\) (Part 1’s erratum E10 is about that scaling), multiplies each \(z_j\) by \(e^{i\theta_j \delta}\). It is the complex FPE shift in real coordinates. So, for two vectors with the same code,
\[\mathrm{score}(\delta) = \langle \mathrm{shift}(H_a, \delta),\, H_b\rangle = \operatorname{Re}\sum_{j=1}^{D} c_j\, e^{i\theta_j\delta}, \qquad c_j = z^a_j\,\overline{z^b_j}.\]
This closed form is not mine. It is the FHRR similarity with data-dependent weights, and the same expression as eq. (35) of RoFormer (Su et al. 2021), the paper behind rotary position embeddings, which [P3] also connects to its code.
On a uniform grid \(\delta_m = \delta_0 + m h\) this is a type-1 non-uniform DFT, with nodes \(\theta_j h \bmod 2\pi\). Gaussian gridding (Greengard and Lee 2004) does it in O(D·w + M log M) instead of O(D·M), where w = 24 is the width of the spreading stencil in my code. Any single real δ costs O(D), and the derivatives come in closed form, so a bounded 1-D search refines the grid argmax to a fractional shift. Variants A and C have no ⋄; their curve needs a re-encoding per δ.
| D | shifts | NUFFT (ms) | direct sum (ms) | ⋄ once per shift (ms) | re-encode at every shift (s) | NUFFT rel. error |
|---|---|---|---|---|---|---|
| 1024 | 257 | 0.48 | 8.76 | 12.90 | 2.7 | 4e-13 |
| 1024 | 4097 | 1.06 | 134.57 | 227.39 | 40.0 | 2e-12 |
| 10000 | 257 | 4.14 | 72.57 | 99.12 | 30.8 | 8e-13 |
| 10000 | 4097 | 4.34 | 1228.37 | 1504.52 | 409.9 | 4e-13 |
Time for one whole curve, one core, T = 256, on a machine shared with other jobs. The re-encoding column is extrapolated from 33 shifts. The relative error is the largest deviation from the direct sum over the curve, divided by the curve’s largest value. The unit tests also check the fast curve against applying ⋄ once per shift, to 10⁻⁹, for several ρ, step sizes and offsets.
What the curve estimates. Assume the frequencies are drawn independently of the data and both vectors use the same ones. Average over the frequencies with the element vectors \(f_t\) held fixed. With sinc(x) = sin(πx)/(πx), which is what uniform frequencies give,
\[\mathbb{E}\,\mathrm{score}(\delta) = \sum_\tau R_{ab}(\tau)\, \mathrm{sinc}\big(\rho(\delta-\tau)\big),\qquad R_{ab}(\tau) = \frac{1}{D}\sum_t \langle f^a_t, f^b_{t+\tau}\rangle .\]
That is the element-level cross-correlation smoothed by the position kernel: generalised cross-correlation with randomly sampled frequencies. At ρ = 1 and integer δ the sinc vanishes at all other integers, so with scalar elements the expected curve is exactly the ordinary cross-correlation; the curve itself scatters around it. After cosine normalisation the scatter away from the peak is of order √(κ/2D), where κ measures how peaked the spectra are. As a rough check, not recorded in a results file, κ is about 2 for white noise and in the tens (18 to 86 over five walks) for a random walk at ρ = 1 and T = 256. The kernel’s main lobe has its first zeros at ±(T − 1)/s samples, so the expected peak is at least about that wide, and at least as wide as the signals’ own correlation. The derivation is in docs/DESIGN.md, sections 2.4 and 2.5.
This explains the scope. The curve can be no better than the exact cross-correlation of the features, which is cheap to compute when the features are at hand. The sweep is useful only when they are not: when all you kept is the vectors.
Shifting the vector is not shifting the signal
In Part 1 I found that [P3]’s ⋄ is exact for the bundling step, but it does not give the encoding of a time-shifted signal. MiniROCKET’s features near the ends of a series see zero padding, and with dilations up to (T − 1)/8 that zone can be half the series. In Part 1’s test (a peak in a series of length 500, shifted by 10 steps) the shifted vector is closest to the vector of the shifted signal at δ = 0 or 1, not 10, at s = 1, 3 and 7, the classification scales tested. Only at s = 30 does the best δ move to 8.
For shift search this matters more than anything below. Between two HDC-MiniROCKET vectors of separately encoded series, the curve compares feature sequences whose edges differ. At classification scales the edges can dominate, and the peak need not sit at the true shift. So the use I first had in mind, a shift-invariant similarity of whole series for classification, starts out on weak ground, and I have not run it. What is left are settings with less of that problem: pointwise element encoders with no edge effect at all (experiment 1), and MiniROCKET features computed once on a whole stream (experiment 2), where only the query still has its own edges.
Experiment 1: a known offset in a random walk
I take two windows of 256 steps of one random walk. The second is offset from the first by a fractional amount, uniform in ±64 samples (a quarter window either way), both are z-normalised and both get independent noise. I encode them, sweep δ over ±128, and compare the argmax with the truth, 40 trials per setting. Elements are either the value itself (scalar) or random Fourier features of the value (rff). I compare four objectives. The raw HDC curve is what ⋄ gives directly. The normalised HDC curve divides by overlap statistics, each of which is again a shift curve (the trick MASS uses): Pearson over the overlap for scalar elements, the mean element similarity for rff. The other two are objectives on the raw windows: the plain cross-correlation, and the Pearson correlation over the overlap (normalised cross-correlation, NCC).
At ρ = 1 (s = 255) and D = 16384, median |error| in samples / rate of gross errors (more than 10 samples off):
| noise | elements | HDC normalised | HDC raw | raw NCC | raw xcorr |
|---|---|---|---|---|---|
| 0.0 | scalar | 0.08 / 0.15 | 0.25 / 0.25 | 0.07 / 0.00 | 0.31 / 0.25 |
| 0.0 | rff | 0.08 / 0.05 | 0.22 / 0.18 | 0.06 / 0.00 | 0.32 / 0.20 |
| 0.3 | scalar | 0.39 / 0.18 | 0.67 / 0.30 | 0.25 / 0.00 | 0.50 / 0.30 |
| 0.3 | rff | 0.33 / 0.15 | 0.83 / 0.30 | 0.18 / 0.00 | 0.97 / 0.28 |
| 1.0 | scalar | 1.76 / 0.15 | 2.38 / 0.30 | 1.73 / 0.15 | 2.13 / 0.30 |
| 1.0 | rff | 2.11 / 0.05 | 19.53 / 0.58 | 0.95 / 0.03 | 0.97 / 0.13 |
Three things stand out. Without normalisation, the vector sweep and the raw cross-correlation are both grossly wrong in 18 % to 25 % of trials even with no noise: they prefer large overlaps to good matches. That is the objective’s fault, not the vectors’. With normalisation, the median error of the vector sweep comes within 0.01 to 0.15 samples of the raw NCC at noise ≤ 0.3. The tail does not come close. For scalar elements most failures sit at the edge of the search range (|δ̂| of 9, 124, 127, 127, 127, 128, 128 at noise 0.3), where the overlap is smallest and the ratio of noisy Monte-Carlo sums is least stable. For rff elements they sit inside the range (|δ̂| of 2, 7, 7, 21, 26, 34), so small overlap does not explain them. At noise 1 the medians meet for scalar elements, and the rff version is about twice as far off as the raw NCC.
| elements, noise 0.3 | s = 1 | s = 2 | s = 4 | s = 8 | s = 16 | s = 32 | s = 64 | s = 128 | s = 255 | s = 510 |
|---|---|---|---|---|---|---|---|---|---|---|
| scalar | 113.35 / 1.00 | 29.61 / 0.73 | 4.59 / 0.30 | 0.87 / 0.05 | 0.63 / 0.05 | 0.46 / 0.03 | 0.22 / 0.10 | 0.25 / 0.15 | 0.39 / 0.18 | 0.50 / 0.13 |
| rff | 35.10 / 0.78 | 15.60 / 0.58 | 5.54 / 0.35 | 2.61 / 0.15 | 1.04 / 0.08 | 0.67 / 0.03 | 0.39 / 0.13 | 0.28 / 0.13 | 0.33 / 0.15 | 0.60 / 0.15 |
Normalised HDC curve, D = 16384, median |error| / gross-error rate, against s. The kernel’s main lobe reaches ±(T − 1)/s samples, but from s = 4 on the argmax is found to a small fraction of that. At the scales HDC-MiniROCKET uses for classification (s ≤ 7; the grid has 1, 2, 4) the error is several to over a hundred samples and many trials fail grossly. Scalar elements get to about a sample at s = 8, rff at s = 16. The medians keep falling to s ≈ 64 to 128, but the gross-error rate is lowest around s = 16 to 32 and climbs again above that. Past ρ = 1 (s = 510) the medians get worse, which fits aliasing, though I have not tested that explanation.
I had expected the peak width to track the kernel. It does so only roughly at s = 4. For s ≤ 2 the measurement says little: my width measure takes half the height above the curve’s median over the ±128 window, and a lobe that fills most of the window raises that median (s = 1, whose lobe is wider than the window, is left out of the figure). From s = 8 on, the random walk’s own correlation, several dozen samples wide, sets the width. Peak width was the wrong thing to test. The error against s, above, is the useful measure.
Experiment 2: a query in a long stream
Next I concatenated 16 or 64 z-normalised series from a UCR test set (GunPoint, ECG200, CBF, Trace, TwoPatterns, ECG5000) into one stream, encoded it once, and looked for a query by sweeping δ over the whole stream. There are two tasks. A planted copy is one of the stream’s own series plus noise; it counts as found if the top-1 start is within ±m/10 of the truth (m is the series length). For same class the query is a series of one class from the training set, and I score precision@k: of the k best starts, with k the number of stream series of that class, the fraction within ±m/4 of one of them. MASS (stumpy.mass, z-normalised) on the raw stream gets the same stream, the same queries and the same scoring as the HDC row it sits in. Each element type drew its own streams and queries, so the MASS columns differ between rows: by about 3 points in the averages below, and by up to 29 points for a single dataset and stream length (Trace with 16 series). Single cells are noisy. Elements are scalar values with the MASS normalisation built from three shift curves (scalar_mass), value RFFs, or MiniROCKET’s per-step features computed on the whole stream (D = 9996). The stream is stored either as one vector or as blocks of 4m that overlap by m − 1.
| elements | stored as | memory / raw stream | planted, noise 0.3: HDC | MASS | same class: HDC | MASS |
|---|---|---|---|---|---|---|
| scalar_mass | one vector | 19× | 0.35 | 0.97 | 0.48 | 0.59 |
| scalar_mass | blocks of 4m | 152× | 0.64 | 0.97 | 0.56 | 0.59 |
| rff | one vector | 9× | 0.44 | 0.95 | 0.51 | 0.59 |
| rff | blocks of 4m | 76× | 0.71 | 0.95 | 0.57 | 0.59 |
| minirocket | one vector | 6× | 0.47 | 0.97 | 0.50 | 0.62 |
| minirocket | blocks of 4m | 46× | 0.77 | 0.97 | 0.63 | 0.62 |
Means over the six datasets and both stream lengths, ρ = 1, D = 16384 (MiniROCKET: 9996). Memory counts the floats stored for the stream (2D per vector, two banks for scalar_mass) against the stream’s length. Each cell has 14 to 20 queries per task.
This is a clear negative for the planted copy. Even with far more memory than the raw stream, the vector sweep finds the copy less often than MASS. With no more memory than the raw stream (24 configurations at ρ = 1, single vectors with D = 1024 or 4096) it finds it in 10 % of cases at noise 0.3, against 93 % for MASS. So a single vector is no compressed index of the stream at these sizes. Per query, HDC took 0.07 to 1.36 s with blocks (encoding the query and one curve per block, in Python), MASS a median of 3.1 ms.
The MiniROCKET query is featurised on its own, with zero padding at its ends, while the planted window in the stream sees its neighbours. That is the edge effect from above. As a control I also cut the query’s features out of the stream’s own features, at noise 0 only, where that is possible. Then the single-vector hit rate goes from 84 % to 92 %, and with blocks it is 100 % either way. So the edge mismatch costs a little with one vector. The control cannot tell how much of the gap at noise 0.3 and 1 it explains.
My signal-to-noise scale does not predict success: the hit rate rises with D·m/(L ln L), but it scatters by dataset far more than it trends. The sweep works on rough series (CBF, TwoPatterns) and fails on smooth ones (GunPoint, Trace). My guess is that smooth series put their energy at a few frequencies (a large κ), and that competing windows are almost as similar as the copy; one hand check on a GunPoint stream supports the second part, nothing more. Same-class retrieval with blocks is on average close to MASS, and with MiniROCKET features level with it, but not everywhere. On Trace, blocks with scalar or RFF elements are 11 to 17 points behind MASS, and single vectors 21 to 46. These are paired comparisons on the same streams and queries, but with 14 to 20 queries per cell, and MASS itself moving by up to 29 points between draws of the same dataset, gaps of 10 to 20 points in a single cell are suggestive, not established. The vectors seem to carry what happens better than exactly where.
Open questions
- Can the tail of the normalised estimator be fixed (weighting by the overlap, or a narrower search range fixed in advance) so that it matches the raw NCC’s gross-error rate, not just its median?
- Is there any regime where the sweep beats the raw-signal computation: many channels whose raw features are not kept, as the cost argument in
docs/DESIGN.mdsuggests, or vectors that exist anyway? - Does the gross-error rate follow the estimate in
docs/DESIGN.md(section 2.5), which needs D to grow with κ and with the log of the search range, and to shrink with the square of the gap between the true peak and the best wrong one, once κ and that gap are measured per stream? My simpler signal-to-noise scale did not predict it. - Can the MiniROCKET edge effect be removed for whole-series vectors, for example by encoding only the interior, so that a max-over-δ similarity (Rachkovskij and Kleyko’s) becomes meaningful for classification? Until then the classification experiment is not worth running as planned.
- With frequencies on a grid instead of random, the curve is an exact FFT but the kernel becomes periodic. Does that trade help anywhere?
- The prior-art search was short. Compressive time-delay estimation and the spatial semantic pointer literature may already contain the whole-curve trick under another name.
The code, the derivation and all results are in the repository (docs/DESIGN.md, results/). Schlegel, Neubert and the [P3] coauthors get them first.
Generated by Claude on Benjamin Schwerdtner’s behalf.
source: notebooks/finding_the_shift.clj