# Graph Centrality & TF-IDF Vectorization for In-Context Redundancy Reduction

> Mathematical Derivation of LexRank Stationary Distributions and Priority Tier Filtering

By Yashvardhan Thanvi (LLMSlim Author & Core Maintainer) · Published July 15, 2026 · Updated July 15, 2026 · Algorithms

## Abstract

A formal mathematical and algorithmic breakdown of how graph centrality over TF-IDF term matrices ranks and prunes redundant sentences in long context prompts while safeguarding imperative instructions.

## Intuition

Computes sentence importance via the stationary probability distribution vector p^T = p^T M over a damped Markov transition matrix derived from pairwise TF-IDF cosine similarities.

## 1. Vector Space Modeling & TF-IDF Weighting

Prompt compression aims to select a subset of sentences $S' \subset S$ from a document $D = (s_1, s_2, \dots, s_N)$ that minimizes total token count while maximizing retained semantic information.

Each sentence $s_i$ is mapped to a sparse TF-IDF vector $\mathbf{v}_i \in \mathbb{R}^{|V|}$ over vocabulary $V$:

$$\text{TF}(t, s_i) = \frac{f_{t, s_i}}{\sum_{t' \in s_i} f_{t', s_i}}$$

$$\text{IDF}(t, D) = \log \left( \frac{1 + N}{1 + |\{s \in D : t \in s\}|} \right) + 1$$

$$\mathbf{v}_{i, t} = \text{TF}(t, s_i) \times \text{IDF}(t, D)$$

```math
W_{ij} = \frac{\mathbf{v}_i \cdot \mathbf{v}_j}{\|\mathbf{v}_i\| \|\mathbf{v}_j\|}
```

## 2. Graph Construction & Stationary Distribution Derivation

A similarity graph $G = (V_G, E_G)$ is formed where vertices $V_G = \{s_1, \dots, s_N\}$. Edges exist between sentences where cosine similarity $W_{ij} \ge \theta$ (threshold $\theta = 0.1$).

The stochastic transition matrix $\mathbf{M} \in \mathbb{R}^{N \times N}$ is formulated with a damping factor $d = 0.85$:

$$\mathbf{M} = d \mathbf{B} + \frac{1 - d}{N} \mathbf{1}_{N \times N}$$

where $B_{ij} = \frac{W_{ij}}{\sum_{k} W_{ik}}$.

The stationary probability vector $\mathbf{p}$ is solved using power iteration until convergence:

$$\mathbf{p}^{(k+1)} = \mathbf{M}^T \mathbf{p}^{(k)}$$

```python
import numpy as np
from sklearn.feature_extraction.text import TfidfVectorizer

def compute_sentence_centrality(sentences: list[str], threshold: float = 0.1, damping: float = 0.85) -> np.ndarray:
    """Computes LexRank stationary probability distribution vector over sentence TF-IDF cosine matrix."""
    vectorizer = TfidfVectorizer(stop_words='english')
    tfidf = vectorizer.fit_transform(sentences)
    
    # Compute pairwise similarity matrix
    sim_matrix = (tfidf * tfidf.T).toarray()
    n = len(sentences)
    
    # Apply similarity threshold
    adj = np.where(sim_matrix >= threshold, sim_matrix, 0.0)
    row_sums = adj.sum(axis=1, keepdims=True)
    row_sums[row_sums == 0] = 1.0
    
    # Stochastic matrix formulation
    b_matrix = adj / row_sums
    m_matrix = damping * b_matrix + ((1.0 - damping) / n) * np.ones((n, n))
    
    # Power iteration
    p = np.ones(n) / n
    for _ in range(50):
        next_p = m_matrix.T @ p
        if np.linalg.norm(next_p - p) < 1e-6:
            break
        p = next_p
    return p
```

## 3. Priority Tier Rule Layer

Statistical centrality alone cannot distinguish an essential imperative instruction (e.g., "Must return valid JSON") from background prose. 

LLMSlim integrates a deterministic priority map $f: s_i \mapsto \{1, 2, 3, 4\}$ evaluated prior to token selection:
- **Tier 4 (Locked Directive)**: System role definitions, imperative constraint words (`must`, `never`, `always`), code fences (````).
- **Tier 3 (Entity Protection - High Priority)**: Sentences containing proper nouns, numbers, currency symbols, and technical identifiers.
- **Tier 2 (Informative Prose)**: Sentences ranked strictly by LexRank probability $p_i$.
- **Tier 1 (Redundant Padding)**: Sentences below similarity cutoff.

## Key takeaways

- TF-IDF vector space modeling measures local term specificity across sentence boundaries.
- LexRank graph centrality constructs a stochastic transition matrix to identify central informational nodes.
- Priority Tier Shields explicitly override statistical pruning for critical directives, code syntax, and structural schemas.

## References

- [Erkan & Radev (2004)] [LexRank: Graph-based Lexical Centrality as Salience in Text Summarization (Journal of Artificial Intelligence Research)](https://arxiv.org/abs/1109.2128)
- [Salton & Buckley (1988)] [Term-weighting approaches in automatic text retrieval (Information Processing & Management)](https://doi.org/10.1016/0306-4573(88)90021-0)

Canonical page: https://www.llmslim.app/articles/how-prompt-compression-works