betaFeedback

WorksComputer Science

StitchRAG: Constructing Compact and Evidence-Preserving Contexts for RAG with Diffusion-Based Stitching

Abstract

Retrieval-augmented generation (RAG) improves factuality by grounding large language models (LLMs) in external evidence. However, long retrieved contexts incur computational overhead and can even hurt performance due to noisy or irrelevant content. We propose StitchRAG, a framework for constructing compact context in RAG. StitchRAG builds a faithful, information-dense context while dynamically compressing the retrieved passages. We adapt the size reduction ratio to each passage by formulating a utility maximization trading-off the retained information and computation costs. We then extract answer candidates and query-related keywords from passages as anchors and collect passage sentences containing anchors under the derived size constraint. Finally, we connect or stitch the collected sentences together using text diffusion to form a coherent and natural context. Experiments on five open-domain QA benchmarks show that StitchRAG consistently outperforms diverse multi-step and compression baselines. Extensive ablations show the effectiveness of dynamic size allocation, anchor preservation, and diffusion-based stitching.

Introduction

Large language models (LLMs) (Achiam et al., [1]; Huang et al. [15]) have rapidly advanced and enabled a wide range of real-world applications. However, they face fundamental limitations: updating their knowledge is costly, and LLMs often hallucinate responses that are plausible but incorrect (Welleck et al., [37]; Kalai et al. [20]). Retrieval-augmented generation (RAG) addresses these issues by grounding generation on external evidence retrieved at inference time (Chen et al., [5]; Lewis et al. [25]). By conditioning on retrieved passages, RAG improves factuality and enables easy updates with up-to-date information.

Constructing Compact Context

Figure 1. Constructing Compact Context. From retrieved passages, StitchRAG extracts and preserves sentences containing key terms. Then it connects them via diffusion-based stitching to construct a compact context.

A growing body of work improves RAG via advanced retrieval and generation loops, including multi-step reasoning (Trivedi et al., [35]; Kim et al. [23]), self-reflection (Jiang et al., [17]; Asai et al. [2]), and multi-agent debate or verification (Du et al., [6]; Hu et al. [13]), in order to reduce hallucinations and strengthen reasoning. However, these methods primarily focus on iterative retrieval or post hoc verification, while largely leaving the context constructed from retrieved passages unconstrained. As a result, the context often accumulates redundant or conflicting evidence. Such longer or repeatedly processed contexts also increase inference latency and computational cost. More importantly, even with strong retrievers, simply providing more evidence does not reliably improve answers: LLMs can be confused by noisy passages and long inputs (Liu et al., [28]; Hong et al. [12]; Du et al. [7]).

This has motivated substantial interest in context engineering (Mei et al., [31]; Hua et al. [14]) for RAG, which helps models better interpret the retrieved contexts. Context compression methods, such as selection (Li et al., [27]) and compression prior to generation (Pan et al., [33]; Xu et al. [39]), reduce the inference cost and latency by shortening the input length. However, most existing approaches rely on fixed or heuristic compression ratios, largely independent of the query, passage quality, or reasoning complexity. In practice, a good compression should be context-dependent: some questions require preserving long, cross-passage evidence chains, whereas others benefit from aggressively filtering irrelevant content. Consequently, applying a single global compression ratio to all passages can create a mismatch between the context reduction and the information needs of each problem. Moreover, because prior compression methods typically operate at the token level rather than preserving original sentences, they often degrade the readability of contexts and thus the overall performance of RAG.

Contribution. We propose STITCHRAG, a framework for constructing compact contexts for RAG. STITCHRAG dynamically retains evidence in retrieved passages for size reduction and reconstructs a coherent context from preserved evidence. We formulate evidence retention as a constrained optimization problem: we maximize relevance utility combined with a computation-aware penalty to derive a closed-form retention ratio for each retrieved passage. This enables a dynamic adjustment of the retention ratio to each passage, improving the efficiency and relevance of the constructed context. To build a compact yet readable context, we introduce hybrid anchor selection and diffusion-based stitching. Anchors are defined as key terms for the query, and sentences containing anchors are preserved in the context as fixed evidence. Next, we perform context stitching, which connects fragmented sentences using text diffusion in order to restore coherence of the generated context. The proposed refinement enables faithful context reconstruction while reducing factual drift and hallucination. In our experiments, STITCHRAG consistently improves the RAG performance over baseline methods. Extensive ablations confirm the importance of dynamic context retention, anchor preservation, and diffusion-based stitching.

Related Work

Advanced RAG and Multi-step Retrieval/Generation. Recent work has explored multi-step and adaptive strategies that couple retrieval with intermediate reasoning steps. IRCoT (Trivedi et al., [35]) interleaves reasoning traces with retrieval, enabling sequential evidence acquisition for multi-hop questions. FLARE (Jiang et al., [17]) triggers retrieval based on token-level uncertainty during generation, while Self-RAG (Asai et al., [2]) incorporates self-reflection to assess retrieved evidence and adapt the generation accordingly. SuRe (Kim et al., [22]) is a multi-stage framework that generates answer candidates and summarizes retrieved passages conditioned on each candidate, then ranks candidates by verifying the resulting summaries. More recently, DRAG (Hu et al., [13]) introduces a debate-based verification framework to reduce hallucinations and improve answer reliability under retrieval constraints. However, these methods primarily focus on when to retrieve and how to expand or revise evidence through multi-step cycles. In contrast, StitchRAG addresses how to compress retrieved context under a dynamic budget while preserving crucial information and connecting fragmented evidence.

Context Compression. Prior work has studied context compression as a means of reducing input length before generation. Selective Context (Li et al., [27]) prunes tokens using information-theoretic criteria (e.g., self-information), aiming to remove redundant content. LLMLingua and LongLLMLingua (Jiang et al., [16] (2024)) propose coarse-to-fine compression using a small language model to budget and select query-relevant spans. RECOMP (Xu et al., [39]) trains compressive models to distill retrieved documents into compact representations or summaries. Recent work also studies attention-guided pruning for RAG contexts (Fang et al., [8]), which leverages attention signals to identify and remove redundant evidence. Many prior methods frame context compression as a separate pre-processing step, relying on static heuristics or auxiliary models. In contrast, StitchRAG incorporates budget allocation and evidence retention in context construction for RAG.

Diffusion Models for Text Generation. Diffusion models provide a non-autoregressive framework for text generation via iterative refinement. Early works such as Diffusion-LM (Li et al., [26]) and DiffuSeq (Gong et al., [9]) adapted denoising processes to discrete sequence modeling. Recent scalable approaches ([32, 41]) operate on masked generative principles and achieve performance competitive with autoregressive LLMs at scale. Their iterative refinement supports global editing with bidirectional context, which is particularly suitable for controlled text modification. Building on these properties, StitchRAG adopts a retrieve-and-refine paradigm.

Method

StitchRAG is a framework to construct a compact context from retrieved passages for RAG. It first computes how much to reduce each passage in its size and determines its context budget; next, it retains only sentences containing key terms under the budget; finally, it bridges retained sentences via text diffusion. Figure 2 presents an overview.

Overview of StitchRAG

Figure 2. Overview of StitchRAG. Given a query and a set of retrieved passages, StitchRAG 1) computes a per-passage dynamic retention ratio r∗r^*, 2) extracts passage sentences containing key terms, called anchors, and aggregates them under the token budget constrained by r∗r^*, and 3) generates bridging text between the aggregated sentences using a diffusion LLM. Finally, the constructed context is fed into the LLM to generate the answer.

Optimal Context Retention via Utility Maximization

Problem Formulation. We consider a standard RAG setting where a query qq retrieves KK passages P={x1,…,xK}\mathcal{P} = \{x_1, \ldots, x_K\}. Consider compressing passage x∈Px \in\mathcal{P} where the compression rate depends on xx. For passage xx, we define the retention ratio r(x,q)∈[0,1]r(x, q) \in[0, 1] (for simplicity, hereafter we drop the dependence of rr on x,qx, q). The compressed passage has length r⋅∣x∣r \cdot|x| where ∣x∣|x| denotes the length of passage xx in the number of tokens. For example, if r=0.7r = 0.7, the compressed passage has 70% of the original length. Our goal is to find the optimal r∗r^* for given passage xx. We formulate this problem as cost-aware utility maximization. Specifically, we maximize the objective F(r)\mathcal{F}(r) for r∈[0,1]r \in[0, 1]:

F(r)=U(r)−C(r)(1)\mathcal{F}(r) = \mathcal{U}(r) - \mathcal{C}(r) \tag*{(1)}

where U\mathcal{U} denotes the achievable utility and C\mathcal{C} denotes the computation cost.

Relevance utility. The utility is defined to measure how the compressed passage is relevant to query qq.

