Abstract Synthesis

Jeremy Budd, Assistant Professor at the University of Birmingham, and Tim Scarfe, CEO of Machine Learning Street Talk, discuss the paper “Why Creativity Cannot Be Interpolated”, which argues that genuine creativity requires respect for constraints that today’s AI lacks.

Building on ideas from François Chollet, Kenneth Stanley, and others, explore why AI slop is the result of novelty unconstrained by understanding and how systems capable of extending their own phylogeny could become creative, regardless of substrate.

In This Episode -

• Creativity vs. interpolation
• Understanding as structured constraint-following
• Picbreeder’s evolutionary image representations
• AlphaZero and creative game play
• Why LLMs remain highly derivative
• Human-AI co-creativity
• Open-ended search vs. optimization
• Evolvable representations and abstraction
• Constraints enable creativity
• Future directions beyond gradient descent

References -

• CBMM10 Panel: Research on Intelligence in the Age of AI - https://www.youtube.com/watch?v=Gg-w_n9NJIE&t=2885
• “Sparks of Artificial General Intelligence: Early experiments with GPT-4” - https://arxiv.org/abs/2303.12712
• Chollet: “On the Measure of Intelligence” - https://arxiv.org/abs/1911.01547
• Stanley: PicBreeder - https://picbreeder.net/6793
• Sakana’s PicBreeder Experiment - https://pub.sakana.ai/picbreeder-vlm/
• ARC-AGI-3 - https://arcprize.org/arc-agi/3

About the Paper -

“Why Creativity Cannot Be Interpolated: And Why Understanding Is the Path to Get There”
Jeremy Budd and Tim Scarfe

The paper argues that novelty alone is insufficient for creativity. Instead, creative systems must develop structured, path-dependent representations that preserve the constraints underlying previous discoveries, allowing them to extend rather than merely recombine existing ideas. Through examples including Picbreeder, AlphaGo, AlphaZero, and modern large language models, the authors propose that human-AI collaboration currently offers the strongest path toward genuinely creative machine intelligence.

https://arxiv.org/abs/1911.01547

About the Guests -

Dr. Jeremy Budd is Assistant Professor of Mathematics at the University of Birmingham. His research focuses on the intersection of applied analysis and data science, specializing in graph-based learning methods for image processing.

https://jeremybudd.com/

Dr. Tim Scarfe is the founder and host of the popular AI podcast Machine Learning Street Talk (MLST). He’s a multi-time startup founder and was previously a Principal Engineer at Microsoft and Chief Data Scientist at bp. He has a Ph.D in machine learning and a first-class degree in computer science.

https://www.mlst.ai/about
https://www.youtube.com/@MachineLearningStreetTalk

Credits -

• Host & Music: Bryan Landers, Technical Staff, Ndea
• Editor: Alejandro Ramirez
• https://x.com/ndea
• https://x.com/bryanlanders
• https://ndea.com

Loris D’Antoni, Professor of Computer Science and Engineering at UC San Diego, discusses his paper “Constrained Adaptive Rejection Sampling,” which introduces a constrained decoding algorithm that preserves the original language model distribution while satisfying formal constraints, enabling higher-quality structured generation for applications including compiler testing, code generation, and scientific discovery.

Explore how the rise of large language models has reshaped research in programming languages, and how formal methods remain essential for producing software that is both useful and trustworthy in the era of AI-generated code.

In This Episode -

• Program synthesis in the age of LLMs
• Why constrained decoding distorts language model distributions
• Adaptive rejection sampling with remembered failures
• Formal methods for trustworthy AI-generated code
• Compiler fuzzing with language models
• Using symbolic methods to improve LLM output
• Automata theory
• Verified code translation and equivalence checking

References -
• UCSD Programming Systems: https://cseweb.ucsd.edu/groups/progsys/
• Nadia Polikarpova: https://cseweb.ucsd.edu/~npolikarpova/
• Rajeev Alur: https://www.cis.upenn.edu/~alur/
• Code Metal: https://www.codemetal.ai/

