acceptodds
Under review as a conference paper at ICLR 2027

Superposed Inference for Hyperdimensional Computing

Abstract

Hyperdimensional computing (HDC) is attractive for efficient and robust learning, but conventional inference still encodes every query independently, repeatedly paying the cost of high-dimensional projection. We introduce SupHDC, a new inference paradigm that processes multiple queries through a shared encoding computation. SupHDC assigns lightweight random slot keys, superposes the keyed queries before encoding, and uses slot-specific classifiers to recover their individual predictions. A random-feature kernel view explains why exact recovery of each hypervector is unnecessary: inference only needs to preserve the class evidence that determines the prediction. Across ten datasets, SupHDC achieves 1.39x analytical speedup with no average accuracy loss, and up to 2.08x speedup with only a 2.67 percentage-point mean accuracy loss. On a Raspberry Pi 5, it delivers 2.01x measured wall-clock speedup with a 2.26 percentage-point loss in mean prediction accuracy. SupHDC shows that high-dimensional redundancy can be used not only for robustness, but also as capacity for shared inference.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Hyperdimensional Computing, Vector Symbolic Architectures, Superposition, Edge AI, TinyML, Efficient Inference

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_bVH7OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes SupHDC, which combines several inputs using random permutation and sign keys, applies one shared random feature encoder, and produces separate predictions with slot specific prototype classifiers. It adapts these classifiers to mixed inputs and individually recomputes predictions with small score margins. A kernel analysis explains how predictions can survive interference without recovering each input's encoded vector. Experiments on ten classification datasets and a Raspberry Pi report inference savings with an accuracy tradeoff against Plain HDC at the same representation dimension.

Critical strengths

SupHDC offers a simple way to share the expensive projection in HDC while keeping the encoder fixed. The kernel analysis usefully separates common score scaling from distortion that changes the ordering of class scores, and explains why exact recovery of each encoded input is unnecessary.

The experiments use five paired seeds across ten datasets and include ablations of adaptation and fallback. Table 2 also tests actual runtime against batched Plain HDC on the same query blocks, reporting 2.01x speedup with a 2.26 percentage point mean accuracy loss at K=4 with fallback.

Critical weaknesses

The practical advantage over simply reducing the representation dimension remains unclear. Averaging the supplied full precision summaries gives Plain HDC at D=2,000 an accuracy of 84.37%, compared with 81.71% for D=10,000 SupHDC at K=4 with adaptation and fallback. The smaller Plain model has higher mean accuracy on all ten datasets. Its analytical speedup relative to Plain at D=10,000 is 5x, compared with 2.08x for SupHDC; these are cost estimates, not measured hardware speedups. The reported savings at fixed D are valid, but retaining a large D needs a demonstrated benefit. The supplement includes a robustness experiment script, but I could not find its results.

The diagnostic in Figure 4 needs clarification. Eq.6 uses a query dependent kernel scaling factor, and Eq.12 normalizes the residual by the scaled clean scores. The supplied run_interference_grid.py instead fits one global scaling factor and divides by the magnitude of the unscaled clean scores. This difference matters when scaling is small. The script may be an intermediate step, but the supplied materials do not establish how its output becomes the quantity plotted in Figure 4, limiting the empirical support for the proposed explanation.

Questions for authors

Do the existing results from the supplied robustness experiment show a benefit of retaining D=10,000 over lower-D Plain models that offsets the accuracy and cost comparison above?

Which scaling factor and normalization were used for Figure 4? Was there additional analysis after the supplied interference script to obtain Eq.12?

1 comment

We thank the reviewer for the encouraging review. We provide point-by-point clarifications below:

W1. Practical advantage over reducing the representation dimension.

SupHDC provides additional computational savings even after reducing D. Please see the following comparison across ten datasets and five seeds:

ConfigurationMean accuracyAnalytical speedup relative to Plain D=10,000
Plain, D=10,00084.39%1.00×
Plain, D=2,00084.37%5.00×
Plain, D=5,00084.45%2.00×
SupHDC, D=10,000, K=4 + fallback81.71%2.08×
SupHDC, D=2,000, K=2 + fallback84.41%6.93×

Starting from the reviewer’s suggested D=2,000 baseline, SupHDC reduces analytical computation by a further 27.84%, with similar mean accuracy. This demonstrates that superposition can complement dimension reduction and supports selecting D and K jointly.

We will add those direct comparisons and clarify the practical operating points.

W2. Figure 4 scaling and normalization.

Our figure 4 does include the scale normalization: the plotting notebook applies R_int = epsilon_rel_l2 / rho after the supplied interference script.

We also added diagnostics using the theoretical scale directly. At D=10,000 before adaptation, relative distortion is 0.057 at K=2 and 0.103 at K=4. Thus, the superposed scores remain close to the theoretically scaled clean scores, while sharing an encoding across more inputs increases interference. This supports the proposed explanation without fitting the scale to the observed scores. Small distortion can still change predictions with narrow class margins.

Q1. Do the robustness results demonstrate a benefit from retaining D=10,000?

Yes, at moderate superposition: HAR and ISOLET show that high-D SupHDC can preserve robust accuracy while reducing computation relative to high-D Plain HDC.

With 40% random-phase corruption of encoded coordinates, averaged over five model seeds and three corruption realizations:

DatasetPlain D=2,000Plain D=5,000Plain D=10,000SupHDC D=10,000, K=2 + fallback
HAR91.50%92.56%92.89%93.28%
ISOLET92.48%93.27%93.50%93.89%

