Hyperbolic Codebooks for Dominator-Block Code Indexes

Code retrieval systems, such as the ones that feed repository context to a coding assistant, store one dense vector for every chunk of every file. At repository scale that index becomes large, so it is usually compressed by vector quantization: each vector is replaced with a few short integer codes that point into a learned table of prototype vectors (a codebook). Both the chunking and the quantization ignore how code is organized. Programs form deep trees. A repository contains files, files contain classes, classes contain methods, and methods contain control-flow blocks. A tree with a fixed branching factor has a number of leaves that grows exponentially with depth, while room in ordinary flat (Euclidean) space grows only polynomially. Compressing tree-shaped data in flat space therefore crowds the leaves together and wastes codebook entries.

This note proposes building the code index from dominator blocks and quantizing it in hyperbolic space. A dominator block is a piece of a method that every execution path into its region must pass through, so it forms a natural unit of logic. Hyperbolic space is a curved geometry whose volume grows exponentially with radius, which matches the way trees grow. The claim is narrow and testable. Suppose the index is held to a fixed budget of bits per chunk, between 32 and 128. Then dominator-block chunks embedded and residual-quantized in hyperbolic space should keep more retrieval accuracy than syntax-tree chunks quantized in flat space. The advantage should grow as the bit budget shrinks.

Core Claim

Prior work supplies each piece of this design separately but never combines them. BASTS (Improving Code Summarization with Block-wise Abstract Syntax Tree Splitting) splits methods along the dominator tree of the control-flow graph and improves summarization. It reports 10.58% S-BLEU over Rencos on Java. However, it pools the blocks with a flat Transformer and never compresses anything. cAST (cAST) shows that structure-aware chunking helps retrieval-augmented generation for code, with +4.3 Recall@5 on RepoEval over fixed-size chunks. Its chunk boundaries come only from grammar, and its index is an uncompressed Euclidean one. HypeCodeNet (The Natural Geometry of Code) shows that a 32-dimensional Lorentz-model embedding of whole syntax trees matches a 768-dimensional Euclidean one. Its compression is limited to continuous dimension, and it never partitions code into blocks. Two hyperbolic quantizers exist: HRQ (Hyperbolic Residual Quantization) and HyperVQ (HyperVQ). Both show that hyperbolic codebooks resist collapse and keep hierarchical recall at 4–8 dimensions, but only on WordNet, product graphs, images and audio.

The new element in this proposal is the measured rate–accuracy curve of a code index, swept along three crossed axes:

  • Partition unit: fixed window, syntax subtree, or dominator block.
  • Geometry: Euclidean or hyperbolic.
  • Coding scheme: the hierarchy is either learned by residual quantization or written down explicitly as a structural address.

The hypothesis predicts a specific shape for this curve. Partition and geometry should interact, with the hyperbolic gain largest for dominator blocks and largest at low bit budgets. A uniform shift across all partitions would refute the claim that the two pieces belong together.

Research Program

Indexing hierarchy. For Java and Python repositories, the system builds intra-procedural control-flow graphs from Tree-sitter parses, computes dominator trees, and cuts each method at dominator-tree nodes. Undersized sibling blocks are merged with cAST's character-budget rule so that chunk sizes stay comparable across partition schemes. When a control-flow graph cannot be built, which happens with unparsable or heavily unstructured code (the failure mode BASTS reports), the method falls back to syntax-subtree blocks. The fallback rate will be reported per repository. Each block becomes a leaf in a containment hierarchy of repository, file, class, method, dominator path and block. Because dominator paths add several levels inside each method, this tree is much deeper than the method-level tree alone.

Encoder. A frozen Euclidean code encoder (GraphCodeBERT, as in SEA) is followed by a small trainable head. The head maps each block into the Lorentz model, using the exponential map at the origin and Riemannian Adam as in HypeCodeNet. The training objective combines two terms:

$$\mathcal{L} = \mathcal{L}_{\text{retr}} + \lambda \, \mathcal{L}_{\text{tree}}$$

Here $\mathcal{L}_{\text{retr}}$ is a contrastive loss that pulls a query toward its relevant block, using hyperbolic distance in place of the dot product. $\mathcal{L}_{\text{tree}}$ asks that a block's distance from the origin increase with its depth in the containment hierarchy, and that each block lie closer to its ancestors than to non-ancestors. $\lambda$ weights the second term.

Quantization. HRQ-style residual quantization is applied with $L$ stages, each using a codebook of $K$ entries, which gives a budget of $L\log_2 K$ bits per block. The hypothesis is that the early residual stages will come to encode coarse position in the hierarchy (roughly, which file region) and the later stages will encode which block. This will be checked directly by measuring the mutual information between each stage's codes and each hierarchy level.

Precondition check. Before any comparison, the program tests whether the semantic geometry of blocks is actually tree-like. A dominator tree is a tree by construction, so it is trivially tree-like. The real question concerns the distances between blocks under the frozen encoder. The check computes Gromov δ-hyperbolicity, a standard score of how tree-like a distance matrix is, on the block distance matrices under each partition. It also computes Ollivier–Ricci curvature on the raw control-flow graphs, following the analysis HFE (Hyperbolic Function Embedding) ran on call graphs. If dominator partitioning does not lower δ relative to syntax chunking, the stated reason for pairing it with hyperbolic geometry is gone, and the note will say so.

Baselines

