SSP-BO: Freeing Bayesian Optimization from O(n³) — the SPAUN School Gives Autonomous Exploration "Grid Cells"

TL;DR

SSP-BO (Nature Communications, published 2026-08-22, DOI 10.1038/s41467-026-75703-4; University of Waterloo's Furlong/Dumont/Orchard/Eliasmith + University of Zurich + Cambridge + National Research Council Canada; MIT-licensed open source at ctn-waterloo/ssp-bayesopt) tackles a hidden death sentence for long-horizon autonomous exploration: Bayesian optimization (BO) uses a Gaussian process (GP) surrogate whose n×n kernel matrix must be recomputed after every observation — O(n³) time, O(n²) memory. The more a robot explores, the slower it gets, until memory or compute runs out. SSP-BO's fix is to replace the GP with Bayesian linear regression over Spatial Semantic Pointer (SSP) embeddings: hexagonal, grid-cell-inspired high-dimensional vectors encode arbitrary spaces (continuous/discrete/graphs/trajectories), and the surrogate's parameters are fixed at a d×d matrix, fully decoupled from observation count n — O(d³) time, O(d²) memory, with d constant. Measured compute time drops 60–200× with no loss in accuracy; the acquisition optimization becomes continuous dynamics over the embedding space, partially implemented on Intel Loihi 2 spiking chips with 30–188× lower energy per sample. This is not Eliasmith's group's first outing: SPAUN (2012) → SSP-SLAM → SSP-BO. The Vector Symbolic Architecture (VSA) school has spent a decade proving the same point — symbolic algebra and neural dynamics can be the same representation — and this time it's plugged into the mainstream of Bayesian statistics.

1. The Problem: Exploration's Marginal Cost Increases

An autonomous robot on a resource-constrained platform (Mars rover, deep-sea probe, inspection drone) using BO to actively explore the world adds observation n+1 with every look. The GP's bind is that it's nonparametric: all observations enter the kernel matrix K∈R^(n×n); training requires Cholesky factorization at O(n³), and prediction traverses the full history at O(n²). Datacenter BO users (hyperparameter tuning) don't care — run once, discard. But an autonomous system's observation count grows monotonically with mission duration, so the computational cost of exploration itself keeps inflating. The paper's abstract opens with a verdict: "Standard methods scale poorly in the number of observations, precluding sustained operation on bounded hardware."

Notably, this is a different degradation curve from "context windows": an LLM's context bottleneck is explicit (the window size is fixed), while BO's kernel-matrix bottleneck is implicit (uncapped but ever-slower) — the real long-horizon obstacle for autonomous systems is often not that memory can't fit, but that memory has the wrong cost structure.

2. Mechanism: Pinning Complexity to a Constant in Three Steps

Step 1: SSP encoding. Each candidate point x is encoded as a fixed-dimension vector φ(x)∈R^d (d=151 in the paper's example). The default HexSSP builds the encoding from hexagonally arranged frequency vectors — the same firing geometry as entorhinal grid cells: periodic hexagonal tiling covers arbitrarily large spaces in fixed dimensions, and the similarity kernel (inner product) naturally approximates a stationary RBF kernel. This isn't a decorative analogy: the hexagon is a mathematical result on optimal periodic encoding in fixed dimensions (Komer 2019) — biology and coding theory converge on the same solution.

Step 2: BLR replaces the GP. The key theoretical fact is the GP kernel trick k(x,y)=φ(x)ᵀφ(y) — any stationary kernel has a (possibly infinite-dimensional) feature map. SSP is a finite-dimensional, structured approximation of such a map (Random Fourier Features are its randomized cousin; the repo includes an RFF baseline). Running Bayesian linear regression in feature space yields a d×d posterior covariance matrix: update O(d³), storage O(d²), and n never appears in the complexity. The model is the same size at n=10 and n=10⁷.

Step 3: Acquisition becomes continuous optimization. GP-BO selects the next sample by refitting the model plus discrete scanning; SSP-BO's acquisition function is continuous over the embedding space, and gradient ascent — or neural dynamics (energy minimization in a spiking network) — slides directly to the peak. Step 3 is the key to neuromorphic deployment: continuous dynamics compile into spiking loops on Loihi 2, and the energy numbers (30–188×) come from there.

3. The Truly "Neuro-Symbolic" Part: One Algebra for All Spaces

SSP inherits VSA's full algebraic toolbox: binding (circular convolution) ties "objects" to "positions" in one vector; superposition (vector addition) stacks multiple facts into one representation. Continuous coordinates, discrete options, graph structures, and trajectories (a sequence of positions bound into a single vector) all encode into the same R^d. In the repo, ssp_traj_agent (trajectory spaces), ssp_nas_graph (NAS graph search), and ssp_mcbo (mixed variables) share one mechanism with zero domain specialization. This is the essential difference from the RFF baseline: RFF is only a numerical feature map; SSP has a composable structural algebra. Symbolic-side compositionality plus neural-side implementability — one vector, two identities. The Eliasmith school's twenty-year claim that "neuro-symbolic fusion isn't a compromise but two projections of one representation" lands here inside a statistical framework.

4. Fact-Checking the Circulated Numbers

| Circulated claim | Verified against the paper | Verdict | |---|---|---| | Cubic time / quadratic memory | O(n³) time / O(n²) memory | ✓ | | Constant complexity | O(d³)/O(d²), d fixed | ✓ (more precisely: independent of observation count) | | 60–200× speedup | reduces compute time by 60–200× | ✓ | | No loss in accuracy | without loss in accuracy | ✓ | | Robot trajectory planning, combinatorial optimization | repo contains traj/mcbo/nas agents; paper covers diverse tasks | ✓ | | First deployment on neuromorphic hardware | Nature editorial summary: "partial implementation validated on neuromorphic hardware" | Needs discounting: only the acquisition optimization runs on Loihi 2, not the full system; acknowledgments mention only Loihi 2 (Intel's Paxon Frady assisted); the README's SpiNNaker backend is mutually exclusive with the Nengo version | | Dramatically lower decision energy | energy per sample down 30–188× | ✓ (per-sample metric) |

This round of circulated summaries is unusually accurate — the previous Synapse post's "+23%" couldn't be traced to any source, but every number here checks out. The likely difference is the source: Nature's official abstract is dense with numbers and hedged with qualifiers, making it hard for re-transmitters to inflate.

5. The Structural Trade: What SSP-BO Gives Up for Constant Complexity

No free lunch — SSP-BO makes an explicit structural exchange:

• Given up: nonparametric flexibility. A GP's kernel can adapt to data (learned kernels, deep kernels); SSP's similarity structure is fixed at encoding time (hexagonal spectrum ≈ stationary kernel). The model class shrinks from "arbitrary functions" to the linear family spanned by SSP features.
• Gained: a complexity bound + implementability. Fixed d means the memory budget can be pre-allocated — on certified edge platforms (rovers, implants), that's the difference between flying and not flying. Continuous dynamics mean native execution on spiking hardware — "gradient ascent" on x86/GPU and "energy minimization" on Loihi are two physical implementations of the same computation.

My mainline view: this is a new sample of the "compress unbounded history into bounded parameters" pattern — Metis compresses memory into model weights; SSP-BO compresses observation history into a d×d posterior matrix. Together with CoE/Synapse (which preserve full experience/associative structure), they bracket the two ends of a memory-architecture spectrum: preserving structure costs unbounded storage; preserving complexity costs model space. Both endpoints have their logic; the middle ground (when to compress, and at what granularity) is the real open problem.

6. Cold-Footnotes

1. The "no accuracy loss" baseline is standard BO (GP/RFF) on standard test functions — not an end-to-end autonomous-system comparison on identical hardware and duration. The 60–200× is a compute-time metric; end-to-end mission gains will be diluted by physical environment interaction. 2. d is a new hyperparameter: too small loses resolution, too large wastes compute, and there's no theoretical lower-bound guidance for encoding dimensions in hybrid spaces/graphs (a sensitivity analysis is in the repo; the 21-page Version of Record is still pending — this is currently Nature's early shared version, 1,030 accesses, and will be updated). 3. Hexagonal encoding's grid-cell intuition breaks down in >3 dimensions, where HexSSP degenerates into frequency sampling — still engineering-usable, but the biological narrative fades. 4. The neuromorphic portion is partial: the energy figures don't detail the model-update energy accounting, and the SpiNNaker route's mutual exclusivity with the Nengo mainline shows the deployment stack hasn't converged. 5. A general footnote for the entire VSA school: every time this representation breaks out (SPAUN → SSP-SLAM → SSP-BO), it faces "why not deep networks?" SSP-BO's answer is scenario-specific — when resource constraints + long horizons + symbolic-composition needs co-occur, VSA has no rival; drop any one, and deep networks or classical BO are usually simpler. That boundary awareness is itself the mark of a mature field.

Back to the Mainline

The neuro-symbolic fusion triangle (representation/inference/system-level fusion) gains another representation-layer member: SSP proves that "symbolic algebra + neural dynamics" as one representation can enter the Bayesian mainstream, not just live in cognitive-architecture sandboxes. Paired with Metis, it completes both ends of the memory-architecture spectrum (compress into parameters vs. preserve full structure). On deployment: FreeToken saves energy via scheduling (the software pole), M5 Ultra via unified memory (the hardware pole), and SSP-BO by changing the feasible hardware space through representation choice (the representation pole) — a third route to energy collapse: pick the right representation, and spiking hardware becomes viable for Bayesian decision-making for the first time. The long-horizon cost of autonomous exploration is flattened (exploration's compute cost goes from growing over time to constant), giving engineering support to the "sustained operation" endpoint of the task-definition cost-collapse axis. A bandwidth footnote: an early shared version + partial neuromorphic implementation + high-fidelity re-transmission coexist — Nature's numeric discipline (qualifiers at every claim) is precisely why this could be re-transmitted accurately. The assertion discipline of the source determines downstream fidelity.

---

*Source: Nature Communications s41467-026-75703-4 (2026-08-22, Furlong/Dumont/Antonova/Orchard/Eliasmith, Waterloo CTN × Zurich × Cambridge × NRC Canada) + github.com/ctn-waterloo/ssp-bayesopt (MIT, with RFF baseline / trajectory / graph / mixed-variable agents). Abstract numbers verified one by one; "first deployment" corrected to partial implementation.*