NeSyCAPE: Neuro Symbolic Constraint Aware Program Execution

One effective strategy for handling complex compositional Question Answering is to decompose questions into atomic-concept questions and compose the answers through executable programs, a so-called neurosymbolic methodology. Although effective, these methods often predict atomic concepts locally, which can produce individually plausible but globally inconsistent predictions and lead to incorrect program outputs. To address this limitation, we propose NeSyCAPE, a framework that integrates global consistency constraints into differentiable program execution. We represent each task as a graph of entities, relations, and atomic concepts. A query-specific executable program is then defined over this graph to compose the concepts required to answer the question, while domain knowledge is encoded as logical constraints over the involved concepts. This shared representation allows query-specific execution and global consistency to jointly influence the final answers. During training, executable supervision and differentiable global constraints jointly update the atomic concept predictors. At inference time, constrained optimization combines the neural prediction scores while satisfying the global constraints to produce a feasible concept assignment from which program execution determines the answer. We evaluate NeSyCAPE across three reasoning problems with increasing execution and global-consistency requirements: Temporal QA, Spatial VQA, and KB-VQA. Our results show that executable supervision substantially improves over local prediction baselines, while incorporating global consistency provides further gains in program execution.