Searching for Actual Causes: Approximate Algorithms with Adjustable Precision

Actual causes differ from general explanations: The paper highlights a key gap in current AI explainability—most systems explain general patterns, but users typically want to know what specifically caused their particular outcome. The authors argue that formal "actual causation" better matches what people expect from explanations.

Finding actual causes is computationally hard but now more practical: Identifying actual causes was previously proven to be NP-complete (extremely difficult computationally), making it impractical for real applications. This paper introduces the first polynomial-time approximate algorithms that can find actual causes with adjustable precision, making the approach feasible for real-world use.

The solution works beyond simple models: Previous algorithms only worked for narrow classes of models and typically found just one cause. The new approach handles more complex, realistic scenarios including non-Boolean variables and stochastic (probabilistic) models, expanding where actual causation can be applied.

The problem can be broken into smaller pieces: The paper proves that actual-cause identification can be decomposed into smaller sub-problems without losing solutions. This theoretical insight directly enables more efficient algorithms and suggests a practical path forward for implementation.

Bridges theory and practice in responsible AI: By making formal causality theory computationally tractable, this work helps close the gap between rigorous philosophical foundations for explainability and what can actually be deployed in real AI systems—a critical step for trustworthy AI.