Additive Integer Codes for Hyperbolic Embeddings on Edge Devices

Hyperbolic embeddings place hierarchical data, such as taxonomies, phylogenies and disease-spread graphs, into a curved space whose volume grows exponentially with distance from the center. This lets a 5-dimensional vector do work that a flat embedding cannot do even with 200 dimensions. On WordNet nouns, 5-dimensional Poincaré embeddings reach a mean average precision (MAP) of 0.823, against 0.168 for 200-dimensional Euclidean ones (Poincaré Embeddings). That compactness should make them a natural fit for phones and microcontrollers. In practice they are a poor fit, for two reasons. Deep points sit exponentially close to the edge of the ball, so their coordinates need a number of bits that grows linearly with tree depth (Representation Tradeoffs for Hyperbolic Embeddings). And computing a single distance calls functions like $\text{acosh}$ that small integer processors do not have. The field's current fixes go in the opposite direction from edge deployment: they store each coordinate as a sum of two to many floats, reaching hundreds of bits per coordinate (Multi-Component Floats; HS-DTE / HypFPE).

This note proposes a different trade. Store each point not by its absolute coordinates but relative to a hierarchy of anchor points. The code has three parts: which anchor it hangs from, a small fixed-point number for its hyperbolic depth, and a low-bit local offset. Distances between far-apart points then become integer additions plus a single table lookup, because in negatively curved space the triangle inequality is almost tight. The claim is that this sidesteps the precision wall rather than paying for it. The bits that must grow with depth go into a depth scalar and an anchor index, which scale logarithmically. No coordinate ever needs more than a few bits.

Core Claim

The linear-in-depth precision requirement proved by Representation Tradeoffs for Hyperbolic Embeddings is a property of absolute Cartesian coordinates, not of hyperbolic geometry itself. Hyperbolic space is close to a tree at large scales. A point can therefore be described by where it sits in a learned anchor tree, plus a well-conditioned local correction. Distance computation then needs only integer adds and a small lookup table indexed by quantized branch angles.

We expect such codes, at roughly 32 to 48 bits per entity, to match 5-dimensional FP32 Poincaré embeddings (160 bits) on hierarchy reconstruction and link prediction. We also expect that, unlike naive INT8 or INT4 quantization of Poincaré, Lorentz or tangent coordinates, their accuracy will not degrade as hierarchy depth grows.

The Mechanism

The key fact is the hyperbolic law of cosines. Take two points $x$ and $y$ that leave a shared anchor $a$ at geodesic distances $d_1 = d(a,x)$ and $d_2 = d(a,y)$, separated by angle $\theta$ at $a$. Their distance satisfies $\cosh d = \cosh d_1 \cosh d_2 - \sinh d_1 \sinh d_2 \cos\theta$. When $d_1$ and $d_2$ are moderately large, this reduces to

$$ d(x,y) \approx d_1 + d_2 + 2\log\sin(\theta/2), $$

with an error that shrinks roughly like $e^{-2\min(d_1,d_2)}$. That rate comes from dropping the smaller exponential terms in $\cosh$ and $\sinh$.

Now let each entity store three things: its leaf anchor, its fixed-point depth $\rho(x) = d(o, x)$ from a root anchor $o$, and a low-bit offset in the tangent frame of its leaf anchor. Each anchor stores its own depth and a small INT8 table of $2\log\sin(\theta/2)$ values for pairs of its child branches. For two entities whose lowest common anchor is $a$, the distance estimate is

$$ \hat d(x,y) = \rho(x) + \rho(y) - 2\rho(a) + T_a[i,j], $$

where $i$ and $j$ are the child branches of $a$ that lead toward $x$ and $y$, and $T_a$ is that anchor's lookup table. Two cases fall outside this formula. When $x$ and $y$ share a leaf anchor, or when $d_1$ or $d_2$ is below a threshold, the distance is computed directly from the two low-bit offsets in the anchor's tangent frame. That frame is nearly flat at the relevant scale, so 8-bit fixed point with a small table-based $\text{acosh}$ is well conditioned there.

