When a retrieval system answers a multi-hop question such as "which river flows through the birthplace of the author of X?", it usually looks for the single best chain of facts that links the question to an answer. A more trustworthy signal is how many chains support the answer independently: chains that are built from different source documents. One chain can be an accident of a single bad page. Five chains from five unrelated sources are corroboration. Counting such chains is hard in general, because the number of candidate chains grows exponentially with their length, and because "uses distinct sources" is a global constraint that greedy search cannot enforce. This note proposes to compute that count with color coding, a technique from graph algorithms. Color coding assigns each item one of $k$ colors, then searches only for structures whose items all have different colors. That restriction lets a dynamic program track a set of colors instead of a list of visited items.
The concrete proposal has three parts. We break documents into atomic propositions, meaning minimal self-contained factual statements. We link propositions that share an entity. We then color each proposition by a hash of its source document and count "source-colorful" chains of length up to $k$ from the question entities to each candidate answer. A deterministic, balanced family of hash functions turns this count into a reproducible approximation with a guaranteed error band. The central empirical claim is that this count ranks answers, and detects unanswerable questions, better than the best-single-chain score produced by beam search over the same graph. It should do so at a cost that is linear in the size of the query's local graph rather than exponential in its degree.
Core Claim and What Is New
Proposition graphs for multi-hop retrieval already exist. Hierarchical Lexical Graph for Enhanced Multi-Hop Retrieval builds lineage, topic and entity tiers over propositions. Its StatementGraphRAG retriever runs an entity-aware beam search with a 0.5% diversity threshold. This paper motivates our work, since it shows proposition graphs beat chunk retrieval. It also leaves the gap we target: its search returns high-scoring chains, with no guarantee about coverage and no notion of how many independent chains exist. On the summarization side, Proposition-Level Clustering for Multi-Document Summarization uses cross-document cluster size as a salience signal. That is a count of single repeated propositions, not of multi-step chains. We extend the "redundancy equals salience" intuition from single facts to $k$-hop reasoning chains, where exhaustive counting is no longer feasible.
The method comes from Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs, which finds colorful paths in $2^{O(k)}\cdot m$ time on a graph with $m$ edges. It also comes from Balanced Families of Perfect Hash Functions and Their Applications. That paper builds explicit hash families in which every $k$-subset is mapped injectively a nearly equal number of times. This yields deterministic $(1\pm\delta)$ approximate counting of paths. Neither paper touches text.
Our one conceptual change is to color by provenance rather than by vertex identity. Standard color coding hashes vertices so that colorful means "no repeated vertex." We hash source documents so that colorful means "every hop comes from a different document." That is exactly the independence notion corroboration needs, and it is a constraint that a visited-set search over propositions does not enforce.
Let $c(p)\in\{1,\dots,k\}$ be the color of proposition $p$, obtained by hashing its source document. Let $N(p)$ be the propositions sharing an entity with $p$. Let $C(p,S)$ be the number of chains ending at $p$ whose propositions carry exactly the color set $S$, each color once. The counting recurrence is
$$C(p,S)=\sum_{q\in N(p)} C\big(q,\,S\setminus\{c(p)\}\big),\qquad C(p,\{c(p)\})=\mathbb{1}[p \text{ mentions a question entity}].$$
Summing $C(a,S)$ over answer-bearing propositions $a$ gives the colorful count under one coloring. Suppose $N_k$ is the true number of source-distinct chains of length $k$. A uniformly random coloring makes each such chain colorful with probability $k!/k^k$. Over a $\delta$-balanced family $\mathcal{F}$, each chain is made colorful by between $T/\delta$ and $\delta T$ functions, where $T$ is the family's baseline count. The estimator is therefore
$$\hat N_k=\frac{1}{T}\sum_{f\in\mathcal{F}} \mathrm{colorful}_f, \qquad \hat N_k\in[N_k/\delta,\ \delta N_k].$$
Here $\mathrm{colorful}_f$ is the colorful count under hash function $f$. The guarantee is inherited directly from Alon and Gutner, and it means the same query always receives the same score.
Research Program
We build the graph with the open GraphRAG Toolkit released with the Hierarchical Lexical Graph paper. That keeps the proposition extraction, entity linking and lineage tier identical to the strongest baseline. Our work then begins at the search step.
For each query we take the local subgraph the toolkit already retrieves. On that subgraph we run the counting dynamic program for $k=2$ to $5$. Answer candidates are scored by a combination of the length-wise counts $\hat N_2,\dots,\hat N_k$ and the existing chain-relevance scores. The top colorful chains are then handed to the reader model. Because colorful chains can be recovered from the dynamic program table, we can also give the reader a small set of source-diverse chains rather than the beam's near-duplicates.
The combinatorial feature selection literature serves as our methodological lens, not as a second application. The family of candidate signals is combinatorial: counts by chain length, by reasoning shape (MuSiQue defines six graph shapes), by source type, and weighted versus unweighted. Testing all subsets reproduces the $2^N$ problem. We will instead use the incremental-gain test from OpenFE: Automated Feature Generation with Expert-level Performance. OpenFE freezes a base model and fits a small model on its residuals with only the candidate signal, so each count type is scored without full retraining. OpenFE also warns that deeply nested features add noise. That warning is a constraint for us: we expect gains to saturate around $k=4$, and we will report where they stop.
On the derandomization side we implement two things. One is a practical balanced family: splitters followed by small perfect hash families, as in Alon and Gutner. The other is plain Monte Carlo coloring with the same number of colorings. We will measure the actual family sizes, since the theoretical $2^{O(k\log\log k)}\log n$ bound hides constants that may be prohibitive. The open-problem record in the file flags this gap between theory and practice explicitly. We will treat any shortfall as a result to report, not a detail to bury.
Baselines
The naive reference point is chunk-based dense retrieval with the same reader. In the Hierarchical Lexical Graph evaluation, the proposition-graph retrievers beat this setup by an average relative 23.1% in recall and correctness. It shows how much any graph method buys before counting enters.
The strongest existing method is StatementGraphRAG with the 0.5% diversity threshold, run from the GraphRAG Toolkit. That paper reports an average correctness of 73.6% across its five-domain suite, 7.5 points above its best baseline. It is the right competitor because it uses the same proposition graph and differs from us only in how chains are found and scored. We run it with its released configuration on the same graphs, the same reader model and the same final context-token budget. Its beam width is tuned on a development split with the same number of trials we give our scoring combination. Beating it means a statistically significant correctness gain on the five-domain average and on MuSiQue. A tie that comes with much better unanswerable-question detection would also count as a meaningful result.
On HotpotQA, the only system number in the file is the dataset paper's BiDAF baseline: 58.28 answer F1 in the distractor setting and 17.73 joint F1 in the full-wiki setting. That is a floor, not a competitor. For MuSiQue, no reported result was found on Lacuna for any retrieval system; only the human reference of 78.0 answer F1 is available. We will therefore run all methods ourselves there.
Three ablations isolate the key ingredient. The first replaces counting with the single best colorful chain, which tests whether counts matter at all. The second colors by proposition identity instead of by source document, which tests whether the provenance constraint matters. The third replaces the balanced family with Monte Carlo coloring under a matched number of colorings, which tests what determinism costs or buys. Where the local graph is small enough, exact enumeration with source-distinctness provides ground-truth counts to check $\hat N_k$ against.
Why not just…?
Why not just keep beam search and count the distinct chains in the beam? A beam keeps the top-scoring partial chains. Those tend to pass through the same high-relevance hub propositions, so the beam undercounts independent chains in exactly the cases where corroboration is spread across lower-scoring sources. The best-chain and beam-count ablations test this directly. If counting within a wide beam matches our estimator, the color-coding machinery is unnecessary, and we would report that.
Why not just enumerate chains exactly with a visited set? For $k=2$ or $3$ on sparse local graphs this probably works, and we will use it there as ground truth. The cost grows as roughly $d^k$, where $d$ is the degree, and entity hubs in proposition graphs (a country, a year, a company name) can have hundreds of neighbors. Enforcing distinct sources also requires carrying the set of used documents, which is the state explosion color coding removes. We will plot runtime of exact enumeration against the dynamic program as hub degree and $k$ grow. The honest prediction is a crossover near $k=4$, not a uniform win.
Why not just use random colorings, which are simpler and unbiased? This is the most serious alternative. On accuracy it may well match the deterministic family at equal cost. The balanced family's advantage is a worst-case error band and identical scores on repeated runs, which matters for audited domains such as the SEC filings and aviation reports in the HLG suite. We will report variance across seeds for Monte Carlo alongside the deterministic band. If Monte Carlo matches on accuracy, the paper's claim narrows to reproducibility, and we will say so.
Why not just let the reader model judge how well-supported an answer is? Readers see only what fits in context; BRIEF, for example, works within a 512-token window. Readers cannot count chains they were never shown. We will include a condition where the reader receives the beam's context and is prompted to rate support, then compare its calibration on unanswerable questions with the count signal.
Proposed Experiments and Decisive Checks
We evaluate on HotpotQA in the full-wiki setting, on MuSiQue-Ans and MuSiQue-Full, and on the five-domain suite from the Hierarchical Lexical Graph paper (MultiHop-RAG, SEC-10Q, ConcurrentQA, NTSB, WikiHowQA). ♫ MuSiQue: Multihop Questions via Single-hop Question Composition was built so that disconnected single-hop shortcuts fail, which makes it the sharpest test of whether chain counts carry real signal. Metrics are answer exact match and F1, supporting-fact F1, the HLG paper's correctness and recall, AUROC for flagging unanswerable MuSiQue-Full questions, and wall-clock time per query at each $k$.
Four checks decide the proposal. First, at a fixed retrieved subgraph and a fixed reader, count-based scoring must beat best-chain scoring; otherwise the core claim fails. Second, source coloring must beat proposition coloring, especially on the HLG domains where documents restate one another. If it does not, provenance is not the right notion of independence. Third, on MuSiQue-Full, a near-zero colorful count should predict unanswerability better than beam scores do. Fourth, against exact enumeration, the estimator must stay within its stated error band while running faster on high-degree subgraphs at $k\ge4$, and the measured size of the deterministic family must be reported honestly next to the Monte Carlo cost.
References
- Hierarchical Lexical Graph for Enhanced Multi-Hop Retrieval
- Proposition-Level Clustering for Multi-Document Summarization
- Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs
- Balanced Families of Perfect Hash Functions and Their Applications
- OpenFE: Automated Feature Generation with Expert-level Performance
- ♫ MuSiQue: Multihop Questions via Single-hop Question Composition