Compositional neurosymbolic representations enable efficient active exploration Authors: P. Michael Furlong, Nicole S.-Y. Dumont, Rika Antonova, Jeff Orchard, Chris Eliasmith Published: 2026 ABSTRACT Autonomous systems that learn and explore over long horizons face a problem. Standard methods scale poorly in the number of observations, n, precluding sustained operation on bounded hardware. We show that compositional, high-dimensional vector representations inspired by neural computation address these constraints. We use these representations to construct a Bayesian optimization (BO) algorithm that operates in complex spaces and reduces the time and memory requirements compared to state-of-the-art BO algorithms on diverse tasks. Whereas standard methods incur O(n3) time and O(n2) memory complexity, our approach holds both at O(d2) in the embedding dimension, which remains constant over the algorithm’s lifetime. Our algorithm reduces compute time by 60–200 × without loss in accuracy. Implementation on neuromorphic hardware reduces energy consumption per sample by 30–188 × . These efficiencies stem from converting sample selection into continuous optimization on a compact domain, implementable by gradient methods or neural dynamics, enabling long-term, resource-bound, autonomous exploration. Introduction Generalizing efficiently from limited data in complex environments remains a major challenge for artificial intelligence (AI). Humans, in contrast, learn and act in complex, high-dimensional state and action spaces with remarkable efficiency, even in the face of uncertainty. A crucial aspect of this ability is the use of compositional representations, where simpler elements are systematically combined to form more complex structures. This principle underlies human cognition, from perception to language, and is fundamental to generalization and adaptability in complex environments1–4. However, achieving both scalability and compositional expressiveness in AI models remains an open challenge5,6. In machine learning, kernel methods offer a principled way to encode structured inductive biases7, support data-efficient learning, and model uncertainty. Compositional kernels, constructed by combining simpler kernels via addition or multiplication, enable the expression of rich relational structures8. However, the practical application of such kernels is hindered by scalability: inference with Gaussian processes (GPs) requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({n}^{3})$$\end{document}O(n3) time and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({n}^{2})$$\end{document}O(n2) memory, where n is the number of observations. While kernel approximation methods such as Random Fourier Features [RFFs; 9] reduce this complexity, approximating compositional kernels with RFFs often leads to unbounded growth in embedding dimensionality10, and representing structured or symbolic inputs remains challenging. Vector Symbolic Algebras (VSAs) - specifically, Holographic Reduced Representations (HRRs) and their complex-valued variant, Fourier HRRs (FHRRs) 11,12–offer a promising solution by providing a dimensionality-preserving algebra for compositional representation. We note that VSAs are more commonly known as vector symbolic architectures13, but we use the term algebra to distinguish the algebras from the systems architected using VSAs. Vector embeddings used in kernel approximation (such as RFFs) typically implement composition using operations like concatenation (for additive kernels) or tensor products (for multiplicative kernels), both of which increase dimensionality. In contrast, VSAs achieve similar compositionality using fixed-dimensional operations such as bundling and binding (e.g., circular convolution in HRRs). This allows vector embeddings of structured and hierarchical data to have fixed dimensionality. VSAs have a long history in cognitive science6,13–21, and have more recently been used for neural-symbolic deep learning21,22, differentiable memory23, efficient attention24,25, and kernel approximation. Indeed, the connection between VSAs and kernel embeddings has been well understood since their inception26, but has garnered recent attention 27–31. The central hypothesis of VSAs is that cognition operates through algebraic manipulations of high-dimensional distributed representations. These operations support not only compositionality and neural implementation20, but also the encoding of uncertainty29,30,32. In this work, we introduce Spatial Semantic Pointer Bayesian optimization (SSP-BO), a new Bayesian optimization (BO) algorithm based on VSA-derived kernel approximations. Our method leverages the algebra of HRRs to construct expressive, compositional, and fixed-size embeddings over various action spaces. Additionally, our work further connects BO to biologically plausible neural representations through the use of continuous vector encodings called Spatial Semantic Pointers (SSPs), also referred to as fractional power encodings,33–35. These representations reproduce activity patterns observed in the brain’s spatial coding systems–such as grid, place, and head direction cells36–38–and serve as our algorithm’s embedding method for continuous variables. This yields several advantages:Scalability: We obtain constant-time sample selection with respect to the number of environment observations, n. Standard BO requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({n}^{3})$$\end{document}O(n3) time and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({n}^{2})$$\end{document}O(n2) memory for surrogate model updates; our approach reduces this to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({d}^{2})$$\end{document}O(d2) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({d}^{2})$$\end{document}O(d2), respectively, where d is the fixed dimensionality of the VSA embeddings. Since d is set prior to optimization and remains constant, both sample generation time and memory usage are independent of the number of observations collected during the run, and hence O(1) with respect to n.Expressivity: Our method supports structured, symbolic, and mixed discrete-continuous input spaces (e.g., graphs, sets, trajectories) via a single algebraic framework.Neuromorphic compatibility: Sample selection in SSP-BO occurs in the continuous embedding space. This makes it possible to perform sample selection over structured action spaces on neuromorphic hardware, providing a biologically grounded pathway for efficient decision-making systems. Scalability: We obtain constant-time sample selection with respect to the number of environment observations, n. Standard BO requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({n}^{3})$$\end{document}O(n3) time and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({n}^{2})$$\end{document}O(n2) memory for surrogate model updates; our approach reduces this to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({d}^{2})$$\end{document}O(d2) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({d}^{2})$$\end{document}O(d2), respectively, where d is the fixed dimensionality of the VSA embeddings. Since d is set prior to optimization and remains constant, both sample generation time and memory usage are independent of the number of observations collected during the run, and hence O(1) with respect to n. Scalability: We obtain constant-time sample selection with respect to the number of environment observations, n. Standard BO requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({n}^{3})$$\end{document}O(n3) time and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({n}^{2})$$\end{document}O(n2) memory for surrogate model updates; our approach reduces this to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({d}^{2})$$\end{document}O(d2) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({d}^{2})$$\end{document}O(d2), respectively, where d is the fixed dimensionality of the VSA embeddings. Since d is set prior to optimization and remains constant, both sample generation time and memory usage are independent of the number of observations collected during the run, and hence O(1) with respect to n. Expressivity: Our method supports structured, symbolic, and mixed discrete-continuous input spaces (e.g., graphs, sets, trajectories) via a single algebraic framework. Expressivity: Our method supports structured, symbolic, and mixed discrete-continuous input spaces (e.g., graphs, sets, trajectories) via a single algebraic framework. Neuromorphic compatibility: Sample selection in SSP-BO occurs in the continuous embedding space. This makes it possible to perform sample selection over structured action spaces on neuromorphic hardware, providing a biologically grounded pathway for efficient decision-making systems. Neuromorphic compatibility: Sample selection in SSP-BO occurs in the continuous embedding space. This makes it possible to perform sample selection over structured action spaces on neuromorphic hardware, providing a biologically grounded pathway for efficient decision-making systems. We evaluate SSP-BO on a suite of tasks involving action selection in structured domains, including robotic trajectory optimization, multi-agent coordination, graph-based search, and combinatorial design. Compared to exact GP-based methods, SSP-BO offers substantial efficiency gains while maintaining strong performance. Whereas existing approaches typically provide either scalable BO or expressive BO, this work combines both within a single compositional kernel embedding framework, enabling efficient optimization in structured domains and supporting neuromorphic implementation. To the best of our knowledge, this constitutes the first demonstration of neuromorphic hardware being used within a BO loop. A graphical abstract is provided in Fig. 1.Fig. 1Overview of the SSP-BO method and experiments.a Our method conducts optimization in the space of vector symbolic representations. Upon obtaining an candidate vector, we decode it using vector symbolic operators. With that, we obtain an action vector xt, which can be executed in the environment. In this example, an action vector represents desired trajectories of robots searching for water in a crater. We obtain a reward f(xt) from the environment and incorporate it into the posterior distribution over the reward function. We update the posterior using Bayesian linear regression. We then optimize an information-theoretic acquisition function in the space of vector symbolic representations, produce the next embedded candidate vector, and so on. This way of conducting optimization yields a method with native support for compositionality and constant time and space complexity. b We demonstrate that a recurrent neural population can be used to optimize the objective in the embedding space. Neurons are connected all-to-all, with connection weights set to approximate gradient ascent on the acquisition function. The selected sample \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi \in {{\mathbb{R}}}^{d}$$\end{document}ϕ∈Rd is linearly decoded from the population’s activity. c The benchmark optimization problems that SSP-BO is tested on. On the left are three standard test functions for global optimization: the Himmelblau, Goldstein-Price, and Branin-Hoo functions. The SSP-BO method was tested on these functions with SSPs used to represent the 2D function input. In the middle are the discrete action space tasks: Pest Control, RNA Inverse Folding and NAS-Bench-101. On the right are the robotics environments: Box Reach, Belt Stretch, and Permanently Shadowed Region (PSR). In Box Reach, the objective is to quickly reach a target within a box. In Belt Stretch, two arms must collaborate to place an elastic belt on a motor and gear assembly. In PSR, multiple robots explore the permanently shadowed of a crater to find water. Overview of the SSP-BO method and experiments. a Our method conducts optimization in the space of vector symbolic representations. Upon obtaining an candidate vector, we decode it using vector symbolic operators. With that, we obtain an action vector xt, which can be executed in the environment. In this example, an action vector represents desired trajectories of robots searching for water in a crater. We obtain a reward f(xt) from the environment and incorporate it into the posterior distribution over the reward function. We update the posterior using Bayesian linear regression. We then optimize an information-theoretic acquisition function in the space of vector symbolic representations, produce the next embedded candidate vector, and so on. This way of conducting optimization yields a method with native support for compositionality and constant time and space complexity. b We demonstrate that a recurrent neural population can be used to optimize the objective in the embedding space. Neurons are connected all-to-all, with connection weights set to approximate gradient ascent on the acquisition function. The selected sample \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi \in {{\mathbb{R}}}^{d}$$\end{document}ϕ∈Rd is linearly decoded from the population’s activity. c The benchmark optimization problems that SSP-BO is tested on. On the left are three standard test functions for global optimization: the Himmelblau, Goldstein-Price, and Branin-Hoo functions. The SSP-BO method was tested on these functions with SSPs used to represent the 2D function input. In the middle are the discrete action space tasks: Pest Control, RNA Inverse Folding and NAS-Bench-101. On the right are the robotics environments: Box Reach, Belt Stretch, and Permanently Shadowed Region (PSR). In Box Reach, the objective is to quickly reach a target within a box. In Belt Stretch, two arms must collaborate to place an elastic belt on a motor and gear assembly. In PSR, multiple robots explore the permanently shadowed of a crater to find water. Bayesian optimization (BO) is a data-efficient framework for black-box optimization and reinforcement learning39–41. It has been applied to problems in autonomous exploration, morphology and material design, and hyperparameter tuning42–47. BO typically models an unknown reward or objective function with a surrogate (often a GP [refs. 43,48–50]) and selects queries by optimizing an acquisition function over the surrogate’s posterior. However, the cost of GP inference grows cubically with the number of data points, which limits its applicability in real-time or embedded systems (e.g., spacecraft, edge devices). Efficiency improvements have been pursued via sparse approximations51,52, discretization42,53,54, and simulation-based augmentation55–57. While effective, these methods either constrain representational flexibility or require significant additional resources (e.g., high-fidelity simulators). Structured and mixed-domain optimization problems remain especially challenging. Existing approaches often rely on engineered kernels58,59 or learned latent space projections60–64. However, these methods require training generative models, introduce interpretability challenges, and can be expensive to optimize. While alternatives to GPs exist, the GP formulation remains attractive because of its ease of implementation, convenient theoretical properties, and connection to exploratory behaviors in humans7,65. Positive-definite kernels are closed under addition and multiplication [66, section 6.2]. These algebraic operations form the basis for compositional kernels67,68, which can be used to encode inductive biases over structured data. This compositionality has been shown to improve generalization in machine learning domains59. Furthermore, in cognitive modeling, structured inductive biases reduce the amount of data required for learning5,69,70. In kernel approximation methods, such as RFFs, compositional constructions are generally obtained using concatenation and tensor products of features [e.g.,10,71–73]. However, these operations result in feature dimensionality that grows linearly or multiplicatively with composition depth, leading to unbounded resource use as kernel complexity increases. A notable exception is the method proposed by ref. 74, which constructs product kernels using element-wise multiplication of complex-valued vectors–a strategy closely related to the FHRR binding operator. In contrast, VSA-based embeddings used in SSP-BO maintain constant dimensionality through fixed-width algebraic operations, such as bundling and binding (a compressed tensor product). This enables scalable kernel approximation without sacrificing expressivity and supports compositional representations over arbitrary data types. Our method falls within the class of syntactic-driven kernels58,75, in which each structured representation induces a corresponding kernel function. Overall, VSAs preserve compositional expressiveness while keeping memory and compute costs bounded – an essential property for neuromorphic implementation. This paper introduces SSP-BO, a BO algorithm that uses compositional kernel embedding based on VSA-derived representations. In sum, the main contributions of this work are:Using hybrid cognitive representations of continuous trajectories and symbolic entities for BO. VSAs allows us to address the long-standing problem of efficient BO in combinatorial, continuous, and mixed discrete-continuous spaces by leveraging VSAs with the same algorithm.Employing neuroscience-inspired representations for BO. We use Hexagonal-Spatial Semantic Pointers (Hex-SSPs), a VSA method for encoding continuous data, used in modeling activity of spatially sensitive neurons found in the hippocampus36.Demonstrating constant time and memory sample selection complexity for BO. SSP-BO reduces the complexity of selecting the next sample during BO from O(n3) and O(n2) in time and memory respectively, to constant in the number of samples collected and O(d2) and O(d2) in the embedding size, which remains fixed during optimization. We empirically support the theoretical claims that SSP-BO’s run time is approximately constant in the number of collected samples, across optimization problems. We show this results in a total sample selection time reduction by a factor of 3.1 − 205.5 × (depending on the total number of samples and the problem size) compared to standard BO methods.Validating the SSP-BO algorithm on neuromorphic computing hardware. We provide a neural implementation of the sample section in SSP-BO and demonstrate performance on two neuromorphic computing platforms (SpiNNaker and Loihi 2). Notably, this showcases the first implementation of BO on neuromorphic computing platforms. Using hybrid cognitive representations of continuous trajectories and symbolic entities for BO. VSAs allows us to address the long-standing problem of efficient BO in combinatorial, continuous, and mixed discrete-continuous spaces by leveraging VSAs with the same algorithm. Using hybrid cognitive representations of continuous trajectories and symbolic entities for BO. VSAs allows us to address the long-standing problem of efficient BO in combinatorial, continuous, and mixed discrete-continuous spaces by leveraging VSAs with the same algorithm. Employing neuroscience-inspired representations for BO. We use Hexagonal-Spatial Semantic Pointers (Hex-SSPs), a VSA method for encoding continuous data, used in modeling activity of spatially sensitive neurons found in the hippocampus36. Employing neuroscience-inspired representations for BO. We use Hexagonal-Spatial Semantic Pointers (Hex-SSPs), a VSA method for encoding continuous data, used in modeling activity of spatially sensitive neurons found in the hippocampus36. Demonstrating constant time and memory sample selection complexity for BO. SSP-BO reduces the complexity of selecting the next sample during BO from O(n3) and O(n2) in time and memory respectively, to constant in the number of samples collected and O(d2) and O(d2) in the embedding size, which remains fixed during optimization. We empirically support the theoretical claims that SSP-BO’s run time is approximately constant in the number of collected samples, across optimization problems. We show this results in a total sample selection time reduction by a factor of 3.1 − 205.5 × (depending on the total number of samples and the problem size) compared to standard BO methods. Demonstrating constant time and memory sample selection complexity for BO. SSP-BO reduces the complexity of selecting the next sample during BO from O(n3) and O(n2) in time and memory respectively, to constant in the number of samples collected and O(d2) and O(d2) in the embedding size, which remains fixed during optimization. We empirically support the theoretical claims that SSP-BO’s run time is approximately constant in the number of collected samples, across optimization problems. We show this results in a total sample selection time reduction by a factor of 3.1 − 205.5 × (depending on the total number of samples and the problem size) compared to standard BO methods. Validating the SSP-BO algorithm on neuromorphic computing hardware. We provide a neural implementation of the sample section in SSP-BO and demonstrate performance on two neuromorphic computing platforms (SpiNNaker and Loihi 2). Notably, this showcases the first implementation of BO on neuromorphic computing platforms. Validating the SSP-BO algorithm on neuromorphic computing hardware. We provide a neural implementation of the sample section in SSP-BO and demonstrate performance on two neuromorphic computing platforms (SpiNNaker and Loihi 2). Notably, this showcases the first implementation of BO on neuromorphic computing platforms. In requiring only fixed rather than growing resources, our approach enables deploying sophisticated methods for lifelong learning and autonomous exploration on resource-constrained platforms, including neuromorphic hardware. Beyond the specific results reported here, we hope this work illustrates a broader point: that the architectural constraints of neuromorphic and biological systems (fixed resources, compositional structure, constant-time operations) need not limit the sophistication of the algorithms they support, and that established machine learning methods can benefit from the representational frameworks developed in these communities. Results Our algorithm follows a Reinforcement Learning (RL) paradigm: an agent interacts with a (potentially stochastic) environment and seeks the most rewarding actions. The agent can observe the reward function by sampling actions x from a domain, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{X}}}}$$\end{document}X, up to some maximum sampling budget. After receiving an observation, the agent updates its surrogate model of the reward function. There is a need to balance exploration, i.e., searching for more rewarding actions, and exploitation, i.e., using the best rewarded actions seen so far. Actions are selected by optimizing an acquisition function that balances these factors (Equation (18)). A key aspect of our approach is the use of a Vector Symbolic Algebra (VSA). Actions are mapped to a high-dimensional embedding space, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi :{{{\mathcal{X}}}}\to {{\mathbb{R}}}^{d}$$\end{document}ϕ:X→Rd, using a VSA. This mapping can be derived for various structured action domains, as explained in the next section. The BO loop using VSA embeddings is presented in section “SSP-BO algorithm” and an overview of SSP-BO is given in Fig. 1. Empirical results begin in section “Experiments”. Vector symbolic algebra (VSA) We introduce VSAs here, but readers interested in greater detail, including how to map them to spiking or non-spiking neural networks, can refer to other resources 12,20,76–80. Below we provide the mathematical introduction to VSAs, intuition about the kernels induced by these structures are given in section “Methods”. VSAs are algebras for capturing symbolic reasoning in high-dimensional vector spaces. In VSAs, symbols, represented as high-dimensional vectors (Fig. 2), can be manipulated by operations on those vectors. Cognitive models are constructed by combining vectors and operators, which can then be used to process stimuli. VSAs are typically equipped with four key operators: bundling ( + ), similarity ( ⋅ ), binding ( ⊗ ), and unbinding ( ⊘ ). Some VSAs also define a hiding operator, which can be implemented using permutation matrices. HRRs, however, do not include a distinct hiding operator, as that can be achieved by binding. In this paper, we work with Holographic Reduced Representations (HRRs), a type of VSA developed by ref. 12. In this framework, bundling is vector addition, similarity is cosine similarity, binding is circular convolution, and unbinding is circular correlation, which can be approximated by circular convolution with the pseudo inverse of a vector. Given a convolutional binding operator, it is common to improve the efficiency of the binding and unbinding operations by conducting them in the Fourier domain. Indeed, Fourier HRRs are a variation on HRRs that is conducted entirely in the Fourier domain, and has been used in a number of neuromorphic applications34,81,82.Fig. 2VSA encodings and kernels for different action spaces.a Example action spaces used in our optimization tasks, including (i) trajectory, (ii) combinatorial, and (iii) graph-based spaces. A reference action from each space is shown: (i) a trajectory τ represented as waypoints connected by arrows, (ii) a combinatorial variable C displayed as a color-coded grid where each square represents a categorical value, and (iii) a directed graph representing a convolutional neural network architecture, with nodes as layers (colored by operation type) and arrows as connections103. b VSA-based representations of randomly sampled actions projected into a 3D space using locally linear embedding for visualization (actual representations are higher-dimensional). The black cross marks the reference action (e.g., τ) and colors of other markers indicate the associated kernel value (e.g., k(τ, ⋅ )). c The kernel values under VSA encodings. Each point represents a randomly sampled action, with insets showing example actions (in (i) the reference trajectory is plotted underneath in black and in (ii) overlap with the reference variable is shown). The y-axis corresponds to the cosine similarity between the VSA representation of the reference action (from a) and other actions, while the x-axis corresponds to a standard distance or similarity measure specific to each action space: (i) L2 distance between trajectories, (ii) categorical overlap similarity, and (iii) a random walk similarity measure for graphs. These results show that VSA-based embeddings induce meaningful similarity measures aligned with known metrics in each space. VSA encodings and kernels for different action spaces. a Example action spaces used in our optimization tasks, including (i) trajectory, (ii) combinatorial, and (iii) graph-based spaces. A reference action from each space is shown: (i) a trajectory τ represented as waypoints connected by arrows, (ii) a combinatorial variable C displayed as a color-coded grid where each square represents a categorical value, and (iii) a directed graph representing a convolutional neural network architecture, with nodes as layers (colored by operation type) and arrows as connections103. b VSA-based representations of randomly sampled actions projected into a 3D space using locally linear embedding for visualization (actual representations are higher-dimensional). The black cross marks the reference action (e.g., τ) and colors of other markers indicate the associated kernel value (e.g., k(τ, ⋅ )). c The kernel values under VSA encodings. Each point represents a randomly sampled action, with insets showing example actions (in (i) the reference trajectory is plotted underneath in black and in (ii) overlap with the reference variable is shown). The y-axis corresponds to the cosine similarity between the VSA representation of the reference action (from a) and other actions, while the x-axis corresponds to a standard distance or similarity measure specific to each action space: (i) L2 distance between trajectories, (ii) categorical overlap similarity, and (iii) a random walk similarity measure for graphs. These results show that VSA-based embeddings induce meaningful similarity measures aligned with known metrics in each space. It is sometimes necessary to represent indivisible concepts or objects that may serve as a referent to some high-level concept without defining its constituent elements. We could represent a concept or category, e.g., “retirement” or “animal”, by creating a discrete symbol that the system treats as having the semantic content of the concept it points to. Here discrete symbols are represented by vectors on the unit hyper-sphere. These are generated randomly by selecting their frequency components in the Fourier domain, and then converting them to the psuedo-time domain through the inverse Fourier transform. This differs from the original proposition of Plate83 for real-valued HRR symbols, who specified that vectors should be drawn from the distribution, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{N}}}}(0,d)$$\end{document}N(0,d). However, the representations we use for discrete symbols are equivalent to the inverse Fourier transform of Plate’s “circular vectors” with the addition of conjugate symmetry. Specifically, we generate a phase vector, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{a}}}}\in {{\mathbb{R}}}^{d}$$\end{document}a∈Rd, where elements of a are sampled uniformly from the interval [ − π, π]. Other sampling distributions can be used to generate a, or it may be set some other way, e.g., end-to-end learning. We further constrain a to have conjugate symmetry, to ensure the inverse Fourier transform does not generate imaginary components, and to be unit-length in the time domain, which places us in a strict subset of HRRs. We define our embedding of the symbol, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s\in {{{\mathcal{S}}}}$$\end{document}s∈S, in the high-dimensional space as: 1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\phi }_{{{{\mathcal{S}}}}}(s)={{{{\mathcal{F}}}}}^{-1}\left\{{{{{\rm{e}}}}}^{i{{{\bf{a}}}}}\right\},$$\end{document}ϕS(s)=F−1eia, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\mathcal{F}}}}}^{-1}$$\end{document}F−1 indicates the inverse Fourier transform, and the exponential function is applied to each element of ia. The kernel induced under this mapping is given in section “Kernels over Discrete Encodings”. To represent multiple entities, like symbols indicating the identities of several agents, we generate a unique ak for every entity. Thus, for a set of discrete symbols, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{S}}}}=\left\{{s}_{1},\ldots,{s}_{M}\right\}$$\end{document}S=s1,…,sM, we generate a corresponding set of phase vectors, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left\{{{{{\bf{a}}}}}_{1},\ldots,{{{{\bf{a}}}}}_{M}\right\}$$\end{document}a1,…,aM. Discrete symbol vectors play multiple roles within VSAs. They can be used to represent the values of categorical data, but they can also be used to impose structure on a vector representation. Chiefly, structure is imposed by using discrete symbol vectors to define the slot in slot-filler relationships. By analogy to programming languages, slots are like the names of variables, and the fillers are the values those variables take on. For example, sentences can be represented in a slot-filler manner with slots such as “subject” or “verb” specifying the functional roles of particular discrete data, such as “Bob” or “throw,” 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\,{\mbox{subject}}\otimes {\mbox{Bob}}+{\mbox{verb}}\otimes {\mbox{throw}}+{\mbox{object}}\otimes {\mbox{ball}}\,.$$\end{document}subject⊗Bob+verb⊗throw+object⊗ball. More generally, consider a multi-category or combinatorial variable C (e.g., an object with multiple properties that take on discrete values). There is a set of category slots \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\phi }_{{{{\mathcal{S}}}}}({s}_{i})$$\end{document}ϕS(si) (e.g., s1 = color and s2 = classification) each of which has an associated value \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\phi }_{{{{{\mathcal{V}}}}}_{i}}({v}_{i,j})$$\end{document}ϕVi(vi,j) (e.g., the possible colors are v1,1 = red, v1,2 = blue, … and possible classifications are v2,1 = door, v2,2 = box, … etc.). The mappings are labeled with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{S}}}}$$\end{document}S and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\mathcal{V}}}}}_{i}$$\end{document}Vi to indicate that there are different dictionaries for category slots and value types. The complete combinatorial variable C can be represented as 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\phi }_{{{{\mathcal{C}}}}}(C)={\sum}_{i=1}^{{\#} \, {{{\rm{of}}}} \, {{{\rm{categories}}}}}{\phi }_{{{{\mathcal{S}}}}}({s}_{i})\otimes {\phi }_{{{{{\mathcal{V}}}}}_{i}}({v}_{i,j})+{ \kappa } {\bigotimes}_{i=1}^{{\#} \,{{{\rm{of}}}} \, {{{\rm{categories}}}}}{\phi }_{{{{{\mathcal{V}}}}}_{i}}({v}_{i,j}).$$\end{document}ϕC(C)=∑i=1#ofcategoriesϕS(si)⊗ϕVi(vi,j)+κ⨂i=1#ofcategoriesϕVi(vi,j). The first term bundles all bound slot-filler pairs, κ = 0.1 is a weighting constant, and the second term is the bound combination of all values. As discussed later in section “Data Structures as Approximate Compositional Kernels”, purely bundling variables restricts the representation to additive kernels. To represent multiplicative kernels and capture interactions between input dimensions, the all-bound term is required. This could be generalized to sum over n-gram bound groups, assuming the category slots are ordered in a meaningful way84,85. An example of multi-category embeddings is shown in Fig. 2(ii). VSAs have been previously used to encode graphs78,86,87. In section “Experiments”, we consider an optimization problem defined over directed acyclic graphs with M labeled nodes, which we represent by 4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\phi }_{{{{\mathcal{G}}}}}(G)= \frac{1}{M}{\sum}_{i=1}^{M}{\phi }_{{{{\mathcal{N}}}}}({n}_{i})\otimes \left(\,{{\mbox{node}}}\_{{\mbox{label}}}\,\otimes {\phi }_{{{{\mathcal{L}}}}}({l}_{i})\,+\,\,{{\mbox{tail}}}\bigotimes \sum \limits_{j{{\rm{{\,where}}}}\,i\to j}{\phi }_{{{{\mathcal{N}}}}}({n}_{j})\right) \\ +\,\kappa {{ \otimes }_{i=1}^{M}} {\phi }_{{{{\mathcal{N}}}}}({n}_{i}) \otimes {\phi }_{{{{\mathcal{L}}}}}({l}_{i}) \otimes {\sum}_{j\,{{{\rm{where}}}}\,i \to j}{\phi }_{{{{\mathcal{N}}}}}({n}_{j}),$$\end{document}ϕG(G)=1M∑i=1MϕN(ni)⊗node_label⊗ϕL(li)+tail⨂ ∑j wherei→jϕN(nj)+κ⊗i=1MϕN(ni)⊗ϕL(li)⊗∑jwherei→jϕN(nj), where tail and node_label are slot vectors, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n}_{i},{n}_{j}\in {{{\mathcal{N}}}}$$\end{document}ni,nj∈N denote nodes, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${l}_{i}\in {{{\mathcal{L}}}}$$\end{document}li∈L is a label associated with the vertex. Nodes disconnected from all others are removed from the graph. Note that, like the multi-category embeddings, there is an all-bound term weighted by a constant κ = 0.1. Moving from discrete symbol representations to discrete ordered representations can be thought of as constructing vector representations of integers. An integer, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$j\in {{{\mathcal{J}}}}\subseteq {{{\mathcal{Z}}}}$$\end{document}j∈J⊆Z, can be represented by first selecting a basis vector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\mathcal{F}}}}}^{-1}\left\{{{{{\rm{e}}}}}^{i{{{{\bf{a}}}}}_{{{{\rm{J}}}}}}\right\}$$\end{document}F−1eiaJ, a randomly generated symbol as described in the previous section (i.e., aJ is a random phase vector). To represent an integer, j, the basis vector is bound with itself j times. We denote this as: 5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\phi }_{{{{\rm{J}}}}}(j)={\otimes }^{j}{{{{\mathcal{F}}}}}^{-1}\left\{{{{{\rm{e}}}}}^{i{{{{\bf{a}}}}}_{{{{\rm{J}}}}}}\right\}={{{{\mathcal{F}}}}}^{-1}\left\{{{{{\rm{e}}}}}^{i{{{{\bf{a}}}}}_{{{{\rm{J}}}}}\cdot j}\right\}.$$\end{document}ϕJ(j)=⊗jF−1eiaJ=F−1eiaJ⋅j. In contrast to discrete symbols, integer representations are used to represent values that are ordered and have a meaningful distance (and hence similarity) metric. To extend iterated binding to real-valued data we exploit the fact that convolution in the time domain is multiplication in the Fourier domain. Integer representations are trivially extended to real-valued data to produce a method known as fractional binding33,35 or fractional power encoding29,34. Because some of these methods were developed in the context of the Semantic Pointer Architecture19, they are sometimes known as Spatial Semantic Pointers (SSPs)35. We can thus represent real-valued data \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x\in {{{\mathcal{X}}}}\subseteq {\mathbb{R}}$$\end{document}x∈X⊆R as 6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\phi }_{{{{\mathcal{X}}}}}(x)={{{{\mathcal{F}}}}}^{-1}\left\{{{{{\rm{e}}}}}^{i{{{{\bf{a}}}}}_{{{{\mathcal{X}}}}}\frac{x}{\ell }}\right\},$$\end{document}ϕX(x)=F−1eiaXxℓ, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell \in {{\mathbb{R}}}^{+}$$\end{document}ℓ∈R+ is the length scale of the representation, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\bf{a}}}}}_{{{{\mathcal{X}}}}}$$\end{document}aX is the phase vector, and the exponentiation is applied element-wise, as above. This is similar to the method of RFFs9, in that it maps scalar inputs to a higher-dimensional feature space via complex exponentials of linear projections. However, unlike RFFs these representations are used with the HRR algebra to create embeddings of compositional structures. Provided that two variables are bound using the same basis vector, the dot product between fractional bound representations induces a kernel, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k({{{\bf{x}}}},{{{{\bf{x}}}}}^{{\prime} })={\phi }_{{{{\mathcal{X}}}}}{({{{\bf{x}}}})}^{T}{\phi }_{{{{\mathcal{X}}}}}({{{{\bf{x}}}}}^{{\prime} })$$\end{document}k(x,x′)=ϕX(x)TϕX(x′). The expected shape of the kernel is a function of the sampling distribution for the phase vector components. Thus, the similarity between continuous variables can be tuned to the needs of a particular application, as typically done with RFFs. In the case of (a)i ~ Uniform[ − π, π], the induced kernel is the sinc function27. This is a useful kernel because it converges to a point mass in the small bandwidth limit, i.e., sinc((i − j)/l) → δ(i − j) as l → 0. This encoding can be extended to m − dimensional data, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\bf{x}}}}\in {{{\mathcal{X}}}}\subseteq {{\mathbb{R}}}^{m}$$\end{document}x∈X⊆Rm, by replacing the phase vector, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\bf{a}}}}}_{{{{\mathcal{X}}}}}$$\end{document}aX, with a phase matrix, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\bf{A}}}}}_{{{{\mathcal{X}}}}}\in {{\mathbb{R}}}^{d\times m}$$\end{document}AX∈Rd×m, 7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\phi }_{{{{\mathcal{X}}}}}({{{\bf{x}}}})={{{{\mathcal{F}}}}}^{-1}\left\{{{{{\rm{e}}}}}^{i{A}_{{{{\mathcal{X}}}}}{{{\bf{x}}}}}\right\}.$$\end{document}ϕX(x)=F−1eiAXx. In this case, the phase matrix is selected such that the columns are independently generated random vectors. We refer to such an encoding scheme as Random SSPs (Rand-SSPs). Hexagonal SSPs In this work, we use a phase matrix that has been structured in a particular way. Specifically, the phase matrix is set so that the induced kernel is a sum of periodic kernels that mimic the neural activity of grid cells in the medial entorhinal cortex36. We have chosen this structure because it allows SSPs to be efficiently represented by neural populations and, as features for deep networks, outperforms Rand-SSPs on a number of classification and regression tasks36,88,89. We call the resulting feature representation Hexagonal SSPs (Hex-SSPs). Section “Hexagonal SSPs” provides the details of the Hex-SSP construction and a derivation of the kernel induced under this embedding. If we consider the space of trajectories, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{T}}}}$$\end{document}T, we can represent a trajectory τ = [x(t)]t∈[0, T] with SSPs as a bundle of time and location representations bound together in a single vector90: 8\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\phi }_{{{{\mathcal{T}}}}}(\tau )=\int_{0}^{T}{\phi }_{{{{\mathcal{X}}}}}({{{\bf{x}}}}(t))\otimes {\phi }_{T}(t)dt,$$\end{document}ϕT(τ)=∫0TϕX(x(t))⊗ϕT(t)dt, where t is time and T is the maximum trajectory duration. Pragmatically, instead of computing the exact integral over the trajectory τ, we often sample the trajectory and encode a bundle of waypoints bound with time: 9\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\phi }_{{{{\mathcal{T}}}}}(\tau )={\sum}_{i=1}^{n}{\phi }_{{{{\mathcal{X}}}}}({{{\bf{x}}}}({t}_{i}))\otimes {\phi }_{T}({t}_{i}).$$\end{document}ϕT(τ)=∑i=1nϕX(x(ti))⊗ϕT(ti). If we want to represent trajectories of multiple agents, we can generate random symbol vectors for each agent, bind them to the corresponding trajectory embeddings, and represent the collection in one bundled vector.10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sum}_{i=1}^{\#\,{{{\rm{of}}}}\, {{{\rm{agents}}}}}{\phi }_{{{{\rm{agts}}}}}({s}_{i})\otimes {\phi }_{{{{\mathcal{T}}}}}({\tau }_{i}),$$\end{document}∑i=1#ofagentsϕagts(si)⊗ϕT(τi), where ϕagts(si) are randomly generated symbol-vectors for the agents whose trajectories are being optimized. The encoding in Equation (10) serves as the projection into the feature space used in the experiments presented in this work. Note that regardless of the trajectory length or the number of agents involved, the dimensionality of the SSP vector representation does not change. SSP-BO algorithm Algorithm 1 SSP Bayesian Optimization (SSP-BO). N is the total sampling budget for the algorithm, β is the inverse variance parameter, α was chosen to be 0.01, f( ⋅ ) is the target function being optimized, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{X}}}}$$\end{document}X is the domain of f( ⋅ ). γc is a scaling parameter that can be used to further control the influence of the exploration term. 1: Procedure SSP-BO (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N,f(\cdot ),\frac{1}{\beta },\alpha,\lambda$$\end{document}N,f(⋅),1β,α,λ) 2: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\bf{m}}}}}_{0},\,{\Sigma }_{0},\,{\Sigma }_{0}^{-1}\leftarrow {{{\bf{0}}}},\,\alpha {{{\bf{I}}}},\,{\alpha }^{-1}{{{\bf{I}}}}$$\end{document}m0,Σ0,Σ0−1←0,αI,α−1I 3: for k ← 1 to N do 4: μn(θ) ≜ mn ⋅ θ 5: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sigma }_{n}(\theta )\triangleq \sqrt{\frac{1}{\beta }+{\theta }^{{{{\rm{T}}}}}{\Sigma }_{n-1}\theta }$$\end{document}σn(θ)≜1β+θTΣn−1θ 6: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\theta }^{*}\leftarrow \arg {{\max }_{\theta \in {{{\mathcal{S}}}}^{d-1}}}\,\left[{\mu }_{n}(\theta )+{\lambda }_{n}{\sigma }_{n}(\theta )\right]$$\end{document}θ*←argmaxθ∈Sd−1μn(θ)+λnσn(θ) 7: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\bf{x}}}}}_{n}\leftarrow \arg {{\max }_{{{{\bf{x}}}}\in {{{\mathcal{X}}}}}}\,\phi ({{{\bf{x}}}})\cdot {\theta }^{*}$$\end{document}xn←argmaxx∈Xϕ(x)⋅θ* ⊳ Decode optimal SSP 8: fn ← f(xn) 9: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\bf{m}}}}}_{n},{\Sigma }_{n},{\Sigma }_{n}^{-1}\leftarrow {{{\rm{updateBLR}}}}\left({{{{\bf{m}}}}}_{n-1},{\Sigma }_{n-1},{\Sigma }_{n-1}^{-1},{{{{\bf{x}}}}}_{n},{f}_{n}\right)$$\end{document}mn,Σn,Σn−1←updateBLRmn−1,Σn−1,Σn−1−1,xn,fn⊳See eqs. (14)–(16) 10: end for 11: end procedure SSP-BO follows the standard BO framework, adapted to operate over VSA representations (section “Kernel Approximations with VSAs”). At each iteration, the agent selects an action \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\bf{x}}}}}_{n}\in {{{\mathcal{X}}}}$$\end{document}xn∈X by optimizing an acquisition function, observes a reward f(xn), and updates its surrogate model. This process repeats until a sampling budget N is exhausted. Surrogate model We model the reward function using Bayesian linear regression (BLR; Fig. 3), which provides a probabilistic surrogate over VSA embeddings. Each action x is mapped to a fixed-dimensional vector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi ({{{\bf{x}}}})\in {{\mathbb{R}}}^{d}$$\end{document}ϕ(x)∈Rd, and the predicted reward is modeled as a Gaussian distribution: 11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{f}({{{\bf{x}}}}) \sim {{{\mathcal{N}}}}(\mu ({{{\bf{x}}}}),{\sigma }^{2}({{{\bf{x}}}})).$$\end{document}f^(x)~N(μ(x),σ2(x)). The parameters of this distribution are computed using standard BLR formulas [66 Section 3.3]: 12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mu }_{n}({{{\bf{x}}}})={{{{\bf{m}}}}}_{n-1}^{T}\phi ({{{\bf{x}}}}),$$\end{document}μn(x)=mn−1Tϕ(x),13\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sigma }_{n}^{2}({{{\bf{x}}}})=\frac{1}{\beta }+\phi {({{{\bf{x}}}})}^{T}{\Sigma }_{n-1}\phi ({{{\bf{x}}}}),$$\end{document}σn2(x)=1β+ϕ(x)TΣn−1ϕ(x), where μn(x) is the posterior mean of the predicted reward at x, parameterized by the mean vector mn−1, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sigma }_{n}^{2}({{{\bf{x}}}})$$\end{document}σn2(x) is the posterior variance, parameterized by the covariance matrix Σn−1. The precision parameter β is set as the inverse variance of the observed rewards and is estimated from the initial samples. The mean vector and covariance matrix are updated incrementally with each new observation.Fig. 3Function posterior estimated using BLR and SSP encoding as the number of samples increases.Red dots indicate sample points, the blue line indicates the estimated function mean, the shaded regions indicate the prediction standard deviation, and the gray line is the true function. a The estimated function using only one observation, where uncertainty is undefined. b After ten samples the mean begins to approach the true function, although the uncertainty is high. c With 20 samples, we obtain an accurate function estimate with reasonable uncertainty bounds. Function posterior estimated using BLR and SSP encoding as the number of samples increases. Red dots indicate sample points, the blue line indicates the estimated function mean, the shaded regions indicate the prediction standard deviation, and the gray line is the true function. a The estimated function using only one observation, where uncertainty is undefined. b After ten samples the mean begins to approach the true function, although the uncertainty is high. c With 20 samples, we obtain an accurate function estimate with reasonable uncertainty bounds. Online updates We use rank-one updates to update the inverse covariance matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma }_{n}^{-1}$$\end{document}Σn−1 and thus update the covariance matrix Σn online via the matrix inversion lemma (Equation (15)), avoiding costly inversions. Online updates to the BLR parameters are given by 14\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma }_{n}^{-1}={\Sigma }_{n-1}^{-1}+\beta \phi ({{{{\bf{x}}}}}_{n})\phi {({{{{\bf{x}}}}}_{n})}^{T},$$\end{document}Σn−1=Σn−1−1+βϕ(xn)ϕ(xn)T,15\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma }_{n}={\Sigma }_{n-1}-\frac{{\Sigma }_{n-1}\phi ({{{{\bf{x}}}}}_{n})\phi {({{{{\bf{x}}}}}_{n})}^{T}{\Sigma }_{n-1}}{\frac{1}{\beta }+\phi ({{{{\bf{x}}}}}_{n}){\Sigma }_{n-1}\phi {({{{{\bf{x}}}}}_{n})}^{T}}\,,$$\end{document}Σn=Σn−1−Σn−1ϕ(xn)ϕ(xn)TΣn−11β+ϕ(xn)Σn−1ϕ(xn)T,16\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\bf{m}}}}}_{n}={\Sigma }_{n}{\Sigma }_{n-1}^{-1}{{{{\bf{m}}}}}_{n-1}+{\Sigma }_{n}\beta \phi ({{{{\bf{x}}}}}_{n})f({{{{\bf{x}}}}}_{n}).$$\end{document}mn=ΣnΣn−1−1mn−1+Σnβϕ(xn)f(xn). Acquisition function Actions are selected by maximizing an acquisition function, ψn(x). We use the Upper Confidence Bound [UCB; 91–94] criterion to balance exploration and exploitation. The acquisition function at iteration n is: 17\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\psi }_{n}({{{\bf{x}}}})={\mu }_{n}({{{\bf{x}}}})+\lambda {\sigma }_{n}({{{\bf{x}}}})$$\end{document}ψn(x)=μn(x)+λσn(x)18\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$={{{{\bf{m}}}}}_{n-1}^{{{{\rm{T}}}}}\phi ({{{\bf{x}}}})+\lambda \sqrt{\frac{1}{\beta }+\phi {({{{\bf{x}}}})}^{{{{\rm{T}}}}}{\Sigma }_{n-1}\phi ({{{\bf{x}}}})}.$$\end{document}=mn−1Tϕ(x)+λ1β+ϕ(x)TΣn−1ϕ(x). where λ = 1 is a scalar that governs the trade-off between uncertainty-driven exploration and predicted reward. Optimization in embedding space To select the next action, we optimize the acquisition function in the high-dimensional VSA space: 19\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\,{\mbox{Optimize:}}\,\quad {\theta }^{*}={{{{\rm{arg}}}\; {{\rm{max}}}}_{\theta \in {{{{\mathcal{S}}}}}^{d-1}}}\,{{{{\bf{m}}}}}_{n-1}^{{{{\rm{T}}}}}\theta+\lambda \sqrt{{\beta }^{-1}+{\theta }^{{{{\rm{T}}}}}{\Sigma }_{n-1}\theta },$$\end{document}Optimize:θ*=argmaxθ∈Sd−1mn−1Tθ+λβ−1+θTΣn−1θ,20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\,{\mbox{Decode:}}\,\quad {{{{\bf{x}}}}}_{n}={{{{\rm{arg}}}\;{{\rm{max}}}}_{{{{\bf{x}}}}\in {{{\mathcal{X}}}}}}\ {\theta }^{*}\cdot \phi ({{{\bf{x}}}}).$$\end{document}Decode:xn=argmaxx∈Xθ*⋅ϕ(x). where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\mathcal{S}}}}}^{d-1}$$\end{document}Sd−1 is the d-dimensional unit hypersphere. Note that θ* may not correspond exactly to any valid action embedding – i.e., θ* might not lie in the set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{\phi ({{{\bf{x}}}}):{{{\bf{x}}}}\in {{{\mathcal{X}}}}\}$$\end{document}{ϕ(x):x∈X}. Thus, we decode it by selecting the action whose embedding is most similar in feature space. This decoding step is conceptually similar to projection methods in constrained optimization, but in our case is based on similarity rather than geometric projection. By operating in the embedding space, SSP-BO transforms a complex optimization problem in a potentially structured or discrete action space, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{X}}}}$$\end{document}X, into a continuous optimization problem on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\mathcal{S}}}}}^{d-1}$$\end{document}Sd−1, at the cost of approximation. The objective is smooth and defined on a compact domain, lending itself to efficient optimization via gradient ascent or neural dynamics. This formulation also lends itself to neuromorphic implementation, as the same recurrent neural architecture can perform sample selection across diverse data types and structures (e.g., discrete, continuous, sets, graphs, and trajectories). However, the task of decoding θ* into an appropriate action, x*, can be challenging, see section “Feature Decoding” for more details. The complete algorithm is given in Algorithm 1. Experiments We now demonstrate that VSA-based representations, when used in the acquisition function Equation (18), support effective optimization. We compare SSP-BO against various BO baselines that optimize directly in the action space \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{X}}}}$$\end{document}X. Our experiments span a range of action types and problem structures (Fig. 1(c)). First, we evaluate SSP-BO on continuous function optimization using the Hex-SSP representation. Second, we test SSP-BO on discrete action spaces, including combinatorial optimization and a neural architecture search problem. These tasks assess whether VSA representations support efficient optimization over symbolic and structured domains. Third, we evaluate SSP-BO on multi-agent trajectories, demonstrating the method’s ability to optimize in mixed, high-dimensional spaces. In all domains, we find that SSP-BO performs better than or comparably to BO baselines. We also conduct runtime profiling and complexity analysis, showing that SSP-BO yields significant computational advantages due to its fixed-size embedding and efficient updates. Finally, we demonstrate that the algorithm can be implemented on neuromorphic hardware using spiking neurons, highlighting its potential for energy-efficient, brain-inspired optimization. Previously, randomly generated SSPs have been used as a feature space for BO95. In this work, we show that Hex-SSP features are more effective than Rand-SSP features for BO, although both can be used. Because we test these algorithms on standard target functions, we know what the maximum value of these functions is, so we can score the algorithms on the basis of regret. Regret is the difference between the reward obtained, f(xn), and the best reward, f(x*). We report the average regret at sample number n, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${R}_{n}=\frac{1}{n}{\sum }_{i=1}^{n}f({x}^{*})-f({x}_{n})$$\end{document}Rn=1n∑i=1nf(x*)−f(xn). Lower values of this quantity are better. Figure 4a shows the performance of SSP-BO on three common global optimization functions, as well as the time complexity of the algorithms compared to a baseline algorithm implemented using GP and a GP approximated with RFFs (see section “Baseline Implementations for BO” and Supplementary Note 3, “Baseline Methods” for details). As anticipated, SSP-BO has constant time complexity, and constant memory complexity (see Supplementary Fig. 1). Note that the time for RFF-BO is also constant, as it too uses a kernel approximation. It is in fact slightly faster than SSP-BO because RFF-BO optimizes in the original action space and therefore does not require a decoding step. However, RFF-BO has higher regret on all test functions. SSP-BO with Hex-SSPs achieves the best regret performance. Furthermore, we find that the Hex-SSP results were stable even when reduced to 25 dimensions (Supplementary Fig. 3).Fig. 4SSP-BO offers bounded execution time and sample selection on neuromorphic hardware, while achieving regret comparable to standard implementations.a Plots (i–iii) show the average regret Rt (lower is better); plot (iv) shows the sample selection time (lines 4-7 and 9 in Algorithm 1), which includes the decoding step and does not include the function evaluation time. Shaded regions are 95% bootstrap confidence intervals for 30 trials with sampling budgets of N = 200. There are an additional 10 random samples that are used to initialize the surrogate models. This stage is not included in the plots, but the initial samples do contribute to the computed regret. SSP-BO-Hex achieves better or equal regret performance to GP (Matérn) while showing a substantial improvement in selection time. b Results when sample selection is performed by an spiking RNN. Plots (i–iii) show the average regret and 95% bootstrap confidence intervals for 5 trials with sampling budgets of N = 100 using different hardware to simulate the RNN. SSP-BO offers bounded execution time and sample selection on neuromorphic hardware, while achieving regret comparable to standard implementations. a Plots (i–iii) show the average regret Rt (lower is better); plot (iv) shows the sample selection time (lines 4-7 and 9 in Algorithm 1), which includes the decoding step and does not include the function evaluation time. Shaded regions are 95% bootstrap confidence intervals for 30 trials with sampling budgets of N = 200. There are an additional 10 random samples that are used to initialize the surrogate models. This stage is not included in the plots, but the initial samples do contribute to the computed regret. SSP-BO-Hex achieves better or equal regret performance to GP (Matérn) while showing a substantial improvement in selection time. b Results when sample selection is performed by an spiking RNN. Plots (i–iii) show the average regret and 95% bootstrap confidence intervals for 5 trials with sampling budgets of N = 100 using different hardware to simulate the RNN. We evaluate our approach on two combinatorial optimization tasks: a synthetic pest control task96 and an RNA inverse folding task97. For comparison, we use benchmark results from 98, which include various GP-based Bayesian optimization methods such as COMBO96, BOiLS99, BODi100, and BOSS101. Each method employs different combinatorial kernels and optimization algorithms that operate directly in the combinatorial action space (see Supplementary Table II). Some methods use computational strategies to manage the cubic scaling of exact GP inference (e.g., Casmopolitan102 dynamically constructs the GP within local trust regions). In contrast, our method approximates a GP via VSA encodings and performs gradient-based optimization directly in the embedding space. In Fig. 5a, we report the best objective value rather than regret, as the true optimal value is unknown for these tasks. In these tasks, lower objective values are better. Within a budget of N = 200, our approach achieves a best objective value within the 95% confidence intervals of the top-performing BO methods in ref. 98, demonstrating competitive performance while substantially reducing computation time. The total time spent by SSP-BO planning actions and updating its surrogate model is 205 to 3891 times faster than the total time for the other BO methods on the pest control task and 176 to 2763 times faster on the RNA inverse folding task. While SSP-BO’s sample efficiency is worse than some methods on the pest control task, it still achieves a good objective value in a fraction of the time–even when function evaluation time is included. In particular, the total time SSP-BO takes to sample and evaluate 200 samples is at least 30 times less than the time the best-performing baseline (SSK) takes to sample and evaluate 100 samples.Fig. 5VSA allow representation and fast optimization over combinatorial spaces.a VSAs allow representation and optimization over combinatorial/categorical spaces. Plots (i–ii) show the best objective function value (lower is better for these two tasks); plot (iii) shows sample selection time on a log scale. In all figures, shaded regions are 95% bootstrap confidence intervals for 10 trials with sampling budgets of N = 200. SSP-BO again shows a substantial improvement in sample selection times. b SSP-BO comparable to state-of-the-art baselines on robotics tasks. (i–iii) show the performance of SSP-BO and baselines in terms of largest reward achieved as a function of the number of samples. In all plots, the lines show the mean of 10 runs (each run initialized with a different random seed); shaded regions indicate 95% confidence intervals. BoTorch leads on a simple Box Reach task (i), SSP-BO attains comparable performance on the more advanced Belt Stretch task with deformables (ii), and finally SPP-BO outperforms BoTorch and other baselines on the PSR planetary exploration task with four agents (iii). c SSP-BO speeds up BO on robotic tasks. (i) The values of SSP dimensionality, d, and number of samples, n, for which SSP-BO is more efficient than exact GP-based BO in terms of time complexity asymptotics (shown by the shaded region). Exact GP-BO has an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({n}^{3})$$\end{document}O(n3) time complexity, while SSP-BO is constant in n but quadratic in d, i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{O}}}}({d}^{2})$$\end{document}O(d2). Consequently, the instantaneous sample point selection for SSP-BO is an improvement over naive GP BO when \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d < {n}^{\frac{3}{2}}$$\end{document}d