Executable Functional Abstractions: Inferring Generative Programs for
  Advanced Math Problems
Authors: name: Zaid Khan, name: Elias Stengel-Eskin, name: Archiki Prasad, name: Jaemin Cho, name: Mohit Bansal

Scientists often infer abstract procedures from specific instances of
problems and use the abstractions to generate new, related instances. For
example, programs encoding the formal rules and properties of a system have
been useful in fields ranging from RL (procedural environments) to physics
(simulation engines). These programs can be seen as functions which execute to
different outputs based on their parameterizations (e.g., gridworld
configuration or initial physical conditions). We introduce the term EFA
(Executable Functional Abstraction) to denote such programs for math problems.
EFA-like constructs have been shown to be useful for math reasoning as problem
generators for stress-testing models. However, prior work has been limited to
abstractions for grade-school math (whose simple rules are easy to encode in
programs), while generating EFAs for advanced math has thus far required human
engineering. We explore the automatic construction of EFAs for advanced math
problems. We operationalize the task of automatically constructing EFAs as a
program synthesis task, and develop EFAGen, which conditions an LLM on a seed
math problem and its step-by-step solution to generate candidate EFA programs
that are faithful to the generalized problem and solution class underlying the
seed problem. Furthermore, we formalize properties any valid EFA must possess
in terms of executable unit tests, and show how the tests can be used as
verifiable rewards to train LLMs to become better writers of EFAs. We
demonstrate that EFAs constructed by EFAGen behave rationally by remaining
faithful to seed problems, produce learnable problem variations, and that
EFAGen can infer EFAs across multiple diverse sources of competition-level math
problems. Finally, we show downstream uses of model-written EFAs e.g. finding
problem variations that are harder or easier for a learner to solve, as well as
data generation.