Naive reference: fixed-size chunks with Euclidean product quantization. Fixed-size chunks are encoded with the same frozen encoder and compressed with FAISS product quantization at each matched bit budget. This is the system most people would deploy, and it marks the floor. It will receive the same training data and the same hyperparameter-search budget as the proposed system.

Strongest structure-aware competitor: cAST chunks with Euclidean residual quantization. cAST chunking is paired with Euclidean residual quantization trained under the same contrastive loss. It is the strongest competitor because cAST is the best structure-aware chunker in the file, and residual quantization is the Euclidean twin of HRQ. The comparison therefore isolates geometry and partition from the use of a learned residual codebook. No compressed-index result for cAST is reported on Lacuna. Only its uncompressed gain of +4.3 Recall@5 over fixed-size chunking on RepoEval is available, so its uncompressed recall will be reproduced first as the ceiling. Beating this baseline means a higher Recall@5 on RepoEval at 64 bits per block or less, across three seeds, with non-overlapping bootstrap intervals.

Whole-method hyperbolic competitor: HypeCodeNet-style embedding. Whole methods are embedded with a HypeCodeNet-style Lorentz encoder at 32 dimensions and then compressed with HRQ. This tests whether partitioning adds anything once hyperbolic geometry is in place. The reported figure for HypeCodeNet is 0.940 F1 on BigCloneBench, uncompressed (The Natural Geometry of Code). For long-code retrieval, SEA's reported CodeSearchNet MRR of 0.785 with GraphCodeBERT (Tackling Long Code Search) is the uncompressed reference that compressed variants are measured against.

Ablations. Two ablations isolate the key ingredients. In the first, dominator blocks are quantized with Euclidean residual quantization, which removes geometry and keeps partition. In the second, the hyperbolic system is trained with $\lambda=0$, which keeps the geometry but drops the explicit hierarchy objective.

Explicit-address baseline. This baseline gives each block an exact structural address (its path in the containment tree, stored for a few bits). Euclidean product quantization encodes the block's content, and the bit budget is split between address and content. It is described further under the hierarchy-ID question below.

Why not just…?

Why not just use cAST chunks and flat product quantization? This alternative is cheap and mature. If the dominator-block hyperbolic index fails to beat it at matched bits, the proposal fails. The HyperVQ result supports expecting a gap. KmeansVQ used only 58.09 effective entries out of 512 on CIFAR-100, against 220.22 for HyperVQ. That is evidence of crowding in flat codebooks, but the evidence comes from images, not code. The factorial sweep settles the question directly, and the outcome is open.

Why not just raise the Euclidean dimension or the bit budget? The question here is accuracy at a fixed memory cost, so raising the budget answers a different question. Even so, the full curve from 32 to 512 bits will be reported. If the curves meet at moderate budgets, the contribution narrows to the extreme low-bit regime, and that regime is exactly where HRQ reports its 20% WordNet recall gain at 4–8 dimensions. The 1.2x slowdown HypeCodeNet reports applies to encoding. Query-time cost will be measured separately, since distance lookups through a codebook can be precomputed in tables.

Why not just store the tree position explicitly as a hierarchical ID? This is the most serious threat. When structural position is known exactly, a learned geometry may be unnecessary for encoding it. The explicit-address baseline tests this. If it matches the hyperbolic system, the honest conclusion is that hyperbolic codes add nothing beyond bookkeeping. The remaining place hyperbolic codes could still help is retrieval across repositories, where tree addresses carry no shared meaning. A cross-repository split is evaluated for exactly this reason.

Why not just use BM25? The CodeSearchNet Challenge found that simple bag-of-words beat neural models on human relevance judgments, with NDCG 0.574 against 0.493 (CodeSearchNet Challenge). BM25 over the same chunks is therefore reported as a reference on every benchmark. An inverted index has a different memory profile, so its size will be reported alongside its accuracy.

Proposed Experiments

Retrieval on RepoEval. Recall@5 is computed for every cell of the factorial (partition × geometry × coding scheme) at 32, 64, 128 and 512 bits per block, plus uncompressed. StarCoder2-7B generation quality is then measured on the retrieved context for the 64-bit setting. The decisive check is a partition-by-geometry interaction in a two-way analysis over seeds. The hypothesis predicts a larger hyperbolic gain for dominator blocks than for syntax or fixed chunks, and a gain that widens as bits fall.

Code search on CodeSearchNet. MRR is compared against SEA's 0.785 uncompressed reference, together with NDCG on the human-annotated set, where the BM25 and bag-of-words references apply.

Clone detection on BigCloneBench. F1 is reported for each clone type. Semantic clones (Types 3–4) are the interesting slice. HypeCodeNet notes that hyperbolic models struggle when two implementations of the same logic differ structurally, such as a loop versus recursion. Dominator blocks might either soften or sharpen that weakness.

End-to-end repository issue resolution. On SWE-bench Lite, Pass@1 is measured with a 64-bit index, compared against cAST's reported +2.67 gain over fixed chunking (cAST) and the uncompressed index.

Diagnostics. These include δ-hyperbolicity per partition, codebook perplexity per residual stage, mutual information between each stage's codes and each hierarchy level, and the fallback rate on code without a usable control-flow graph.

The proposal is falsified under any of three outcomes. It fails if dominator partitioning does not reduce δ. It fails if the Euclidean residual quantization ablation on dominator blocks matches the hyperbolic system. It also fails if the explicit-address baseline matches the hyperbolic system on the cross-repository split.