Human intelligence excels at compositionality. If you know what a "dog" looks like and you know what the adjective "purple" means, you can instantly imagine or recognize a "purple dog," even if you have never seen one.
In computer vision, this ability is studied under Compositional Zero-Shot Learning (CZSL). Traditionally, models are trained on a set of attribute-object pairs (e.g., ripe apple, peeled banana) and tested on a distinct, unseen set of pairs (e.g., peeled apple). However, standard benchmarks make a massive, unrealistic assumption: they operate in a "closed world" where the exact list of unseen test pairs is known beforehand.
In a true open-world scenario, this safety net vanishes. An agent must navigate an unconstrained environment where any attribute could theoretically combine with any object. This shift triggers a catastrophic problem: combinatorial search space explosion.
The Open-World Explosion
When we transition to Open-World CZSL (OW-CZSL), the inference search space expands to the full Cartesian product of all available attributes and objects. As Massimiliano Mancini et al. demonstrate in their foundational work on Open World Compositional Zero-Shot Learning, removing artificial constraints forces a model to evaluate every single permutation.
If a vocabulary contains a few hundred attributes and a few thousand objects, the number of potential combinations scales quadratically into the millions. As Hirunima Jayasekara et al. point out in their Unified Framework for Open-World Compositional Zero-shot Learning, the vast majority of these generated pairs are physically or logically impossible. You end up with an overwhelming influx of nonsensical distractor classes such as ripe dog, steaming necklace, or metallic water.
Closed-World Search Space (Curated Pairs)
[Ripe Apple] [Peeled Banana] [Peeled Apple]
Total: ~Hundreds of valid pairs
Open-World Search Space (Full Cartesian Product)
Attributes × Objects ──> [Ripe Apple] [Peeled Apple] ...
──> [Ripe Dog] [Steaming Necklace] [Fractured Water]
Total: Millions of pairs (mostly nonsense)
This problem is not confined to simple attribute-object pairs. It manifests whenever models compose concepts:
- Scene Graph Generation: The potential search space for object-relationship triplets (e.g., subject-predicate-object) grows exponentially, creating millions of invalid combinations that drown out rare, valid relationships (Jiankai Li et al.).
- Egocentric Action Recognition: Pairing open-world actions with arbitrary objects creates an astronomical search space that makes standard video inference computationally intractable without structural constraints (Sanjoy Kundu et al.).
Why Standard Models Predict Nonsense
Why do state-of-the-art Vision-Language Models (VLMs) like CLIP fail so dramatically when the search space explodes?
VLMs typically compute the similarity between an image embedding and a text prompt embedding (e.g., "a photo of a ripe dog"). If an image contains a dog sitting in golden, warm sunlight, the visual features might strongly align with the independent text primitive "ripe" (which shares statistical overlap with warmth, maturity, or golden colors). Because the model evaluates statistical correlation rather than semantic feasibility, it assigns a high probability to the impossible composition.
As Zhaoheng Zheng explains in the context of CAILA, these models lack internal common-sense constraints. They cannot inherently distinguish between a concept that is unseen but plausible (e.g., "purple apple") and one that is logically impossible (e.g., "ripe dog"). To fix this, the field has shifted toward Feasibility Filtering—mechanisms designed to prune the search space before or during visual classification.
Mechanisms of Feasibility Filtering
The core intuition behind feasibility filtering is simple: decouple visual feature matching from common-sense reasoning. By assigning a "feasibility score" to every potential combination in the Cartesian product, we can mask out or penalize nonsensical pairs, reducing the open-world search space back to a manageable set of realistic candidates.
Researchers have developed three primary paradigms to achieve this.
1. Graph-Based Relational Propagation
One way to determine if an unseen pair is plausible is to look at its conceptual neighbors. In Learning Graph Embeddings for Open World Compositional Zero-Shot Learning, Massimiliano Mancini et al. introduce a framework called Co-CGE that uses Graph Convolutional Networks (GCNs).
The graph treats attributes and objects as nodes, and known, valid compositions from the training set as edges. The GCN propagates embeddings through this network. If an unseen combination (e.g., steaming necklace) is structurally isolated or distant from known valid relationships in the graph, the model computes a low feasibility score for it. During inference, this score acts as a prior that suppresses the impossible class, preventing false positives.
2. External Knowledge Bases and LLM Oracles
Instead of forcing a model to learn feasibility entirely from a limited vision dataset, we can inject external world knowledge. Early symbolic attempts, such as the system designed by Georgios Tagalakis et al., used information retrieval metrics like $tf-idf$ on text corpora to rank the "diagnosticity" and practical utility of concept combinations.
Today, this external knowledge is harvested directly from Large Language Models (LLMs). In Feasibility with Language Models for Open-World Compositional Zero-Shot Learning, Jae Myung Kim et al. demonstrate that LLMs can serve as zero-shot common-sense filters.
[Full Cartesian Product] ──> (LLM Common-Sense Filter) ──> [Pruned Search Space]
(Hundreds of Thousands) "Is 'dark fire' possible?" (Only Plausible Pairs)
"Is 'ripe dog' possible?"
By leveraging in-context learning, the authors prompt an LLM to evaluate the real-world plausibility of hundreds of thousands of candidate pairs. The LLM generates a binary or continuous feasibility mask. When applied to a vision model, this mask filters out the noise of the open world, allowing the system to maintain high accuracy and safely recognize rare but valid visual concepts like dark fire or ruffled chair.
3. Statistical Calibration and Outlier Synthesis
A third approach is to teach the model what "nonsense" looks like by altering its training distribution.
Instead of relying on external text data, Chenchen Jing et al. propose a framework called COMO in Seeing the Unseen: Composing Outliers for Compositional Zero-Shot Learning. During training, the model explicitly synthesizes artificial "outlier" representations that mimic impossible combinations. By forcing the model to classify these synthetic outliers as a generic "invalid" class, it learns a tight decision boundary around seen compositions.
Similarly, Jingcai Guo et al. address this via distribution alignment in TsCA. They use Conditional Transport theory to align three distinct semantic spaces: visual patches, textual primitives, and textual compositions. This geometric alignment naturally penalizes inconsistent or nonsensical pairings because they fail to satisfy cross-modal cycle-consistency constraints.
Summary
Open-world compositionality breaks traditional vision models because it transforms a bounded classification task into an unbounded search problem dominated by noise. Feasibility filtering works because it introduces a logical gatekeeper. Whether through graph structures (Mancini et al.), LLM common sense (Kim et al.), or statistical calibration (Jing et al.), constraining the search space ensures that a model's open-world imagination remains grounded in physical reality.
Key Foundational Work
Open World Compositional Zero-Shot Learning (2021) — contributed 2 concept elements to this direction.
A CLP-Based, Diagnosticity-Driven System for Concept Combinations (2005) — contributed 1 concept elements to this direction.