acceptodds
Under review as a conference paper at ICLR 2027

HEMLOCK - Hybrid Entity Multi-hop Linkage Over Co-occurrence Knowledge

Abstract

A multi-hop question needs documents it reaches only through entities it never names, and on -% of questions ColBERTv2's top misses one. Closing that gap usually costs a generative call per indexed passage or reasoning step. HEMLOCK makes none: a bipartite graph links text segments to the entities they mention, and a Personalised PageRank walk seeded from ColBERTv2 reaches bridge segments through shared entities for a cross-encoder to rerank. It spends zero LLM tokens at index and query time, serves a query in \ms and needs no per-corpus tuning. On HotpotQA, 2WikiMultihopQA and MuSiQue the walk adds -pp of passage recall@ over the same pipeline without it; no other system we evaluate that makes no generative calls retrieves more, LinearRAG at its published configuration included. HEMLOCK reaches -% of the document recall@ of HippoRAG 2, whose graph is LLM-built, and exceeds IRCoT's by -pp. Where ColBERTv2's top- misses a gold document, no reranker over that list can recover it; the walk lifts , and % of them into the top ten, raising exact match under a frozen reader.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Multi-hop question answering, Retrieval-augmented generation, Information retrieval, Graph-based retrieval

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_chn4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper introduces HEMLOCK, a graph-based retrieval pipeline for multi-hop question answering (QA). The pipeline has three stages: (1) initial segment retrieval using ColBERTv2, (2) construction of an entity-based graph from the retrieved segments, and (3) importance scoring of graph nodes via Personalized PageRank (PPR), followed by a final reranking step using a lightweight cross-encoder. The authors evaluate HEMLOCK on HotpotQA, 2WikiMultiHopQA, and MuSiQue, reporting improved retrieval recall compared to a series of retrieval systems, alongside gains in downstream QA performance compared to IRCoT and HippoRAG2.

Critical strengths
  • The approach is computationally lightweight compared to current LLM-based retrieval methods. By using PPR and a small cross-encoder (22M parameters) instead of expensive LLM reasoning loops, the paper presents a more scalable alternative for context expansion.
Critical weaknesses
  • The core assumption of HEMLOCK is that all necessary evidence for a multi-hop query can be retrieved in a single pass, which is against the nature of multi-hop QA. Multi-hop QA is inherently sequential, as the answer to the n-th hop depends on the entity extracted from the (n-1)-th hop. These conditional dependencies are ignored by the present algorithm, as the PPR expands and explores the search space in one shot. For only few hops, or when hops have high entity overlap or relations of future hops are distinct, this can work. However, the approach is not tested on longer reasoning chains, with experiments in the paper being restricted to 2-hop questions.

  • The reported QA metrics are well below state-of-the-art results on 2WikiMultiHopQA and MuSiQue. For example, Interact-RAG (Hui et al., ICLR 2026) achieved 69.6 exact match (EM) on 2WikiMultiHopQA and 34.8 EM on MuSiQue with Qwen3-8B, and IGPO (Wang et al., ICLR 2026) 72.1 EM on 2WikiMultiHopQA and 32.7 EM on MuSiQue with Qwen2.5-7B, compared to the 29.3 EM and 20.8 EM achieved in this work. Only on HotpotQA there is an improvement compared to these approaches: HEMLOCK achieves 65.0 EM, while IGPO reports 59.0 EM and Interact-RAG an exact match of 51.6. While I recognize that the retrieval corpus and setup might differ, such a large gap requires discussion and comparisons to the state-of-the-art in comparable setups.

Questions for authors
  • How does the performance scale for questions as the number of hops increases?

  • The claim that HEMLOCK has no costs (e.g., "Multi-hop retrieval at $0 per query") is overstated. While HEMLOCK avoids expensive LLM calls, there is still an overhead added to the plain ColBERT retrieval: graph construction (NER and coreference resolution), PPR and a reranker that processes segments independently. Could the authors provide a more realistic measure for cost?

  • How does the work relate to prior work on graph-based QA, such as GRAFT-Net (Sun et al., EMNLP 2018) and PullNet (Sun et al., EMNLP 2019), which also employ PPR for exploring the graph?

  • Could the method benefit from stronger first-stage retrieval (e.g., RRF+CE), providing better seeds for the PPR walks?

