Entity linking

Deep dive

How it works

Parts:

• Mention source — typed spans from named-entity-recognition plus the text around them.
• Alias table — normalised alias to (entity id, link count), from names, redirects, anchors, past labels.
• Fuzzy index — character trigram index, or a bi-encoder with HNSW (dense retrieval), for typos and unseen surface forms.
• Entity profile — description words, type, vector, validity dates.
• Scorer — prior, context fit, type match, string similarity; optionally a cross-encoder reranker.
• Collective step (optional) — makes the ids in one document agree.
• NIL decision — threshold or learned abstain; NIL clusters may become new entries.

Operations:

1. Normalise the mention (case, punctuation, legal suffixes, accents; text normalization).
2. Candidates: exact alias hit; else trigram or edit-distance match above a similarity floor (fuzzy-string-matching); else dense nearest neighbours. Keep the top K (often 10-100).
3. Prior: p(entity | alias) = link count / alias total.
4. Context: overlap of the mention's sentence with the entity profile (BM25 or TF-IDF), cosine of embeddings, or a cross-encoder reading mention and description together.
5. Combine: score = string similarity x (w1 x prior + w2 x context) or a learned ranker.
6. Collective: pick one entity per mention to maximise local score plus pairwise coherence (relatedness of the entities in the document).
7. If the best score is below a threshold, return NIL; otherwise return the id with its score.
8. Output (span, id or NIL, score) for relation extraction and joins.

text -> NER spans -> normalise -> alias table --\
                                  trigram/ANN --+-> candidates(K) -> prior + context
                                                                          |
   KB (ids, profiles, validity) ------------------------------------------+
                                                   collective (optional) -> NIL? -> id | NIL

KB updates. Ids must be opaque and stable (LEI, Wikidata Q-number, UMLS CUI), never names or tickers. Names, tickers and parents are attributes with validity intervals: resolve an alias as of the document's date, and keep merged-away ids as redirects to their successor. GLEIF's LEI records carry otherNames, successorEntity and event groups for exactly this. Rebuild counts and priors on every catalogue release.

Code

Alias table with link counts, normalised and trigram-Jaccard candidates, a context-overlap score and a NIL threshold on a made-up catalogue where two companies share the alias "Orbit". The 20,000 pseudo-random aliases only exist for the timing.

use std::collections::{HashMap, HashSet};

