Discourse Stacks for Conversational Multi-Hop Retrieval

When a person works through a multi-step question in conversation with an assistant, they rarely ask it cleanly. They ask the first step, wander into a clarification or a side question about some other entity, come back, and say "so where was he born?" A retrieval system must then turn that last utterance into a search query. Two things go wrong. The word "he" shares no vocabulary with the document that answers it, which is the lexical gap. Worse, the most recent entity in the conversation usually belongs to the side exchange, not to the reasoning chain the user just returned to. Flat rewriting, which reads the whole history as one sequence, tends to grab that recent entity. We propose to give the system an explicit discourse stack: a record that opens a new level when the conversation descends into a sub-exchange and closes it when the conversation returns. Each open level is tied to one reasoning step, called a hop, and stores the entity that step resolved. The query rewriter reads this stack instead of the raw transcript.

The claim is narrow and testable. Most cross-turn retrieval failures in conversational multi-hop question answering come from picking the wrong referent after a nested exchange closes, not from missing knowledge. A small rewriter that conditions on a stack of hop-level entity bindings should fix these failures more cheaply and more reliably than a large model rewriting from flat history. It should give no gain when the dialogue has no nesting. That last prediction is what separates a structural effect from a capacity effect.

What exists and what is missing

The closest work is ChainRAG. It identifies the "lost-in-retrieval" failure: when a multi-hop question is decomposed, later sub-questions contain vague references like "this author," and recall drops by up to 18% at Recall@2. ChainRAG fixes this by substituting the entity resolved at the previous hop. That paper supplies our core motivation and our per-hop metric. But its chain is strictly sequential, inside a single question. "Previous hop" is always well defined there, which is exactly what stops being true in dialogue.

RaFe trains small query rewriters using a cross-encoder reranker as the reward signal and treats each query in isolation. It supplies our training method, not our conditioning signal.

AriadneMem handles multi-hop evidence spread across long conversational histories using graph bridge discovery. It does this by flattening dialogue into fact triples, with no discourse structure. It also selects its starting nodes by embedding similarity, so a colloquial query with a vocabulary gap fails at the first step. KMRKSM reasons over knowledge-graph paths guided by a flat encoding of dialogue history and never touches free-text retrieval. HierTOD does use hierarchical goals and a hierarchical state machine. Its hierarchy, however, is a hand-written YAML workflow, not an inferred structure over an open corpus, and its authors report that coherence degrades as dialogues get longer.

The dialogue side supplies the representation. Rotaru and Litman reduced Grosz–Sidner focus stacks to four per-turn operations:

  • Push enters a sub-dialogue.
  • PopUp returns to a higher level.
  • Advance moves to the next exchange at the same level.
  • NewTopLevel starts a new main task.

They showed that conditioning on these transitions raised the variance their model explained in tutoring outcomes (R²) from 0.39 to 0.75. That is evidence that the operations carry real signal and that they can be annotated. Benotti and Blackburn show that clarification sub-dialogues are common and can be annotated reliably, with a kappa of 0.84 on SCARE. Together these suggest nesting is a realistic condition, not something we invented.

Core mechanism

We map the multi-hop chain onto the discourse hierarchy. The top-level transaction is the user's overall question. Each hop is one exchange at the level below it. Clarifications, corrections, and digressions are pushed beneath the hop they interrupt.

Each stack frame holds two things: the hop's information need, and a binding slot for the entity once that hop is resolved. On a PopUp, the frame being closed hands any binding it resolved to its parent. All other entities from that frame are marked inactive.

When a new retrieval is needed, the rewriter receives the user's utterance plus a short serialization of the open frames, listing their bindings and the inactive entities. Its job is to produce a keyword-dense query for the corpus.

There are two components to build:

  • A stack-operation tagger. It predicts one of the four operations per turn. We will implement it both as a fine-tuned classifier and as a prompted LLM.
  • A stack-conditioned rewriter. This is a small sequence-to-sequence model. It is first fine-tuned on LLM rewrites, then optimized with reranker preference feedback exactly as in RaFe.

Retrieval itself uses a plain dense or BM25 index. This keeps the contribution isolated in the query and away from graph indexing of the kind used by HLG.

Research Program

Benchmark construction. No benchmark in the file tests nested conversational multi-hop retrieval, so we build one from MuSiQue. MuSiQue's 2–4 hop questions come with single-hop decompositions and hard distractor paragraphs. Each question is rendered as a dialogue: the user asks one hop per turn using anaphora instead of the bridge entity.

