A New Unified Memory Design for AI Systems

In the paper's words

Memory architectures for modern AI systems are fragmented across hierarchical similarity indexes, append‑only logs, and relational graphs, causing latency, storage duplication, and provenance inconsistencies. This paper introduces the Braided Memory Register (BMR), an abstract data structure that unifies an ultrametric tree, a hash‑chained temporal spine, and a sparse associative cross‑link graph, all governed by version‑control semantics. Formal definitions are given, and analytic derivations yield (i) logarithmic ultrametric descent cost, (ii) a retrieval‑time bound of O(log N + k + d_max), (iii) a storage overhead of ≈ 2× for a balanced binary tree, (iv) a birthday‑collision probability of 4.3×10^-60 for a 256‑bit chain over 10⁹ commits, and (v) a speedup of 4.2×10⁴ over linear scan for N=10⁶ memories.

The abstract, verbatim; every line below is quoted from the text.

What it claims

that a single composite object can deliver logarithmic retrieval and provable integrity—would be falsified if a concrete update protocol were shown to require super‑constant readdressing of existing commits (e.g., rehashing a linear fraction of the tree on each insertion). Demonstrating such a protocol would invalidate the storage‑overhead and retrieval‑time derivations.

Numbers it reports

1. Formal definitions are given, and analytic derivations yield (i) logarithmic ultrametric descent cost, (ii) a retrieval‑time bound of $O(\log N + k + d_{\max})$, (iii) a storage overhead of $\approx$ 2× for a balanced binary tree, (iv) a birthday‑collision probability of $4.3\times10^{-60}$ for a 256‑bit chain over $10^{9}$ commits, and (v) a speedup of $4.2\times10^{4}$ over linear scan for $N=10^{6}$ memories.

   from Abstract

2. Quantitative analysis for a system with $N=10^{6}$ memories: depth $L=20$, speedup $4.2\times10^{4}$ over linear scan, storage overhead $\approx$ 2×, and hash‑collision probability $4.3\times10^{-60}$ (Section 4).

   from 1. Introduction

3. A graph database (e.g., Neo4j) to store $G$.

   from 3.4 Implementation Sketch (Quipu‑Net)

4. Assuming 32 bytes for the 256‑bit address and 32 bytes for a relation label, each edge occupies $64$ bytes, yielding $$ \text{Cross‑link storage} = 4\times10^{6}\times64\ \text{B} = 2.56\times10^{8}\ \text{B} \approx 256\ \text{MiB}. $$

   from 4.5 Cross‑link storage

5. A software prototype (the “quipu‑net”) should be built with: A balanced binary FAISS IVF index for $N=10^{6}$ vectors, A Merkle‑tree log for $n=10^{9}$ commits (simulated with a smaller $n$ for feasibility), A Neo4j graph storing $k=4$ cross‑links per node.

   from 7.3 Minimal Next Experiment

6. The experiment would measure actual retrieval time (comparisons and wall‑clock latency) and verify that it matches the predicted $24$ comparisons and $\approx$ 5 ms latency on commodity hardware.

   from 7.3 Minimal Next Experiment

How it is done

1. Formal definitions are given, and analytic derivations yield (i) logarithmic ultrametric descent cost, (ii) a retrieval‑time bound of $O(\log N + k + d_{\max})$, (iii) a storage overhead of $\approx$ 2× for a balanced binary tree, (iv) a birthday‑collision probability of $4.3\times10^{-60}$ for a 256‑bit chain over $10^{9}$ commits, and (v) a speedup of $4.2\times10^{4}$ over linear scan for $N=10^{6}$ memories.

   from Abstract

2. Derivation of retrieval‑time complexity $O(\log N + k + d_{\max})$ and proof of a monotonic energy guarantee (Section 4).

   from 1. Introduction

3. The BMR is defined as the tuple $$\mathcal{B} = (T,\,C,\,G,\,\mathcal{H})$$ where: $T$ is a finite ultrametric tree with branching factor $b$ and depth $L$, yielding $N = b^{L}$ leaves.

   from 3.1 Formal Model of the Braided Memory Register

4. Given a cue vector $\mathbf{q}$, retrieval proceeds in three stages: Ultrametric descent.

   from 3.2 Retrieval Procedure

What would falsify it

1. The central claim—that a single composite object can deliver logarithmic retrieval and provable integrity—would be falsified if a concrete update protocol were shown to require super‑constant readdressing of existing commits (e.g., rehashing a linear fraction of the tree on each insertion).

   from 6.3 Falsifiability

2. Falsification condition: observed retrieval time scaling faster than $O(N^{0.6})$ would contradict the logarithmic claim.

   from 7.3 Minimal Next Experiment

Where the claim stops

1. Rebalancing under a content‑addressed regime remains an open problem.

   from 6.1 Limitations

2. The headline cost assumes reduction from $64$ to $4$ candidates; if the filter fails, cost rises to $84$ comparisons, still faster than linear scan but with reduced precision.

   from 6.1 Limitations

3. By construction, any update $\Delta$ that inserts vectors only at leaves does not increase the first term, and cross‑link updates are accepted only if they reduce the second term.

   from 3.3 Consistency Guarantees

Where to read

1. Abstract171 words · 1 min
2. 1. Introduction229 words · 1 min
3. 2. Background and Related Work180 words · 1 min
4. 3. Methods384 words · 2 min
5. 4. Analysis386 words · 2 min
6. 5. Results119 words · 1 min
7. 6. Discussion319 words · 1 min
8. 7. Practical Implications and Engineering Pathways355 words · 2 min
9. 8. Conclusion99 words · 1 min
10. Provenance and AI Involvement225 words · 1 min