Search systems miss relevant documents when the user and the author use different words for the same thing. This vocabulary mismatch is common: in open-domain question answering, many correct answers share no content words with the question (Yang et al.). Two kinds of fix exist. Dense neural retrievers match meaning rather than strings. Structured context, such as links, citations, or taxonomies, tells the system what a document is about even when its own wording is idiosyncratic. Both fixes are expensive at scale. Dense indexes need tens of gigabytes of RAM, and graph neural networks (models that update each node's vector by repeatedly averaging its neighbors' vectors) pull exponentially many neighbors into memory as they go deeper. The cheapest known way to shrink a dense index is to keep only the sign of each coordinate, a 1-bit code. Distances between such codes can then be computed with XOR and bit-counting instructions. Binary retrievers like BPR match full-precision accuracy at 30× less memory (Yamada et al.), but they treat every passage as an isolated chunk of text.
This note proposes giving each document two short binary codes instead of one. The first encodes the document's own text. The second is a bitwise majority vote over the codes of its graph neighbors: hyperlinked articles, cited cases, or catalog items under the same taxonomy class. The neighborhood code is computed without training, using only bit counts. It can be updated when an edge arrives without retraining anything, and it costs the same memory as a longer self-only code. The bet is that, under a fixed bit budget, spending some bits on "what my neighbors say" retrieves more zero-overlap relevant documents than spending all of them on "what I say." The reason is that neighbors often use the query's vocabulary when the target document does not.
Core Claim
At an equal number of bits per document, a code split into a self part and a majority-voted neighborhood part should beat a self-only binary code on recall for queries with little or no lexical overlap with their relevant documents. It should do so without a floating-point reranker. The gain should come from external structure (hyperlinks, citations, taxonomy edges) and not from generic smoothing. A neighborhood code built from the embedding's own nearest neighbors should therefore help much less. If both of these hold, the work shows a cheap, inductive way to put relational context into billion-scale binary indexes. If the equal-budget self-only code wins, the idea is wrong and the bits are better spent on the document itself.
Concretely, let $b_u \in \{-1,1\}^m$ be the self code of node $u$, produced by a binary text encoder. The hop-1 neighborhood code of node $v$ is
$$c_v = \mathrm{sign}\Big(\sum_{u \in \mathcal{N}(v)} b_u\Big),$$
with ties broken toward $b_v$. Here $\mathcal{N}(v)$ is $v$'s graph neighborhood, and the sum is a per-bit popcount over packed words. A query with binary code $q$ is scored as
$$s(q,v) = m - \mathrm{Ham}(q, b_v) + \alpha\, g_v \big(m - \mathrm{Ham}(q, c_v)\big),$$
where $\mathrm{Ham}$ is Hamming distance and $\alpha$ is a single weight tuned on development data. $g_v \in [0,1]$ is a neighbor-agreement gate: the fraction of bits whose majority margin exceeds a threshold, computed from the same popcounts. When a node's neighbors disagree with each other, as on hub pages or in graphs where linked nodes are often about different things, the neighborhood view is turned down. Hop-2 codes are defined the same way over $c_u$. The total budget is $B = 2m$ for one hop, and the comparison is always against a self-only code of length $B$.
Position Relative to Prior Work
Three binary retrievers supply the encoders and the evaluation targets. BPR trains a hash layer on top of a dense passage encoder and reranks with continuous query vectors (Yamada et al.). Bi-ColBERT binarizes token-level embeddings after balancing the spread of their singular values (Chen et al.). BEBR binarizes embeddings for a 6-billion-document web index and refreshes the index without retraining the backbone model (Gan et al.). All three encode each document from its own text alone. This proposal reuses their encoders unchanged and adds a relational view on the index side. It is complementary to all of them, and it would be pointless if a longer self code from them already did as well.
Graph binarization work shows that 1-bit representations survive message passing but stays away from text. BiGeaR++ binarizes every layer of a collaborative-filtering graph network over users and items (Zeng et al.). BitGNN writes GPU kernels for 1-bit sparse matrix products and reports up to 4% accuracy loss on Reddit (Chen et al.). That loss is a warning that binary aggregation can hurt on dense graphs, and it is why the gate exists. node2binary learns codes combinatorially and is transductive: it cannot embed a new node without re-optimizing (Talukder et al.). The proposal differs from all three in three ways: it has no trained message passing, it targets text retrieval, and a new node's codes come from a popcount over its neighbors.
The decision to use fixed aggregation rests on two results. One shows that non-trainable multi-hop reducers fed to an MLP match graph networks on 12 of 14 benchmarks (Fixed Aggregation Features Can Rival GNNs). The other shows that MinHash/HyperLogLog neighborhood sketches beat GNNs on knowledge-graph link prediction at a fraction of the training cost (Knowledge Graphs Can be Learned with Just Intersection Features). The FAF paper also reports a feature explosion as hops are concatenated. A majority vote keeps every hop at $m$ bits, which avoids that growth. FAFs also trail on Roman-Empire and Minesweeper, a reminder that fixed aggregation fails when the task needs many layers of reasoning.
Prior work on vocabulary mismatch with graphs motivates the claim that structure helps but leaves cost unsolved. CaseGNN lifts COLIEE 2022 Precision@5 from 17.9% (BM25) to 35.5% using edge attention over case graphs with float vectors (CaseGNN). RTA recasts message passing as retrieval over dense FAISS and Personalized PageRank neighbors (RTA). ECLASS search shows that adding taxonomy paths to catalog entries beats LLM query rewriting, which actually hurt (ECLASS-Augmented Search). That finding constrains the design toward enriching the document side rather than rewriting the query. It also reaches 94.3% Hit_Rate@5 only with an 8B reranker at 11.45 s per query. MINDER bridges the gap with titles, substrings, and generated pseudo-queries, but uses autoregressive decoding over an FM-index (Li et al.). The proposal asks how much of these gains survives when relational context is folded into bits.
Research Program
The first component is the index builder. It takes any binary encoder (BPR's hash layer, or sign-after-random-rotation of a dense encoder, following Werner's observation that rotation spreads variance before taking signs), a graph, and a bit budget. It produces packed self and neighborhood codes. Majority votes are computed as column popcounts over neighbors' packed words. Small per-bit counters are kept on disk so that adding or removing an edge updates $c_v$ in time proportional to $m$.
The second component is the analysis of where the bits go. For fixed $B$, we sweep the split between self and neighborhood bits, the number of hops, and the gate threshold. We measure recall overall and on a zero-overlap slice: queries whose gold passage shares no content words with the query after stopword removal.
The third component is an optional asymmetric fine-tuning step. The query encoder is trained against frozen index-side codes, so it learns to aim at neighborhood codes when the self code fails. This step is kept separate so the training-free result stands on its own.
Graphs come from structure external to the embedding. For NQ and TriviaQA over Wikipedia passages, the graph combines passages of the same article with passages of hyperlinked articles. For COLIEE, it is the citation links between cases. For the ECLASS catalog, items are linked through shared CL4 classes and their CL3 parents. MS MARCO has no natural graph, so it serves only for the embedding-kNN control.
Baselines
The do-nothing reference is BM25. The file reports BM25 at 16.7 MRR@10 on MS MARCO (Chen et al.), 17.9% Precision@5 on COLIEE 2022 (CaseGNN), and 31.4% Hit_Rate@5 on the ECLASS expert set (ECLASS-Augmented Search). Any binary method that fails to clear these on the zero-overlap slice is not addressing vocabulary mismatch.
The strongest direct competitor is BPR, run as a self-only binary index at the full budget $B$. On NQ, BPR reports 41.6 Exact Match against DPR's 41.5. It uses a 2.0GB index instead of 64.6GB, and candidate search takes 38.1 ms instead of 456.9 ms (Yamada et al.). There is no reported result on Lacuna for BPR's top-k retrieval recall, so we will re-measure it ourselves. BPR is the right opponent because it already solves memory and already bridges some of the vocabulary gap through dense semantics. Fairness rule: both systems use the same encoder checkpoint, the same total bits per document, the same candidate depth, and the same tuning budget, with $\alpha$ and the gate threshold tuned on the same development split BPR uses. Beating it means a statistically significant gain in Recall@20 on the zero-overlap slice at equal bits and equal Hamming-search latency, with overall Recall@20 no lower than BPR's.
Two reference points use more resources. The first is the full-precision dense retriever. For MS MARCO, FP32 ColBERT at 32.8 MRR@10 and Bi-ColBERT at 31.7 bound what binarization costs on a corpus without a graph (Chen et al.). The second is a full-precision graph method. CaseGNN at 35.5% Precision@5 on COLIEE 2022 is the target for structure-aware retrieval, and the ECLASS reranked pipeline at 94.3% Hit_Rate@5 and 11.45 s per query is the target for taxonomy-aware search. Matching these is not required. The question is what fraction of their gain over BM25 the binary system recovers, and at what memory and latency.
Three ablations isolate the key ingredient. Swapping the graph for the embedding's own nearest-neighbor graph tests whether external structure matters. Replacing majority vote with sign-of-float-mean tests whether staying in bit space costs accuracy. Setting the gate to one tests whether gating protects nodes whose neighbors disagree.
Why not just…?
Why not just give the self code more bits? This is the most direct threat, and the equal-budget BPR baseline is built to answer it. Longer self codes recover finer distinctions within a document's own wording, but they cannot add vocabulary the document never used. Our prediction is that extra self bits help mostly on lexically overlapping queries, while neighborhood bits help on the zero-overlap slice. If the $B$-bit self code matches the split code on that slice, the claim fails and we will report it as a negative result.
Why not just expand documents with generated pseudo-queries before encoding? MINDER shows that pseudo-queries bridge the format gap (Li et al.). Pseudo-query expansion followed by a binary encoder is a real competitor, and we will run it at equal bits. It costs one generation pass per document and has to be regenerated when content changes, whereas neighborhood codes cost a popcount. It may also hallucinate attributes, which is what hurt LLM rewriting in the ECLASS study (ECLASS-Augmented Search). The two approaches are combinable, so we will also test expansion together with neighborhood bits. If expansion alone dominates, the contribution shrinks to cheap incremental updates.
Why not just aggregate float embeddings, then binarize, as a graph network or FAF would? Sign-of-float-mean is close in spirit and may be equally accurate. It is included as an ablation. The case for majority vote is operational. At BEBR scale the float vectors are not kept online (Gan et al.), and a bit-space vote lets edges be updated without re-encoding the neighbors. If the float route is clearly more accurate, we adopt it at index build time and keep bit-space voting only for incremental updates.
Why not just add a cross-encoder reranker? Rerankers close most of the gap, as the 94.3% Hit_Rate@5 on ECLASS shows, but they cost 11.45 s per query on CPU (ECLASS-Augmented Search). Our method sits before any reranker. We will report the reranker's gain on top of each first stage. The useful outcome is that neighborhood bits let a shallower rerank depth reach the same accuracy.
Proposed Experiments and Decisive Checks
The main experiment runs NQ and TriviaQA retrieval over the 21M Wikipedia passages used by BPR, with hyperlink and same-article graphs. We report Recall@20/100 and downstream Exact Match, separately on the zero-overlap slice and on the rest, at budgets of 256, 512, and 768 bits per document, together with index memory and Hamming-search latency. The same protocol runs on COLIEE 2022/2023 with the citation graph, using Precision@5 against CaseGNN's 35.5%, and on the ECLASS catalog, using Hit_Rate@5 against BM25's 31.4% and the reranked 94.3%.
Three checks decide the claim. First, the split code must beat the equal-budget self code on the zero-overlap slice. Second, that gain must largely disappear when the external graph is replaced by an embedding-kNN graph; we also run this on MS MARCO, where only the kNN graph exists. Third, the gated version must not lose to the self code on nodes with low neighbor agreement. On graphs where linked nodes often differ in topic, such as the heterophilic web-page graphs where RTA is evaluated, we will check whether the gate correctly turns neighborhood bits off.
A last test checks the inductive property. We hold out 10% of Wikipedia articles, insert them afterwards with popcount updates only, and compare their retrieval quality against nodes that were present at build time. A small gap would show that the neighborhood view handles newly arriving nodes, which node2binary-style transductive codes and structure-free condensation cannot.
References
- WikiQA: A Challenge Dataset for Open-Domain Question Answering
- Efficient Passage Retrieval with Hashing for Open-domain Question Answering
- An Effective Post-training Embedding Binarization Approach for Fast Online Top-K Passage Matching
- Binary Embedding-based Retrieval at Tencent
- Learning Binarized Representations with Pseudo-positive Sample Enhancement for Efficient Graph Collaborative Filtering
- BitGNN: Unleashing the Performance Potential of Binary Graph Neural Networks on GPUs
- node2binary: Compact Graph Node Embeddings Using Binary Vectors
- Fixed Aggregation Features Can Rival GNNs
- Knowledge Graphs Can be Learned with Just Intersection Features
- CaseGNN: Graph Neural Networks for Legal Case Retrieval with Text-Attributed Graphs
- Rethinking Message Passing as Retrieval for Text-Attributed Graph Learning
- ECLASS-Augmented Semantic Product Search for Electronic Components
- Multiview Identifiers Enhanced Generative Retrieval