Paper deep dive
When Are Concept Bottleneck Model Explanations Faithful and Compact?
Stefano Teso, Emanuele Marconato, Steve Azzolin, Antonio Vergari
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Concept bottleneck models (CBMs) are neural classifiers that allow to explain their decisions via high-level concepts, potentially enabling understanding, steering and debugging. However, their explanations are often derived heuristically. Building on formal explainability, we argue they should also be faithful, i.e., not misreport which concepts actually matter. We show that, for widespread CBM architectures, including recent VLM-based variants, faithful explanations must include all concepts in the bottleneck, compromising interpretability when this is large. This result applies to both heuristic and faithful-by-construction formal explanations. To encourage the existence of compact faithful explanations, we suggest i) modeling concepts probabilistically as binary or categorical random variables (rather than logits), and ii) employing per-concept training-time sparsification via group lasso (rather than regular elastic net). We also extend algorithms from formal explainability to CBMs, and show they outperform natural heuristics in terms of guarantees and explanation size. Overall, our work warns against naive interpretability claims and provides formal conditions and practical strategies for ensuring CBMs are as interpretable as advertised.
Tags
Links
- Source: https://arxiv.org/abs/2610.06285v1
- Canonical: https://arxiv.org/abs/2610.06285v1
Trouble viewing inline? Open PDF directly →
Full Text
116,501 characters extracted from source content.
Expand or collapse full text
When Are Concept Bottleneck Model Explanations Faithful and Compact? Stefano Teso Affiliation: CIMeC & DISI Affiliation: University of Trento Email: stefano.teso@unitn.it Emanuele Marconato Affiliation: Department of Mathematical Sciences Affiliation: University of Copenhagen Email: emanuele.marconato@math.ku.dk Steve Azzolin Affiliation: DISI Affiliation: University of Trento Email: steve.azzolin@unitn.it Antonio Vergari Affiliation: School of Informatics Affiliation: University of Edinburgh Email: avergari@ed.ac.uk Abstract Concept bottleneck models (CBMs) are neural classifiers that allow to explain their decisions via high-level concepts, potentially enabling understanding, steering and debugging. However, their explanations are often derived heuristically. Building on formal explainability – we argue they should also be faithful, i.e., not misreport which concepts actually matter. We show that, for widespread CBM architectures, including recent VLM-based variants, faithful explanations must include all concepts in the bottleneck, compromising interpretability when this is large. This result applies to both heuristic and faithful-by-construction formal explanations. To encourage the existence of compact faithful explanations, we suggest i) modeling concepts probabilistically as binary or categorical random variables (rather than logits), and i) employing per-concept training-time sparsification via group lasso (rather than regular elastic net). We also extend algorithms from formal explainability to CBMs, and show they outperform natural heuristics in terms of guarantees and explanation size. Overall, our work warns against naïve interpretability claims and provides formal conditions and practical strategies for ensuring CBMs are as interpretable as advertised. A Preprint 1 Introduction Concept bottleneck models (CBMs) (Koh et al., 2020; Ji et al., 2025; Knab et al., 2026) are “explainable-by-design” neural classifiers that predict high-level concepts (e.g., objects present in an input image) and use these to infer a label (e.g., the image’s class), see Fig. 1 (left). By enabling stakeholders to inspect the set of concept activations – the titular bottleneck – CBMs aim to support interpretation (Bogani et al., 2026), steering (Shin et al., 2023), and interactive debugging (Stammer et al., 2021). Yet, reliable interaction requires CBMs to produce explanations that are both compact (Ramaswamy et al., 2023; Schrodi et al., 2025), thus supporting understanding, and faithful to the CBM’s decision process, so as not to mislead stakeholders (Marques-Silva, 2023; Teso et al., 2023). Neither property is guaranteed in practice. On the one hand, bottlenecks can include hundreds or even thousands (Yang et al., 2023) of activations, well beyond what stakeholders can grasp. The go-to solution is to compute a small explanation – that is, a subset of the bottleneck – ℰE using heuristic algorithms, e.g., by taking the k highest activations, but see Fig. 1 and Section 3 for alternatives (Yuksekgonul et al., 2023; Yang et al., 2023; Oikarinen et al., 2023; Srivastava et al., 2024). On the other, as we will show, heuristic explanations can be unfaithful, i.e., they may misreport which concepts do vs. do not determine the prediction. Specifically, a subset ℰE that supports different predictions is insufficient to justify either (Marques-Silva, 2023; Darwiche, 2023; Soria et al., 2026). To see why, consider the heuristic explanation ℰE in Fig. 1 (right), computed on the CUB bird classification dataset (Wah et al., 2011). It supports predictions for two different classes, Vesper Sparrow and Black-billed Cuckoo. Since the activations in ℰE are identical for both predictions, these cannot be determined by ℰE alone: they must depend on activations outside ℰE. We seek to understand when compact faithful explanations can be obtained. As a first contribution, we demonstrate that this is not always possible: unless a CBM is sufficiently constrained, faithful explanations must include all concepts in the bottleneck, no matter what algorithm is used to compute them. We show that this depends on how a CBM constrains the concept activations and the inference layer mapping concepts to labels and that many existing CBM architectures fail on both fronts. As a second contribution, we discuss two simple but effective strategies that encourage CBMs to admit compact faithful explanations, namely: i) modeling concept activations as probability distributions and not logits; and i) applying structured, rather than unstructured, sparsity to the inference layer via group lasso. As a third contribution, we propose replacing heuristics with algorithms from formal explainability (Marques-Silva, 2023; Darwiche, 2023), which ensure faithfulness, and introduce EA+, an exact algorithm geared for compactness. Our experiments in Section 5 highlight how our modeling strategies enable finding more compact faithful explanations for regular and VLM-based CBMs (Oikarinen et al., 2023; Yang et al., 2023; Debole et al., 2026a) and how EA+ outperforms heuristic alternatives while remaining computationally affordable. Contributions. We: i) Study the faithfulness of CBM explanations, proving that, for many regular and VLM-based CBMs, faithful explanations cannot be compact (Section 4); i) From an algorithmic perspective, extend exact explainers from FXAI that ensure faithfulness to favor compactness (Section 3); i) From a modeling perspective, propose two simple but effective strategies that constrain CBMs to allow more compact faithful explanations (Section 4.2); iv) Present an extensive experimental evaluation showcasing the underlying issues and the benefits of our contributions (Section 5). Figure 1: Current heuristic explanation for CBMs can be unfaithful as shown for a CBM combining a neural backbone generating concept activations ∈ s and a linear inference layer with per-class weights y w_y, with y∈[m]y∈[m]. Left: Standard heuristics compute explanations ℰE by looking at the magnitude of activations, weights, or both, cf. Eq. 2. Right: A heuristic explanation ℰE that covers the k=2k=2 top weights: it justifies two decisions on the ground that the same two activations attain the same values. Yet, the decisions differ: the CBM must be looking at activations outside of ℰE to produce them. Hence, ℰE is insufficient to fully justify either decision. 2 Concept Bottleneck Models Notation. We denote scalar constants in lower-case (x), vector constants in bold ( x), scalar and vector variables in upper-case (X, X), and sets in upper-case italics (X). We abbreviate 1,…,n\1,…,n\ to [n][n] and, given a vector ∈ℝn x ^n, we write ℐ x_I for its restriction to the indices in ℐ⊆[n]I [n]. Concept bottleneck models. CBMs (Koh et al., 2020) are neural classifiers that combine a backbone g:→g:X mapping inputs (e.g., images) ∈ x to a bottleneck of b concept activations ∈ s , and an inference layer f:→ℝmf:S ^m mapping activations to m per-class logits; see Fig. 1 (left). The prediction y^∈[m] y∈[m] is the highest-scoring class. Concept activations s are traditionally modelled as independent logits (Koh et al., 2020; Shin et al., 2023; Park et al., 2025), i.e., ≡ℝbS ^b, and only translated into probabilities for computing the loss. Most commonly, the inference layer is a linear model of the form f()=W+0f( s)=W s+ w_0, where W∈ℝm×bW ^m× b and 0∈ℝm w_0 ^m are parameters. CBMs define a loss for labels and one for concepts: ℓY(f,g):=^(i,yi)[−logp(yi∣i)],ℓC(f,g):=^(i,i)[−1b∑j∈[b]logp(cij∣i)]. ^Y(f,g)\;:=\; E_( x_i,y_i) [- p(y_i x_i) ], ^C(f,g)\;:=\; E_( x_i, c_i) [- 1b _j∈[b] p(c_ij x_i) ]. (1) Here, yi∈[m]y_i∈[m] are task labels and i∈0,1b c_i∈\0,1\^b concept labels; the distributions are p(y∣)=softmax((f∘g)())yp(y x)=softmax((f g)( x))_y and p(cj∣)=sigmoid(g()j)p(c_j x)=sigmoid(g( x)_j); and the expectations are estimated on a densely annotated training set (i,i,yi)\( x_i, c_i,y_i)\. The concept loss aims to align concepts to human semantics, but see Section 6 for a discussion of failure cases. The exact loss depends on whether the model is trained independently (each module fit on corresponding labels), sequentially (backbone fit on concept labels, inference layer on concept predictions), or jointly (end-to-end with a convex combination of the two losses). This backbone-plus-linear-classifier setup acts as a blueprint for most CBM variants – see (Ji et al., 2025; Knab et al., 2026) for overviews – and for other concept-based architectures, like self-explainable (Alvarez Melis and Jaakkola, 2018) and prototype-based (Chen et al., 2019) neural nets. VLM-aided CBMs. Concept supervision is key for ensuring learned concepts are human-aligned (Bortolotti et al., 2025; Fokkema et al., 2025), yet seldom available. For datasets lacking it, “VLM-CBMs” bypass this issue by asking an LLM to generate a concept vocabulary (i.e., textual descriptions of task-relevant concepts) and then obtaining weak concept supervision from a Vision-Language Model (VLM) like CLIP (Radford et al., 2021), typically by measuring the similarity between concept descriptions and images in the VLM’s embedding space (Yuksekgonul et al., 2023; Oikarinen et al., 2023; Yang et al., 2023; Tan et al., 2024a; Kazmierczak et al., 2026; Debole et al., 2026a). These activations are used either to train a backbone or employed directly for inference. 3 Compactness and Faithfulness By decomposing predictions into higher-level concepts, CBMs aim to facilitate mental simulation and reliability assessment (Rudin, 2019; Narayanan et al., 2018; Bogani et al., 2026), human intervention (Shin et al., 2023; Espinosa Zarlenga et al., 2023), and interactive debugging (Stammer et al., 2021; Bontempelli et al., 2023). Reliable interaction, however, requires CBMs to supply stakeholders with concept-level explanations that are both compact – so as to enable understanding – and faithful to their decision process – so as not to mislead stakeholders. Compactness. Taking the whole bottleneck to serve as explanation is rarely useful, as CBM vocabularies can comprise hundreds of entries (Lage et al., 2019; Barker et al., 2023; Schrodi et al., 2025), well beyond what stakeholders can grasp. E.g., the default vocabulary of the CUB bird classification task (Wah et al. (2011), illustrated in Fig. 1, right) comprises 312312 activations, and LLM-generated vocabularies for the same task count up to 10,00010,000 (Yang et al., 2023). Practitioners often construct a smaller explanation by extracting a subset ℰ⊂[b]E⊂[b] of concept activations. Given a prediction (,y^)( s, y) and a target size k<bk<b, three well-known heuristic algorithms for doing so (shown in Fig. 1, middle) are picking the k activations11 1 Alternatively, one can fix a weight, activation, or score threshold τ≥0τ≥ 0. Our results extend to this case. with the highest value (Chen et al., 2019; Ley et al., 2026), the largest-magnitude weights (Yuksekgonul et al., 2023; Yang et al., 2023), or a combination thereof (Oikarinen et al., 2023; Srivastava et al., 2024): ℰ=argtopksi,ℰ=argtopk|wy^,i|,ℰ=argtopk|si⋅wy^,i|.E=argtop_k\s_i\, =argtop_k\|w_ y,i|\, =argtop_k\|s_i· w_ y,i|\. (2) One exception are Selective CBMs (Schrodi et al., 2025), which construct ℰE via gating. These heuristics are sometimes paired with training-time sparsification penalties encouraging CBM predictions to rely only on few concepts. We will detail these and Selective CBMs in Section 4.2. Faithfulness. Another essential requirement is that ℰE covers all and only those concepts that determine the target prediction but not others (Marques-Silva, 2023; Darwiche, 2023). To see why, consider the example in Fig. 1 (right): despite covering the k=2k=2 highest-weight activations (as per Eq. 2), ℰE supports predictions for two different classes, Vesper Sparrow and Black-billed Cuckoo. Since the same activations within ℰE are compatible with different predictions, the predicted class cannot be determined by ℰE alone, but it must depend on activations outside ℰE. In other words, ℰE is insufficient to fully justify either decision. Unfaithful explanations ℰE can mislead users, compromising model assessment and reliable interaction. As illustrated by the example above, the core requirement for a faithful explanation is that ℰE cannot simultaneously back up predictions for different classes (Shih et al., 2018; Ignatiev, 2020). Surprisingly, this aspect has been off the radar in the CBM literature, and the go-to heuristics from Eq. 2 have been implicitly assumed to be faithful. We show this is not the case. Following the FXAI literature, explanations satisfying this requirement are called abductive explanations22 2 Aka sufficient reasons (Shih et al., 2018) and prime implicant explanations (Ignatiev et al., 2019). ( AXps) (Marques-Silva, 2023), which we extend to CBMs as follows: Definition 1. Given a CBM (g,f)(g,f), a prediction (,y^)( s, y), and a set of attainable concept activation vectors S, then ℰ⊆[b]E [b] is said to be a weak AXp for y y with respect to S if and only if ∀′∈.(ℰ′=ℰ)⟹(y^∈argmaxy∈[m]f(′)y). ∀ s \;.\; ( s_E = s_E )\; \; ( y∈ _y∈[m]f( s )_y ). (3) A weak AXp that is also subset-minimal (s.t. no proper subset ℰ′⊂ℰE is a weak AXp), is an AXp. The definition requires sufficiency – an adversary cannot construct any counterexample ′∈ s that matches s on all concepts in ℰE and yet entails a different class33 3 If a CBM predicts two classes when the same subset of activations attain exactly the same values, these classes cannot be faithfully explained. This is unlikely to happen for discriminatively trained models. – and subset-minimality – all selected concepts should be needed for this to hold. As shown in Fig. 1 (right) and by our experiments in Section 5.3, the heuristics in Eq. 2 provide no such guarantees for commonly used values of k. Enforcing faithfulness. If guarantees are desired, a better option is to resort to exact algorithms for computing AXps. Concretely, we build on the simple but flexible Algorithm 1 of Marques-Silva (2023), denoted EA (Exact Algorithm). Starting from the full bottleneck, ℰ=[b]E=[b], it iteratively removes unneeded activations following an arbitrary order (e.g., activation index), invoking an oracle to check whether the candidate ℰE admits a counterexample ′∈ s . Doing so can be computationally expensive – in fact, NP-hard – in general (Shih et al., 2018; Ignatiev et al., 2019). However, the decision function of CBMs is linear and S is a conjunction of linear inequalities; therefore, the oracle boils down to a linear program that can be solved efficiently (see Section A.1). We propose a variant of EA biased toward more compact explanations. Our algorithm, denoted EA+, grows a candidate ℰ=∅E= into a weak AXp by adding groups of activations following a heuristic-informed and shrinks the result until it is subset minimal. This is akin to Algorithm 1 of Soria et al. (2026), except EA+ i) computes three AXps – one for each heuristic in Eq. 2 – and picks the smallest, and i) employs binary search during the growth stage, and as such requires only a logarithmic number of oracle calls. As shown in Section D.1, EA+’s explanations are always AXps, whereas heuristics explanations often are not, while remaining computationally affordable in practice. Pseudo-code for all algorithms is listed and discussed in Appendix A. 4 The Trade-off Between Faithfulness and Compactness Our goal is to construct explanations ℰE that are both compact and faithful. These properties, however, are at odds: any (weak) AXp must pin all activations that can be (even adversarially) manipulated to yield a different prediction.44 4 E.g., a weak AXp can always be obtained by taking ℰ=[b]E=[b]: since this fixes the whole bottleneck, there exists no counterexample. However, as we discussed, such an explanation is unusable if b is large. Hence, the more leeway a CBM offers to construct counterexamples, the larger (weak) AXps have to be. We proceed to make this argument exact. The next result shows how two architectural properties – (P1) the structure of the activation space S, and (P2) the structure of the inference layer’s weights W – determine whether a given ℰ⊂[b]E⊂[b] can be a weak AXp. We begin from unbounded activations =(−∞,∞)bS=(-∞,∞)^b and analyze the other cases to Appendix B. Proposition 1 (Informal). Fix any CBM prediction (,y^)∈×[m]( s, y) ×[m] and explanation ℰ⊂[b]E⊂[b], and let δ(j):=j−y^∈ℝbδ w^(j):= w_j- w_ y ^b be the delta between the weight vectors of classes j and y y. If (P1) =(−∞,∞)bS=(-∞,∞)^b, and (P2) there exists an activation i∈[b]∖ℰi∈[b] and a class j≠y^j≠ y s.t. δwi(j)≠0δw^(j)_i≠ 0, then ℰE is not a weak AXp. The proof can be found in Appendix B. Hence, if S is unbounded, fixing the prediction y y requires ℰE to fix all concept activations j that link it to any alternative y′y via a non-zero weight difference δwi(j)δw^(j)_i. Together with our earlier observation that ℰ=[b]E=[b] is a (weak) AXp, this entails that for regular CBMs, which (P1) model activations as raw logits and (P2) employ dense linear layers, no AXp smaller than the entire bottleneck exists at all.55 5 In the binary case (m=2m=2), the top layer has a single output (the score of the positive class) and a single weight vector ∈ℝb w ^b. This is equivalent to a top layer with two outputs and symmetric per-class weight vectors, that is, 0=−1 w_0=- w_1. Hence, the precondition wy^,j−wy′,j≠0w_ y,j-w_y ,j≠ 0 becomes wy^,j≠0w_ y,j≠ 0: Proposition 1 triggers whenever an independent, unbounded activation cjc_j not in ℰE is associated to a non-zero weight. This affects both heuristic and exact algorithms. Proposition 1 suggests – and Proposition 3 confirms – that P1 and P2 indeed control for the existence and size of (weak) AXps: intuitively, larger activation spaces S leave more room for manipulating concept activations not fixed by ℰE, while non-zero learned weights, especially if large, translate these into higher scores for non-predicted classes (see Section B.3 for a detailed discussion). Thus, appropriately constraining S and W can reduce the adversary’s ability to construct working counterexamples, meaning (weak) AXps do not have to cover as many activations to safeguard the prediction. 4.1 Existing CBMs vs. Proposition 1 Next, we discuss existing CBMs in light of P1 and P2, summarizing our findings in Table 1. Table 1: Representative CBMs grouped by domain of concept activations S (P1) and structure of the inference layer’s weights W (P2). Constraining S and W can make it more difficult to construct counterexamples that flip the prediction, allowing (weak) AXp to be smaller. Few CBMs employ probabilistic activations and none group lasso. Act. S Wei. W Representative Models (Not Exhaustive) (−∞,∞)b(-∞,∞)^b Dense CBM (Koh et al., 2020) , ProbCBM (Kim et al., 2023) , MCBM (Almudévar et al., 2026) (−∞,∞)b(-∞,∞)^b Elastic Net LF-CBM (Oikarinen et al., 2023) , VLG-CBM (Srivastava et al., 2024) [α,∞)b,α≥0[α,∞)^b,α≥ 0 Elastic Net Selective CBM (Schrodi et al., 2025) [−1,1]b[-1,1]^b Dense LaBo (Yang et al., 2023) ⊆[0,1]b [0,1]^b Dense CB2M (Steinmann et al., 2024) , GlanceNets (Marconato et al., 2022) Concept activation space. Standard CBMs (Koh et al., 2020; Shin et al., 2023; Park et al., 2025) and extensions (Sawada and Nakamura, 2022; Wu et al., 2022; Huang et al., 2024; Almudévar et al., 2026) employ independent, unbounded activations, and thus trigger Proposition 1. Despite the name, probabilistic CBMs do the same (Kim et al., 2023). VLM-CBMs with a backbone (Oikarinen et al., 2023; Srivastava et al., 2024) do supervise it with bounded concept annotations, yet feed the inference layer unbounded activations. Post-hoc CBMs (Yuksekgonul et al., 2023) lack a backbone, but they employ unbounded dot products as activations. All these models leave the adversary unconstrained. Selective CBMs (Schrodi et al., 2025) pass activations through an input-dependent gating function max(0,−) (0, s- o) with a learnable bias o.66 6 The JumpReLU/TopK-based variants (Schrodi et al., 2025) behave analogously. While this prevents Proposition 1 from applying, it allows pushing activations not in ℰE to +∞+∞, which can flip the label whenever these are associated to positive (rather than non-zero) weight differences δwi(j)δw^(j)_i (see Proposition 3 for a formal statement); as we show in Section D.5, this inflates faithful explanations in practice. LaBo (Yang et al., 2023) fares best in that its activations are cosine similarities living in =[−1,1]bS=[-1,1]^b, yet we show in Section 5.2 this does not guarantee (weak) AXps are compact unless the weights of the inference layer are also appropriately constrained. Inference layer weights. Standard CBMs do not regularize W and as such do not encourage learning non-zero differences δ(j)δ w^(j). Recent alternatives – like Selective CBMs (Schrodi et al., 2025) and most VLM-CBMs (Yuksekgonul et al., 2023; Oikarinen et al., 2023; Srivastava et al., 2024) – sparsify W through an elastic net penalty (Zou and Hastie, 2005), thus encouraging predictions to depend on few concepts. This penalty takes the form α∥W∥1+(1−α)∥W∥22/2α W _1+(1-α) W _2^2/2, where α mediates between the L1L_1 and L2L_2 terms. While the elastic net encourages unstructured sparsity, it still allows learning pairs of entries satisfying δ(j)≠δ w^(j) 0, and, as we show in Section 5.2, it struggles to produce compact faithful explanations for VLM-CBMs. 4.2 Beyond Proposition 1 with Probabilistic Concepts and Group Lasso Probabilistic modeling of concept activations. We propose to constrain S by modeling concepts probabilistically, i.e., by passing activations of binary (resp. categorical) concepts through sigmoid (resp. softmax) activations. Besides ensuring activations are bounded to [0,1]b[0,1]^b, doing so allows exploiting mutual exclusivity of categorical concepts. To see why this matters, imagine encoding a categorical “color” concept with three values – red, green and blue – as three softmax outputs s_ r, s_ g, s_ b. Critically, s+s+s=1s_ r+s_ g+s_ b=1. Suppose red is predicted with high probability, say, s=0.95s_ r=0.95. If ℰE covers s_ r, the adversary is left little room to construct a counterexample ′ s : at most, it can shift the residual 0.050.05 mass between s_ g and s_ b, which is unlikely to flip the prediction. Formally, this shrinks S from [0,1]b[0,1]^b to a product of per-concept simplices: the two only match if all concepts are binary. Structured weight sparsity. We suggest to constrain the weights W via group lasso (Yuan and Lin, 2006), treating each activation as a separate group. This penalty takes the form ∑i∥i∥2 _i w_i _2, where i iterates over activations, so as to actively discourage each of them from contributing to any class. In turn, this encourages all differences wy′,j′−wy^,j′w_y ,j -w_ y,j to be exactly zero. Benefits & Limitations. As we will show empirically in Section 5, both proposed strategies are effective at shrinking the size of (weak) AXps. Probabilistic modeling of concepts is not new (see e.g., (Marconato et al., 2022; Steinmann et al., 2024; Tan et al., 2024b), but it has never been linked to the compactness of faithful explanations. In contrast, despite being a widely known technique, no existing CBM architecture employs group lasso. As we will see, probabilistic modeling does not come at any accuracy cost, while excessive sparsification can lower downstream accuracy (see Sections 5.2 and 5.3) and as such has to be applied with care. We stress, however, that even our strategies, while helpful, cannot ensure large bottlenecks always admit small AXps. We will briefly outline other potentially promising remedies in Section 7. 5 Experiments We address the following research questions: Q1: Does modeling concepts probabilistically enable more compact AXps? Q2: Does group lasso shrink AXps further? Q3: How does EA+ fare compared to the heuristic algorithms in Eq. 2? Due to space constraints, we leave some experimental details to Appendix C and additional results to Appendix D. Table 2: Datasets. Cat. is the # of categorical concepts. Dataset m b Cat. Train Val Test CelebA 2 39 0 162,770 19,867 19,962 Derm7pt 5 28 7 413 203 395 WBCAtt 5 31 11 6,169 1,030 3,099 CUB 200 312 28 5,394 600 5,794 Datasets. We evaluate four CBM datasets spanning different number of classes m, concept activations b, and ratio of binary vs. categorical concepts, cf. Table 2. CelebA (Liu et al., 2015) comprises 203203K face images annotated with 4040 binary concepts, split into 163163K training / 2020K validation / 2020K test images. The goal is to predict sex from the remaining 3939 concepts. Derm7pt (Kawahara et al., 2018) includes 11K dermoscopic skin-lesion cases annotated with diagnostic criteria, one-hot encoded into 2828 activations, and a 55-class diagnosis label obtained by grouping 2020 raw diagnoses. WBCAtt (Tsutsui et al., 2023) annotates 1010K white blood cell microscopy images with 1111 categorical morphological attributes, one-hot encoded into 3131 activations, and a 55-class cell-type label. CUB (Wah et al., 2011) involves classifying bird images into one of 200200 classes using 2828 categorical concepts (multi-hot encoded into 312312 activations). It comprises 55K training and 55K test images; we carve about 10%10\% of the training set for validation. Models. For all models, the backbone is a frozen pre-trained image encoder – OpenCLIP’s ViT-L-14-quickgelu (Ilharco et al., 2021) – followed by a linear concept probe. The inference layer is a logistic regressor, either dense or sparsified via elastic net (enet) or group lasso (glasso). For regular CBMs, we take the concept vocabularies and annotations from the dataset and evaluate logit (=(−∞,+∞)bS=(-∞,+∞)^b), ReLU (=[0,+∞)bS=[0,+∞)^b), and probabilistic (⊆[0,1]bS [0,1]^b) concept activations. For the latter, we employ softmax activations for categorical concepts and sigmoids for binary ones, as per Section 4.2. We resort to sequential training, as it achieves competitive performance while reducing the amount of label-specific information affecting the concepts. For VLM-CBMs, we employ LLM-generated vocabularies from LaBo (Yang et al., 2023), LF-CBM (Oikarinen et al., 2023), and VLG-CBM (Srivastava et al., 2024) and compute concept activations as cosine similarities in CLIP’s embedding space, as customary (Debole et al., 2026a). Following Section 4.1, we ensure =[−1,1]bS=[-1,1]^b by employing the obtained activations for inference, like LaBo.77 7 The original LF-CBM and VLG-CBM employ a different VLM and a separate backbone; this explains the accuracy drop in our results compared to the original papers. This difference is irrelevant for our purposes. Due to space constraints, we defer our analysis of Selective CBMs to Section D.5. Metrics. For each model, we report the test set label and concept F1F_1 score (denoted F1YF_1^Y and F1CF_1^C). The latter is micro-averaged over concept activations when these are independent (i.e., logits and ReLUs) and over concepts otherwise (i.e., for probabilities). For each algorithm, we explain a random subset of 11K test instances; for Derm7pt we explain all 395395 test points; for the LaBo CUB vocabulary, which has 1010K entries, we explain 100100 instances. For each model, we test faithfulness following Definition 1 using the model’s declared activation space S; as we discuss in Section C.1, this guarantees our weak AXps are robust to all possible counterexamples, regardless of whether are produced by the backbone or by (potentially malicious) human interventions. 5.1 Q1: Probabilities Shrink Faithful Explanations At No Accuracy Cost We compute faithfulness-compactness curves (FCCs) plotting the cumulative percentage of explained instances admitting a (weak) AXp within a specified size budget k: the faster they grow, the more instances admit a smaller faithful explanation. In Fig. 2, we report FCCs for dense CBMs: logit activations above and probabilities below. Colors represent different algorithms: the TopK heuristics in Eq. 2 (Act in green, Wei in orange, Prod in violet) and EA+ (pink). Table 3: Probabilities are competitive with logits in terms of F1F_1 score. F1CF_1^C F1YF_1^Y Dataset prob logit prob logit CelebA 0.7600.760 0.7600.760 0.9890.989 0.9910.991 Derm7pt 0.6760.676 0.6700.670 0.6530.653 0.6660.666 WBCAtt 0.8770.877 0.8720.872 0.9430.943 0.9480.948 CUB 0.7960.796 0.7810.781 0.8170.817 0.8320.832 Logits are pathological. For all algorithms, the curves for logit activations are squashed to zero until the explanation size budget reaches the bottleneck size b. This empirically confirms Proposition 1: logits leave the adversary unconstrained, meaning that – since the inference layer is dense – no (weak) AXp smaller than the entire bottleneck exists at all. Figure 2: Modeling concepts as probabilities shrinks AXps on Derm7pt (left), WBCAtt (middle), and CUB (right). Top row: logits. Bottom row: probabilities. CelebA is left to Section D.2. Probabilities shrink faithful explanations of all algorithms without hindering accuracy. For probabilistic activations, the FCCs grow much quicker, meaning several explained instances admit smaller (weak) AXps. Focusing on EA+, the FCC shows that about 80%80\% instances (Y-axis) admit a faithful explanation of size ≤9≤ 9 in Derm7pt (down from 2828 for logits), ≤10≤ 10 in WBCAtt (3131 for logits), and ≤60≤ 60 in CUB (312312 for logits). The results for CelebA in Section D.2 are analogous. Comparing the FCCs of the heuristics in the top and bottom rows shows they also require a smaller budget k to find weak AXps: TopK-Act and TopK-Prod fare best, i.e., explain compactly and faithfully almost as many instances as EA+, while TopK-Wei lags behind. Overall, these results confirm that modeling concepts probabilistically is effective at preventing counterexamples. Crucially, these benefits come at no cost as CBMs with logit and probabilistic activations perform equally well: Table 3 shows that they attain almost identical F1YF_1^Y and F1CF_1^C, with the worst-case gap being 22 percentage points (p). 5.2 Q2: Group Lasso Outperforms Elastic Net Next, we compare enet and glasso on CBMs with probabilistic activations and VLM-CBMs with cosine similarity activations. We focus here on the average size of the (weak) AXps found by the various algorithms, and report the FCCs for all models and datasets in Sections D.3 and D.4. Note that cranking up sparsity strength λ helps finding faithful explanations (per P2) but also sinks performance. To ensure a fair comparison, for each sparse CBM we maximize λ under the constraint that its F1YF_1^Y is at most 10%10\% worse than the dense CBM’s on the validation split, as shown in Table 4. We fix enet’s α to 0.990.99, Yuksekgonul et al. (2023) and Oikarinen et al. (2023)’s default. Table 4: glasso shrinks faithful explanations at less than 10%10\% F1YF_1^Y cost. VLM-CBMs have no F1CF_1^C as they have no ground-truth annotations. F1CF_1^C F1YF_1^Y Dataset dense enet glasso CUB 0.7960.796 0.8170.817 0.7590.759 0.7560.756 Derm7pt 0.6760.676 0.6530.653 0.6480.648 0.6380.638 WBCAtt 0.8770.877 0.9430.943 0.9160.916 0.9270.927 LF-CBM – 0.5450.545 0.5890.589 0.5640.564 VLG-CBM – 0.6260.626 0.6320.632 0.5760.576 LaBo – 0.8350.835 0.7530.753 0.7660.766 enet only partially works. For CBMs (Table 5, top), in most cases enet shrinks explanation sizes, but in three cases (in red) it actively regresses: barely on Derm7pt (+1.8+1.8p for TopK-Prod) and substantially on CUB (+58.4+58.4p for TopK-Wei and +68.5+68.5p for TopK-Prod). This is because at α=0.99α=0.99, which favors L1L_1 over L2L_2, it tends to learn larger non-zero weights, which allow the adversary to flip the prediction with smaller activations deltas (as larger weights help convert these into comparatively larger changes to the class scores). enet also fares poorly with VLM-CBMs, which have less constrained concept activations: it often fails to shrink explanations (see the red entries), except for EA+ (LF-CBM: −16.6-16.6p; VLG-CBM: −30.7-30.7p; LaBo: −52.7-52.7p). glasso performs better and is key for VLM-CBMs. glasso always yields smaller faithful explanations compared to the dense baseline. E.g., for EA+, the improvement amounts to Derm7pt: −22.3-22.3p; WBCAtt: −18.3-18.3p; CUB: −7.7-7.7p. It only loses to enet by a small margin in two cases: WBCAtt/EA+ (explanation size 7.3%7.3\% vs 8.1%8.1\%) and CUB/TopK-Act (13.1%13.1\% vs 14.3%14.3\%). Moreover, Table 5 (bottom) shows that glasso is essential for VLM-CBMs, where it substantially outperforms enet (except for TopK-Act, which misbehaves in all cases): with glasso, EA+ explanations take 17.5%17.5\% of LF-CBM’s bottleneck (whereas enet requires 82.9%82.9\% of it), 15.9%15.9\% of VLG-CBM’s (versus 68.7%68.7\%), and only 6.5%6.5\% of LaBo’s (versus 46.9%46.9\%). Table 5: glasso consistently yields smaller faithful explanations than enet. Explanation size is reported as a percentage (i.e., normalized by bottleneck size b) for concision. Bold indicates best in column and red no shrinkage w.r.t. the dense baseline. Derm7pt (b=28b=28) WBCAtt (b=31b=31) CUB (b=312b=312) Act Wei Prod EA+ Act Wei Prod EA+ Act Wei Prod EA+ dense 34.134.1 47.347.3 35.135.1 29.629.6 34.034.0 57.657.6 35.635.6 26.326.3 16.616.6 28.628.6 18.518.5 15.415.4 enet 27.727.7 36.936.9 36.9 [rgb]1,0,036.9 9.59.5 29.929.9 31.031.0 30.930.9 7.3 13.1 87.0 [rgb]1,0,087.0 87.0 [rgb]1,0,087.0 10.210.2 glasso 27.4 8.1 7.8 7.3 28.1 11.7 13.6 8.18.1 14.314.3 9.8 9.4 7.7 LF-CBM (b=202b=202) VLG-CBM (b=419b=419) LaBo (b=10,000b=10,000) Act Wei Prod EA+ Act Wei Prod EA+ Act Wei Prod EA+ dense 100.0100.0 99.999.9 99.999.9 99.599.5 99.999.9 99.899.8 99.899.8 99.499.4 99.899.8 99.699.6 99.699.6 99.699.6 enet 100.0 [rgb]1,0,0100.0 99.9 [rgb]1,0,099.9 99.9 [rgb]1,0,099.9 82.982.9 100.0 [rgb]1,0,0100.0 99.9 [rgb]1,0,099.9 99.9 [rgb]1,0,099.9 68.768.7 99.9 [rgb]1,0,099.9 99.199.1 99.199.1 46.946.9 glasso 99.7 [rgb]1,0,099.7 19.3 19.4 17.5 99.8 [rgb]1,0,099.8 17.1 17.1 15.9 99.9 [rgb]1,0,099.9 6.6 6.7 6.5 5.3 Q3: EA+ finds smaller faithful explanations Finally, we assess how the various algorithms fare in recovering compact (weak) AXps, focusing on properly constrained CBMs to enable meaningful comparison. Additionally, we report an in-depth analysis of runtimes, number of oracle calls, and subset-minimality in Section D.1. EA+ finds AXps at a lower budget k. While EA+ finds k automatically, the TopK heuristics take it as input: if too small, they cannot find any weak AXp. This is what the FCCs in Fig. 2 (bottom row) show for CBMs with probabilistic concepts: setting k too low yields no weak AXp at all. Moreover, compared to EA+, heuristics need a larger k to find a weak AXp. This is expected: EA+ returns the smallest of three AXps, each computed by refining a weak AXp obtained by ranking activations using weights, activations, or their product, cf. Appendix A. Among heuristics, TopK-Act and TopK-Prod work best. This is due to modeling categorical concepts as probabilities: as discussed in Section 4.2, they pin the largest activations first, constraining the other activations via mutual exclusivity in turn. This advantage disappears when all concepts are binary, as shown on CelebA in Section D.2 and by VLM-CBMs. EA+ also yields smaller weak AXps for VLM-CBMs, as shown in Table 5. The gap is substantial for enet-sparsified models: the best heuristic yields explanations with average size >99%>99\% of the bottleneck across vocabularies, while EA+ attains 82.9%82.9\% (LF-CBM), 68.7%68.7\% (VLG-CBM) and 46.9%46.9\% (LaBo). On glasso, EA+ still wins but with a smaller margin, attaining 17.5%17.5\%, 15.9%15.9\% and 6.5%6.5\% versus 19.3%19.3\%, 17.1%17.1\% and 6.6%6.6\% for the runner-up. 6 Related Work Formal XAI sets itself apart from classic XAI (Guidotti et al., 2018) by seeking explanations with formal guarantees (Marques-Silva, 2023; Darwiche, 2023). Most works focus on discrete features, and as such do not apply to CBMs with continuous concepts, although a handful of CBM variants do employ discrete concepts, e.g., (Havasi et al., 2022; Vandenhirtz et al., 2024; Knab et al., 2026); we plan to investigate their faithfulness in future work. We build on the well-known EA algorithm due to its flexibility and good empirical performance. More refined algorithms for computing size-minimal AXps of linear classifiers with polynomial delay (Marques-Silva et al., 2020; Cooper and Marques-Silva, 2023; Fernandes and Rocha, 2026) are restricted to binary tasks and cannot replace EA+ in our experiments. Our theoretical contribution is novel. Compatibly with it, the algorithms of Marques-Silva et al. (2020) require continuous features to be bounded. Our work, however, studies not only existence of AXps but also modeling choices (beyond boundedness) that control their size. Three papers lie closest to our work. Srivastava et al. (2024) show that top-55 heuristic explanations of VLM-CBM decisions often allow flipping predictions; our results systematize their observation. Soria et al. (2026) introduce FXAI algorithms for computing AXps of prototype neural nets, where concept activations encode similarities to learned prototypical embeddings. Our theory backs up their findings but also allows us to identify architectural choices that facilitate the existence of more compact (weak) AXps. Their Algorithm 1 is close to EA+ except it ranks activations by absolute value only, which performs poorly for independent activations (see CelebA in Section D.2) and for VLM-CBMs (see Section 5.3). Finally, Paul et al. (2024) design an FXAI algorithm for neuro-symbolic models that, similarly to CBMs, pair concept extraction with (logic) inference (Marconato et al., 2026). Whereas they seek hierarchical AXps (covering both inputs and concepts) robust to local (ε -ball) perturbations, we construct concept-level AXps robust to all counterexamples in S. Transparency of CBMs. Most critiques of CBMs study human-alignment of the learned concepts. Some works show that, without concept supervision, CBMs can learn arbitrarily misaligned concepts (Bortolotti et al., 2025); others look at the impact of replacing expert supervision with VLM annotations (Kazmierczak et al., 2026; Debole et al., 2026a); others still show that, even when concepts are supervised, CBMs can push accuracy by encoding spurious information into the concepts (Mahinpei et al., 2021; Margeloiu et al., 2021; Raman et al., 2025) and propose several remedies (Havasi et al., 2022; Marconato et al., 2022; Huang et al., 2024; Fokkema et al., 2025; Almudévar et al., 2026) (but see Zarlenga (2026) for counterarguments). While concept alignment is sometimes referred to as “concept faithfulness” (Schmalwasser et al., 2026), none of these works consider the faithfulness of CBM explanations. 7 Conclusion We study the faithfulness of CBM explanations and adapt ideas and techniques from FXAI to these models. Our work shows that many existing CBMs do not admit compact faithful explanations; that probabilistic modeling and structured sparsity enable retrieving substantially more compact (weak) AXps for regular and VLM-based CBMs; and that, while existing heuristic strategies for computing compact CBM explanations often fail to identify (even weak) AXps, our exact algorithm does. At a high level, our work suggests that (large) concept bottlenecks should not be naïvely equated with faithful interpretability. In future work, we will study how to shrink faithful explanations further. A first direction involves squeezing (Schrodi et al., 2025; Yan et al., 2023) and enlarging (Feng et al., 2025) bottlenecks on demand while ensuring faithfulness. A second direction involves relaxing the notion of faithfulness, e.g., by adapting probabilistic variants (Wang et al., 2021; Azzolin et al., 2025; Subercaseaux et al., 2025) that require the prediction holds with high probability. Finally, while we require explanations to be robust to both natural and (possibly out-of-distribution) human interventions, we plan to study how to shrink AXps by considering only counterexamples achievable by the backbone, leveraging approximations from the neural net verification literature (Singh et al., 2019; Zhang et al., 2018) to keep EA+ tractable. As a side benefit, this would automatically account for dependencies between input variables, which FXAI algorithms (including ours) typically ignore. AI use statement We used generative AI tools for writing a first version of the code, for support when deriving the proofs in Appendix B, for scanning the literature in search of relevant publications we originally missed, and for reviewing the manuscript before submission. We have not used generative AI tools for other tasks with required disclosure. The code was manually reviewed by the authors. The proofs were manually written and carefully checked by the authors. The figures were made by the authors. The manuscript was written by the authors. The bibliography was manually compiled by the authors using bibentries sourced from Google Scholar. We take responsibility for the final content of this work, including text, claims or artifacts produced with the aid of generative AI. Author Contributions The core ideas were born from a chat between AV and ST while the latter was visiting the University of Edinburgh in 2024. The idea evolved over time through several discussions with SA. In the summer of 2026, ST made a push toward translating ideas into a paper, designing the experiments and a basic theoretical analysis, and leveraging generative AI to write the necessary code. AV, SA and EM provided invaluable ideas and feedback throughout the process. Meanwhile, EM developed and integrated a more in-depth theoretical analysis. All authors contributed to the writing of the paper and approved the current manuscript. Reproducibility statement Experimental details are provided in Section 5 and Appendix D. Acknowledgments The authors are grateful to Dario Pesenti for useful discussion. Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union, the MSCA-PF programme, or the European Health and Digital Executive Agency (HaDEA). Neither the European Union nor the granting authority can be held responsible for them. Grant Agreement no. 101120763 - TANGO. EM is funded by the Horizon Europe/Marie Sklodowska-Curie under Grant Agreement No. 101282115 - AI-CURE. Antonio Vergari is supported by the “UNREAL: Unified Reasoning Layer for Trustworthy ML” project (EP/Y023838/1) selected by the ERC and funded by UKRI EPSRC. References Almudévar et al. (2026) A. Almudévar, J. M. Hernández Lobato, and A. Ortega There was never a bottleneck in concept bottleneck models. In ICLR, Cited by: §4.1, Table 1, §6. Alvarez Melis and Jaakkola (2018) D. Alvarez Melis and T. Jaakkola Towards robust interpretability with self-explaining neural networks. NeurIPS. Cited by: §2. Azzolin et al. (2025) S. Azzolin, A. Longa, S. Teso, and A. Passerini Reconsidering faithfulness in regular, self-explainable and domain invariant gnns. In ICLR, Cited by: §7. Barker et al. (2023) M. Barker, K. M. Collins, K. Dvijotham, A. Weller, and U. Bhatt Selective concept models: permitting stakeholder customisation at test-time. In HCOMP, Cited by: 2nd item, §3. Beck and Teboulle (2009) A. Beck and M. Teboulle A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences. Cited by: Appendix C. Bogani et al. (2026) A. Bogani, N. Debole, E. Marconato, A. Pugnana, K. Tentori, and A. Passerini Are concept bottleneck models effective as decision-support systems?. arXiv:2608.25581. Cited by: §1, §3. Bontempelli et al. (2023) A. Bontempelli, S. Teso, K. Tentori, F. Giunchiglia, and A. Passerini Concept-level debugging of part-prototype networks. In ICLR, Cited by: §3. Bortolotti et al. (2025) S. Bortolotti, E. Marconato, P. Morettin, A. Passerini, and S. Teso Shortcuts and identifiability in concept-based models from a neuro-symbolic lens. In NeurIPS, Cited by: §2, §6. Chen et al. (2019) C. Chen, O. Li, D. Tao, A. Barnett, C. Rudin, and J. K. Su This looks like that: deep learning for interpretable image recognition. NeurIPS. Cited by: §2, §3. Cooper and Marques-Silva (2023) M. C. Cooper and J. Marques-Silva Tractability of explaining classifier decisions. Artificial Intelligence. Cited by: §6. Darwiche (2023) A. Darwiche Logic for Explainable AI. In Annual ACM/IEEE Symposium on Logic in Computer Science, Cited by: §1, §1, §3, §6. Debole et al. (2026a) N. Debole, P. Barbiero, F. Giannini, A. Passerini, S. Teso, and E. Marconato If concept bottlenecks are the question, are foundation models the answer?. Machine Learning. Cited by: Appendix C, §1, §2, §5, §6. Debole et al. (2026b) N. Debole, A. Passerini, S. Teso, A. Pugnana, and E. Marconato Concepts worth having: refining vlm-guided concept bottleneck models with minimal annotations. arXiv:2605.16405. Cited by: Appendix C. Espinosa Zarlenga et al. (2023) M. Espinosa Zarlenga, K. Collins, K. Dvijotham, A. Weller, Z. Shams, and M. Jamnik Learning to receive help: intervention-aware concept embedding models. NeurIPS. Cited by: §3. Feng et al. (2025) J. Feng, A. Kothari, L. Zier, C. Singh, and Y. S. Tan Bayesian concept bottleneck models with llm priors. NeurIPS. Cited by: §7. Fernandes and Rocha (2026) G. P. Fernandes and T. A. Rocha Concisely explaining the doubt: minimum-size abductive explanations for linear models with a reject option. World Conference on Explainable Artificial Intelligence. Cited by: §6. Fokkema et al. (2025) H. Fokkema, T. van Erven, and S. Magliacane Sample-efficient learning of concepts with theoretical guarantees: from data to concepts without interventions. NeurIPS. Cited by: §2, §6. Guidotti et al. (2018) R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Giannotti, and D. Pedreschi A survey of methods for explaining black box models. ACM Computing Surveys. Cited by: §6. Havasi et al. (2022) M. Havasi, S. Parbhoo, and F. Doshi-Velez Addressing leakage in concept bottleneck models. NeurIPS 35, p. 23386–23397. Cited by: §6, §6. Huang et al. (2024) Q. Huang, J. Song, J. Hu, H. Zhang, Y. Wang, and M. Song On the concept trustworthiness in concept bottleneck models. In AAAI, Cited by: §4.1, §6. Ignatiev et al. (2019) A. Ignatiev, N. Narodytska, and J. Marques-Silva Abduction-based explanations for machine learning models. In AAAI, Cited by: §3, footnote 2. Ignatiev (2020) A. Ignatiev Towards trustable explainable ai. In IJCAI-PRICAI, Cited by: §3. Ilharco et al. (2021) OpenCLIP External Links: Document Cited by: §5. Ji et al. (2025) Y. Ji, Y. Sun, Y. Zhang, Z. Wang, Y. Zhuang, Z. Gong, D. Shen, C. Qin, H. Zhu, and H. Xiong A comprehensive survey on self-interpretable neural networks. Proceedings of the IEEE. Cited by: §1, §2. Kawahara et al. (2018) J. Kawahara, S. Daneshvar, G. Argenziano, and G. Hamarneh Seven-point checklist and skin lesion classification using multitask multimodal neural nets. IEEE journal of biomedical and health informatics. Cited by: Appendix C, §5. Kazmierczak et al. (2026) R. Kazmierczak, S. Azzolin, G. Frehse, E. Berthier, and G. Franchi Enhancing concept localization in CLIP-based concept bottleneck models. TMLR. Cited by: §2, §6. Kim et al. (2023) E. Kim, D. Jung, S. Park, S. Kim, and S. Yoon Probabilistic concept bottleneck models. In ICML, Cited by: §4.1, Table 1. Knab et al. (2026) P. Knab, D. Steinmann, C. Bartelt, K. Kersting, B. Schiele, T. Seidl, U. Schlegel, and W. Stammer What’s in the bottle? a survey and roadmap of concept bottleneck models. TMLR. Cited by: §1, §2, §6. Koh et al. (2020) P. W. Koh, T. Nguyen, Y. S. Tang, S. Mussmann, E. Pierson, B. Kim, and P. Liang Concept bottleneck models. In ICML, Cited by: Appendix C, §1, §2, §4.1, Table 1. Lage et al. (2019) I. Lage, E. Chen, J. He, M. Narayanan, B. Kim, S. J. Gershman, and F. Doshi-Velez Human evaluation of models built for interpretability. In HCOMP, Cited by: §3. Ley et al. (2026) D. Ley, G. Nguyen, H. Lakkaraju, and J. Adebayo Prototype language models. arXiv:2607.00510. Cited by: §3. Liu and Nocedal (1989) D. C. Liu and J. Nocedal On the limited memory bfgs method for large scale optimization. Mathematical programming. Cited by: Appendix C. Liu et al. (2015) Z. Liu, P. Luo, X. Wang, and X. Tang Deep learning face attributes in the wild. In IEEE international conference on computer vision, Cited by: Appendix C, §5. Mahinpei et al. (2021) A. Mahinpei, J. Clark, I. Lage, F. Doshi-Velez, and W. Pan Promises and pitfalls of black-box concept learning models. arXiv:2106.13314. Cited by: §6. Marconato et al. (2026) E. Marconato, S. Bortolotti, E. Van Krieken, P. Morettin, E. Umili, A. Vergari, E. Tsamoura, A. Passerini, and S. Teso Symbol grounding in neuro-symbolic ai: a gentle introduction to reasoning shortcuts. Journal of Artificial Intelligence Research. Cited by: §6. Marconato et al. (2022) E. Marconato, A. Passerini, and S. Teso GlanceNets: Interpretabile, Leak-proof Concept-based Models. In NeurIPS, Cited by: §4.2, Table 1, §6. Margeloiu et al. (2021) A. Margeloiu, M. Ashman, U. Bhatt, Y. Chen, M. Jamnik, and A. Weller Do concept bottleneck models learn as intended?. arXiv:2105.04289. Cited by: §6. Marques-Silva et al. (2020) J. Marques-Silva, T. Gerspacher, M. Cooper, A. Ignatiev, and N. Narodytska Explaining naive bayes and other linear classifiers with polynomial time and delay. NeurIPS. Cited by: §B.1, §6. Marques-Silva (2023) J. Marques-Silva Logic-based explainability in machine learning. In Reasoning Web. Causality, Explanations and Declarative Knowledge: 18th International Summer School 2022, Tutorial Lectures, Cited by: Appendix A, §B.1, §D.1, §1, §1, §1, §3, §3, §3, §6. Narayanan et al. (2018) M. Narayanan, E. Chen, J. He, B. Kim, S. Gershman, and F. Doshi-Velez How do humans understand explanations from machine learning systems? an evaluation of the human-interpretability of explanation. arXiv:1802.00682. Cited by: §3. Oikarinen et al. (2023) T. Oikarinen, S. Das, L. M. Nguyen, and T. Weng Label-free concept bottleneck models. In ICLR, Cited by: Appendix C, §1, §1, §2, §3, §4.1, §4.1, Table 1, §5.2, §5. Park et al. (2025) S. Park, J. Mun, D. Oh, and N. Lee An analysis of concept bottleneck models: measuring, understanding, and mitigating the impact of noisy annotations. NeurIPS. Cited by: §2, §4.1. Paul et al. (2024) S. Paul, J. Yu, J. J. Dekker, A. Ignatiev, and P. J. Stuckey Formal explanations for neuro-symbolic ai. arXiv:2410.14219. Cited by: §6. Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay Scikit-learn: machine learning in Python. Journal of Machine Learning Research. Cited by: Appendix C. Radford et al. (2021) A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, et al. Learning transferable visual models from natural language supervision. In ICML, Cited by: §2. Raman et al. (2025) N. Raman, M. E. Zarlenga, J. Heo, and M. Jamnik Do concept bottleneck models respect localities?. TMLR. Cited by: §6. Ramaswamy et al. (2023) V. V. Ramaswamy, S. S. Kim, R. Fong, and O. Russakovsky Overlooked factors in concept-based explanations: dataset choice, concept learnability, and human capability. In CVPR, Cited by: §1. Rudin (2019) C. Rudin Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence. Cited by: §3. Sawada and Nakamura (2022) Y. Sawada and K. Nakamura Concept bottleneck model with additional unsupervised concepts. IEEE Access. Cited by: §4.1. Schmalwasser et al. (2026) L. Schmalwasser, J. Blunk, N. Penzel, J. Niebling, and J. Denzler On the faithfulness of post-hoc concept bottleneck models. In ECCV, Cited by: §6. Schrodi et al. (2025) S. Schrodi, J. Schur, M. Argus, and T. Brox Selective concept bottleneck models without predefined concepts. TMLR. Cited by: §B.3, item , §D.5, §1, §3, §3, §4.1, §4.1, Table 1, §7, footnote 6. Shih et al. (2018) A. Shih, A. Choi, and A. Darwiche A symbolic approach to explaining bayesian network classifiers. In IJCAI, Cited by: §3, §3, footnote 2. Shin et al. (2023) S. Shin, Y. Jo, S. Ahn, and N. Lee A closer look at the intervention procedure of concept bottleneck models. In ICML, Cited by: §1, §2, §3, §4.1. Singh et al. (2019) G. Singh, T. Gehr, M. Püschel, and M. Vechev An abstract domain for certifying neural networks. POPL. Cited by: §C.1, §7. Soria et al. (2026) J. Soria, Z. Chihani, J. Girard-Satabin, A. Grastien, R. Xu-Darme, and D. Cancila Formal abductive latent explanations for prototype-based networks. In AAAI, Cited by: §1, §3, §6. Srivastava et al. (2024) D. Srivastava, G. Yan, and T. Weng VLG-CBM: Training Concept Bottleneck Models with Vision-Language Guidance. In NeurIPS, Cited by: §1, §3, §4.1, §4.1, Table 1, §5, §6. Stammer et al. (2021) W. Stammer, P. Schramowski, and K. Kersting Right for the right concept: revising neuro-symbolic concepts by interacting with their explanations. In CVPR, Cited by: §1, §3. Steinmann et al. (2024) D. Steinmann, W. Stammer, F. Friedrich, and K. Kersting Learning to intervene on concept bottlenecks. In ICML, Cited by: §4.2, Table 1. Subercaseaux et al. (2025) B. Subercaseaux, M. Arenas, and K. S. Meel Probabilistic explanations for linear models. In Proceedings of the AAAI Conference on Artificial Intelligence, Cited by: §7. Tan et al. (2024a) A. Tan, F. Zhou, and H. Chen Explain via any concept: concept bottleneck model with open vocabulary concepts. In ECCV, Cited by: §2. Tan et al. (2024b) Z. Tan, T. Chen, Z. Zhang, and H. Liu Sparsity-guided holistic explanation for llms with interpretable inference-time intervention. In AAAI, Cited by: §4.2. Teso et al. (2023) S. Teso, Ö. Alkan, W. Stammer, and E. Daly Leveraging explanations in interactive machine learning: an overview. Frontiers in Artificial Intelligence. Cited by: §1. Tsutsui et al. (2023) S. Tsutsui, W. Pang, and B. Wen Wbcatt: a white blood cell dataset annotated with detailed morphological attributes. NeurIPS. Cited by: Appendix C, §5. Vandenhirtz et al. (2024) M. Vandenhirtz, S. Laguna, R. Marcinkevičs, and J. E. Vogt Stochastic concept bottleneck models. NeurIPS. Cited by: §6. Wah et al. (2011) C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie The caltech-ucsd birds-200-2011 dataset. Technical report Technical Report CNS-TR-2011-001, California Institute of Technology. Cited by: Appendix C, §1, §3, §5. Wang et al. (2021) E. Wang, P. Khosravi, and G. Van den Broeck Probabilistic sufficient explanations. In IJCAI, Cited by: §7. Wu et al. (2022) C. Wu, S. Parbhoo, M. Havasi, and F. Doshi-Velez Learning optimal summaries of clinical time-series with concept bottleneck models. In Machine Learning for Healthcare Conference, Cited by: §4.1. Yan et al. (2023) A. Yan, Y. Wang, Y. Zhong, C. Dong, Z. He, Y. Lu, W. Y. Wang, J. Shang, and J. McAuley Learning concise and descriptive attributes for visual recognition. In ICCV, Cited by: §7. Yang et al. (2023) Y. Yang, A. Panagopoulou, S. Zhou, D. Jin, C. Callison-Burch, and M. Yatskar Language in a bottle: language model guided concept bottlenecks for interpretable image classification. In CVPR, Cited by: Appendix C, §1, §1, §2, §3, §3, §4.1, Table 1, §5. Yuan and Lin (2006) M. Yuan and Y. Lin Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society Series B: Statistical Methodology. Cited by: §4.2. Yuksekgonul et al. (2023) M. Yuksekgonul, M. Wang, and J. Zou Post-hoc concept bottleneck models. In ICLR, Cited by: §1, §2, §3, §4.1, §4.1, §5.2. Zarlenga (2026) M. E. Zarlenga In defense of information leakage in concept-based models. ICML. Cited by: §6. Zhang et al. (2018) H. Zhang, T. Weng, P. Chen, C. Hsieh, and L. Daniel Efficient neural network robustness certification with general activation functions. NeurIPS. Cited by: §C.1, §7. Zou and Hastie (2005) H. Zou and T. Hastie Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society Series B: Statistical Methodology. Cited by: §4.1. Appendix A Algorithmic Details The algorithms we evaluate are the following: i) TopK-Act, TopK-Wei, and TopK-Prod, three heuristic strategies that require a target explanation size k as input; i) EA, a general exact algorithm, appearing as Algorithm 1 in Marques-Silva [2023], which does not require k as input; and i) EA+, our improved EA. All pseudo-code assumes access to a CBM (f,g)(f,g) with a linear inference layer and to a prediction (,y^)( s, y) to be explained; we leave these implicit for brevity. A.1 Finding a Counterexample Most algorithms rely on a procedure Oracle(ℰ,) Oracle(E,S) for checking whether a given explanation ℰE admits constructing a counter-example ′∈ s . Given (,y^)( s, y), a vector ′ s is a valid counterexample if it matches s on all activations covered by ℰE but yields a different prediction y′≠y^y ≠ y, that is: (ℰ′=ℰ)∧(y^∉argmaxy∈[m]f(′)y). ( s_E = s_E )\; \; ( y ∈ _y∈[m]f( s )_y ). (4) We are dealing with linear inference layers of the form f()=W+0f( s)=W s+ w_0. Hence, letting y∈ℝb w_y ^b be the vector of inference layer weights W associated to class y∈[m]y∈[m], and wy,0w_y,0 be the corresponding bias term, the second term in Eq. 4 translates to: ⟨y′,′⟩+y′,0>⟨y^,′⟩+y^,0. w_y , s + w_y ,0> w_ y, s + w_ y,0. (5) We ignore follow-up monotonic transformations, e.g., sigmoid and softmax activations, as they do not alter the ranking between classes. In order to find a counterexample, the oracle has to find a class y′≠y^y ≠ y out of m−1m-1 possible alternatives and a vector ′∈ s that satisfies Eq. 5. This can be readily done by solving, for each candidate y′y , the following optimization problem: max′ _ s ⟨y′−y^,′⟩+(y′,0−y^,0) w_y - w_ y, s +( w_y ,0- w_ y,0) (6) s.t. .t. ℰ′=ℰ∧′∈ s _E= s_E s (7) The objective is linear in ′ s . At the same time, in our setting the feasible set S can be encoded as a (conjunction of) linear constraints. For cosine similarities (=[−1,1]bS=[-1,1]^b), ReLU activations (=[0,+∞)bS=[0,+∞)^b), and raw logits (=(−∞,+∞)bS=(-∞,+∞)^b), the constraint is a conjunction of axis-aligned open or closed bounds aj≤sj′≤bja_j≤ s _j≤ b_j. For probabilistic activations (≡⊆[0,1]bS≡ δ w [0,1]^b, where δ w is a product of simplices) it is a conjunction of per-concept linear constraints ∑jsi,j=1 _js_i,j=1, where i runs over concepts and j over activations encoding that concept, and non-negativity constraints sj≥0s_j≥ 0 running over all activations. Hence, finding a counterexample boils down to a linear program (LP). In short: the oracle is a collection of m−1m-1 LPs. If the LP for class y′y admits a positive objective, its solution ′ s is a valid counterexample for ℰE within S, and the oracle returns it. Otherwise, if no LP yields a positive objective, ℰE admits no counterexample and the oracle returns false. A.2 The Heuristic Algorithms Algorithm 1 TopK⋆(,b,h) TopK (S,b,h) 1: π←[b]π←[b] decreasing by h’s criterion 2: for k=1,…,bk=1,…,b do 3: if not Oracle(π1:k,) Oracle( _1:k,S) then 4: return π1:k _1:k 5: return [b][b] These are the three strategies introduced in Eq. 2. Given a decision (,y^)( s, y) and a budget k, they sort the b concept activations by either largest activation (TopK-Act), largest absolute weight (TopK-Wei), or largest absolute score (activation times weight) (TopK-Prod), and construct an explanation ℰE by taking the top k activations. This procedure, however, does not guarantee the output is an AXp (faithful and subset-minimal) or even a weak AXp (faithful but not subset-minimal). Crucially, the likelihood of finding a (weak) AXp increases with the budget k, making a fair comparison with EA+ difficult, as the latter does not require to fix k. For this reason, rather than fixing k a priori, we compute it dynamically by taking the smallest k such that the resulting explanation a (weak) AXps. This is precisely what TopK∗ (Algorithm 1) does: it first ranks the b concept activations according to value, absolute weight, or absolute score – depending on the choice of heuristic h – and then checks prefixes of increasing size k until it finds a (weak) AXp. If no proper prefix is faithful, it returns the entire bottleneck. This ensures the resulting explanation is a weak AXp at the cost of at most b calls to Oracle. A.3 The EA algorithm Algorithm 2 Shrink(,ℰ) Shrink(S,E) 1: for j∈ℰj do 2: if not Oracle(ℰ∖j,) Oracle(E \j\,S) then 3: ℰ←ℰ∖jE \j\ 4: return ℰE This algorithm is a direct application of the Shrink procedure in Algorithm 2. The procedure takes a weak AXp ℰ⊆[b]E [b] as input and iterates over all indices j∈ℰj in some order (in practice, lowest to highest, for simplicity): for each j, it checks whether ℰE remains a weak AXp – i.e., whether it still admits no counterexamples, using Oracle – even if j is removed. In this case, it removes j, otherwise it keeps it. Note that the output is guaranteed to be a subset-minimal weak AXp, that is, an AXp. The EA algorithm simply invokes Shrink on the full bottleneck ℰ=[b]E=[b], which is a weak AXp by construction. The oracle is called exactly b times. A.4 The EA+ algorithm Algorithm 3 EA+(,b) EA+(S,b) 1: for each heuristic h do 2: ℰh←TopKbs⋆(,b,h)E_h← TopK _bs(S,b,h) 3: ℰh←Shrink(,ℰh)E_h← Shrink(S,E_h) 4: return argminh|ℰh| _h|E_h| Algorithm 4 TopKbs⋆(,b,h) TopK _bs(S,b,h) 1: π←[b]π←[b] decreasing by h’s criterion 2: α←0α← 0; β←bβ← b 3: while α<βα<β do 4: μ←⌊12(α+β)⌋μ← 12(α+β) 5: if not Oracle(π1:μ,) Oracle( _1:μ,S) then 6: β←μβ←μ 7: else 8: α←μ+1α←μ+1 9: return π1:α _1:α EA ignores instance-specific information (e.g., the values and weights of the concept activations) and in doing so may return an overly large AXp. At the same time, it requires b oracle calls, which can be problematic for large bottlenecks. Our algorithm, EA+, implements two simple modifications that aim to lessen both issues, see Algorithm 3. It invokes TopK∗ three times, once for each heuristic h, obtaining three weak AXp ℰhE_h. Then it applies the Shrink procedure for removing possibly useless activations to each of them. Out of the three resulting AXps, it returns the smallest. Moreover, rather than invoking Algorithm 1, which costs b oracle calls, it employs a more efficient variant that employs binary search instead, listed in Algorithm 4. The goal is to find the shortest prefix of the bottleneck – sorted according to the given heuristic h – that is faithful. Rather than scanning prefixes linearly as Algorithm 1 does, it employs binary search: in each iteration, it checks whether the prefix delimited by (1,12⌊α+β⌋)(1, 12 α+β ) admits a counterexample. If it does not, it is faithful, so the algorithm halves it (by decreasing β), and repeats. If it does, it is not faithful, so the algorithm enlarges it (by increasing α), and repeats. This modification reduces the number of oracle calls to O(log2b)O( _2b). This offsets the total cost of having to call the procedure for three times total, once per heuristic. Appendix B Conditions for (In)Existence of Weak AXps Recall that an explanation is a weak AXp insofar as it does not allow to flip the CBM’s prediction by manipulating the concept activations it does not cover. In this section, we make explicit the conditions for flipping the label of an arbitrary inference layer weights W for counterexamples taken from an activation space of the form =×i=1b[αi,βi]. = _i=1^b[ _i, _i]. (8) Here, αi,βi∈ℝ _i, _i are arbitrary (finite or infinite) per-activation constants with αi<βi _i< _i. This will be our departure point for discussing four different continuous activation spaces S most common in the CBM literature (as discussed in Section 4.1), namely: • Unbounded: =(−∞,∞)bS=(-∞,∞)^b, e.g., when concept activations are unconstrained logits, as in many CBM architectures (see Table 1). • Bounded-from-below: =[α,∞)bS=[α,∞)^b, e.g., as in Selective CBMs [Barker et al., 2023] where activations are only retained if they exceed a threshold α≥0α≥ 0. • Bounded: =[α,β]bS=[α,β]^b, e.g., in the case of independent probabilistic activations, in which case α=0α=0, β=1β=1. • Bounded-on-simplices: ⊆[0,1]bS [0,1]^b, a product of per-concept simplices, representing the case of probabilistic modeling with (binary and) categorical concepts. Notation. We focus on concept activations ∈ s associated to an input ∈ x . Recall that the inference layer is a linear function f:→ℝmf:S ^m, i.e., f()=W+0f( s)=W s+ w_0 (9) where W∈ℝm×bW ^m× b and 0∈ℝm w_0 ^m, and the prediction is y^:=argmaxy∈[m]fy(),wherefy()=y⊤+w0,y. y:= _y∈[m]f_y( s)\,, f_y( s)= w_y s+w_0,y\,. (10) For any class y′∈[m]y ∈[m], we use y′∈ℝb w_y ^b to indicate its associated weights. Given a non-predicted class j and a prediction y y, we denote the deltas between their associated weights and biases as: δ(j):=j−y^,andδw0(j):=w0,j−w0,y^δ w^(j):= w_j- w_ y\,, δ w^(j)_0:=w_0,j-w_0, y (11) and the difference between their logits as δμ(j)():=fj()−fy^()=δ(j)⋅+δw0(j).δμ^(j)( s):=f_j( s)-f_ y( s)=δ w^(j)· s+δ w^(j)_0\,. (12) Finally, for any real a∈ℝa , we write a+:=max(0,a),a−:=max(0,−a).a^+:= (0,a), a^-:= (0,-a)\,. (13) B.1 The Independent Concept Activations Case Throughout, we will use the shorthands ℰ¯:=[b]∖ℰ E:=[b] and ℰ()=′∈:ℰ′=ℰS_E( s)=\ s : s _E= s_E\. First, we identify general conditions for label flipping in a bounded asymmetric domain when fixing a subset ℰ⊂[b]E⊂[b] of concept activations. Our lemma follows on the footsteps of Marques-Silva et al. [2020]. Lemma 2. Let =×i=1b[αi,βi]S= _i=1^b[ _i, _i]. Take any ∈ s , a prediction y^∈argmaxyfy() y∈ _yf_y( s), a non-predicted class j∈[m]j∈[m], and a subset ℰ⊂[b]E⊂[b]. Let μj:=max∗∈ℰ()δμj(∗) _j:= _ s^* _E( s)δ _j( s^*) be the largest logit difference between classes j and y y achievable by manipulating concept activations outside of ℰE. This quantity can be rewritten as: μj=δμ(j)()+∑i∈¯ℰ[(δwi(j))+(βi−si)+(δwi(j))−(si−αi)]. _j=δμ^(j)( s)+ _i∈ E [(δw^(j)_i)^+( _i-s_i)+(δw^(j)_i)^-(s_i- _i) ]\,. (14) Proof. Recall that the difference in logits for activation j is given by δμ(j)()=δ(j)⋅+δw0(j).δμ^(j)( s)=δ w^(j)· s+δ w^(j)_0\,. (15) We expand the dot product as follows δμ(j)() δμ^(j)( s) =∑i∈ℰδwi(j)si+∑i∈¯ℰδwi(j)si+δw0(j). = _i δw^(j)_is_i+ _i∈ Eδw^(j)_is_i+δ w^(j)_0\,. (16) Now, take any non-fixed concept activation i∈¯ℰi∈ E. Following [Marques-Silva, 2023], we maximize the logit of class j by setting sis_i to βi _i if δwi(j)δw^(j)_i is positive and to αi _i if δwi(j)δw^(j)_i is negative for each i∈¯ℰi∈ E. Plugging this into Eq. 16 and maximizing shows that μj _j, the maximum difference in logits attainable for class j, is: max∗∈ℰ()δμj(∗) _ s^* _E( s)δ _j( s^*) =∑i∈ℰδwi(j)si+∑i∈¯ℰ[(δwi(j))+βi−(δwi(j))−αi]+δw0(j) = _i δw^(j)_is_i+ _i∈ E [(δw^(j)_i)^+ _i-(δw^(j)_i)^- _i ]+δ w^(j)_0 (17) =∑i∈ℰδwi(j)si+∑i∈¯ℰδwi(j)si+δw0(j)⏟δμ(j)() = _i δw^(j)_is_i+ _i∈ Eδw^(j)_is_i+δ w^(j)_0_δμ^(j)( s) −∑i∈¯ℰδwi(j)si+∑i∈¯ℰ[(δwi(j))+βi−(δwi(j))−αi] - _i∈ Eδw^(j)_is_i+ _i∈ E [(δw^(j)_i)^+ _i-(δw^(j)_i)^- _i ] (18) =δμ(j)()+∑i∈¯ℰ[(δwi(j))+(βi−si)+(δwi(j))−(si−αi)] =δμ^(j)( s)+ _i∈ E [(δw^(j)_i)^+( _i-s_i)+(δw^(j)_i)^-(s_i- _i) ] (19) This proves the claim. ∎ The reason we care about μj _j is that it allows us to rewrite the condition under which a label-flipping counterexample exists as follows: there must exist a class j≠y^j≠ y such that μj>0 _j>0, i.e., that attains a larger logit than the prediction y y. Equivalently, we can write maxj≠y^μj>0 _j≠ y _j>0. Next, we exploit Lemma 2 to identify explicity conditions under which different choices S admit (weak) AXps smaller than the bottleneck: Proposition 3 (Extended Proposition 1). For any CBM prediction (,y^)∈×[m]( s, y) ×[m], an explanation ℰ⊂[b]E⊂[b] smaller than the entire bottleneck cannot be a weak AXp unless: 1. Unbounded (=(−∞,∞)bS=(-∞,∞)^b) There exists no concept activation i∈ℰ¯i∈ E and alternative class j≠y^j≠ y such that δwi(j)≠0δw^(j)_i≠ 0. 2. Bounded from below: (=[α,∞)bS=[α,∞)^b.) There exists no concept activation i∈¯ℰi∈ E and alternative class j≠y^j≠ y such that δwi(j)>0δw^(j)_i>0. 3. Bounded symmetric: (=[α,β]bS=[α,β]^b) There exists no alternative class j≠y^j≠ y such that maxj≠y^μj>0 _j≠ y _j>0, where μj _j can be written as μj=δμj(¯)+β−α2∥δℰ¯(j)∥1; _j=δ _j( s)+ β-α2 δ w^(j)_ E _1\,; (20) and ¯ s is such that ¯ℰ¯=α+β2 1ℰ¯ s_ E= α+β2\,1_ E is the mid-point between α and β for all coordinates in ℰ¯ E. 4. Bounded asymmetric: (=×i=1b[αi,βi]S= _i=1^b[ _i, _i]). There exists no alternative class j≠y^j≠ y such that maxj≠y^μj>0 _j≠ y _j>0, where μj _j can be written as μj=δμ(j)()+∑i∈ℰ¯[(δwi(j))+(βi−si)+(δwi(j))−(si−αi)]; _j=δμ^(j)( s)+ _i∈ E [(δw^(j)_i)^+( _i-s_i)+(δw^(j)_i)^-(s_i- _i) ]\,; (21) Proof. Recall that finding the conditions for ℰE to be an AXp is equivalent to find conditions for which a label flip cannot occur. Since cases satisfy the conditions of Lemma 2, and we will exploit it below. We begin from the most general case. Bounded asymmetric. Eq. 21 follows directly from the lemma. An adversary can flip the label if and only if there exist a counterexample ∗∈ℰ() s^* _E( s) such that argmaxjfj(∗)≠argmaxjfj() _jf_j( s^*)≠ _jf_j( s), or, equivalently, maxj≠y^μj>0 _j≠ y _j>0. If μj>0 _j>0, then max∗∈ℰ()fj(∗)−fy^(∗)>0 _ s^* _E( s)f_j( s^*)-f_ y( s^*)>0, that is, ∗ s^* ensures class j attains a larger logit than the prediction y y. Conversely, if maxjμj≤0 _j _j≤ 0, no ∗ s^* can induce a label flip. Bounded symmetric. This is a corollary of Lemma 2, as the symmetric domain [α,β]b[α,β]^b is a special case of the asymmetric case. Denoting with ¯∈ℰ() s _E( s) the activation with ¯¯ℰ=α+β2¯ℰ s_ E= α+β21_ E, we can write max∗∈ℰ()δμj(∗) _ s^* _E( s)δ _j( s^*) =∑i∈ℰδwi(j)si+∑i∈ℰ¯max(δwi(j)β,δwi(j)α)+δw0(j) = _i δw^(j)_is_i+ _i∈ E (δw^(j)_iβ,δw^(j)_iα )+δ w^(j)_0 (22) =∑i∈ℰδwi(j)si+∑i∈ℰ¯δwi(j)s¯i+δw0(j)⏟δμj(¯)−∑i∈ℰ¯δwi(j)s¯i+∑i∈ℰ¯max(δwi(j)β,δwi(j)α) = _i δw^(j)_is_i+ _i∈ Eδw^(j)_i s_i+δ w^(j)_0_δ _j( s)- _i∈ Eδw^(j)_i s_i+ _i∈ E (δw^(j)_iβ,δw^(j)_iα ) (23) =δμj(¯)−α+β2∑i∈ℰ¯δwi(j)+∑i∈ℰ¯max(δwi(j)β,δwi(j)α) =δ _j( s)- α+β2 _i∈ Eδw^(j)_i+ _i∈ E (δw^(j)_iβ,δw^(j)_iα ) (24) Now we make use of max(a,b)=(a+b+|a−b|)/2 (a,b)=(a+b+|a-b|)/2 to rewrite max(δwi(j)β,δwi(j)α)=(α+β)2δwi(j)+(β−α)2|δwi(j)| (δw^(j)_iβ,δw^(j)_iα )= (α+β)2δw^(j)_i+ (β-α)2|δw^(j)_i| (25) and substituting back to the previous expression we get the result: max∗∈ℰ()δμj(∗) _ s^* _E( s)δ _j( s^*) =δμj(¯)−α+β2∑i∈ℰ¯δwi(j)+∑i∈ℰ¯[(α+β)2δwi(j)+(β−α)2|δwi(j)|] =δ _j( s)- α+β2 _i∈ Eδw^(j)_i+ _i∈ E [ (α+β)2δw^(j)_i+ (β-α)2|δw^(j)_i| ] (26) =δμj(¯)+β−α2∥δℰ¯(j)∥1 =δ _j( s)+ β-α2 δ w^(j)_ E _1 (27) Bounded from below. We first check if there are any positive weights. Because S is only bounded from below, by rewriting the logit difference expression as δμj(∗)=δμ(j)()+∑i∈ℰ¯max(δwi(j),0)(si∗−si)+∑i∈ℰ¯max(−δwi(j),0)(si−si∗)δ _j( s^*)=δμ^(j)( s)+ _i∈ E (δw^(j)_i,0)(s^*_i-s_i)+ _i∈ E (-δw^(j)_i,0)(s_i-s^*_i) (28) we can see that the quantity (si∗−si)(s_i^*-s_i) is also unbounded. Therefore, any positive weight δwi(j)δw^(j)_i would naturally allow for ∗∈ s^* with fixed ℰ∗=ℰ s^*_E= s_E that give positive ℓμj(∗) _j( s^*). If ∃j≠y^,∃i∈ℰ¯∃ j≠ y,∃ i∈ E, such that δwi(j)>0δw^(j)_i>0, we get limsi∗→∞δμj(∗)=∞. _s^*_i→∞δ _j( s^*)=∞\,. (29) When these conditions are not met, i.e., for all j≠y^j≠ y and i∈ℰ¯i∈ E, δwi(j)<0δw^(j)_i<0, the μj _j expression can be derived from Lemma 2 and simplifies as88 8 To be precise, here we are taking the convention here that 0⋅(+∞)=00·(+∞)=0 as resulting from the limit of β→∞β→∞. μj _j =δμ(j)()+∑i∈ℰ¯[(δwi(j))+⏟=0(β−si)+(δwi(j))−(si−α)] =δμ^(j)( s)+ _i∈ E [ (δw^(j)_i)^+_=0(β-s_i)+(δw^(j)_i)^-(s_i-α) ] (30) =δμ(j)()−∑i∈ℰ¯δwi(j)(si−α) =δμ^(j)( s)- _i∈ Eδw^(j)_i(s_i-α) (31) Unbounded. follows directly from the previous case. Since the domain is unbounded, we have that if ∃j≠y^,∃i∈ℰ¯∃ j≠ y,∃ i∈ E, such that δwi(j)>0δw^(j)_i>0, limsi∗→∞δμj(∗)=∞ _s^*_i→∞δ _j( s^*)=∞ (32) or, if ∃j≠y^,∃i∈ℰ¯∃ j≠ y,∃ i∈ E, such that δwi(j)<0δw^(j)_i<0, limsi∗→−∞δμj(∗)=∞. _s^*_i→-∞δ _j( s^*)=∞\,. (33) This shows that non-zero weight differences in ℰ¯ E lead to a label flip for unbounded domains. ∎ B.2 The Probabilistic Concept Activations Case Proposition 3 only considers independent concept activations. When modeling concept activations as distributions, activations referring to alternative values of the same categorical concept (e.g., different colors) must sum to one, so independence no longer holds. We study this case separately. Let ⊊[0,1]bS [0,1]^b be the probability simplex for t>1t>1 categorical concepts. For each concept c∈[t]c∈[t], the number of values it can take are set to ncn_c, such that b=∑c=1tnc. b= _c=1^tn_c\,. (34) We indicate with B1,…,BtB_1,…,B_t the partitions induced by the t concepts over the b total activations. The probability simplex is given by =×c=1tΔnc−1,Δnc−1:=∈[0,1]nc:∑i∈Bczi=1.S= _c=1^t ^n_c-1, ^n_c-1:=\ z∈[0,1]^n_c: _i∈ B_cz_i=1\\,. (35) For a given ℰ∈[b]E∈[b], we denote with Fc:=Bc∖ℰF_c:=B_c the free coordinates per concept c that are not fixed by ℰE. Because activations in ℰE are fixed, the per-concept residual probability mass is given by γ:=∑ℰ∈Fcsi=1−∑i∈Bcsi.γ:= _E∈ F_cs_i=1- _i∈ B_cs_i\,. (36) We use this to prove how μj _j changes: Proposition 4. Let =×c=1tΔnc−1S= _c=1^t ^n_c-1, let ∈ s , let y y be the argmax of f()f( s) and let ℰ⊂[b]E⊂[b] be fixed. Define, for j≠y^j≠ y, μj:=δμ(j)()+∑c=1tρc,ρc:=[γcmaxi∈Fcδwi(j)−∑i∈Fcδwi(j)si] _j:=δμ^(j)( s)+ _c=1^t _c, _c:= [ _c _i∈ F_cδw^(j)_i- _i∈ F_cδw^(j)_i\,s_i ] (37) with the convention ρc=0 _c=0 when Fc=∅F_c= . A label flip is possible if and only if maxj≠y^μj>0 _j≠ y _j>0. Proof. We start from the logit difference expression for fj−fy^f_j-f_ y and consider a generic ∗∈ℰ() s^* _E( s) δμj(∗) δ _j( s^*) =δμ(j)()+∑i∈¯ℰδwi(j)(si∗−si) =δμ^(j)( s)+ _i∈ Eδw^(j)_i(s_i^*-s_i) (38) =δμ(j)()+∑c=1t∑i∈Fcδwi(j)(si∗−si), =δμ^(j)( s)+ _c=1^t _i∈ F_cδw^(j)_i(s_i^*-s_i)\,, (39) where the last step follows by the fact that only activations in FcF_c are allowed to differ to the original s. Because activations are bounded in each c∈[t]c∈[t], the maximum gain per concept is given by placing all residual probability mass μc _c to the highest weight difference, i.e., max∑i∈Fc∗∈δwi(j)(si∗−si)=γcmaxi∈Fcδwi(j). _ s^* _i∈ F_cδw^(j)_i(s_i^*-s_i)= _c _i∈ F_cδw^(j)_i\,. (40) Therefore, max∗∈ℰ()δμj(∗)=δμ(j)()+∑c=1t[γcmaxi∈Fcδwi(j)−∑i∈Fcδwi(j)si]=μj. _ s^* _E( s)δ _j( s^*)=δμ^(j)( s)+ _c=1^t [ _c _i∈ F_cδw^(j)_i- _i∈ F_cδw^(j)_i\,s_i ]= _j\,. (41) Clearly, if μj>0 _j>0 a label flip is possible and, viceversa, if μj<0 _j<0 no label flip can happen. ∎ B.3 Discussion We briefly discuss our theoretical results. First of all, the unbounded case recovers Proposition 1: it shows that unless ℰE covers all unbounded activations associated to a non-zero weight difference between the prediction y y and an alternative class j≠y^j≠ y, then it cannot be a weak AXp. Hence, any weak AXp is forced to cover all concept activations linking the prediction to any alternative class through a non-zero weight difference. The more such activations a CBM admits, the more (weak) AXp size blows up. This is precisely what happens with dense CBMs with unbounded logit activations in Section 5.1. It also backs up our suggestion to implement glasso at training time, as doing so is likely to reduce the number of non-zero weight differences, in turn shrinking the size of weak AXps. The bounded from below case recovers both CBMs modeling concepts using ReLU activations and Selective CBMs [Schrodi et al., 2025]. The logic is the same as for the unbounded case above, except that now AXps have to cover all concept activations associated to a positive weight difference, while negative weight differences can be left uncovered. While this can shrink explanation sizes, CBMs do not control for weight polarity during training. In contrast, our glasso strategy encourages differences to be zero, typically reducing the number of (positive and negative) weight differences between classes. This yields the improvements reported in Section D.5. The bounded symmetric case shows that what matters are the ranges of activations [α,β][α,β] and the range of weight differences δi(j)δ w^(j)_i for i∈¯ℰi∈ E. Smaller activation ranges leave less room for manipulating the concept activations, and smaller weight differences leave less room for translating these into a higher score for the alternative class j. This backs up our discussion of cosine similarity activations in Section 4.1, which constrain activations to [−1,1]b[-1,1]^b and are relevant to VLM-CBMs, and also partially motivates our suggestion to model concepts probabilistically, which constrains activations to [0,1]b[0,1]^b. It also suggests that shrinking the range of the learned weights, which enet and glasso both implicitly do, is beneficial for constraining the adversary in the bounded case. The bounded asymmetric case conveys essentially the same message. Finally, the probabilistic case shows that the exact condition for label flipping is stricter than that for the pure bounded (symmetric and asymmetric) case, meaning that the product-of-simplices structure of the activation space prevents it even more from constructing counterexamples. Since the concept activation space is fixed, the only knob for reducing the number of possible counterexamples – and therefore shrinking weak AXps – is the magnitude of the learned weights, which both enet and glasso can shrink. Further improvements may be gained by designing sparsification penalties targeting the quantities reported in our propositions; we will explore these in future work. Appendix C Experimental Details We ran all experiments on a 64-core machine with 256 GiB RAM and two RTX 5090 GPUs. These are used only for computing the CLIP embeddings and nothing else. Excluding this step, our experiments take about one full day to complete in this setup. Data preparation. For each dataset, we use the released train/validation/test partitions; for CUB, which has no validation split, we carve one via stratified sampling from the training split. Images are RGB and passed through CLIP’s own preprocessing transform without extra resizing or normalization. We discuss the preparation of each dataset in turn. For CelebA [Liu et al., 2015], we follow the pipeline of Debole et al. [2026a]. We translate each of the 4040 binary concept annotations from ±1\± 1\ to 0,1\0,1\, and predict Male from the others. Rather than subsampling, as in [Debole et al., 2026b], we keep all splits as they are. We stress that CelebA has no categorical concepts and therefore glasso does not apply to it. For Derm7pt [Kawahara et al., 2018], we take the seven dermoscopic checklist criteria from the meta.csv file shipping with the dataset and one-hot encode them into 2828 activations. Following [Kawahara et al., 2018], we also collapse the 2020 raw diagnoses into 55 classes (basal cell carcinoma, melanoma, nevus, seborrheic keratosis, and a miscellaneous class) by matching keywords. This reproduces their Table I. Depending on the experiment, Kawahara et al. [2018] perform one additional round of label merging; we skip this step. For WBCAtt [Tsutsui et al., 2023] we one-hot encode the 1111 morphological attributes into 3131 activations, and use the released 55-way cell-type label. For CUB [Wah et al., 2011], we follow Koh et al. [2020] by replacing per-image concept annotations with class-level concepts, using only data from the training split to determine the aggregation. Koh et al. [2020] aggregation step, however, does not treat categorical concepts are as such. Specifically, it thresholds each attribute independently, which often does not yield a one-hot vector useful for training categorical concepts. Moreover, Koh et al. [2020] filter out activations that do not contribute to at least 1010 classes, as these are too sparse/noisy to be predicted with high accuracy ([Koh et al., 2020, Appendix A]), and only 112112 activations survive this stage. This also removes categories from categorical concepts. Since we are interested in evaluating the interpretability of CBMs and the benefits of modeling concept activations probabilistically, rather than sheer prediction accuracy, we depart from their processing. First, we aggregate annotations by taking, within each of the 2828 categorical concepts the value with the largest share of positive votes, with ties broken at random. Moreover, we skip the filtering step. LLM-generated vocabularies All VLM-CBM vocabularies are taken directly from the LF-CBM, VLM-CBM and LaBo GitHub repositories and used as-is to compute, for each image, concept activations. Concretely, we compute the cosine similarity between each image embedding and each concept textual description, both normalized, obtaining concept activation that individually range in [−1,1][-1,1]. For the LF-CBM and VLM-CBM vocabularies, we filter out those activations that do not meet a fixed 0.250.25 threshold (computed on the training split, to avoid contamination), as done by Oikarinen et al. [2023], yielding bottleneck sizes of b=202b=202 for the LF-CBM vocabulary and b=419b=419 for the VLG-CBM one. Since the LaBo vocabulary is pre-filtered via submodular optimization [Yang et al., 2023], we keep all activations. Architectures. For all models, the concept probes and dense inference layers are sklearn [Pedregosa et al., 2011] logistic regressors fit using L-BFGS [Liu and Nocedal, 1989] with default hyperparameters. enet- and glasso-sparsified inference layers are fit with FISTA [Beck and Teboulle, 2009] with step size 1/L1/L, where L is the (approximate) Lipschitz constant of the loss, ensuring stability and quick convergence. C.1 Concept Activation Spaces: In- vs. Out-of-distribution Counterexamples In all experiments, we employ a model-specific activation space S for both testing whether heuristic explanations are (weak) AXps, and for constructing AXps with the exact algorithms. As anticipated in Sections 4.1 and 4.2, we set =(−∞,∞)bS=(-∞,∞)^b for logit-based CBMs, =[0,∞)bS=[0,∞)^b for ReLU CBMs and Selective CBMs, =[−1,1]bS=[-1,1]^b for VLM-CBMs with cosine similarity activations, and ⊆[0,1]bS [0,1]^b for CBMs modeling concepts probabilistically. Natural vs. out-of-distribution counterexamples. In all cases, the adversary can construct counterexamples by manipulating the activations not covered by explanations independently from each another – except for CBMs modelling concepts probabilistically, where activations of the same categorical concept are mutually constrained to sum to 11. This setup ignores correlations between concept activations, meaning (weak) AXps are required to be robust even against “out-of-distribution” (OOD) counterexamples that the bottleneck does not naturally output. While this choice does not invalidate our modeling and algorithmic contributions, we wish to elucidate the rationale behind it. First, even though OOD counterexamples cannot be generated by the backbone, they can be manually constructed by (possibly ill-intentioned) stakeholders intervening on the model. By ensuring our activation spaces S match the full range of attainable activation vectors, we explicitly ensure our (weak) AXps are robust against all natural and human-constructed counterexamples. Second, ensuring an explanation does not admit naturally occurring counterexamples – with guarantees – requires inferring the image of the bottleneck, or at least to build a tractable outer approximation thereof. This is highly non-trivial [Singh et al., 2019, Zhang et al., 2018], making it technically challenging to construct explanations robust only to naturally occurring counterexamples. Regardless, while focusing on natural counterexamples only downgrades the guarantees that AXps provide, doing so can in principle shrink AXp size further. Hence, as mentioned in Section 7, we plan to investigate how to do so in future work. Appendix D Additional Experiments In this section, we report the following additional results: Section D.1 Presents an in-depth algorithmic comparison. Section D.2 Extends Q1 to logits vs. ReLU activations vs. probabilities, including CelebA. Section D.3 Extends Q2 to probability-based CBMs, including CelebA. Section D.4 Extends Q2 to all three available VLM-CBM vocabularies. Section D.5 Evaluates AXp sizes for Selective CBMs [Schrodi et al., 2025]. D.1 Extra: Algorithmic Comparison We compare EA+ against the original exact algorithm from [Marques-Silva, 2023], denoted EA, and the three heuristic algorithms – TopK-Act, TopK-Wei, and TopK-Prod – along several dimensions: explanation size, computational cost, and percentage of output explanations that are both faithful and subset-minimal (as per Definition 1). All tests are carried out on a random sample of 100100 test instances, kept fixed across experiments. Since CBMs with raw logits exhibit pathologic behavior, we focus on CBMs that model concepts with either probabilities (⊆[0,1]bS [0,1]^b) and VLM-CBMs modeling them as cosine similarities (=[−1,1]bS=[-1,1]^b), giving all algorithms a chance of producing compact explanations. CelebA has no categorical concepts that glasso can work with, so we only consider dense CBMs for this dataset. D.1.1 EA+ Outputs Smaller AXps than EA CBM CBM + glasso EA EA+ EA EA+ Dataset b Size Calls Size Calls Size Calls Size Calls CelebA 3939 20.8 ± 4.6 3939 12.6 ± 3.7 102102 – – – – Derm7pt 2828 17.1 ± 1.8 2828 8.3 ± 2.0 5353 3.1 ± 2.9 2828 2.1 ± 0.8 3333 WBCAtt 3131 9.9 ± 3.6 3131 8.2 ± 3.0 6060 2.6 ± 0.9 3131 2.4 ± 0.8 3737 CUB 312312 169.5 ± 28.5 312312 46.3 ± 18.6 221221 47.0 ± 9.9 312312 23.5 ± 3.6 134134 Table 6: Comparison between EA and our EA+ on regular CBMs with prob. activations. Bold indicates a size improvement of at least one activation. VLM-CBM VLM-CBM + glasso EA EA+ EA EA+ Dataset b Size Calls Size Calls Size Calls Size Calls LF-CBM 202202 201.0 ± 0.8 202202 200.9 ± 0.9 633633 36.9 ± 5.8 202202 35.3 ± 5.9 308308 VLG-CBM 419419 416.5 ± 1.5 419419 416.3 ± 1.5 12861286 78.0 ± 8.4 419419 66.5 ± 11.3 593593 Table 7: Comparison between EA and our EA+ on VLM-CBMs. Bold indicates a size improvement of at least one activation. As a first experiment, we compare EA and EA+ in terms of explanation size and number of oracle invocations, averaged across the 100100 test instances. Both algorithms are exact in that they are guaranteed to always output (subset-minimal) AXps, but neither ensures these are size-minimal. The results on dense and glasso-sparsified CBMs are reported in Table 6 and those for VLM-CBMs in Table 7. EA+ always produces smaller AXps. Let us begin from explanation size. The tables indicate that EA+ always produces smaller explanations compared to the original algorithm. This is expected considering it i) exploits information about the instance and the model to determine a ranking over activations, and i) picks the smallest AXp for all three possible heuristic rankings, cf. Appendix A. The size reduction is more noticeable for dense CBMs. E.g., for CUB, it drops from nearly 170170 activations to about 4646. The improvement is more limited for glasso-sparsified CBMs, especially on Derm7pt and WBCAtt. Owing to the benefits of structured sparsification, EA already performs very well. Still, on CUB under glasso, EA explanations cover about 4747 activations, while EA+ only 2424. The size delta is minimal for dense VLM-CBMs, regardless of vocabulary, due to cosine similarity activations failing to properly constrain the adversary, while a gap forms for sparse VLM-CBMs, with improvements of about 1.51.5 and 11.511.5 activations depending on the chosen vocabulary. EA+ makes less than 3×3× oracle calls per run. Recall that EA+ runs each ∗ TopK^* once, each time making a logarithmic number of oracle calls, whereas EA calls the oracle exactly b times with no early exit. The tables show that, in practice, EA tends to make fewer total calls in many cases – e.g., dense CelebA/dense (3939 vs. 102102), Derm7pt/dense (2828 vs. 5353), WBCAtt/dense (3131 vs 6060), Derm7pt/sparse (2828 vs. 3333), WBCAtt (3131 vs. 3737). The worst offenders are the dense VLM-CBMs, where EA+ makes as much as three times the number of calls (202202 vs. 633633 and 419419 vs. 12861286). This is because concept activations are independent, meaning the Shrink step has to test each of the activations covered by the candidate weak AXps individually. However, EA+ makes fewer calls in selected cases, and specifically for dense and sparse CBMs on CUB (312312 vs. 221221 and 312312 vs. 134134, respectively). In short, in the worst case, EA+ can be more demanding than EA, but it typically does not pay the entire 3×3× cost. In fact, while EA+ invokes ∗ TopK^* three times – which helps with finding smaller AXps – thanks to binary search it can pay less than the full 3×3× price. As we will show next, despite making more oracle calls, EA+ remains affordable in terms of wall-clock time. D.1.2 EA+ Is Computationally Affordable Next, we compare the practical computational cost EA+ with that of the TopK heuristics. To this end, we measure wall-clock times and the number of oracle calls, averaged across the 100100 test explanations. Recall that EA+ is guaranteed to output an AXp, while the TopK heuristics likely don’t unless the budget k is sufficiently large. For fairness, we compare here EA+ against the TopK∗bs^*_bs algorithm (Algorithm 4), which selects k automatically to ensure the output is a (weak) AXp and makes use of binary search to cut on the number of oracle calls. This gives it two substantial advantages over heuristics as used in the literature. CBM CBM + glasso TopK∗ TopK^* EA+ TopK∗ TopK^* EA+ Dataset b Calls Time Calls Time Calls Time Calls Time CelebA 3939 66 0.0010.001 102102 0.0070.007 – – – – Derm7pt 2828 66 0.0040.004 5353 0.0250.025 66 0.0040.004 3333 0.0160.016 WBCAtt 3131 66 0.0050.005 6060 0.0400.040 66 0.0060.006 3737 0.0260.026 CUB 312312 99 0.7040.704 221221 16.60716.607 99 0.7040.704 134134 10.66710.667 Table 8: Runtime cost of all algorithms for regular CBMs. Time is measured in seconds. VLM-CBM VLM-CBM + glasso TopK∗ TopK^* EA+ TopK∗ TopK^* EA+ Dataset b Calls Time Calls Time Calls Time Calls Time LF-CBM 202202 88 0.0050.005 633633 0.1880.188 88 0.0060.006 308308 0.1470.147 VLG-CBM 419419 99 0.0120.012 12861286 1.0951.095 99 0.0200.020 593593 1.2151.215 Table 9: Runtime cost of all algorithms for VLM-CBMs. Time is measured in seconds. The results for CBMs in Table 8 and those for VLM-CBMs in Table 9 tell the same story: EA+ makes far more calls to the oracle than the TopK∗bs^*_bs algorithm, yet it remains affordable. The reason behind the extra calls is the checking phase: TopK∗bs^*_bs only invokes the oracle a logarithmic number of times (thanks to binary search) for growing an explanation; on the other hand, like EA, EA+ invokes it an additional linear number of times for ensuring subset minimality. However, we stress that, in the worst case, computing a (compact) AXp with EA+ takes 1111s on CUB for dense CBMs. While slower, it is very much affordable. The benefit, as we will see momentarily, is that EA+ always outputs smaller explanations than the heuristics. D.1.3 EA+ Finds The Most Compact Explanations CBM CBM + glasso Dataset Act Wei Prod EA+ Act Wei Prod EA+ CelebA 35.0 ± 3.8 15.7 ± 4.9 29.6 ± 5.1 12.6 ± 3.7 – – – – Derm7pt 9.5 ± 2.8 13.4 ± 5.0 9.7 ± 2.5 8.3 ± 2.0 7.7 ± 1.8 2.3 ± 0.7 2.2 ± 0.9 2.1 ± 0.8 WBCAtt 10.7 ± 4.3 17.5 ± 4.8 11.0 ± 4.9 8.2 ± 3.0 8.7 ± 3.2 3.5 ± 0.9 4.1 ± 1.3 2.4 ± 0.8 CUB 50.3 ± 19.0 84.7 ± 36.8 55.4 ± 21.8 46.3 ± 18.6 44.4 ± 14.6 30.0 ± 5.2 28.2 ± 4.3 23.5 ± 3.6 Table 10: Comparison between explanation sizes across datasets for regular CBMs. CBM CBM + glasso Dataset Act Wei Prod EA+ Act Wei Prod EA+ LF-CBM 202.0 ± 0.2 201.8 ± 0.5 201.8 ± 0.5 200.9 ± 0.9 201.3 ± 1.3 39.0 ± 6.8 39.1 ± 6.8 35.3 ± 5.9 VLG-CBM 418.6 ± 0.6 418.1 ± 1.1 418.2 ± 1.1 416.3 ± 1.5 418.0 ± 2.1 71.6 ± 12.2 71.7 ± 12.2 66.5 ± 11.3 Table 11: Comparison between explanation sizes for CUB using VLM-CBM vocabularies. Next, we evaluate the average size of the explanations extracted by the various algorithms. We report the results for regular and glasso-sparsified CBMs in Table 10, marking the smallest average explanations for each model in bold. As expected, EA+– thanks to the shrink step (Algorithm 3) – always finds smaller explanations, and this holds for both dense and sparse CBMs. Results for CBMs. For dense CBMs (Table 10, left), compared to the runner-up, EA+ achieves average size 12.612.6 (vs. 15.715.7 for the runner up, bottleneck size b=39b=39) in CelebA; 8.38.3 (vs. 9.79.7, b=28b=28) for Derm7pt; 8.28.2 (vs. 10.710.7, b=31b=31) for WBCAtt; and 46.346.3 (vs. 50.350.3, b=312b=312) for CUB. The difference is in-between 1.41.4 activations on average for Derm7pt and 99 for CUB. For glasso-sparsified CBMs (Table 10, right), the gap tightens, further supporting our usage of glasso to contrast Proposition 1. The only algorithm showing no benefit from glasso is TopK-Act, which does not directly depend on the learned weights. EA+ still outperforms all heuristics, but (compared to the runner-up) by less than one activation on average on Derm7pt, about 11 activation in WBCAtt, and 55 activations on CUB. Results for VLM-CBMs. We report additional results on dense and glasso-sparsified VLM-CBMs in Table 11. Recall that the LF-CBM vocabulary comprises 202202 activations and the VLG-CBM one 419419. Here, concept activations are cosine similarities, which explains the large explanations output by all algorithms – and the small gaps between them – when using dense inference layers (Table 11, left): this is yet another instance of Proposition 1 and it is consistent with the poor results reported for cosine similarity activations in Section 5.2. The picture is more favorable for sparse CBMs, with explanation sizes dropping sharply for all algorithms (except TopK-Act, as above). Again, EA+ is the winner across the board, with an advantage of 44 activations on average for the LF-CBM vocabulary and of 55 activations for the VLG-CBM one. Summary. While EA+ provides a modest advantage, size-wise, over the competitors, it is by far the most reliable alternative, as there is no obvious ranking between heuristics, barring poor interactions between TopK-Act with sparsification. D.1.4 EA+ Always Finds AXps, Heuristics Very Often Do Not We evaluate whether the algorithms are capable of computing explanations that are both faithful (sufficient to defend the prediction) and subset-minimal, as required by Definition 1. Since all algorithms, including our TopK heuristics, always return a weak AXp, as explained in Appendix A, we only need to check how frequently these are also subset-minimal. TopK Dataset Act Wei Prod EA+ CelebA 0%0\% 10%10\% 1%1\% % 100\% Derm7pt 37%37\% 2%2\% 37%37\% % 100\% WBCAtt 9%9\% 0%0\% 12%12\% % 100\% CUB 5%5\% 1%1\% 5%5\% % 100\% Average 12.8%12.8\% 3.5%3.5\% 13.8%13.8\% % 100\% TopK Dataset Act Wei Prod EA+ CelebA – – – – Derm7pt 0%0\% 81%81\% 85%85\% % 100\% WBCAtt 0%0\% 18%18\% 22%22\% % 100\% CUB 0%0\% 1%1\% 1%1\% % 100\% Average 0%0\% 33.4%33.4\% 36%36\% % 100\% Table 12: Whereas EA+ always computes AXps, heuristics do not. Left: dense CBMs. Right: glasso-sparsified CBMs. We compute the percentage of subset-minimal explanations across 100100 test instances and report the results for regular CBMs in Table 12. The table indicates that, as expected, EA+ retrieves subset-minimal AXps for every instance, model and dataset. The heuristics, on the other hand, never achieve 100%100\% subset-minimality. For dense CBMs, they attain at best 37%37\% subset-minimality (on Derm7pt with TopK-Act and TopK-Prod), but the percentage can go as low as 0%0\% (on CelebA with TopK-Act). The weight-based heuristics, TopK-Wei and TopK-Prod, fare better on glasso-sparsified CBMs, in that they manage to achieve high percentage of subset-minimality on Derm7pt (up to 85%85\%); yet they still fail catastrophically on CUB, where the best heuristic attains 1%1\% subset-minimality. In conclusion, these results demonstrate the advantages of EA+ over common heuristics. D.2 Extended Q1: Logits vs. ReLUs vs. Probabilities We report a comparison of all common concept activation modeling strategies – logits, ReLU activations, probabilities – in Fig. 3. Figure 3: Modeling concepts as probabilities shrinks AXps the most on all datasets. From the top: CelebA, Derm7pt, WBCAtt, CUB). Left to right: logits, ReLU, probabilities. ReLUs sit in-between logits and probabilities. All datasets display the same trend: logits (=(−∞,+∞)bC=(-∞,+∞)^b) are pathologic, probabilities (⊆[0,1]bC [0,1]^b) enable more compact AXps for all algorithms, and ReLU activations (=[0,∞)bC=[0,∞)^b) sit in-between, as shown by the curves in the middle row. This is perfectly in line with Proposition 1. TopK-Act and TopK-Prod underperform on CelebA. This is evident when comparing the curves of the heuristic algorithms in CelebA (top row) and on the other datasets (other rows). The reason is simple. This is because CelebA only has binary concepts, which means =[0,1]bS=[0,1]^b, with no simplex structure, leaving the adversary less constrained than in other datasets. This directly penalizes heuristics focusing on the highest activations. D.3 Extended Q2: enet vs. glasso for Probabilities Fig. 4 reports a complete comparison of enet vs. glasso sparsification for all datasets with categorical concepts, as these are needed to define the groups used by glasso. These include Derm7pt, WBCAtt, and CUB, but not CelebA. As in Section 5.2, we focus on CBMs with probabilistic activations, which are much better behaved than CBMs with logit activations (as per Section 5.1). Figure 4: enet (middle) works partially, glasso (below) works consistently. enet partially works, glasso is more consistent. The results are compatible with those reported in Section 5.2 for CUB: while enet primarily helps EA+, it makes some heuristics – TopK-Wei and TopK-Prod– misbehave as it learns larger non-zero weights. On the other hand, glasso helps more consistently across algorithms. At the same time, TopK-Act does not benefit from sparsification as much for either penalty. D.4 Extended Q2: Sparsity on VLM-CBMs Here, we report the complete FCCs for all VLM-CBM vocabularies. Recall that concept activations are modelled as cosine similarities. Figure 5: Q3: For VLM-CBMs, glasso outperforms other sparsification strategies, as shown here with CUB. Each VLM-CBM employs its own LLM-generated vocabulary, with LaBo’s sporting 10,00010,000 activations. glasso outperforms enet on all vocabularies. The FCCs in Fig. 5 – dense above, enet in the middle, and glasso at the bottom – indicate a large margin in the percentage of explained examples admitting a smaller weak AXp. As before, despite employing bounded concept activations, dense VLM-CBMs display pathologic behavior, precisely because their weights are dense. Introducing enet (middle row) helps: focusing on EA+ for LF-CBM, about 80%80\% explained instances admit (weak) AXps of size ∼160 160 (where the full bottleneck holds 202202 activations); for VLG-CBM, of size ∼300 300 (compared to 419419); for LaBo, of size ∼5,000 5,000 (compared to 10,00010,000). The heuristic algorithm, however, do not see any size improvement, backing up our observations in Section 5.2. In stark contrast, glasso dramatically shrinks explanations of all algorithms except TopK-Act (again, as noted in Section 5.2). VLM-CBMs resist compactly faithul explanations. Despite the substantial improvements given by glasso, faithful explanations of size 100100 (for VLG-CBM) and up to 500500 (for LaBo) are unlikely to be human interpretable. This supports our key message: large concept bottlenecks should not be (always, at least) equated with reliable interpretability. We discuss possible ways to overcome this roadblock in Section 7 and leave an extensive evaluation to future work. D.5 Extra: SelectiveCBM Compared to standard CBMs, Selective CBMs [Schrodi et al., 2025] sparsify both concept activations (per-input) and weights (across inputs) by combining an instance-dependent gating function with an elastic net penalty. To assess the benefits of this double sparsification strategy, we compare Selective CBMs against: i) a baseline, namely dense CBMs with ReLU concept activations; and i) sparsified CBMs (enet for CelebA and glasso for WBCAtt) with logit activations. We apply them to two datasets, CelebA (no categorical concepts, i.e., glasso is unnecessary) and WBCAtt (several categorical concepts, i.e., glasso is useful). As usual, we maximize λ subject to the constraint that F1YF_1^Y is at most 10%10\% worse than the dense baseline, for fairness. Figure 6: Selective CBMs behave like ReLU CBMs and worse than sparsified CBMs in terms of AXp size, shown here for CelebA (top) and WBCAtt (bottom). Selective CBMs behave similarly to ReLU CBMs. Fig. 6 shows that Selective CBMs (left) behave similarly to ReLU CBMs (middle), i.e., they provide a moderate improvement to AXp size compared to regular CBMs (which are pathological, as shown in Section 5.1). The improvement applies chiefly to EA+ (in pink), whereas all heuristics continue to behave poorly. However, like ReLU CBMs, Selective CBMs underperform compared to appropriately sparsified CBMs even when these employ raw logits (right). This is most visible for EA+, TopK-Wei, and TopK-Prod, which all display the same trend, whereas TopK-Act lags behind by a fair amount. These results support our arguments in Sections 4.1 and B that, from the perspective of AXps, SelectiveCBM’s learnable gating function is equivalent to a pure ReLU: neither prevents the construction of counterexamples whenever the prediction can be flipped by pushing a concept activation sjs_j to +∞+∞. The only difference is the threshold for constructing the counterexample: for ReLUs it is 00, for Selective CBMs it is a possibly non-zero positive constant (i.e., the learned gating threshold).