SupHDC exceeds Plain D=2,000 by 1.78 pp on HAR and 1.41 pp on ISOLET, with improvements in all five model seeds. It also exceeds Plain D=5,000 and D=10,000, while requiring 28.81% and 25.94% less analytical computation than Plain D=10,000, respectively. The mean accuracy advantage on these two datasets persists across all tested nonzero corruption levels.

These results demonstrate useful operating points where retaining the larger representation with moderate superposition provides robust accuracy that the tested lower-D Plain models do not match. Lower-D Plain remains cheaper, so the benefit is an accuracy–cost tradeoff.

Q2. Which scaling factor and normalization were used for Figure 4? Was there additional analysis?

Yes. Figure 4(b,c) uses the same clean prototypes on both sides, before adaptation. For each (dataset, D, K, seed) configuration, the interference script fits one global least-squares scale across the collected score entries:

ρ^=⟨s,s~⟩/∣s∣22\widehat\rho = \langle s,\widetilde{s}\rangle / \\|s\\|_2^2.

The plotting notebook then applies:

raw["R_int"] = raw["epsilon_rel_l2"] / raw["rho"].replace(0, np.nan)

Thus, the plotted quantity includes the additional scale normalization, which is appropriate for this analysis.

Reviewer_AHEdOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper targets the high-dimensional encoding step, the main bottleneck of HDC inference, and revisits the basic HDC operations of binding and bundling from a superposition perspective. To reduce the number of encodings, it binds KK inputs with slot-specific random keys (signed permutations) and bundles them in the original input space before encoding, so that a single encoding is shared across all KK queries. Each query is then classified by slot-specific prototypes, which are further adapted on superposed inputs, and a margin-based selective fallback re-encodes low-confidence predictions to mitigate superposition interference. Theoretically, the paper views RFF-HDC as an approximate kernel machine, decomposes the superposed score into a common scaling term ρk\rho_k and a class-dependent distortion ϵk,c\epsilon_{k,c}, shows that random keys suppress cross-slot alignment at the scale of (K−1)/d\sqrt{(K-1)/d}, and gives a margin-based condition for prediction preservation. Experiments on ten datasets report both FLOP-based analytical speedups and measured wall-clock speedups on a Raspberry Pi 5, demonstrating practical acceleration, and show that the method can be combined with orthogonal efficiency techniques such as quantization.

Critical strengths

The main strengths of this paper lie in its approach and its empirical results. In particular, I appreciate the reinterpretation of superposition through binding and bundling applied at the input stage, before the high-dimensional encoding. The motivation is clear, and applying superposition as a means to reduce the number of encodings is a reasonable and well-targeted design choice. The experiments across ten datasets, together with both FLOP-based analysis and wall-clock measurements on a Raspberry Pi 5, provide concrete support for the claimed efficiency benefits. Finally, the method is orthogonal to existing inference acceleration techniques such as quantization and can be used in combination with them.

Critical weaknesses
  • Theoretical weakness : The analysis in Section 5 covers only the setting before prototype adaptation, whereas the main experimental results report performance after adaptation. Eq. (4) trains the prototypes Pk,cP_{k,c} by adding and subtracting zmixz_{\text{mix}}, and the resulting terms carry a scaling factor κ(vk−v(t))\kappa(v_k - v^{(t)}) that differs across training groups, so they cannot be factored into a single common scale ρk\rho_k. Therefore, the decomposition in Eq. (6) and Propositions 1 and 2 do not directly apply to the adapted model, and the theory does not explain the reported performance. In addition, Proposition 1 fixes the inputs and takes the expectation over random keys. In practice, however, the keys are sampled once and reused for all queries, so the relevant quantity is the interference under a single fixed key across the input distribution. Guaranteeing this would require additional assumptions on the input distribution for a fixed key, which the paper does not address.

  • Experimental weakness : Proposition 1 predicts that cross-slot interference decreases as 1/d1/\sqrt{d}, but the per-dataset results in Fig. 9 do not follow this trend at large KK. Datasets with large dd such as MNIST (d=784d=784), ISOLET (d=617d=617), and HAR (d=561d=561) degrade most severely, while Airline Sentiment (d=64d=64) remains relatively robust. Moreover, the condition of Proposition 2, 2∥ϵk∥∞<ρkγk2\|\epsilon_k\|_\infty < \rho_k \gamma_k, is never measured on real data. With ℓ2\ell_2 normalized inputs and σ=1\sigma = 1, kernel values lie in a narrow range, and ρk\rho_k shrinks as KK grows, so the scaled margin ρkγk\rho_k \gamma_k may be small on datasets such as MNIST, yet this is not verified empirically. Finally, the practical benefit is limited for a method framed as a new inference paradigm. With adaptation alone, the speedup is large but the mean accuracy drops by 4 to 7 pp at K=3K=3 and K=4K=4 (Table 1), and with fallback the loss is reduced but the speedup falls to at most about 2×2\times, which confines the useful operating range to K=2K=2 to 44.

