Superposed Inference for Hyperdimensional Computing

1 INTRODUCTION

• Conventional HDC repeats the encoding pipeline K times for K queries, and encoding accounts for most inference latency across representative workloads.Reducing representation dimension can lower the cost but also removes some of the redundancy valued for HDC.Source: §1 · pp. 1–2
• SupHDC assigns each query a lightweight random slot key, superposes the keyed inputs, encodes the mixture once, and uses slot-specific classifiers to predict each query’s label.It is motivated by the view that prediction requires preserving class evidence, not exactly recovering each individual representation.Source: §1 · p. 2
• Superposition-aware adaptation and selective clean-path recomputation address interference, while the superposition factor provides an efficiency–accuracy operating tradeoff.The paper frames high-dimensional redundancy as capacity for shared inference as well as robustness.Source: §1 · p. 2
• 1.39× analytical inference speedup with no accuracy loss across ten datasets, and 2.08× speedup with a 2.67 percentage-point mean accuracy loss at a more aggressive operating point.On a Raspberry Pi 5, SupHDC achieves 2.01× measured wall-clock speedup with a 2.26 percentage-point mean accuracy loss.Source: §1 · p. 2

2 RELATED WORK

• SupHDC reduces the number of independent encoding operations by amortizing one high-dimensional encoding across multiple queries, complementing quantization and hardware acceleration.The paper situates projection-based HDC as an approximation to kernel machines, including through random Fourier features.Source: §2 · p. 2
• Classical HDC superposition bundles multiple representations into a fixed-dimensional representation that remains similar to its constituents.The passage also distinguishes model or parameter superposition, which stores multiple models in a shared parameter tensor and retrieves them through context-dependent transformations.Source: §2 · pp. 2–3
• Earlier superposition methods bundle representations or multiplex inputs through neural networks, whereas SupHDC shares the high-dimensional encoding itself and seeks to preserve prediction-relevant information.The passage contrasts this approach with DataMUX and MIMONets, which use learned demultiplexing or VSA-inspired binding and unbinding, respectively.Source: §2 · pp. 2–3

3 PRELIMINARIES AND PROBLEM DEFINITION

• Projection-based HDC maps an input x in d dimensions to a representation in D dimensions using a random or quasi-random projection, with the projection forming the principal encoding operation.Nonlinear random Fourier feature encoders apply a phase nonlinearity to projected features and can approximate shift-invariant kernels.Source: §3 · pp. 3–4
• Prototype classification compares an encoded query with class prototypes, and when encoder similarities approximate a kernel, the readout approximates a kernel-machine score.Linear random projections support a linear-kernel interpretation, while random Fourier features approximate shift-invariant kernels.Source: §3 · p. 3
• For K queries, conventional HDC performs K separate encoder evaluations, and SupHDC seeks shared encoding while still producing one prediction per query.The goal is orthogonal to choosing D and can reduce repeated encoding without compressing a dimension retained for fidelity or robustness.Source: §3 · pp. 3–4

4 SUPHDC: SUPERPOSED INFERENCE FOR HDC

• Each query receives a fixed random slot key, and keyed queries are superposed before the expensive d-to-D encoding so that the encoding computation is shared.The encoder remains unchanged from the conventionally trained base model.Source: §4 · p. 4
• The nonlinear RFF encoder generally does not encode a sum as the sum of separately encoded queries, so SupHDC uses slot-specific prototype banks to read class evidence from the shared representation.Each slot’s prototypes use the base classifier’s sample weights with examples encoded under that slot’s key.Source: §4 · p. 4
• Superposition-aware adaptation updates only slot-specific prototype banks using mixed-input training signals, while keeping the encoder and keys fixed.Corrective updates teach classifiers to recognize class evidence under interference rather than learning an inverse of the mixing operation.Source: §4 · pp. 4–5
• Margin-gated fallback selects the ⌈qNb⌉ predictions with the smallest score margins and recomputes those queries through the clean inference path.The margin test has negligible overhead because the slot-specific readout has already produced the scores.Source: §4 · p. 5
• SupHDC replaces repeated encoding with one shared encoding while retaining K slot-specific readouts, for approximate cost E + KR + Fkey rather than K(E + R).With fallback ratio q, approximately qK queries incur an additional clean encoding and readout; storage mainly adds slot-specific prototype banks and lightweight keys.Source: §4 · p. 5
• The fallback ratio q trades some compute savings for improved prediction fidelity by adding clean encoding and readout for selected queries.Unselected queries retain their superposed predictions.Source: §4 · p. 5