1 comment

Thank you for the review and for the suggestion about stronger seeds, which turned out to matter a great deal.

Clarification. The graph is built offline over the whole corpus, not from the retrieved segments. At query time it is only scored.

Sequential multi-hop. We have three results. First, hop strata: on MuSiQue 3/4-hop questions, HEMLOCK as submitted loses 4.9 points, whereas with stronger seeds the change is +0.5 (not significant) and 4-hop questions gain +2.0 (significant). Second, we implemented the sequential variant you describe, in which a second round is seeded from the first round's top evidence. We tried both ways of merging the rounds, re-applying the candidate cut or keeping everything, and neither changes recall by more than 0.7 points on any set. One-shot expansion is therefore not the bottleneck. The candidate cut is, and G3 fixes it. Third, breadth: on 2Wiki's 4-document questions, which have two parallel bridges, the gain is +11.3 as submitted and +15.0 with stronger seeds.

EM compared with the state of the art. The cited systems are multi-step LLM agents. HEMLOCK is a retriever that makes no LLM calls, so it corresponds to their search tool rather than to the whole agent. Interact-RAG's ablation shows that the gap comes from the agent. Its training-free workflow with plain search reaches 56.3 EM on 2Wiki, against 35.9 for standard RAG. Our frozen reader scores only 46.9 EM on 2Wiki even with the gold passages, so the gap lies in the reader and the setup rather than in retrieval. The 65.0 EM quoted for HotpotQA is our train-split number at k = 20.

Q2 ("$0 per query"): We agree and will reword it to "zero generative calls". The measured cost is \0.05per1,000queries,unbatchedonanH200,whichisabout0.05 per 1,000 queries, unbatched on an H200, which is about \\0.015 above ColBERTv2+CE, plus \0.21to0.21 to \\0.36 per index. On the same GPU IRCoT costs \0.95to0.95 to \\1.18 per 1,000 queries, or \0.26to0.26 to \\0.37 through an API. Further details are in G2.

Q4 (Stronger first-stage seeds): Yes, and thank you for suggesting it. Seeding from the cross-encoder's top 5 improves every set and fixes the depth failure (G3).

Q3 (GRAFT-Net and PullNet): Both are trained and work over a knowledge base. Please see our reply to Reviewer R2 for the full comparison.

Reviewer_obrcOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces HEMLOCK, an extractive, LLM-free retrieval pipeline designed for multi-hop question answering. Existing multi-hop retrieval methods either rely heavily on generative LLMs for knowledge graph extraction (e.g., HippoRAG 2) or iterative chain-of-thought retrieval (e.g., IRCoT), incurring significant latency and API costs. Standard dense/late-interaction retrievers (e.g., ColBERTv2), on the other hand, frequently fail when bridge passages lack lexical/semantic overlap with the query.To bridge this gap without generative calls, HEMLOCK extracts named entities offline (via NuNER + spaCy), applies canonicalization, and builds an unweighted bipartite segment-entity graph. At query time, top-kk hits from ColBERTv2 seed a Personalized PageRank (PPR) walk to surface bridge passages, which are subsequently reranked using a lightweight cross-encoder (ms-marco-MiniLM-L-6-v2). The paper also shows that the steady-state PPR distribution over bipartite segments can be reduced to a two-pass sparse matrix-vector multiplication featuring an entity degree discount (1/degE1/\text{deg}_E). Evaluations across HotpotQA, 2WikiMultihopQA, and MuSiQue demonstrate competitive passage recall and downstream QA accuracy under a frozen reader, with reported query latencies around 96 ms.