Questions for authors
  1. Can the analysis in Section 5 be extended to the adapted prototypes? Alternatively, can the authors empirically show whether the decomposition s~k,c≈ρksk,c+ϵk,c\tilde{s}_{k,c} \approx \rho_k s_{k,c} + \epsilon_{k,c} still approximately holds after adaptation?

  2. Are Fig. 4(b) and 4(c) computed with or without adaptation? If with adaptation, how is ρ\rho obtained when computing RintR_{\text{int}}?

  3. Can the authors report per-dataset results without adaptation, so that the dd dependence predicted by Proposition 1 can be checked directly against Fig. 9?

  4. Can the authors report the empirical distributions of γk\gamma_k, ρk\rho_k, and ∥ϵk∥∞\|\epsilon_k\|_\infty, and the fraction of queries satisfying the condition of Proposition 2?

3 comments
AuthorsOpenReview ↗

We've add new experiments and extended theory to adopted prototypes

We thank the reviewer for the constructive comments. Please see our point-by-point response below:

W1 — We improve the theory considering prototype adaptation and fixed keys

**Updated theory considering adapted prototypes: ** The reviewer’s concern is that different training mixtures introduce different scaling factors. Our extension keeps each factor separately. Adaptation changes the learned weights, but the classifier remains a weighted combination of kernel similarities:

s~k,cA=∑tbk,c,tκ(δk,t)κ(vk−vt,k)+ϵk,cA.\widetilde s^A_{k,c}=\sum_t b_{k,c,t}\kappa(\delta_{k,t})\kappa(v_k-v_{t,k})+\epsilon^A_{k,c}.

Here, bk,c,tb_{k,c,t} includes the prototype updates and normalization, δk,t=Ak(xk−xt,k)\delta_{k,t}=A_k(x_k-x_{t,k}) is the target-input difference, and vk,vt,kv_k,v_{t,k} are the test and training companion contributions. The residual includes the interaction and finite-feature errors.

Each training mixture retains its own factor κ(vk−vt,k)\kappa(v_k-v_{t,k}); no common scale is assumed. Random-key geometry controls the cross-slot interaction, while the learned weights determine its effect on the scores. If the weighted sum has a unique winner with margin ΓkA\Gamma^A_k, then 2∣ϵkA∣∞<ΓkA2\\|\epsilon^A_k\\|_\infty < \Gamma^A_k preserves that winner.

Intuitively, the extension asks whether interference is small relative to the separation achieved by the adapted classifier.

Our new ablations across ten datasets and five seeds show:

KKBefore adaptationAfter adaptation
273.76%83.30%
466.16%77.40%

Adaptation recovers 9.55–11.24 percentage points, showing that training on combined inputs substantially improves classification. These results establish adaptation’s benefit and the theory extension covers the resulting classifier.

Updated analysis under fixed keys: The geometric identity also gives a conservative guarantee for a bank sampled once and reused. Let Gk(A)=E[(δk⊤wk)2∣A]G_k(A)=\mathbb E[(\delta_k^{\top}w_k)^2\mid A], where the expectation is over a distribution of test–training input tuples independent of the key draw.

If all original inputs have norm at most one, each difference has norm at most two. Therefore, for any η∈(0,1)\eta\in(0,1):

Pr⁡A[Gk(A)≤16(K−1)dη]≥1−η.\Pr_A\left[G_k(A)\le\frac{16(K-1)}{d\eta}\right]\ge1-\eta.

For the original clean-support setting, where the training companions are zero, the numerator improves to 4(K−1)4(K-1). This is a guarantee on average geometric interference for a reused bank, rather than a uniform guarantee for every query. The learned coefficients enter separately through the deterministic score-error bound above.

We additionally evaluated the original alignment quantity separately for 20 key banks per dataset–KK setting. Across settings, the bank-averaged measured-to-predicted alignment-second-moment ratio averaged 0.996, with a mean absolute deviation from one of 3.28%.

DatasetMeasured/predicted ratio, mean ± SD across banks
HAR0.988 ± 0.134
ISOLET1.003 ± 0.036
MNIST0.985 ± 0.035
Airline Sentiment0.947 ± 0.105
IMDB1.114 ± 0.455

These measurements directly examine interference under reused keys and quantify its dataset-dependent variability.

W2 — Experimental Improvements

At large KK, the measured alignment follows Proposition 1, the proposition predicts normalized cross-slot alignment. At K=6K=6, the Fig. 4(a) measurements for the four datasets identified by the reviewer are:

DatasetInput dimensionPredicted alignmentMeasured alignment
Airline Sentiment640.27950.2847
HAR5610.09440.0948
ISOLET6170.09000.0899
MNIST7840.07990.0794

Thus, the higher-dimensional datasets do exhibit smaller alignment, as predicted. Their final accuracy also depends on class margins and adaptation. In our new K=6K=6 ablations, adaptation improves Airline Sentiment by 18.11 pp, compared with 4.77 pp for MNIST. This difference helps explain why Airline remains more robust after adaptation despite having larger geometric interference.

The practical contribution is acceleration within the useful K=2K=2–44 range. With adaptation and fallback, we have a significant efficiency over those operating points:

SettingSpeedupMean accuracy change
K=2K=2, analytical1.39×+0.37 pp
K=3K=3, analytical1.78×−1.16 pp
K=4K=4, analytical2.08×−2.67 pp
K=4K=4, Raspberry Pi 52.01× measured−2.26 pp

We agree that moderate KK is the demonstrated practical regime and will state this explicitly. Within that regime, SupHDC provides up to approximately 2x measured acceleration.

Q1 — Can the analysis be extended to adapted prototypes?

