🧠 Logic & Algorithms

# 🧠 Logic & Algorithms This document explains **how** the screener works — what we index, how we score, and how decisions are made. (Updated to include **passage-level chunking** and **cross-encoder** re-ranking.) > The earlier logic overview is retained and expanded here. :contentReference[oaicite:2]{index=2} --- ## Overview 1. **Index time (CLI)** Parse each resume → PII mask → normalize → build 3 document-level signals (hash, lexical, semantic) → (optionally) build **chunk-level** semantic vectors → persist. 2. **Query time (API)** Parse upload → **exact-dup gate** → candidate search (document & chunk levels) → per-candidate scoring → **cross-encoder re-rank** on the top set → **decision** → (optional) evidence report. --- ## A. Parsing & Normalization - **Parsing:** PDFs via `pdfminer`, DOCX via `python-docx`. We keep `text` and a simple `layout`. - **PII masking:** `mask_pii_if_enabled(text)` to reduce false positives and make **hashing stable** across runs. - **Normalization:** lowercase, whitespace collapse, Unicode cleanup, and section/bullet extraction used for reporting. --- ## B. Signals & Indexes ### 1) Exact-duplicate hash (O(1)) Aggressive normalization → SHA-1 → perfect equality check for “effectively the same” resume. ```python import hashlib def normalized_hash(t: str) -> str: s = " ".join(t.lower().split()) return hashlib.sha1(s.encode("utf-8")).hexdigest() ``` We persist a **hash map**: `hash -> [doc_ids...]`. ### 2) Lexical fingerprint (MinHash + LSH) * Build MinHash signatures over word 5-grams (or char 5-grams for more robustness). * Insert into an LSH index to retrieve likely neighbors. * Provides a fast **Jaccard** overlap estimate without comparing to every doc. ### Lexical fingerprint: Lexical fingerprint (MinHash + LSH) is a technique that combines two powerful algorithms, MinHash and Locality Sensitive Hashing (LSH), to efficiently find and group together documents that are lexically similar. Lexical fingerprint refers to a way of representing a document based on its words and phrases. Instead of treating a document as a whole, it's broken down into smaller, overlapping units called shingles (e.g., sequences of words or characters). These shingles become the building blocks for identifying similarity. MinHash: MinHash is a technique that estimates the Jaccard similarity between two sets. 1. Shingling: Documents are first converted into sets of shingles. 2. Hashing and Minimums: Multiple hash functions are applied to these sets of shingles, and for each function, the minimum hash value is recorded. 3. Signatures: This process generates a compact "signature" (a vector of these minimum hash values) for each document. 4. Similarity Estimation: The number of matching values between two documents' MinHash signatures provides an approximation of their Jaccard similarity. NOTE: Jaccard similarity, also known as the Jaccard index, is a statistic used for gauging the similarity and diversity of sample sets. It measures the overlap between two sets by dividing the size of their intersection by the size of their union. Essentially, it provides a ratio indicating how much the sets have in common compared to the total number of unique elements in both sets. Formula: The Jaccard similarity (J) between sets A and B is calculated as: J(A, B) = |A ∩ B| / |A ∪ B| ### Locality Sensitive Hashing (LSH): LSH is a technique for speeding up the search for similar items in large datasets. It's crucial because comparing every MinHash signature pairwise is still computationally expensive for large collections of documents. 1. Banding: LSH typically employs a technique called "banding." It divides each MinHash signature into several smaller "bands". 2. Hashing Bands: Each band is then hashed into a bucket. 3. Candidate Identification: The key idea is that documents with similar signatures are more likely to have at least one band that hashes to the same bucket. These documents become "candidate pairs" for further, more precise similarity comparison. This differs from traditional hashing, which aims to minimize collisions. In harmony, they work like this: 1. Documents are transformed into sets of shingles (lexical fingerprints). 2. MinHash creates compact signatures (hash representations) of these shingle sets that preserve similarity. 3. LSH, using the banding technique, takes these MinHash signatures and efficiently groups potential similar documents into buckets, significantly reducing the number of pairwise comparisons needed to find near-duplicates or similar texts. ### 3) Semantic vector (embeddings) A semantic vector is a numerical representation of a word, phrase, or document that captures its meaning and contextual relationships within a larger dataset or corpus (in our case, our corpus of resumes). Semantic vector embeddings are numerical representations of data (like words, sentences, or documents) that capture their meaning or semantic relationships in a multi-dimensional space. Cosine similarity is a method to measure the similarity between these embeddings by calculating the cosine of the angle between them. Essentially, it tells you how closely the vectors point in the same direction, with a higher cosine value indicating greater similarity * Encode **whole document** with a sentence-transformer (configurable). * Similar docs → high **cosine** similarity. * Stored as `sem.npy` + `sem_ids.json`; searched via ANN (Approximate Nearest Neighbor (ANN) search is a technique used to find data points that are similar to a given query point, but it doesn't necessarily find the absolute closest one. Instead, it finds a point (or points) within a certain "close enough" distance, prioritizing speed and efficiency, especially when dealing with large, high-dimensional datasets) or brute force for small corpora. ### 4) Layout vector (optional) * A small numeric vector (e.g., section order, bullet density). If unused, set `w_lay = 0.0`. --- ## C. Passage-level Chunking Why chunk? Whole-document embeddings can miss partial plagiarism (e.g., one copied project section). Chunking raises recall. - **Chunking strategy:** sliding windows over tokens/sentences (e.g., ~140 tokens, stride ~70) — see `chunk.py`. - **Indexing:** For each doc, we embed each chunk and store vectors + `(doc_id, chunk_id, offsets)`. - **Query:** The uploaded resume is chunked the same way. We retrieve top-k neighbors **per chunk** using semantic ANN. We then aggregate candidates across chunks by **doc_id** (vote/score sum). --- ## D. Cross-Encoder Re-Ranker (pairwise scoring) A cross-encoder is a type of model in natural language processing (NLP) that analyzes the relationship between two pieces of text by processing them together as a single unit. To sharpen precision, we run a **cross-encoder** on top of the ANN/LSH candidates — see `cross_encoder.py`. - **What it does:** For each candidate doc (or its strongest chunk pair), the CE receives `(query_text, candidate_text)` and outputs a relevance score. - **Why it helps:** Cross-encoders **jointly** attend to both texts, catching paraphrases and nuanced overlaps that bi-encoders may blur. - **How we use it:** After initial scoring, we take the top N candidates (e.g., 20–50) and compute CE scores; we then **blend** CE into the fused score (weighted) or use it to re-order the top set. --- ## E. Candidate Generation (multi-signal) We take the **union** of: - Top-K **semantic** neighbors for the whole document - **LSH** neighbors from MinHash (lexical) - **Chunk**-level semantic neighbors (aggregated by doc) - (Optional) **layout** neighbors Deduplicate → cap to `k` (e.g., 20–50). This balances recall and speed. --- ## F. Scoring & Fusion For each candidate `doc`: 1. **Semantic (document):** `s_sem_doc = cosine(emb_doc(q), emb_doc(doc))` 2. **Semantic (chunk, max/avg):** `s_sem_chunk = max/mean over best chunk pairs` 3. **Lexical:** `s_lex = MinHash-estimated Jaccard` 4. **Layout (optional):** `s_lay ∈ [0,1]` or `0.0` 5. **Cross-encoder:** `s_ce ∈ [0,1]` (after sigmoid/normalization) **Fused total** (example default): ```` total = 0.40*s\_sem\_doc \+ 0.20*s\_sem\_chunk \+ 0.30*s\_lex \+ 0.00*s\_lay \+ 0.10\*s\_ce ```` > Weights are configurable in `config`/env. If you’re not using layout, keep `w_lay=0.0`. > If you want a stronger CE influence, increase `w_ce` (with care—CE is slower than bi-encoder). --- ## G. Near-Duplicate & Decision Policy **Near-dup hard gates** (short-circuit to 100% plagiarized): - `best_sem_doc ≥ 0.985` **or** `best_lex ≥ 0.95` **Component overrides** (to avoid “high semantic but low total” issues): - Examples: - `sem_doc ≥ 0.90 & lex ≥ 0.25` → plagiarized - `sem_doc ≥ 0.70` → at least needs_review **Fused thresholds** (after CE re-rank): - `total ≥ 0.85` → **plagiarized_likely** - `0.30 ≤ total < 0.85` → **needs_review** - `< 0.30` → **unique** --- ## H. Evidence Report (HTML) For `/screen_with_report` we render: - Header with **Overall / Lex / Sem / CE** (as configured) - **Exact overlaps** (phrase highlighter) or **soft keyword** overlaps when exact is sparse - **Similar bullets** (cosine-matched pairs) with inline token highlights - Filenames for context Reports are saved to `data/reports/<timestamp>.html` and linked from the API/UI. --- ## I. FAISS / Embedding Dimensions Embedding models output different vector sizes (e.g., MiniLM: 384, MPNet: 768). The vector index is created for that dimension. - Switching models with a different **dim** → **reindex** (`rm -rf ./data/index && cli index`) - Same dim → vectors can be reused --- ## J. Complexity & Performance - Exact hash: **O(1)** - Candidate gen: **sublinear** with ANN + LSH (or brute force for small corpora) - CE re-rank: **O(K)** forward passes (slower; keep K modest) - Index build: linear in documents and chunks (embedding + MinHash dominate) **Scaling tips** - Use ANN (FAISS/ScaNN) for both doc and chunk indices - Keep NUM_PERM consistent for MinHash & LSH - Tune chunk sizes/stride and CE weight for balanced quality vs. latency --- ## K. Why scores can differ with/without report Scores should match now that `/screen` and `/screen_with_report` share the same candidate & scoring path (including chunking + CE). If you ever see drift, reindex and ensure env variables match. --- ## L. Pseudocode (query) ```python text, layout = parse(upload) raw_text = text text = mask_pii_if_enabled(text) qdoc = normalize_and_split(text) # 1) exact dup if hash(qdoc["text"]) in hash_index or hash(raw_text) in hash_index: return 100%, plagiarized_likely # 2) candidates (doc ANN, LSH, chunk ANN) -> union C = generate_candidates(qdoc) # 3) score v_q_doc = enc_doc(qdoc["text"]) scores = [] for cid in C: odoc = store.get(cid) s_lex = jaccard_minhash(qdoc["text"], odoc["text"]) s_semD = cosine(v_q_doc, enc_doc(odoc["text"])) s_semC = max_chunk_cosine(qdoc_chunks, odoc_chunks) s_ce = cross_encode(q_best_text, odoc_best_text) # pair with best chunk or doc total = fuse(s_semD, s_semC, s_lex, s_ce, s_lay=0.0) scores.append((cid, total, s_lex, s_semD, s_semC, s_ce)) best = max(scores, key=lambda x: x[1]) # 4) near-dup and decision policy if best.s_semD >= 0.985 or best.s_lex >= 0.95: return 100%, plagiarized_likely decision = decide(best.total, best.s_lex, best.s_semD, best.s_semC, best.s_ce) # 5) (optional) evidence report = build_html_report(qdoc, top_doc, overlaps, similar_bullets, scores) return result ````

Related Documents

cheap-RAG Development Roadmap

Semblance AI — Development Roadmap

Changelog

Toasty — AI Triage & Responsible Disclosure Assistant (2026 — 350 hours)