Critical strengths
  1. Practical Motivation: Dispensing with generative LLM calls during both indexing and query serving addresses a prominent real-world cost and throughput bottleneck in GraphRAG systems.

  2. Effective Bridging for Dense Failures: The empirical analysis on failure recovery (Section 5.2 / Figure 3) is compelling. The paper convincingly shows that when ColBERTv2 misses gold documents in the top-30, HEMLOCK recovers 21.7%–49.5% of them into the top-10, demonstrating the value of entity co-occurrence edges.

  3. Sound Theoretical Simplification: The derivation in Section 3.3 and Appendix J showing that the bipartite PPR walk can be approximated via two sparse incidence passes—and the analytical ablation highlighting the criticality of the degree discount (1/degE1/\text{deg}_E)—is mathematically neat and insightful.

  4. Token Efficiency: By retrieving granular 3-sentence segments rather than entire documents, HEMLOCK supplies higher gold evidence density per reader token compared to baselines like LinearRAG.

Critical weaknesses
  1. The Core Claim of "Efficiency" Is Not Empirically Solid The paper repeatedly emphasizes that HEMLOCK is an ultra-fast, production-friendly system ($0 query cost, 96 ms latency). However, the experimental methodology supporting the efficiency claims suffers from several methodological issues:
  • Confounded Hardware Benchmarks (Cross-GPU Comparisons): In Section 4 and Table 7, HEMLOCK’s 96 ms latency was measured on an NVIDIA H200 (with 2TB RAM and a 64-core Xeon), whereas the local vLLM IRCoT baseline was run on an NVIDIA B200. Comparing wall-clock times across distinct GPU architectures and memory bandwidth profiles undermines the scientific validity of the comparison. While the authors briefly acknowledge this in parentheses, using it to substantiate claims of being "4.5–7x faster" is problematic.

  • Network & Queueing Latency Confounded with Compute: Comparing local pipeline execution against cloud API endpoints (e.g., OpenRouter latencies of 21–29 s/query for IRCoT) is comparing compute latency against network RTT and external queuing delays.

  • Disconnect Between Theoretical Acceleration and System Latency: The authors make a major contribution out of the two-pass reduction, reporting an 18–26x speedup (from 32–59 ms down to 1.3–3.2 ms) at the graph scoring stage. However, as admitted in Appendix J, this has negligible impact on the overall 96 ms query latency, which remains heavily dominated by ColBERTv2 and Cross-Encoder neural passes. Thus, the practical end-to-end impact of this optimization appears marginal.

  • Underreported Indexing Overhead: While the paper advertises "zero generative calls," the offline indexing pipeline is computationally heavy: sliding-window coreference resolution, multi-backend NER (NuNER 209M + spaCy), three-stage fuzzy clustering canonicalization, and building PLAID indexes. As Table 7 notes, indexing takes 5–15 minutes on relatively tiny corpora (6k–12k documents), whereas LinearRAG requires only 40–87 seconds (~10–15x faster). The paper does not provide FLOPs, wall-clock breakdowns, or memory footprints for this complex offline process.

  1. Ranking as an Unresolved Bottleneck

Section 5.5 and Appendix M show that the majority of missed gold evidence was actually traversed by the graph walk, but dropped due to reranking limitations (ColBERT top-30 and MiniLM-L-6). When switching rerankers (e.g., to BGE-Reranker-Base), recall fluctuates significantly. The paper leaves the impression that graph traversal is only a small piece of the puzzle, and performance remains fundamentally gated by the cross-encoder's capacity.

Questions for authors
  • Standardized Hardware Benchmarking: Could you report end-to-end latency and throughput (queries per second) for all local baselines (ColBERTv2+CE, LinearRAG, IRCoT-local) strictly on the same machine and GPU (e.g., either purely on the H200 or purely on the B200)?

  • End-to-End Latency Breakdown: Could you provide a clear latency breakdown (in milliseconds) of the 96 ms per-query time: How many ms are spent on (a) ColBERTv2 seed retrieval, (b) graph propagation (PPR / two-pass), (c) candidate assembly/filtering, and (d) Cross-Encoder scoring?