Yes. We extended the theory retaining the separate attenuation factor associated with each training mixture. Because prototype updates add or subtract encoded mixtures, the final adapted classifier remains a weighted kernel classifier:

s~k,cA=∑tbk,c,tκ(δk,t)κ(vk−vt,k)+ϵk,cA.\widetilde s^A_{k,c}=\sum_t b_{k,c,t}\kappa(\delta_{k,t})\kappa(v_k-v_{t,k})+\epsilon^A_{k,c}.

Each training mixture retains its own factor κ(vk−vt,k)\kappa(v_k-v_{t,k}), so the analysis does not require a common scale across training groups. The residual and margin conditions are stated in our response to W1.

The new ablations also establish adaptation’s practical benefit. Across ten datasets and five seeds, at D=10,000 without fallback:

KBefore adaptationAfter adaptationImprovement
273.76%83.30%+9.55 pp
466.16%77.40%+11.24 pp

These results demonstrate that adaptation improves classification on superposed inputs.

Q2 — Are Fig. 4(b,c) computed with adaptation, and how is the scale obtained?

They are computed without adaptation. Both clean and superposed inputs are scored using the same clean slot prototypes which is the appropriate way for study analytical distortion and accuracy. We will make that clear in the revision.

Q3 — Can you report per-dataset results without adaptation?

Yes. Below are test accuracies without adaptation or fallback, averaged over five seeds at D=10000D=10000:

DatasetPlainK=2K=2K=3K=3K=4K=4K=6K=6
HAR93.3689.2684.9380.5668.67
ISOLET93.6691.7888.9586.0768.01
CIFAR-1090.5687.6184.0877.8053.30
Airline Sentiment88.0562.1959.4160.6058.17
AG News86.9064.2252.5548.6139.53
IMDB82.2660.0858.7257.6353.35
20 Newsgroups37.5820.6814.9313.889.11
SECOM93.2591.7887.9684.2072.17
MNIST93.6891.7289.4485.3265.08
Fashion-MNIST85.5678.2672.7766.9549.55

The results here still show SupHDC to be broadly useful at moderate K even without prototype adaptation. The results here also show that the level of improvement after adaptation cannot be attributed to input dimension alone. The direct alignment measurements testing Proposition 1 are reported in W2.

Q4 — Fraction satisfying Proposition 2?

We measured a tighter pairwise refinement of Proposition 2. The refinement instead compares each change in a class-score gap against that gap’s original size. It therefore removes common score shifts and accounts for differences between competitors.

Let a be the clean classifier’s winning class. The refined sufficient condition is:

∣ϵa−ϵc∣<ρ(sa−sc)|\epsilon_a-\epsilon_c| < \rho(s_a-s_c) for every competing class c≠ac\ne a.

If this condition holds, the superposed classifier preserves the clean prediction. The table compares the fraction satisfying this condition with actual prediction agreement, averaged over ten datasets and five seeds:

KPairwise coverage before adaptationActual agreement before adaptationPairwise coverage after adaptationActual agreement after adaptation
262.99%79.36%68.32%84.75%
354.82%73.28%61.75%81.53%
447.72%68.83%55.05%78.57%
627.07%54.94%35.73%69.89%

These results show that the refined condition is informative in the practical K=2–4 range, certifying prediction preservation for 55.05%–68.32% of queries after adaptation. Both coverage and actual agreement improve after adaptation on average, demonstrating that the condition remains useful for the adapted classifier. For MNIST at K=4, coverage reaches 86.92%, close to the observed 89.67% agreement, directly addressing the reviewer’s concern about this dataset.

Reviewer_AHEdOpenReview ↗

Official Comment by AHEd

I thank the authors for the detailed response.

The extended condition for the adapted classifier only states that the winner is preserved when the error is smaller than half the margin, which holds for any classifier and does not show that superposition interference is actually small.

In Q4, the authors measure a refined pairwise condition rather than the original condition of Proposition 2, and they do not report the distributions of γk\gamma_k, ρk\rho_k, and ∣ϵk∣∞|\epsilon_k|_\infty. In addition, the W1 response states that the adapted model has no common scale, yet the Q4 response computes a ρ\rho-based condition after adaptation, so it is unclear how ρ\rho is defined in that setting.

Finally, the accuracy gains from adaptation show that adaptation is effective but do not validate the theory. Since the authors attribute the per-dataset differences to margins and adaptation, my concern that the theory does not explain the reported performance remains.

