English · Español

Lab 02 — Baseline BM25 + híbrido RRF

BM25 es búsqueda léxica clásica: pondera palabras por TF-IDF, normaliza por longitud, devuelve un ranking. Es la otra cara del bi-encoder. Si combinas ambos con Reciprocal Rank Fusion, el ranking conjunto suele superar a cada uno por separado. Este lab construye los dos sistemas y prueba la hipótesis.

Objetivo

Implementar BM25 sobre la KB de reglas de gramática, evaluarlo en solitario, y luego fusionarlo con el retriever denso del Lab 01 usando Reciprocal Rank Fusion (RRF). Demostrar que el híbrido le gana a ambos retrievers por separado por ≥ 5pp en hit@5.

Setup

• Lab 01 hecho (retriever denso en src/minirag/retrieve.py; eval set con 30 consultas).
• Python puro; sin librería externa de BM25 (lo implementamos para entenderlo).
• theory/03-hybrid-search-and-reranking.md cubre la matemática.

La fórmula BM25

Para una query \(q = \{q_1, q_2, ..., q_n\}\) y un documento \(D\):

\[\text{BM25}(q, D) = \sum_{i=1}^n \text{IDF}(q_i) \cdot \frac{f(q_i, D)(k_1 + 1)}{f(q_i, D) + k_1 (1 - b + b \cdot |D| / \text{avgdl})}\]

Donde:

• \(f(q_i, D)\) = frecuencia del término \(q_i\) en \(D\).
• \(|D|\) = longitud del documento en tokens.
• \(\text{avgdl}\) = longitud media de documento en el corpus.
• \(\text{IDF}(q_i) = \log\left( \frac{N - \text{df}(q_i) + 0.5}{\text{df}(q_i) + 0.5} + 1 \right)\) donde \(N\) = tamaño del corpus, \(\text{df}(q_i)\) = frecuencia documental.
• \(k_1 = 1.5\), \(b = 0.75\) — valores por defecto estándar.

La intuición: las palabras comunes en este documento pero raras en el corpus contribuyen más; los documentos largos se penalizan ligeramente.

Tareas

Parte A — Implementar src/minirag/bm25.py

import math
import re
from collections import Counter
from dataclasses import dataclass

@dataclass
class BM25:
    chunk_ids: list[str]
    tokens_per_doc: list[list[str]]
    avgdl: float
    df: Counter         # term → number of docs containing it
    N: int              # corpus size
    k1: float = 1.5
    b: float = 0.75

    @classmethod
    def from_chunks(cls, chunks) -> "BM25":
        ids = []
        tokens_per_doc = []
        df = Counter()
        for c in chunks:
            ids.append(c.chunk_id)
            t = tokenize(c.title + " " + c.body)
            tokens_per_doc.append(t)
            for term in set(t):
                df[term] += 1
        avgdl = sum(len(t) for t in tokens_per_doc) / len(tokens_per_doc)
        return cls(ids, tokens_per_doc, avgdl, df, N=len(ids))

    def idf(self, term: str) -> float:
        return math.log((self.N - self.df[term] + 0.5)
                        / (self.df[term] + 0.5) + 1.0)

    def score(self, query_tokens: list[str], doc_idx: int) -> float:
        doc = self.tokens_per_doc[doc_idx]
        doc_len = len(doc)
        tf = Counter(doc)
        s = 0.0
        for q in query_tokens:
            if q not in self.df:
                continue
            num = tf[q] * (self.k1 + 1)
            den = tf[q] + self.k1 * (1 - self.b + self.b * doc_len / self.avgdl)
            s += self.idf(q) * (num / den)
        return s

    def search(self, query: str, k: int = 5) -> list[tuple[str, float]]:
        q = tokenize(query)
        scores = [(self.chunk_ids[i], self.score(q, i)) for i in range(self.N)]
        scores.sort(key=lambda x: -x[1])
        return scores[:k]


TOKEN_RE = re.compile(r"\w+", re.UNICODE)

def tokenize(text: str) -> list[str]:
    return [t.lower() for t in TOKEN_RE.findall(text)]

Notas:

• Sin stemming en la Fase 29 — la KB es suficientemente pequeña como para que la coincidencia exacta de forma sea aceptable. Stretch: stemmer español.
• Sin eliminación de stop-words por la misma razón. Stretch: probar stop-words en español.
• La regex de token coincide con alfanuméricos incluidos caracteres acentuados (re.UNICODE).

Parte B — Evaluar BM25 en solitario

Reutiliza la función evaluate del Lab 01 con BM25Retriever envolviendo la clase BM25:

class BM25Retriever:
    def __init__(self, kb_path):
        from .chunk import load_chunks
        chunks = load_chunks(kb_path)
        self.bm25 = BM25.from_chunks(chunks)
    def search(self, query, k=5):
        return self.bm25.search(query, k)

Esperado: el hit@5 de BM25 solo cae en algún punto de [0.40, 0.65]. Fuerte en consultas con coincidencia de keywords; débil en consultas parafraseadas / cross-language.

Parte C — Implementar RRF en src/minirag/retrieve.py

def reciprocal_rank_fusion(results_a: list[tuple[str, float]],
                           results_b: list[tuple[str, float]],
                           k_rrf: int = 60,
                           top_k: int = 5) -> list[tuple[str, float]]:
    """Fuse two ranked lists. RRF score = sum 1 / (k_rrf + rank).
    Scores from A and B are NOT used — only ranks."""
    score = {}
    for rank, (cid, _) in enumerate(results_a, start=1):
        score[cid] = score.get(cid, 0) + 1.0 / (k_rrf + rank)
    for rank, (cid, _) in enumerate(results_b, start=1):
        score[cid] = score.get(cid, 0) + 1.0 / (k_rrf + rank)
    fused = sorted(score.items(), key=lambda x: -x[1])
    return fused[:top_k]


