Split When Stuck, Merge When Easy: Run-Time Granularity for Multi-Hop Retrieval

Multi-hop questions such as "in what city was the director of Inception born?" break ordinary retrieval-augmented generation (RAG, where a language model answers using passages fetched by a search step). The original question does not contain the words needed to find the second fact. The standard fix is to break the question into smaller sub-questions and retrieve for each one. Planners such as Plan$^\ast$RAG break every question down to single-retrieval "atomic" steps before execution starts. This choice fixes the size of each unit of work in advance. Parallel-computing research has studied that same choice for decades under the name task granularity. Units that are too fine drown the system in coordination cost. Units that are too coarse leave parallelism unused and let one hard unit stall everything. In multi-hop RAG, fine units cost extra model calls and tokens. They also force the system to commit to an answer at every intermediate hop, and a wrong commitment cascades. Coarse units are cheap, but their retrieval query may lack the cue the next hop needs.

We propose to choose this granularity per hop, at run time, from cheap black-box signals. The system starts each question coarse, as one retrieval and one answer. It splits a unit into finer sub-questions only when a sufficiency check says the evidence did not resolve it. It merges sibling sub-questions back into one call when their retrieved evidence overlaps. The claim is empirical and falsifiable. The best granularity varies within a dataset and even within a single question, so a run-time policy should reach the accuracy of always-atomic decomposition at a fraction of its calls, and should beat any single fixed granularity tuned per dataset. If a per-question oracle turns out to be no better than the best fixed granularity, the idea is wrong. We test that first.

Core Claim and What Is New

The work closest to ours fixes granularity in one place or another. Plan$^\ast$RAG turns reasoning into a directed acyclic graph (DAG) of atomic sub-queries, planned once and executed layer by layer. Its authors list dynamic plan refinement and backtracking as open. SPARC-RAG scales parallel width and sequential depth with three fixed agent roles: a query rewriter, a context manager, and a trained stop/continue evaluator. Its unit of work is a batch of parallel queries per round, not a node whose size changes. Mix-of-Granularity routes each query to one of five fixed chunk sizes. HGRAG mixes entity-level and passage-level structure in the corpus. Both of these tune the granularity of retrieved data, not of reasoning steps. HeraSys does slice agent workflows into fine preemptible nodes and fuses duplicates across users. It treats nodes as black boxes, however, and never asks whether the slicing changes answer accuracy.

Our contribution is a node-level refine-and-coarsen rule for the reasoning graph itself, together with the measurement that justifies it. The mechanism takes its idea from workload coalescing in task-graph QR factorization. That work merges micro-tasks into batches under hand-set thresholds, and it names hand tuning of those thresholds as an open problem. We replace the hand-set thresholds with a decision driven by evidence sufficiency. The signal is deliberately black-box. DRAGIN showed that token entropy and attention can detect when a model needs retrieval, but it requires access to model internals, which rules out API-served models.

Research Program

The system keeps a graph whose nodes are questions of any size, from the original question down to single-fact lookups. Executing a node means one retrieval with the node's text as the query, then one generation that proposes an answer plus the bridge entities it used. A sufficiency check then scores the result. It has two cheap parts. The first is agreement among $k$ sampled answers. The second is a grounding test: do the proposed answer and each named bridge entity appear in the retrieved passages? If the node passes, its answer is committed and children that depend on it are released. The release is asynchronous, as soon as the parent resolves, rather than waiting for the whole layer as in Plan$^\ast$RAG.

If the node fails, it is split. The planner decomposes only that node, conditioned on whatever partial evidence was found, so later hops can use the cues earlier hops recovered. There is also a coarsening step. When two ready sibling nodes retrieve passage sets that overlap above a threshold, or when a parent's passages already contain the child's bridge entity, they are merged into one call.

We state the split rule compactly. Let $s(v)\in[0,1]$ be the sufficiency score of node $v$, and let $\tau$ be a single threshold. Node $v$ is split when

$$s(v) < \tau,$$

and $\tau$ is the only knob. We sweep it to trace a cost–accuracy curve rather than tuning it to one point. Splitting depth is capped at the gold hop count range of the benchmark (four for MuSiQue).

The program has three stages. The first is an oracle study that decides whether the idea has any room. The second builds the run-time policy. The third is a cost–accuracy comparison against fixed-granularity and adaptive-scaling baselines on the same retriever and model.

The oracle study uses MuSiQue. Its questions are composed from single-hop questions, so every question comes with a gold decomposition chain. For each question we enumerate every way of grouping its 2–4 gold hops into contiguous segments. There are $2^{h-1}$ groupings for an $h$-hop chain, which is at most eight. We execute each grouping and record answer F1 and call count. This gives us three things: the per-question best grouping, the best single fixed grouping rule per dataset, and how often coarse groupings succeed without decomposition.

Baselines

