COCO-Tree: Compositional Hierarchical Concept Trees for Enhanced Reasoning in Vision Language Models

AI summary

Overview

• Research area: Computer Vision / Vision-Language Models (VLMs), specifically compositional reasoning and neurosymbolic augmentation of VLMs with LLM-derived concept structures.
• Technical level: Intermediate — the paper assumes familiarity with VLM scoring (e.g., VQAScore), image-caption alignment benchmarks, and basic graph search concepts (breadth-first exploration, greedy vs. beam search).
• Scope: The paper introduces COCO-Tree, a training-free framework that builds LLM-generated hierarchical concept trees for each candidate caption, searches them for a reasoning pathway, and fuses that pathway score with the base VLM's alignment score to improve compositionality across four benchmarks and seven open-source VLMs.

What This Paper Is About

VLMs can often detect the objects and attributes present in an image but fail to understand how those objects relate to one another — for example, distinguishing "the bird eats the snake" from "the snake eats the bird." Existing fixes either rely on prompting tricks inside a single frozen VLM or offload reasoning to much larger external models, which is resource-intensive and often yields no interpretable rationale. COCO-Tree instead decomposes captions into morphological entities, grows a concept tree over them with an 8-billion-parameter LLM reasoner, and uses a beam-search-inspired pathway to produce both a better prediction and an explicit reasoning trace.

Key Contributions

1. COCO-Tree framework: A method that constructs hierarchical concept trees associated with textual inputs and finds reasoning pathways through them to augment VLM outputs.
2. Broad empirical validation: Evaluation on four compositionality benchmarks (Winoground, EqBench, SugarCrepe, ColorSwap) across seven open-source VLMs, reported as a 5–10% increase in compositionality performance over baselines.
3. Two path-finding strategies and ablations: Extensive ablation studies validate each component, and the authors propose two novel pathway selection strategies based on greedy search and beam search.
4. Interpretability demonstration: Using a strong LLM reasoner (GPT-4o as judge), the paper shows that the neurosymbolic reasoning pathways discovered by COCO-Tree improve interpretability.

Main Findings

• Baseline metric selection: On LLaVA-1.5-7B Group Score, VQAScore (29.25 Winoground / 21.75 EqBench) outperforms VisualGPTScore (27.50 / 20.25) and Caption Score (17.50 / 16.75), so VQAScore is adopted as the raw VLM-only baseline.
• Head-to-head against CECE: On 200 randomly sampled Winoground and EqBench examples with LLaVA-1.5-7B and LLaMA-3.1-8B, COCO-Tree reaches 35.00 and 37.50 versus CECE's 32.50 and 34.25 and VQAScore's 29.00 and 24.50.
• Winoground gains: COCO-Tree outperforms all baselines by an average of 5% for the LLaVA family and InstructBLIP-XXL, and by an average of 2% on Qwen and InternVL.
• EqBench gains: Consistent improvement over all baselines across all models, averaging 5–8%.
• ColorSwap gains: Average improvement of 4–6%, achieved on top of already high off-the-shelf numbers.
• SugarCrepe gains: Roughly 2% improvement, on a benchmark where baseline performance is already extremely high, reported as the mean Text Score over all sub-sets.
• Win rates on subsets: A 100% win rate on Winoground labeled subsets and an 89% win rate on SugarCrepe subsets.
• CCoT can hurt: In certain cases CCoT degrades performance relative to VQAScore, which the authors attribute to inaccurate scene graphs generated during first-stage prompting.
• Image-task limitation: Gains on Image scores are more modest than on Text and Group scores, indicating that improved linguistic reasoning alone cannot significantly improve the Image selection task.
• Ablation on tree structure: Increasing tree depth L from 1 to 3 improves performance across models; increasing the splitting factor S improves performance before plateauing; increasing the number of morphological entities M improves performance but increases tree size by two orders of magnitude.
• Ablation on fusion weights: Too low or too high a value of β degrades performance, and intermediate values of α produce the highest performance.
• Interpretability: Rules derived from selected pathways score higher entailment confidence from a GPT-4o judge than captions alone. On Winoground without an image, AND-rules score 0.74, OR-rules 0.81, and captions alone 0.65; combining rules with captions reaches 0.91 (AND) and 0.93 (OR). With images, caption-only reaches 0.92 while combined settings reach 0.98. On EqBench the same ordering holds, with OR-rules giving higher confidence.
• Cost profile: COCO-Tree uses a 2-step process (tree construction and scoring) versus DSG's 3-stage process (Prompt, Tuple, Question), and uses an 8-billion-parameter LLM where CECE requires a 70-billion-parameter LLM; the upper bound of time complexity is O(MSL).
• Reported headline improvement: The abstract states a 5–10% improvement in compositional generalization over baselines; the conclusion states an average improvement of 10% across multiple open-source VLMs.

Methodology in Plain English

The approach adds a slow, symbolic "System-2" reasoning layer on top of a fast, opaque "System-1" VLM prediction, then fuses the two.

