Grammar Filtering For Syntax-Guided Synthesis - Mark Santolucito

Leading program synthesis researcher Mark Santolucito (Assistant Professor, Barnard College, Columbia University) discusses his paper "Grammar Filtering for Syntax-Guided Synthesis".

This conversation explores how machine learning can be used to shrink the search space of syntax-guided synthesis (SyGuS) problems, dramatically speeding up synthesis without sacrificing the strong correctness guarantees of formal methods.

Mark shares the unexpected origin story of the paper, which began at a hackathon in Bermuda, explains the core ideas behind grammar filtering, and reflects on the broader role of neurosymbolic approaches in modern program synthesis.

In This Episode -

• What program synthesis is and why it matters

• Intro to syntax-guided synthesis (SyGuS)

• Why grammar size dominates synthesis runtime

• How machine learning can safely prune grammars before synthesis

• Predicting both criticality and runtime impact of grammar terminals

• Combining neural guidance with SMT-based synthesis solvers

• Results from SyGuS benchmarks (including ~50% runtime improvements)

• Reflections on the future of neurosymbolic program synthesis

About the Paper -

"Grammar Filtering for Syntax-Guided Synthesis"

Kairo Morton, William Hallahan, Elven Shum, Ruzica Piskac, Mark Santolucito

Published at AAAI 2020

The paper introduces a machine-learning–based technique for identifying and removing low-utility grammar terminals in SyGuS problems, significantly accelerating synthesis while maintaining correctness guarantees.

https://arxiv.org/abs/2002.02884

About the Guest -

Mark Santolucito is an Assistant Professor of Computer Science at Barnard College, Columbia University, where he develops novel program synthesis and analysis techniques to help programmers interact with code more effectively with a focus on Temporal Logic.

https://www.marksantolucito.com

Credits -

• Host & Music: Bryan Landers, Technical Staff, Ndea

• Editor: Alejandro Ramirez

• https://x.com/ndea

• https://ndea.com

• https://x.com/bryanlanders