Executable Functional Abstractions: Inferring Generative Programs for
  Advanced Math Problems
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.
67fdf0faea4d2ba44335ffa7
Zaid Khan
67fdf0faea4d2ba44335ffa8
Elias Stengel-Eskin
admin_assigned
2025-04-15T08:33:58.055Z
61781c4caf41befe8ff060e8
/avatars/8871d7b046fc28cbc8638228da8e9737.svg
Elias Stengel-Eskin
user
esteng
67fdf0faea4d2ba44335ffa9
Archiki Prasad
admin_assigned
2025-04-15T08:34:04.468Z
607aeae5d2cd8c150e6ae074
/avatars/a087743b98b6fe2181283a9610db4ec4.svg
Archiki Prasad
user
archiki
67fdf0faea4d2ba44335ffaa
Jaemin Cho
admin_assigned
2025-04-15T08:34:12.982Z
5ffe32d8942cf3533d364449
https://cdn-avatars.huggingface.co/v1/production/uploads/1654821969191-5ffe32d8942cf3533d364449.jpeg
Jaemin Cho
user
j-min
67fdf0faea4d2ba44335ffab
Mohit Bansal
admin_assigned
2025-04-15T08:34:19.233Z
665d9d3a057f7c508f98c625
https://cdn-avatars.huggingface.co/v1/production/uploads/665d9d3a057f7c508f98c625/u1R9P9sJoAl4zEIcetbPy.jpeg
Mohit Bansal
user
mohitbansal
Executable Functional Abstractions: Inferring Generative Programs for
  Advanced Math Problems
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.
EFAGen, an LLM-based system, automatically generates executable functional abstractions (EFAs) for advanced math problems, enabling programmatic problem variation and data generation.
Executable Functional Abstraction EFA program synthesis LLM candidate EFA programs executable unit tests verifiable rewards seed problems problem variations data generation