PaperlayerView exact revision on arXiv

Source-linked AI summary

Hypergraph Embedding Indexing for Efficient Dense Vector Retrieval

Kishore Konda

arXiv:2608.22980v1cs.IRcs.AI

TL;DR

Dense retrieval indexes often treat embeddings as indivisible geometric points, motivating a coordinate-inverted alternative. HEI builds hyperedges from highly activated dimensions, combines complementary activation views, and reranks candidates with dense similarity; its efficiency depends on activation diversity, while coverage remains bounded by shared hyperedges.

  • Problem

    Existing ANN indexes treat embeddings as indivisible high-dimensional points, leaving a need to organize retrieval around latent activation patterns while balancing coverage and candidate-pool efficiency.

  • Method

    HEI constructs inverted posting lists from higher-order combinations of selected latent embedding activations, generates candidates through shared hyperedges, and applies cosine reranking.

  • Results

    HEI combines complementary activation views to improve retrieval coverage, while activation diversity identifies embedding representations that yield more selective hyperedges and efficient candidate pruning.

  • Takeaways & Limitations

    Coordinate-inverted dense retrieval is governed by both hypergraph coverage and the statistical diversity of embedding activations.

  • Takeaways & Limitations

    Retrieval is bounded by hypergraph coverage: semantically similar documents may be unreachable when query and document embeddings share no hyperedge.

Abstract

from arXiv · show

Dense vector retrieval has become the foundation of modern semantic search, yet existing approximate nearest neighbor (ANN) indexes treat an embedding as an indivisible point in a high-dimensional space. In this work, we propose the Hypergraph Embedding Index (HEI), a framework that instead organizes documents according to combinations of highly activated latent embedding dimensions. This formulation enables inverted-index style candidate generation while preserving the semantic ranking capabilities of dense embeddings. We further demonstrate that constructing multiple complementary hypergraphs substantially improves retrieval coverage without the combinatorial growth associated with increasing the dimensionality of a single hypergraph. Finally, we establish that the statistical properties of embedding activations strongly influence coordinate-inverted indexing efficiency, introducing \emph{activation diversity} as a diagnostic metric governing embedding indexability in coordinate-inverted frameworks.

1 Introduction

HEI reorganizes documents by higher-order combinations of latent embedding activations, enabling inverted-index candidate generation followed by dense similarity reranking. Multiple complementary hypergraphs improve coverage, while activation diversity governs hyperedge selectivity and candidate-pool efficiency.

  • Motivation: Existing ANN indexes generally treat embeddings as indivisible points searched through graphs, partitions, or hashes.These paradigms approximate nearest-neighbor search in high-dimensional vector spaces.
  • Framework: HEI constructs inverted posting lists from higher-order combinations of highly activated latent embedding dimensions.Documents sharing activation-pattern hyperedges become candidates, which are subsequently reranked using original embedding similarity.
  • Multiple Hypergraphs: Multiple complementary hypergraphs improve candidate recall and retrieval coverage while avoiding the combinatorial growth of increasing one hypergraph’s dimensionality.The paper instantiates positive and negative activation views and combines their candidate sets.
  • Activation Diversity: Activation diversity determines hyperedge selectivity, candidate-pool size, and retrieval efficiency in coordinate-inverted architectures.The analysis uses Shannon entropy and the Gini coefficient to quantify activation diversity.

2 Related Work

Related ANN systems primarily exploit geometric proximity, spatial partitions, quantized representations, sparse projections, or discrete coordinate codes. HEI instead uses higher-order combinations of activation ranks to control inverted posting-list selectivity.

  • Geometric and Partition-based ANN: Graph, partitioning, and hashing methods approximate neighborhood search through proximity structure, space division, or compact binary signatures.Examples include HNSW, IVF, Product Quantization, and LSH.
  • Learned Sparse and Hybrid Retrieval: Learned sparse models project representations onto vocabulary or latent dimensions so classical inverted indexes can execute retrieval.SPLADE, SparTerm, and SNRM explicitly produce sparse weightings.
  • Coordinate Hashing and Extreme Multi-Label Learning: Coordinate hashing and extreme multi-label methods use activation ranks or structured routing to generate discrete candidate codes or lists.HEI shares coordinate-rank usage but indexes r-combinations of top-k activations as higher-order hyperedges.

3 Hypergraph Embedding Index (HEI)

