Contents · 8 sections
1What the system does at build, query and delete time2Each passage yields one line of JSON3Entities are computed by rule from name cards and recomputed on deletion4Two designs removed for this property5Is the graph after deletion really the same as never ingesting?6Retrieval walks the graph, without model calls, to entities the question never names7Cheapest to build, with accuracy trading wins against the strongest baseline8Which questions does it lose on?SHARE
The GraphRAG system Lightfoot moves the work of "deleting one document cleanly from a knowledge graph" into graph construction. Each passage's extraction result is stored on its own, and every entity, fact and edge in the graph is computed only from passages that are still present, so deleting a document only requires removing those passages' records and recomputing the affected parts, with no further LLM calls.
Systems like GraphRAG do multi-hop question answering. The evidence for an answer is spread across several passages, but the question often names only something that appears in the first passage; the later passages do not look like the question on the surface, and similarity search alone cannot find them. So the system first uses an LLM to extract entities (names such as companies and people) and the relations between them from every passage, links the entities into a knowledge graph, and at question time starts from the entities the question mentions and follows relations in the graph step by step to the later passages.
Imagine a company knowledge base (illustrative; the whole article uses this example) holding four passages:
- P1 (news): "Lin Zhou is the chief executive (CEO) of Xinghe Logistics."
- P2 (a contract): "Xinghe Logistics Co. acquired Lanjing Warehousing in 2019."
- P3 (company profile): "Lanjing Warehousing is headquartered in Ningbo."
- P4 (industry report): "Xinghe Group Logistics expanded its East China routes this year." Whether "Xinghe Group Logistics" is the same company as "Xinghe Logistics" in the first two passages cannot be told from the name.
A user asks: "Where is the headquarters of the warehousing company acquired by the company Lin Zhou runs?" The question names only Lin Zhou. The system must first learn from P1 that Lin Zhou runs Xinghe Logistics, then learn from P2 that Xinghe Logistics acquired Lanjing Warehousing, and finally get "Ningbo" from P3.
The trouble comes later: the contract expires, and the legal team requires that P2 and everything the system extracted from P2 be deleted, leaving the system as if it had never read P2. Retention policies, expiring contracts and the right to be forgotten all lead to requests like this. Deleting P2's raw text is easy. The hard part is that P2's content has already been turned into entities, facts and edges in the graph, and may have been written, together with content from other documents, into the same piece of model-generated text.
Existing systems run into trouble precisely with this mixed text. LightRAG has the model write a description for each entity and calls the model again to merge descriptions when an entity has several, so the description of "Xinghe Logistics" may contain P1's CEO, P2's acquisition and P4's expansion all at once. To delete P2, the model must rewrite this description without the acquisition. Microsoft GraphRAG is harder still: it groups closely related entities into a community and has the model write a summary report for each community, and there is no way to trace which document a sentence in the report came from. The authors went through the source code of 17 open-source GraphRAG frameworks: 5 support deletion by document, and none claims that the graph left after deletion equals the graph built without that document in the first place.
Lightfoot's fix is to never mix content from different passages: each passage's extraction result is stored separately, and entities, aliases (different names for the same entity) and synonym edges (links between entities with similar names) are all computed by rules from the passages still present. To delete P2, the system only removes P2's extraction records and recomputes, with the same rules, the entities and edges that involve P2. Deleting the same 1,140 documents from MuSiQue, a multi-hop QA dataset with 11,402 documents, took LightRAG 2,187 model calls and 3.7 hours, and took Lightfoot 74 seconds and 0 calls. LightRAG's time goes into having the model rewrite the description of every affected entity. Lightfoot's graph after deletion also matches, table by table, a graph newly built from only the remaining 10,262 documents.
What the system does at build, query and delete time
Lightfoot calls the LLM in only two places: one extraction per passage when building the graph, and one answer generation per question. Every other step is local computation.
| When | Input | What the system does | Output | LLM calls |
|---|---|---|---|---|
| Build | One passage | Extract entities and facts, cache the result | This passage's own extraction result | 1 per passage |
| Build | All extraction results | Compute name embeddings, link with two similarity thresholds | Entities, aliases, synonym edges, fact sources | 0 |
| Query | One question | Choose starting points from facts and passages, walk the graph, rerank with a cross-encoder | Ranked passages | 0 for retrieval, 1 for the answer |
| Delete | Documents to delete | Remove their records, recompute affected entities and synonym edges | The graph after deletion | 0 |
The split between the two build rows is why deletion needs no model calls: the LLM only ever reads one passage at a time, and merging the same entity across different passages is left entirely to similarity rules that can be recomputed at any time.
Each passage yields one line of JSON
Each passage gets exactly one call to Llama 3.3 70B, which returns JSON compressed onto one line. It holds at most 12 entities, each with a name, a type and a description of at most 8 words, plus at most 12 facts, each written as subject, predicate and object with a piece of source evidence of at most 12 words. P2's extraction looks roughly like this (illustrative; field names and content are made up):
{"entities":[["Xinghe Logistics Co.","company","logistics company that acquired Lanjing Warehousing"],["Lanjing Warehousing","company","acquired warehousing company"]],"facts":[["Xinghe Logistics Co.","acquired","Lanjing Warehousing","acquired Lanjing Warehousing in 2019"]]}
Facts are written as arrays rather than objects with field names, and the output has no line breaks, to cut output tokens (the model is billed and timed by token). On a 32-passage sample, output per passage fell from 436 tokens to 269, while facts extracted per passage rose from 3.8 to 7.7. This shows that in the same single call, the tokens saved by the compact format can be spent on writing more facts.
Extraction results are cached per passage, and the cache key includes a hash of the prompt and the output format, so once the prompt or format changes, old cache entries are not reused by mistake. Rebuilding a graph from the cache later needs no model calls at all.
Entities are computed by rule from name cards and recomputed on deletion
Suppose the system kept an entity table, and when P2 arrived it merged "Xinghe Logistics" and "Xinghe Logistics Co." into one entry. Once P2 is deleted, the table holds only the merged entry, and the system cannot tell whether the merge depended on P2. Lightfoot therefore treats the raw occurrence records as the only source of truth: the entity table is still stored, but every entity in it is computed from these records by fixed rules, and when a record is deleted, the affected entities are recomputed by the same rules.
Each time a name appears in a passage, the system stores a name card (the paper calls it a form) recording which passage, the normalized name, the type, and this passage's description of the entity. There are only two rules. Two cards of the same type are linked when the cosine similarity of their name embeddings reaches 0.92, and a group of linked cards (a connected component) is one entity.
An entity's id is the lexicographically smallest name among its cards, and its display name is the name in the group that appears in the most passages. Both look only at cards that are still present.
Illustration: P1's "Xinghe Logistics" is card a, P2's "Xinghe Logistics Co." is card b, and P4's "Xinghe Group Logistics" is card c. Assume the similarity of a and b is 0.95, of b and c 0.93, and of a and c 0.88.
Before P2 is deleted, a links to b and b links to c, so the three cards form one entity even though a and c are only at 0.88. After P2 is deleted, card b disappears, a and c at 0.88 fall short of 0.92, and the entity splits in two. This is exactly what the system would get if it had never ingested P2, so P2 leaves no trace at the entity level.
After the split, the two entities are not fully cut off. Lightfoot has a second threshold: two entities of the same type get a synonym edge when the similarity of their display names reaches 0.80, and there is no cap on how many synonym edges one entity can have. The 0.88 between a and c clears this line, so "Xinghe Logistics" can still reach "Xinghe Group Logistics" through a synonym edge.
Facts are handled the same way. Each fact records which passages stated it. Illustration: if the source set of "Xinghe Logistics acquired Lanjing Warehousing" is only {P2}, deleting P2 empties the set and the fact disappears. If another document P5 also reported the acquisition, the set goes from {P2, P5} to {P5} and the fact stays.
As long as everything in the graph is determined only by the individual extraction results of passages still present, deletion becomes removing records and recomputing by rule, with no need to ask the model again.
The paper states this property as a proposition: split the document set arbitrarily into A and B, delete B from the full graph, and the resulting store equals the store built from A alone. The core of the proof is the example above: cards and fact sources are deleted together with their passages, and a link depends only on two cards, so which cards form an entity has nothing to do with the order in which documents were inserted, how many batches they came in, or what was deleted before. Name vectors are also computed in fixed-size batches; without this, the same name could get a different vector before and after a deletion because the other names in its batch differed. Hoot says
The three name cards and their similarities are illustrative, reusing the example in the text (a from P1, b from P2, c from P4). After P2 is deleted, a and c at 0.88 fall short of 0.92 and the entity splits in two; 0.88 clears the 0.80 synonym threshold, so a synonym edge joins the two entities.
Source
paper §3.2 (definition of a form, 0.92 links, connected components, entity ID and canonical-name rules, 0.80 synonym edges, facts keyed by forms; proof of Proposition 1: delete the forms and assertions contributed by B's chunks, then recompute the components and synonym edges touched)Two designs removed for this property
The first thing given up is having the model judge whether two names refer to the same entity. Name pairs with similarity between 0.80 and 0.92 are the most ambiguous, and the 0.88 between a and c in the example falls right there, so asking the model to decide is a natural move. But once the model judges them to be the same entity, that link depends on what the model saw at the time, for example P2's acquisition description being in its context. After P2 is deleted, the result of that judgment stays in the graph and cannot be recomputed by rule, so the graph can no longer return to what it would be without P2.
Removing it costs little. On a 2,000-passage slice with 141 questions, Recall@5 (the share of gold evidence passages that land in the top 5) changed by less than 1 point with and without model judgments, within noise, and the full corpus saved 5,626 judgment calls. This shows that, at least on this slice, exact deletion was not bought with retrieval quality.
The second thing given up is the top-k synonym list. Illustration: with k=2, entity X's neighbors are Y (0.90), Z (0.85) and W (0.82); the list keeps only Y and Z, and W is pushed out. After deleting the document containing Y, in a graph that never saw Y, X's list should be Z and W, but the store holds only Z.
With a fixed threshold of 0.80 instead, X has one edge each to Y, Z and W; deleting Y removes only the X–Y edge, and the other two are unaffected.
This design, which looks only at current cards and never at history, came from a failure seen in testing. An early version matched each new name against the display entities already in the graph at that moment and also kept top-k synonym lists; after deletion it differed from a freshly built index by 12 entities and 340 synonym edges. In terms of the example, if card c, on arrival, was merged into the entity whose display name was b because it resembled b, that merge was fixed for good; after P2 is deleted, c would still sit in the entity containing a, whereas in a graph that never saw P2, a and c are two entities. Twelve entities is small against the 68,455 entities on MuSiQue, but "equal to a rebuilt graph" demands entry-by-entry equality, and a single difference breaks it.
Is the graph after deletion really the same as never ingesting?
The authors ran two layers of checks. The first applies to every system that supports deletion: on MuSiQue, call each system's own delete interface, randomly delete 10% of the documents, and rerun all questions. Questions fall into two groups: those whose evidence passages were all kept (evidence survived) and those with at least one evidence passage deleted (evidence deleted).

On evidence-survived questions, Lightfoot's Recall@5 is .648 before deletion and .661 after. After the same deletion, evidence-deleted questions score only .369. The clearly lower score on evidence-deleted questions shows that deletion really removed the content from retrieval results; the evidence-survived score did not fall, which shows the remaining content was not damaged. LightRAG's Recall@5 values are .491, .507 and .292, the same pattern, but at the price of 2,187 model calls.
fast-graphrag (a framework that does one structured extraction per passage and ranks with PageRank) has no delete interface, so deleting means rebuilding everything. HippoRAG 2 (which also uses PageRank and extracts twice per passage at build time) also needs 0 calls and took only 9 seconds, faster than Lightfoot's 74. So Lightfoot's advantage is not deleting fastest, but that its post-deletion result has been verified table by table.
The second layer applies only to Lightfoot. The authors compute a fingerprint of the store after deletion (think of it as a checksum of the whole store), then start a separate process that rebuilds an index of the remaining 10,262 documents from the extraction cache, and compare the two. The fingerprints are identical and all six tables match: 68,455 entities, 71,195 aliases, 106,472 mentions, 92,608 facts, 94,032 fact sources and 63,514 synonym edges. This shows that the question in this section's heading gets a yes in this experiment: after deleting 10% of the full MuSiQue corpus, the graph is the same as one that never ingested those documents.
This verification was run only on Lightfoot. HippoRAG 2 also deletes by provenance, and the authors say it may be exact as well, so these numbers should not be read as HippoRAG 2 failing to delete cleanly.
Retrieval walks the graph, without model calls, to entities the question never names
Clean deletion only solves the operations problem; the system still has to answer correctly. Lightfoot's graph has two kinds of nodes, entities and passages. Edges between passages and entities come from name cards, edges between entities are weighted by the number of facts connecting them, and synonym edges are weighted by name similarity.
Retrieval starts from the two facts most like the question. The system uses bge-base to embed the question and every fact, finds the two facts most similar to the question, and uses their subject and object entities as seeds for Personalized PageRank. Each seed's initial weight is the fact's similarity divided by the number of passages that mention the entity.
Illustration: the question's similarity to "Lin Zhou is the CEO of Xinghe Logistics" is 0.9. Lin Zhou appears in only 1 passage, so its initial weight is 0.9. Xinghe Logistics appears in 3 passages, so its initial weight is 0.3. This division keeps entities mentioned everywhere from taking too much of the starting weight.
Besides entities, the 100 passages most similar to the question also serve as seeds, but with small weights: after these passages' similarities are min–max normalized, each passage seed gets a weight of at most 0.05. The walk uses damping 0.9, meaning that at each step there is a 90% chance of continuing along an edge. Weight flows from Lin Zhou to Xinghe Logistics, then along the "acquired" fact edge to Lanjing Warehousing, and finally to P3. P3 therefore gets a score even though the question never mentions Lanjing Warehousing.
Once P2 is deleted, the "acquired" fact edge is gone too, and weight can no longer reach Lanjing Warehousing along this path. This broken path is exactly what deletion is supposed to do.
The walk takes the 30 highest-scoring passages and hands them to a local cross-encoder for scoring. Lightfoot does not let the cross-encoder's ranks simply replace the PageRank ranks; it fuses them with RRF (adding the reciprocals of the two ranks, with k=60).
Illustration: P3 ranks 2nd in PageRank and 20th in the cross-encoder, so its fused score is 1/(60+2) + 1/(60+20) = 1/62 + 1/80 ≈ 0.0286. A distractor passage that merely looks like the question on the surface ranks 25th in PageRank and 1st in the cross-encoder, with a fused score of 1/85 + 1/61 ≈ 0.0282. With the cross-encoder alone, P3 would fall out of the top five; after fusion, P3 ranks above the distractor.
In the ablation, fusion gained 3.4 points of Recall@5 over directly replacing the PageRank ranks, the largest gain of any single component. This shows that keeping the PageRank rank in the final ordering beats trusting the cross-encoder alone. My reading is that passages for later hops do not look like the question on the surface, so they lose out when the cross-encoder scores them alone, which is the situation in the illustration above.
Cheapest to build, with accuracy trading wins against the strongest baseline
The comparison conditions are uniform: the four systems use the same extraction model, the same answer model, the same embedding and the same answer instruction. Lightfoot's retrieval parameters were tuned only on the first 500 MuSiQue questions, and the MuSiQue retrieval comparison with HippoRAG 2 uses the last 500. The other two multi-hop QA datasets, 2WikiMultiHopQA and HotpotQA, have 300 questions each and were not used for tuning.
| System | MuSiQue build cost | Model calls per passage | Model calls per question at retrieval | MuSiQue median retrieval latency |
|---|---|---|---|---|
| Lightfoot | $1.64 | 1.0 | 0 | 0.53 s |
| HippoRAG 2 | $2.23 | 2.0 | 1 | 1.56 s |
| fast-graphrag | $4.89 | 1.1 | 1 | 1.96 s |
| LightRAG | ≈$9.5 | 2.5 | 1 | 0.81 s |
Costs are converted at uniform model list prices, and LightRAG's MuSiQue figure is estimated from its call count. Lightfoot's build cost is the lowest on all three datasets: 26–31% below HippoRAG 2, and 3 to 6 times lower than LightRAG and fast-graphrag. This shows that the constraints added for exact deletion did not raise build cost; extracting only once per passage actually pushed the bill down.

In paired comparisons with the strongest baseline, HippoRAG 2, the authors compared 15 items in total: Lightfoot is significantly better on 5, significantly worse on 2, and tied on the other 8.
The table below lists only the 7 significant items, in percentage points, with 95% intervals in brackets. EM is the share of answers that match exactly, and F1 is computed over answer tokens.
| Dataset | Metric | Lightfoot minus HippoRAG 2 |
|---|---|---|
| MuSiQue | Recall@5 | +2.8 [+0.5, +5.1] |
| MuSiQue | Recall@10 | +4.3 [+2.5, +6.2] |
| HotpotQA | Recall@10 | +1.3 [+0.2, +2.7] |
| HotpotQA | EM | +7.7 [+3.0, +12.3] |
| HotpotQA | F1 | +5.0 [+1.3, +8.7] |
| 2WikiMultiHopQA | Recall@2 | −3.9 [−7.0, −0.8] |
| 2WikiMultiHopQA | F1 | −8.4 [−12.9, −4.2] |
This shows that on accuracy alone, Lightfoot and HippoRAG 2 each win some. Lightfoot's clear advantages are a cheaper build, retrieval without model calls, and a post-deletion result verified table by table.
Compared with the other two kinds of approach, its retrieval is steadier. On MuSiQue its Recall@5 is .646, 10.2 points above plain vector retrieval at .544. On all three datasets its Recall@5 is above LightRAG and fast-graphrag.
Answer metrics deserve some margin. The authors ran the system twice, changing only the context given to the answer model from 8 passages to 10, and about 30 of 300 questions flipped between right and wrong while the net change was close to zero. The authors therefore treat answer differences below about 4 points on 300 questions as ties. HippoRAG 2's absolute scores are also lower than in its own paper, because the same embedding was used for everyone here instead of the 7B embedder from its paper.
Which questions does it lose on?
The failures on MuSiQue also come from the graph-walk path described above. In one run that added BM25 (keyword retrieval) and vector retrieval as two extra candidate channels on top of the graph walk, 183 of 300 questions were answered wrongly, and for 109 of them the context was missing at least one gold evidence passage. The missing passages are concentrated in later hops: 83% of entities in first-hop passages are named in the question, which falls to 36% for the second hop and only 28% for the third and fourth hops. This shows that searching on the question text cannot reach these passages; only following the chain can.
The starting point for following the chain can also be wrong. Lightfoot takes only the two facts most like the question as seeds, and sometimes it picks a fact that touches the question but is not on the reasoning chain, such as a work's release date. In terms of the example, if the chosen fact were "Xinghe Logistics was founded in 2008" (illustrative), weight would not necessarily flow to the "acquired" edge.
HippoRAG 2 uses one model call at retrieval to filter candidate facts, which targets exactly this problem. The authors think this may explain its advantage on 2WikiMultiHopQA, where most questions compare two named entities. If that explanation holds, this is the price Lightfoot pays for dropping model calls at retrieval.
All the questions here are multi-hop QA, and Lightfoot has no community reports, so the comparisons above speak only to multi-hop QA and not to corpus-level summary questions such as "what is this batch of documents about overall".
Back to the contract: the legal team wants P2 gone from the graph completely. Lightfoot's answer is to never let P2 be mixed with other passages at build time, so that entities, synonym edges and facts can all be recomputed from the passages still present. For this it gave up model judgments of same-name entities and top-k synonym lists, verified on MuSiQue that the graph after deletion matches a rebuild table by table, and trades wins with the strongest baseline on retrieval quality.
How did this read for you?
Hoot made a note. Thanks for the feedback.
One tap, no sign-in; tap again to undo. Only anonymous counts are kept, never who you are.
Related papersMore from Paper Daily
Retrieval · 2026-11-05From Logs to Faults: Reference-Free Fault Localization for Retrieval-Augmented Generation PipelinesRAGLog reads only the API logs each run of a RAG pipeline leaves behind, with no reference answers and no code changes, and points out which stage of the run went wrong. This matters because a pipeline can go wrong in the middle and still give the right final answer. Across natural runs of five open-source pipelines, 37% had at least one faulty stage, and more than a third of those still answered…
Retrieval · 2026-11-16CURATOR: Scalable Fine-grained Evidence Selection for Retrieval-Augmented Generation using Decision ModelsRAG usually stuffs whole retrieved passages into the LLM, though often only a few sentences in them can answer the question. Picking those sentences is not easy: a sentence can look irrelevant on its own, and whether to keep it may depend on other retrieved text. Judging each sentence with the full context is too expensive. Decision models can score many candidate sentences in one pass, with each…
Retrieval · 2026-11-13PCG-RAG: Progressive Compositional Grounding for Retrieval-Augmented Generation in Complex Web Question AnsweringComplex web QA often requires first working out who or what several clues describe, then looking up an attribute of it, and a common mistake is to treat a name as settled after only one clue matches. The paper's example is a London power station converted into an art museum: a system that settles on Battersea from London and power station alone retrieves an architect who actually belongs to a dif…
Retrieval · 2026-11-12OpticalRAG: Pixel-Space Compression for Token-Efficient Retrieval-Augmented GenerationTo save tokens, RAG systems usually delete words or summarize the text, and the harder they compress, the more detail they lose. OpticalRAG goes the other way: it renders documents as page images, encodes them into visual tokens with a frozen vision encoder, and does both retrieval and compression on those visual tokens. A text query passes through a light projection into the same visual feature…
Retrieval · 2026-11-02Retrieving from Your Own Mistakes: On-Policy Training of Embedding Models for Multi-Hop Retrieval-Augmented GenerationChain embedding retrievers for multi-hop retrieval see different histories in training and in use, and this paper fixes that without adding any LLM call. At each step such a retriever joins the question with the passages found so far to look for the next one; in training its history holds only correct passages, but in use it often holds wrong passages it found itself. On four-hop MuSiQue question…
Retrieval · 2026-10-29Tessera: Structure-Completed Evidence Units for Web Retrieval-Augmented GenerationAsk Wikipedia who produced Willy Wonka and the Chocolate Factory, and the answer sits in the producer row of the page's infobox. Text extraction drops the two names in that cell, the reader model sees only the director, and it answers wrong. Tracing answer evidence from page source to reader input over all of English Wikipedia, this paper finds such loss is common: for 7.6% of questions the evide…
Retrieval · 2026-07-24Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph ApproachDeep dive: Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach.
Retrieval · 2026-10-24Chunk Recomputation under Real Document Revisions: Measuring Update Cost and Retrieval Quality of Fixed, Recursive, and Content-Defined ChunkingChunking schemes for RAG are almost always compared on one static corpus, yet the documents in a knowledge base keep changing. Each chunk is embedded on its own, so if an edit moves a chunk boundary, the chunks on either side become new embedding inputs even when not a single word in them changed. The authors take adjacent revisions of Chinese and English Wikipedia articles and allow an old vecto…
Discussion
Add experiment details, reproduction notes or a different take. Requires a GitHub sign-in.
Loading the discussion…