提出新型向量符号记忆清理方法，速度提升至线性对数级。
Linearithmic Clean-up for Vector-Symbolic Key-Value Memory with Kroneker Rotation Products
- 用克罗内克旋转矩阵构造代码本，实现高效清理
- 清理时间复杂度降至O(N log N)，空间仅需O(N)
- 代码本可压缩存储，适合大规模向量系统
当前向量符号架构（VSAs）的计算瓶颈在于从架构中检索出的噪声向量需进行‘清理’。传统清理方式将噪声向量与原型向量构成的‘代码本’逐一比对，时间复杂度为二次或类似级别。本文提出一种基于克罗内克旋转矩阵的新代码本表示方法，支持高效清理，清理时间复杂度为线性对数级，即O(N log N)，其中N为向量维度，也等于代码本中的向量数量。清理空间复杂度为O(N)。此外，代码本无需显式存储：其可仅以O(log N)空间表示，代码本中任意向量可在O(N)时间和空间内生成。同时，渐近内存容量与标准方法相当。计算机实验验证了上述结果，表明其相比基线VSA技术具备数个数量级的可扩展性。
原文摘要 · Abstract (English)
A computational bottleneck in current Vector-Symbolic Architectures (VSAs) is the ``clean-up'' step, which decodes the noisy vectors retrieved from the architecture. Clean-up typically compares noisy vectors against a ``codebook'' of prototype vectors, incurring computational complexity that is quadratic or similar. We present a new codebook representation that supports efficient clean-up, based on Kroneker products of rotation-like matrices. The resulting clean-up time complexity is linearithmic, i.e. $\mathcal{O}(N\,\text{log}\,N)$, where $N$ is the vector dimension and also the number of vectors in the codebook. Clean-up space complexity is $\mathcal{O}(N)$. Furthermore, the codebook is not stored explicitly in computer memory: It can be represented in $\mathcal{O}(\text{log}\,N)$ space, and individual vectors in the codebook can be materialized in $\mathcal{O}(N)$ time and space. At the same time, asymptotic memory capacity remains comparable to standard approaches. Computer experiments confirm these results, demonstrating several orders of magnitude more scalability than baseline VSA techniques.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。