When a multimodal model loses one of its inputs, say the audio track drops out or an image fails to load, the input that remains usually still says something useful, just less precisely. Text alone might establish that a dish is "some kind of noodle soup" without identifying which one. A spoken utterance with no video might establish that the speaker is "negative" without settling between mildly and strongly negative. Current systems cannot keep that intermediate answer. Imputation methods invent the missing features and then commit to a single class. Evidential fusion methods keep an explicit "I don't know" amount, but they can only spread belief over individual classes plus one catch-all bucket for total ignorance. We propose having each modality place belief directly on groups of classes arranged as a tree. A modality commits exactly as far down the tree as its evidence supports, and a missing modality contributes nothing at all.
This design is only practical because of a result from the complexity theory of Dempster-Shafer theory. In that theory, evidence is expressed as belief placed on sets of classes rather than on single classes, and pieces of evidence are merged with Dempster's rule of combination. Merging general set-valued evidence exactly is #P-hard, yet it becomes polynomial when every set carrying belief fits into a single tree, meaning any two such sets are either nested or disjoint (Using hierarchies to efficiently combine evidence with Dempster's rule of combination). A family of sets with this nested-or-disjoint property is called laminar. Our central observation is that laminarity survives having members removed and survives intersection. So if the union of all modalities' belief-carrying sets is laminar, exact fusion stays cheap under every one of the $2^M$ patterns of which modalities are missing, where $M$ is the number of modalities. That complexity guarantee comes with no approximation. The research question is whether this expressiveness, which is guaranteed to be tractable, buys real accuracy and calibration under missingness compared with much simpler alternatives.
Core Claim
A deep evidential head that outputs belief over the nodes of a laminar class family, whether a given taxonomy or one learned from the modalities' own confusions, fuses modalities exactly in time $O(M \cdot |T| \cdot d)$, where $|T|$ is the number of tree nodes and $d$ the tree depth. It needs no imputation. Our hypothesis is that at high missing rates it gives a better trade-off between accuracy and how often the model answers than the two existing extremes. One extreme is singleton-only evidential fusion (Trusted Multi-View Classification). The other is imputation-based recovery (API: Adaptive Prototype Imputation for Incomplete Multimodal Sentiment Analysis; MoRA: Missing Modality Low-Rank Adaptation for Visual Recognition).
The fusion step is concrete. For tree nodes $A$ and belief assignments $m_1, m_2$, meaning the amount of belief each modality places on each node, Dempster's rule gives
$$m_{1\oplus 2}(A) = \frac{1}{1-K}\sum_{B\cap C=A} m_1(B)\,m_2(C),$$
where $K$ is the total product mass on pairs of nodes that are disjoint, i.e. the amount of conflict between the two modalities. Two nodes in a tree either intersect in the deeper of the two or do not intersect at all. So each sum involves only ancestor-descendant pairs, and the fused result again lives on the tree.
A missing modality is given $m(\Theta)=1$: all of its belief sits on the whole set of classes $\Theta$, which is the root of the tree. This is the identity element of the rule, so dropping a modality is handled exactly rather than by feeding zeros through an encoder. We treat this identity property as a known fact. The proposal's contribution lies in the structure the other modalities are allowed to express.
Relation to Prior Work
Three evidential lines supply the pieces, and each stops short of this proposal.
The first is trusted multi-view classification. Trusted Multi-View Classification and its dynamic variant Trusted Multi-View Classification with Dynamic Evidential Fusion map per-view network outputs to belief on the $K$ single classes plus the whole set. They fuse views with a reduced Dempster rule, and they evaluate unreliable views by injecting noise rather than by removing modalities. Their focal structure, meaning the sets allowed to carry belief, is our tree with depth one. The method is therefore a special case of ours and serves as the natural ablation. Later variants add class prototypes (Structure-Aware Prototype Guided Trusted Multi-View Classification) or domain-specific filters and a Gini-based uncertainty (Trusted Multi-View Classification with Expert Knowledge Constraints). Neither changes the singleton restriction.
The second line compresses belief to stay tractable. Focal triplets keep only the top two classes and the whole set (On Combining Multiple Classifiers Using an Evidential Approach). That paper found that adding a third or fourth singleton cost 48% and 78% more time with negligible gain. This finding constrains our design: more singletons are not what helps. It is also why our extra expressiveness is spent on nested groups of classes rather than on more single classes. Graph-based multigranular fusion clusters belief-carrying sets into coarse groups before fusing them with the PCR6 rule, a rule that redistributes conflicting mass proportionally (Graph-Structure-Based Multigranular Belief Fusion for Human Activity Recognition). It reports 0.15 ms against 7.92 ms per fusion on OPPORTUNITY. However, it coarsens after the fact, and it assumes all sensors are present.
The third line supplies the method. The hierarchy paper (Using hierarchies to efficiently combine evidence with Dempster's rule of combination) contributes the polynomial-time combination over hierarchies. It also contributes a 2-satisfiability test for whether a collection of sets is hierarchical, and a fixed-parameter-tractable merging algorithm with running time $2^k\cdot\mathrm{poly}$ when the sets are not hierarchical. Here $k$ is the depth of merging needed to force the sets into a hierarchy. That paper was tested only on a symbolic five-disease example and has never been attached to learned models. We reuse its test and its merging procedure as a training-time design step.
On the missing-modality side, imputation and latent-recovery methods motivate the proposal by showing where it hurts. API: Adaptive Prototype Imputation for Incomplete Multimodal Sentiment Analysis documents semantic drift in generated features and reports over 2,200 ms of diffusion latency. CPM-Nets: Cross Partial Multi-View Networks needs per-sample optimization at test time. Calibrated Multimodal Representation Learning with Missing Modalities identifies "anchor shift", the drift in cross-modal alignment caused by missing inputs, and still resorts to imputation to correct it. None of these methods outputs a calibrated coarse answer when the evidence only supports one.
Research Program
The first component is a node-level evidential head. Each modality encoder feeds a head that outputs non-negative evidence for every tree node, including the root. We normalize these outputs into a belief assignment in the subjective-logic style of Trusted Multi-View Classification, with one difference: internal nodes can receive evidence directly. Training uses two terms. The first is an evidential loss on the fused output. The second is a hierarchical term that rewards belief on the true leaf and on its ancestors, and penalizes belief on nodes that do not contain the true class. Without this second term, the head could dump everything on the root. During training we randomly drop modalities at the benchmark's missing rates, and a dropped modality is replaced by its root-only (vacuous) assignment.
The second component builds the tree, and this is where the complexity results do real work. There are three options. The first uses an existing label taxonomy where one exists. The second learns one shared tree by agglomerative clustering of pooled single-modality confusion matrices. The third lets each modality propose its own candidate groups from its own confusions: audio might confuse A with B while vision confuses B with C. The union of these proposals is generally not laminar. We then run the 2-satisfiability test and, where it fails, the vertex-cover-based merging from Using hierarchies to efficiently combine evidence with Dempster's rule of combination to select the largest jointly laminar subfamily. We track the parameter $k$ as a measure of how much the modalities' "natural" groupings disagree.
We also study a relaxed variant that keeps a small number of groups violating the hierarchy and fuses them with the $2^k$-cost exact algorithm. This measures what strict laminarity costs in accuracy. The file notes that the known merging algorithm is overly aggressive and inflates $k$. Our measured $k$ values on real learned confusions would be the first empirical data on how large $k$ is in practice.
The third component is decoding and analysis. From the fused belief we compute a set-valued decision: the deepest node whose belief exceeds a threshold, or the node that minimizes a hierarchical cost. We also compute a forced leaf decision using the pignistic transform, which spreads each node's mass evenly over its leaves, for comparison with ordinary classifiers.
Finally, we test the independence concern raised in Trusted Multi-View Classification: jointly trained modalities are correlated, and Dempster's rule double-counts shared evidence. We measure calibration error as a function of how many modalities are present. We then test one inexpensive remedy, learned discounting per missingness pattern. Discounting is Shafer's operation of moving a fraction $\Gamma$ of each modality's mass to the root. It also preserves laminarity.
Baselines
The do-nothing reference is a late-fusion softmax model that replaces a missing modality with zeros. The file documents that this kind of placeholder degrades sharply (MoRA: Missing Modality Low-Rank Adaptation for Visual Recognition; CPM-Nets: Cross Partial Multi-View Networks). We include it only to anchor the scale of all other results.
The strongest missing-modality competitor on sentiment is API (API: Adaptive Prototype Imputation for Incomplete Multimodal Sentiment Analysis). It is fast (46–48 ms), lightweight (about 0.14M extra parameters), and reports F1 of 74.1% on CMU-MOSI at a 70% missing rate and 79.6% averaged across rates. We will train it on the same encoders, splits, and missingness masks as our method, with an equal hyperparameter search budget. Beating it means matching or exceeding 74.1% F1 at 70% missingness when our model is forced to commit to a leaf. Separately, it means strictly dominating API's accuracy-coverage curve when abstention to a coarse node is allowed, with calibration error no worse than API's.
On vision-language benchmarks the strongest competitor is MoRA (MoRA: Missing Modality Low-Rank Adaptation for Visual Recognition). It reports an average improvement of 5.24% across missing scenarios, but no reported result found on Lacuna for its absolute UPMC Food101 accuracy. We will therefore rerun it ourselves on the same frozen backbone.
Two evidential baselines isolate the key ingredient. The first is TMC with singletons plus the whole set, which is our method with the tree flattened to depth one. It uses identical encoders, training, and dropout. Any gain of ours over it is attributable to group-level belief. The second is focal-triplet fusion (On Combining Multiple Classifiers Using an Evidential Approach) applied to the same heads. It tests whether a fixed, cheaper truncation suffices.
On OPPORTUNITY we compare fusion cost and accuracy against multigranular fusion (Graph-Structure-Based Multigranular Belief Fusion for Human Activity Recognition). It reports 90.82% accuracy with full sensors and 0.15 ms per fusion. Beating it means comparable accuracy with full sensors, a smaller degradation as sensors drop out, and fusion time of the same order.
Why not just…?
Why not just drop the missing modality and fuse the rest with TMC? This is our depth-one ablation. It handles absence correctly but cannot say "noodle soup, species unknown". It must either spread belief over single classes or send it to total ignorance. If our tree head does not beat this ablation at high missing rates on set-valued utility, the proposal's central idea fails. The experiments report exactly this comparison.
Why not just use a hierarchical softmax and sum leaf probabilities to get group probabilities, fusing modalities by multiplying their probabilities? This is the most serious threat. It is cheap, it yields probabilities for coarse groups, and it can also be decoded to the deepest confident node. The claimed difference is that a probability over leaves cannot distinguish "evidence for the group but nothing inside it" from "evidence spread evenly over its members". After fusion that distinction changes the answer. A vision modality that picks one member should win cleanly over text that only supports the group, rather than being diluted by text's arbitrary split within the group. Separating these two kinds of uncertainty helped substantially in single-modality recognition: Flexible Visual Recognition by Evidential Modeling of Confusion and Ignorance reports AUROC 90.0 versus 57.3 for softmax at identifying the true class within the candidate set on misclassified samples. That evidence is single-modality, however, and it does not settle the multimodal case. We therefore run this baseline with the same tree, the same encoders, and a tuned temperature. If it matches us, we will report that the belief-function machinery is unnecessary here.
Why not just impute the missing features with API or a generative model and keep a standard classifier? Imputation answers a different question: it always produces a single class. At a 70% missing rate, an imputer is guessing features for which there is no instance-specific evidence, and the drift documented in API: Adaptive Prototype Imputation for Incomplete Multimodal Sentiment Analysis makes its confident errors hard to detect. Our comparison on forced-leaf F1 tests whether we lose anything by not imputing. The comparison on accuracy-coverage and calibration tests whether we gain anything.
Why not just use full power-set fusion with approximation, or multigranular coarsening? Full power-set fusion is #P-hard in general, and approximate coarsening after the fact gives no guarantee across missingness patterns. The relaxed variant with a bounded number of hierarchy-violating groups measures directly how much accuracy strict laminarity gives up.
Proposed Experiments
The primary benchmark is CMU-MOSI, and CMU-MOSEI as a scale check, with missing rates from 10% to 70% following the protocol of API: Adaptive Prototype Imputation for Incomplete Multimodal Sentiment Analysis. The seven ordered sentiment levels form a natural tree of nested intervals: overall polarity, then polarity strength, then the exact level. This gives a principled hierarchy with no label engineering.
The second benchmark is UPMC Food101 and MM-IMDb under the MoRA missing protocol, at missing rates up to 90%. There the tree is learned from confusion matrices, which exercises the 2-satisfiability and merging step. Because MM-IMDb is multi-label, we treat each genre as a binary two-class tree, and it serves only as a robustness check. We add the partial multi-view datasets CUB, Handwritten, and PIE used by CPM-Nets: Cross Partial Multi-View Networks and Trusted Multi-View Classification. Finally, OPPORTUNITY with simulated sensor dropout supports the timing comparison.
We report metrics in four groups. The first is forced-leaf accuracy and F1. The second is the accuracy-coverage curve, with coverage counted as the fraction of predictions made at the leaf level. The third is a hierarchical set-valued utility that pays partial credit for a correct coarse node. The fourth is expected calibration error, split by how many modalities are present, alongside per-sample fusion latency and the measured merging parameter $k$.
Three checks decide the outcome. First, at 50–70% missingness our method must beat both the depth-one TMC ablation and the hierarchical-softmax product baseline on accuracy-coverage. Failing against the softmax product would mean the gain comes from the tree, not from belief functions. Second, forced-leaf F1 must stay within noise of API's 74.1% on MOSI at 70% missing, so that the coarse answers are not bought with worse single-class answers. Third, calibration error must not grow with the number of fused modalities once discounting is on. If it does grow, the independence assumption behind Dempster's rule is the binding problem, and fixing it becomes the next project.
As a side result, we will report the distribution of $k$ across datasets. This gives the first evidence on whether the fixed-parameter-tractable regime of Using hierarchies to efficiently combine evidence with Dempster's rule of combination is small enough in practice to be relevant for learned evidence.
References
- Using hierarchies to efficiently combine evidence with Dempster's rule of combination
- Trusted Multi-View Classification
- API: Adaptive Prototype Imputation for Incomplete Multimodal Sentiment Analysis
- MoRA: Missing Modality Low-Rank Adaptation for Visual Recognition
- Trusted Multi-View Classification With Dynamic Evidential Fusion
- Structure-Aware Prototype Guided Trusted Multi-View Classification
- Trusted Multi-View Classification with Expert Knowledge Constraints
- On Combining Multiple Classifiers Using an Evidential Approach
- Graph-Structure-Based Multigranular Belief Fusion for Human Activity Recognition
- CPM-Nets: Cross Partial Multi-View Networks
- Calibrated Multimodal Representation Learning with Missing Modalities
- Flexible Visual Recognition by Evidential Modeling of Confusion and Ignorance