fn norm(s: &str) -> String { // lowercase, strip punctuation and legal suffixes
    let w = s.to_lowercase();
    let w = w.split(|c: char| !c.is_alphanumeric()).filter(|w| !w.is_empty() && !["inc", "ltd", "plc", "corp", "the"].contains(w));
    w.collect::<Vec<_>>().join(" ")
}
fn grams(s: &str) -> HashSet<[char; 3]> {
    let c: Vec<char> = format!("  {s} ").chars().collect();
    c.windows(3).map(|w| [w[0], w[1], w[2]]).collect()
}
struct Kb {
    id: Vec<String>,                   // entity index -> stable id
    ctx: Vec<HashSet<String>>,         // entity index -> description words
    alias: HashMap<String, Vec<(usize, u32)>>, // normalised alias -> (entity, link count)
    names: Vec<(String, usize)>,       // alias index -> (alias, its trigram count)
    tri: HashMap<[char; 3], Vec<usize>>, // trigram -> alias indexes
}
impl Kb {
    fn new() -> Self { Kb { id: vec![], ctx: vec![], alias: HashMap::new(), names: vec![], tri: HashMap::new() } }
    fn add(&mut self, id: &str, ctx: &str, aliases: &[(&str, u32)]) {
        let e = self.id.len();
        self.id.push(id.into());
        self.ctx.push(ctx.split(' ').map(String::from).collect());
        for &(a, n) in aliases {
            let a = norm(a);
            if !self.alias.contains_key(&a) {
                let g = grams(&a);
                for x in &g { self.tri.entry(*x).or_default().push(self.names.len()); }
                self.names.push((a.clone(), g.len()));
            }
            self.alias.entry(a).or_default().push((e, n));
        }
    }
    fn candidates(&self, m: &str) -> Vec<(&str, f32)> { // (alias, string similarity)
        if let Some((a, _)) = self.alias.get_key_value(m) { return vec![(a.as_str(), 1.0)]; }
        let g = grams(m);
        let mut shared: HashMap<usize, usize> = HashMap::new();
        for x in &g { for &i in self.tri.get(x).into_iter().flatten() { *shared.entry(i).or_default() += 1; } }
        shared.into_iter().filter_map(|(i, s)| {
            let j = s as f32 / (g.len() + self.names[i].1 - s) as f32; // trigram Jaccard
            (j >= 0.5).then(|| (self.names[i].0.as_str(), j))
        }).collect()
    }
    fn link(&self, mention: &str, context: &str) -> Option<(&str, f32)> {
        let words: HashSet<String> = context.to_lowercase().split(|c: char| !c.is_alphanumeric()).map(String::from).collect();
        let mut best: Option<(&str, f32)> = None;
        for (a, sim) in self.candidates(&norm(mention)) {
            let links = &self.alias[a];
            let total: u32 = links.iter().map(|l| l.1).sum();
            for &(e, n) in links {
                let prior = n as f32 / total as f32;
                let ctx = (self.ctx[e].intersection(&words).count().min(2)) as f32 / 2.0; // 2 matching words saturate
                let s = sim * (0.4 * prior + 0.6 * ctx);
                if best.map_or(true, |b| s > b.1) { best = Some((&self.id[e], s)); }
            }
        }
        best.filter(|b| b.1 >= 0.3) // below the threshold: NIL
    }
}
fn main() {
    let mut kb = Kb::new();
    kb.add("ORBK", "bank loan deposits rates guidance", &[("Orbit", 70), ("Orbit Bank plc", 30)]);
    kb.add("ORBT", "phase trial drug fda patients", &[("Orbit", 30), ("Orbit Therapeutics Inc.", 20)]);
    kb.add("KSTR", "satellite launch rocket orbital", &[("Kestrel Aerospace", 10), ("Kestrel", 40)]);
    let tests = [
        ("Orbit", "Orbit raised guidance as loan growth beat rates", Some("ORBK")),
        ("Orbit", "Orbit reported phase 3 trial results for its drug", Some("ORBT")), // context beats the prior
        ("Orbit Therapeutics Inc.", "Shares fell", Some("ORBT")),
        ("Orbitt", "Orbitt bank cut deposits rates", Some("ORBK")), // typo: trigram match
        ("Kestrel", "the launch went well", Some("KSTR")),
        ("Orbit", "the telescope reached low orbit", None), // known alias, no context evidence
        ("Zorblax Holdings", "Zorblax filed a patent", None), // unknown name
    ];
    let hit = tests.iter().filter(|t| kb.link(t.0, t.1).map(|l| l.0) == t.2).count();
    println!("linking accuracy {hit}/{}", tests.len());
    assert_eq!(hit, tests.len());
    // scale: 20,000 pseudo-random single-word entities, then time mixed lookups
    let mut x = 0x9E3779B97F4A7C15u64;
    for i in 0..20_000 {
        let name: String = (0..8).map(|_| { x ^= x << 13; x ^= x >> 7; x ^= x << 17; (b'a' + (x % 26) as u8) as char }).collect();
        kb.add(&format!("S{i}"), "synthetic", &[(&name, 1)]);
    }
    assert_eq!(kb.link("Orbit", "phase trial drug").map(|l| l.0), Some("ORBT"));
    let t0 = std::time::Instant::now();
    let n = 20_000;
    let found = (0..n).filter(|i| kb.link(tests[i % tests.len()].0, tests[i % tests.len()].1).is_some()).count();
    println!("{:.0} lookups/s (exact, fuzzy and NIL mix, {found} linked), {} aliases", n as f64 / t0.elapsed().as_secs_f64(), kb.names.len());
}

Output on an Apple M4 Pro, one thread, release build (measured, five runs): accuracy 7/7; 126 k to 128 k lookups/s on a mix of exact, fuzzy and NIL cases over 20,005 aliases. The toy's weights (0.4, 0.6, threshold 0.3) are hand-set; tune them on labelled mentions.