Reviewer_6rpsOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes HEMLOCK, a multi-hop passage retrieval pipeline that requires no generative LLM calls. It constructs a segment–entity graph, seeds Personalized PageRank with ColBERTv2 retrieval results, and reranks the selected passages using a cross-encoder. Experiments on three multi-hop QA benchmarks show improvements in retrieval recall and downstream answer accuracy.

Critical strengths
  1. Good experimental performance. HEMLOCK consistently improves retrieval recall across three multi-hop QA benchmarks, with gains translating into improved answer accuracy under a fixed reader.

  2. Informative ablations. The ablations isolate the effects of graph propagation, degree normalization, and candidate selection, helping explain which components drive the improvements.

Critical weaknesses
  1. Limited methodological novelty. HEMLOCK combines established components: entity extraction and canonicalization, a segment–entity graph, seeded Personalized PageRank, and cross-encoder reranking. Its differences from closely related approaches, particularly SPRIG and LinearRAG, appear primarily to concern seed selection and candidate filtering. Although the experiments demonstrate practical benefits, the paper does not clearly establish a substantive methodological advance.

  2. Misleading motivation and incomplete historical positioning. The introduction suggests that retrieving unnamed bridge evidence requires expensive generative LLM calls. However, non-generative graph-guided and iterative retrieval methods addressed this problem well before LLM-based approaches, including GRAFT-Net, PullNet, and Asai et al.’s graph retriever. Comparing against IRCoT and other LLM-heavy systems demonstrates a cost–accuracy trade-off, but does not establish an advance over this earlier literature. The limited discussion and evaluation of these established approaches make the contribution difficult to assess.

Questions for authors

None. My concerns are about the methodological novelty and positioning against prior work described above, rather than specific clarification questions.

2 comments

Thank you for the review. We agree that our positioning was incomplete, and the revision corrects it.

Earlier non-generative methods. The revision adds GRAFT-Net, PullNet and Asai et al. All three are trained on question-answer data. GRAFT-Net is a graph convolutional network over a knowledge base plus entity-linked text, and PPR around the question's entities is its subgraph-retrieval heuristic. PullNet is a graph CNN, weakly supervised on question-answer pairs, that learns which nodes to expand. Asai et al. train a recurrent retriever over Wikipedia's hyperlink graph. HEMLOCK needs no training on question-answer data, no knowledge base and no hyperlinks. It builds its graph from raw text with off-the-shelf NER and uses ColBERTv2 and the cross-encoder as released. Its niche is retrieval that runs on a new corpus without any question-answer data and without generative calls. For the same reason we do not run these methods as baselines: each needs question-answer pairs to train on, and GRAFT-Net and PullNet predict answer entities rather than ranking passages, so the comparison would not be like for like. We accept that the introduction implied only LLM-based methods retrieve bridge evidence, and the revision corrects this.

SPRIG and LinearRAG. We agree that our differences from them lie mainly in seeding and candidate selection. We do not claim a new walk or a new scoring rule: the degree-discounted score is the resource-allocation index (Zhou et al., 2009), which the paper credits.

What we think the paper contributes. We see its value as a strong, cheap reference point rather than a new operator. HEMLOCK is the strongest retriever we evaluate that makes no generative calls, and it reaches 85 to 95% of the recall of HippoRAG 2, whose graph is built by an LLM, at $0.05 per 1,000 queries (G2). Future graph-based retrievers can then report how much they add over an entity co-occurrence graph built with off-the-shelf NER, not only over dense retrieval.