Kernel View of a Superposed Slot

• SupHDC analyzes each keyed query alongside the aggregate of the other slots, asking how that interference perturbs kernel similarities and class scores.The analysis treats adaptation and fallback as additional mechanisms for handling the interference.Source: §5 · p. 6

Score Preservation under Superposition

• A perturbed kernel similarity separates into a common scaling term and a residual; the scaling affects all classes alike, while the residual can alter their ranking.Thus, exact recovery of the mixed representation is unnecessary when class-dependent distortion remains small enough to preserve the winner.Source: §5 · p. 6

Random Keys Suppress the Residual

• Random slot keys reduce coherent cross-slot alignment; increasing K raises interference, while increasing input dimension d reduces alignment for fixed vector norms.For the RBF residual, small cross-slot alignment relative to the kernel scale makes the residual correspondingly small; sensitivity also depends on kernel bandwidth.Source: §5 · pp. 6–7

Margin-Based Prediction Preservation

• When the common score scaling is positive, superposed inference preserves the clean prediction if class-dependent distortion is less than half the scaled clean margin.Larger-margin queries can tolerate more distortion; smaller-margin queries are more vulnerable to a flip.Source: §5 · pp. 6–7

Finite-D Random-Feature Approximation

• Finite-D random-feature approximation adds a distinct distortion source: larger D improves approximation of the underlying kernel, while K controls the number of interfering queries.The input dimension d governs random-key separation, distinct from D’s effect on finite-feature approximation.Source: Finite-D Random-Feature Approximation · p. 7

Experimental Setup

• The evaluation covers 10 datasets, D values from 1,000 to 10,000, K = 2–10, and numerical precisions from 1 to full-precision bits.Results are averaged over five random seeds; efficiency uses projection and prototype-scoring FLOPs, with separate Raspberry Pi 5 evaluation.Source: §6 · pp. 7–8

Accuracy–Compute Tradeoff

• 1.39× analytical speedup matches Plain accuracy at K = 2, while 2.08× speedup at K = 4 incurs a 2.67 ± 0.65 pp average accuracy loss with adaptation and fallback.Table 1 reports the accuracy–compute tradeoff at D = 10,000 and full precision; ∆Acc. is relative to Plain.Source: Table 1 · p. 8, §6 · p. 8

Complementary Efficiency Knobs

• At K = 4, mean accuracy loss falls from 8.31 pp at D = 1,000 to 2.67 pp at D = 10,000; 4–8-bit configurations closely track full-precision accuracy behavior.SupHDC’s analytical speedups are 1.39×, 1.78×, and 2.08× at K = 2, 3, and 4 across evaluated precisions; 1–2-bit quantization introduces larger degradation.Source: §6 · p. 8

Understanding the Superposition Regime

• Across benchmark inputs, cross-slot alignment follows the predicted (K −1)/d dependence, while score distortion increases with K and its finite-feature contribution falls as D grows.Across K = 2–6 operating points, distortion strongly tracks accuracy degradation (Pearson r = 0.99, Spearman ρ = 0.994).Source: Figure 4 · p. 9, §6 · p. 9

Edge Deployment

• At K = 4 on Raspberry Pi 5, recomputing the lowest-confidence 20% reduces mean accuracy loss from 6.66 to 2.26 pp while retaining 2.01× measured speedup.Without fallback, measured speedups are 1.79× at K = 2 and 3.36× at K = 4; timing uses one CPU thread and excludes training and model loading.Source: §6 · p. 9

7 CONCLUSION

• Around 2× inference speedup with minimal accuracy loss is reported across diverse datasets and edge deployment.SupHDC replaces repeated per-query encoding with shared superposed inference.Source: §7 · p. 9
• Superposed inference treats high-dimensional representational redundancy as computational capacity for carrying multiple predictions through shared representation computation.The conclusion presents this as a direction for HDC and kernel machines.Source: §7 · p. 10

B.1 DERIVATION OF THE SCORE DECOMPOSITION

• The score decomposition separates a class-independent scaling from class-dependent distortion, while common positive scaling alone preserves class ordering.The scaling changes the clean margin available to tolerate class-dependent distortion.Source: §B.1 · p. 15, §B.4 · p. 16

B.2 RBF RESIDUAL AND RESIDUAL BOUND

• For the RBF kernel, the superposition residual is controlled by cross-slot alignment relative to the kernel scale σ^2.The proof passage describes the alignment as δ⊤v relative to σ^2.Source: §B.2 · p. 15

B.5 FINITE-D RANDOM-FEATURE APPROXIMATION

