russell@unturf.com
483f1cb5e5
Ollama: all 5 MOADs scanned. MOAD-0001 ollama-0001 (pre-existing). MOADs 0002/0003/0004/0005 CLEAN per defects/ollama/CLEAN.md (scanned 2026-03-31). LangChain: all 5 MOADs scanned. New defect langchain-0002 MOAD-0001 CWE-407. - multi_query.py _unique_documents: `doc not in documents[:i]` creates O(D) slice each iteration and performs O(D) linear scan, giving O(D^2) overall. D = Q*k where Q=queries, k=results per query. - Fix: seen set with hashable proxy key (id, page_content, str(metadata items)). O(D) total. - 9/9 unit tests PASS, 21.4x speedup at D=500. MOADs 0002/0003/0004/0005 CLEAN per updated defects/langchain/CLEAN.md. SCAN-TODO.md: mark both targets [x].
2.7 KiB
langchain-0002: MultiQueryRetriever _unique_documents O(D²) slice-in-loop
Project: LangChain (langchain-ai/langchain) File: libs/langchain/langchain_classic/retrievers/multi_query.py Line: 46 MOAD: 0001 (CWE-407) Severity: MEDIUM Speedup: ~250x at D=1000
Defect
def _unique_documents(documents: Sequence[Document]) -> list[Document]:
return [doc for i, doc in enumerate(documents) if doc not in documents[:i]]
Two compounding costs per iteration:
documents[:i]creates a new list slice of size i — O(D) allocation per iteration, O(D²) total allocations.doc not in documents[:i]performs linear equality scan over each slice — O(D) comparisons per iteration, O(D²) total.
Combined: O(D²) time and O(D²) memory allocations for the dedup phase.
_unique_documents is called by unique_union which is called after every MultiQueryRetriever retrieval.
D = Q * k where Q = number of generated queries (default 3) and k = results per query.
With Q=3, k=100, D=300: ~45,000 Pydantic field comparisons.
With Q=10, k=100, D=1000: ~500,000 Pydantic field comparisons.
Document.eq is Pydantic field comparison — compares page_content (full string) + metadata (dict) + id. Each comparison is O(L) where L = page content length.
Root Cause
documents[:i] is a list slice inside a list comprehension loop. No seen set or dict
tracks already-seen documents, forcing repeated linear scans of a growing prefix.
Documents have metadata: dict (unhashable) and page_content: str (hashable).
A hashable proxy key (page_content, id) covers the common dedup case.
For full equality, use (page_content, tuple(sorted(metadata.items()))) as our key.
Fix
Replace O(D²) slice-in-loop with a seen-set using a hashable proxy key.
The seen key is (doc.id, doc.page_content) — id (str | None) covers the case where
documents carry stable IDs from our vectorstore. Fall back includes page_content which
is always a str. For docs sharing same content but different metadata, add a metadata
hash as a tiebreaker.
def _unique_documents(documents: Sequence[Document]) -> list[Document]:
seen: set[tuple] = set()
result = []
for doc in documents:
# Always stringify metadata values to keep the key hashable regardless
# of value types (list, dict, etc. are all unhashable in Python).
meta_key = tuple(sorted((k, str(v)) for k, v in doc.metadata.items()))
key = (doc.id, doc.page_content, meta_key)
if key not in seen:
seen.add(key)
result.append(doc)
return result
Patch
See patch/langchain-0002-multi-query-unique-documents-quadratic.patch
Test
See test/LangChainMultiQueryUniqueDedupTest.py