Into these dialogues we insert sub-dialogues at controlled depth (0, 1, 2) and controlled distance from the hop they interrupt. There are three types:

  • Clarification. The agent asks and the user answers.
  • Digression. The user asks about an entity taken from a MuSiQue distractor paragraph. This creates a plausible competing referent.
  • Correction. The user revises an earlier binding.

To vary the lexical gap independently, we paraphrase user turns into colloquial wording at controlled levels of content-word overlap with the gold paragraph. Gold stack operations come for free from the construction.

Guarding against template artifacts. Annotators will write roughly 300 dialogues freely from decompositions, with no templates. Results must hold on this subset.

Transfer to real conversation. We use LoCoMo's multi-hop questions as a test on real dialogue. Stacks must be inferred there, and the structure is less clean.

Analysis. We will measure how errors split between wrong referent, right referent but wrong vocabulary, and retrieval miss despite a correct query. We will also measure how gains scale with nesting depth and with the number of competing entities.

Baselines

The naive reference point sends the user's raw utterance to the retriever. This measures the combined lexical and referential gap.

The strongest practical competitor is flat-history rewriting by a large LLM in the GPT-4o class. It is prompted with the full transcript and told to resolve all references and produce a search query. This is what a deployed system would do. It is run with the same retriever, the same index, and a prompt tuned on the same development split we use for our own tuning.

The strongest existing structured method is ChainRAG's retrieve-answer-rewrite loop, adapted to dialogue by substituting the most recently resolved entity. Its paper reports an F1 gain of roughly 60% over naive RAG on its benchmarks. On MuSiQue the best absolute figures in the file are F1 47.0 for Stop-RAG and 48.5 for SG-FSM with Qwen. These are single-question numbers. No reported result was found on Lacuna for any conversational, nested version of MuSiQue, and the file gives only relative gains for AriadneMem on LoCoMo. We will therefore run every baseline ourselves.

A matched-capacity control is a RaFe-trained rewriter of identical size, trained on the same data with the same reranker reward and the same number of preference steps. The only difference is that it sees flat history instead of the stack. This baseline isolates the representation.

Two further ablations isolate the key ingredient:

  • Stack without binding. The stack is kept, but nothing is propagated on PopUp. This tests whether binding inheritance, rather than mere segmentation, does the work.
  • Stack in a large model's prompt. The large LLM receives the stack serialization in its prompt. This separates "structure helps" from "a small trained model helps."

Beating the field means the following. Per-hop Recall@2 and final answer F1 must exceed both the large flat-history rewriter and the matched flat rewriter at depth ≥1, by a margin larger than the variance across seeds. This must hold with predicted, not gold, stack operations, and must show no loss at depth 0.

Why not just…?

Why not just let a strong LLM rewrite from the full flat history? This is the real threat. Large models may track nesting implicitly. ChainRAG found that even strong LLMs produce underspecified sub-questions within a single chain. RaFe reports that unconstrained LLM rewrites drift and pad queries. Neither paper tests nested dialogue, so this remains open. The depth-stratified comparison settles it. If the large flat rewriter matches the stack at depth 2 with digressions present, the structural claim fails. The contribution would then shrink to a cheap substitute for a large model, and we would report it that way. The stack-in-prompt ablation also tells us whether large models benefit from being handed the structure.

Why not just apply ChainRAG's substitute-the-last-resolved-entity rule across turns? In a single chain the last resolved entity is the right one. After a digression, it is by construction the wrong one. Our digression condition is designed to measure exactly this failure. If ChainRAG-adapted does not degrade relative to depth 0 there, our premise is wrong.

Why not just put the whole conversation and all retrieved passages into a long-context model? AriadneMem reports large multi-hop F1 gains over this kind of setup on LoCoMo, at a fraction of the token cost. PRISM shows that distractor-heavy context hurts answers. We include this condition, and we measure its cost alongside its accuracy, rather than assuming it loses.

Decisive checks

The first check is the depth curve. The stack's advantage over the matched flat rewriter should be near zero at depth 0 and grow with depth and with the number of competing entities. A flat curve would mean any gain comes from something other than structure.

The second check is the error decomposition. Gains should come mainly from fewer wrong-referent queries. The lexical-gap residual should be closed by the RaFe-style training in both arms equally.

The third check is robustness. Results must survive predicted stack operations, the human-written subset, and LoCoMo transfer. If gold stacks help but predicted ones do not, the bottleneck is the tagger. In that case the next study is how to detect stack operations, not how to rewrite queries.