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

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)$$

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)}$$

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.