However, in the first place, the original passage xx should be relevant to qq prior to compression. Suppose we obtain utility u(r)u(r) with retention ratio rr if xx is relevant, and utility 0 if xx is irrelevant. Let random variable Z∈{0,1}Z \in\{0, 1\} indicate relevance (Z=1Z=1 iff xx is relevant). The achievable utility is given by Z⋅u(r)Z \cdot u(r), and U(r)\mathcal{U}(r) is defined as its expectation:

U(r)=E[Z]⋅u(r)=P(Z=1)⋅u(r).(2)\mathcal{U}(r) = \mathbb{E}[Z] \cdot u(r) = P(Z=1) \cdot u(r). \tag*{(2)}

We estimate P(Z=1)P(Z=1) by probing the LLM with a binary prompt that asks whether passage xx is useful to answer qq (see Appendix § 7.§ 3 for the template). We compute the log-probabilities of the LLM of the answers (“Yes” vs. “No”), denoted by LYes\mathcal{L}_{\mathrm{Yes}} and LNo\mathcal{L}_{\mathrm{No}}, and convert them into a relevance score:

P(Z=1)≈R(x,q):=exp⁡(LYes)exp⁡(LYes)+exp⁡(LNo).P(Z=1) \approx R(x, q) := \frac{\exp(\mathcal{L}_{\mathrm{Yes}})}{\exp(\mathcal{L}_{\mathrm{Yes}}) + \exp(\mathcal{L}_{\mathrm{No}})}.

Next, we define u(r)u(r). Since u(r)u(r) is obtained assuming xx is a relevant passage, u(r)u(r) should be increasing in rr; retaining more from xx is more informative to answer qq. However, we assume a diminishing return: new information does not increase proportionately with the context length. Thus, we adopt a logarithmic utility in rr:

u(r)=log⁡(1+r)(3)u(r) = \log(1 + r) \tag*{(3)}

A diminishing return is consistent with Heaps’ law ([10]), which states that the number of distinct words grows sub-linearly in the document length. Thus, redundancy grows faster than novel information as the context gets longer. Later, we give more justification for log-utility u(r)u(r). In summary, U(r)=R(x,q)log⁡(1+r)U(r) = R(x, q) \log(1 + r).

Computation Cost. The latency of self-attention scales quadratically with the sequence length. Thus, the computation cost of retaining r∣x∣r|x| tokens is proportional to (r∣x∣)2(r|x|)^2. In RAG, documents are commonly segmented into passages of fixed word count [21] or fixed token length [3, 42] for indexing. Thus, we treat ∣x∣|x| as a constant and define the cost objective:

C(r)=βr2,(4)C(r) = \beta r^2, \tag*{(4)}

where the hyperparameter β>0\beta> 0 controls the latency penalty and absorbs the constant factor ∣x∣2|x|^2.

Deriving the optimal r∗r^*. We maximize expected utility minus cost:

max⁡r∈[0,1]F(r)=R(x,q)⋅log⁡(1+r)−βr2.(5)\max_{r \in[0,1]} \mathcal{F}(r) = R(x, q) \cdot\log(1 + r) - \beta r^2. \tag*{(5)}

F(r)\mathcal{F}(r) is a strictly concave function in rr, and (5) admits a unique solution [4] as follows:

r∗=min⁡{12(1+2R(x,q)β−1),1}.(6)r^* = \min\left\{ \frac{1}{2} \left( \sqrt{1 + \frac{2R(x, q)}{\beta}} - 1 \right), 1 \right\}. \tag*{(6)}

We set hyperparameter β=0.25\beta= 0.25. In this setting, one can show that r∗=1r^* = 1 if and only if R(x,q)=1R(x, q) = 1, which is a reasonable choice. In (6), r∗r^* increases with relevance confidence RR, i.e., highly relevant passages should retain more context.

Hybrid Anchor Extraction

For passage xx, our token budget is set to r∗∣x∣r^*|x|. We select and retain important sentences from xx under this budget. Retaining sentences, instead of individual tokens, helps to maintain the coherence of context after compression. To that end, we select sentences which contain important spans, called anchors. We first select the anchors by a hybrid strategy: a semantic-lexical selection that combines reasoning-centric generation with query-centric lexical matching.

Reasoning-centric anchors (AR-based). We generate multiple answer candidates using the LLM conditioned on (q,x)(q, x). The answer spans form the anchor set, AARA^{\mathrm{AR}}, to capture implicit semantic dependencies beyond simple keyword matching.

Query-centric anchors (TF-IDF-based). In parallel, we extract the query-centric anchor set denoted by ATFIDFA^{\mathrm{TFIDF}} using a TF-IDF score to ensure the coverage of rare entities and lexical cues. The final anchor set is the union of the anchor sets:

A=AAR∪ATFIDF.(7)A = A^{\mathrm{AR}} \cup A^{\mathrm{TFIDF}}. \tag*{(7)}

Fact-First Sentence Selection

Given the token budget Tbudget=r∗⋅∣x∣T_{\mathrm{budget}} = r^* \cdot|x|, we select sentences from xx that contain anchors. We initially mark all the sentences in xx as “unselected”.

  1. Anchor protection. We identify sentences that contain anchors in AA and mark them as “selected”. Let SAS_A denote this set of sentences, which forms the factual backbone of the compressed context.

  1. Budget-aware selection. If the total number of tokens in SAS_A is less than TbudgetT_{\mathrm{budget}}, we select some non-anchor sentences using a lightweight priority rule: (i) sentences containing query keywords, and (ii) earlier sentences in retrieved passages, which often summarize salient local context. These high-priority non-anchor sentences are marked as “selected” until the token budget is reached. Finally, all the sentences marked as “unselected” are removed from xx to obtain the compressed passage.

Passage Compression and Log-utility. We provide a heuristic argument relating log-utility u(r)u(r) to our passage compression. Suppose we randomly choose a sentence from passage xx. The probability of choosing an anchor sentence is p=∣SA∣∣S∣p = \frac{|S_A|}{|S|}. If we take the logarithm of 1/p1/p, we have that

log⁡1p=log⁡∣S∣∣SA∣(8)\log\frac{1}{p} = \log\frac{|S|}{|S_A|} \tag*{(8)}

(8) is analogous to the well-known Inverse Document Frequency (IDF); consider SS as a collection of documents (treating sentences as documents), and SAS_A as the document set containing a keyword, then (8) is the IDF. The IDF serves as a relevance metric for retrieval [34]. Suppose xx is compressed by our sentence selection method with retention ratio rr. The compressed passage retains SAS_A, but its size is reduced to approximately r∣S∣r|S|. Thus, (8) for the compressed passage is

log⁡r∣S∣∣SA∣=log⁡r+log⁡∣S∣∣SA∣(9)\log\frac{r|S|}{|S_A|} = \log r + \log\frac{|S|}{|S_A|} \tag*{(9)}

(9) shows the logarithmic dependence of relevance metric on rr (the second term is constant and does not affect optimization (5)), where we used u(r)=log⁡(1+r)u(r) = \log(1 + r) for numerical stability. Overall, u(r)u(r) can be approximately seen as a relevance metric associating the compressed passage with anchor terms.

Diffusion-based Context Stitching

All the retrieved passages are compressed and then concatenated to construct the final context denoted by X\mathcal{X}. While X\mathcal{X} preserves crucial factual information, concatenated sentences may not form a coherent context as a whole, because (i) some sentences are removed within the passage during compression; (ii) possibly heterogeneous passages are directly concatenated. We propose context-stitching based on text diffusion. The goal of stitching is to simply connect the sentences to maintain their natural semantic flows using a small amount of tokens. The stitching consists of two steps:

  1. Dynamically allocate stitching tokens, initialized as masked tokens, and insert them between adjacent sentences in X\mathcal{X}.

  2. Fill these stitching tokens in parallel via a diffusion-based denoising process.

Allocation based on Semantic overlap. We allocate κi,j\kappa_{i,j} stitching tokens between sentences ii and jj based on their semantic overlap. Let Ji,j\mathcal{J}_{i,j} denote the Jaccard similarity of sentences ii and jj, then

κi,j=⌊κˉ⋅(1−Ji,j)⌋(10)\kappa_{i,j} = \left\lfloor\bar{\kappa} \cdot(1-\mathcal{J}_{i,j}) \right\rfloor \tag*{(10)}

where κˉ\bar{\kappa} is the maximum budget for each stitching. κˉ\bar{\kappa} may differ depending on the types of ii, jj: if ii and jj belong to different passages, i.e., they are at passage boundaries and are likely to have a large semantic distance, κˉ\bar{\kappa} is set relatively large. In contrast, if ii and jj belong to the same passage, κˉ\bar{\kappa} is set relatively small; see § 4 for details.