HEI selects informative embedding coordinates, forms size-r combinations as hyperedges, and builds inverted posting lists over those activation patterns. Query hyperedges retrieve and score candidates before exact cosine reranking on full embeddings.

  • Embedding Representation: Each embedding is interpreted as a pattern of signed and magnitude-valued activations across latent feature coordinates.The vector is treated as a latent-feature response rather than an indivisible geometric point.
  • Dimension Selection: HEI selects k informative dimensions from each embedding using activation criteria such as magnitude or signed-tail activity.The selected set is denoted S(e).
  • Hypergraph Formulation: Higher-order combinations of selected dimensions form hyperedges, which serve as indexing keys for coordinate-inverted posting lists.For a selected set S(e), H(e) contains unique subsets of size r; each hyperedge represents one activated-dimension combination.
  • Inverted Index Construction: The corpus index maps each generated hyperedge to the documents that share it, allowing candidate matching across multi-dimensional activation patterns.HEI posting lists represent higher-order latent patterns rather than atomic terms.
  • Candidate Generation and Scoring: Query hyperedges traverse their corresponding posting lists, merge duplicate documents, and retain evidence from shared hyperedges for Stage-1 scoring.Candidate scores aggregate shared-hyperedge weights, including IDF and activation magnitudes.
  • Cosine Reranking: Top-N candidates undergo exact Stage-2 cosine reranking using the original full query and document embeddings.This preserves dense similarity for the final retrieval list after coordinate-inverted candidate generation.

4 Analysis of Hypergraph Retrieval

HEI retrieval balances hyperedge selectivity against coverage: selective posting lists reduce candidate pools, but missing shared hyperedges make similar documents unreachable. This makes candidate-generation coverage, rather than cosine reranking, the central bottleneck and motivates multiple compact hypergraphs.

  • 4.1 Hyperedge Selectivity: HEI must balance selective hyperedges that reduce candidate pools with sufficient coverage of semantically similar documents.Highly selective hyperedges can reduce recall when they fail to connect related documents.
  • 4.1 Hyperedge Selectivity: Stage-1 scoring aggregates evidence across all hyperedges shared by a query and document before Stage-2 cosine reranking.Both individual hyperedge selectivity and the diversity of shared hyperedges influence retrieval effectiveness.
  • 4.2 Coverage Limitation: Single-hypergraph coverage can miss semantically similar documents despite high similarity in the original embedding space.The limitation arises because one hypergraph captures only one view of the embedding’s latent activation space.
  • 4.2 Coverage Limitation: A document is retrieved only when its hyperedge set overlaps the query’s hyperedge set.If H(eq) ∩ H(ed) = ∅, cosine similarity cannot recover the document during Stage 1.
  • 4.3 Motivation for Multiple Hypergraphs: Increasing selected dimensions raises hyperedge counts rapidly, enlarging indexes and retrieval cost while producing diminishing coverage returns.For hyperedges of size r, the growth follows combinations over the selected dimensions.
  • 4.3 Motivation for Multiple Hypergraphs: Multiple independent hypergraphs preserve compact individual indexes while their union substantially improves candidate coverage.Each complementary hypergraph provides an additional opportunity to retrieve semantically related documents without densifying one structure.

5 Complementary Hypergraph Indexing

Complementary hypergraphs address single-view coverage limits by independently generating candidate sets and merging them. This improves recall while keeping each hypergraph compact and complexity growth linear in the number of hypergraphs.

  • 5 Complementary Hypergraph Indexing: Increasing the selected-dimension count k creates combinatorially more hyperedges, increasing index size and retrieval cost.The resulting coverage improvements diminish as the single hypergraph becomes denser.
  • 5 Complementary Hypergraph Indexing: Multiple independent hypergraphs represent complementary activation views while keeping each individual structure compact.This provides independent opportunities to retrieve semantically related documents instead of increasing one hypergraph’s complexity.
  • 5 Complementary Hypergraph Indexing: Each of L hypergraphs independently generates a candidate set, and the final Stage-1 set combines those candidate sets.The construction uses H(1), H(2), …, H(L) and candidate sets C(ℓ) for a query.
  • 5 Complementary Hypergraph Indexing: A document becomes retrievable if any complementary hypergraph discovers it, increasing retrieval recall without increasing each hypergraph’s combinatorial complexity.This is the central coverage benefit of the multi-hypergraph formulation.
  • 5 Complementary Hypergraph Indexing: The experiments instantiate two complementary views: the k largest positive activations and the k largest negative activations.A separate hypergraph is built for each view, and their candidates are merged before scoring and cosine reranking.
  • 5 Complementary Hypergraph Indexing: Using L complementary hypergraphs yields linear complexity growth with respect to L, unlike increasing dimensions within one hypergraph, which grows combinatorially.The formulation therefore improves coverage through multiple compact indexing structures.

6 Experimental Evaluation

