Learning To Control BDD Size

Binary Decision Diagrams (BDDs) are canonical representations of Boolean functions widely used to compactly and exactly represent and query large state spaces across computer science and artificial intelligence. Their principal limitation is a severe dependence on variable ordering, under which the same function can admit exponentially different representation sizes. Dynamic variable reordering (DVR) addresses this problem using hand-designed heuristics that search over orderings through sequences of adjacent variable swaps, often requiring substantial reordering effort to obtain high-quality solutions. We instead formulate DVR as a sequential decision-making problem and investigate whether good reordering decisions can be learned and generalized. First, we show that tabular reinforcement learning can discover orderings that closely match the strongest established heuristics while requiring only a small number of swaps at execution. We then distill these learned action values into a neural controller built around a compositional bottom-up encoder of BDD subgraphs and hierarchical attention that aggregates and contextualizes variable-level structure. The resulting policy generalizes to unseen Boolean functions and to larger variable counts than observed during training, retaining near-teacher reordering quality while using only a small fraction of the swaps required by competitive search-based heuristics. These results suggest that expensive online combinatorial search over symbolic representations can be substantially replaced through learned control.