Reviewer_j1DvOpenReview ↗
Rating
1(−1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
1(−1)
Read review
Paper summary

The paper proposes SupHDC, an inference-time method for projection-based (random Fourier feature) HDC classifiers that lets several queries share the expensive projection from the input dimension to the hypervector dimension. Each query is first multiplied by a fixed random signed permutation "slot key", the keyed inputs are summed in input space, and the sum is encoded once with the frozen complex RFF encoder. Each slot has its own prototype bank, built by re-encoding the training set under that slot's key and reusing the base model's sample weights (Eq. 3). Interference is controlled in two ways. First, the slot prototypes are adapted on mixed training groups with the usual perceptron-style HDC update (Eq. 4). Second, a margin-gated fallback re-encodes, without superposition, the fraction of predictions in each batch that have the smallest margins. Section 5 gives a kernel-level interpretation. The superposed score decomposes into a class-independent scale, which is the kernel evaluated at the interference coming from the other slots, and a class-dependent residual (Eq. 6). For the RBF kernel, the residual is governed by a cross-slot alignment term between the query-prototype difference and the interference vector (Eqs. 7, 10). Random keys make this alignment zero-mean, with a variance that shrinks in inverse proportion to the input dimension (Prop. 1), and a margin condition guarantees that the prediction does not change (Prop. 2). On ten datasets at a hypervector dimension of 10,000, adaptation plus 20% fallback gives a 1.39× analytical speedup with no average accuracy loss with two superposed queries, and a 2.08× speedup with a 2.67 pp accuracy loss with four. A single-threaded Raspberry Pi 5 implementation measures a 2.01× speedup with a 2.26 pp accuracy loss.

Critical strengths
  1. The idea is simple, easy to deploy, and aimed at a real bottleneck. The trained encoder projection is left unchanged. The method only adds sign flips, permutations and sums whose cost grows linearly with the number of queries and the input dimension, plus one prototype bank per slot, so the storage overhead is moderate (1.04× to 1.29× of Plain, Table 6 and Fig. 12). Superposing before the nonlinear encoder, instead of bundling hypervectors after encoding, is a natural way to share the projection, and the profiling in Fig. 1 motivates it.
  2. The kernel-level decomposition is useful. Eq. 6 separates a common positive scale, which cannot change the argmax, from the class-dependent distortion. Together with Prop. 2, this explains why exact recovery of each hypervector is not needed. The closed form of the RBF residual in Eq. 7 is exact. I checked the proofs in App. B.1-B.4: Eq. 25, the claim that the transpose of one key multiplied by another key is still a uniform signed permutation, the vanishing of the cross terms when one slot uses the identity key, and the margin argument in Eq. 35 all look correct to me.
  3. The experimental protocol is careful. Comparisons are paired, reusing the same base model, projection and test order across different numbers of superposed queries (App. C.3, D.2). There are five random seeds and ten datasets, and the SEM is computed over dataset-level means. The sweeps cover two to ten superposed queries, hypervector dimensions of 1K, 2K, 5K and 10K, and five numerical precisions (Figs. 5-8, Fig. 3b). The ablation of the fallback gate in Fig. 11a is informative: with a fallback fraction of 0.2, lowest-margin selection catches 67% (two queries) and 54% (four queries) of the errors, compared with 20% for random selection.
  4. The analytical compute savings carry over to real hardware. The Raspberry Pi 5 experiments (Table 2, Fig. 13, App. C.4) rotate the execution order of the methods, control for thermal drift, and report median latency over 30 repetitions. Without fallback, the measured speedup is close to the FLOP model (3.36× vs. 3.45× with four queries).
Critical weaknesses
  1. The most important baseline is missing: compute-matched Plain HDC, that is, Plain HDC with a smaller hypervector dimension. Because the queries share one encoding, each query effectively gets the projection budget divided by the number of queries. The obvious competitor at equal FLOPs is Plain RFF-HDC with a hypervector dimension reduced by the superposition factor, or more precisely, with the dimension at which the two pipelines have the same total cost per group of queries. The paper states that reducing the dimension and increasing the number of superposed queries "are not equivalent operations" (Sec. 6, Complementary Efficiency Knobs), but it only reports the change of SupHDC relative to Plain at the same dimension (Fig. 3a, Fig. 7) and never gives the accuracy of Plain itself at dimensions of 2,000, 2,500 or 5,000. For L2-normalized inputs with dimensions between 64 and 2048, RFF classifiers often saturate in accuracy well below a dimension of 10,000. If Plain at 5,000 (roughly 2× cheaper) loses less than 2.67 pp, or Plain at 2,500 (roughly 4× cheaper) loses less than the 7.11 pp of adapted SupHDC without fallback at four queries (3.58×, Table 1), then simply shrinking the dimension beats SupHDC. The results needed for this are already available. Please report Plain accuracy as a function of dimension, and put both methods on the same accuracy vs. FLOPs plot, per dataset and on average.
  2. The main motivation, keeping a large dimension for robustness, is never tested. Sections 1 and 3 argue for SupHDC on the grounds that a smaller dimension "removes the redundancy" that makes HDC attractive, namely robustness to noise and hardware defects. Yet the paper has no robustness experiment at all. Superposition may well use up exactly the margin and redundancy that robustness relies on (Prop. 2 is itself a margin argument). I would like to see SupHDC and smaller-dimension Plain evaluated under bit flips, additive noise on hypervectors or prototypes, or analog-style noise. If SupHDC at a dimension of 10K turns out to be more robust than compute-matched Plain, the motivation would hold.
  3. The theory covers direct superposition, but all headline results use adaptation and fallback, and one factor is underestimated. Section 5 analyzes the model "before prototype adaptation", while Tables 1 and 2 report only adapted variants. More importantly, the analysis treats the common scale as harmless (App. B.4 says that a common scaling alone preserves the class ranking). With L2-normalized inputs and a kernel bandwidth of 1 (Table 4), the squared norm of the interference is about the number of queries minus one, so the common scale factor shrinks exponentially with the number of superposed queries, to about 0.22 at four queries and about 0.01 at ten. The finite-dimension RFF error in Eq. 11 only decays with the inverse square root of the hypervector dimension and is not multiplied by the common scale. The effective condition is therefore roughly that twice the worst-case sum of the superposition error and the RFF error must stay below the common scale times the margin, and the signal-to-noise ratio decays exponentially in the number of queries. I think this explains the dependence on dimension and the collapse at large numbers of queries in Fig. 3a and Fig. 7 better than the key-separation term, which scales with the inverse square root of the input dimension. In addition, Prop. 1 is a pairwise Markov bound over the keys that is never combined with a union bound or a sum over training samples, so there is no end-to-end sufficient condition and the theory stays qualitative. Please spell out how the common scale interacts with the RFF error, discuss the role of the kernel bandwidth, and ideally give a combined bound on the worst-case per-slot error.
  4. The empirical support for the theory is weaker than presented. Fig. 4a shows that the RMS of the cross-slot alignment matches the predicted value (the square root of the number of queries minus one over the input dimension), with a ratio of 1.001. Given Eq. 25, this is only a Monte Carlo check of a mathematical identity and says very little about classification performance. The correlation of 0.99 between the interference ratio and the accuracy loss in Fig. 4c is computed over a set of (dimension, number of queries) points along which both quantities are monotone, so a high correlation is to be expected. It is also unclear how the scale is obtained for the adapted classifier, where Eq. 6 no longer holds. Finally, the per-dataset results in Fig. 9 do not fit the input-dimension explanation. Airline Sentiment has the smallest input dimension (64) and should therefore have the strongest cross-slot alignment, yet the paper reports that its performance degrades gradually, while ISOLET (input dimension 617), HAR (561) and MNIST/Fashion-MNIST (784) are the most sensitive. Please define how the scale in Eq. 12 is estimated, report the correlation across datasets, at a fixed number of queries, between the interference ratio (or prediction interference) and the accuracy change, and discuss the role of input dimension relative to margins and class structure.
  5. The accuracy comparison has confounds. (a) The base model is trained for 20 epochs, while SupHDC adds another 100 epochs of adaptation (Table 4). The fallback also uses the reconstructed clean keyed prototype banks rather than the base model. The +0.37 pp gain with two queries could come partly from the extra training or from an ensemble-like effect rather than from lossless superposition. A Plain model trained for 120 epochs is needed, and the authors should check whether the clean keyed prototype banks reproduce Plain accuracy. (b) The kernel bandwidth is fixed at 1 for all datasets, so the Plain baseline may be untuned, and the tradeoff between the number of queries and the bandwidth is not explored. (c) SECOM is highly class-imbalanced, so accuracy differences on it say little; please report balanced accuracy or F1 for this dataset.
  6. The end-to-end efficiency claims go beyond the evidence, and deployment constraints are not discussed. For CIFAR-10 (ResNet-50 features) and the four text datasets (Word2Vec with positional encoding and pooling), feature extraction will dominate end-to-end latency, so the statement in Fig. 1 that encoding dominates inference latency only holds for the HDC stage. SupHDC also requires all queries in a group to be available at once, which adds latency in streaming TinyML settings. The fallback selects the lowest-margin predictions, a fixed fraction of each batch of 1,024 groups (rounded up), so the prediction for one query depends on the other queries in the same batch, and this selection rule cannot be used on a single stream. Please report end-to-end latency including feature extraction, and evaluate a fixed margin threshold calibrated on a validation set.
  7. The positioning relative to prior work and other efficiency options is incomplete. Superposing keyed inputs and separating them with slot-specific output heads is the core idea of DataMUX and MIMONets. MIMONets already uses VSA binding and unbinding and comes from the HDC community; the paper cites it but does not compare against it. The paper also misses a structural observation. For FHRR/FPE encoders, the complex exponential of the projected sum of keyed inputs equals the elementwise product of the complex exponentials of the individually projected keyed inputs. So input-space superposition is exactly the binding (elementwise product) of the keyed hypervectors, and it is also equivalent to a structured random feature map applied to the concatenated inputs, whose blocks are the projection composed with each key. This connects SupHDC to standard VSA operations such as fractional power encoding (Frady et al.) and spatial semantic pointers (Komer & Eliasmith), and it should be discussed. On the efficiency side, the paper cites Yu et al. (2016) but uses dense ORF. Structured random features (SORF, Fastfood) reduce the encoding cost from linear to logarithmic in the input dimension, which can give more than a 2× speedup at little accuracy cost, and they could be combined with SupHDC. Please compare against structured projections or combine them with SupHDC, and clarify the contribution relative to MIMONets and FPE binding.
Questions for authors
  1. Averaged over the ten datasets, what is the absolute accuracy of Plain RFF-HDC at dimensions of 2,000, 2,500 and 5,000, and how does it compare with 10,000? On the same accuracy vs. analytical FLOPs curve, where does SupHDC + Adapt. + FB with two, three and four queries sit relative to Plain?
  2. Does a Plain model trained for 120 epochs (the base training plus the adaptation budget) close the +0.37 pp gap at two queries? For the second slot onward, does fallback with the clean keyed prototype banks reproduce Plain accuracy exactly, or does it differ because of finite-dimension effects?
  3. In Eq. 12, how is the scale computed for the adapted classifier, where the decomposition of Eq. 6 no longer applies? Is it the analytic kernel value at the interference vector, or a least-squares fit between the superposed and clean scores?
  4. How does performance depend on the kernel bandwidth? Since the common scale decays as a Gaussian in the interference norm relative to the bandwidth, I would expect a larger bandwidth to tolerate more queries at some cost in clean accuracy. Was the bandwidth of 1 tuned for Plain or for SupHDC?
  5. Fig. 9 shows that Airline (input dimension 64) tolerates superposition better than MNIST or ISOLET, which contradicts the inverse-square-root dependence on input dimension predicted by Prop. 1. How do you explain this? Would the distribution of clean margins be a better predictor of per-dataset sensitivity?
6 comments
AuthorsOpenReview ↗

We've added new experiments and clarifications to theory interpretation

We want to thank the reviewer for the detailed comments, please see blow the new experiments show casing the border advantage of SupHDC and clarifications:

W1. Comparison with smaller-dimensional, compute-matched Plain HDC.

Our additional comparisons show that SupHDC can provide better accuracy at the same cost even when compared with reduced dimension baseline.

We matched Plain’s dimension to the cost of SupHDC at D=10000, K=2, with adaptation and 20% fallback.

DatasetMatched Plain dimensionPlain: 20 epochsPlain: 120 epochsSupHDC
HAR7,10993.15%92.60%93.79%
ISOLET7,39493.71%93.59%94.23%

The analytical costs differ by less than 0.01%. SupHDC outperforms both Plain controls on both datasets at matched cost.

Superposition also provides savings after dimension reduction. Across our existing ten-dataset, five-seed evaluation, Plain at D=2,000 achieves 83.37% mean accuracy. Applying SupHDC at that same dimension with K=2, adaptation, and fallback achieves 84.41%, while reducing analytical computation by a further 27.84%.

Thus, reducing dimension is effective, but it does not make superposition redundant. The results support selecting D and K jointly.

W2. Robustness at matched computation.

We have now directly evaluated SupHDC against compute-matched, smaller-dimensional Plain under hypervector corruption (directly test robustness). The experiment replaces encoded coordinates with random number at the specified corruption rate, including coordinates recomputed during fallback.

SupHDC uses D=10,000, K=2, adaptation, and 20% fallback. Plain uses D=7,109 for HAR and D=7,394 for ISOLET, matching analytical inference cost within 0.01%.

DatasetCorruptionPlain: 20 epochsPlain: 120 epochsSupHDC
HAR20%93.15%92.40%93.48%
HAR40%92.40%91.69%92.98%
ISOLET20%93.71%93.91%94.10%
ISOLET40%93.26%93.46%93.52%

SupHDC maintains higher accuracy than both Plain controls at every tested corruption level, without requiring a larger inference budget. These results establish useful operating points where retaining the larger representation with moderate superposition provides better accuracy under corruption.

W3. Adaptation, shrinking scale, and finite-dimensional error.

The original was meant to explain why and how inference under superposition works. We hereby extend our theory and analysis to cover interaction between these terms and the practical algorithm.

Account for the shrinking margin: Before adaptation, prediction is preserved if:

2(∥ϵksup∥∞+∥ϵkRFF∥∞)<ρkγk.2(\|\epsilon_k^{\mathrm{sup}}\|_\infty+\|\epsilon_k^{\mathrm{RFF}}\|_\infty)<\rho_k\gamma_k.

The left-hand side combines interference from other queries and finite-feature approximation error. The right-hand side is the clean classification margin after scaling. Both errors must fit within this remaining margin.

For approximately orthogonal, unit-norm inputs, ρk≈exp⁡(−(K−1)/(2σ2))\rho_k\approx\exp(-(K-1)/(2\sigma^2)). Therefore, increasing K can rapidly shrink the available margin. Increasing D reduces finite-feature error. Increasing bandwidth slows the scale decay but also changes class separation. This clarifies the relationship between key quantities.

**Include the actual adapted prototypes: ** Adaptation updates prototypes using mixed training examples. Each final prototype is therefore a weighted sum of clean and mixed training features, with weights bk,c,tb_{k,c,t} that include prototype normalization.

For a test–training pair, let δk,t\delta_{k,t} be the difference between their desired-slot inputs, and let wk,tw_{k,t} be the difference between their interference vectors. We define the reference score:

gk,cA=∑tbk,c,tκ(δk,t)κ(wk,t).g^A_{k,c}=\sum_t b_{k,c,t}\kappa(\delta_{k,t})\kappa(w_{k,t}).

This score separates desired-slot similarity from interference similarity. The actual adapted score is:

s~k,cA=gk,cA+rk,cA+ek,cD.\widetilde{s}^A_{k,c}=g^A_{k,c}+r^A_{k,c}+e^D_{k,c}.

Here, rAr^A measures the interaction that remains after this separation, and eDe^D is finite-feature error. Thus, the extension explicitly covers adapted prototypes. Its prediction guarantee is relative to gAg^A; agreement with the original clean classifier is measured separately.

Combine the errors into one sufficient condition:

If we define:

  • Bk=max⁡c∑t∣bk,c,t∣B_k=\max_c\sum_t|b_{k,c,t}|: how strongly the prototype weights can amplify errors.
  • RkR_k: a bound on the structural kernel residual over the relevant test–training pairs.
  • ξD\xi_D: a bound on their finite-feature approximation errors.

Then:

∥s~kA−gkA∥∞≤Bk(Rk+ξD).\|\widetilde{s}^A_k-g^A_k\|_\infty\le B_k(R_k+\xi_D).

Let γkA\gamma_k^A be the gap between the largest and second-largest reference scores. The adapted prediction matches the reference prediction whenever:

2Bk(Rk+ξD)<γkA.2B_k(R_k+\xi_D)<\gamma_k^A.

The resulting theory is precise. Prediction is preserved when the combined error is smaller than the available margin. The analysis includes adaptation and explains why increasing D can help, while also identifying the limitation caused by large K.

W4. Empirical support for the theory.

The distortion–accuracy relationship remains when D and K are fixed. At D=10,000, the cross-dataset correlations are:

KCorrelation between relative distortion and accuracy loss
20.791
30.854
40.900

These use ten datasets, five-seed averages, and the theoretical per-query scale, before adaptation. Thus, the relationship is not solely a consequence of varying D or K.

Figure 4 panel (a) checks the random-key mechanism and it is not direct evidence of classification accuracy. Panels (b,c) use clean prototypes before adaptation and a fitted global scale. The plotting notebook includes the additional scale normalization. We will clarify this.

We also want to clarify that Input dimension alone does not predict accuracy loss. Proposition 1 concerns cross-slot alignment, while prediction changes depend on whether the resulting distortion exceeds the class-score margin. Smaller input dimension therefore does not necessarily imply worse classification performance. Airline Sentiment’s behavior does not contradict the proposition.

W5. Training budget, bandwidth, and class imbalance.

Longer Plain training does not explain the SupHDC gain over the baselines. Using the original training splits, D=10,000 and σ=1:

DatasetPlain: 20 epochsPlain: 120 epochsSupHDC: 20 + 100 adaptation epochs
HAR93.42%93.11%93.82%
ISOLET93.52%93.65%94.03%

These one-seed controls show that SupHDC’s advantage persists after extending Plain training.

“”The new experiment also gives Plain and SupHDC the same bandwidth-tuning opportunity.** The original σ=1 was fixed across datasets. In the new controls, each method independently selects σ from {1, 2} using the same held-out validation split. SupHDC remains ahead of both bandwidth-tuned Plain20 and Plain120.

We additional reports SECOM’s macro-F1. At D=10000, averaged over five seeds:

MethodMacro-F1
Plain0.580
SupHDC, K=2 + adaptation + fallback0.583
SupHDC, K=4 + adaptation + fallback0.537

Thus, K=2 retains similar macro-F1, while K=4 has a mild degradation. We will include this metric.

W6. Latency scope and deployment constraints.

Our reported speedups apply to the HDC classification stage, after feature extraction. And we have also evaluated a fixed margin threshold calibrated on validation data. This replaces batch-wide ranking: once a K-query group is available, each prediction can be accepted or recomputed without waiting for 1024 groups.

For D=10,000, K=2 and σ=1:

DatasetRank-based fallback accuracyFixed-threshold accuracyTest fallback rate with fixed threshold
HAR93.79%93.72%26.30%
ISOLET94.23%94.23%20.78%

The threshold is calibrated once to target 20% fallback on validation data; its test fallback rate is measured rather than enforced. Accuracy changes by only 0.07 pp on HAR and 0 pp on ISOLET, while analytical computation remains 22.63% and 25.29% lower, respectively, than same-D Plain. So the threshold is calibrated on a validation set still retains the SupHDC.

W7: Distinction from prior work.

SupHDC’s contribution is to let multiple queries share a fixed encoder while preserving separate predictions. More broadly, we expand inference under superposition to kernel machines, a powerful family of methods, which is not seen in prior works.

DataMUX and MIMONets requires one to train neural networks to process mixed inputs. SupHDCuses an existing model and adapts only its class prototypes. It obtains predictions directly from the shared encoding.

FPE and spatial semantic pointers provide the underlying binding identity. Our contribution is the classification method built around it, the slot-specific readouts, an analysis of when interference preserves predictions, and adaptation plus selective fallback to control errors.

SORF and Fastfood make each encoding cheaper whereas SupHDC reduces the number of encodings needed in the first place. Two families of methods are complimentary which is what we demonstarcted in SupHDC by using ORF.

Q1: Absolute accuracy and the accuracy–compute tradeoff.

The following results average five seeds and ten datasets. SupHDC includes adaptation and 20% fallback. Cost is normalized to Plain at D=10,000 within each dataset, then averaged.

MethodDKAccuracy (%)Relative cost
Plain2,000—84.370.200
Plain5,000—84.450.500
Plain10,000—84.391.000
SupHDC10,000284.760.721
SupHDC10,000383.220.562
SupHDC10,000481.710.482
SupHDC2,000284.410.144

Superposition still provides savings after dimension reduction. At D=2,000, K=2 achieves comparable average accuracy to Plain (84.41% vs. 84.37%) with 27.84% lower cost.

It is also worth noting that we did not consider robustness or corruption here. In that case SupHDC will provide an even better trade-off as it allow one to retain the high-D robustness while accelerating the inference (please see our response for W2).

Q2: Extra training and clean keyed prototypes.

Training Plain for 120 epochs does not close the gap with SupHDC in our additional experiments:

DatasetPlain, 20 epochsPlain, 120 epochsSupHDC + Adaptation + 20% fallback
HAR93.42%93.11%93.82%
ISOLET93.52%93.65%94.03%

Hence, the advantage of SupHDC is not a result of extra training.

Clean keyed fallback does not reproduce Plain exactly for every slot. The identity-key slot matches Plain exactly. For slot 2, clean keyed accuracy is 93.69% on HAR and 93.78% on ISOLET, with prediction agreement of 99.25% and 99.49%, respectively. The keys preserve the underlying RBF kernel, but a fixed finite-dimensional random-feature approximation is not exactly invariant to keying.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.