Source-linked AI summary
STITCH-RAG: Spatio-Temporal Influence Tracing over Topic Hypergraphs for Multi-Hop Retrieval-Augmented Generation
Haodong Yang, Mengzhu Chen, Jia Cai
TL;DR
Multi-hop RAG needs to connect evidence across documents, but chunking can break those chains and existing representations may not preserve topic context alongside local entity states. STITCH-RAG combines a semi-merged topic hypergraph with influence bridging and continuous-prior localized PPR. Under the reported protocol, it leads the compared methods on reported accuracy point estimates and on Recall@8 where standardized retrieval comparisons are available.
Problem
Chunk-based RAG can miss cross-boundary evidence chains, while the scoped unlabeled pairwise and full-merge representations do not jointly preserve topic provenance and chunk-specific entity roles.
Source: §1 · p. 1Method
STITCH-RAG links chunk-specific entity states by canonical-name equivalence, propagates influence through topic and index-proximity channels, and uses continuous scores as a localized PPR prior.
Source: §1 · pp. 1–2Results
STITCH-RAG has the highest reported Contain-Acc and LLM-Acc point estimates in Table 1 and the highest Recall@8 in Table 2 under the reported protocol.
Source: §5 · p. 6Takeaways & Limitations
The paper couples topic-preserving hyperedges, local entity states, frequency-adaptive bridging, and continuous-prior PPR, while characterizing these mechanisms without claiming end-to-end optimality guarantees.
Source: §5 · p. 6The sufficient alignment condition for the evidence-mass result is not independently verified because reachability, seed coverage, empty matches, and prior-support size are unmeasured.
Source: Chunk Score Projection and Localized… · p. 5
Abstract
from arXiv · showhide
Multi-hop retrieval-augmented generation requires a retriever to connect evidence distributed across documents while preserving a concise, faithful generation context. Existing indexes leave two complementary gaps: chunk-based RAG can break cross-passage evidence chains, whereas an unlabeled pairwise projection without generating-topic provenance cannot jointly preserve topic-level co-participation and per-occurrence entity descriptions. We propose STITCH-RAG, a hypergraph-based framework with three coupled components. First, a semi-merged topic hypergraph encodes multi-entity co-participation as topic-summary hyperedges while retaining per-chunk entity states linked by canonical-name equivalence. Second, spatio-temporal influence bridging propagation (STIBP) combines topic-space propagation with deterministic chunk-index linkage across name-equivalent states under frequency-adaptive decay. Third, continuous STIBP scores replace binary entity-match seeds in localized Personalized PageRank (PPR). We characterize the condition under which this prior assigns more PPR mass to ground-truth evidence than a binary prior. Under the reported protocol, STITCH-RAG attains the highest reported Contain-Acc and LLM-Acc point estimates among the compared methods on HotpotQA and 2WikiMultiHopQA, and higher Recall@8 than the methods included in the standardized retrieval comparison. Results on the mixed-domain benchmark remain auxiliary preference-based evidence because only LLM-judged accuracy is available.
1 Introduction
Existing retrieval representations can lose cross-passage connections or fail to preserve both topic context and local entity states. STITCH-RAG couples a semi-merged topic hypergraph, influence bridging, and continuous-prior PPR; under the reported protocol, it achieves the highest reported accuracy point estimates on the named benchmarks.
Motivation
- Chunk-based RAG can miss evidence chains across chunk or document boundaries, while the scoped unlabeled pairwise and full-merge representations fail to retain both topic provenance and chunk-specific entity roles.The passage explicitly excludes pairwise graphs augmented with relation labels, provenance, event identifiers, or equivalent higher-order attributes from this limitation.Source: §1 · p. 1
Approach
- STITCH-RAG preserves topic-level co-participation as hyperedges and chunk-specific entity states as separate nodes linked by normalized canonical-name equivalence.The name-equivalence link is a heuristic, not a ground-truth entity linker; across documents, temporal proximity means deterministic index proximity rather than chronology.Source: §1 · p. 1
Results
- STITCH-RAG attains the highest reported Contain-Acc and LLM-Acc point estimates on HotpotQA, 2WikiMultiHopQA, and Mix; Recall@8 comparisons cover only methods with standardized retrieval outputs.LLM-judged metrics are auxiliary, and Mix results are not specified in this passage as a standardized Recall@8 comparison.Source: §1 · p. 2
Contributions and scope
- Its contributions couple this representation with frequency-adaptive STIBP and a continuous chunk prior for localized PPR, alongside conditional characterizations of recoverability and evidence mass.The paper states that these theoretical characterizations clarify design assumptions but do not guarantee end-to-end superiority.Source: §1 · p. 2
2 Related Work
The related-work discussion distinguishes STITCH-RAG by the properties its retrieval pipeline couples, while locating it among graph-based, hypergraph-based, and complementary retrieval approaches.
Graph-based RAG
- Graph-based methods use varied index structures, while STITCH-RAG couples topic identity, linked local entity states, and graded influence as a PPR prior.The paper’s comparison is scoped to published representations considered and excludes provenance-enriched pairwise graphs from its projection limitation.Source: §2 · p. 2
Hypergraph-based RAG
- Hypergraph RAG methods use relational, thematic, or causal hyperedges; STITCH-RAG uses semi-merging and propagates only within the activated subgraph.The controlled constructions distinguish full merging, which removes local states, from no merging, which removes ϕ.Source: §2 · p. 2
Complementary directions
- Adaptive routing, long-context retrieval, and granularity selection are presented as complementary design choices, while STITCH-RAG targets boundary fragmentation in large or dynamic knowledge bases.The paper notes that one-time indexing can be amortized across repeated queries in that setting.Source: §2 · p. 2
3 Method
STITCH-RAG compresses documents into a semi-merged topic hypergraph, then uses query-conditioned influence bridging and localized PPR to rank chunks. Its method preserves topic and local-state structure while making cross-chunk linkage and scoring choices explicit.
3.1 Overview and Design Rationale
- The pipeline converts documents into a semi-merged topic hypergraph, applies STIBP to identify relevant entity-state pathways, and diffuses continuous scores over a chunk graph with localized approximate PPR.The framework then retrieves top-k chunks for answer generation.Source: §3.1 · p. 2, Figure 2 · p. 3
3.2 Hypergraph Construction Phase
- Semi-merging retains each entity’s canonical name and chunk-specific description, while ϕ links identical normalized names and ψ records local context.Each extracted topic-summary hyperedge preserves its generating-topic identity; a provenance-free pairwise projection cannot in general reproduce topic-selective propagation.Source: §3.2 · p. 3, Structural Advantage over Pairwise… · p. 3
- For the controlled constructions, only semi-merging retains both name-equivalence links and local descriptions needed by the stated state-specific propagation rule.In the specified case, no-merge gives the evidence state no temporal influence, full-merge cannot assign it state-specific influence, and semi-merge gives it strictly positive temporal influence.Source: Recoverability Benefit of Semi-Merging · pp. 3–4
3.3 Retrieval Phase
- Retrieval activates nodes and topic hyperedges by dense similarity, propagates influence through spatial and temporal channels, projects scores onto chunks, and runs localized PPR with that prior.Spatial updates require source activation and topic relevance; temporal updates link name-equivalent states using deterministic preprocessing-index distance and frequency-adaptive decay.Source: §3.3 · p. 4, Spatio-Temporal Influence Bridging… · p. 4
- The temporal decay retains nonzero mass for distant states but attenuates frequent-name links more strongly, while the per-source bound assumes signal–noise separation and is not an end-to-end retrieval guarantee.The bound excludes final max aggregation and permits over-suppression of distant relevant states.Source: Spatio-Temporal Influence Bridging… · p. 4, Per-Source Analysis of… · p. 4
- STIBP scores form a normalized continuous chunk prior for PPR; the sufficient alignment condition for assigning more evidence mass than a binary prior is not independently verified.The diagnostic lacks measurements of reachability, seed coverage, empty matches, and prior-support size.Source: Chunk Score Projection and Localized… · pp. 4–5
4 Experiments
The experiments evaluate answer accuracy, answer quality beyond correctness, module-level causality, and computational efficiency. HotpotQA and 2Wiki use fixed sampled questions, while Mix is an exploratory cross-domain evaluation.
4.1 Experimental Setup
- HotpotQA and 2Wiki use fixed stratified samples of 1,000 questions; the 512-question Mix evaluation is exploratory and lacks supporting-fact annotations.Contain-Acc, EM, and Recall@8 are primary objective evidence for HotpotQA and 2Wiki; LLM-Acc and pairwise quality judgments are auxiliary preference-based evaluations.Source: Datasets · p. 5, Metrics · p. 5
4.2 Generation Accuracy (RQ1)
- STITCH-RAG ranks first in Contain-Acc and LLM-Acc on every dataset; Recall@8 exceeds LinearRAG by 7.5 points on HotpotQA and 5.7 on 2Wiki.The reported Contain-Acc/LLM-Acc margins over the strongest per-dataset baseline are 3.9/0.8 points on HotpotQA and 5.6/1.1 on 2Wiki.Source: §4.2 · p. 5, Table 1 · p. 6, Table 2 · p. 6
4.3 Answer Quality Comparison (RQ2)
- STITCH-RAG exceeds the 50% win-rate line on most dataset–dimension pairs, with its largest comprehensiveness and diversity margins on HotpotQA and 2Wiki.The comparison includes only methods with publicly available retrieval outputs under the standardized embedding protocol; LightRAG remains competitive on selected Mix dimensions.Source: §4.3 · pp. 5–6
4.4 Ablation Study (RQ3)
- Removing STIBP/PPR lowers LLM-Acc by 7.2/7.0 points on HotpotQA and 15.4/6.8 on 2Wiki; adaptive decay reaches 0.884 on Mix versus 0.853 and 0.846.The tested hyperparameters δ = 0.5, λ = 0.3, and k = 8 were selected on HotpotQA development data and transferred unchanged to 2Wiki and Mix.Source: §4.4 · p. 6, Hyperparameter Sensitivity Analysis · p. 6
4.5 Efficiency Analysis (RQ4)
- Table 4 pairs STITCH-RAG’s top Mix LLM-Acc with the second-lowest structural-retrieval latency; its added cost is one-time indexing, with no query-time LLM calls.Query-stage tokens include answer generation and method-specific query-time LLM calls under identical hardware and API conditions.Source: §4.5 · p. 6
5 Conclusion
STITCH-RAG couples topic-preserving hyperedges and local entity states with frequency-adaptive STIBP and continuous-prior PPR. Its reported benchmark results are point-estimate comparisons, with stated limitations and no end-to-end optimality guarantee.
5 Conclusion
- The proposed pipeline couples topic-preserving hyperedges, semi-merged local entity states, frequency-adaptive STIBP, and continuous-prior PPR; its mechanism results are not end-to-end optimality guarantees.Proposition 1 is limited to provenance-discarding pairwise inputs, while Proposition 2 compares three controlled merge constructions.Source: §5 · p. 6
- Under the reported protocol, STITCH-RAG has the highest Contain-Acc and LLM-Acc point estimates in Table 1 and the highest Recall@8 in Table 2.The merge and binary diagnostics remain inconclusive; 2Wiki EM is below LinearRAG, and the merge comparison does not establish a compression–relevance optimum.Source: §5 · p. 6
- Limitations include extraction and exact-name-linking errors, preprocessing-order-sensitive index proximity, unmeasured baseline variance, same-family Mix judging, and roughly 15M-token Mix indexing cost.Future work includes robust entity linking, order-insensitive propagation, adaptive routing, incremental indexing, and multimodal topic hyperedges.Source: §5 · pp. 6–7
Reproducibility Checklist
The checklist reports formal theoretical claims and dataset documentation, alongside several incomplete reproducibility and statistical-reporting items.
Reproducibility Checklist
- The checklist says the paper includes a conceptual outline or pseudocode, separates speculation from objective results, and provides pedagogical references.Source: Reproducibility Checklist · p. 9
- The checklist marks theoretical assumptions, formal claims, proofs, proof sketches, citations, and code as present, but empirical demonstration of all theoretical claims as partial.Source: Reproducibility Checklist · p. 9
- The checklist reports dataset motivation, dataset documentation and availability, and hyperparameter ranges and selection criteria as addressed.Source: Reproducibility Checklist · p. 9
- The checklist says preprocessing and experiment-analysis code are not included, run counts and significance tests are unreported, and computing infrastructure is only partially specified.It also reports that source code will be made publicly available and that distributional information is analyzed.Source: Reproducibility Checklist · p. 9
A Reproducibility and Implementation Details
The appendix describes how chunk-level extraction builds the semi-merged hypergraph, analyzes indexing and retrieval costs, and qualifies the interpretation of semi-merging. It also documents baseline reproduction checks and the materials provided for verification.
A Reproducibility and Implementation Details
- Baseline reproduction metrics fell within 1.5 percentage points of reported values, and frozen code, Docker images, outputs, and verification logs are provided.The remaining deviations may reflect API-version or random-seed differences.Source: A Reproducibility and Implementation… · p. 10
- Each chunk is independently split into coherent topic segments, represented by summary hyperedges and entity-state nodes with chunk-grounded descriptions.Entity boundaries follow maximal noun phrases, and repeated entities receive role-specific local descriptions.Source: A Reproducibility and Implementation… · p. 10
B.1 Complexity Analysis
- Indexing stores O(M) incidence links, while localized PPR costs O(T|Bq|); candidate-generation cost remains corpus-dependent.The analysis excludes LLM inference and embedding execution from symbolic complexities; measured latency is reported separately in Table 4.Source: §B.1 · pp. 10–11
B.2 Qualitative Compression–Context Interpretation of Semi-Merging
- Semi-merging retains distinct local entity states while exposing operational name equivalence, but the paper does not measure compression or retained task information.Table 8 is an answer-level controlled comparison, not an information-bottleneck result.Source: §B.2 · p. 12
B.3 Complete Hyperparameter Sensitivity Results
The sensitivity appendix reports post-hoc Mix sweeps for δ and λ, plus a top-k sweep on a HotpotQA development subset. The supplied passages describe the sweep settings but not their results.
B.3 Complete Hyperparameter Sensitivity Results
- Tables 5 and 6 examine post-hoc Mix LLM-Acc sensitivity to δ and λ, with the bold settings preselected on HotpotQA rather than Mix.Other hyperparameters are fixed in each sweep.Source: §B.3 · p. 12, Table 5 · p. 12, Table 6 · p. 12
- Table 7 varies top-k on a 200-question HotpotQA development set, with other hyperparameters fixed at their defaults.The bold column marks the selected value.Source: §B.3 · p. 12, Table 7 · p. 12
C Additional Experimental Results
The appendix points to additional phase-level ablation, pairwise answer-quality, merge-strategy, and temporal-decay comparisons. The supplied table captions identify the merge and decay comparison scopes but provide no outcome values.
C Additional Experimental Results
- The appendix includes a phase-level ablation visualization and a pairwise answer-quality comparison.The supplied passages do not state their outcomes.Source: C Additional Experimental Results · p. 12
- Table 8 compares LLM-Acc point estimates for one implementation of each merge strategy under a fixed retrieval pipeline.The diagnostic does not assess run-level variance, retrieval recall, compression, statistical significance, or all possible implementations.Source: Table 8 · p. 12
- Table 9 compares three temporal decay functions on Mix while holding the hypergraph, PPR initialization, and α = nu/¯n fixed.The caption supplies comparison conditions but no results.Source: Table 9 · p. 12
D Proofs of Main Results
The proofs establish that topic hyperedges preserve query-selective propagation that an unlabeled pairwise projection cannot recover, and that semi-merging uniquely retains both local entity descriptions and name-equivalence links among the controlled constructions. They also give a sufficient condition for STIBP initialization to increase PPR evidence mass and delimit the scope of the related-work comparisons.
D Proofs of Main Results
- Identical pairwise projections can yield different topic-selective propagation: H1 gives b and c influence but not d, while H2 cannot reproduce that outcome.Thus, retrieval based only on the unlabeled projection cannot in general reproduce propagation over the original hypergraph.Source: D Proofs of Main Results · p. 13
- Semi-merging alone retains both per-chunk descriptions for state-specific activation and name-equivalence links for temporal bridging.No-merging lacks cross-chunk linkage; full-merging discards local descriptions and either spreads influence across mentions or suppresses it.Source: D Proofs of Main Results · pp. 13–14
- With the sets and constants fixed, the sufficient signal-to-noise bound is non-decreasing in the frequency-adaptive rate α.The proof does not compare realized ratios across name-equivalence groups of different sizes.Source: D Proofs of Main Results · p. 14
- STIBP assigns more PPR mass to ground-truth evidence when its prior favors chunks with high discounted reachability to that evidence over the binary prior.The aggregate ablation is consistent with this condition, but does not establish alignment for every query.Source: D Proofs of Main Results · p. 15
E Extended Related Work
- The extended related-work comparison concerns published representations and algorithms, not provenance-enriched variants beyond those specifications.It compares what the evaluated inputs retain about multi-entity topics and local entity states.Source: E Extended Related Work · p. 15
E.1 Representing Topic Provenance and Local Entity State
- An unlabeled pairwise projection cannot recover which n-ary topic generated a pair, while LinearRAG’s published index does not expose STITCH-RAG’s chunk-specific states.STITCH-RAG fixes its chunking policy rather than determining the optimal chunk size.Source: §E.1 · p. 15
E.2 Initializing and Controlling Graph Propagation
STITCH-RAG replaces binary entity-match seeds with continuous STIBP priors derived from local entity states, topic hyperedges, and name-equivalent neighbors. Against LinearRAG, it reports higher Contain-Acc and Recall@8 on HotpotQA and 2Wiki, while aggregate margins do not isolate the effects of its coupled design changes.
E.2 Initializing and Controlling Graph Propagation
- STIBP derives a continuous prior from query similarity of local entity states, their topic hyperedges, and name-equivalent neighbors, instead of binary seeds.The compared HippoRAG and HippoRAG2 entity-match priors seed every matched entity and assign zero to unmatched entities.Source: §E.2 · p. 15
- STITCH-RAG uses no path enumeration or query-time LLM call; STIBP scores activated hypergraph structures before PPR runs on the induced chunk graph.Table 4 reports combined retrieval latency, not the isolated cost of localization.Source: §E.2 · p. 16
- 15.5 points on HotpotQA and 6.7 on 2Wiki are STITCH-RAG’s Contain-Acc gains over LinearRAG; Recall@8 gains are 7.5 and 5.7 points, respectively.These aggregate margins do not separate representation, initialization, and localization effects.Source: §E.2 · p. 16
- STITCH-RAG assumes repeated queries amortize its one-time hypergraph construction cost.The passage places this deployment assumption in a comparison of retrieval with knowledge internalization.Source: §E.2 · p. 16