Learning Retrieval Hops Without Questions

Answering a question like "Where was the director of Film X born?" requires two lookups: one to find the director, and a second, written from what the first returned, to find the birthplace. Systems that do this well today either prompt a large language model to plan each lookup, which is slow and costly, or train on labeled question–answer data, which most specialized document collections do not have. This note proposes a third route. A small query-writing model teaches itself the kinds of hops a corpus supports, such as "person → birthplace" or "film → director", by practicing on the raw documents alone, with no questions and no answers. The training signal comes from unsupervised skill discovery in reinforcement learning: the agent conditions on a latent "skill" code and is rewarded when that code can be recovered from what it did.

The core move is to change what the skill code must explain. In robotics, a skill is discriminated from the states it visits. Here it is discriminated from the change in evidence produced by one retrieval step, conditioned on the passage the step started from. Under that objective, a skill cannot win by being "the sports topic" or "the medicine topic"; it has to be a reusable operation that works from many starting passages. That is roughly what a relation is. If this works, a corpus-specific library of hop operators can be pretrained without labels and composed into multi-hop retrieval with a handful of labeled questions, or with none.

Core Claim

Skills discovered by maximizing conditional mutual information between a latent code and the evidence transition it causes will line up with corpus relations. A cheap selector over these skills will then match prompted multi-agent retrieval on supporting-passage recall, at a fraction of the model calls, and beat outcome-reward reinforcement learning when labeled questions are scarce. "Mutual information" here means how much knowing the skill code reduces uncertainty about the evidence change.

