-
Notifications
You must be signed in to change notification settings - Fork 1
Markov Retrieval Tutorial
type: synthesis up: "Home_markov_chain_rag_tutorial" tags: [project-overview, retrieval, markov-chain] related: ["README-Summary", "Tutorial-PDF-Summary", "Extraction-Retrieval-Co-Design"]
A small, runnable demonstration of heterogeneous-graph retrieval using a Markov chain (random walk with restart) over a corpus of chunks, documents, and concepts.
This is a tutorial, not a deployed system. The corpus is intentionally small (24 chunks across 12 manufacturing entities, see Tutorial Corpus) so every behavior of the chain is inspectable. The primary artifact is docs/tutorial.pdf, a 7-page document explaining the architecture and demonstration; see Tutorial PDF Summary for its section map and headline numbers. The Python code reproduces every number and figure in the writeup.
The writeup makes three claims:
- Vanilla RAG fails on tail vocabulary by construction, not because the encoder is bad.
- A heterogeneous graph plus a Markov chain produces structurally better rankings, with the bridge entity as the canonical mechanism. See Tutorial Queries for the per-query findings.
- The architecture's effectiveness is upper-bounded by the extractor that produced the graph. See Extraction-Retrieval Co-Design.
A heterogeneous graph is built from a corpus of text chunks, the documents they belong to, and the concepts attached to them. Embeddings come from MiniLM for both chunk text and concept strings. A query seeds a random walk with restart on the graph, and the resulting stationary distribution ranks chunks, documents, and concepts by relevance. A path-length decomposition tells you how relevance arrived at any given node.
The repository declares three commitments as non-negotiable. They drive most design decisions and define what is in or out of scope.
- Open vocabulary over declared schema. Concepts are extracted from text and attached to chunks rather than declared by a formal ontology.
- Text fidelity. Chunks remain as nodes carrying the original prose. The chain runs on the text-bearing graph, not on a triple-extracted abstraction.
- Trajectory respect. Retrieval treats questions as having trajectories across the corpus. Path-length decomposition is a first-class diagnostic.
These flow from the broader Notre Dame DAC team's work on retrieval for scientific discovery. Discovery requires open vocabulary, text fidelity, and trajectory respect, and the chain on chunks-with-concepts is what these three jointly select.
Deployment infrastructure, GNN-based retrieval, agentic retrieval, two-stage scaling, and concept extraction from raw text. The tutorial corpus is too small to motivate any of these, and they belong in separate codebases.
The tutorial cites specific numbers (for example HoosierMetals' total mass at 0.0315, ITAMCO's at 0.013). If the corpus, graph construction, or chain parameters change, the figures regenerate and the prose in docs/tutorial.tex is updated to match. Honest reporting is preferred over tuning until results look good.
Note that the cited masses and ranks depend on the embeddings, so requirements.txt pins the sentence-transformers / transformers / torch stack to the versions used to generate the writeup. Installing the pinned requirements reproduces the numbers; relaxing the pins to newer versions changes the embeddings and can shift the exact masses and ranks.