• Pointwise random-feature approximation error is O(D^-1/2), and the implementation uses orthogonal random features to reduce variance without changing that convergence order.The concentration result is stated for standard i.i.d. random Fourier features; ORF is used in implementation.Source: §B.5 · p. 17

C.1 BASE HDC MODEL TRAINING

• The base classifier bundles encoded examples into class prototypes and refines them using prediction errors, a procedure described as broadly applicable across HDC classifiers.SupHDC retains learned sample weights and does not modify the base projection matrix.Source: §C.1 · pp. 17–18

C.2 FULL SUPHDC ALGORITHM

• SupHDC uses fixed slot keys and re-encodes training examples into clean slot prototype banks before adapting working prototypes with superposed groups.At inference, each group shares one encoding; the lowest-margin fraction can instead be individually re-encoded and rescored with the clean bank.Source: §C.2 · pp. 18–19

C.3 HYPERPARAMETERS

• Random-feature projections and slot keys remain fixed across training, adaptation, and inference, so SupHDC adapts only the slot-specific prototype banks.Source: §C.3 · p. 20

C.4 EDGE EXPERIMENT DETAILS

• The Raspberry Pi 5 evaluation uses full-precision D = 10,000 models on HAR, ISOLET, CIFAR-10, and AG News, with K ∈ {2, 4}.Models are prepared offline; training, bundle loading, and accuracy evaluation are excluded from the timed region.Source: §C.4 · p. 20
• Timing compares batched Plain HDC and SupHDC on matching query blocks, with one CPU thread, five warm-ups, and 30 measured repetitions.Thermal conditions are controlled, and reported latency is the median; fallback queries are re-encoded in a batch.Source: §C.4 · p. 20

D.1 DATASETS AND INPUT REPRESENTATIONS

• Dataset inputs include tabular measurements, image vectors or pretrained ResNet-50 features, and Word2Vec-based text representations; all final vectors are ℓ2-normalized.Text representations add sinusoidal positional encodings before mean pooling.Source: §D.1 · p. 21

D.2 EXPERIMENTAL PROTOCOL AND RESULT AGGREGATION

• The main evaluation covers ten classification datasets, dimensions D ∈ {1,000, 2,000, 5,000, 10,000}, K values from 2 to 10, and precisions from full precision to 1 bit.It compares Plain RFF-HDC with four SupHDC variants across five paired random seeds.Source: §D.2 · p. 21
• Results are averaged over five seeds per dataset, then across datasets with equal dataset-level weight; accuracy changes are paired against Plain HDC and uncertainty is SEM.Repeated inference timings stabilize runtime measurements and are not treated as independent predictive trials.Source: §D.2 · pp. 21–22

Behavior across the full superposition range

• Moderate superposition remains the most favorable balance; at K = 2 adaptation with fallback matches Plain HDC accuracy on average, while losses grow beyond K = 4.Larger K continues to increase nominal savings, but with diminishing returns and increasingly dataset-dependent degradation.Source: E EXTENDED ACCURACY–COMPUTE RESULTS · pp. 22, 24
• Combining adaptation and fallback gives the strongest accuracy preservation across K = 2, . . . , 10, while direct superposition degrades as interference increases.Adaptation improves accuracy without additional inference-time encoding operations; fallback further improves fidelity by recomputing low-confidence predictions.Source: Figure 5 · p. 22, E EXTENDED ACCURACY–COMPUTE RESULTS · p. 22

Extended accuracy–compute landscape

• Adaptation improves accuracy at nearly unchanged inference cost, whereas fallback trades some speedup for cleaner recomputation of uncertain queries.The combined methods provide operating points between clean inference and aggressive superposition.Source: E EXTENDED ACCURACY–COMPUTE RESULTS · pp. 22–23, Figure 6 · p. 23

Effect of representation dimension

• Larger D improves tolerance to superposition across the evaluated dimensions, while adaptation and representation dimension address distinct sources of accuracy degradation.Adaptation better matches slot-specific readouts to superposed inputs; larger D improves the fidelity of the underlying random-feature representation.Source: E EXTENDED ACCURACY–COMPUTE RESULTS · pp. 23–24

Dataset-level sensitivity to superposition

• Accuracy degradation varies by dataset: most remain near or above their paired baseline at K = 2, but sensitivity and cross-dataset uncertainty grow at larger K.The suitable K depends on workload-specific classification margins and tolerated score distortion.Source: E EXTENDED ACCURACY–COMPUTE RESULTS · p. 24

Superposition-aware prototype adaptation

