Search indexes are usually built as if documents never change after they arrive. Real collections such as wikis, codebases, contracts, and help centers are edited constantly. When someone fixes one sentence in a long article, a modern neural index must either re-encode the whole document or keep serving a stale vector. The reason is that a Transformer gives every token a vector that depends on every other token, so a local edit is not local in the representation. We propose an index whose entries are the nodes of a parse tree over each document. A parse tree here is a binary tree in which each node stands for a contiguous span: phrase, clause, sentence, and up to the whole document. Each node's vector is computed only from its two children. With this design, an edit invalidates only the nodes above the edited text, and the index can be repaired by recomputing a handful of nodes rather than the whole document.
Parsing has a reputation for being too slow for this use. Exact chart parsing, which scores every span and every split point, costs time cubic in length. We do not use it at indexing time. Each tree is built by greedy top-down splitting on learned boundary scores, which takes near-linear time. We then show that if those scores have a bounded receptive field, the tree itself changes only locally under edits. The central claim is that bottom-up composition over a locally scored tree gives an index with multi-granularity entries, including a document-level vector. That index can be updated under insertions, deletions, and substitutions at a cost proportional to tree depth instead of document length, at little or no loss in retrieval quality against full re-encoding.
Why this gap is real
The dynamic-indexing literature is almost entirely about appending new documents. IncDSI adds one document vector per new document by constrained optimization in 20–50 ms. DSI++ fights forgetting with flatter minima and replayed pseudo-queries. CLEVER keeps quantized identifiers stable as clusters shift. MEVI routes queries to coarse clusters so that new documents can be dropped into an external vector index without retraining. The research file records that editing and deleting existing content remains unresolved for all of them, and DISCo explicitly leaves dynamic corpora open. These papers motivate the problem. None of them offers a representation in which an edit has bounded blast radius.
Two older and more distant papers supply the mechanism. Interactive Incremental Chart Parsing keeps dependency pointers between chart entries so that a word edit invalidates only the spans that touch it. It is purely symbolic and has no learned representations. Fast-R2D2 shows that a learned top-down split scorer can prune a chart. It reports 30–50× faster than its predecessor and 57.22 unsupervised F1 on WSJ. It then composes node vectors bottom-up in parallel, and its 62M-parameter model is competitive with a 12-layer BERT on single-sentence tasks. Fast-R2D2's split scorer is a global BiLSTM, so a single inserted token can move every split score. That breaks locality, and repairing it is the technical core of this proposal. A third paper constrains the design. Probability Distribution Collapse documents that induced trees tend to collapse to left- or right-branching chains. A chain has depth linear in length, which would destroy the update-cost advantage, so balance has to be enforced rather than assumed.
Core Claim
Top-down splitting at the highest-scoring boundary produces exactly a Cartesian tree over the boundary scores. In that tree, the root is the maximum score and each subtree is built recursively on either side of it. Suppose each boundary score depends only on tokens within $w$ positions. Then an edit changes at most $O(w)$ scores. The nodes whose span or children change are confined to the ancestors of those boundaries, which is the same reason treap insertions are local. With bottom-up composition, the number of node vectors that must be recomputed per edit is
$$C_{\text{edit}} = O(w \cdot d),$$
where $w$ is the scorer's receptive-field radius in tokens and $d$ is the depth of the document's tree. If scores behave like random keys, $d$ grows logarithmically in document length $n$, following the standard treap depth argument. A flat Transformer by contrast needs $O(n)$ token re-encodings, each with $O(n)$ attention. The claim therefore has two falsifiable halves. The first is efficiency: measured recomputation counts should track $w \cdot d$, and $d$ should stay near logarithmic under a balance regularizer. The second is quality: retrieval over node vectors should match a flat encoder that is fully re-encoded after every edit.
Research Program
We will build a retrieval encoder with three parts. The first is a split scorer with a fixed window. It is a small convolutional or windowed-attention network over token embeddings, and its window size $w$ is a swept hyperparameter. The second is a Fast-R2D2-style composition cell that maps two child vectors to a parent vector. It has no top-down or sibling context, so locality is exact rather than approximate. The third is a query encoder.
Training has two phases. The parser and composition cell are first pretrained with Fast-R2D2's pruned-chart objective on WikiText103, so cubic parsing appears only during training and on pruned charts. The system is then fine-tuned end-to-end with a contrastive retrieval loss in which a query is scored against a document by the maximum similarity over its node vectors. The document root vector is also scored, so that whole-document context gets trained. A depth penalty on expected tree depth guards against the branching collapse described above.
At indexing time every node vector goes into a standard approximate-nearest-neighbor index, with a pointer from each node to its document. The edit algorithm is the neural analogue of the 1989 chart-invalidation method. It recomputes boundary scores within $w$ of the edit, repairs the Cartesian tree locally, recomposes ancestors bottom-up, and deletes and inserts the changed node vectors in the index. Deletion of a whole document is exact, because every node belongs to one document.
We will also analyze where the guarantee bends. Learned scores are not random, so we will measure the empirical depth distribution and the gap between predicted and observed recomputation. We will also check whether edits that change the topic of a paragraph ought to change high-level nodes more than the local rule allows. In that case staleness at the root is a quality question rather than a correctness one, and we will measure it directly.
Baselines
The naive reference point is to do nothing. The index keeps the pre-edit vectors, and we measure how badly retrieval of edited content degrades. Its upper-quality counterpart is full re-encoding of each edited document with a strong flat dual encoder. That is the quality oracle for every update-cost comparison, and it also bounds our encoder's own staleness, because we likewise re-encode our tree from scratch.
The strongest practical competitor is a flat dual encoder over content-defined chunks. Chunk boundaries are set by local content, so an insertion does not shift every later chunk, and an edit re-encodes only the one or two affected chunks. We add a separately maintained document-level vector that is re-encoded on a budget. This baseline directly attacks our claim, because it also has bounded update cost. It will use the same backbone size as our encoder (about 62M parameters), the same retrieval training data and pseudo-queries, and the same tuning budget over chunk size and document-vector refresh rate. We beat it only if, at matched update FLOPs per edit, we achieve higher Hits@10 and MRR@10 on queries that need cross-chunk or document-level context, while not losing on queries that target the edited span itself.
For the parametric family we run IncDSI, treating an edit as deletion of the old document vector followed by constrained insertion of a new one. Its reported result is Hits@1 of 62.0 on newly added documents in the NQ320K streaming setting, versus 48.0 for DPR. We expect to approximately reproduce this append number on our NQ320K split before the edit experiments. For edits, we found no reported result on Lacuna for IncDSI or any other generative retriever. MEVI is a further append-friendly reference: it reports +3.62% MRR@10 over AR2 on MS MARCO passage. We will run it with edited documents reassigned to clusters by their new embeddings.
Three ablations isolate the key ingredient. The first replaces the windowed scorer with Fast-R2D2's global BiLSTM. Retrieval quality should be similar, but locality should vanish and recomputation should approach the whole tree. The second removes the depth penalty, to measure how much collapse inflates $d$. The third keeps the local tree repair but skips ancestor recomposition, leaving high-level nodes stale. This shows whether recomputing the path to the root is what preserves quality.
Why not just…?
Why not just re-encode the whole edited document with a Transformer? For short passages this wins, and we will report the crossover length honestly. The argument is about long documents. The file notes that document-level structure at $n>1000$ is where cost explodes, and re-encoding scales at least linearly per edit while our cost scales with $w \cdot d$. The experiment plots update cost and quality against document length, and if the crossover lies beyond typical document lengths in our edit streams, the efficiency half of the claim fails.
Why not just chunk the document and re-embed the affected chunk? This is the real threat, and we treat it as the main baseline rather than a straw man. Chunking already gives local updates. Its weakness is that each chunk sees no context beyond its boundaries, and any document-level vector it adds must be refreshed with full re-encoding. The tree index offers spans at every scale with exact locality for all of them. If content-defined chunking plus a periodically refreshed document vector matches us at equal update cost, then the tree adds nothing for retrieval. We would then report that, and the contribution narrows to exact deletion and multi-granularity indexing.
Why not just extend IncDSI or DSI++ with delete-then-reinsert? A parametric index entangles documents in shared weights, which the file's forgetting results from DSI++ make clear. Removing one document's associations has no exact counterpart there, while in a node index deletion is exact by construction. We still run delete-then-reinsert IncDSI because its append quality is strong, and we measure both the drop on untouched documents after many edits and the residual retrievability of deleted content.
Why not just use a linear-time sequence-labeling parser instead of trees? We already avoid cubic parsing at indexing time, so speed is not what trees buy here. What trees buy is the bottom-up dependency structure that bounds edit propagation. Labeled flat sequences, as in Dependency Graph Parsing as Sequence Labeling, do not give a composition order with that property.
Proposed Experiments
The file contains no benchmark for document edits, so we will construct one. We take the Wikipedia articles underlying NQ320K and the MS MARCO passages behind CDI-MS. Over these we apply edit streams of three kinds: real revision pairs extracted from Wikipedia revision history for the NQ articles, and synthetic sentence insertions, deletions, and substitutions with controlled locality. Queries for edited content are generated on the post-edit text with docTTTTTquery (15 per document, as in IncDSI) and filtered to those answerable only after the edit. Queries for untouched content are the original NQ and MS MARCO queries. Append-only behavior is checked on CDI-MS, where CLEVER reports 43.75% MRR@10 after four sessions against 34.93% for naive fine-tuning. Parser sanity is checked by unsupervised F1 on WSJ against Fast-R2D2's 57.22, where a small drop is acceptable if locality is gained.
The metrics are Hits@1, Hits@10, and MRR@10, reported separately for edited-content queries, untouched-content queries, and deleted-content queries (lower is better). Alongside them we report recomputed node count, FLOPs, and wall-clock time per edit, and the number of index entries rewritten.
The decisive checks are three. First, observed recomputation per edit should fit $w \cdot d$, and $d$ should stay near logarithmic with the depth penalty and visibly grow without it. Second, at matched update FLOPs, the tree index should beat content-defined chunking on queries requiring context beyond a single chunk, while staying within a small margin of the full-re-encode oracle across a stream of thousands of edits. Third, the global-scorer ablation should match quality but lose locality, confirming that the bounded window, not the tree alone, is responsible for cheap updates. If the second check fails, the proposal reduces to an exact-deletion index, and we will say so.
References
- IncDSI: Incrementally Updatable Document Retrieval
- DSI++: Updating Transformer Memory with New Documents
- Continual Learning for Generative Retrieval over Dynamic Corpora
- Model-enhanced Vector Index
- A Dense Subset Index for Collective Query Coverage
- Interactive Incremental Chart Parsing
- Fast-R2D2: A Pretrained Recursive Neural Network based on Pruned CKY for Grammar Induction and Text Representation
- Probability Distribution Collapse: A Critical Bottleneck to Compact Unsupervised Neural Grammar Induction
- Dependency Graph Parsing as Sequence Labeling