1. Semantic Morphological Decomposition (SMD): Each candidate caption is split into M structurally discrete, non-overlapping phrases that each preserve the caption's meaning. For the bird/snake example, the entities computed are "bird eats" and "snake gets eaten."
2. Recursive Concept Exploration (RCE): Starting from each morphological entity, the LLM generates semantically related visual concepts entailed by the root caption, expanding breadth-first. A splitting factor S controls how many children each node spawns, and L controls the tree depth.
3. Composite Vision-Language Score: Every node gets a score that blends linguistic relevance with visual grounding: C_S(n^l) = α·L_S(n^l, C) + (1−α)·V_S(I, n^l). The visual score V_S is the VLM's probability of answering "yes" to whether the concept is present in the image; the linguistic score L_S is the LLM's probability of non-contradiction between two text inputs.
4. Dynamic Path Selection: A path is a chain from a morphological entity down the tree. The greedy variant picks each next node by its highest composite score; the beam variant keeps k highest-scoring nodes and then takes the path with the maximum total path weight.
5. Fusion: The final output is β·f(I, C) + (1−β)·W_p, where f(I, C) is the original VLM alignment score and W_p is the selected path weight. β controls how much the System-2 reasoner influences the VLM output.
6. Interpretability: Nodes along a selected path are chained using AND (∧) or OR (∨) operations to form a neurosymbolic rule, which a GPT-4o judge scores for entailment.

Implementation settings: the LLM reasoner is instruction-tuned LLama-3.1-8b (8 billion parameters) with temperature 0; M = 2, S = 3, L = 3. Tuned hyperparameters are α = 0.6 and β = 0.8 for Winoground and EqBench, and α = 0.5 and β = 0.8 for ColorSwap. Tuning used 1000 random samples from the EqBench (Light) subset (disjoint from test) plus the ColorSwap train set.

Models tested span four families: InstructBLIP-XXL, LLaVA, Qwen, and InternVL, in 8-billion-parameter settings (LLaVA-1.5-7b, LLaVA-1.6-7b, Qwen-7b, InternVL-8b) and a 13-billion-parameter range (InstructBLIP-XXL, LLaVA-1.5, LLaVA-1.6).

Why This Matters

Impact on research. The paper argues that many VLMs behave like "a bag of visual words" rather than true reasoners, and that VLM pre-training on image-caption pairs causes catastrophic forgetting of linguistic reasoning, since similarly sized LLMs built into VLMs often outperform them at language understanding. COCO-Tree shows that a modest, similarly sized LLM reasoner plus symbolic search can recover a meaningful portion of that lost reasoning without retraining the VLM, and it produces explicit rationales — addressing a key criticism that prior LLM-augmented approaches are either resource-intensive or not interpretable.

Real-world applications:

• Medical imaging, where misreading relational context (which structure contains or surrounds which) has safety consequences.
• Industrial safety monitoring, where attributing the wrong action to the wrong object can lead to incorrect alerts or missed hazards.
• Image retrieval and caption verification systems that must distinguish near-identical captions differing only in word order or attribute binding.
• Assistive or accessibility captioning, where an interpretable rationale for a caption decision supports auditing and trust.

Industry relevance. The method requires no fine-tuning of the base VLM and is positioned as a resource-constrained "Multiple" setting where only an LLM comparable in scale to the VLM is needed at inference. That makes it relevant to teams deploying open-source VLMs who cannot afford a 70-billion-parameter reasoning model, though the authors acknowledge that maintaining VLM feature maps plus a breadth-concept tree scales exponentially and limits edge deployment.

Future Directions

• Mitigating hallucinated concepts: Because every node is generated by a frozen LLM, spurious concepts can enter the tree and be weighted into the final score; refining filtering and scoring to catch these is an open problem.
• Reducing memory and inference cost: The joint search runs a VLM forward pass for each candidate, and tree memory scales exponentially, which the authors flag as a barrier to edge deployment and a target for future efficiency work.
• Extending beyond two-entity compositionality: Current benchmarks are designed primarily to test relations between two entities; the method is claimed to generalize to an arbitrary number of entities but may underperform there.
• Broadening to other vision-language tasks: The authors state future work will refine the neurosymbolic structures and extend applicability beyond the compositionality benchmarks studied here.

Target Audience

Researchers and engineers working on vision-language models, compositional reasoning, and neurosymbolic or concept-based AI who want a training-free augmentation technique that improves compositionality while producing an inspectable reasoning trace. It is also useful for practitioners evaluating open-source VLMs under compute constraints, and for readers interested in interpretability methods that convert model predictions into inspectable logical rules. Beginners will find the notation and search formalisms demanding, so some prior exposure to VLM benchmarking is helpful.

Authors’ abstract

Compositional reasoning remains a persistent weakness of modern vision language models (VLMs): they often falter when a task hinges on understanding how multiple objects, attributes, and relations interact within an image. Multiple research works have attempted to improve compositionality performance by creative tricks such as improving prompt structure, chain of thought reasoning, etc. A more recent line of work attempts to impart additional reasoning in VLMs using well-trained Large Language Models (LLMs), which are far superior in linguistic understanding than VLMs to compensate for the limited linguistic prowess of VLMs. However, these approaches are either resource-intensive or do not provide an interpretable reasoning process. In this paper, we present 'COCO-Tree' - a novel approach that augments VLM outputs with carefully designed neurosymbolic concept trees learned from LLMs to improve VLM's linguistic reasoning. COCO-Tree's beam search-inspired reasoning process boosts compositionality performance and provides a rationale behind VLM predictions. Empirical results on four compositionality benchmarks, Winoground, EqBench, ColorSwap, and SugarCrepe, in seven different open-source VLMs with varying sizes, demonstrate that COCO-Tree significantly improves compositional generalization by 5-10% over baselines.