Let $e$ be the embedding of the current evidence passage and $z$ a skill code drawn from a uniform prior $p(z)$. The policy writes a query, a frozen retriever returns a new passage, and $e'$ is the embedding of that new passage. We maximize $I(E'; Z \mid E)$, the information the skill carries about where a hop lands given where it started. Following the variational treatment of Variational Intrinsic Control and Diversity is All You Need, with a learned discriminator $q_\phi(z \mid e, e')$ standing in for the intractable true posterior over skills, the per-hop reward is

$$ r(e, e', z) = \log q_\phi(z \mid e, e') - \log p(z) + \lambda \, \log \big\| (e, e') - \mathrm{kNN}_k(e, e') \big\|, $$

where the last term is the particle-based entropy bonus of CIC. It rewards transitions far from their $k$-th nearest neighbor in a batch, which pushes the skill set as a whole to cover the corpus. $\lambda$ trades coverage against within-skill consistency.

Why this formulation, and what prior work it builds on

Three pieces of prior work supply the method. DIAYN rewards a policy for visiting states from which a discriminator can recover the skill, but it produces skills that partition state space; in text, that means skills that partition topics. DADS conditions on the current state and learns a skill-conditioned dynamics model usable for zero-shot planning, and we reuse that conditioning and that planner. CIC defines skills over transitions and decouples coverage from predictability. It shows that state-based discriminators converge to easily distinguished "static poses." We expect a textual analogue of that failure: a skill that re-retrieves near-duplicates of the start passage, which is trivially predictable and useless. CIC's transition entropy term is our guard against it.

Two lines of work motivate the problem. Multi-hop retrieval systems such as PRISM, which runs analyzer, selector and adder agents for three iterations to recover missing "bridge" passages, and Think Straight, Stop Smart, which uses fixed reasoning templates and stops when consecutive sub-queries exceed cosine 0.85, get their hop behavior entirely from prompting. Chain-of-Skills instead hand-specifies five retrieval skills, gives each its own attention heads, and pretrains on Wikipedia hyperlinks. None of these discovers which hops a corpus supports.

Two other lines constrain the design. Language Guided Skill Discovery shows that information-theoretic diversity in raw coordinates yields meaningless twitching, and that measuring distance in sentence-embedding space makes skills semantic. This supports operating directly on passage embeddings, where text is already the state and no hand-written state-to-text translator is needed. LiFT and Agentic Skill Discovery show that letting foundation models propose skills works but invites reward hacking, which demanded smoothing in one case and a GPT-4V referee in the other. Our reward is computed by a small discriminator rather than an LLM judge, so it is cheaper, though it is still exploitable, and we test for that.

The paper closest in name, Cooperative RAG with Mutual Information Exchange, reranks by contrasting a retriever's early and late layers and masks uncertain entities during question unrolling. It does not optimize any mutual information bound and learns no skills. Pointwise Mutual Information as a Performance Gauge uses PMI between question and context to reorder an already-retrieved set. It cannot issue a new query, so it cannot recover a bridge passage the first retrieval missed.

Research Program

The system has four learned parts around a frozen retriever. A frozen BM25 index and a frozen dense bi-encoder are both reported. The first part is a query policy: a small instruction-tuned language model that reads the current passage and a skill token and writes one query. The second is the discriminator $q_\phi(z \mid e, e')$, a small network over frozen passage embeddings. The third is a skill-conditioned dynamics model $\hat{q}(e' \mid e, z)$ in the style of DADS, which predicts where a skill will land. The fourth is a skill selector used at question time.

Pretraining samples start passages uniformly from the corpus and rolls out single hops, or short chains with a fresh skill per hop. The policy is updated by group-relative policy gradient on the reward above, the same optimizer family used in Binary RAR. No questions are seen. We use 64 discrete skills as the default and sweep 16 to 256.

At question time there are two modes. In the few-shot mode, a selector maps (question, current passage) to a skill. It is trained by behavior cloning on gold supporting-passage chains from $n \in \{0, 50, 500, 5000\}$ labeled questions; at each hop it picks the skill whose rollout most likely reaches the next gold passage. In the zero-shot mode, the dynamics model plans by scoring each skill's predicted landing point against the question embedding and expanding the best two. Retrieval stops when no skill's predicted landing point gains question similarity, which replaces the fixed threshold used by TSSS. The retrieved chain is passed to the same frozen reader model used by every baseline.

The analysis we care most about is whether skills are relations. 2WikiMultiHopQA comes with explicit evidence paths built from typed relations, so we can measure the mutual information between discovered skill and annotated relation type on held-out hops.

Baselines

The naive reference is single-shot dense retrieval of the top-$k$ passages for the full question, fed to the same reader. It shows how much any hopping buys.

The strongest existing method is PRISM's prompted three-agent loop. It reports supporting-passage recall of 90.9% on HotpotQA against 72.8% for IRCoT, and 83.2% against 57.1% on MuSiQue, plus 54.20 exact match on HotpotQA (PRISM). It is the strongest competitor because it targets exactly the bridge-passage recall our skills are meant to improve, and it needs no training. We rerun it with our retriever, our corpus snapshot and our reader. We report recall both at matched total model calls and with PRISM unconstrained, so the comparison covers the cost frontier and not just one point. Beating it means matching its recall within two points at no more than a quarter of its model calls, or exceeding it at equal calls. We do not expect to beat it outright with a small policy, and say so in advance.

IRCoT and TSSS serve as cheaper iterative references. TSSS reports 34.1 exact match on HotpotQA against IRCoT's 28.0, and a MuSiQue latency of 9.5 seconds per sample against 27.2 for Iter-RetGen (Think Straight, Stop Smart). On 2WikiMultiHopQA, RaDIO with a sentence-embedding retriever reports 0.254 exact match (RaDIO). We rerun all three rather than copying numbers, because readers and retrievers differ across papers.

Chain-of-Skills is the hand-specified-skills competitor; it reports 88.89 passage exact match on HotpotQA (Chain-of-Skills). We run it twice, with and without its hyperlink pretraining, to separate the value of hand-designed skills from the value of link supervision.

An outcome-reward baseline trains the same query policy, with the same optimizer and the same total update steps, on the reward "did the chain contain the gold supporting passages," using the same $n$ labeled questions. It isolates whether reward-free pretraining helps over spending the compute on labeled reward directly.

Three ablations isolate the key ingredient: an unconditional discriminator $q(z \mid e')$, which should rediscover topics; a run with no entropy bonus ($\lambda = 0$), which should produce near-duplicate "static" hops; and a random-skill policy in which skill tokens are present but the reward is replaced by sampling temperature. All runs share the same tuning budget of twenty configurations per method, selected on a held-out development split.

Why not just…?

Why not just prompt an LLM to write several diverse queries per hop? This is the most serious threat. Large models already know common relations like "director of," so on Wikipedia a prompted decomposer may match learned skills. Our bet is that it is weaker on corpora whose relations are idiosyncratic, and more expensive per hop. The random-skill and PRISM baselines at matched calls test the first point on Wikipedia. A held-out-corpus test with hyperlinks stripped, in which pretraining on MuSiQue paragraphs is evaluated against a prompted decomposer on MuSiQue, tests where learned hops should matter most. If the prompted decomposer matches us at equal cost on both, the proposal reduces to "a cheaper distilled prompter," and we will report it that way.

Why not just train the query writer with reinforcement learning on answer correctness? With thousands of labeled questions it may simply win. The claim is limited to the low-label regime, and the $n$-sweep from 0 to 5000 directly measures where the two curves cross. Binary RAR's evidence that a single strict target narrows behavior to one mode (Binary RAR) is suggestive but comes from a different task, so the sweep, not that paper, settles it.

Why not just use hyperlinks or entity links as hop supervision? On Wikipedia this is free and strong, which is why Chain-of-Skills is run both with and without link pretraining. Many document collections, such as clinical guidelines or internal manuals, lack dense links. The link-stripped condition is the regime we target. If skills only help when links are absent, that is still the intended contribution.

Why not just rerank a larger first-round retrieval by pointwise mutual information? Reranking can only reorder what was retrieved. PMI reordering lifted Mistral-7B on NQ-Open from 62.89% to 65.72% (PMI Gauge), but that is single-hop. The naive top-$k$ baseline with PMI reordering added shows how much of the bridge-passage gap it closes on MuSiQue.

Proposed Experiments

Pretraining corpora are the HotpotQA Wikipedia abstracts, the 2WikiMultiHopQA documents and the MuSiQue paragraph pool, with questions withheld. Evaluation uses the standard development splits of HotpotQA, 2WikiMultiHopQA and MuSiQue. We report supporting-passage recall at fixed retrieval budgets, reader exact match and F1, model calls and wall-clock latency per question.

The first decisive check is relational alignment: on 2WikiMultiHopQA, the mutual information between skill and annotated relation type should be well above that of the unconditional-discriminator ablation. The topic-discriminating ablation should score high on topic and low on relation. If our skills do not beat it on relation alignment, the central mechanism has failed regardless of downstream accuracy.

The second check is the label-efficiency curve against outcome-reward training and Chain-of-Skills without hyperlinks. Pretrained skills should lead at $n \le 500$.

The third is the cost frontier against PRISM and IRCoT on MuSiQue, where bridge passages matter most.

The fourth is cross-corpus transfer: pretrain on one corpus, apply the few-shot selector on another. This shows whether skills are corpus-specific, which would argue for per-domain pretraining, or general.

We also monitor discriminator exploitation, meaning skills that become distinguishable through query surface artifacts rather than retrieved content. We check this by re-scoring skills with a discriminator trained on paraphrased queries.