Do embedding dimensions fundamentally limit retrievable document combinations?

"On the Theoretical Limitations of Embedding-Based Retrieval" (2508.21038) establishes that single-vector embedding retrieval has a fundamental mathematical ceiling, not just an empirical one. Using results from communication complexity theory and geometric algebra, the paper proves that for a given embedding dimension d, there exists a maximum number of top-k subsets of documents that can be returned as the result of any query. Beyond this limit, no training data, model architecture, or optimization strategy can help.

The empirical validation is striking. Even when embeddings are directly optimized on test data with free parameters (no model constraints whatsoever), there exists a critical point for each embedding dimension where the number of documents overwhelms the representational capacity. This relationship follows a polynomial function of d. The proof holds for k=2 — the simplest non-trivial retrieval case.

The LIMIT dataset makes this concrete: trivially simple natural language tasks ("Who likes Apples?" with "Jon likes Apples, ...") defeat state-of-the-art embedding models when document combinations exceed dimensional capacity. The simplicity of the task is the point — failure isn't due to semantic complexity but to geometric impossibility.

This connects to Do vector embeddings actually measure task relevance? at a deeper level. The semantic-vs-relevance critique is about what embeddings measure. The LIMIT finding is about what embeddings CAN'T measure regardless of training — a geometric constraint that exists independent of the training objective. Even a perfect embedding model trained for exact task relevance would hit this wall.

For Why does retrieval-augmented generation fail in production?, this provides the theoretical foundation for the first failure axis (embedding inadequacy). The practical implication: as instruction-based retrieval pushes models to handle more diverse query types and relevance definitions, the combinatorial explosion of top-k possibilities will increasingly collide with dimensional limits. This is especially acute for What do enterprise RAG systems need beyond accuracy?, where heterogeneous knowledge bases with domain-specific terminology multiply the document combinations that must be representable. Cross-encoders or multi-vector models are architecturally necessary, not just empirically better.

Cross-domain KG foundation models as partial escape. UniGraph proposes a cross-domain foundation model for knowledge graphs that transfers across different KG structures. Rather than training separate embeddings per domain, a unified representation enables zero-shot transfer to unseen KGs. This is relevant because it suggests the dimensional limit may be partially addressable by enriching embeddings with structural KG information rather than increasing raw dimension — using relational structure to disambiguate what flat embedding geometry cannot distinguish.

Source: LLM Architecture; enriched from Knowledge Graphs