Aperon Technical Report: Hierarchical No-Pointer Tangent-Local Search for High-Dimensional Approximate Nearest Neighbors Yong Fu Substratum Labs [email protected]
arXiv:2606.08813v1 [cs.DC] 7 Jun 2026
Abstract We present HNTL (Hierarchical No-pointer Tangent-Local), the core vector indexing and candidate generation framework of the Aperon vector memory system. Proximity graphs (e.g., HNSW) incur a heavy pointer tax in memory overhead and induce irregular memory accesses that stall CPU pipelines. HNTL resolves this by partitioning the high-dimensional space into local, coherent grains, representing vectors as low-dimensional coordinates on local tangent spaces, and scanning them sequentially using a pointerless Block-SoA (Structure-of-Arrays) layout. On anisotropic manifold data (𝑑 = 768, 𝑁 = 10,000), local PCA captures 96.3% of the variance, allowing HNTL to achieve a final Rerank Recall@10 of 1.0000 with a candidate pool size of only 𝐶 = 20 vectors. Hardware profiling via Apple kperf CPU Performance Monitoring Unit (PMU) counters demonstrates a 3.61x speedup (4.137 ns/vector vs. 14.951 ns/vector) for our NEON auto-vectorized Rust Block-SoA scan engine over standard pointer-chasing graph traversals, driven by a 3.59× IPC (Instructions Per Cycle) and near-zero L1/L2 data cache misses.
Keywords approximate nearest neighbor, vector database, SIMD, Block-SoA, tangent-local projection, PCA quantization
1
Introduction & Background
High-dimensional approximate nearest neighbor (ANN) search is a core primitive in modern machine learning systems, including retrieval-augmented generation (RAG) and long-running cognitive agents. Traditional approaches range from locality-sensitive hashing (LSH) [3] to product quantization (PQ) [4] and its optimized variants (OPQ) [2]. In production, standard vector databases rely on proximity graphs (e.g., HNSW [7] or graph implementations in FAISS [1, 5]), which chase memory pointers during traversal. This design has two critical flaws for agent environments: (1) The Pointer Tax: Graph links frequently exceed raw vector data in size, requiring substantial DRAM. (2) Cognitive Impedance: Long-running agents require transactional properties like instant zero-copy branching (counterfactual reasoning), snapshots, and unified mixed-recall (vector similarity combined with temporal, spatial, and symbolic filters). To resolve these limitations, the production core of the Aperon database [9] is implemented in Rust to guarantee memory safety, concurrency, and high-performance execution. Aperon resolves the pointer tax by introducing the HNTL (Hierarchical No-pointer Tangent-Local) framework. Mathematically, ,
HNTL abandons graph links completely by partitioning the vector space into localized grains and projecting vectors onto lowdimensional local tangent spaces. Algorithmically, searching for nearest neighbors within a grain is transformed into a sequential local scan rather than a pointer-chasing graph traversal. Physically, this scan is implemented using a pointerless, cache-aligned BlockSoA memory layout, enabling the CPU to run SIMD-accelerated execution with near-zero cache misses. To resolve cognitive impedance, HNTL’s localized grain structure is mapped directly to Aperon’s immutable Memory SSTable (LogStructured Memory Segment) architecture. Because grains are selfcontained and geographically isolated, updating or adding vectors does not trigger global graph re-wiring. This allows the database to support instant, zero-copy branching (via copy-on-write segment forks for parallel counterfactual simulations) and simplifies mixedrecall queries, as symbolic or temporal filters can be checked in-situ within the sequential scan loop. Specifically, the system is structured around a hierarchical routing plane and a dual-mode query planner: • Mode A (Self-Contained): Performs online vector reconstruction directly in DRAM from local projections, bypassing disk reads completely. • Mode B (Tiered Filter): Uses a hot DRAM-resident manifold index (< 8% HNSW footprint) as a candidate generator, loading raw vectors from cold storage (SSD/mmap) for exact re-ranking.
2
System Architecture & Design
The Aperon database engine is structured around three primary layers to enable high-efficiency agent memory storage and retrieval (see Figure 1): • Log-Structured SSTable Layer: Consists of immutable memory segments on disk or memory-mapped files. Each segment groups raw records and their index access paths in contiguous, pointerless Block-SoA structures to enable hardware-friendly linear scanning. • Hierarchical Routing Plane: A coarse centroid index (routing table) that maps queries to matching candidate grains, pruning grains that fail a query-specific envelope filter. • Dual-Mode Query Planner: Dynamically schedules query tasks. Under Mode A, it reconstructs approximate vectors directly from tangent space coordinates. Under Mode B, it routes queries to candidates before performing exact L2 reranking.
2.1
Query Execution Lifecycle
When a query vector 𝑞 ∈ R𝑑 is submitted to the HNTL engine, it executes through the following stages (as shown in Figure 1):
(1) Centroid Routing: The engine calculates the Euclidean distance between 𝑞 and all grain centroids 𝜇𝑔 in the global routing plane, selecting the top-𝑃 (e.g., 𝑛𝑝𝑟𝑜𝑏𝑒) closest candidate grains. (2) Manifold Projection & Filtering: For each candidate grain, 𝑞 is projected onto the local PCA basis to produce subspace coordinate 𝑧𝑞,𝑔 and residual 𝑟𝑞 . The Quantization Envelope Filter checks for coordinate saturation; if coordinates clip across more than 25% of dimensions, the grain is pruned. (3) Block-SoA Scanning: The SIMD scan engine sequentially scans the remaining candidate grains in DRAM using the Block-SoA layout, computing distance approximations using integer register math. (4) Query Planner Resolution: • Mode A (Self-Contained): The approximate nearest neighbors are returned directly from the DRAM-based scan results. • Mode B (Tiered Filter): The query planner fetches the original high-dimensional vectors corresponding to the DRAM candidate set from cold storage (SSD or memorymapped segments) and performs exact float32 L2 re-ranking.
2.2
enabling integer SIMD calculations: 𝑧ˆ = round
2.3
𝑟 Δres
(5)
(6)
Hierarchical Centroid Routing
The "Hierarchical" aspect of HNTL is realized through a two-tier search process that combines global coarse routing with local finegrained scanning: (1) Global Routing Plane (First Level): The index maintains a routing plane consisting of grain centroids 𝜇𝑔 ∈ R𝑑 (𝑔 = 1 . . . 𝐺). For a query 𝑞 ∈ R𝑑 , we compute its distance to all centroids in the ambient space and select the top-𝑃 (e.g., 𝑛𝑝𝑟𝑜𝑏𝑒) closest grains. This limits the scan to a small set of candidate grains, achieving sub-linear retrieval time. (2) Local Manifold Scan (Second Level): Within each of the 𝑃 selected grains, the query is projected to the local tangent space, and a sequential SIMD scan is executed over the grain’s Block-SoA blocks. To protect against distance distortion from out-of-subspace queries, HNTL integrates a Quantization Envelope Filter directly into the routing phase. When the query is projected into a candidate grain’s local PCA space, we check for coordinate saturation (clipping at the boundaries of the signed 16-bit range). If coordinates saturate across more than a threshold fraction of dimensions (e.g., 25%), the grain is flagged as structurally incompatible with the query and pruned from the search path before the local scan begins.
2.4
Block-SoA Memory Layout
Per-grain data is grouped into cache-line-aligned blocks of size 𝐵 (e.g., 𝐵 = 64). Each block is stored contiguously in memory with coordinates arranged dimension-major to enable direct SIMD loading. For a block of size 𝐵, local tangent dimension 𝑘, and residual sketch dimension 𝑠, the total storage per block is:
(1) Mean Centering: Centering the input vector 𝑣 ∈ R𝑑 relative to the local grain centroid: (1)
BlockBytes = 𝐵 · (2𝑘 + 𝑠 + 6) bytes
(2) Subspace Projection: Projecting the centered vector onto the local PCA basis 𝑊𝑔 to obtain low-dimensional tangent space coordinates:
(7)
For 𝐵 = 64, 𝑘 = 16, and 𝑠 = 8, each block is exactly 2816 bytes, perfectly aligned to L1/L2 cache line size boundaries.
(2)
3 Implementation & Experimental Results 3.1 Hardware Setup and Compilation
(3) Residual Calculation: Reconstructing the subspace vector 𝑣˜ = 𝑊𝑔 𝑧 and calculating the orthogonal projection error vector: 𝑒 = 𝑣 ′ − 𝑊𝑔 𝑧 ∈ R𝑑 (3)
Following database vectorization practices [6, 8], the low-level SIMD scan kernels are designed to process coordinates sequentially within registers. For hardware evaluation, the prototype scan engine is written in Rust and compiled using rustc -C opt-level=3 -C target-cpu=native on an Apple M2 Max CPU (arm64, 32 GB unified memory, macOS 15) and an Intel Xeon workstation (AVX2/AVX512). ARM NEON and x86 AVX2/AVX-512 vector execution lanes are auto-vectorized directly by the compiler.
(4) Residual Norm: Computing the squared 𝐿2 norm of the residual vector to represent out-of-subspace energy: 𝑟 = ∥𝑒 ∥ 22 ∈ R
𝑟ˆ = round
𝐷 (𝑞, 𝑥𝑖 ) ≈ ∥𝑧𝑞 − 𝑧𝑖 ∥ 2 + 𝑟𝑞 + 𝑟𝑖
HNTL Subspace Projection
𝑧 = 𝑊𝑔⊤ 𝑣 ′ ∈ R𝑘
Δ
,
For a query 𝑞 and a database vector 𝑥𝑖 , their quantized representations 𝑧ˆ𝑞 , 𝑟ˆ𝑞 and 𝑧ˆ𝑖 , 𝑟ˆ𝑖 are used to compute the distance approximation:
The core idea of HNTL (Hierarchical No-pointer Tangent-Local) is that while high-dimensional vector embeddings generally occupy a huge global space, vectors in a localized neighborhood (a grain) tend to lie on or near a low-dimensional flat surface (a tangent space). By exploiting local geometric coherence, HNTL represents vectors using low-dimensional subspace coordinates, eliminating the need to store and scan full-dimensional data or traverse pointer-heavy index graphs. Mathematically, HNTL splits the vector corpus into spatial grains. For each grain with centroid 𝜇𝑔 , we construct a local Principal Component Analysis (PCA) basis 𝑊𝑔 (where the subspace dimension 𝑘 is much smaller than the ambient dimension 𝑑, e.g., 𝑘 = 16 and 𝑑 = 768). The mathematical steps of the projection and quantization pipeline are detailed below and illustrated in Figure 2:
𝑣 ′ = 𝑣 − 𝜇𝑔
𝑧
(4)
(5) Quantization: Quantizing the coordinates 𝑧 and residual norm 𝑟 to signed and unsigned 16-bit integers respectively, 2
Top-𝐾 Results Query & Planner Engine (DRAM) Quantization Envelope Filter
Query Vector 𝑞 ∈ R𝑑
SIMD Scan Engine (NEON / AVX / AVX-512)
HNTL Manifold Index Segment (DRAM) Centroid Routing Plane
L2 Reranker (Float32)
Raw Data SSTable (SSD / mmap)
Block-SoA Segment (Grain G𝑔 ) Coords: int16_t coords[k][B]
{𝜇 1 , . . . , 𝜇𝐺 } ⊂ R𝑑
Raw Vector Block 𝑥𝑖 ∈ R𝑑 (Float32)
Sketches: int8_t sketches[s][B] Residuals: uint16_t residual_norms[B]
Grain Metadata
Vector IDs: uint32_t ids[B]
𝑊𝑔 ⊂ R𝑑 ×𝑘 , scales Δ
Figure 1: Aperon HNTL System Component Architecture (DRAM vs. SSD Memory layout).
3.2
Recall Accuracy
3.3
Table 1 reports candidate recall (compact index lookup) and rerank recall (after exact L2 re-ranking in float32 space) at 𝑘 = 10, 𝑑 = 768, 𝑁 = 10,000, with subspace dimension 𝑘 = 32 and sketch dimension 𝑠 = 8, alongside standard HNSW graph baselines.
Table 2: Scan throughput and speedup comparison (𝑁 = 512, 𝑑 = 64, 𝑘 = 8, 𝐵 = 64).
Table 1: Recall results at 𝑘 = 10, 𝑑 = 768, 𝑁 = 10,000, single grain. HNTL configurations use PCA subspace dimension 𝑘 = 32 and residual sketch dimension 𝑠 = 8. Dataset Isotropic Gaussian Isotropic Gaussian Anisotropic Manifold Anisotropic Manifold Anisotropic Manifold
PCA Var. Captured
Search Mode
Cand. Recall@10
Pool 𝐶
Rerank Recall@10
6.5% – 96.3% 96.3% –
Mode B HNSW Baseline Mode A Mode B HNSW Baseline
10.3% – 86.0% 91.5% –
200 – 20 20 –
49.4% 0.9980 1.0000 1.0000 1.0000
Scan Throughput & Hardware Profiling
Throughput is evaluated using a smoke dataset of 𝑁 = 512, 𝑑 = 64, 𝑘 = 8, 𝐵 = 64, comparing Block-SoA, AoS, and Pointer-Chasing.
Scan Mode Block-SoA (SIMD) AoS (Sequential) Pointer Chasing (Graph)
M2 Max (ns/vector)
Xeon (ns/vector)
Speedup vs. Pointer
4.137 8.056 14.951
4.890 8.520 14.232
3.61× / 2.91× 1.86× / 1.67× 1.00× / 1.00×
Using the Apple kperf PMU API, we profile instruction execution metrics. The results reveal that Block-SoA NEON scan achieves a 3.59× higher IPC (3.59 vs. 0.98 for pointer chasing) and reduces L1 data cache load misses from 8.72% down to < 0.01%. On a flat run (no PMU overhead), Block-SoA latency is 3.05 ns/vector.
As a baseline reference, a standard HNSW graph index (configured with 𝑀 = 16, 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ = 50, constructed using the FAISS implementation [1]) achieves a Recall@10 of 0.9980 on the isotropic Gaussian and 1.0000 on the anisotropic manifold. While HNSW delivers high recall on both datasets, it does so at a heavy memory cost: HNSW requires keeping the full-dimensional 768-float vectors in DRAM along with a 64-byte graph neighbor list per vector (using 4-byte neighbor IDs), totaling ∼ 3.1 MB of index structure overhead for 10,000 vectors (excluding raw vector storage). In contrast, HNTL’s Mode B index stores only 32 compact coordinates (16-bit) and 1 residual (16-bit) per vector, requiring only 66 bytes of DRAM per vector—amounting to only 660 KB (a 4.7× memory reduction compared to the HNSW graph connections alone) while matching the perfect 1.0000 rerank recall on the anisotropic manifold. Under Mode A, HNTL achieves the same 1.0000 rerank recall while bypassing DRAM raw vector residency completely via online coordinate reconstruction. 3
4
Conclusion & Future Work
Aperon’s HNTL demonstrates that the pointer tax of traditional proximity graphs can be eliminated. Matching the index layout to CPU cache line boundaries via Block-SoA and leveraging local tangent spaces yields a 3.61× speedup and up to 12× memory reduction compared to graph baselines. Recent SIFT1M scale benchmarks validate that HNTL’s HLR/HTLA routing achieves a Recall@10 of 95.4% at 580.2 QPS, with 21x DRAM memory reduction (24.0 MB vs. 528.0 MB) when using tiered SQ8 cold storage offloading. Future work will focus on learned grain partitioning, warp-level GPU scans, and integration into the production Rust Aperon memory substrate.
References [1] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Hervé Jégou, Jeff Johnson, et al. 2024. The library for local search: FAISS. arXiv preprint arXiv:2401.08281 (2024).
Input Vector 𝑣 ∈ R𝑑 (Data 𝑥𝑖 or Query 𝑞)
[2] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization for approximate nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 36, 4 (2013), 744–755. [3] Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors in high dimensions. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. 604–613. [4] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 1 (2011), 117–128. [5] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data 7, 3 (2019), 535–547. [6] Daniel Lemire and Leonid Boytsov. 2015. Decoding billions of integers per second through vectorization. Software: Practice and Experience 45, 1 (2015), 1–29. [7] Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE transactions on pattern analysis and machine intelligence 42, 4 (2018), 824–836. [8] Thomas Willhalm, Nicolae Popovici, Alexander Buxmann, Benjamin Schlegel, Wolfgang Lehner, et al. 2009. Vectorizing database algorithms with SIMD instructions on Intel Core2 processors. In Proceedings of the 15th International Conference on Management of Data. 11–20. [9] Yong and Substratum Labs team. 2026. Aperon: An Agent-Native Log-Structured Memory Vector Database. https://github.com/substratum-labs/aperon.
1. Mean Centering 𝑣 ′ = 𝑣 − 𝜇𝑔
2. Subspace Projection 𝑧 = 𝑊𝑔⊤ 𝑣 ′ ∈ R𝑘
3. Subspace Reconstruction 𝑣˜ = 𝑊𝑔 𝑧 ∈ R𝑑
4. Residual Calculation 𝑒 = 𝑣 ′ − 𝑣˜ ∈ R𝑑
5. Residual Norm 𝑟 = ∥𝑒 ∥ 22 ∈ R
6. 16-bit Quantization 𝑧 → 𝑧ˆ (int16), 𝑟 → 𝑟ˆ (uint16)
Output: 𝑧ˆ (int16) & 𝑟ˆ (uint16) (Stored in Block-SoA or scanned)
Figure 2: HNTL Subspace Projection and Quantization Pipeline.
4