RAG over dense entity-rich documents, 85% faster — by pruning before embedding.
Hierarchical entity-indexed knowledge retrieval with Cuckoo Filter acceleration. Prunes irrelevant document clusters before dense embedding — achieving sub-5ms P99 retrieval latency at scale.
For non-technical readers: Searching through thousands of medical records, legal documents, or technical specs to answer a question is slow when you have to check every single document. EntityTree is smarter — it first asks "does this document even mention the things I'm looking for?" using an ultra-fast lookup table. If a document cluster doesn't contain the right entities (like a drug name or a specific legal term), it's skipped entirely. This makes retrieval up to 85% faster by only doing the expensive search on the small fraction of documents that might actually be relevant.
Standard vector search over large document sets evaluates all chunks — or all cluster centroids — incurring latency proportional to corpus size. EntityTree introduces a two-phase retrieval pipeline: a hardware-efficient Cuckoo Filter membership check eliminates document subtrees that cannot possibly contain the query entities before a single dense embedding is computed.
❓ Query: "What dosage of Lisinopril was prescribed for hypertension?"
│
▼
🔍 Named Entity Extractor
Entities: ['Lisinopril', 'hypertension']
│
▼
⚡ Cuckoo Filter Fast-Pruning
For each document subtree in the hierarchy:
Is 'Lisinopril' ∈ subtree? (O(1) probabilistic lookup)
Is 'hypertension' ∈ subtree?
Subtrees failing entity membership check → pruned
~85% of subtrees eliminated before embedding
│
▼
🧠 Dense Vector Reranking
Evaluates only the surviving candidate nodes
Full semantic similarity over reduced candidate set
│
▼
📄 Final Context Chunks ⚡ <5ms P99 latency
Cuckoo Filter Properties — Cuckoo Filters provide set-membership lookups in O(1) time with a configurable false-positive rate (< 1% in this implementation). Crucially, they support deletion (unlike Bloom Filters), which allows the entity index to be updated as new documents are ingested without rebuilding the entire filter structure.
Hierarchical Tree Structure — Documents are organized into a hierarchy based on entity co-occurrence density: documents sharing many entities cluster together. This makes the pruning more effective — a subtree containing only cardiology records is fully pruned for a query about contract law, not just individual documents.
Named Entity Extraction — The NER model runs on queries (not documents) to extract lookup entities before the Cuckoo Filter is queried. The entity vocabulary in the filter is populated at indexing time using the same NER model over all document text — ensuring consistent entity surface form matching between query and index.
False Positive Handling — The ~1% Cuckoo Filter false-positive rate means a small fraction of non-matching subtrees survive pruning. These are harmlessly passed to the dense reranker, which correctly scores them low. The reranker is the correctness backstop; the filter is purely a performance optimization.
| Metric | Standard Vector Search | EntityTree |
|---|---|---|
| ⚡ Corpus Pruning | None | ~85% of subtrees eliminated |
| 🕐 P99 Retrieval Latency | Scales with corpus | < 5ms |
| 🎯 Recall@K | Baseline | Comparable (filter false-positives handled by reranker) |
git clone https://github.com/nathaniel-gordon/entitytree
cd entitytree
pip install -e .# Run latency and retrieval quality benchmark
python main.py --benchmarkpytest tests/ -ventitytree/
├── src/
│ └── etree/
│ ├── ner.py # Named entity extractor for queries & documents
│ ├── cuckoo.py # Cuckoo Filter implementation & entity index
│ ├── tree.py # Hierarchical document tree & subtree pruning
│ ├── retrieval.py # Dense reranker over surviving candidates
│ └── __main__.py
└── tests/
Built by Nathaniel Gordon