The analyses also identify a limitation we expect any retriever to share that expands candidates through a graph and then reranks them against the question: a cross-encoder scores relevance to the question, and a bridge passage is by definition one the question does not name. Where ColBERTv2's top 30 misses a gold document, the walk lifts 49.5, 39.9 and 21.7% of them into the top ten (Section 5.2), yet of the evidence HEMLOCK still misses, 31 to 52% is already in the cross-encoder's pool. Gold that only the graph reached makes the top ten far less often (59.3, 42.8 and 28.7%) than gold ColBERTv2 had already found (96 to 98%). The gap narrows with a reranker trained on different data but persists: under bge-reranker-base, graph-only gold reaches the top ten 59.7 and 40.2% of the time on 2Wiki and MuSiQue, against over 90% for gold ColBERTv2 had found (Appendix N). For this class of retrievers, a large part of what remains is ranking bridge passages, not only reaching them (Section 5.5). The general response adds new evidence on soundness (G1 to G3).

Thank you for your response! Unfortunately, I’m not able to access the revision you referred to, as the current PDF still appears to be the original version.

My main concerns regarding the methodological novelty and motivation of the work remain insufficiently addressed. LLM-based methods are not the de facto standard for this task. Multi-stage (graph) retrieval and ranking pipelines were already well-established approaches before the emergence of LLMs and would therefore serve as more appropriate baselines for comparison.

While the proposed method may offer computational cost advantages over LLM-based approaches, I do not find this comparison alone sufficient to establish a compelling motivation or a significant methodological contribution.

Given the above reasons, I will maintain my original rating.

Reviewer_vRq1OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper presents HEMLOCK for 2-hop question answering that chains off-the-shelf extractive components without using generative LLMs. The proposed bipartite PPR walk reduces to a two-pass sparse neighborhood lookup, and the pipeline was evaluated on 1,000-query 2-hop subsets of three QA datasets. The work serves as a practical systems benchmark showing that simple inverse-degree-weighted entity co-occurrence can approach LLM-based GraphRAG recall at sub-100 ms latency, without introducing new learning parameters or algorithm designs. The manuscript suffers from a fragmented presentation, and its evaluation is compromised by performing manual architecture selection directly on the eval splits.

Critical strengths
  • The paper demonstrates that an entirely non-generative pipeline using off-the-shelf encoders and degree-discounted entity co-occurrence can capture 85–95% of the recall of expensive LLM-indexed graphs (HippoRAG 2) in under 100 ms per query, offering a practical cost-latency reference point.
  • Section 5.5 provides empirical insights for multi-hop QA that graph walks already surface most missing gold passages into the candidate pool, but standard cross-encoders fail to promote them into the top-10 because bridge passages lack direct lexical overlap with the query.
Critical weaknesses
  • HEMLOCK is an assembly of off-the-shelf models and heuristics. The proposed graph stage mathematically collapses to a two-step sparse lookup identical to the Resource Allocation index.
  • A central claim of this paper is "zero per-corpus tuning" compared to baselines like LinearRAG. Appx. L revealed that15 architectural variants were iteratively designed, evaluated, and pruned directly on these benchmark questions after inspecting their scores, which essentially replaced hyperparameter tuning with manual architecture selection on the evaluation data.
  • The manuscript is difficult to follow. It frequently switches context, evaluation granularities, and between dataset splits.
Questions for authors
  1. Because the two-pass sparse reduction (M2M^2) explicitly models a single segment → entity → segment hop and all experiments restrict evaluation to 2-hop subsets, how does the pipeline perform on MuSiQue’s 3- and 4-hop questions? Does extending the operator to higher-order passes introduce compounding entity-hub noise?
  2. How much of HEMLOCK's recall gain survives if the Wikipedia-tailored indexing rules are disabled, specifically anchoring entity mentions to corpus document titles and resolving pronouns to the last PERSON within four sentences?
  3. Table 20 shows that truncating the candidate union purely by PPR score degrades recall whenever the query names both target entities, as valid ColBERTv2 hits are discarded before reranking. Can this regression be resolved without introducing a tuned mixing hyperparameter between lexical and graph scores?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.