The evaluation tests HEI on QQP and STS-B across two 384-dimensional sentence-embedding models, comparing retrieval and candidate-generation behavior against exhaustive cosine search.

  • Evaluation Questions: The evaluation examines HEI accuracy against exhaustive search, complementary-hypergraph coverage, embedding-model variation, and the quality-efficiency trade-off.
  • Datasets and Models: HEI is evaluated on QQP and STS-B using all-MiniLM-L6-v2 and BGE-small-en embeddings.Both models produce embeddings with dimensionality m = 384.
  • Baselines: FAISS Flat exhaustive cosine search serves as the exact dense-retrieval baseline for accuracy.
  • Metrics: Evaluation reports Hit@10, Gold Recall, mean candidate pool size, and latency to separate retrieval quality from Stage-1 candidate generation.Gold Recall measures whether the relevant document appears in the Stage-1 candidate set.
  • HEI Configuration: Hyperedges use r = 3 combinations from the top k = 10 activation dimensions, followed by Stage-1 scoring and Stage-2 cosine reranking.

7 Retrieval Performance

Complementary HEI combines positive and negative activation views to improve candidate coverage and Hit@10, with gains attributable to Stage-1 candidate generation because Stage-2 reranking is unchanged.

  • Complementary Hypergraphs: Complementary HEI consistently improves candidate coverage and Hit@10 over individual positive or negative hypergraphs.Positive and negative variants achieve comparable retrieval accuracy, indicating complementary semantic signals.
  • QQP: 64.06% Hit@10: Complementary HEI on QQP with MiniLM, versus 62.26% for Positive HEI and 64.51% for FAISS Flat.The complementary result is within 0.45 percentage points of the exact baseline.
  • QQP: 60.84% Hit@10: Complementary HEI on QQP with BGE-small, up from 55.37%, while Gold Recall rises from 71.48% to 84.97%.
  • STS-B: 96.97% Hit@10: Complementary HEI on STS-B with MiniLM, up from 91.29%, with Gold Recall reaching 97.73%.FAISS Flat achieves 98.48% Hit@10 on this setting.
  • STS-B: 97.73% Hit@10: Complementary HEI on STS-B with BGE-small fully matches FAISS Flat.
  • Source of Gains: Identical Stage-2 cosine reranking across HEI variants means the Hit@10 gains stem from improved Stage-1 candidate generation.
  • Latency: FAISS Flat has lower absolute latency on these small, CPU-cache-fitting benchmarks, whereas HEI targets large corpora where exhaustive multiplication is costly.FAISS Flat measures 0.29 ms on QQP and 0.05 ms on STS-B.

8 Embedding Activation Analysis

Embedding activation statistics strongly affect coordinate-inverted indexing: higher activation diversity yields selective hyperedges and smaller candidate pools, while coordinate hubs inflate candidates.

  • Model-Dependent Indexability: MiniLM produces much smaller candidate pools than BGE-small: approximately 2.9k versus 27k on QQP.
  • Model-Dependent Indexability: Activation diversity is proposed as a diagnostic metric for coordinate-inverted frameworks because semantic retrieval quality and coordinate indexability can differ.
  • Activation Statistics: MiniLM has Hnorm = 0.988 and G = 0.205, whereas BGE-small has Hnorm = 0.850 and G = 0.603 on QQP.The statistics indicate more uniform MiniLM activations and more concentrated BGE-small activations.
  • Hypergraph Selectivity: High activation diversity produces nearuniform coordinate selection, minimizing hyperedge collisions and maintaining compact posting lists and small Stage-1 pools.The supported indicators are Hnorm →1 and G →0.
  • Hypergraph Selectivity: Low activation diversity concentrates selections in hub dimensions, causing posting-list collisions and larger candidate pools without added discriminative power.
  • Candidate Pool Efficiency: 209 candidates: MiniLM’s average Complementary HEI pool on STS-B, compared with 8.8k for BGE-small.This follows the same model-dependent candidate-pool pattern observed on QQP.
  • Conclusion: Uniform coordinate activations improve candidate-pruning efficiency, while low-diversity embeddings suffer candidate-set inflation from coordinate hubs.

9 Conclusion

HEI uses higher-order latent activation combinations and complementary activation views to approach exhaustive retrieval recall while pruning candidate pools; activation diversity governs indexability.

  • Conclusion: HEI constructs inverted posting lists from higher-order combinations of latent embedding activations and combines complementary views.The framework organizes documents through multi-dimensional hyperedges for candidate generation.
  • Conclusion: HEI achieves retrieval recall competitive with exhaustive vector search while pruning candidate evaluation pools.
  • Conclusion: Activation diversity is identified as a critical determinant of indexability in coordinate-inverted retrieval.
Loading 2608.22980v1…