From Perception to Programs: Regularize, Overparameterize, and Amortize

Hao Tang 1 Kevin Ellis 1

Abstract

systems should learn to carve the perceptual world into
their own discretization. What constitutes a ‘symbol’ mayvary across domain and across datasets, and can be hardfor human engineers to anticipate. By jointly learning thesymbols, as well as synthesizing the programs that operateon them, we hope to side-step the pitfalls associated withhand-engineered representations.

We develop techniques for synthesizing neurosymbolic programs. Such programs mix discrete symbolic processing with continuous neural computation. We relax this mixed discrete/continuous problem and jointly learn all
modules with gradient descent, and also incorporate amortized inference, overparameterization,
and a differentiable strategy for penalizing lengthy
programs. Collectedly this toolbox improves thestability of gradient-guided program search, andsuggests ways of learning both how to parse continuous input into discrete abstractions, and how
to process those abstractions via symbolic code.

Delivering on the above promises requires synthesizing neurosymbolic programs, which poses unique technical challenges. Unlike conventional programs, which are discrete,a neurosymbolic program has both continuous weights anddiscrete program structure, both of which must be synthesized. In addition to solving a mixed discrete/continuous
problem, synthesizing a neurosymbolic program is severely
underconstrained. Because neural nets are universal function approximators, they can in theory satisfy any program
learning problem, at least on the training data.

1. Introduction

Our main technical contribution is a suite of methods forcircumventing the above two challenges. We assume amultitask setup where the learner is exposed to a varietyof neurosymbolic programming tasks. Having multiple
tasks introduces extra constraints, and also allows learning
across tasks how to search for programs. Hence multitasking can address both the ill-posed nature of the problem,
and also the intractable search aspect due to the mixed discrete/continuous nature of the problem.

We seek steps toward AI systems that learn to symbolically process perceptual input. Consider, for example, asystem which learns to control a moving object that navigates around obstacles: starting from sensory data (lidar,
RGBD), it must first parse the world (into objects, proximities, freespace), and then compute trajectories using
high-level computations (PID controllers, etc.). Similar
perceptual-symbolic problems arise when learning structured world models from pixels, inferring instructions fromnatural language, or constructing visual analogies. We propose framing such tasks as neurosymbolic program synthesis: learning neural components that extract symbols
from perception, and synthesizing programs to further process those symbols with more complex computations.

Concretely, our method trains a neural search policy tosynthesize neurosymbolic programs. It uses a differentiableinterpreter to backprop gradients from the desired program
output all the way back to the parameters of the searchpolicy. We overparametrize the program search space toease continuous optimization, but this overparametrization
leads to bloated programs with too much code, hence weregularize the length of the programs to produce concise,interpretable code. We therefore call our method ROAP
(Regularize, Overparametrize, Amortize, for Programs).

Our ultimate goal is to develop general methods that could,
we hope, apply to challenging neurosymbolic tasks likethose previously mentioned. We take the stance that symbols should be grounded in perception, and that symbol
processing should be implemented by learnable programlike representations. However, We also propose that rather
than hand-code a preordained set of primitive symbols, AI

We apply ROAP to two different domains (Fig. 1). Our
CIFAR-MATH domain is a harder version of a classic proving ground for neural logic programming (Manhaeve et al.,2018), modified to include program synthesis. On it, weshow that ROAP can synthesize arithmetic equations whileat the same time learning to parse images into symbolic digits. Our 3D-Reconstruction domain involves synthesizing*
Equal contribution 1 Cornell University. Correspondence to:
Hao Tang <haotang@cs.cornell.edu>.

Published at the Differentiable Almost Everything Workshop of theth International Conference on Machine Learning, Honolulu,
Hawaii, USA. July 2023. Copyright 2023 by the author(s).

1

ROAP

Programming Tasks
Training

Synthesized Programs
Neural Part

Test