The approximation error of the anchor tree itself is governed by how tree-like the data is. This is the same quantity HGCN identifies as predicting when hyperbolic models help (Hyperbolic Graph Convolutional Neural Networks). We will measure it rather than assume it.

Research Program

The work has four parts. The first builds the anchor hierarchy from a trained full-precision hyperbolic embedding. We will use top-down hyperbolic clustering with a branching factor of 16 to 64 at each level, so that anchor paths fit in whole bytes. We will not require a given taxonomy, because WordNet's multiple inheritance and HGCN node embeddings are not trees.

The second part is quantization-aware fine-tuning. Full-precision shadow copies of depths and offsets receive gradients through a straight-through estimator (Training Quantized Nets: A Deeper Understanding). Step sizes for depth and offset are learned in the manner of Learned Step Size Quantization. The original ranking or link-prediction loss is evaluated on the decoded distance $\hat d$, not on the float distance. Offsets are norm-clipped before quantization, reusing the radius clip of Clipped Hyperbolic Classifiers as a range bound on the local frame rather than on the whole ball.

The third part is a bit-accounting analysis. We will make precise how per-entity bits scale with the number of entities and with depth, and set this against the Sala et al. bound. The point to establish is that the only depth-dependent cost is about $\log_2 D$ integer bits in $\rho$.

The fourth part is an integer-only top-k retrieval kernel for an ARM Cortex-M class microcontroller and a mobile CPU. It finds the lowest common anchor by comparing prefixes of anchor paths, then evaluates $\hat d$.

The scope is deliberately narrow. We target embedding tables and distance-based scoring, meaning taxonomy lookup, hypernym retrieval and link scoring from precomputed HGCN node embeddings. We do not attempt to quantize full hyperbolic networks end to end.

This work differs from the three hyperbolic discrete-code papers in the file, which it partly builds on. HyperVQ quantizes encoder outputs of generative models with hyperbolic logistic-regression codebooks. HiHPQ does product quantization in the Lorentz model for image hashing. Hyperbolic Residual Quantization is the closest: it builds multi-stage codes with Möbius residuals. All three keep full-precision codebooks and evaluate distances with floating-point transcendental arithmetic at inference time. Our contribution is a storage format whose distance evaluation is additive and integer-only. The anchor hierarchy supplies the "residual" structure, and the depth scalar makes the tree-like part of the metric exact in integers.

Hyperbolic Binary Neural Network uses the Poincaré ball only as a training scaffold for Euclidean binary weights and discards it at test time. Here the hyperbolic geometry is exactly what survives to inference. PolarQuant motivates our split into radius and angle: it shows that separating norm from direction removes per-block scale metadata for Euclidean KV caches. We apply a similar split where curvature makes it far more consequential.

Baselines

The do-nothing reference is the full-precision 5-dimensional Poincaré embedding at FP32, costing 160 bits per entity. On WordNet nouns it reports MAP 0.823 (Poincaré Embeddings). We retrain it with the same data and epochs so that every compressed variant starts from the same checkpoint.

The strongest existing accuracy reference is the combinatorial construction of Representation Tradeoffs for Hyperbolic Embeddings, which reports MAP 0.989 on WordNet nouns in 2 dimensions. It reaches that only with high-precision coordinates. We will run it at its native precision and again at matched bit budgets. On WordNet mammals, the 2-component multi-component float model reports MAP 93.85% (Multi-Component Floats). On the Mosses phylogenetic tree, HS-DTE reports distortion 9.42 in float64 and near-optimal distortion with about 100-bit expansions (HS-DTE). Beating these means reaching at least 95% of their MAP, or at most 1.2 times their distortion, at 48 bits per entity or fewer.

The naive quantization baseline is the one a practitioner would try first: per-channel INT8 and INT4 post-training and quantization-aware quantization of Poincaré coordinates, of Lorentz coordinates, and of origin tangent vectors. Each is run both with and without the radius clip of Clipped Hyperbolic Classifiers, and each gets the same fine-tuning budget as our method. To beat it, our method must be flat in accuracy as depth grows where this baseline falls.

