Bin Mapping
Bin Mapping is a mapping component of the GENESYS program synthesis system, which formulates program synthesis as a continuous optimization problem solved with CMA-ES combined with a token probability model (LSTM).
Role in GENESYS
- The mapping scheme translates the continuous decision variables explored by CMA-ES into discrete program tokens.
- According to the source, the mapping is resilient to small changes in continuous variables, in contrast to the autoencoder-based latent representation used by NPO, where a small change in a latent variable can map the representation to a wildly different program.
- This resilience makes the underlying continuous optimization problem easier than that of NPO.
Uniform Bin Mapping
A particularly notable variant is uniform bin mapping, a scheme that does not rely on any learning model at all. Even this model-free variant:
- Synthesizes 73% of all programs.
- Outperforms NPO, which synthesizes 58% of all programs.
Comparison Context
Bin Mapping is presented within a broader comparison of program synthesis schemes (Table 4 of the source):
| Scheme | Main Idea |
|---|---|
| Shgo | Simplicial global optimization |
| NPO | Autoencoder embedding + CMA-ES |
| DeepCoder | Function probability (DNN) + DFS search |
| PCCoder | Encoder-decoder (DNN) + Beam search |
| RobustFill | Encoder-decoder (LSTM) + Beam search |
| PushGP | Genetic algorithm (GA) |
| NetSyn | Fitness function (LSTM) + GA |
| GENESYS | Function formulation + CMA-ES + Token probability (LSTM) |
Bin Mapping is part of what differentiates GENESYS from NPO: NPO uses autoencoder-generated latent variables that can produce large errors from small perturbations, while GENESYS's bin mapping is stable under small perturbations in the continuous variables.
Stability Under Noise
In a noise-injection experiment (Section 5.4.2 of the source), random noise is added to continuous variables. GENESYS's synthesis rate drops about 10% on average across different program lengths, compared with a 20% drop for NPO, further indicating the robustness of the bin mapping approach.
Reported Synthesis Results
From the same study (Figure 5, Table 4, and accompanying text):
- GENESYS synthesizes 50% of length-10 programs in less than half the time required by other approaches.
- Compared with DeepCoder, PCCoder, RobustFill, PushGP, and NetSyn, GENESYS synthesizes at least 1.1% and up to 31.3% more programs across all lengths.
- For higher program length (e.g., length 10), GENESYS on average synthesizes 28.1% more programs than those existing schemes.
- Uniform bin mapping alone synthesizes 73% of programs, exceeding NPO's 58%.
Related Entities
- GENESYS — uses Bin Mapping as part of its program synthesis pipeline (USES, incoming relation).