Deep Dive: Knowledge Graph & Hybrid Search

Before writing wiki pages, extract all entities from this source.

For each entity found, list:
- Name: (exact name, consistent with existing wiki)
- Type: Concept | Person | Project | Library | Decision | Event
- Key attributes: (3-5 most important facts)
- Relationships to other entities: (type: name)

Format:
```
Entity: Attention Mechanism
Type: Concept
Attributes:
  - Scaled dot-product of Query, Key, Value vectors
  - Computational complexity: O(n²) in sequence length
  - Enables direct dependency between any two positions
Relationships:
  - part_of: Transformer Architecture
  - enables: Long-range dependency modeling
  - variant_of: [none — this IS the base]
  - used_by: BERT, GPT series
```

Wait for my confirmation before creating pages.

# BERT
**Type**: Project
**Confidence**: 0.90

## Relationships
- **depends_on**: [[transformer-architecture]] — uses encoder-only stack
- **uses**: [[masked-language-modeling]] — core pre-training objective
- **uses**: [[next-sentence-prediction]] — secondary pre-training task
- **evolved_from**: [[elmo]] — BERT replaced ELMo as SOTA on NLP benchmarks
- **superseded_by**: [[roberta]] — same arch, better training (no NSP)
- **enables**: [[transfer-learning-nlp]] — fine-tune on downstream tasks
- **contradicts**: [[gpt-architecture]] — bidirectional vs autoregressive
- **part_of**: [[pre-training-paradigm]] — foundational to modern LLMs

Use graph traversal to answer: "What would be impacted if we deprecated the attention mechanism?"

Start at entity: [[attention-mechanism]]
Walk outward via edges: used_by, depends_on, enables

For each entity encountered:
- Note it
- Walk its outward edges (max depth: 3)

Return a dependency tree showing all impacted entities.
Format as nested list with relationship type on each edge.

import math
from collections import Counter

def bm25_score(query_terms: list, doc: str, corpus: list,
               k1: float = 1.5, b: float = 0.75) -> float:
    """
    BM25: term frequency với length normalization.
    k1 = term frequency saturation (default 1.5)
    b  = length normalization (default 0.75)
    """
    doc_terms = doc.lower().split()
    doc_len = len(doc_terms)
    avg_len = sum(len(d.split()) for d in corpus) / len(corpus)
    tf = Counter(doc_terms)
    N = len(corpus)

    score = 0
    for term in query_terms:
        # Inverse document frequency
        n_docs_with_term = sum(1 for d in corpus if term in d.lower())
        idf = math.log((N - n_docs_with_term + 0.5) / (n_docs_with_term + 0.5) + 1)

        # Term frequency with saturation + length normalization
        tf_term = tf.get(term, 0)
        tf_norm = (tf_term * (k1 + 1)) / (tf_term + k1 * (1 - b + b * doc_len / avg_len))

        score += idf * tf_norm

    return score

# Practical: use rank-bm25 or whoosh library

from rank_bm25 import BM25Okapi
import glob, os

def build_wiki_bm25_index(wiki_dir: str):
    pages = []
    for filepath in glob.glob(f"{wiki_dir}/**/*.md", recursive=True):
        with open(filepath) as f:
            content = f.read()
        pages.append({
            "path": filepath,
            "content": content,
            "tokens": content.lower().split()
        })

    tokenized_corpus = [p["tokens"] for p in pages]
    bm25 = BM25Okapi(tokenized_corpus)
    return bm25, pages

def search_bm25(query: str, bm25, pages, top_k=10):
    query_tokens = query.lower().split()
    scores = bm25.get_scores(query_tokens)
    ranked = sorted(enumerate(scores), key=lambda x: x[1], reverse=True)
    return [(pages[i]["path"], score) for i, score in ranked[:top_k] if score > 0]

from sentence_transformers import SentenceTransformer
import numpy as np
import faiss

def build_wiki_vector_index(wiki_dir: str):
    model = SentenceTransformer('all-mpnet-base-v2')  # 768-dim, good quality/speed
    pages = []

    for filepath in glob.glob(f"{wiki_dir}/**/*.md", recursive=True):
        with open(filepath) as f:
            content = f.read()

        # Chunk by section (H2 headers)
        chunks = split_by_sections(content, max_tokens=512)
        for chunk in chunks:
            pages.append({"path": filepath, "content": chunk})

    contents = [p["content"] for p in pages]
    embeddings = model.encode(contents, show_progress_bar=True)

    # FAISS index for fast similarity search
    dim = embeddings.shape[1]
    index = faiss.IndexFlatIP(dim)  # Inner product (cosine after normalization)
    faiss.normalize_L2(embeddings)
    index.add(embeddings)

    return index, pages, model

def search_vector(query: str, index, pages, model, top_k=10):
    query_emb = model.encode([query])
    faiss.normalize_L2(query_emb)
    scores, indices = index.search(query_emb, top_k)
    return [(pages[i]["path"], float(scores[0][j]))
            for j, i in enumerate(indices[0]) if scores[0][j] > 0.3]

from collections import defaultdict

def reciprocal_rank_fusion(result_lists: list[list[str]], k: int = 60) -> list[str]:
    """
    RRF: fuse multiple ranked lists.
    k = smoothing constant (default 60, from original paper)

    Score(doc) = Σ 1 / (k + rank_in_list_i)
    """
    scores = defaultdict(float)

    for ranked_list in result_lists:
        for rank, doc_id in enumerate(ranked_list, start=1):
            scores[doc_id] += 1 / (k + rank)

    # Sort by fused score descending
    return sorted(scores, key=scores.get, reverse=True)

# Example usage:
bm25_results = ["doc_a", "doc_c", "doc_b", ...]      # BM25 ranked
vector_results = ["doc_b", "doc_a", "doc_d", ...]    # Vector ranked
graph_results = ["doc_e", "doc_a", "doc_c", ...]     # Graph ranked

fused = reciprocal_rank_fusion([bm25_results, vector_results, graph_results])
# Returns: ["doc_a", "doc_c", "doc_b", "doc_e", "doc_d", ...]