About the Paper -

“Constrained Adaptive Rejection Sampling”
Loris D’Antoni, Pavel Parys, Sriram Vadia, Taylor Berg-Kirkpatrick

Large language models often rely on constrained decoding to generate outputs that satisfy grammars or structured schemas, but existing methods can substantially distort the model’s probability distribution. This paper introduces Constrained Adaptive Rejection Sampling (CARS), an algorithm that incrementally learns from rejected samples while provably sampling from the correct constrained distribution, producing significantly higher-quality outputs and large improvements in practical tasks such as compiler fuzzing.

https://arxiv.org/pdf/2510.01902

About the Guest -

Loris D’Antoni is Jacobs Faculty Scholar and Professor of Computer Science and Engineering at the University of California, San Diego, where he leads the Programming Systems Group. His research spans program synthesis, programming languages, formal verification, compiler testing, and trustworthy AI systems, with recent work focusing on combining formal methods with LLMs. He also serves as a Scholar at Code Metal, where he works on verified AI-assisted software engineering.
https://cseweb.ucsd.edu/~ldantoni/

Credits -
• Host & Music: Bryan Landers, Technical Staff, Ndea
• Editor: Alejandro Ramirez
• https://x.com/ndea
• https://x.com/bryanlanders
• https://ndea.com

Stephen Muggleton, Emeritus Professor at Imperial College London, discusses his paper “Inductive Logic Programming”, which introduced and named the field. The paper presents a framework that combines logic programming with machine learning, enabling systems to learn interpretable logical rules from examples and background knowledge.

Muggleton reflects on the intellectual origins of ILP, tracing its development through his PhD work under Donald Michie and his interactions with pioneering figures including John McCarthy, Ross Quinlan, and others from the early AI community. He describes how dissatisfaction with purely propositional learning systems motivated a search for richer representations capable of expressing structured knowledge and supporting scientific discovery.

In This Episode -

• Origins of ILP
• Michie, Turing, and AI research bans
• Logic programming meets machine learning
• Learning from positive examples
• Learning from a single example
• Predicate invention & abstraction
• Robot Scientist research program
• Efficient greedy search algorithms
• ILP & modern large language models

References -

• https://www.doc.ic.ac.uk/~shm/Papers/Reduce.pdf
• https://en.wikipedia.org/wiki/Donald_Michie
• https://en.wikipedia.org/wiki/John_McCarthy_(computer_scientist)
• https://en.wikipedia.org/wiki/Ross_Quinlan
• https://en.wikipedia.org/wiki/Karl_Popper

About the Paper -

“Inductive Logic Programming”
Author: Stephen Muggleton
Venue: New Generation Computing (1991)

The paper formally introduced inductive logic programming as a research field at the intersection of machine learning and logic programming. It argues that learning systems should be able to construct logical theories using both observed examples and existing background knowledge, enabling more expressive and interpretable forms of machine learning.

https://www.doc.ic.ac.uk/~shm/Papers/ilp.pdf

About the Guest -

Stephen Muggleton is Emeritus Professor of Machine Learning at Imperial College London. He is the founder of inductive logic programming and has made foundational contributions to machine learning, scientific discovery systems, program synthesis, and neurosymbolic AI. His research focuses on machine learning, logic-based reasoning, scientific discovery, probabilistic inference, and automated knowledge acquisition.
https://www.doc.ic.ac.uk/~shm/

Credits -

• Host & Music: Bryan Landers, Technical Staff, Ndea
• Editor: Alejandro Ramirez
• https://x.com/ndea
• https://x.com/bryanlanders
• https://ndea.com

Aws Albarghouthi, Associate Professor of Computer Science at the University of Wisconsin-Madison, discusses his paper “Recursive Program Synthesis”, which introduced Escher, an inductive synthesis algorithm for learning recursive programs from input-output examples.

The project emerged from Albarghouthi’s early work in program verification and inductive proofs for recursive procedures. After he and fellow graduate student Zachary Kincaid developed initial ideas for synthesizing recursive programs, they cold-emailed Sumit Gulwani at Microsoft Research, whose feedback and collaboration helped shape the direction of the paper.

