📘

CHAIR Hallucination Rate

HardVision-Language Models 📚 VLM 1: Vision-Language Models

Problem Statement

Given the object words a VLM produced for each image and the ground-truth objects actually present, compute the two CHAIR hallucination rates and list which objects were hallucinated.

Background

CHAIR (Caption Hallucination Assessment with Image Relevance) measures how often a captioner names objects that are not in the image. It has two variants:

$\text{CHAIR}_i = \frac{\#\{\text{hallucinated objects mentioned}\}}{\#\{\text{all objects mentioned}\}}, \qquad \text{CHAIR}_s = \frac{\#\{\text{captions with} \ge 1 \text{ hallucination}\}}{\#\{\text{captions}\}}$

CHAIR_i is instance-level (how noisy is the average mention) and CHAIR_s is sentence-level (what fraction of outputs are contaminated at all). CHAIR_s is always at least as alarming as CHAIR_i, because one bad word condemns a whole caption.

Three details are load-bearing:

Synonym mapping. Raw caption words are mapped to canonical MSCOCO categories - "man", "woman", "person" all map to person. Words absent from the map are not object mentions at all and are simply dropped.
Deduplicate within a caption. A caption saying "dog" twice mentions one object. Deduplicate after mapping, per caption, so "man" and "woman" in the same sentence count once.
Order. The hallucinated-object list you return must be sorted alphabetically, and unique. A raw Python set has no defined iteration order, so sort it before returning - the same trap that makes hallucination-eval scripts produce different output on different runs.

Your Task

Implement:

def chair_metrics(captions, ground_truth, synonym_map):

Return [chair_i, chair_s, hallucinated_objects] where the first two are floats rounded to 4 decimals and the third is a sorted list of the unique canonical object names that were hallucinated anywhere in the dataset.

Input Format

captions - list of n lists of raw word strings, one list per image
ground_truth - list of n lists of canonical object names present in that image
synonym_map - dict mapping a raw word to its canonical object name

Output Format

[float, float, [str, ...]]

Sample

caps = [["a", "man", "riding", "a", "horse"], ["dog", "dog", "frisbee"]]
gt = [["person", "horse"], ["dog"]]
syn = {"man": "person", "woman": "person", "horse": "horse", "dog": "dog", "frisbee": "frisbee"}
print(chair_metrics(caps, gt, syn))

Output:

[0.25, 0.5, ['frisbee']]

Example:

Input:

caps = [["a", "man", "riding", "a", "horse"], ["dog", "dog", "frisbee"]]
gt = [["person", "horse"], ["dog"]]
syn = {"man": "person", "woman": "person", "horse": "horse", "dog": "dog", "frisbee": "frisbee"}
print(chair_metrics(caps, gt, syn))

Output:

[0.25, 0.5, ['frisbee']]

Reasoning:

Caption 1 mentions person and horse, both present. Caption 2 mentions dog (twice, counted once) and frisbee, which is absent. That is 1 hallucination out of 4 mentions = 0.25, and 1 of 2 captions contaminated = 0.5.

Constraints:

Map every word through synonym_map; words that are not keys are NOT object mentions
Deduplicate canonical objects WITHIN each caption, after mapping
chair_i divides by the total number of (deduplicated) mentions across all captions
chair_s divides by the number of captions
The returned object list must be UNIQUE and SORTED alphabetically - never return a raw set
Return 0.0 for chair_i when there are no mentions at all
Round both rates to 4 decimals

More from VLM 1: Vision-Language Models

Visual Token Pruning by Attention MassHard CHAIR-i and CHAIR-s Hallucination RatesMedium Merge a LoRA Update into the Base WeightMedium QLoRA Memory Footprint EstimateMedium POPE Precision, Recall, and F1Medium

1. Background Knowledge

The CHAIR (Caption Hallucination Assessment with Image Relevance) metric is a standard evaluation tool in Vision-Language Models (VLMs) used to quantify how often a model generates object mentions that are not present in the corresponding image. Unlike general captioning metrics like BLEU or CIDEr, which measure overall fluency and similarity, CHAIR specifically targets object-level hallucinations. It distinguishes between the frequency of hallucinated words within mentions ( $\text{CHAIR}_i$ ) and the prevalence of hallucinated captions across the dataset ( $\text{CHAIR}_s$ ).

Understanding the distinction between instance-level and sentence-level metrics is crucial. $\text{CHAIR}_i$ calculates the ratio of hallucinated object mentions to total object mentions. This provides a granular view of noise in the model's output. In contrast, $\text{CHAIR}_s$ calculates the ratio of captions containing at least one hallucination to the total number of captions. This is a stricter metric because a single hallucinated word invalidates the entire caption for this score. Consequently, $\text{CHAIR}_s$ is always greater than or equal to $\text{CHAIR}_i$ .

A critical component of this problem is semantic normalization. Raw text outputs from VLMs are noisy and inconsistent (e.g., "man", "woman", "person"). To evaluate hallucinations accurately, these raw tokens must be mapped to a canonical set of categories (like MSCOCO classes) using a provided synonym_map. Words not present in this map are ignored, as they are not considered object mentions. Furthermore, deduplication is required per caption to ensure that repeated mentions of the same canonical object (e.g., "dog" appearing twice) are counted only once.

2. Algorithm Approach

The core algorithmic pattern here is set-based comparison with preprocessing. The problem can be decomposed into three main phases: normalization, comparison, and aggregation.

Normalization: Iterate through each caption, mapping raw words to their canonical forms using the synonym_map. Filter out words that do not have a mapping.
Deduplication: Convert the list of canonical objects for each caption into a set to remove duplicates. This ensures that multiple mentions of the same object are treated as a single mention.
Comparison: For each caption, compare the set of mentioned canonical objects against the set of ground-truth objects. Identify the difference (mentioned but not in ground truth) to find hallucinations.
Aggregation: Accumulate the counts of total mentions, hallucinated mentions, and captions with hallucinations across all images. Finally, collect all unique hallucinated objects into a global set.

This approach leverages set operations (specifically set difference) to efficiently identify hallucinations. Using sets also naturally handles the deduplication requirement.

3. Step-by-Step Strategy

Initialize Counters: Create variables to track total_mentions, hallucinated_mentions, captions_with_hallucinations, and a global set for all_hallucinated_objects.
Iterate Through Data: Loop through each index i from 0 to n-1 (where n is the number of captions).
Process Caption:

Extract the raw words for the current caption.
Map each word to its canonical form using synonym_map. If a word is not in the map, skip it.
Store the resulting canonical objects in a set to deduplicate. Let's call this mentioned_set.

Process Ground Truth:

Convert the ground-truth list for the current image into a set called gt_set.

Identify Hallucinations:

Compute the set difference: hallucinated_set = mentioned_set - gt_set.
If hallucinated_set is not empty, increment captions_with_hallucinations.
Add all elements from hallucinated_set to all_hallucinated_objects.
Add the size of hallucinated_set to hallucinated_mentions.
Add the size of mentioned_set to total_mentions.

Calculate Metrics:

Compute $\text{CHAIR}_i = \frac{\text{hallucinated\_mentions}}{\text{total\_mentions}}$ . Handle division by zero if total_mentions is 0.
Compute $\text{CHAIR}_s = \frac{\text{captions\_with\_hallucinations}}{n}$ .

Format Output:

Round both metrics to 4 decimal places.
Convert all_hallucinated_objects to a sorted list.
Return [chair_i, chair_s, sorted_hallucinated_objects].

4. Common Pitfalls

Incorrect Deduplication Timing: Deduplication must happen after synonym mapping. If you deduplicate raw words first, "man" and "woman" might both remain, but after mapping they both become "person". If you don't deduplicate after mapping, you might count "person" twice, inflating the denominator for $\text{CHAIR}_i$ .
Ignoring Non-Object Words: Words not in synonym_map (like "a", "the", "riding") should be completely ignored. Including them in the mention count will skew the metrics.
Set Order Issues: Python set objects are unordered. When returning the list of hallucinated objects, you must sort them alphabetically. Returning a list directly from a set will result in non-deterministic order, causing test failures.
Division by Zero: If a dataset has no object mentions at all (empty captions or no mapped words), total_mentions will be 0. Ensure your code handles this edge case to avoid ZeroDivisionError. Typically, the metric should be 0.0 in this case.
Floating Point Precision: Ensure you round the final results to exactly 4 decimal places as specified. Using round(value, 4) is standard.

5. Time & Space Complexity

Let $N$ be the number of captions, $M$ be the average number of words per caption, and $K$ be the average number of ground-truth objects per image.

Time Complexity: $O(N \cdot (M + K))$ .
For each of the $N$ captions, we iterate through $M$ words to map and deduplicate.
We then perform set operations (difference) which take time proportional to the size of the sets, roughly $O(M + K)$ .
Sorting the final list of hallucinated objects takes $O(H \log H)$ , where $H$ is the number of unique hallucinated objects. Since $H$ is bounded by the vocabulary size, this is generally negligible compared to the iteration over captions.
Space Complexity: $O(N \cdot M + H)$ .
We store intermediate sets for each caption, which take $O(M)$ space.
We store the global set of hallucinated objects, which takes $O(H)$ space.
The input data itself takes $O(N \cdot M)$ space.

This approach is efficient and scales linearly with the size of the input dataset, making it suitable for large-scale VLM evaluation.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.