Inferred Symbolic Program(latent goal func: ! " #$)?

Geometric
Transformation

=8

CNN

=?

ProgramSynthesizer=1

ProgramSynthesizer

=7

7
8
6

55

∪
∪

flip-union∩∪

Figure 1. Top, CIFAR-MATH domain. System synthesizes symbolic equations, but instead of learning the equations from concrete
numbers, it inputs CIFAR-10 images, where each image category (dog, cat, frog, ...) has been mapped to a digit from 0–9. Note: we show
MNIST above for ease of understanding. Bottom, graphics domain. Given a partial observation of a 3D shape, system learns to infer a
3D graphics program completing the shape. Note: For CIFAR-MATH we show one task. For 3D we show several tasks.

ultimately minimizing L(θ, ϕ) shown below:XLoss(y, Jαθ K(x ))
L(θ, ϕ) =Egraphics programs that algebraically transform and combine
neural geometric primitives, and can be used to decompose
3D shapes and infer missing geometry.

t∼T
α∼πφ (·|t)

2. Problem statement & Definition

Already, this framing helps address one issue with synthesizing neurosymbolic programs: Each program can invoke
learned neural networks, but only ones using shared parameters θ. Thus having multiple tasks introduces extra
constraints on θ, preventing the system from solving everything with monolithic neural networks.

A neurosymbolic program has both a symbolic programarchitecture α ∈ A, and also continuous parametersθ ∈ Rd , where A is a set of possible architectures. We
write αθ for the program with architecture α and parameters
θ. We assume a denotation operator J·K, which takes
a program αθ and outputs what the program executes to.
Generally, Jαθ K is a function. An example of synthesizing aneurosymbolic program is optimizing for the architectureα ∈ A and parameters θ ∈ Rd minimizing a loss function
over training data D:α, θ = arg min
θ∈Rd
α∈A

X

(x ,y)∈D

Loss y, Jαθ K (x )(2)

(x ,y)∈Dt

Gradient estimation via Relaxation. Learning to searchfor programs requires optimizing the search policy parameters ϕ. We implement our policies as neural networks, so
we are interested in taking gradients of L with respect to ϕ(and also θ). ROAP relaxes the symbolic program space;assumes that sampling a program architecture is equivalent
to sampling an array of one-hot vectors from categorical distributions for all discrete choices within a program; and thenfinally uses Gumbel-Softmax to backprop through thesecategorical draws (Appendix C.1).

(1)

We assume a training corpus of neurosymbolic programming tasks, T . Each such task t ∈ T is specified by adataset Dt of input-output pairs, (x , y).

(Over)parameterizing the program space. We model eachprogram architecture as straightline code (Appendix C.2).
To compute the denotation of α, given its vectorized encoding, we use a simple dynamic program that memoizes thecomputation of the value computed by each line of code.

Amortization & Parameter Sharing. We start with anobjective function for amortized inference (Appendix B)that optimizes the parameters of a policy, ϕ, to increase theprobability of generating a program architecture that has
low loss. We also optimize the parameters θ of the neuralnetworks invoked by these symbolic program architectures,

We now overparametrize the problem by expanding the
maximum possible lines of code far beyond what the systemneeds to solve its programming problems. This dramaticallyincreases the dimensionality of α, and empirically we foundthat this significantly improved the convergence propertiesof gradient descent when optimizing Eq. 5 (Appendix C.3).

3. Method

2

ROAP

Table 1. Experimental Results on CIFAR-MATH

Program-Acc Symbolic-Acc Test-Symbolic-Acc

Loss

Test-Loss OOD-Loss

ROAP (ours)

99.8%

100%

69.4%

2.4e-40.11

0.05

w./o. program
w./o. amortized inference
w./o. gumbel-softmax
w./ max lines=10

0.0%
28.4%
21.0%
11.6%

4.2%
49.5%
1.8%
9.9%

4.7%
27.9%
0.9%
6.9%

1.3e-5
0.022
0.007
0.027

0.11
0.16
0.14
0.14

0.52
0.15
2.07
2.12

REINFORCE
TerpretNEAR
dPads
HOUDINI

0.2%
0.9%
0.8%
2.0%
17.4%

0.0%
4.0%
8.3%
9.6%
13.1%

0.0%
3.4%
6.9%
9.2%
9.4%

0.59
6.4e19
0.059
0.36
0.015

0.65
5.9e19
0.18
0.36
0.09

0.64
N/A
0.93
0.96
0.60

Regularizing program length. Unsurprisingly, overparametrizing by increasing the max program size generates
excessively long programs that tend to be more overfit andalso harder for humans to understand and interpret.To combat the code explosion caused by overparametrization, we
incorporate an additional term in our loss which penalizes
the average program length (Appendix C.4).

• Can we synthesize the correct program?
• Do we successfully learn a neural perception module,
equivalently did the CNN learn a CIFAR-10 classifier asa side effect of the overall training procedure?
• To understand if the learned programs generalize out ofsample, we designate one task to be trained only on small
numbers (0–5), and then check if the synthesized neurosymbolic program extrapolates to larger numbers (6–9;
multitasking makes it see these numbers on other tasks).

Min-sampling. The policy acts as a search heuristic thatstochastically proposes programs. Running the policy multiple times per task and taking the sampled program withthe minimum loss allows trading more compute for lower
loss, a trick we call ‘Min-sampling’. This is conceptuallyrelated to importance reweighting of samples from neuralrecognition models (Burda et al., 2015).

Tbl. 1 shows the metrics relating to the above questions
for our system as well as ablations and baselines (Appendix D.1). Overall, we find that the full model can jointly
learn to ground its visual input into discrete symbols (numbers 0–9), and then transform those discrete symbols using
symbolic equations that the system itself infers. None of thebaseline neurosymbolic synthesis methods meet that criteria.
We also find that a symbolic program aids out-of-sample
generalization, as can be seen by comparing with the ‘w/o
program’ baseline, which replaces the program architecture with a small neural network. This suggests ROAP haslearned an appropriate division of labor between its CNN
and its symbolic programs, with the CNN handling perception (but not reasoning) while the symbolic programs handle
reasoning, thus enabling it to extrapolate out-of-distribution.

4. Experiments
4.1. CIFAR-MATH
The classic warmup problem for neurosymbolic systems is
to train an MNIST classifier by supervising only on the result of running an algorithm on that classifier’s outputs, e.g.,+ →11 (Manhaeve et al., 2018; Huang et al., 2021).
CIFAR-MATH makes this warmup domain harder along
several dimensions (Appendix D.1). Following Fig. 1, eachtask has a different hidden equation (Fig. 1 illustrates x +yz ).
The inputs to the equation are presented as CIFAR-10 images. Each of the ten CIFAR-10 categories (dog, boat, frog,...) is mapped to a different digit from 0–9, but this mappingis never given to the system. Architectures α are built froma Domain Specific Language containing addition, multiplication, and subtraction. The shared continuous parameters
θ are the weights of a CNN that maps a CIFAR-10 image toa scalar.

4.2. Graphics Program Synthesis
We use ROAP to synthesize neurosymbolic graphics programs. We consider the problem of reconstruction, whichmeans inferring the shape of an object given a partial/occluded observation. The graphics programs start withbasic parts, like boxes and balls, which are transformed
and combined to generate 3D geometry. What makes thesegraphics programs neurosymbolic is that, instead of hardcoding these basic parts, we allow the system to learn its
own part library. Each learned part is a simple shape that

We are interested in a variety of research questions, andcompute evaluation metrics to help us answer each of them:

3

ROAP

can be viewed as the output of a (tiny and unusual) neuralnetwork, whose parameters comprise θ. Fig. 2 illustrates
example learned parts: Rather than preprogram boxes, cylinders, etc., the system learns from the data which primitives
are most suitable. It learned, for example, a boxy cuboid
with rounded corners for modeling chair/sofa seats (yellow), and an elongated cuboid with a subtly curved top formodeling backs and headrests (red).

Table 3. 2D results. (NEAR’s pathological behavior on these problems is to loop forever because it can fit a shape arbitrarily wellwith increasingly long partially completed programs, thus it neverterminates with a completed program. HOUDINI’s enumeration isinapplicable due to continuous parameters in affine transforms.)

We first test on reconstructing 2D silhouettes of furniture(Fig. 9), which a series of recent graphics program synthesis
works evaluate on (Appendix E.2). Tbl. 3 shows that ROAP
achieves higher reconstruction accuracy (i.e., lower Chamferdistance) compared to these comparable recent works.
Next we evaluate on 3D models. Because ROAP does notsupervise on ground-truth programs, we can apply it todatasets not designed for program synthesizers, and so wechoose the canonical ShapeNet dataset (Chang et al., 2015).

No-refinement

Test-time-refinement

CSG-NetCSG-NETSTACKPLAD
UCSGNet

1.14
1.02
0.811
0.32

0.41
0.34
-

REINFORCENEAR
HOUDINI
Terpret

inf
N/A
N/A
N/A

Pathological behavior
N/A
4.76±2.22

ROAP (ours)

0.21

-

Each reconstruction task is specified by a partial observation of a voxel field, and the synthesized program describes
how to generate the underlying complete 3D shape. We
consider corrupting the input voxel field by cropping out arandom half-plane (Fig. 3, Fig. 10, Appendix F.3). Fig. 1
diagrams how ROAP represents shapes as programs that algebraically combine basic parts. This data-driven discovery
of basic symbolic abstractions was done without supervisingon programs or part decompositions.
Last, we again quantify reconstruction quality via Chamfer distance, and compare against ablations of our system(Tbl. 2). The most important ablation of our system is ‘w/o
program’. This replaces the program with a neural network,
essentially modeling an occupancy network (Mescheder
et al., 2019), which is a foundational deep learning architecture for 3D reconstruction. Given a complete observationof the shape, a pure neural network is superior at reconstruction (‘Full’ in Tbl. 2). But given a partial observation,
the neurosymbolic program comes out ahead (‘Crop-Plane’in Tbl. 2). This is because the symbolic program structure
has an inductive bias primed to recognize symmetries andrepeated parts. Hence this high-level symbolic prior helps
impute missing observations.

Figure 2. Neural part learning for 3D

Table 2. Experimental Results on 3D

Full

Crop-Plane

ROAP (ours)

1.7

1.8

w./o. program
w./o. amortized inference
w./o. gumbel-softmax
w./ depth=10
w./ depth=3

1.2
N/A
9.5
8.7
2.7

2.0
N/A
8.4
2.7
13.1

Figure 3. Results on 3D where the system inputs a voxel fieldwith a random subset cropped out (left models), from which it
synthesizes a program (right models) that approximates the groundtruth shape (middle point cloud).

References
Andreas, J., Rohrbach, M., Darrell, T., and Klein, D. Neuralmodule networks. In Proceedings of the IEEE Conference
4

ROAP

on Computer Vision and Pattern Recognition, pp. 39–48,
2016.

2017, Toulon, France, April 24-26, 2017, Workshop
Track Proceedings. OpenReview.net, 2017. URL https://openreview.net/forum?id=Byp_ccVte.

Burda, Y., Grosse, R., and Salakhutdinov, R. Importanceweighted autoencoders. arXiv preprint arXiv:1509.00519,
2015.

Frankle, J. and Carbin, M. The lottery ticket hypothesis:
Finding sparse, trainable neural networks. arXiv preprint
arXiv:1803.03635, 2018.

Chang, A. X., Funkhouser, T., Guibas, L., Hanrahan, P.,
Huang, Q., Li, Z., Savarese, S., Savva, M., Song, S.,
Su, H., Xiao, J., Yi, L., and Yu, F. ShapeNet: An
Information-Rich 3D Model Repository. Technical Report arXiv:1512.03012 [cs.GR], Stanford University —Princeton University — Toyota Technological Institute at
Chicago, 2015.

Gaunt, A. L., Brockschmidt, M., Singh, R., Kushman, N.,
Kohli, P., Taylor, J., and Tarlow, D. Terpret: A probabilistic programming language for program induction. arXiv
preprint arXiv:1608.04428, 2016.
Gaunt, A. L., Brockschmidt, M., Kushman, N., and Tarlow,
D. Differentiable programs with neural libraries. In
International Conference on Machine Learning, pp. 1213–
1222. PMLR, 2017.

Chang, O., Flokas, L., Lipson, H., and Spranger, M. Assessing satnet’s ability to solve the symbol grounding
problem. Advances in Neural Information Processing
Systems, 33:1428–1439, 2020.

Genova, K., Cole, F., Sud, A., Sarna, A., and Funkhouser, T.
Local deep implicit functions for 3d shape. In Proceedings of the IEEE/CVF Conference on Computer Vision
and Pattern Recognition, pp. 4857–4866, 2020.

Chaudhuri, S. and Solar-Lezama, A. Smooth interpretation.
ACM Sigplan Notices, 45(6):279–291, 2010.
Chaudhuri, S., Ellis, K., Polozov, O., Singh, R., SolarLezama, A., and Yue, Y. Neurosymbolic programming. Foundations and Trends® in Programming Languages, 7(3):158–243, 2021. ISSN 2325-1107. doi:
10.1561/2500000049. URL http://dx.doi.org/
10.1561/2500000049.

Gershman, S. and Goodman, N. Amortized inference inprobabilistic reasoning. In Proceedings of the annual
meeting of the cognitive science society, volume 36, 2014.
Gulwani, S., Polozov, O., Singh, R., et al. Program synthesis.
Foundations and Trends® in Programming Languages, 4(1-2):1–119, 2017.

Chen, X., Liu, C., and Song, D. Execution-guided neural program synthesis. In International Conference on
Learning Representations, 2018.

Harnad, S. The symbol grounding problem. Physica D:
Nonlinear Phenomena, 42(1-3):335–346, 1990.

Chen, Z., Tagliasacchi, A., and Zhang, H. Bsp-net: Generating compact meshes via binary space partitioning. In
Proceedings of the IEEE/CVF Conference on Computer
Vision and Pattern Recognition, pp. 45–54, 2020.

He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE
conference on computer vision and pattern recognition,
pp. 770–778, 2016.

Cui, G. and Zhu, H. Differentiable synthesis of programarchitectures. Advances in Neural Information Processing
Systems, 34:11123–11135, 2021.

Hewitt, L. and Tenenbaum, J. Learning structured generativemodels with memoised wake-sleep. under review, 2019.

Devlin, J., Uesato, J., Bhupatiraju, S., Singh, R., Mohamed,
A.-r., and Kohli, P. Robustfill: Neural program learning
under noisy i/o. ICML, 2017.

Evans, R. and Grefenstette, E. Learning explanatory rules
from noisy data. Journal of Artificial Intelligence Research, 61:1–64, 2018.

Huang, J., Li, Z., Chen, B., Samel, K., Naik, M., Song,L., and Si, X. Scallop: From probabilistic deductive
databases to scalable differentiable reasoning. In Ranzato,
M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan,
J. W. (eds.), Advances in Neural Information Processing
Systems, volume 34, pp. 25134–25145. Curran Associates, Inc., 2021. URL https://proceedings.
neurips.cc/paper/2021/file/d367eef13f90793bd8121e2f675f0dc2-Paper.
pdf.

Feser, J. K., Brockschmidt, M., Gaunt, A. L., and Tarlow,
D. Neural functional programming. In 5th International Conference on Learning Representations, ICLR

Jang, E., Gu, S., and Poole, B. Categorical reparameterization with gumbel-softmax. arXiv preprint
arXiv:1611.01144, 2016.

Ellis, K., Ritchie, D., Solar-Lezama, A., and Tenenbaum,
J. B. Learning to infer graphics programs from handdrawn images. NIPS, 2018.

5

ROAP

Jha, S., Gulwani, S., Seshia, S. A., and Tiwari, A. Oracleguided component-based program synthesis. In ICSE,
volume 1, pp. 215–224. IEEE, 2010.

Shi, K., Dai, H., Ellis, K., and Sutton, C. Crossbeam:
Learning to search in bottom-up program synthesis. In
International Conference on Learning Representations,
2021.

Jones, R. K., Walke, H., and Ritchie, D. Plad: Learning toinfer shape programs with pseudo-labels and approximate
distributions. The IEEE Conference on Computer Vision
and Pattern Recognition (CVPR), 2022.

Si, X., Raghothaman, M., Heo, K., and Naik, M. Synthesizing datalog programs using numerical relaxation. IJCAI,
2019.
Solar Lezama, A. Program Synthesis By Sketching. PhD
thesis, 2008.

Kania, K., Zieba, M., and Kajdanowicz, T. Ucsg-netunsupervised discovering of constructive solid geometry
tree. Advances in Neural Information Processing Systems,
33:8776–8786, 2020.

Topan, S., Rolnick, D., and Si, X. Techniques for symbol
grounding with satnet. Advances in Neural Information
Processing Systems, 34, 2021.

Kingma, D. P. and Ba, J. Adam: A method for stochastic
optimization. arXiv preprint arXiv:1412.6980, 2014.

Valkov, L., Chaudhari, D., Srivastava, A., Sutton, C., andChaudhuri, S. Houdini: Lifelong learning as program
synthesis. In Advances in Neural Information Processing
Systems, pp. 8687–8698, 2018.

Langley, P. Crafting papers on machine learning. In Langley,
P. (ed.), Proceedings of the 17th International Conference
on Machine Learning (ICML 2000), pp. 1207–1216, Stanford, CA, 2000. Morgan Kaufmann.
Manhaeve, R., Dumancic, S., Kimmig, A., Demeester, T.,
and De Raedt, L. Deepproblog: Neural probabilistic
logic programming. In Advances in Neural Information
Processing Systems, pp. 3749–3759, 2018.
Mao, J., Shi, F., Wu, J., Levy, R., and Tenenbaum, J.
Grammar-based grounded lexicon learning. Advances in
Neural Information Processing Systems, 34:7865–7878,
2021.
Mescheder, L., Oechsle, M., Niemeyer, M., Nowozin, S.,
and Geiger, A. Occupancy networks: Learning 3d reconstruction in function space. In Proceedings IEEE Conf.
on Computer Vision and Pattern Recognition (CVPR),
2019.
Sahoo, S., Lampert, C., and Martius, G. Learning equations
for extrapolation and control. In International Conference
on Machine Learning, pp. 4442–4450. PMLR, 2018.
Shah, A., Zhan, E., Sun, J., Verma, A., Yue, Y., and Chaudhuri, S. Learning differentiable programs with admissible
neural heuristics. Advances in neural information processing systems, 33:4940–4952, 2020.
Sharma, G., Goyal, R., Liu, D., Kalogerakis, E., and Maji, S.
Csgnet: Neural shape parser for constructive solid geometry. In Proceedings of the IEEE Conference on Computer
Vision and Pattern Recognition, pp. 5515–5523, 2018.
Sharma, G., Goyal, R., Liu, D., Kalogerakis, E., and Maji,
S. Neural shape parsers for constructive solid geometry. IEEE transactions on pattern analysis and machine
intelligence, 44(5):2628—2640, May 2022. ISSN 01628828. doi: 10.1109/tpami.2020.3044749. URL https://doi.org/10.1109/TPAMI.2020.3044749.
6

ROAP

A. Related Work
Neurosymbolic programming is a growing area that seeks to engineer learning and inference methods for hybrid program/neural architectures (Chaudhuri et al., 2021), and our work is a special case of this broad framework. Specifically, wetackle inductive program synthesis (Gulwani et al., 2017)–synthesizing programs from input-output examples–but where
the inputs are continuous and must be preprocessed by neural networks into symbolic form. Prior works in this setting
assume a hand-engineered inventory of basic symbols (Ellis et al., 2018), while others backpropagate through differentiable
programs to jointly train network weights and program structure (Gaunt et al., 2017). Multitasking is a known strategy forthis setting (Valkov et al., 2018). Training a neural network to help guide search for discrete programs (amortized inference)is standard (Shi et al., 2021; Chen et al., 2018), and we extend that idea to continuous relaxations of program spaces.
The difficulties of gradient descent over relaxed program spaces is well known, to the extent that it has been dubbed theso-called ‘terpret problem’ (Gaunt et al., 2016). Unfortunately, such an approach is the most straightforward way of training
neurosymbolic programs. From a technical perspective, our work hopes to make progress on the ‘terpret problem’, thereby
unlocking scalable and reliable training of this class of neurosymbolic programs.
Some of our core tricks have debuted in prior neurosymbolic program synthesizers: Terpret noticed overparametrization
helps (Gaunt et al., 2016), Memoized Wake-Sleep deployed amortized inference (Hewitt & Tenenbaum, 2019), and
HOUDINI shares neural network parameters across tasks (Valkov et al., 2018). Our technical contribution is providing themathematical and algorithmic framework which allows these tricks, and more, to be combined into the same end-to-end
learnable system. For example, we showed that the reparametrization trick (Jang et al., 2016) made amortization compatible
with relaxation and gradient-guided search.
More fundamentally, our efforts connect to the body of work on the ‘symbol grounding problem’ (Harnad, 1990): How doesa system learn to ‘ground’ abstract symbols (e.g., numbers, parts) in terms of their high-dimensional perceptual counterparts(e.g., images of digits)? This problem is especially difficult absent strong supervision on the meaning of each abstract
symbol (Chang et al., 2020), and ROAP considers a distantly supervised setting. Prior works consider a variety of orthogonaltechniques to address symbol grounding (Topan et al., 2021), including scaffolding with natural language (Andreas et al.,2016; Mao et al., 2021).

B. Problem Statement & Technical BackgroundDefinitions: Architecture, parameters, denotation. A neurosymbolic program has both a symbolic program architecture
α, and also continuous parameters θ. Each architecture comes from a set A of possible architectures. We can instantiate afixed architecture with different continuous parameters, and we write αθ for the program with architecture α and parameters
θ. We assume a denotation operator J·K, which takes a program αθ and outputs what the program executes to. Generally,Jαθ K is a function.
An example of synthesizing a neurosymbolic program is optimizing for the architecture α ∈ A and parameters θ ∈ Rd
minimizing a loss function over training data D:Xα, θ = arg min
Loss y, Jαθ K (x )
(3)
θ∈Rd
α∈A

(x ,y)∈D

This is challenging because it involves optimizing over discrete α (from combinatorially large A) and continuous θ (whichis potentially high dimensional). The trick of relaxation is to convert this mixed discrete-continuous problem into a purely
continuous one, and then optimize with continuous methods. Intuitively, relaxations index the space of architectures using
continuous weights that interpolate between discrete structures:
Definition: Relaxation. Architectures A and denotation J·K admit a k -dimensional relaxation when the architectures are
represented as k -dimensional vectors (A ⊂ Rk ) and we can take the denotation of any such k-dimensional vector, even ones
not in A, which means Rk ⊆ domain(J·K).
There are many relaxation approaches differing on what exactly the denotation means as an embedding ‘interpolates’
between architectures. Some relaxations define an approximate probabilistic semantics and interpret the k -dimensional
vector as a vector of probabilities (Si et al., 2019; Gaunt et al., 2016; Chaudhuri & Solar-Lezama, 2010). Others use schemes
reminiscent of fuzzy logic (Evans & Grefenstette, 2018), or form linear combinations of discrete subprograms (Sahooet al., 2018). Either way, solving the relaxation typically proceeds by finding a continuous vector using gradient-based
7

ROAP

optimization, and then discretizing that vector to the closest symbolic architecture.
Amortized inference: Learning to search. The idea behind amortized inference (Gershman & Goodman, 2014) is tolearn to search for programs (“infer” programs). Instead of directly optimizing over the space of programs, amortized
inference in this context means optimizing a policy that probabilistically generates programs, conditioned on a particular
programming task to solve. Typically the policy is trained across many tasks so that it learns to generate programs that solve
each task (Devlin et al., 2017).

C. Method Details
C.1. Gradient estimation via Relaxation
At a high level, ROAP relaxes the symbolic program space; assumes that sampling a program architecture is equivalent tosampling an array of one-hot vectors from categorical distributions; and then finally uses Gumbel-Softmax to backprop
through these categorical draws. In low-level detail, we assume the relaxed program semantics allow backpropagating
through the denotation operator. However, we still have to pass gradients backward through the random sampling fromthe policy (expectation over α ∼ πφ (· | t) in Eq. 2). To do this, we assume each symbolic architecture α is encoded as CC
one-hot vectors, notated {αc }c=1 , and the policy πφ samples an architecture α by drawing from C categorical distributions
cC
with parameters {pφ (t)}c=1 :πφ (α | t) =Y

Cat αc ; pφc (t)

1≤c≤C



(4)

This licenses rewriting the objective in Eq. 2 asEEt∼T αc ∼Cat(·; p c (t))φ∀ 1≤c≤CX(x ,y)∈Dt

Loss(y, Jαθ K(x ))

(5)

At this point we can deploy the well-known Gumbel-Softmax trick (Jang et al., 2016), which offers a low-varianceapproximation to the above expectation. Gumbel-Softmax perturbs the raw probabilities {pφc (t)}C
c=1 with Gumbeldistributed noise, then takes a softmax with a temperature that aneals toward 0. At 0 temperature, Gumbel-Softmax
exactly implements Eq. 5. When the temperature is positive, Gumbel-Softmax produces program architectures α whose
constituent “one-hot” vectors actually contain multiple positive components. This causes the relaxed denotation operator tointerpolate the behavior of nearby program architectures, yielding stable gradient estimation.
C.2. Program Architecture
We now specify what program architectures look like, and how we parameterize them in terms of one-hot vectors. We model
each program architecture as straightline code: A sequence of L lines of code, each of which introduces a new variablein scope by applying a function to variables introduced by preceding lines of code (Fig. 4). Each function comes froma Domain Specific Language, which contains components customized to the kinds of programs we expect to synthesize.
Toggling which vector component of α is a 1 corresponds to toggling which function each line of code uses, and which
preceding lines are passed as arguments to that function.
To compute the denotation of α, given its vectorized encoding, we use a simple dynamic program that memoizes thecomputation of the value computed by each line of code. This runs in time quadratic w.r.t. the total lines of code.
Although this parametrization works reasonably well, there are many alternatives. We also tried encoding a syntax tree
instead of a list of lines of code, but this worked worse. In general, the classic program synthesis literature is filled withdifferent techniques for ‘sketching’ a large set of possible programs, and then indexing that set with boolean decisionvariables (Solar Lezama, 2008; Jha et al., 2010).
C.3. Overparameterization and its theoretical analysis
Without overparametrization, the system is prone to falling into poor local minima. We speculate that overparametrization
helps for our problem for similar reasons as to why it helps for deep networks: (1) that it is harder to get trapped in higher
8

ROAP

Expression: (x + x ) × y
Domain Specific Language:f+ (a, b) = a + b
f× (a, b) = a × b
Straight Line Code:ℓ1 ← xℓ2 ← yℓ3 ← f+ (ℓ1 , ℓ1 )ℓ4 ← f× (ℓ3 , ℓ2 )Architecture parametrization:left arg
right arg
functionf+ f× ℓ1 ℓ2 ℓ3 ℓ1 ℓ2 ℓ3Line 3 (1, 0) (1, 0)(1, 0)
Line 4 (0, 1) (0, 0, 1) (0, 1, 0)
Figure 4. Symbolic expressions are built from operators in a Domain Specific Language and represented as straightline code. Each line ofcode is parametrized by three one-hot binary vectors specifying a function from the Domain Specific Language, and left/right argumentsfrom earlier lines. (The first lines of code simply load variables into scope.) The bottommost box shows the 6 one-hot vectors encoding
the example expression (α in the paper).

dimensional spaces, because there is likely at least one direction which leads to lower loss, and (2) with more parameters
there is a higher chance of a randomly initialized subnetwork falling within the basin of a good optimum, known as thelottery ticket hypothesis (Frankle & Carbin, 2018).
Speculatively, if lottery-ticket type behavior accounts for the success of overparametrization in our setting, then we might
expect that increasing the maximum lines beyond the needed sizes actually increases the probability that randomly initialized
weights encode the correct program. We built a simplified theoretical model of randomly initialized program architectures.
Using this model we calculated the probability of a random network containing the correct program (Fig. 5). Across a rangeof different ground-truth program lengths, this probability saturates around a few tens of lines of code. In agreement withthis analysis, we empirically found L = 30 max lines of code worked well on both of our domains.

Figure 5. Simulation results showing probability of randomly initializing to a correct program, while varying max program length andtarget program length

Theoretical Setting We demonstrate the advantages of using over-parameterization in a simplified setting. Specifically,
we consider a program synthesis algorithm that utilizes random search, and we assume that all programs are distinct and that
operators take only one argument. Our goal is to find a program in the form of p = oL (oL−1 (· · · (o1 (x )))), where L ≥ 1
is the length of the program, ol ∈ O denotes operators, and x is the input. There is no other program p ′ ∈ P such that
∀ x , p(x ) == p ′ (x ).
We represent the program sketch as a straight-line code with length L′ , as shown in Figure 4. Each line randomly selects one′
operator from the operator space
S O and its argument from previous lines. We allow the program sketch to use the identity′
operator, resulting in O = O {identity}.
Due to the formulation of straight-line codes and the usage of the identity operator, there are multiple possible assignments ofprogram parameters for the correct program. We calculate the exact probability of finding the correct program by randomly
9

ROAP

initializing the program assignment of the program sketch using dynamic programming. We set |O| = 3 as the otherexperiments and show the probabilities of randomly initializing to a correct program for different correct program lengths L
and program sketch lengths L′ in Figure 5.
C.4. Regularizing Program Length
Calculating program length from our parametrization of α is straightforward to do in linear time using dynamic programming,and is also a smooth, differentiable function of α’s components. Hence we can simply add the length-penalizing term to ourloss.
In practice we train ROAP without regularization for the first half of its training process–to encourage exploration–and thenturn on this regularizer halfway through to compress and optimize the programs (Fig. 6).

Figure 6. Regularizing program length halfway through training refactors the programs to be shorter (orange) without sacrificing accuracy(blue). Top: CIFAR-MATH. Bottom: 3D graphics.

D. CIFAR-MATH Experimental Details
D.1. Experimental Setup
CIFAR-MATH task. The classic warmup problem for neurosymbolic systems is to train an MNIST classifier bysupervising only on the result of running an algorithm on that classifier’s outputs. For example, DeepProbLog (Manhaeve
et al., 2018) and Scallop (Huang et al., 2021) both train a digit classifier given examples of handwritten digits being added
together: Given examples like + →11, together with the logic of addition, these systems reason backward through theaddition operator to train a neural network MNIST classifier.
CIFAR-MATH makes this warmup domain harder along several dimensions. First, we introduce program synthesis by not
telling the system what arithmetic expression is executing on the input images: this system must infer and synthesize thecorrect symbolic equation. Second, we consider more complex equations with several arithmetic operators. Last, we switchfrom MNIST to CIFAR-10, and do not tell the system that there are only 10 digits. Thus the system has a harder reasoning
challenge, because it has to reason backward through more complex expressions; a new induction challenge, because theexpressions are hidden; and a nontrivial perception challenge, because CIFAR-10 is more visually complex than MNIST.
Following Fig. 1, each task has a different hidden equation (Fig. 1 illustrates x + yz ). The inputs to the equation arepresented as CIFAR-10 images. Each of the ten CIFAR-10 categories (dog, boat, frog, ...) is mapped to a different digit
from 0–9, but this mapping is never given to the system. Architectures α are built from a Domain Specific Language
containing addition, multiplication, and subtraction. The shared continuous parameters θ are the weights of a CNN thatmaps a CIFAR-10 image to a scalar.
Metrics. To evaluate program-acc, because CIFAR-MATH comes with ground truth hidden programs, we check if thesynthesized programs generate the same outputs on random inputs. To evaluate the (test-)symbolic-acc, we snap the CNN
outputs to the nearest integer and report how often this yields the correct integer. For example, if frogs correspond to thenumber 3, then correctly classifying a frog means predicting a number in the range [2.5, 3.5).
Baselines. We use a REINFORCE baseline, which uses the score function estimator instead of Gumbel-Softmax;
NEAR (Shah et al., 2020), which uses A∗ to search the space of neurosymbolic programs, and does not perform multitasking
10

ROAP

or amortized inference; dPads (Cui & Zhu, 2021), which improves upon NEAR; Terpret (Gaunt et al., 2016), which directly
optimizes the parameters of α, and does not perform multitasking or amortized inference ; and HOUDINI (Valkov et al.,2018), which solves tasks sequentially via enumeration while sharing neural network parameters across tasks.
We also tried Scallop (Huang et al., 2021), a leading neural logic programming system, but its differentiable-top-k-proofs
inference method did not terminate on CIFAR-MATH problems. We suspect this is because it has to build a massive proof
tree when the arithmetic equation is unknown.
Neural network. We use an 18-layer ResNet backbone (He et al., 2016) as the image encoder with an MLP decoder,whose parameters collectively comprise θ.
Program denotation.
program.

Fig. 7 specifies how we execute program architectures α in this domain using a simple dynamic

Dataset. We generate 500 arithmetic tasks with 3 input variables, containing up to 3 operators. For each arithmetic task
we have 1e6 I/O pairs for each task for training and 1000 I/O pairs for each task for testing.
Training. We train models using the Adam (Kingma & Ba, 2014) optimizer with a learning rate equal to 3e-4 and ϵ =1e-5
for 20 epochs. The program length regularizer is not applied until halfway through training with a coefficient of λ =1e-4,
which is multiplied into the program length before it is added to the rest of the loss. The temperature for gumbel softmax is
set to 1 in the beginning and changed to 3 from epoch 15 to minimize the error gap from the continuous approximations ofprograms near the end of training.

JαKθ (x ) = Execθ (α, x , L + V )execute program and extract output on line L + V

Execθ (α, x , l ) = CNNθ (xl ), whenever l ≤ V
load variables as first lines of code. We have V variables


X
X
X
R
O
L
Execθ (α, x , l ) =αlb
× Execθ (α, x , b) , whenever l > V
αlo
× Fo x ,αla× Execθ (α, x , a),
o

1≤b<l

1≤a<l

O

L

R

where α is a tuple of (α , α , α )F1 (x , A, B ) = A + B add

F2 (x , A, B ) = A − B

subtraction

F3 (x , A, B ) = A × B
F4 (x , A, B ) = A

multiplication
no-op/skip connection

Figure 7. Differentiable execution model for a program sketch containing L lines of code. α parametrizes the program via a triple ofO
2-dimensional arrays (αO , αL , αR ) containing values from 0-1. If αlo= 1, then line l of the program computes its value by executing
LR
operator o. If αla= 1, then line l of the program gets its left argument for the operator from line a. If αlb= 1, then line l of the program
gets its rights argument for the operator from line b. The first V lines of the program evaluate to input variables, and we assume that there
are V such variables and L lines of code that follow.

D.2. Experiment Results and Analysis
D.2.1. E FFECTS OF CONTINUOUS IMAGE AND MIN - SAMPLING
We additionally verified that ROAP does not need the image to be split into three separate images showing each digit.
When the input is presented as a single contiguous image, our model’s performance is essentially unchanged (Tbl. 1,‘contiguous-image’).
11

ROAP

Table 4. More Experimental Results on CIFAR-MATH. min-sampling: 3 samples/gradient step

Program-Acc Symbolic-Acc Test-Symbolic-Acc Loss Test-Loss OOD-Loss
ROAP (ours)
ROAP + min-sampling (ours)+ min-sampling; contiguous-image

91.8%
99.8%
99.2%

82.6%
100%
100%

48.7%
69.4%
72.2%

0.005
2.4e-47.3e-4

0.11
0.11
0.12

0.07
0.05
0.04

w./ Syntax-Tree parametrizationw./ max lines=10

69.0%
11.6%

43.0%
9.9%

28.1%
6.9%

0.013
0.027

0.14
0.14

0.22
2.12

D.2.2. W HY DOES THE MODEL LEARN THE ‘ RIGHT ’ LATENT SYMBOLS ?
A single CIFAR-MATH problem is ill-posed: it is not clear what latent symbols the neural network should output, because
they are reprocessed by a (latent) program. Our experiments establish however that the system readily converges on the‘right’ symbol grounding by mapping each CIFAR-10 image category to its corresponding digit. Intuitively, this happens
because multitasking introduces extra constraints on the function learned by the neural component, which has to serve avariety of downstream symbolic computations.
100%

1

80%

Number of Tasks

2
3

60%

10

40%

30
100

20%

300
1e1 1e2 1e3 1e4 1e5 1e6Dataset Size per Task
Figure 8. Effects of constraints on symbol grounding. Both having more tasks, and having more input-outputs per task, introduced added
constraints. Heatmap shows max Symbolic-Acc over 5 runs, and should be approximately interpreted as whether or not it has a goodchance of converging correctly in 5 runs.

If this story is true, then the ability of the system to converge on a good symbol grounding hinges on having a sufficiently
constrained optimization problem. Extra tasks impose extra constraints, but so does having more input-output examples foreach task. We therefore study whether either of those constraints suffice for recovering the correct symbol grounding. Fig. 8
shows success in recovering the correct symbolic basis as a function of the constraints imposed on the optimization problem,
both by multitasking and input-outputs per task. We see a phase-transition like structure where, once the total numberof constraints passes a tipping point, the system ‘snaps’ into the expected symbolic basis. This shows the importance ofconstraints, and also that there is a tradeoff between the number of tasks, and the number of examples per task.

E. 2D Reconstruction Experimental Details
E.1. Methods
E.1.1. CSG, F LIP -U NION , AND F OR -L OOP O PERATIONS
We now specify the denotation of graphics programs. Recall that every graphics program is a function that takes a pointin space (R3 ) to 0/1 depending on if that point is outside or inside the object. In the relaxed semantics, we think of thedenotation as producing a number in the range [0, 1]. We refer to such numbers in [0, 1] as ‘occupancy values’.
12

ROAP

In general, the denotations of the graphics operations follows straightforwardly from their mathematical definitions. For
example, the union operator is represented as the maximum of its argument’s denotations, i.e., oS= max(oleft , oright ).
Specifically, the occupancy function of any shape that is a union of two parts is defined as J (zleft , zright )K(⃗p ) =max(Jzleft K(⃗p ), Jzright K(⃗p )). The intersection operator is represented as the minimum of the occupancy values, i.e.,o = min(oleft , oright ), and the difference operator is represented as o = max(oleft − oright , 0).
The flip-union and for-loop operations are implemented as unions of multiple sub-components. The occupancy values of the
sub-components are determined by applying transformations to the coordinates that align with their semantics. Specifically,
the flip-union operation is defined as:
Jflip-unionθf (z )K(⃗p )=max(Jz K(⃗p ), Jz K(flipθf (⃗p ))),

where θf ∈ R3 defines a line by θfT [⃗p ; 1] = 0 in the 2D case. Flipping a point against this line, i.e., flipθf (⃗p ) can be
implemented using a simple affine transformation. Let θf = [a, b, c], then 21b − a2−2ab2acflip(⃗p ) = 2⃗p .
a 2 − b 2 2bc
a + b 2 −2ab
The for-loop operation is defined as
Jfor-loopθd ,C (z )K(⃗p )=max({Jz K(⃗p − c × θd ) : c ∈ {0, 1, · · · , C − 1}}),

which repeats the part Jz K for C times by moving it in θd ∈ R2 direction for c times.
E.1.2. P ROGRAM S KETCH
The generation program is a union of three components: a simple component, a symmetry component, and a repeatedcomponent. The simple component, denoted as Jzsim K, comprises of various CSG operations. The symmetry component,
Jflip-unionθf (zsym )K, is implemented using the flip-union operator. The repeated component, Jfor-loopθd ,C (zrepeat )K, is
implemented using the for-loop operator. All sub-components Jzsim K, Jzsym K, and Jzrepeat K, involve multiple CSG operations
on simple primitive shapes such as squares and circles, using the straight-line-coding formulation. In addition, we incorporate
gate parameters θαsym and θαrepeat to control which components are included as
Jshape-programK(⃗p )=max(Jzsim K(⃗p ), αsym × Jflip-unionθf (zsym )K(⃗p ), αrepeat × Jfor-loopθd ,C (zrepeat )K)

αsym

=

1(θαsym >= 0)αrepeat=1(θαrepeat >= 0).

E.1.3. BALANCED T RAINING L OSS
To prevent models from becoming stuck in sub-optimal local optimums that fit only a portion of the training data, we employ
a balanced training loss that adjusts the weights of samples based on the model’s performance on them. Specifically, the loss
is designed to asX
L(θ, ϕ) = Et∼T weight(t; θ, ϕ)Loss(x , y; θ, ϕ) .
(x ,y)∈Dt

We use the chamfer distance to measure the performancesof models, cd(t; θ, ϕ), and adjusts the weights of samples
θ,φ)accordingly: weight(t; θ, ϕ) = 1 − max 1 − cd(t;threshold , 0 . In practice, we set the threshold to be 0.95 based on our
preliminary experimental results.
E.2. Experimental Setup
We utilize the same CNN encoder and MLP decoder as UCSGNet (Kania et al., 2020). The program sketch includes one
simple component, two symmetry components, and one repeated component. Each of their sub-components has 20 lines ofcodes in addition to the 32 transformed primitive shapes, including 16 circles and 16 squares. The maximum count of thefor-loop operator is 3. We use the same dataset as UCSGNet (Kania et al., 2020) which consists of 8000 CAD shapes inthree categories, chair, desk, and lamps (Sharma et al., 2018).
13

ROAP

Baselines.

We compare with (Jones et al., 2022; Sharma et al., 2022; Kania et al., 2020; Sharma et al., 2018).

Metrics. We assess reconstruction accuracy via Chamfer distance between the ground truth shape and the output of thesynthesized program.
E.3. More Experimental Results
Table 5. More 2D results. (NEAR’s pathological behavior on these problems is to loop forever because it can fit a shape arbitrarily wellwith increasingly long partially completed programs, thus it never terminates with a completed program. HOUDINI’s enumeration isinapplicable due to continuous parameters in affine transforms)

Name
CSG-NetCSG-NETSTACKPLAD
UCSGNetREINFORCENEAR
HOUDINI
Terpret
ROAP (ours)

MethodTrain-mode
Supervised+RL
Supervised+RL
LEST+ST+WS
Unsupervised
RL
Unsupervised
Unsupervised
Unsupervised
Unsupervised

Test-beam-size
10
10
10
1
1
1000
1
1

Chamfer DistanceNo-refinement Test-time-refinement
1.14
0.41
1.02
0.34
0.811
0.32
inf
N/A
Pathological behavior
N/A
N/A
N/A
4.76±2.22
0.21-

Figure 9. Qualitative results of 2D furniture silhouettes. Top, input silhouette. Middle, reconstruction. Bottom, parts used.

More reconstruction results are visualized in Figure 11.

F. 3D Reconstruction
F.1. Task Statement
Our Domain Specific Language for graphics programs includes the ability to intersect and union shapes; reflect shapes
over principal axes; a for loop that repeatedly translates its loop body; and affine transformations upon basic parts. Eachgraphics program is a function from a point in space (R3 ) to a boolean indicating whether that point is inside or outside of
the object.
F.2. Method
F.2.1. Q UADRATIC P RIMITIVE S HAPESOur program’s expressive capacity is enhanced by the integration of curved primitive shapes, defined using a combination of
two quadratic functions. The first function dictates the surface geometry, while the second performs a warp transformation.
The signed distance function that defines the surface geometry is presented as follows:Dθg (⃗p ) = max(θgT [px2 , py2 , pz2 , |px |, |py |, |pz |] − 1, 2|px | − 1, 2|py | − 1, 2|pz | − 1).
This formulation ensures that the primitive shapes do not exceed the dimensions of a 1 × 1 × 1 box by utilizing the last
three linear surfaces. Additionally, the use of absolute value functions guarantees symmetry across the x, y, and z planes.
14

ROAP

This formulation not only allows for the representation of basic shapes such as boxes and spheres, but also enables therepresentation of more complex, curved primitive shapes with greater representation power.
Similar to affine transformations, quadratic warp transformations fθw can be represented using a coordinate mapping function,
as demonstrated below:px − t xfθw (⃗p )x =sxfθw (⃗p )y = pyfθw (⃗p )z

=

pz ,

where
θw

=

[θs ; θt ; θα ]αx=1(θα >= 0)sx=

αx · (θsT [py , pz , py2 , pz2 , py pz ]) + 1tx=

αx · (θtT [py , pz , py2 , pz2 , py pz ]).

The warp transformation allows for the representation of irregular shapes, such as the mattock shape depicted in Figure 1, by
applying quadratic transformations to the coordinate x based on the coordinates y and z . The parameter αx serves as a gatefunction that controls the degree of transformation. Note that, due to the symmetry properties of quadratic surfaces, thetransformation of x is equivalent to transforming y and z .
F.2.2. S HAPE L IBRARY
To enhance the efficiency of primitive learning and grounding, we incorporate a shape library that is shared across tasks.
The library comprises 128 warp transformations and 128 quadratic surface formulations, resulting in a total of 16,384
primitive shapes. The shape library retrieval mechanism is designed similarly to vector quantization. In particular, the shapelibrary include parameters Θw ∈ R128×|θw | for warp transformations and Θg ∈ R128×|θg | for quadratic surfaces. For eachquery ⃗q ∈ R|θg |+|θw | , it will return a primitive shape with the warp transformation parameter Θw [arg max Θw ⃗q [: |θw |]]and the quadratic surface parameter Θg [arg max Θg ⃗q [−|θg | :]]. To enable training via gradient descent, we implement a
probabilistic relaxation of the retrieval mechanism:
αw=(gumbel-)softmax(Θw ⃗q [: |θw |])

θw
αg

=
=

T
αw
Θw
(gumbel-)softmax(Θp ⃗q [−|θg | :])θg=

αgT Θg .

The implicit function of the softly retrieved primitive shape is then Dθg (fθ−1(⃗p )).
w
F.2.3. CSG AND F LIP -U NION O PERATIONSThe CSG operations are defined in the same way as in the 2D case as outlined in Appendix E.1.1. The flip-union operation
is an extension of its 2D counterpart, with the added dimension of flipping points against a plane defined by θf [⃗p ; 1] = 0.
In practice, we set θf [−1] = 0 to ensure that the plane passes through the origin.
F.2.4. P ROGRAM S KETCH
The shape generation program is a symmetry of a sub-component that involves multiple CSG operations on learned primitives
retrieved from a shared shape library. The CSG operations are formulated as straight-line coding.
F.3. Experimental Setup
We utilize the same 3D-CNN encoder and MLP decoder as UCSGNet (Kania et al., 2020). The program sketch is a symmetryof a sub-component that has 20 lines of code in addition to the 128 learned primitive shapes, retrieved from the shared shape
15

ROAP

library. We use the preprocessed dataset ShapeNet provided by (Chen et al., 2020). It includes 643 volumes of voxelized
shapes and samples 16384 points as a ground truth with a higher probability of sampling near the surface for training. In the
7/8 voxelized input setting, we randomly crop one-octant of the voxels by setting their values to zero. In the 1/2 voxelized
input setting, we randomly sample planes as a, b, c ∼ uniform(0, 1) and setting half of the voxels to zero, i.e., those voxels
with coordinates ⃗p such that apx + bpy + cpz > 0.
F.4. More Experimental Results
Note that our goal is to study the qualitative behavior of our system and contrast with other general-purpose program
synthesizers, not to set a new state-of-the-art for ShapeNet. ShapeNet has received over 7 years of attention from the deeplearning and computer vision communities, who have built sophisticated yet specialized 3D reconstruction networks andtraining regimes (Genova et al. (2020) is representative in its sophistication).

Figure 10. Results on 3D where the system inputs a voxel field with a random subset cropped out (left models), from which it synthesizes
a program (right models) that approximates the ground-truth shape (middle point cloud). Our model can be trained to complete partial
geometry with a variety of different subsets taken out. Cropping out more of the input voxels makes the problem harder. Tbl. 2 reports
quantitative results contrasting the easiest regime (full voxel inputs) vs the hardest regime (an entire random half plane cropped).

More reconstruction results are visualized in Figure 12, Figure 13, Figure 14.

G. More Comments
Our goal is to make progress on basic neurosymbolic problems: starting from perception, and absent symbol-levelsupervision, how can we discover basic symbolic abstractions together with the symbolic programs which manipulate them?
Although our experiments confirm that ROAP might be on the right track for solving these problems, our method has
important limitations. ROAP cannot operate without a reasonably-sized training corpus of programming tasks, although
the fact that it does not need to supervise on source code helps address this limitation. Fundamentally, ROAP assumes
end-to-end gradient descent is the right approach, which means that program execution must be relaxed and differentiated. It
is not clear that differentiable program induction can handle sophisticated programming constructs, such as data structuresand recursion (Feser et al., 2017), at least in its current form. Thus we especially hope ROAP helps spur more fundamental
16

ROAP

progress on differentiable program relaxation techniques.

17

ROAP

Figure 11. 2D Results

18

ROAP

Figure 12. Full Voxelize Inputs

19

ROAP

Figure 13. 7/8 Voxelize Inputs

20

ROAP

Figure 14. 1/2 Voxelize Inputs

21