Skip to content

Tutorial PDF Summary

Jump to bottom
Chris Sweet edited this page Jul 10, 2026 · 2 revisions

type: source-summary up: "index_markov_chain_rag_tutorial" source: "tutorial-pdf" related: ["Markov-Retrieval-Tutorial", "README-Summary"] tags: [tutorial, writeup, primary-artifact]

Tutorial PDF Summary

Summary of docs/tutorial.pdf, the seven-page writeup that is the primary artifact of this repository.

Title and authorship

"Why retrieval over a graph beats retrieval over an embedding (and what this means for how we extract data)" by Chris Sweet, Center for Research Computing / Digital AI and Compute, University of Notre Dame.

Three claims the writeup makes

  1. The structural failure of vanilla RAG on tail data is real and identifiable in small, inspectable corpora. See Vanilla RAG Failure Mode.
  2. A heterogeneous graph plus a Markov chain over it produces structurally better rankings, modest in absolute magnitude on a small corpus but clear in their mechanism. See Random Walk With Restart and Heterogeneous Graph.
  3. The architecture's effectiveness is upper-bounded by the extraction that produced the graph. Extraction and retrieval are co-designed. See Extraction-Retrieval Co-Design.

Section map

Section Subject
1. The problem Vanilla RAG fails on tail vocabulary by construction, not because the encoder is bad
2. What this looks like in the data The 24-chunk synthetic corpus and the UMAP geometry of its embedding space
3. Where the missing structure lives Documents, chunks, and concepts form a graph the embedding space discards
4. Random walk with restart The Markov chain, its recursion, and the path-length decomposition
5. When this helps, when it doesn't, and what it costs Findings across five queries, including the DLA partial-bridge case
6. Extraction and retrieval are co-designed What the extractor captures determines what retrieval can later answer
7. Conclusion Restatement of the three claims and the next step (iScout-equivalent validation)

Headline numbers cited

These appear in the writeup and the code reproduces them. Changes to corpus or chain parameters that move them require updating the prose in docs/tutorial.tex.

Quantity Value
HoosierMetals overview chunk total stationary mass (DLA query) 0.0315
ITAMCO capabilities chunk total stationary mass (DLA query) 0.013
Queries where the chain produced clearly better rankings 3 of 5
Queries where chain and vanilla performed similarly 1 of 5
Queries where bridging was partial (the DLA query) 1 of 5

Figures referenced

Figure Subject
Figure 1 UMAP projection of chunks, concepts, and the "metal 3D printing in Indiana" query
Figure 2 Subgraph for the DLA query, showing the recovery path through HoosierMetals
Figure 3 Path-length decomposition contrasting HoosierMetals (recovered) against ITAMCO (not recovered)

See Tutorial Figures for where the figures live and how to regenerate them.

Honest limitations the writeup names

  1. The chain's biggest wins on this corpus are reordering wins, not pure recovery wins. Pure tail recovery happens but with modest magnitudes.
  2. The chain inherits encoder limitations. The DLA query brought up FoodCo at rank 5 because the encoder placed "cold chain logistics" near "Defense Logistics Agency" by surface word overlap.
  3. Costs are real. Concept extraction at indexing time is non-trivial, the chain is more expensive than nearest-neighbor lookup, and the transition matrix has parameters that need calibration against the query distribution.

See also

Clone this wiki locally