Complexity and constants

• Exact lookup: one hash probe. Trigram candidates: the sum of the posting lengths of the mention's trigrams; common trigrams ("ing", "ion") make long postings, so cap them.
• Cross-encoder: one transformer pass per (mention, candidate), about 2 x parameters x tokens FLOPs (my arithmetic: 100 M x 128 is order of 25 GFLOPs per pair).
• Memory: an embedding index adds dimension x 4 B (float32) per entity.

Efficiency

• Cost: the toy, one M4 Pro core, 20,005 aliases: about 8 µs per lookup (measured, mixed cases); exact hits are cheaper, fuzzy misses cost most. A cross-encoder over K candidates multiplies a pass by K: latency bound by compute, so rerank only a few. BLINK reports bi-encoder retrieval over 5.9 M candidates in 2 ms with nearest-neighbour search (Wu et al., abstract).
• Levers:
  • Precompute the trigram count per alias — 11 k to 127 k lookups/s on the toy (measured) — any fuzzy index.
  • Exact alias hit first, fuzzy only on a miss — skips the postings walk — most mentions.
  • Cache (normalised mention, context hash) — repeated mentions are common — news streams, product feeds.
  • Cross-encoder only when the top two scores are close — fewer passes (no figure) — latency budgets.
  • One pass for detect, type and link — ReFinED reports more than 60x faster than competitive approaches (Ayoola et al., abstract) — bulk web-scale extraction.
• Naive → standard → state of the art:
  • Edit distance against every KB name · O(KB x length^2) per mention.
  • Alias table + trigram index, prior x context score · order of 10 µs per mention, no GPU.
  • Bi-encoder retrieval + cross-encoder rerank (BLINK) or end-to-end single pass (ReFinED) · accuracy on unseen entities, one to several model passes.

Implementation notes

• Build aliases from every source: legal and previous names, tickers, redirects, anchors, past editor links. Key by normalised form; keep raw forms for display.
• Type is a filter: a person span never links to a company id.
• Calibrate (calibration) the score before thresholding; set the NIL threshold per type and KB.
• Store (alias, id, count, first_seen, last_seen); a count floor shrinks the table.
• Log every NIL with its context: it is the queue for new entries.

Pitfalls

• Prior dominance: the popular sense always wins unless context is on a comparable scale; test the rare sense.
• Candidate recall hides in the headline: measure the share of gold ids in the top K before tuning the ranker.
• Linking to names or tickers: tickers are reused after delistings and change at mergers; ids must not.
• Over-linking: an answer forced for every span puts wrong ids in the data; common-word aliases ("Apple", "Orbit") need a context floor.
• Collective linking spreads one wrong decision across the document and is quadratic in mentions; cap it.
• Train/test entity overlap inflates zero-shot claims. Stale KB: new entities get linked to their nearest old neighbour unless NIL works.

Variants and alternatives

In production

• Finance news: issuer mentions to LEI/ticker/FIGI by as-of date; NIL for firms outside the universe.
• Biomedical: scispaCy links to UMLS (about 3 M concepts), MeSH or RxNorm via char-3gram nearest-neighbour search.
• Search: queries and pages to Wikidata items for knowledge panels.
• Commerce titles to SKUs; registers: party names to registry numbers; customer and patient data: names to a master id.

Implementations

Sources

• Wu et al., Scalable Zero-shot Entity Linking with Dense Entity Retrieval, EMNLP 2020. paper · code
• Ayoola et al., ReFinED: An Efficient Zero-shot-capable Approach to End-to-End Entity Linking, 2022. paper · code
• Ganea, Hofmann, Deep Joint Entity Disambiguation with Local Neural Attention, EMNLP 2017. paper · code
• Hoffart et al., Robust Disambiguation of Named Entities in Text, EMNLP 2011. paper
• Milne, Witten, Learning to link with Wikipedia, CIKM 2008. paper
• Shen, Wang, Han, Entity Linking with a Knowledge Base: Issues, Techniques, and Solutions, IEEE TKDE 27(2), 2015. paper
• GLEIF, LEI records API (legal name, other names, successor entity). docs