The naive reference point is one-shot RAG: retrieve once with the original question, then answer. It shows the size of the multi-hop gap on our exact setup. MuSiQue's authors report that single-hop models lose about 30 F1 on MuSiQue-Ans relative to HotpotQA, and the 2WikiMultiHopQA paper reports an 8.7-point drop, so we expect a large deficit.

The sequential baseline is IRCoT. It interleaves one chain-of-thought sentence with one retrieval, using each sentence as the next query. It reports 11–21 points of retrieval recall and up to 15 F1 over one-step retrieval across HotpotQA, 2WikiMultihopQA, MuSiQue and IIRC. It represents "fine granularity everywhere, strictly sequential."

The always-atomic baseline is Plan$^\ast$RAG. Its authors say it outperforms prior RAG methods on MuSiQue-Ans and HotpotQA, but we found no reported MuSiQue number on Lacuna for it, so we rerun it. We use its own setting, Contriever-MS MARCO over 100-word Wikipedia chunks, and adopt that retrieval setup for every system.

The strongest adaptive competitor is SPARC-RAG. It reports 24.3 F1 on MuSiQue against DeepNote's 19.8, with Qwen2.5-7B and Qwen3-32B. We run all systems on Qwen2.5-7B and, where compute allows, Qwen3-32B. We rerun SPARC-RAG under our retriever and corpus if its components are reproducible. We quote 24.3 only as a reference, because its corpus setup may differ. On 2WikiMultihopQA the relevant white-box reference is DRAGIN at 0.3931 F1 with LLaMA2-13B. We rerun DRAGIN with LLaMA2-13B alongside our method on that model, to compare a white-box trigger against our black-box one.

Fairness means four things. All systems share the retriever, the passage count per retrieval, and the generator. The prompt-tuning budget is capped at the same number of development-set trials per method. Every result is reported as a curve of answer F1 against LLM calls and total tokens, not as a single point. Beating the strongest competitor means matching Plan$^\ast$RAG's F1 on MuSiQue-Ans with at least 30% fewer calls. It also means exceeding SPARC-RAG's F1 at equal token cost in our rerun.

Three ablations isolate the key ingredient, which is the choice of where to split. Split-only disables merging, and merge-only starts atomic and only coalesces. The most important ablation is random splitting at a matched split rate. It gives the same number of splits as our policy but places them without the sufficiency signal. If random splitting at matched budget does as well, the sufficiency check contributes nothing.

Why not just…?

Why not just tune one fixed granularity per dataset? This is the most serious threat. The analogous systems result is that a modest, fixed number of chunks per worker captures most of the benefit of fine partitioning. That hints that a well-chosen static setting may be enough. The oracle study settles it directly. The idea survives only if the per-question best grouping beats the best fixed grouping rule by a clear margin, which we set at 5 F1 on MuSiQue-Ans, and if our run-time policy recovers a substantial share of that gap. If the oracle gap is small, we will report that and recommend static tuning.

Why not just let a ReAct-style agent replan when it gets stuck? In-context agents keep the whole trajectory in the prompt. Plan$^\ast$RAG reports that this causes plan fragmentation and context overflow on the same benchmarks, and it outperforms ReAct. Our design keeps the graph outside the prompt and decomposes only the failed node. We include ReAct with retry at matched call budget as an extra baseline, so this is measured rather than assumed.

Why not just use SPARC-RAG's trained stop/continue evaluator? Its evaluator decides whether to keep going for the whole question. It does not decide which piece of the question to break apart or merge. It also needs preference fine-tuning, while our check is training-free. If our rerun of SPARC-RAG dominates our curve, the per-node control is not paying for itself. A natural follow-up would then be to use SPARC-RAG's evaluator as our sufficiency score.

Why not just use DRAGIN's internal uncertainty signal? It works, but only with access to model internals. The LLaMA2-13B comparison tells us how much accuracy the black-box signal gives up. A small loss makes the black-box design strictly more deployable.

Proposed Experiments and Decisive Checks

We evaluate on MuSiQue-Ans, where gold decompositions and six reasoning-graph shapes allow per-hop analysis, and supporting-fact F1 measures whether the evidence chain is correct. We also evaluate on the HotpotQA fullwiki setting and on 2WikiMultiHopQA. Metrics are answer EM/F1, supporting-fact F1 where available, LLM calls, total tokens, and critical-path latency (the longest chain of dependent calls). We break results down by hop count and graph shape.

The checks, in order of how much they could kill the idea, are as follows. The first is the oracle gap between per-question and fixed granularity. The second is that our policy beats random splitting at matched split rate. The third is that it lies on or above the Plan$^\ast$RAG and SPARC-RAG cost–accuracy curves. The fourth is a cascading-error analysis: among questions where atomic decomposition commits a wrong intermediate answer, how often does starting coarse avoid the error entirely? That fourth measurement tests the mechanism we believe explains why coarser is sometimes more accurate, not just cheaper.