When a question asked in Bengali or Arabic needs two or three facts chained together, today's retrieval-augmented systems have to do two hard things at once. Retrieval-augmented generation (RAG) means fetching passages from a document collection and having a language model answer from them. Here the system must find each linking fact, possibly in English documents, and it must reason across those facts while still answering in the user's language. Prior work has largely treated these as one problem and attacked it either by translating everything into English or by building better multi-hop machinery that works only in English. We propose to separate them. The step of deciding which relation to follow next ("this kind of question usually goes from person to birthplace to country") is mostly independent of language. It can be learned from the large supply of English multi-hop reasoning paths and then reused for any language. Language then matters only at the two ends of the chain: linking the native question to entities, and writing out the final answer.
The mechanism comes from an older idea in interactive data systems, trace-based navigation. Systems like sMash recorded the paths that many users took through a network of services and recommended the links that past users had followed successfully. We do the same with machine reasoning traces. We run an English evidence-chain builder over English multi-hop training questions, keep only the chains that reached correct answers, and abstract each one into a language-neutral sequence of relation types. At test time, a non-English question is answered by walking a multilingual evidence graph, with each hop ranked by how often that relation step succeeded in the English trace memory. Only the short facts along the chosen path are ever translated. The English-only nature of reasoning resources, usually treated as the obstacle, becomes the source of navigation knowledge.
Core Claim
The claim is that a memory of successful English reasoning paths, stored as relation-type sequences drawn from a fixed relation inventory, improves multi-hop evidence selection for non-English questions by at least as much as it improves it for English questions. It should do so at a small fraction of the translation cost of full-document translation pipelines. If the gain shrinks sharply outside English, then path structure is not language-neutral in the way we assume, and the idea fails. That is a clean, falsifiable prediction.
Relation to Prior Work
The method builds directly on TRACE the Evidence. TRACE turns retrieved passages into knowledge triples (head entity, relation, tail entity) and grows an evidence chain one triple at a time. A dense ranker proposes candidates, and a language model picks the next step and decides when to stop. TRACE-Triple reaches 33.43% exact match on MuSiQue using about 169 tokens of context, against 16.14% for vanilla RAG using about 2,551 tokens. Each TRACE chain is built from scratch, nothing learned from one question's successful path is reused for the next, and everything is English. We keep TRACE's chain-building loop. We add a cross-query path memory, and we move the loop onto a multilingual graph.
KG²RAG and GRAG supply the case that graph structure beats flat passages on multi-hop questions. KG²RAG expands from seed chunks over a triple graph; GRAG retrieves and prunes small neighborhoods and feeds them to the model as text and as learned embeddings. Both are monolingual. GRAG also needs access to model internals, so we do not reuse its embedding interface. MoPo shows that intermediate hops drift away from the original question and stabilizes training with query-focused summaries. That drift result motivates our use of a fixed relation inventory, which anchors each hop to a discrete, checkable choice rather than free-form reformulation.
On the multilingual side, three papers motivate the problem and one supplies our strongest competitor. XOR QA showed that native-language Wikipedias often lack the answer and that pivoting to English raises answer coverage by an average of 22%. XRAG showed that GPT-4o reaches only 62% on its English multi-document setting against 85% for humans, with relative drops exceeding 50% for some models in Arabic. It also located the bottleneck in reasoning across languages rather than in generating non-English text. Retrieval-augmented generation in multilingual settings documented that models drift into English when given English context, and that exact match breaks on transliteration differences. It proposed character 3-gram recall, which we adopt. CrossRAG is the competitor. It retrieves from a multilingual pool, translates every retrieved non-English document into English, reasons in English, and answers in the user's language, improving on mixed-language retrieval by +3.5% for GPT-4o in aggregate. CrossRAG translates whole documents and reasons over flat passages. We translate only path facts and reason over a chain.
The navigation idea is taken from Mashup by Surfing a Web of Data APIs, which mines collective traversal traces to recommend frequently and successfully used links. From that work we also inherit its known weakness, cold start on regions with no traces. Two further ideas come from Guided Interaction. One is enumeration: the system lists the valid moves instead of asking for free-form input, which here means extracting triples against a closed relation list. The other is non-prescriptive suggestion, which we use as a soft prior rather than a hard rule.
Research Program
The first component is trace mining. We run an open-weight TRACE-style chain builder on the English training splits of HotpotQA, 2WikiMultiHopQA and MuSiQue, and keep only chains whose final answer is correct. Each relation in a chain is mapped to a Wikidata property ID. 2WikiMultiHopQA is already built from Wikidata properties, and for the other datasets free-text relations are mapped by nearest-neighbor matching in a multilingual embedding space, with low-confidence mappings discarded. A chain thus becomes a sequence such as "director, then place of birth, then country." We store it with coarse question features: the answer type and the type of the question's seed entity.
The second component is cross-lingual graph construction. Retrieval runs over a pooled English and native-language Wikipedia index with BGE-m3, following the all-languages datastore that worked best in the multilingual RAG study. Triples are extracted from retrieved passages in their original language. The extractor must choose relations from the same property list, which makes English and non-English triples comparable without translation. Entities are linked to Wikidata IDs where possible.
The third component is guided traversal. At hop $k$, a candidate triple with relation $r$ is scored by combining the ranker score with the trace prior:
$$s(t) = \text{rank}(t \mid q, \text{chain}_{<k}) + \lambda \log \hat{P}(r \mid r_1,\dots,r_{k-1}, c),$$
where $t$ is the candidate triple and $q$ the native-language question. $r_1,\dots,r_{k-1}$ are the relations already chosen, $c$ are the question features, $\hat{P}$ is a smoothed frequency estimate from successful English traces, and $\lambda$ is tuned on a development set. When the prefix has too few supporting traces, $\hat{P}$ backs off to shorter prefixes and finally to uniform, which recovers plain TRACE. The language-model selector then picks among the top-scored candidates and decides when to stop, as in TRACE. We use greedy selection so that closed models remain usable.
The fourth component is answering. Only the triples on the final chain, typically a few dozen tokens, are translated into the question's language, or into English for the English-reasoning variant. When the answer entity has a Wikidata ID, its surface form is taken from the target-language label. This targets the transliteration and English-drift failures directly.
A side product is that every hop carries a stated reason ("questions of this type usually continue via place of birth"). We report how often these reasons match the chain actually used, but the evaluation is automatic and does not depend on users.
Baselines
The naive reference point is mixed-language RAG with no structure: BGE-m3 retrieval of the top passages from the pooled index, fed directly to the reader with a target-language system prompt. This is the MultiRAG setting in CrossRAG and the all-languages setting in the multilingual RAG study. It shows how much any structure buys.
The strongest existing method for the language side is CrossRAG, which translates all retrieved non-English documents into English before generation. It is the method that most directly attacks the cross-lingual reasoning gap XRAG identified, and it has a reported margin over mixed-language RAG of +3.5% for GPT-4o and +5.0% for Command-R on low-resource languages, aggregated over MKQA, MLQA and XOR-TyDi QA (CrossRAG). No reported result was found on Lacuna for CrossRAG on XRAG or on any multi-hop benchmark, so we run it ourselves.
The strongest existing method for the multi-hop side is TRACE run on our multilingual graph without the trace prior ($\lambda = 0$). This is the ablation that isolates the key ingredient. Its English reference is the reported 33.43% exact match on MuSiQue. We also run the composition a reviewer will ask for: translate the question to English, run TRACE over English Wikipedia, and translate the answer back.
All systems share the same reader models (Llama-3-8b and GPT-4o, both used in CrossRAG), the same retriever, the same index, the same number of retrieved passages, and the same development-set tuning budget. Our only extra hyperparameter is $\lambda$, so each baseline gets an equal number of tuning runs on its own settings. We count beating CrossRAG as matching or exceeding its accuracy on the cross-lingual multi-hop sets while translating at least an order of magnitude fewer tokens. We count beating trace-free TRACE as a significant accuracy gain, by paired bootstrap, on non-English questions.
Why not just…?
Why not just translate the question to English and run TRACE? This is the most serious threat. It inherits TRACE's English-only strengths and needs no new machinery. Its weaknesses are documented: the round-trip translation pipeline in XOR QA reached only 18.7 average F1 on the full native-language task, with the authors attributing losses to question and answer translation errors. It also cannot use evidence that exists only in native-language Wikipedia, which matters because coverage is asymmetric in both directions. The trace prior is orthogonal to this choice, so we cross the two factors: native-entry versus translate-entry, each with the prior on and off. If translate-entry TRACE plus the prior matches our native-entry system, we will report that the contribution is the trace memory alone and recommend the simpler entry point.
Why not just use CrossRAG? CrossRAG fixes the mixed-language reasoning problem by brute force but still hands the reader a pile of flat passages. MultiHop-RAG shows this is where multi-hop systems fail: GPT-4 reaches 0.56 accuracy with retrieved chunks against 0.89 with gold evidence (MultiHop-RAG). Its translation cost also grows with every retrieved document. Our cost comparison and multi-hop accuracy comparison settle whether chain-level translation keeps CrossRAG's benefit at lower cost. If CrossRAG wins on accuracy, a CrossRAG-plus-trace-prior variant tells us whether the prior still adds value on translated text.
Why not just fine-tune a multilingual multi-hop retriever on translated English data? MoPo-style training reaches 64.3 F1 on HotpotQA in English, so learned retrieval is clearly strong. However, it requires translating training data, which reintroduces the translation-error problem the monolingual-constraint literature warns about. It must also be retrained per corpus, while a trace memory is a lookup table. We do not claim to beat such a retriever outright. We test whether the trace prior adds to a stronger retriever by swapping it in, budget permitting, as the ranker term in the scoring equation.
Proposed Experiments and Decisive Checks
The primary multi-hop test set is new and small but clean. We take 500 held-out 2WikiMultiHopQA and MuSiQue development questions per language, with no overlap with the trace-mining split. Native speakers translate the questions into Arabic, Bengali, Japanese, Russian and Telugu (from XOR-TyDi QA's language set) plus German and Chinese. Only questions are translated; the evidence pool is untouched. Because 2WikiMultiHopQA answers are Wikidata entities, scoring can use language-independent IDs, as MKQA does, alongside character 3-gram recall.
The second test is XRAG as released, in Arabic, Chinese, German and Spanish. Its news events postdate Wikidata coverage, so the prior operates only on relation types. That makes it the hard case for the language-neutrality claim. The reported anchors are GPT-4o at 62% in English and humans at 85%.
The third test uses MKQA and XOR-TyDi QA as single-hop controls. There the prior should neither help nor hurt much, and a drop would signal that it pushes the system into needless extra hops.
We measure answer accuracy, character 3-gram recall, response-language correctness as defined in XRAG, gold-evidence recall along the chain, and tokens translated per question.
Three checks decide the proposal. First, the trace prior's gain on non-English questions should be at least as large as its gain on the same questions in English. A materially smaller gain falsifies the claim that path structure transfers across languages. Second, accuracy should rise with trace coverage of a question's relation prefix and fall back to plain-TRACE accuracy at zero coverage. Questions are binned by number of supporting traces, and the cold-start behavior inherited from sMash is measured directly rather than assumed away. Third, the system should match or beat CrossRAG on the multi-hop sets while translating at least ten times fewer tokens. If it loses on accuracy, the result is a measured cost-accuracy trade-off rather than a claimed win. The 2-by-2 factor crossing of native versus translated entry and prior on versus off is reported in full, whichever way it comes out.
References
- TRACE the Evidence: Constructing Knowledge-Grounded Reasoning Chains for Retrieval-Augmented Generation
- Knowledge Graph-Guided Retrieval Augmented Generation
- GRAG: Graph Retrieval-Augmented Generation
- Momentum Posterior Regularization for Multi-hop Dense Retrieval
- XOR QA: Cross-lingual Open-Retrieval Question Answering
- XRAG: Cross-lingual Retrieval-Augmented Generation
- Retrieval-augmented generation in multilingual settings
- Multilingual Retrieval-Augmented Generation for Knowledge-Intensive Task
- Mashup by Surfing a Web of Data APIs
- Guided Interaction: Rethinking the Query-Result Paradigm
- MultiHop-RAG: Benchmarking Retrieval-Augmented Generation for Multi-Hop Queries