• At 20 adaptation epochs, adapted models recover approximately 86–92% of the 100-epoch improvement, rising to approximately 90–97% with fallback.The benefit of adaptation largely arrives early; the 100-epoch setting is a conservative converged configuration.Source: F ABLATIONS OF ADAPTATION AND… · p. 25, Figure 10 · p. 26

Margin-gated selective fallback

• At a 20% fallback fraction, low-margin selection captures approximately 67% of pre-fallback errors for K = 2 and 54% for K = 4, versus 20% expected under random selection.The classification margin therefore indicates predictions vulnerable to superposition interference.Source: F ABLATIONS OF ADAPTATION AND… · p. 25, Figure 11 · p. 27
• Increasing the fallback fraction improves accuracy by recomputing more uncertain queries, but reduces analytical speedup.At K = 2, relatively small fallback fractions approach Plain HDC accuracy; K = 4 requires larger fractions to recover more accuracy while retaining meaningful speedup.Source: F ABLATIONS OF ADAPTATION AND… · p. 26, Figure 11 · p. 27

Combined mechanisms

• Adaptation improves slot-specific classifiers without extra inference encodings, while fallback spends added computation on difficult queries identified by prediction margin.The mechanisms address different aspects of interference and can be combined to improve fidelity while retaining shared-encoding savings.Source: F ABLATIONS OF ADAPTATION AND… · pp. 26–27

Analytical inference cost

• SupHDC uses one shared projection while retaining one prototype readout per slot, with analytical cost F_SupHDC = E + KR.Here E is the projection cost and R is the cost of scoring against class prototypes; adaptation changes prototype banks without adding inference-time computation.Source: G DETAILED COMPUTATIONAL AND STORAGE… · p. 27
• The shared projection makes the analytical speedup approach K× when projection dominates readout cost, but the KR term and selective recomputation create diminishing returns as K grows.Signed-permutation keys add lightweight operations in the input space; these are excluded from analytical FLOPs but included in wall-clock measurements.Source: G DETAILED COMPUTATIONAL AND STORAGE… · p. 27

Model storage cost

• At K = 2–4, adapted SupHDC requires about 1.04–1.13× Plain HDC persistent storage, increasing to approximately 1.13–1.29× with fallback.The projection matrix is shared; fallback adds a clean prototype bank for each slot.Source: G DETAILED COMPUTATIONAL AND STORAGE… · p. 28, Figure 12 · p. 28

Overall tradeoff

• SupHDC trades a modest increase in persistent classifier storage for reduced repeated high-dimensional encoding computation.Fallback requires additional computation and a clean prototype bank, while providing a tunable way to recover prediction fidelity.Source: G DETAILED COMPUTATIONAL AND STORAGE… · pp. 27–28

Analytical versus measured speedup

• Without fallback, Raspberry Pi 5 speedups are 1.79× measured versus 1.90× analytical at K = 2, and 3.36× measured versus 3.45× analytical at K = 4.Increasing fallback moves both analytical and measured speedups toward 1× as more queries are individually recomputed.Source: H ADDITIONAL EDGE DEPLOYMENT RESULTS · p. 29
• At 20% fallback, measured Raspberry Pi 5 speedups are 1.19× for K = 2 and 2.01× for K = 4, versus analytical predictions of 1.38× and 2.04×, respectively.Across the evaluated fallback sweep, measured speedup follows the analytical trend; the remaining gap reflects implementation and system overheads outside the FLOP model.Source: Figure 13 · p. 29, H ADDITIONAL EDGE DEPLOYMENT RESULTS · p. 29

• SupHDC uses high-dimensional redundancy as shared inference capacity, preserving prediction-relevant class evidence without requiring exact recovery of each hypervector.Source: I DISCUSSION AND LIMITATIONS · p. 29
• Unlike reducing dimension, lowering precision, or specializing hardware, SupHDC reduces how many independent encodings are required.The Raspberry Pi results show that this algorithmic saving can translate into real wall-clock acceleration.Source: I DISCUSSION AND LIMITATIONS · p. 29
• The useful superposition factor K varies by dataset, and the current method selects K empirically.Source: I DISCUSSION AND LIMITATIONS · p. 30
• Randomly paired queries may not be optimal because interference depends on within-group sample interactions; interference-aware grouping could improve the accuracy–compute tradeoff.Source: I DISCUSSION AND LIMITATIONS · p. 30
• The study focuses on projection-based HDC, leaving other HDC/VSA encoders and representation schemes outside its coverage.Source: I DISCUSSION AND LIMITATIONS · p. 30