In This Episode -

• Recursive synthesis from examples
• Escher’s forward and backward search
• Goal graphs for partial programs
• Components as reusable building blocks
• Synthesis benchmarks and comparisons with Sketch
• Quantum compiler synthesis
• Qubit mapping and routing synthesis- Agent correctness and prompt injection

References -

• Microsoft PROSE: https://www.microsoft.com/en-us/research/project/prose/
• SKETCH: https://people.csail.mit.edu/asolar/papers/Solar-Lezama09.pdf
• Generating Compilers for Qubit Mapping and Routing: https://arxiv.org/abs/2508.10781
• Synthesizing Quantum-Circuit Optimizers: https://arxiv.org/abs/2211.09691
• 'Introduction to Neural Network Verification' book: https://verifieddeeplearning.com/

About the Paper -

“Recursive Program Synthesis”
Aws Albarghouthi, Sumit Gulwani, and Zachary Kincaid

Computer Aided Verification, CAV 2013The paper presents Escher, a synthesis algorithm that learns recursive procedures from input-output examples. Escher combines component-based enumeration, interactive example refinement, and a goal graph that helps assemble partial programs into complete recursive solutions.
https://www.microsoft.com/en-us/research/publication/recursive-program-synthesis/

About the Guest -

Aws Albarghouthi is an associate professor of computer science at the University of Wisconsin-Madison. His research focuses on program synthesis, formal verification, quantum computing systems, and the correctness of AI agents.
https://pages.cs.wisc.edu/~aws/

Credits -

• Host & Music: Bryan Landers, Technical Staff, Ndea
• Editor: Alejandro Ramirez
• https://x.com/ndea
• https://x.com/bryanlanders
• https://ndea.com

Kevin Ellis, Assistant Professor at Cornell University, discusses his influential paper “DreamCoder,” which presents a system that jointly learns reusable program abstractions and a neural search strategy through an iterative wake-sleep process.

The work emerged from early efforts in library learning and a broader question about how humans accumulate concepts over time. Ellis reflects on the challenge of searching vast program spaces and how inspiration from cognitive processes, particularly dreaming and replay, led to a system that incrementally builds knowledge by reusing prior solutions.

In This Episode -

• Program synthesis beyond formal specifications
• Natural language as executable programs
• Library learning for compositional reuse
• Wake-sleep cycles for program learning
• Neural-guided search over program space
• E-graph refactoring for abstraction discovery
• Emergence of map and fold primitives
• Probabilistic programs for uncertainty
• World models beyond frame prediction
• Program synthesis benchmarks

References -

• ARC-AGI-3: https://arcprize.org/arc-agi/3
• ExoPredicator: https://arxiv.org/abs/2509.26255
• AutumnBench: https://www.basis.ai/blog/autumn-platform-2025/

About the Paper -

“DreamCoder: bootstrapping inductive program synthesis with wake-sleep library learning”
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke Hewitt, Luc Cary, Armando Solar-Lezama, Joshua B. Tenenbaum
PLDI 2021 (ACM SIGPLAN Conference on Programming Language Design and Implementation)

DreamCoder is a program synthesis system that learns both a library of reusable program components and a neural search policy by iteratively solving tasks and compressing solutions into abstractions. It alternates between solving problems (wake phase) and improving its internal representations via abstraction and dreaming phases, enabling more efficient search and generalization across domains.

https://dl.acm.org/doi/10.1145/3453483.3454080

About the Guest -

Kevin Ellis is an Assistant Professor at Cornell University working on program synthesis, neurosymbolic AI, and computational models of cognition. His research focuses on learning structured representations such as programs that capture compositional knowledge about the world.
https://www.cs.cornell.edu/~ellisk/

Credits -

• Host & Music: Bryan Landers, Technical Staff, Ndea
• Editor: Alejandro Ramirez
• https://x.com/ndea
• https://x.com/bryanlanders
• https://ndea.com