Diffusion with a verbatim constraint. We perform text diffusion [26, 29] only on stitching tokens in X\mathcal{X}, while keeping the original context tokens frozen. We treat the frozen tokens as observed conditioning context and perform masked denoising only on the stitching positions (i.e., text infilling [43]). Let X(t)X^{(t)} denote the partially denoised version of X(T)≡XX^{(T)} \equiv\mathcal{X} at reverse step t=T,…,0t=T,\ldots,0. Let pθ(X(t−1)∣X(t))p_\theta(X^{(t-1)} \mid X^{(t)}) denote the reverse denoising distribution parameterized by θ\theta. Let I\mathcal{I} denote the index set of stitching tokens in X\mathcal{X}. We first sample an intermediate state

X~(t−1)∼pθ(X(t−1)∣X(t)),(11)\widetilde{X}^{(t-1)} \sim p_\theta(X^{(t-1)} \mid X^{(t)}), \tag*{(11)}

and update the context state at index ii or XiX_i:

Xi(t−1)={X~i(t−1),i∈I,Xi(T),i∉I.(12)X_i^{(t-1)} = \begin{cases} \widetilde{X}_i^{(t-1)}, & i \in\mathcal{I},\\ X_i^{(T)}, & i \notin\mathcal{I}. \end{cases} \tag*{(12)}

Our diffusion with the verbatim constraint, i.e., denoising only stitching tokens and keeping the original context fixed, prevents factual drift while allowing coherent transitions between fragmented passages. We use pre-trained denoising models, e.g., [32, 41], as pθp_\theta.

Why Diffusion? Text diffusion is advantageous for context stitching for the following reasons. 1) Auto-regressive models generate tokens only from left context, i.e., P(xt∣x<t)P(x_t \mid x_{<t}), whereas stitching is an interpolation problem capturing both preceding and succeeding contexts. We therefore adopt text diffusion, whose bidirectional attention works conditionally on both sides of the context. 2) Text diffusion enables parallel decoding over masked tokens, which can reduce latency when the diffusion step count is much smaller than the context length.

Experiment

Experimental Settings

We evaluate performance on five open-domain QA benchmarks. Following prior work [17, 13], we randomly sample 500 examples from each dataset using the default setup provided by FlashRAG [18].

Dataset. We evaluate retrieval-augmented generation on HotpotQA [40], Natural Questions (NQ) [24], TriviaQA [19], 2WikiMultiHopQA (2Wiki) [11], and PopQA [30]. HotpotQA and 2Wiki require multi-hop reasoning across multiple passages. NQ consists of real user queries paired with Wikipedia answers. TriviaQA focuses on factoid questions with evidence from web or Wikipedia sources. PopQA is an entity-centric open-domain QA benchmark constructed from Wikidata and designed to probe long-tail factual knowledge. For each query, we retrieve a fixed number of passages and condition the generator on the retrieved context.

