Markov Chain RAG Tutorial

A small, runnable tutorial that demonstrates heterogeneous-graph retrieval using a Markov chain (random walk with restart) over a corpus of chunks, documents, and concepts. Embeddings come from all-MiniLM-L6-v2 for both chunk text and concept strings.

The corpus is intentionally tiny (12 manufacturing entities, 24 chunks) so that every behavior of the chain is inspectable. The primary artifact is docs/tutorial.pdf, a self-contained explanation of the architecture and the demonstration that reads on its own without running the code. The code in this repository reproduces every number and figure cited in the tutorial.

What it shows

Dense (nearest-neighbor) retrieval finds passages that lexically match the query. It fails on tail vocabulary: when the answer is written in a different register than the question, cosine similarity never reaches it. The Markov chain treats retrieval as a trajectory across a graph of chunks, documents, and extracted concepts. Seeding the walk from the query and diffusing with restart lets relevance cross a bridge entity into a cluster that similarity alone could not reach. A path-length decomposition shows exactly how much relevance arrived at each hop.

Setup

git clone https://github.com/crcresearch/markov_chain_rag_tutorial.git
cd markov_chain_rag_tutorial
uv venv
source .venv/bin/activate
uv pip install -r requirements.txt

First run downloads the MiniLM model (about 90MB) and caches it under ~/.cache/huggingface. Subsequent runs are offline.

Run

python run_tutorial.py

Layout

markov_chain_rag_tutorial/
  README.md            this file
  CLAUDE.md            guidance for AI coding assistants in this repo
  requirements.txt     pip dependencies
  corpus.py            the synthetic corpus (12 entities, 24 chunks)
  graph.py             heterogeneous graph construction
  markov.py            transition matrix, RWR, path decomposition
  figures.py           generates the three tutorial figures
  run_tutorial.py      main entry point
  figures/             figures regenerated by run_tutorial.py
  docs/
    tutorial.pdf       the tutorial document (the primary artifact)
    tutorial.tex       LaTeX source
    figures/           committed copies of the figures, used by tutorial.tex
  wiki/                LLM-maintained wiki (separate git repository)

Edit corpus.py to add or modify entities. Edit markov.py to change type weights or sparsification thresholds. Edit graph.py to change the embedding model.

What the output shows

For each query the script prints:

1. The vanilla baseline ranking (plain cosine query-chunk similarity)
2. The starting concepts and chunks selected for the random walk
3. The chain ranking (top chunks, top documents, top concepts by stationary mass)
4. For tail-test queries, a path-length decomposition for selected entities showing how much relevance arrived through paths of each length

After all queries run, the script generates three PDF figures into figures/ at the repository root:

• fig1_umap.pdf: 2D UMAP projection of chunk and concept embeddings, with one query overlaid as a red star. Shows the geometry of embedding space and how the query relates to entity clusters.
• fig2_graph_schematic.pdf: hand-laid-out subgraph for the DLA query, showing the recovery path through HoosierMetals (the bridge entity).
• fig3_path_decomposition.pdf: side-by-side bar charts contrasting one chunk that the chain successfully recovered against one it did not.

The same three figures are also committed under docs/figures/ so the tutorial PDF compiles without first running the code.

Building the writeup PDF

cd docs
pdflatex tutorial.tex
pdflatex tutorial.tex   # second pass for cross-references

The writeup uses \graphicspath{{figures/}}, so figures are loaded from docs/figures/.

Reproducibility note

The stationary masses and ranks cited in the writeup depend on the embeddings, which depend on the sentence-transformers / transformers / torch stack. requirements.txt pins those versions, and docs/tutorial.pdf and the committed figures were generated with them, so installing the pinned requirements reproduces the writeup's numbers. Relaxing the pins to newer versions changes the embeddings and can shift the exact masses and ranks; do so only if you do not need bit-for-bit agreement with the PDF.

This repository uses LLM wiki memory

Alongside the code, this project keeps a persistent, LLM-maintained knowledge base under wiki/markov_chain_rag_tutorial.wiki/ (a separate git repo), following the llm-wiki pattern. For this tutorial the wiki is the concept companion: it walks through the random walk with restart, the heterogeneous graph, path-length decomposition, the restart probability, the vanilla-RAG failure mode, and the bridge entity. Browse it at https://github.com/crcresearch/markov_chain_rag_tutorial/wiki.

Three operations, Query (read it), Ingest (write to it), and Lint (health-check it), are codified in CLAUDE.md, in wiki/markov_chain_rag_tutorial.wiki/SCHEMA_markov_chain_rag_tutorial.md, and in the .claude/commands/ slash commands (/wiki-source, /wiki-experiment, /wiki-lint). See also llm-wiki.md for the underlying pattern.

The wiki is a separate git repository, not pulled in by the main clone. To work with it locally alongside Claude Code:

[ -d wiki/markov_chain_rag_tutorial.wiki ] || \
    git clone https://github.com/crcresearch/markov_chain_rag_tutorial.wiki.git wiki/markov_chain_rag_tutorial.wiki
./wiki/agents/claude-code/setup.sh --seed-memory

After any wiki edit, commit in the wiki repo (not the project repo), and push only when you intend to publish:

git -C wiki/markov_chain_rag_tutorial.wiki add <files>
git -C wiki/markov_chain_rag_tutorial.wiki commit -m "..."
git -C wiki/markov_chain_rag_tutorial.wiki push origin master

About the template

This project was instantiated from crcresearch/llm-wiki-memory-template. Maintainers who need to pull template updates, add a new agent overlay (Cursor, OpenCode, etc.), or understand the instantiate/update scripts should read the template repo's documentation.