class HybridRetriever:
    def __init__(self, dense, bm25, k_rrf: int = 60):
        self.dense = dense
        self.bm25 = bm25
        self.k_rrf = k_rrf
    def search(self, query: str, k: int = 5) -> list[tuple[str, float]]:
        n = max(k, 20)
        ra = self.dense.search(query, k=n)
        rb = self.bm25.search(query, k=n)
        return reciprocal_rank_fusion(ra, rb, k_rrf=self.k_rrf, top_k=k)

El valor por defecto k_rrf=60 es el estándar del paper de RRF (Cormack 2009). Prueba otros valores en la sección de stretch.

Parte D — Comparar tres retrievers

Ejecuta evaluate del Lab 01 sobre los tres:

results = {
    "dense": evaluate(DenseRetriever(...), queries),
    "bm25":  evaluate(BM25Retriever(...),  queries),
    "hybrid":evaluate(HybridRetriever(...),queries),
}

Produce una tabla comparativa:

Retriever	hit@1	hit@3	hit@5	MRR
Dense (Lab 01)	0.42	0.58	0.67	0.52
BM25	0.38	0.55	0.60	0.48
Hybrid (RRF, k=60)	0.50	0.70	0.78	0.61

Esperado: el híbrido le gana a ambos en solitario en hit@5 por ≥ 5pp. Si no lo hace, depura:

• ¿Están produciendo denso y BM25 top-5s solapados para la mayoría de las consultas? Si es así, RRF no puede añadir diversidad.
• ¿Están los rankings densos dominados por un pequeño conjunto de chunks "siempre arriba"? Comprueba el CSV por consulta.
• ¿Es el parámetro k_rrf demasiado bajo (sobre-pondera el top-1) o demasiado alto (todo parece igual)?

Parte E — Desgloses por idioma y por dificultad

Corta el eval set por:

• Idioma (consulta EN / consulta ES / cross): ¿le gana denso a BM25 en cross-language? (Debería — los embeddings densos puentean idiomas.)
• Dificultad (verbatim-keyword / parafraseada): ¿domina BM25 en verbatim? ¿Domina denso en parafraseada? ¿Promedia el híbrido entre ellos con elegancia?

Reporta esto en experiments/29-bm25-hybrid/SLICED_REPORT.md.

Parte F — Tests en tests/minirag/test_bm25.py

1. test_tokenize_accented — tokenize("ÉL trabajó") devuelve ["él", "trabajó"] (minúsculas, acento preservado).
2. test_bm25_keyword_hit — dados 3 docs y una query con una keyword presente en 1 doc, ese doc rankea primero.
3. test_bm25_idf_rare_wins — dada una query con 2 palabras, una rara (en 1 doc) y otra común (en los 3), gana el doc con la palabra rara.
4. test_rrf_fusion_combines — dadas dos listas rankeadas donde el doc A está en rango 2 en ambas, y el doc B está en rango 1 solo en una, el score RRF de A supera al de B.
5. test_hybrid_beats_alone_on_eval — sobre un eval sintético pequeño, hit@5 del híbrido ≥ max(dense, bm25) hit@5.

Entregables

experiments/29-bm25-hybrid/: - REPORT.md — la tabla comparativa a 3 bandas + interpretación. - SLICED_REPORT.md — desgloses por idioma y por dificultad. - metrics.json — números agregados de los tres retrievers. - per_query.csv — tres columnas de resultados (dense, bm25, hybrid) por consulta. - manifest.json.

Aceptación

• Pasan los 5 tests.
• Hit@5 del híbrido ≥ max(dense, bm25) hit@5 + 5pp.
• El análisis por slices muestra el patrón predicho: dense > BM25 en parafraseado, BM25 ≥ dense en verbatim, hybrid ≥ ambos en la mayoría de slices.
• Si el híbrido NO gana por 5pp, el informe contiene un análisis de depuración que explica por qué (p. ej., "BM25 y denso están muy correlacionados en esta KB pequeña").

Trampas

• Mismatch de tokenización entre BM25 y el embedder denso. BM25 usa tu función tokenize; el embedder usa su propio tokenizer. Se supone que difieren — BM25 es léxico, denso es semántico. No intentes unificarlos.
• Incluir metadatos del chunk en el texto BM25. Si tokenizas el objeto JSON (p. ej., nombres de campo como "language"), todos los chunks tienen esas palabras y el IDF de BM25 queda destruido. Tokeniza solo title + body.
• El score RRF demasiado sensible a k_rrf. El default 60 es robusto. Si bajas a 5, el top-1 domina. Si subes a 1000, todo es igual.
• Híbrido peor que solo. Si ves esto, o bien denso y BM25 apuntan a respuestas erróneas distintas (combinarlos esparce la masa), o un retriever aporta puro ruido. Diagnóstico con el CSV por consulta.
• Stop-words españolas contando como contenido. Palabras como de, el, la, que están en todas las consultas en español; sin eliminación de stop-words, el IDF de BM25 las pondera a la baja pero aun así contaminan ligeramente el score. Aceptable a N=50.

Stretch

• Añade stemming en español (Snowball) al tokenizer de BM25. Mide el cambio de hit-rate por idioma.
• Prueba distintos valores de k_rrf (5, 20, 60, 200). Dibuja hit@5 vs k_rrf.
• Implementa una fusión alternativa: combinación lineal de scores normalizados. Compara con RRF.
• Añade un cross-encoder re-ranker (teoría 03) sobre el top-20 del híbrido. Mide la mejora.

---

Siguiente lab: lab/03-end-to-end-rag.md.