# Learning Differentiable Programs with Admissible Neural Heuristics

arXiv: https://arxiv.org/abs/2007.12101 · HTML: https://mlsanity.com/paper/2007.12101/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2020.

## Built on by (most cited first, 30 of 32)

- [Symbolic Regression with a Learned Concept Library](https://mlsanity.com/paper/2409.09359/) (2024)
- [Scallop: A Language for Neurosymbolic Programming](https://mlsanity.com/paper/2304.04812/) (2023)
- [Top-Down Synthesis for Library Learning](https://mlsanity.com/paper/2211.16605/) (2022)
- [Towards Data-and Knowledge-Driven Artificial Intelligence: A Survey on Neuro-Symbolic Computing](https://mlsanity.com/paper/2210.15889/) (2022)
- [Logic-induced Diagnostic Reasoning for Semi-supervised Semantic Segmentation](https://mlsanity.com/paper/2308.12595/) (2023)
- [Programmatically Grounded, Compositionally Generalizable Robotic Manipulation](https://mlsanity.com/paper/2304.13826/) (2023)
- [Neurosymbolic Grounding for Compositional World Models](https://mlsanity.com/paper/2310.12690/) (2023)
- [Neural Program Generation Modulo Static Analysis](https://mlsanity.com/paper/2111.01633/) (2021)
- [From Perception to Programs: Regularize, Overparameterize, and Amortize](https://mlsanity.com/paper/2206.05922/) (2022)
- [Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars](https://mlsanity.com/paper/2211.01842/) (2022)
- [Program Synthesis Guided Reinforcement Learning for Partially Observed Environments](https://mlsanity.com/paper/2102.11137/) (2021)
- [Unsupervised Learning of Neurosymbolic Encoders](https://mlsanity.com/paper/2107.13132/) (2021)
- [Neurosymbolic Programming for Science](https://mlsanity.com/paper/2210.05050/) (2022)
- [Smoothing Methods for Automatic Differentiation Across Conditional Branches](https://mlsanity.com/paper/2310.03585/) (2023)
- [Large Language Models are Interpretable Learners](https://mlsanity.com/paper/2406.17224/) (2024)
- [Automatic Synthesis of Diverse Weak Supervision Sources for Behavior Analysis](https://mlsanity.com/paper/2111.15186/) (2021)
- [Efficient Non-Parametric Optimizer Search for Diverse Tasks](https://mlsanity.com/paper/2209.13575/) (2022)
- [Uncertainty Quantification for Neurosymbolic Programs via Compositional Conformal Prediction](https://mlsanity.com/paper/2405.15912/) (2024)
- [Lobster: A GPU-Accelerated Framework for Neurosymbolic Programming](https://mlsanity.com/paper/2503.21937/) (2025)
- [Hybrid Memoised Wake-Sleep: Approximate Inference at the Discrete-Continuous Interface](https://mlsanity.com/paper/2107.06393/) (2021)
- [Interpreting Expert Annotation Differences in Animal Behavior](https://mlsanity.com/paper/2106.06114/) (2021)
- [NESTER: An Adaptive Neurosymbolic Method for Causal Effect Estimation](https://mlsanity.com/paper/2211.04370/) (2022)
- [Differentiable Tree Search Network](https://mlsanity.com/paper/2401.11660/) (2024)
- [Programmatic Context Augmentation for LLM-based Symbolic Regression](https://mlsanity.com/paper/2605.03101/) (2026)
- [Synthesizing Machine Learning Programs with PAC Guarantees via Statistical Sketching](https://mlsanity.com/paper/2110.05390/) (2021)
- [Learning and Compositionality: a Unification Attempt via Connectionist Probabilistic Programming](https://mlsanity.com/paper/2208.12789/) (2022)
- [AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT](https://mlsanity.com/paper/2604.20744/) (2026)
- [Grounding vs. Compositionality: On the Non-Complementarity of Reasoning in Neuro-Symbolic Systems](https://mlsanity.com/paper/2604.26521/) (2026)
- [Compile Once, Differentiate Everywhere: A Differentiable Meta-Circular Interpreter](https://mlsanity.com/paper/2606.09930/) (2026)
- [Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data](https://mlsanity.com/paper/2606.11946/) (2026)

## Abstract (arXiv)

We study the problem of learning differentiable functions expressed as programs in a domain-specific language. Such programmatic models can offer benefits such as composability and interpretability; however, learning them requires optimizing over a combinatorial space of program "architectures". We frame this optimization problem as a search in a weighted graph whose paths encode top-down derivations of program syntax. Our key innovation is to view various classes of neural networks as continuous relaxations over the space of programs, which can then be used to complete any partial program. This relaxed program is differentiable and can be trained end-to-end, and the resulting training loss is an approximately admissible heuristic that can guide the combinatorial search. We instantiate our approach on top of the A-star algorithm and an iteratively deepened branch-and-bound search, and use these algorithms to learn programmatic classifiers in three sequence classification tasks. Our experiments show that the algorithms outperform state-of-the-art methods for program learning, and that they discover programmatic classifiers that yield natural interpretations and achieve competitive accuracy.