java-topology/whitepaper/outreach/langchain-0002.md

LangChain — CWE-407 Disclosure Brief (langchain-0002)

2026-04-13 · Patch available — awaiting upstream merge

Finding

One O(D²) defect in LangChain's MultiQueryRetriever. The _unique_documents() function uses not in documents[:i] for deduplication, creating a slice copy and performing a linear scan for each document, producing O(D²) time and memory.

The Defect

langchain-0002 (PATCHED — MEDIUM): libs/langchain/langchain_classic/retrievers/multi_query.py:44

def _unique_documents(documents: Sequence[Document]) -> list[Document]:
    return [doc for i, doc in enumerate(documents) if doc not in documents[:i]]

For each document at index i, documents[:i] creates a new list slice (O(i) allocation) and not in scans it (O(i) comparisons). Total: O(D²) time and O(D²) memory from slice copies. With Q queries and k results per query, D = Q*k total documents.

Complexity Proof

At D=500 documents (5 queries × 100 results):

• Defective: 500 × 250 (avg) = 125,000 comparisons + 125,000 list elements allocated
• Fixed: 500 × O(1) set lookups = 500 operations
• ~250× op reduction.

Impact

LangChain's MultiQueryRetriever generates multiple query variations and merges results. It fires on every RAG query when multi-query mode is enabled. High retrieval counts across multiple query variants produce large document lists that hit the quadratic dedup.

The Fix

Build a hashable proxy key from each document and use a set for O(1) dedup:

# After
seen: set[tuple] = set()
result: list[Document] = []
for doc in documents:
    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

Fix available: defects/langchain-0002/patch/langchain-0002-multi-query-unique-documents-quadratic.patch

Single-file patch in multi_query.py. ~250× speedup at 500 documents.

What We Ask

A patch is ready for review.

1. Confirm receipt and assign a GitHub issue reference (langchain-ai/langchain).
2. Assess severity — fires on every multi-query RAG retrieval.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the LangChain team in the public disclosure. Preferred acknowledgment format welcome.

Contact: see cover email. This brief is confidential until coordinated disclosure.