The Euclidean discrete-code baseline is the KD coding of Knowledge Graph Embedding Compression. It reports FB15k MRR 0.477 at 42 to 950 times compression for TransE, but gives no reported result on Lacuna for WordNet hierarchy reconstruction. We will apply it at matched bits per entity both to Euclidean embeddings and to Poincaré embeddings mapped to the origin tangent space.

The closest hyperbolic discrete code, Hyperbolic Residual Quantization, will be trained at matched code lengths. It reports up to a 20% Recall@10 gain over Euclidean residual quantization on WordNet hypernym prediction. We compare accuracy and on-device latency, counting its full-precision codebook in memory.

Finally, two ablations isolate our ingredients. The anchor-only variant keeps depth plus lowest-common-anchor distance and drops both the angle table and the local offsets. The no-depth variant spends those bits on larger offsets instead.

Why not just…?

Why not just embed in a larger Euclidean space and quantize to INT4? The file's evidence goes against this. A 200-dimensional FP32 Euclidean embedding already reaches only 0.168 MAP on WordNet nouns (Poincaré Embeddings), and at INT4 it would cost 800 bits per entity. Quantization can only lower that accuracy. The Euclidean KD-code baseline is the fair version of this idea at matched bits, and we include it.

Why not just quantize the Poincaré or tangent coordinates to INT8, with clipping? This is the real threat for shallow hierarchies. Clipping bounds the range, and a shallow tree may never need boundary precision. For deep trees, clipping to a fixed radius caps the representable depth and merges distant subtrees. That is exactly the failure the Sala bound predicts for fixed-width absolute coordinates. The depth sweep on synthetic trees and the Mosses tree will settle it. If clipped INT8 matches us at every depth we test, the anchor machinery is unnecessary, and we will report that.

Why not just store the tree and use shortest-path distance? For an exact tree this is optimal, and our anchor-only ablation is essentially this baseline. Our claim is that real data is not a tree. WordNet has multiple parents, and HGCN embeddings of DISEASE and AIRPORT encode graph structure beyond any single spanning tree. There, the angle table and local offsets should recover accuracy that anchor-only distance loses. If the ablation shows no gap on these datasets, the continuous part of the code is not earning its bits.

Why not just use multi-component floats? They fix precision by multiplying the storage per coordinate, to 100 to 400 bits in HS-DTE. They also still require transcendental functions per distance. We include them only as accuracy ceilings, not as edge competitors.

Proposed Experiments

The first decisive check is a depth sweep. We use synthetic $m$-ary trees with depth from 5 to 30, the Mosses tree (path length 30), and WordNet mammals and nouns. For each we plot MAP or distortion against depth at a fixed bit budget of 32, 48 or 64 bits per entity. The prediction is that naive INT8 and INT4 coordinate quantization degrades with depth while anchor codes stay flat.

The second check is the ablation described above, on WordNet nouns and on link prediction with HGCN embeddings for DISEASE and AIRPORT. HGCN reports a 63.1% and a 47.5% error reduction over Euclidean GCNs on these, but no absolute value appears in the file. The ablation should measure how much of the accuracy the angle table and offsets restore beyond the pure anchor tree. We will also report how that gain tracks each dataset's measured tree-likeness.

The third check is a direct measurement of approximation error. We plot $|\hat d - d|$ against $\min(d_1, d_2)$ to confirm the predicted exponential decay, which determines the fallback threshold.

The fourth check is on-device. On a Cortex-M microcontroller and a mobile CPU we measure top-10 retrieval latency, energy per query and total memory, including anchor tables. These are compared with FP32 Poincaré distance evaluation using software $\text{acosh}$ and with Hyperbolic Residual Quantization decoding.

Success means reaching at least 95% of full-precision MAP at 48 bits or fewer, flat across depth, with integer-only scoring that is measurably faster than float hyperbolic scoring on the same device. Failure on the depth sweep would falsify the core claim. Failure only on the ablation would reduce the contribution to a well-engineered tree index.