Extraction name resolution is quadratic in a document's entity count

Aperta
#358 2 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
3/5
Tempo stimato
1-2 giorni
Idoneità per principianti
74/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
python, typescript

Direzione di ricerca

Read src/selfgraph/extraction/extractor.py and typescript/src/extraction/extractor.ts, focusing on resolve() and the registry construction in _assemble and assembleExtraction. Check existing extraction tests, then reproduce the timings with the provided script. Done means both implementations avoid rescanning registered entities for each unresolved name and existing extraction behavior still passes.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

approved-for-pr area: extraction bug effort: S P2 perf

What happens

_assemble (Python) and assembleExtraction (TypeScript) resolve every relation, preference, and decision name against the extracted entities. A name that is not a key of the registry falls back to a linear scan that calls entity_id twice per registered entity. All chunks of one document share one registry, so the cost grows with the square of the document's entity count. The work is synchronous and blocks the event loop, so an MCP server or other async callers stall while it runs.

Reproduce

On main (5a277c9), no store needed:

import time
from selfgraph.extraction.extractor import LLMExtractor, _RelOut
from selfgraph.models import EntityInput

for n in (250, 500, 1000, 2000):
    ents = [EntityInput(type="Person", name=f"Person {i}") for i in range(n)]
    rels = [_RelOut(from_name=f"Person {i}", type="KNOWS", to_name=f"Stranger {i}") for i in range(n)]
    t = time.time()
    LLMExtractor._assemble(ents, rels, [], [])
    print(n, f"{time.time() - t:.2f}s")
250 0.44s
500 1.54s
1000 5.97s
2000 24.87s

A document of about 150 chunks with 20 entities per chunk and 5 relations per chunk to names the entities pass did not list takes 9 s in _assemble alone.

Cause

resolve() in src/selfgraph/extraction/extractor.py and typescript/src/extraction/extractor.ts: registry.get(key) or next(e for e in registry.values() if entity_id(e.type, name) == entity_id(e.type, e.name)). Precomputing the canonical name of each registered entity once, and looking candidates up by it, makes this linear.

Lingua principale
TypeScript
Stelle
173
Fork
58
Merge medio
6h
PR unite (30g)
120

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di hydra-db/selfgraph

Tutte le issue di hydra-db/selfgraph

Issue simili

Altre issue su TypeScript

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.