Explainability Requirements as Hyperproperties

Bernd Finkbeiner, Julian Siber · 2025

Read Explainability Requirements as Hyperproperties by Bernd Finkbeiner, Julian Siber (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16402.txt.

Introduction

Bernd Finkbeiner and Julian Siber take up a logic puzzle in their 2025 paper. Smart systems must not just act, but be able to say why. The pair ask how to state that need in exact terms. They treat it as a hyperproperty, a trait that links many runs of a system at once.

They blend three forms of logic to state when an agent knows why a thing took place. The blend can state a range of such needs for whole systems. They then show the logic fits inside a known hyperlogic. Best of all, checks in this logic can be solved by machine. That opens the door to auto checks of why-needs in real systems.

Catalog record

CREATORBernd Finkbeiner, Julian Siber
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-16402

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Explainability Requirements as Hyperproperties Bernd Finkbeiner, Julian Siber Abstract Explainability is emerging as a key requirement for autonomous systems. While many works have focused on what constitutes a valid explanation, few have considered formalizing explainability as a system property. In this work, we approach this problem from the perspective of hyperproperties. We start with a combination of three prominent flavors of modal logic and show how they can be used for specifying and verifying counterfactual explainability in multi-agent systems: With Lewis’ counterfactuals, linear-time temporal logic, and a knowledge modality, we can reason about whether agents know why a specific observation occurs, i.e., whether that observation is explainable to them. We use this logic to formalize multiple notions of explainability on the system level. We then show how this logic can be embedded into a hyperlogic. Notably, from this analysis we conclude that the model-checking problem of our logic is decidable, which paves the way for the automated verification of explainability requirements. 1 Introduction The increase in system complexity and opaqueness perceived in recent years has been answered by a plethora of techniques aimed at providing some sort of explanation for observed system behavior Almagor and Lahijanian 2020 ; Brandao et al 2022 ; Wachter et al 2018 ; Rosenfeld and Richardson 2019 . While this demonstrates a need for systems to be explainable, there is no formal theory to specify different notions of explainability and to algorithmically verify them. In this paper, we make the claim that hyperproperties, and their respective logics, are an excellent basis for such a formal theory of explainability. We start from previous theories for individual instances of explanations Halpern and Pearl 2005a ; Halpern and Pearl 2005b , which combine counterfactual and epistemic reasoning. Besides extending them to system specifications, we add temporal reasoning to specify explainability on the possibly infinite executions of multi-agent systems. We use modal operators for these three reasoning dimensions to express explainability requirements such as: \operatorname{\hbox to6.98pt{\vbox to6.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.25833pt\lower-1.11945pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} { {\lx@inpgf@ignorespaces}{{}}{} {\lx@inpgf@ignorespaces}{} {\lx@inpgf@ignorespaces}{} {\lx@inpgf@ignorespaces}{} {\lx@inpgf@ignorespaces}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\lxSVG@roundjoin\lxSVG@begingroup@{stroke-linejoin} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 -1.19 L 0 7.74 L 8.94 7.74 L 8.94 -1.19 Z}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}\Big(\lnot\mathit{offer}\rightarrow\big(\bigvee_{\alpha,\beta\in\mathit{Att}(a)}\mathtt{K}_{a}\left((\alpha\land\beta)\mcf_{a}\mathit{offer}\right)\big)\Big)\kern 5.0pt, which we simply term Internal Counterfactual Explainability (ICE). Interpreted in a hiring system where some agent a applies to get a job offer, ICE states that, whenever agent a does not get the offer (i.e., atomic proposition \mathit{offer} does not hold), they know that if they had applied with some (other) attribute values \alpha,\beta\in\mathit{Att}(a) , they would have gotten the offer. We call this notion internal because it depends only on actions performed by agent a themselves. The formula for ICE uses operators from all three modal logics that we fuse together: It uses the temporal operator \operatorname{\hbox to6.98pt{\vbox to6.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.25833pt\lower-1.11945pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} { {\lx@inpgf@ignorespaces}{{}}{} {\lx@inpgf@ignorespaces}{} {\lx@inpgf@ignorespaces}{} {\lx@inpgf@ignorespaces}{} {\lx@inpgf@ignorespaces}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\lxSVG@roundjoin\lxSVG@begingroup@{stroke-linejoin} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 -1.19 L 0 7.74 L 8.94 7.74 L 8.94 -1.19 Z}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}} to specify that the requirement holds at every time point and it uses the knowledge operator \mathtt{K}_{a} to express that agent a has knowledge about some counterfactual dependency expressed with the counterfactual operator \mcf_{a} . Later on, we will use this logic to formalize other aspects of explainability, such as weak , external , and general explainability. We will also see how these notions discriminate between – intuitively – explainable and unexplainable systems in Section 3 . This appeal to intuition is without alternative: There is no universally correct definition of explainability Köhl et al 2019 and much depends on the context and the agents involved. The strength of our modal-logic approach is exactly that it provides a flexible specification language that can be applied to varying contexts and definitions, while retaining a general model-checking algorithm. Double-fusions of the three modal logics we consider have been studied extensively: Epistemic temporal logic has been used in security for information-flow control Halpern and O’Neill 2008 ; Balliu et al 2011 , counterfactual temporal logic for expressing causal dependencies in reactive systems Finkbeiner and Siber 2023 ; Coenen et al 2022b , and counterfactual epistemic logics to characterize notions of rationality in game theory Stalnaker 2006 ; Sandu 2021 . Our work brings these diverse frameworks together based on the viewpoint that explainability is an intended flow of information about counterfactual dependencies . This interpretation stands in the tradition of a long line of works on individual causal explanations Lewis 1986 ; Halpern and Pearl 2005b ; Beckers 2022 ; Goyal et al 2019 . With this paper, we shift the focus away from the question of what constitutes a valid individual explanation toward analyzing the abstract epistemic properties that the global system needs to fulfill such that an explanation is available to an agent whenever it is needed. In short, we do not analyze explanations, but explainability . \pi_{n} … \pi_{1} … \pi … \pi_{k} … \mathtt{K}_{a}\,\varphi \varphi =_{\Omega(a)} =_{\Omega(a)} \neq_{\Omega(a)} (a) Semantics of the epistemic operator \mathtt{K}_{a} . \rho_{n} … \rho_{1} … \rho … \rho_{k} … \varphi\mcf_{a}\psi \varphi \psi <_{\Sigma_{a}^{\rho}} <_{\Sigma_{a}^{\rho}} <_{\Sigma_{a}^{\rho}} (b) Semantics of the counterfactual \mcf_{a} . Figure 1 : Illustrating the semantics of the statements \mathtt{K}_{a}\,\varphi and \varphi\mcf_{a}\psi on a set of traces. The statements are evaluated at the second position of the trace \pi , which is framed by the black square. The epistemic operator \mathtt{K}_{a} (cf. Subfigure 1(a) ) requires \varphi to hold at the same position on all traces \pi^{\prime} with an observation equivalent prefix, i.e., where \pi=_{\Omega(a)}\pi^{\prime} is satisfied. These positions are covered by the area with diagonal lines (colored red). In contrast, the counterfactual \mcf_{a} (cf. Subfigure 1(b) ) requires that the trace closest to \rho that satisfies \varphi , which is in this case \rho_{1} , also satisfies \psi at the same position. This is marked by the area with crossed lines (colored red and blue). <_{\Sigma_{a}^{\rho}} is used in the illustration to denote, e.g., (\rho_{n},\rho_{k})\in\Sigma_{a}^{\rho}\land(\rho_{k},\rho_{n})\notin\Sigma_{a}^{\rho} , which means that \rho_{n} is strictly more similar to \rho than \rho_{k} . Knowledge and Counterfactuals. The logic we consider is an extension of epistemic temporal logic, in particular of Linear Temporal Logic (LTL) with the knowledge modality \mathtt{K} (KLTL). We extend KLTL with counterfactual conditionals as defined by Lewis Lewis 1973 , which we interpret on paths of a multi-agent system. We illustrate the semantics of these two modal operators in Figure 1 . The epistemic formula \mathtt{K}_{a}\,\varphi is satisfied at a given position of a given trace if all traces that are indistinguishable for agent a satisfy \varphi (cf. Subfigure 1(a) ). Indistinguishability is defined based on the observation-equivalence =_{\Omega(a)} that compares the prefixes of two traces with respect to the observations of agent a . The Lewisian counterfactual \varphi\mcf_{a}\psi , on the other hand, informally has the following meaning: “If \varphi had been true then \psi might also have been true”. More formally, the counterfactual formula has the following semantics: it holds on a position i of a given trace if one of the closest traces that satisfy \varphi at i also satisfies \psi at i . These semantics are illustrated in in Subfigure 1(b) , where there is in fact a unique closest trace

Read the complete text