awslabs / awslabs/graphrag-toolkit
[BUG] Two documents sharing a truncated source id merge into one __Source__ node
- Dominant language
- Python
- Stars
- 442
- Forks
- 106
- Avg merge
- 2d 17h
- Merged PRs (30d)
- 52
Description
### Package version
3.19.1
### Package
lexical-graph
### Python version
3.12.13
### Operating System
macOS
### Description
`create_source_id` truncates the text digest to 8 hex characters (`id_generator.py:82`):
```python
return f"aws::{self._get_hash(text)[:8]}:{self._get_hash(metadata_str)[:4]}"
```
`IdRewriter` passes `''` for the metadata component when a node carries no metadata (`id_rewriter.py:74`), which makes the second component constant. A corpus loaded without metadata therefore discriminates on 32 bits, and two documents collide sooner than the width suggests.
Every downstream identity derives from the source id: the S3 storage prefix, the `__Source__` node the graph MERGEs on, and every chunk, topic, statement and fact id. Nothing detects or reports a collision.
### Reproduction
Hashing sequentially numbered documents until two share a digest takes 30,059 of them:
```python
from graphrag_toolkit.lexical_graph.indexing.id_generator import IdGenerator
A = 'document 27347 body text'
B = 'document 30059 body text'
g = IdGenerator()
assert A != B
assert g.create_source_id(A, '') == g.create_source_id(B, '') == 'aws::a4439cdb:d41d'
```
Both documents then land under one S3 prefix. `S3DocDownloader._download_doc` merges every object under a prefix into one `SourceDocument`, so the pair reads back as a single document holding both their chunks. In the graph, `source_graph_builder.py:79` is `MERGE (source:__Source__ {sourceId: params.sourceId})`, which attaches both to one node.
### Impact
Retrieval returns chunks belonging to a different source, and the two documents cannot be distinguished. Nothing is logged and no error is raised, so a merged document cannot be told apart from a correct one.
Measured with a generator that reproduces `IdGenerator` exactly, metadata absent:
| Documents | Colliding pairs |
|---|---|
| 100,000 | 1 |
| 1,000,000 | 127 |
| 10,000,000 | 11,762 |
With metadata present nothing collided at 10M, but 48 bits is that path's ceiling and 10M carries a 16% chance of at least one collision.
### Why the configurable width does not close this
#517 made the digest width a configuration setting and left the default at 8, so a default deployment behaves as it did before.
Truncating to a larger width lowers the probability but does not remove the case. Two changes are under consideration:
1. Stop truncating and use the full digest. `MAX_SOURCE_ID_HASH_LENGTH` is already 32, and `_create_node_id` already uses the full digest for entity, topic, statement and fact ids. Source and chunk ids are the only truncated ones.
2. Raise an error when two different documents resolve to one id, instead of merging them.
Widening changes every source id and chunk id, so a graph written at one width cannot be read at another. Chunk text is unaffected, so a re-ingest reproduces the same chunks under new ids rather than re-chunking the corpus.
### Notes
The 32-bit case is not the original design. `_new_doc_id` previously passed `node.doc_id` as the metadata fallback, so a document with no metadata still received a distinct second component. Commit `21dadffc` changed that fallback to the empty string so that ids are deterministic across runs. That was correct, because `doc_id` is loader-assigned and varies between runs, but it halved the discriminating width whenever metadata is absent.
Related: #325 (document-level extraction manifest, which needs storage identity to be unique), #517 (the configurable width).
Contributor guide
Research direction
Start with create_source_id in id_generator.py:82 and the empty-metadata path in id_rewriter.py:74, then trace S3DocDownloader._download_doc and the MERGE in source_graph_builder.py:79. Reproduce the collision using the documents in the issue and review #517 and the two proposed approaches. Done means collisions are handled deliberately, covered by regression tests, and cannot silently merge distinct documents.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- aws, python
- Domain
- backend, cloud, databases
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100