Baselines. We compare StitchRAG against (i) non-retrieval baselines, including Naive Gen and MAD [6], (ii) Standard RAG [25], (iii) iterative / multi-step RAG methods that involve multiple stages of retrieval and/or generation (SuRe [22], FLARE [17], IRCoT [35], Self-RAG [2], DRAG [13]), and (iv) *context compression* methods (LongLLMLingua {citep}(Jiang et al., 2024)`, RE-

COMP [39], SELECTIVE CONTEXT [27]).

Implementation details. The system is built on the FLASHRAG toolkit [18]. Following this setup, we use E5-base-v2 [36] as the retriever and the widely adopted December 2018 Wikipedia dump as the retrieval corpus [21]. For fair comparison, all methods use the same retriever, and we report Exact Match (EM) and token-level F1 using standard evaluation protocols. For single-shot retrieval methods (including ours and non-iterative baselines), we retrieve Top-K=9K=9 passages once and condition the generator on the retrieved context. For baselines that explicitly iterate retrieval (e.g., FLARE, IRCoT, DRAG), we follow their original settings and retrieve Top-K=3K=3 passages per iteration for up to three retrieval–generation iterations (up to 9 passages total). The generator is LLAMA3-8B-INSTRUCT [15]. We instantiate our approach with LLADA [32] as the diffusion backbone, using T=32T=32 reverse diffusion steps. We set κˉ\bar{\kappa} to 2 for intra-passage sentences and to 7 for inter-passage sentences. For the diffusion backbone, we build on Fast-dLLM [38] and optimize its dynamic remasking for batched, GPU-parallel execution, which is crucial in context-stitching where

multiple retrieved passages are processed simultaneously. Specifically, we remove Python-level per-sample loops via vectorized sorting, prefix-product cutoff detection, and batched scatter-based selection, preserving the same remasking policy and matching transfer decisions while achieving an average ∼1.3×\sim1.3\times speedup for batch size ≥4\ge4 (Appendix A.5). All experiments were conducted on A100 GPUs.

Context budget for baselines. StitchRAG reduces the retrieved context to 72.29% on average of its original length across datasets. To match the retention budget, we set the retention ratio of other compression-based baselines and fixed-retention budget methods to 75% in all experiments. Table 9 in Appendix § 7.§ 4 provides detailed statistics.

HotpotQANQTriviaQA2WikiPopQAAvg.
Avg. retention ratio (%)74.2572.8376.2667.4470.6672.29

Table 9. Average r∗r^* of retrieved tokens achieved by STITCHRAG on each dataset.

Main Results

Table 1 summarizes end-to-end QA performance (EM/F1) on five open-domain benchmarks. Overall, StitchRAG achieves the strongest results, ranking first on 6 of 10 metrics and second on the remaining three, demonstrating robust performance across both single-hop and multi-hop QA. On HotpotQA, it improves over RAG [25] by +2.4 EM and +2.3 F1, and also outperforms DRAG [13] by +1.8 EM and +1.7 F1. On NQ, although Self-RAG [2] at tains the highest EM, StitchRAG achieves the best F1, improving over RAG by +2.1 F1. On TriviaQA, it sets the best EM and F1, surpassing RAG by +1.4 EM and +1.8 F1. On PopQA, DRAG achieves the highest EM, while SuRE attains the best F1. StitchRAG ranks second on both metrics. On 2Wiki, StitchRAG achieves the best F1 while ranking second in EM. Across datasets, both StitchRAG variants consistently outperform the retrieval baselines and most multi-step and compression-based methods. This shows that our dynamic context construction and diffusion-based stitching are an effective alternative to multi-round retrieval and generic context compression.

Ret.MethodHotpotQA EMHotpotQA F1NQ EMNQ F1TriviaQA EMTriviaQA F1PopQA EMPopQA F12Wiki EM2Wiki F1
Baselines
✗Naive Gen16.823.817.426.256.665.519.223.38.616.5
✗MAD23.032.721.833.156.466.321.428.218.225.1
✓RAG30.241.137.650.462.0<u>71.0</u>37.045.619.028.2
Compression Methods
✓LongLLMLingua29.439.533.445.460.269.334.041.516.827.0
✓RECOMP29.239.235.246.058.365.835.843.021.433.5
✓Selective Context22.136.432.542.657.665.929.536.813.619.5
Multi-step Methods
✓SuRe19.032.334.8<u>51.3</u>47.664.141.848.910.218.6
✓FLARE16.623.719.427.653.663.021.624.39.220.1
✓IRCoT25.234.428.637.347.254.527.033.022.831.1
✓Self-RAG14.828.844.051.246.458.322.034.313.026.6
✓DRAG<u>30.8</u><u>41.7</u>36.850.3<u>60.8</u>69.938.646.128.8<u>34.9</u>
Ours
✓StitchRAG32.643.4<u>39.4</u>53.363.472.8<u>37.2</u><u>46.3</u><u>27.8</u>35.4

Table 1. Comparison of retrieval-augmented generation methods. (✓: Retrieval used, ✗: No retrieval). Bold indicates the best performance. and <u>Underline</u> denotes the second-best performance.

Analyses

Robustness to Retrieval Noise. Figure 3 evaluates robustness under increasing retrieval depth by sweeping Top-KK from 10 to 30. As KK grows, the retrieved context becomes longer and typically noisier, substantially hurting RAG pipelines: Standard RAG drops sharply at Top-30, falling to 45.1 average F1 (from 48.1 at Top-10), indicating a pronounced sensitivity to retrieval noise and context-length effects. In contrast, StitchRAG remains essentially invariant across the sweep, staying at 51.2 average F1 for Top-10/20/30. This stability suggests that our dynamic context construction effectively decouples generation quality from the raw amount of retrieved evidence by filtering redundant content and preserving an information-dense context, thereby mitigating the degradation observed in naive scaling of retrieval depth.

Figure 3. Robustness to increased retrieval passages. Average F1 across four QA benchmarks (Hotpot, NQ, TriviaQA, 2Wiki) as the retrieval number of Top-KK increases (Top-10/20/30). While standard RAG degrades sharply at larger KK due to longer and noisier contexts, StitchRAG remains stable, mitigating retrieval noise and context-length effects.

Effectiveness of Dynamic Retention Budgets. Table 2 compares a fixed retention ratio (75%) against

CompressionHotpotQANQTriviaQA2Wiki
EMF1EMF1EMF1EMF1
Fixed 75%30.841.937.452.461.672.226.833.3
Dynamic (Avg. 72.7%)32.643.439.453.363.472.827.835.4

Table 2. Effect of adaptive vs. fixed retention ratio (75%) on StitchRAG (EM/F1).

our dynamic, utility-guided budgeting (average retention ≈72.7%\approx72.7\%). Across all four benchmarks, dynamic budgeting consistently improves both EM and F1, indicating that a fixed retention rate is sub-optimal under heterogeneous retrieval quality and question difficulty. The gains are most pronounced on multi-hop datasets: on HotpotQA, dynamic budgeting improves +1.8 EM and +1.5 F1, and on 2Wiki, +1.0 EM and +2.1 F1. We also observe consistent improvements on single-hop settings: on NQ, F1 increases by +0.9, and on TriviaQA, +1.8 EM and +0.6 F1. These results suggest that allocating a slightly larger budget to high-utility passages while aggressively filtering low-utility ones yields a higher information density under a comparable overall compression level, outperforming fixed-budget compression.

Ablation Study of Anchor Protection. Table 3 studies the contribution of our hybrid anchor extraction by ablating reasoning-centric AR anchors and query-centric lexical TF-IDF anchors. Using either anchor set alone is consistently worse than combining both, indicating strong complementarity. With AR-ONLY (TF-IDF removed), performance drops markedly on multi-hop datasets (HotpotQA: 29.8/41.4; 2Wiki: 25.8/33.4), suggesting that AR candidates alone may miss rare entities or exact lexical cues needed for precise evidence grounding. With TF-IDF-ONLY (AR removed), results improve over AR-only on HotpotQA and TriviaQA (31.8/42.4 and 63.2/72.4, respectively) but degrade on NQ (37.2/50.9), where paraphrased answers benefit from semantically guided anchors. Combining AR+TF-IDF yields the best performance across all datasets, demonstrating that semantic anchors from AR and lexical coverage from TF-IDF have synergistic effects, yielding faithful and information-rich sentences for subsequent stitching.

Impact of Stitching Strategies. Table 4 shows the effect of context stitching. We compare the modifications of StitchRAG: (i) NO STITCHING performs only dynamic context construction without stitching; (ii) AR STITCHING performs stitching with autoregressive models instead of diffusion. Table 4 shows that full StitchRAG performs the best on all benchmarks (e.g., HotpotQA +0.4 EM / +0.7 F1; NQ +1.4 EM / +2.4 F1; 2Wiki +1.8 EM / +2.0 F1) over NO STITCHING, showing that stitching contributes non-trivial gains by producing coherent transitions and reducing discontinuities between retained spans. In contrast, AR-stitching underperforms drastically, suggesting that left-to-right generation is brittle for constrained context editing: it tends to drift from frozen evidence and accumulates errors when forced to connect disjoint fragments. Our results show that diffusion-based stitching is better suited for faithful context construction.

VariantStitcherHotpotQANQTriviaQA2Wiki
EMF1EMF1EMF1EMF1
No stitching–32.242.738.050.961.471.126.033.4
AR-stitchingLLAMA27.438.337.650.556.065.524.033.2
StitchRAGDiffusion32.643.439.453.363.472.827.835.4

Table 4. Ablation on stitching components (EM/F1). “No stitching” removes diffusion stitching and uses only extracted evidence spans; “AR-stitching” replaces diffusion stitching with an autoregressive stitcher (LLAMA).

Effects of the number of Answer Candidates. From Table 5, we observe that the number of AR candidates has limited benefit beyond a single candidate. Using one AR candidate achieves a strong performance (43.4), and expanding the candidate set to 2 brings little improvement, while further increasing it to 5 substantially hurts performance. This trend suggests that additional AR candidates may introduce noisy or weakly relevant anchor signals. By contrast, performance consistently im-

SettingHyperparameterAvg F1
AR candidates sweep143.4
243.3
542.4
TF-IDF anchors sweep542.4
1043.4
2043.5

Table 5. Sensitivity to the number of Anchors. Left: AR candidate sweep with TF-IDF fixed to 10. Right: TF-IDF anchor sweep with AR fixed to 1. Values are Avg F1 on HotpotQA.

proves as the number of TF-IDF anchors increases from 5 to 10, and then saturates at 20. The small gain from 10 to 20 implies that a moderate number of TF-IDF anchors is sufficient to capture useful lexical evidence. Based on this trade-off, we use 1 AR candidate and 10 TF-IDF anchors.

Latency Analysis. Table 6 shows that StitchRAG strikes a practical balance between efficiency and performance. Although it is slower than Base RAG and Self-RAG, it remains substantially more efficient than IRCoT and DRAG, both of which require iterative multi-step reasoning. When we replaced diffusion-based stitching in StitchRAG with autoregressive stitching, latency increased by about 10.3 s. Thus, diffusion has advantages not only in performance but also in efficiency compared to AR due to its parallel decoding. Overall, our result positions StitchRAG as a middle-ground design point that improves over simple one-pass baselines without incurring the full cost of iterative methods.

RAGSelf-RAGIRCoTDRAGStitchRAG
Latency (seconds)7.24±2.847.24 \pm2.848.08±0.568.08 \pm0.5624.66±9.8124.66 \pm9.8127.39±7.9727.39 \pm7.9710.62±4.3010.62 \pm4.30

Table 6. Latency comparison. We randomly sample 100 examples from HotpotQA. All experiments are conducted with FlashRAG (Jin et al., [18]) on A100 GPUs, and results are reported as mean ± standard deviation.

Additional Results. We provide additional experiments on the use of another diffusion backbone, DREAM (Ye et al., [41]), and an analysis of stitching tokens in Appendix § 7.§ 1. A qualitative analysis is provided in Appendix § 7.§ 2.

Conclusion

In this work, we introduced StitchRAG, which addresses a central challenge in RAG: how to build a compact context without discarding the evidence most critical for answering. By combining passage-adaptive context-length allocation, hybrid anchor selection, and diffusion-based stitching, StitchRAG constructs compact yet information-dense contexts without incurring a substantial efficiency cost. Across five open-domain QA benchmarks, StitchRAG consistently outperforms prior multi-step and compression baselines while also offering a clear efficiency advantage. We hope this work motivates further research on adaptive and faithful context construction for long and complex retrieval settings.

Limitations

StitchRAG improves answer quality, reduces context length, and provides a theoretically grounded framework to determine the retention ratio. However, our approach still requires multiple model inferences similar to other advanced RAG methods. This incurs overhead as compared to the default baseline: single-pass RAG.

To mitigate this overhead, we design the pipeline to be batch-friendly. The extra calls can be amortized via auto-regressive batch inference for anchor scoring/selection across many queries. We also use parallelization strategies for stitching, such as diffusion parallel decoding (multi-sample denoising executed in parallel, enhanced by our modification A.5). In practice, these batching and parallel decoding techniques substantially reduce per-request overhead.

Finally, while our framework prevents factual drift by freezing verbatim anchors during diffusion, we restricted the diffusion method to lightweight stitching. This is mainly due to the limited capability of state-of-the-art discrete diffusion LLMs as of this writing. As diffusion-based generators mature, we envision an exciting direction beyond stitching: towards more aggressive yet faithful context refinement, elegantly rewriting and reorganizing non-anchor regions while keeping anchors intact, without increasing inference latency.

Appendix

Additional Experiments

Analysis of Stitching token budgets. Figure 4 sweeps the stitching-token budget κˉ\bar{\kappa} on HotpotQA (EM) while isolating intra-passage vs. inter-passage stitching. We find that the optimal budget differs substantially by scope: Intra-only peaks at a small budget (κˉ=2\bar{\kappa}=2, 32.4 EM), suggesting that within-passage gaps primarily require short local smoothing. In contrast, Inter-only benefits from a larger budget and peaks later (κˉ=7\bar{\kappa}=7, 31.8 EM), consistent with the higher difficulty of bridging cross-passage evidence. Performance degrades when κˉ\bar{\kappa} is overly large (e.g., inter-only at κˉ=9\bar{\kappa}=9), indicating that excessive stitching capacity can introduce drift or dilute the evidence-to-stitching ratio. Overall, this motivates using distinct budgets for intra- and inter-passage stitching rather than a single global setting.

Figure 4. Effect of stitching-token budget on intra-vs. inter-passage stitching.

Table 7 analyzes where stitching tokens matter by restricting stitching to intra-passage gaps only or inter-passage gaps only. Using either scope alone is insufficient: INTRA-ONLY yields strong HotpotQA performance but lags on NQ and 2Wiki, while INTER-ONLY improves cross-passage reasoning metrics but is slightly worse on HotpotQA and does not help TriviaQA. Enabling BOTH consistently delivers the best results across all datasets. This indicates that effective context construction requires both local smoothing within retrieved passages and global bridging across passages: intra-passage stitching resolves fragment boundaries and improves readability, while inter-passage stitching is essential for multi-hop evidence composition and cross-passage coherence.

SettingHotpotQANQTriviaQA2Wiki
EMF1EMF1EMF1EMF1
Intra-only32.042.738.651.561.070.726.033.7
Inter-only32.443.139.253.161.270.626.634.5
Both32.643.439.453.363.472.827.835.4

Table 7. Ablation on stitching scope (EM/F1). “Intra-only” uses stitching tokens only within the same passage; “Inter-only” stitches only across passages; “Both” enables both intra- and inter-passage stitching.

Results of StitchRAG with different Diffusion Backbone (Dream). Table 8 shows the performance of StitchRAG comparing different diffusion backbones for stitching: LLaDA [32] and Dream [41]. The Dream-based variant achieves competitive performance across all benchmarks, ranking second on HotpotQA (EM/F1), NQ F1, and TriviaQA (EM/F1) compared to the baseline methods shown in the main results in Table 1. These results indicate that the proposed framework generalizes across diffusion backbones.

Ret.MethodHotpotQANQTriviaQA2Wiki
EMF1EMF1EMF1EMF1
✓StitchRAG (Dream)<u>32.0</u><u>42.2</u>38.6<u>52.6</u><u>62.7</u><u>71.9</u>27.234.7
✓StitchRAG (LLaDA)32.643.4<u>39.4</u>53.363.472.8<u>27.8</u>35.4

Table 8. Results of StitchRAG with different diffusion LLMs. Bold and Underline respectively denote the best performance and the second-best performance in the Table 1 (main results).

Qualitative Analyses

We present three qualitative case studies, each organized around a different baseline: NaiveRAG, AR-RAG, and No Stitching. Each case highlights how STITCHRAG improves context construction and downstream answer generation under a distinct retrieval failure pattern.

Case Study: Evidence Stitching for Multi-hop Reasoning (HotpotQA)

Question

When was the novel published in 2010 which is part of the series of The Maze Runner?

Correct Answer

September 18, 2010

Reasoning Requirement

The Maze Runner series →\to novel released in 2010

The Scorch Trials

publication date →\to September 18, 2010

Evidence in the Original Retrieved Context

The retrieved passages already contain the necessary evidence, but the relevant facts are fragmented across different sentences. In the original context, the two pieces of evidence are separated by multiple sentences:

. . .

The Scorch Trials is a 2010 young adult post-apocalyptic . . . in the “The Maze Runner” series. The novel was published on September 18, 2010 by Delacorte Press.

. . .

Failure of Naive Context Concatenation

The naive RAG concatenates retrieved passages into a long context (1607 tokens) without explicitly connecting related evidence. As a result, the relationship between the Maze Runner series, the 2010 novel, and its publication date remains implicit. The model therefore stops at the intermediate entity:

NaiveRAG →\to The Scorch Trials (incorrect)

Evidence Stitching by Diffusion

StitchRAG preserves the original evidence spans as anchors and generates a short connective sentence that stitches them into a coherent reasoning chain:

. . .

The Scorch Trials is the second book released in the series, on September 18, 2010.

. . .

Importantly, the stitched sentence does not introduce new factual evidence. Instead, it connects the preserved evidence spans into a form that is easier for the language model to interpret.

Outcome

NaiveRAG →\to The Scorch Trials (incorrect) StitchRAG →\to September 18, 2010 (correct)

Context Reduction

1607 tokens →\to 1219 tokens (24% compression)

Analysis

This example highlights the role of diffusion-based stitching. Although the retrieved context already contains the necessary evidence, the relevant information appears in fragmented sentences. StitchRAG preserves the original evidence spans and generates a short bridging sentence that connects them into a coherent reasoning path. This stitched context makes the relationship between evidence explicit and shortens the multi-hop reasoning process, enabling the model to produce the correct answer.

Case Study: Evidence Stitching for Multi-hop Reasoning (WikiMultiHopQA)

Question

Who is James Roosevelt Roosevelt’s sibling-in-law?

Correct Answer

Eleanor Roosevelt

Reasoning Requirement

James Roosevelt Roosevelt ⇓\Downarrow (half-brother) Franklin Delano Roosevelt ⇓\Downarrow (married) Eleanor Roosevelt

Evidence in the Original Retrieved Context

The retrieved passages contain the necessary facts, but they appear in separate documents. The relationship chain required for multi-hop reasoning is therefore fragmented across the context.

. . .

“James Roosevelt “Rosy” Roosevelt (April 27, 1854 – May 7, 1927) was an American diplomat, heir, and the older half-brother of 32nd President of the United States Franklin Delano Roosevelt.”

. . .

“In 1905, he married his fifth cousin once removed, Eleanor Roosevelt.”

. . .

These two pieces of evidence provide the required relations:

James Roosevelt Roosevelt →\to Franklin Delano Roosevelt Franklin Delano Roosevelt →\to Eleanor Roosevelt

However, in the original retrieved context these facts are separated by large amounts of unrelated biography text, making the reasoning path implicit.

Failure of Naive Context Concatenation

Naive RAG concatenates the retrieved passages without aligning the relations across documents. As a result, the model often stops at the intermediate entity:

NaiveRAG →\to Franklin Delano Roosevelt (incorrect)

The final relational step linking Franklin Roosevelt to Eleanor Roosevelt is not explicitly connected to the earlier evidence.

Evidence Stitching by Diffusion

StitchRAG preserves the original evidence spans and places them within a single coherent reasoning segment:

. . .

James Roosevelt “Rosy” Roosevelt was the older half-brother of Franklin Delano Roosevelt. Franklin Delano Roosevelt married Eleanor Roosevelt.

. . .

This stitched context makes the relational chain explicit:

James Roosevelt Roosevelt →\to Franklin Delano Roosevelt →\to Eleanor Roosevelt

Outcome

NaiveRAG →\to Franklin Delano Roosevelt (incorrect) StitchRAG →\to Eleanor Roosevelt (correct)

Analysis

The required relations already exist in the retrieved passages but appear in separate documents and are embedded in irrelevant text. By preserving the evidence spans and placing them in a coherent context, StitchRAG enables the model to connect the relations and correctly infer that the sibling-in-law of James Roosevelt Roosevelt is Eleanor Roosevelt.

Case Study: Diffusion-based Knowledge Completion (HotpotQA)

Question

The rapper whose debut album was titled “Thug Misses” has sold over how many records worldwide?

Correct Answer

2 million

Reasoning Requirement

This HotpotQA example requires bridge-type multi-hop reasoning:

Thug Misses →\to rapper Khia

⇓\Downarrow

Khia’s worldwide record sales →\to 2 million

Missing Evidence in the Retrieved Context

The retrieved passages correctly identify the artist associated with the album, but they do not contain the worldwide record sales required to answer the question.

...

“Thug Misses is the debut album by American rapper Khia.” “The album spawned the single “My Neck, My Back (Lick It)”.” “As of June 2007 the album had sold 611,000 copies in the US.”

...

Thus, the retrieved evidence provides information about the album and its U.S. sales, but the key fact about Khia’s worldwide record sales is missing from the retrieved context.

Model Outputs

Because the retrieved passages prominently contain the number 611,000, several RAG systems incorrectly treat this number as the answer.

NaiveRAG →\to 611,000 (incorrect)

No Stitching →\to 611,000 (incorrect)

AR-RAG →\to Not specified

StitchRAG →\to 2 million (correct)

Diffusion-based Completion

After diffusion-based context reconstruction, the refined context contains the following passage:

...

“The album was moderately successful and achieved moderate crossover chart success.” “Khia released her album later that year, which also gained gold status.” “Khia sold over 2 million records worldwide.”

...

Notably, the statement about Khia’s worldwide sales does not appear in the retrieved passages.

Analysis

This example illustrates that diffusion-based stitching can go beyond simply connecting retrieved evidence spans. While the retrieved context contains only partial information (the album and its U.S. sales), the diffusion process introduces a missing factual link using parametric knowledge learned during pretraining. By combining the retrieved evidence with this generated fact, StitchRAG is able to complete the multi-hop reasoning chain and produce the correct answer.

Case Study: Structural Evidence Stitching (HotpotQA)

Question

Which author wrote a play in 2006 and a book on homosexual sex in 1977?

Correct Answer

Edmund Valentine White III

Reasoning Requirement

This question requires identifying an author who satisfies two conditions:

book about homosexual sex (1977) →\rightarrow author →\rightarrow playwright (2006)

Evidence in the Original Context

The retrieved passages mainly discuss unrelated topics such as:

  • religious views on homosexuality

  • legal cases and legislation

  • unrelated books and films

  • historical events

Although the word homosexual sex appears multiple times, the passages do not contain any information linking a specific book to its author, nor do they provide any connection to theatrical works.

Structural Evidence Stitching in the Stitched Context

The stitched context organizes evidence into structured topical segments. For example:

Documentary film

Gay Sex in the 70s

and the literary reference:

Faggots (novel)

“The novel’s portrayal of promiscuous sex and recreational drug use provoked controversy.”

In addition, the stitched context contains structural markers such as:

References

These elements group related cultural and literary references, creating a structured context around LGBTQ-related works.

How Stitching Enables Reasoning

The stitched context introduces a crucial evidence anchor:

Faggots (novel)

This work is associated with the author Edmund White and is known for its depiction of homosexual culture in the late 1970s. This anchor satisfies the first condition in the question:

book about homosexual sex (1977)

Through structural evidence stitching, related passages about LGBTQ literature and cultural works are placed within the same semantic region. This stitched context allows the model to identify Edmund White as the author and recognize that he is also a playwright who produced theatrical works in 2006.

Rather than inserting the answer directly, StitchRAG stitches topically related evidence into a coherent reasoning structure, enabling the model to recover the reasoning chain and correctly infer the answer.

Error Case

Question

Who is Thessalonike of Macedon’s father-in-law?

Correct Answer

Antipater

Model Prediction

Cassander

Reasoning Requirement

Answering this question requires a two-step kinship inference:

Thessalonike of Macedon →\to wife of Cassander Cassander →\to son of Antipater ⇓\Downarrow father-in-law of Thessalonike →\to Antipater

Evidence in the Retrieved Context

The retrieved context clearly supports that Thessalonike married Cassander, but it does not explicitly preserve the second link needed for the full inference: Cassander →\to son of Antipater. Thus, the context strongly supports identifying the husband, but not the father-in-law.

[. . .]

“Thessalonike was a Macedonian princess . . . and wife of Cassander.”

[. . .]

“Cassander married her. Thessalonike became queen of Macedon . . . ”

[. . .]

Example of Structural Stitching

In the refined context, the main preserved evidence anchor is:

Thessalonike of Macedon →\to wife of Cassander

This anchor provides only partial structural Stitching. It links Thessalonike to her husband, but not Cassander to his father:

Cassander →\to Antipater’s son

As a result, the context encourages a relation collapse from father-in-law to husband.

Reasoning Failure Induced by Incomplete Structural Stitching

With only the first kinship link preserved, the model defaults to the nearest available male relative:

Thessalonike →\to Cassander

Prediction →\to Cassander

But the correct reasoning requires an additional genealogical step:

Thessalonike →\to husband: Cassander Cassander →\to father: Antipater ⇓\Downarrow father-in-law →\to Antipater

Analysis

This is a failure case of structural stitching. The refinement preserves an anchor sufficient to recover Thessalonike’s husband, but not the extra bridge needed to resolve the father-in-law relation. The model therefore predicts Cassander, a locally supported but semantically incorrect answer. The gold answer, Antipater, requires a second genealogical link that is absent from the refined context.

Error Case

Question

Where does the director of film Présentation ou Charlotte et son steak work at?

Correct Answer

Cahiers du cinéma

Model Prediction

Switzerland

Reasoning Requirement

Answering this question requires identifying the film’s director and then linking that director to his workplace:

Preˊsentation ou Charlotte et son steak→ directed by Eˊric Rohmer\text{Présentation ou Charlotte et son steak} \mathbin{\to} \text{ directed by Éric Rohmer}
Eˊric Rohmer→ worked at Cahiers du cineˊma\text{Éric Rohmer} \mathbin{\to} \text{ worked at Cahiers du cinéma}
↓\downarrow
director’s workplace→ Cahiers du cineˊma\text{director’s workplace} \mathbin{\to} \text{ Cahiers du cinéma}

Evidence in the Retrieved Context

The retrieved context preserves the first step but not the second, and instead highlights an irrelevant location cue tied to the film’s setting.

[…]

“Présentation ou Charlotte et son steak is a French short drama film written and directed by Éric Rohmer … In a Swiss village in winter, Walter is walking with Charlotte when they meet Clara.”

[…]

The missing second-hop fact is:

Eˊric Rohmer→ worked at Cahiers du cineˊma\text{Éric Rohmer} \mathbin{\to} \text{ worked at \textbf{Cahiers du cinéma}}

Example of Structural Stitching

In the refined context, the system preserves the director anchor but also highlights a competing location anchor:

Preˊsentation ou Charlotte et son steak→Eˊric Rohmer\textbf{Présentation ou Charlotte et son steak} \mathbin{\to} \textbf{Éric Rohmer}
Preˊsentation ou Charlotte et son steak→Swiss village\textbf{Présentation ou Charlotte et son steak} \mathbin{\to} \textbf{Swiss village}

These anchors create misleading structural stitching, since the workplace link is missing while an irrelevant geographical cue remains salient.

Reasoning Failure Induced by Misleading Structural Stitching

The model may therefore substitute the film’s setting for the director’s workplace:

Preˊsentation ou Charlotte et son steak→ Swiss village\text{Présentation ou Charlotte et son steak} \mathbin{\to} \text{ Swiss village}
Swiss village→ Switzerland\text{Swiss village} \mathbin{\to} \text{ Switzerland}
Prediction→Switzerland\text{Prediction} \mathbin{\to} \textbf{Switzerland}

The correct reasoning is:

Preˊsentation ou Charlotte et son steak→ director: Eˊric Rohmer\text{Présentation ou Charlotte et son steak} \mathbin{\to} \text{ director: Éric Rohmer}
Eˊric Rohmer→ workplace: Cahiers du cineˊma\text{Éric Rohmer} \mathbin{\to} \text{ workplace: Cahiers du cinéma}
↓\downarrow
answer→Cahiers du cineˊma\text{answer} \mathbin{\to} \textbf{Cahiers du cinéma}

Analysis

This example illustrates a relation-substitution error. Although the refined context correctly links the film to Éric Rohmer, it does not preserve the evidence connecting Rohmer to Cahiers du cinéma. Instead, it highlights the film’s Swiss setting, which encourages the model to substitute a salient location for the director’s workplace.

Prompt Templates

Relevance probing prompt. We estimate R(x,q)=P(Z=1)R(x,q)=P(Z=1) using a fixed binary prompt that asks whether a retrieved passage is useful for answering the query. We decode neither a rationale nor a free-form answer; instead, we only score the canonical responses Yes and No.

Question: ⟨q⟩
Passage: ⟨x⟩
Is this passage relevant to the question? Answer (Yes/No):

Scoring. Let LYes\mathcal{L}_{\mathrm{Yes}} and LNo\mathcal{L}_{\mathrm{No}} denote the (sequence) log-probabilities of the targets Yes and No under the model given the prompt. If a target is tokenized into multiple tokens, we sum log-probabilities across its token sequence. We then compute

R(x,q)=exp⁡(LYes)exp⁡(LYes)+exp⁡(LNo).(13)R(x,q)=\frac{\exp(\mathcal{L}_{\mathrm{Yes}})}{\exp(\mathcal{L}_{\mathrm{Yes}})+\exp(\mathcal{L}_{\mathrm{No}})}. \tag*{(13)}

Answer generation prompt (RAG). For all methods, the final answer is generated by an autoregressive generator conditioned on the (possibly compressed/stitched) context. We use the following instruction-style RAG prompt.

[System] Answer the question based on the given passages. Provide a direct and accurate answer.
[User]
Passage:
⟨context⟩

Question: ⟨q⟩

Please provide the answer in the format: ‘The answer is: [your answer]’.

Average Retention ratio r∗r^* of StitchRAG

Vectorized Implementation of Dynamic Remasking

This appendix compares the original Fast-dLLM dynamic remasking implementation ([38]) with our vectorized PyTorch version. The vectorized implementation follows the same dynamic remasking policy as the original version and produced matching transfer decisions in all of our tests, while removing Python-level per-sample loops to improve batched inference efficiency.

Background (Dynamic Remasking Policy). Let masked tokens be ranked by confidence in descending order. Conceptually, the algorithm selects the longest confidence-sorted prefix whose elements satisfy a rank-dependent threshold,

τr=1−αr+1,(14)\tau_r=1-\frac{\alpha}{r+1}, \tag*{(14)}

where α\alpha is a factor parameter (typically α=1\alpha=1), while ensuring that at least one token is transferred whenever masked positions exist.

Original Implementation (Fast-dLLM) The original implementation iterates over batch elements in Python: it computes per-sample thresholds, sorts masked-token confidences, scans ranks to find the cutoff kk, and then applies per-sample top-kk selection.

Our Vectorized Implementation We implement the same logic using tensor-native operations only. Instead of sorting only masked positions, we sort the full sequence after assigning unmasked positions a sentinel “−∞-\infty-like” value, ensuring they are placed at the tail and do not affect the top-kk masked ranks. Cutoff detection and index materialization are fully vectorized across the batch.

ComponentOriginalOurs
Batch iterationPython for loopVectorized
Threshold computationList comprehensiontorch.arange
SortingPer-sample (masked-only)Batch-parallel (full, with sentinel)
Cutoff detectionNested loopPrefix-product (cumprod)
SelectionPer-sample topkBatched scatter
Edge casesManual iftorch.where

Table 10. Comparison of implementation strategies.

Batch SizeOriginalOursSpeedup
12.41 ms2.31 ms1.04×
49.25 ms8.49 ms1.09×
826.49 ms20.00 ms1.32×
1644.92 ms36.00 ms1.25×
3284.56 ms65.14 ms1.30×

Table 11. Inference time comparison of get_transfer_index_dynamic (seq_len=2048, vocab=32k, warmup=10, repeat=50). We conducted our experiments on a single NVIDIA A100 GPU.

Key Optimization To avoid explicit scanning loops, we implement threshold-based prefix selection with a vectorized prefix-product operation over the sorted pass mask. This yields the valid prefix length efficiently and is well-suited for batch-parallel GPU execution.

Performance Both versions are dominated by sorting at long sequence lengths; the practical speedup comes from eliminating Python overhead and enabling batch-parallel execution on GPU, which improves utilization for B≥4B \ge4 in our setup.

Equivalence Validation The vectorized implementation follows exactly the same threshold rule and prefix selection criterion as the original version. We verified output equivalence through randomized unit tests over 1,000 cases with varying batch sizes, sequence lengths, and mask densities, and observed no accuracy difference in end-to-end evaluation on HotpotQA and NQ.

def get_transfer_index_dynamic(logits, temperature, remasking,
                               mask_index, x, num_transfer_tokens, factor=1):
    # Sample proposals and compute confidence
    logits_with_noise = add_gumbel_noise(logits, temperature)
    x0 = torch.argmax(logits_with_noise, dim=-1)
    p = F.softmax(logits.to(torch.float64), dim=-1)
    x0_p = torch.squeeze(
        torch.gather(p, dim=-1, index=torch.unsqueeze(x0, -1)), -1)

    x0 = torch.where(mask_index, x0, x)
    confidence = torch.where(mask_index, x0_p, -np.inf)

    transfer_index = torch.zeros_like(x0, dtype=torch.bool)
    num_transfer_tokens = mask_index.sum(dim=1, keepdim=True)

    # Per-sample loop (sequential processing)
    for j in range(confidence.shape[0]):
        num_tokens = int(num_transfer_tokens[j].item())
        if num_tokens == 0:
            continue

        # Compute thresholds (Python list comprehension)
        ns = list(range(1, num_tokens+1))
        es = [factor/(n+1) for n in ns]
        threshs = [1-e for e in es]
        threshs[0] = -1 # Ensure at least one transfer

        # Sort masked tokens only
        sorted_confidence = torch.sort(
            confidence[j][mask_index[j]], descending=True)[0]

        # Find cutoff rank
        for top_i in range(len(threshs)):
            if sorted_confidence[top_i] < threshs[top_i]:
                break

        # Edge case handling
        if top_i == 0 or top_i == len(threshs)-1:
            top_i += 1

        # Select top-k
        _, select_index = torch.topk(confidence[j], k=top_i)
        transfer_index[j, select_index] = True

    return x0, transfer_index

Table 12. Original Fast-dLLM implementation (sequential per-sample loop).

def get_transfer_index_dynamic(logits, temperature, remasking,
                               mask_index, x, num_transfer_tokens=None,
                               factor=1.0, threshold=None):

    # Sample proposals and compute confidence
    logits_with_noise = add_gumbel_noise(logits, temperature)
    x0 = torch.argmax(logits_with_noise, dim=-1)
    p = F.softmax(logits.to(torch.float64), dim=-1)
    x0_p = torch.gather(p, dim=-1, index=x0.unsqueeze(-1)).squeeze(-1)

    x0 = torch.where(mask_index, x0, x)
    neg_inf = torch.tensor(torch.finfo(x0_p.dtype).min,
                           device=x0_p.device, dtype=x0_p.dtype)
    confidence = torch.where(mask_index, x0_p, neg_inf)

    B, L = confidence.shape
    mask_counts = mask_index.sum(dim=1).to(dtype=torch.long)

    # Early exit for empty masks
    if (mask_counts == 0).all():
        return x0, torch.zeros_like(mask_index, dtype=torch.bool)

    # Vectorized threshold computation
    ranks = torch.arange(L, device=confidence.device, dtype=torch.float64)
    thr = 1.0 - (float(factor) / (ranks + 2.0))
    thr[0] = torch.finfo(torch.float64).min # At least one transfer

    # Batch sorting (parallel across batch dimension)
    values, idx = torch.sort(confidence, dim=1, descending=True)

    # Vectorized threshold comparison
    pass_mask = values >= thr.unsqueeze(0) # (B, L)

    # Prefix product to find consecutive passing ranks
    prefix_ok = torch.cumprod(pass_mask.to(torch.int64), dim=1)
    k = prefix_ok.sum(dim=1).to(dtype=torch.long) # Per-sample k

    # Vectorized edge case handling (match original boundary handling)
    k = torch.minimum(k, mask_counts)
    k = torch.where(mask_counts > 0, torch.clamp(k, min=1), k)
    k = torch.where((mask_counts > 0) & (k == mask_counts-1),
                    mask_counts, k)

    # Vectorized top-k selection via scatter
    cols = torch.arange(L, device=confidence.device).unsqueeze(0).expand(B, L)
    select_sorted = cols < k.unsqueeze(1)
    transfer_int = torch.zeros(B, L, device=confidence.device, dtype=torch.int8)
    transfer_int = transfer_int.scatter(1, idx, select_sorted.to(torch.int8))
    transfer_index = transfer_int.bool() & mask_index

    return x0, transfer_index

Table 13. Our vectorized implementation (batch-parallel on GPU).

References

  1. [1]Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774.arxiv.org/abs/2303.08774
  2. [2]Akari Asai, Zeqiu Wu, Yizhong Wang, Avirup Sil, and Hannaneh Hajishirzi. 2023. Self-rag: Learning to retrieve, generate, and critique through self-reflection. In The Twelfth International Conference on Learning Representations.arxiv.org/abs/2310.11511
  3. [3]Sinchanа Ramakanth Bhat, Max Rudat, Jannis Spiekermann, and Nicolas Flores-Herr. 2025. Rethinking chunk size for long-document retrieval: A multi-dataset analysis. arXiv preprint arXiv:2505.21700.arxiv.org/abs/2505.21700
  4. [4]Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press.
  5. [5]Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. 2017. Reading wikipedia to answer open-domain questions. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1870–1879.arxiv.org/abs/1704.00051
  6. [6]Yilun Du, Shuang Li, Antonio Torralba, Joshua B Tenenbaum, and Igor Mordatch. 2024. Improving factuality and reasoning in language models through multi-agent debate. In Forty-first international conference on machine learning.
  7. [7]Yufeng Du, Minyang Tian, Srikanth Ronanki, Subendhu Rongali, Sravan Bodapati, Aram Galstyan, Azton Wells, Roy Schwartz, Eliu A Huerta, and Hao Peng. 2025. Context length alone hurts llm performance despite perfect retrieval. arXiv preprint arXiv:2510.05381.arxiv.org/abs/2510.05381
  8. [8]Yixiong Fang, Tianran Sun, Yuling Shi, and Xiaodong Gu. 2025. Attentionrag: Attention-guided context pruning in retrieval-augmented generation. arXiv preprint arXiv:2503.10720.arxiv.org/abs/2503.10720
  9. [9]Shansan Gong, Mukai Li, Jiangtao Feng, Zhiyong Wu, and LingPeng Kong. 2022. Diffuseq: Sequence to sequence text generation with diffusion models. arXiv preprint arXiv:2210.08933.arxiv.org/abs/2210.08933
  10. [10]Harold Stanley Heaps. 1978. Information retrieval: Computational and theoretical aspects. Academic Press, Inc.
  11. [11]Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. 2020. Constructing a multi-hop qa dataset for comprehensive evaluation of reasoning steps. In Proceedings of the 28th International Conference on Computational Linguistics, pages 6609–6625.
  12. [12]Kelly Hong, Anton Troynikov, and Jeff Huber. 2025. Context rot: How increasing input tokens impacts llm performance. Technical report, Chroma.
  13. [13]Wentao Hu, Wengyu Zhang, Yiyang Jiang, Chen Jason Zhang, Xiaoyong Wei, and Li Qing. 2025. Removal of hallucination on hallucination: Debate-augmented rag. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 15839–15853.arxiv.org/abs/2505.18581
  14. [14]Qishuo Hua, Lyumanshan Ye, Dayuan Fu, Yang Xiao, Xiaojie Cai, Yunze Wu, Jifan Lin, Junfei Wang, and Pengfei Liu. 2025. Context engineering 2.0: The context of context engineering. arXiv preprint arXiv:2510.26493.arxiv.org/abs/2510.26493
  15. [15]Kunal Chawla Huang, Kushal Lakhotia, Kyle Huang, Lailin Chen, Lakshya Garg, A Lavender, Leandro Silva, Lee Bell, Lei Zhang, Liangpeng Guo, et al. 2024. The llama 3 herd of models. preprint.arxiv.org/abs/2407.21783
  16. [16]Huiqiang Jiang, Qianhui Wu, Chin-Yew Lin, Yuqing Yang, and Lili Qiu. 2023a. Longllmlingua: Accelerating and enhancing llms in long context scenarios via prompt compression. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1658–1677.
  17. [17]Zhengbao Jiang, Frank F Xu, Luyu Gao, Zhiqing Sun, Qian Liu, Jane Dwivedi-Yu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023b. Active retrieval augmented generation. In Proceedings of the 2023 conference on empirical methods in natural language processing, pages 7969–7992.
  18. [18]Jiajie Jin, Yutao Zhu, Zicheng Dou, Guanting Dong, Xinyu Yang, Chenghao Zhang, Tong Zhao, Zhao Yang, and Ji-Rong Wen. 2025. Flashrag: A modular toolkit for efficient retrieval-augmented generation research. In Companion Proceedings of the ACM on Web Conference 2025, pages 737–740.
  19. [19]Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. 2017. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1601–1611.arxiv.org/abs/1705.03551
  20. [20]Adam Tauman Kalai, Ofir Nachum, Santosh S Vempala, and Edwin Zhang. 2025. Why language models hallucinate. arXiv preprint arXiv:2509.04664.arxiv.org/abs/2509.04664
  21. [21]Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 conference on empirical methods in natural language processing (EMNLP), pages 6769–6781.arxiv.org/abs/2004.04906
  22. [22]Jaehyung Kim, Jaehyun Nam, Sangwoo Mo, Jongjin Park, Sang Woo Lee, Minjoon Seo, Jung Woo Ha, and Jinwoo Shin. 2024a. Sure: Summarizing retrievals using answer candidates for open-domain qa of llms. In 12th International Conference on Learning Representations, ICLR 2024.arxiv.org/abs/2404.13081
  23. [23]Minsang Kim, Cheoneum Park, and Seung Jun Baek. 2024b. Qpaug: Question and passage augmentation for open-domain question answering of llms. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 9024–9042.arxiv.org/abs/2406.14277
  24. [24]Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. 2019. Natural questions: a benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:453–466.DOI
  25. [25]Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in neural information processing systems, 33:9459–9474.arxiv.org/abs/2005.11401
  26. [26]Xiang Li, John Thickstun, Ishaan Gulrajani, Percy S Liang, and Tatsunori B Hashimoto. 2022. Diffusion-lm improves controllable text generation. Advances in neural information processing systems, 35:4328–4343.arxiv.org/abs/2205.14217
  27. [27]Yucheng Li, Bo Dong, Frank Guerin, and Chenghua Lin. 2023. Compressing context to enhance inference efficiency of large language models. In Proceedings of the 2023 conference on empirical methods in natural language processing, pages 6342–6353.arxiv.org/abs/2310.06201
  28. [28]Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paran-jape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. 2024. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12:157–173.arxiv.org/abs/2307.03172
  29. [29]Aaron Lou, Chenlin Meng, and Stefano Ermon. 2023. Discrete diffusion modeling by estimating the ratios of the data distribution. arXiv preprint arXiv:2310.16834.arxiv.org/abs/2310.16834
  30. [30]Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, and Hannan eh Hajishirzi. 2023. When not to trust language models: Investigating effectiveness of parametric and non-parametric memories. In Proceedings of the 61st annual meeting of the association for computational linguistics (volume 1: Long papers), pages 9802–9822.
  31. [31]Lingrui Mei, Jiayu Yao, Yuyao Ge, Yiwei Wang, Baolong Bi, Yujun Cai, Jiazhi Liu, Mingyu Li, Zhong-Zhi Li, Duzhen Zhang, et al. 2025. A survey of context engineering for large language models. arXiv preprint arXiv:2507.13334.arxiv.org/abs/2507.13334
  32. [32]Shen Nie, Fengqi Zhu, Zebin You, Xiaolu Zhang, Jingyang Ou, Jun Hu, Jun Zhou, Yankai Lin, Ji-Rong Wen, and Chongxuan Li. 2025. Long language diffusion models. arXiv preprint arXiv:2502.09992.arxiv.org/abs/2502.09992
  33. [33]Zhuoshi Pan, Qianhui Wu, Huiqiang Jiang, Menglin Xia, Xufang Luo, Jue Zhang, Qingwei Lin, Victor Rühle, Yuqing Yang, Chin-Yew Lin, et al. 2024. Limlingua-2: Data distillation for efficient and faithful task-agnostic prompt compression. In Findings of the Association for Computational Linguistics: ACL 2024, pages 963–981.arxiv.org/abs/2403.12968
  34. [34]Stephen Robertson. 2004. Understanding inverse document frequency: on theoretical arguments for idf. Journal of documentation, 60(5):503–520.DOI
  35. [35]Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. 2023. Interleaving retrieval with chain-of-thought reasoning for knowledge-intensive multi-step questions. In Proceedings of the 61st annual meeting of the association for computational linguistics (volume 1: long papers), pages 10014–10037.arxiv.org/abs/2212.10509
  36. [36]Liang Wang, Nan Yang, Xiaolong Huang, Binxing Jiao, Linjun Yang, Daxin Jiang, Rangan Majumder, and Furu Wei. 2022. Text embeddings by weakly-supervised contrastive pre-training. arXiv preprint arXiv:2212.03533.arxiv.org/abs/2212.03533
  37. [37]Sean Welleck, Ilia Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston. 2019. Neural text generation with unlikelihood training. arXiv preprint arXiv:1908.04319.arxiv.org/abs/1908.04319
  38. [38]Chengyue Wu, Hao Zhang, Shuchen Xue, Zhijian Liu, Shizhe Diao, Ligeng Zhu, Ping Luo, Song Han, and Enze Xie. 2025. Fast-dllm: Training-free acceleration of diffusion llm by enabling kv cache and parallel decoding. arXiv preprint arXiv:2505.22618.arxiv.org/abs/2505.22618
  39. [39]Fangyuan Xu, Weijia Shi, and Eunsol Choi. 2023. Recomp: Improving retrieval-augmented lms with compression and selective augmentation. arXiv preprint arXiv:2310.04408.arxiv.org/abs/2310.04408
  40. [40]Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D Manning. 2018. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 conference on empirical methods in natural language processing, pages 2369–2380.arxiv.org/abs/1809.09600
  41. [41]Jiacheng Ye, Zhihui Xie, Lin Zheng, Jiahui Gao, Zirui Wu, Xin Jiang, Zhenguo Li, and Lingpeng Kong. 2025. Dream 7b: Diffusion large language models. arXiv preprint arXiv:2508.15487.arxiv.org/abs/2508.15487
  42. [42]Zijie Zhong, Hanwen Liu, Xiaoya Cui, Xiaofan Zhang, and Zengchang Qin. 2025. Mix-of-granularity: Optimize the chunking granularity for retrieval-augmented generation. In Proceedings of the 31st International Conference on Computational Linguistics, pages 5756–5774.arxiv.org/abs/2406.00456
  43. [43]Wanrong Zhu, Zhiting Hu, and Eric Xing. 2019. Text infilling. arXiv preprint arXiv:1901.00158.arxiv.org/abs/1901.00158

Paper details

vlnc:W_4ucpn5wv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents