Symbolic Functional Decomposition: A Reconfiguration Approach

Mateus de Oliveira Oliveira, Wim Van den BroeckAAAI 2025 · DOI

Introduction

Functional decomposition is a fundamental technique in computer science and artificial intelligence aimed at breaking down a complex Boolean function $f$ into a composition of simpler component functions, such as $f = g(f_1, \dots, f_k)$. This process is vital for enhancing the modularity, interpretability, and explainability of AI systems. By decomposing a decision logic into smaller, understandable sub-tasks, researchers can better trace and verify the behavior of complex models.

Historically, functional decomposition has been computationally expensive. Traditional methods often rely on truth tables, which scale exponentially with the number of input variables, making them impractical for high-dimensional functions. This paper introduces a symbolic framework that leverages Ordered Binary Decision Diagrams (OBDDs) and automata theory to perform decomposition in fixed-parameter linear time.

Symbolic Representation and Automata

The core innovation of this work lies in its symbolic treatment of Boolean functions. Instead of explicit representations, the authors use OBDDs, where the "width" of the diagram serves as a proxy for the function's complexity.

A key insight is the conceptualization of an OBDD as a sequence of layers. By treating these layers as characters in an alphabet, a Boolean function can be viewed as a "string." This allows the authors to employ second-order finite automata to represent entire classes of functions. These automata can process the symbolic layers of an OBDD to determine if the function belongs to a specific complexity class or if it can be decomposed into simpler parts.

A sequence of OBDD layers representing a Boolean function symbolically.

Functional Reconfiguration

Beyond simple decomposition, the authors introduce the concept of functional reconfiguration. This approach ensures that not only are the final components simple, but every intermediate function generated during the evaluation of the decomposition "recipe" (represented as a Boolean circuit $C$) also remains within a specified complexity bound. This "reconfiguration width" provides a novel metric for ensuring that the entire computational path remains interpretable and well-structured.

Complexity and Fixed-Parameter Tractability

The paper proves that the problem of functional decomposition is fixed-parameter tractable (FPT). By fixing parameters such as the number of factor functions ($k$), the maximum allowed OBDD width ($p$), and the size of the combining circuit ($m$), the authors demonstrate that the decomposition can be found in time that scales linearly with the size of the input function's OBDD ($|D|$).

The formal result (Theorem 10) establishes a time complexity of $O(2^{p^{O(2^m)}} \cdot |A|^k \cdot |D|)$. While the constant factors are double-exponential—limiting practical application to small parameter values—the linear scaling with respect to $|D|$ represents a significant theoretical advancement over previous exponential-time algorithms.

Applications and Future Directions

The framework is versatile enough to solve related problems, such as identifying "Generalized Juntas"—functions that are Boolean combinations of $k$ simpler functions—even when the combining logic is unknown. It also provides an FPT algorithm for OBDD factorization, a symbolic counterpart to the difficult problem of factoring deterministic finite automata (DFAs).

Despite these advances, the framework is currently limited to the Boolean domain. Future research may explore extending these symbolic techniques to continuous or real-valued functions, which are more common in modern deep learning. Additionally, integrating this symbolic approach with active learning strategies could allow for the decomposition of functions where the target OBDD is not fully known but can be queried.

Summary updated

BibTeX
@inproceedings{oliveira2025symbolic,
  author = {Mateus de Oliveira Oliveira and Wim Van den Broeck},
  title = {{Symbolic Functional Decomposition: A Reconfiguration Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i2.32117},
}
Figure