Source-linked AI summary
Latent Predictor Networks for Code Generation
Wang Ling, Edward Grefenstette, Karl Moritz Hermann, Tomáš Kočiský, Andrew Senior, Fumin Wang, Phil Blunsom
TL;DR
Code generation from mixed natural-language and structured inputs needs to combine predictors with different granularities, but predictor choices and segment boundaries are unannotated. The paper introduces Latent Predictor Networks with structured attention and code compression, and reports that experiments on two new TCG datasets and a pre-existing corpus suggest performance beyond strong benchmarks.
Problem
Generation from mixed natural-language and structured inputs requires diverse predictors, while predictor choices and output segment granularities lack annotations.
Method
Latent Predictor Networks exactly marginalize over multiple predictors and generated segments, combining character-level generation, pointer networks, structured attention, and code compression.
Results
Experiments on two new TCG datasets and a pre-existing corpus suggest that the model and its extensions outperform strong benchmarks.
Takeaways & Limitations
The experiments support combining different types of predictors for code generation across the evaluated datasets.
Takeaways & Limitations
Correctness cannot be simply validated by running code for cards with conditional or nondeterministic effects.
Abstract
from arXiv · showhide
Many language generation tasks require the production of text conditioned on both structured and unstructured inputs. We present a novel neural network architecture which generates an output sequence conditioned on an arbitrary number of input functions. Crucially, our approach allows both the choice of conditioning context and the granularity of generation, for example characters or tokens, to be marginalised, thus permitting scalable and effective training. Using this framework, we address the problem of generating programming code from a mixed natural language and structured specification. We create two new data sets for this paradigm derived from the collectible trading card games Magic the Gathering and Hearthstone. On these, and a third preexisting corpus, we demonstrate that marginalising multiple predictors allows our model to outperform strong benchmarks.
1 Introduction
The paper introduces Latent Predictor Networks for generating code from mixed natural-language and structured specifications. It contributes a trading-card-game corpus, structured attention, and code compression, with experiments suggesting improved benchmark performance.
- Motivation and approach: Latent Predictor Networks marginalize over latent predictors and generated segments, enabling scalable training without token-level predictor annotations.The architecture supports predictors with different output granularities, including single tokens and multi-token segments.
- Dataset and contributions: The authors introduce a corpus for automatic code generation from Magic the Gathering and Hearthstone card specifications.Cards provide attributes and effect descriptions paired with digital implementations.
- Dataset and contributions: The card datasets require models to handle multiple input sequences, structured attributes, and long generated sequences.The paper addresses these challenges with structured attention over inputs.
- Dataset and contributions: The paper proposes structured attention over structured inputs and code compression intended to reduce code size without reducing prediction quality.These extensions accompany the latent-predictor architecture.
- Results: Experiments on the new datasets and a pre-existing corpus suggest that the extensions outperform strong benchmarks.The model is evaluated through comparisons with multiple benchmarks.
2 Dataset Extraction
The TCG datasets are extracted from open-source MTG and HS implementations, with each card represented by structured fields and executable code. Card effects expose nonlinear mappings between textual specifications and implementations.
- Corpus construction: The corpora come from open-source MTG Java and HS Python implementations, with each card stored in a separate class file stripped of imports and comments.The datasets distinguish singular fields from multiword text fields.
- Field representation: MTG cards contain six singular and four text fields, while HS cards contain eight singular and two text fields.MTG text fields include cost, type, name, and description; HS text fields include name and description.
- Field representation: Text fields are tokenized on whitespace and punctuation, domain-specific artifacts receive exceptions, and empty fields become NIL tokens.The preprocessing preserves artifacts such as MTG’s “{G}” notation.
- Code mapping: The Divine Favor implementation computes a hand-size difference and repeatedly invokes a draw method, illustrating a nonlinear description-to-code mapping.The card text does not specify these implementation details directly.
3 Problem Definition
Given a card description x, the problem is to find the code ŷ that maximizes the model-estimated conditional log probability log P(y | x). The code is represented as a character sequence.
- Objective: The decoder seeks code ŷ that maximizes log P(y | x) for a given card description x.The conditional log probability is estimated by the model.
- Notation: The output code y is represented as a sequence of characters y1..y|y| with length |y|.The input fields are indexed separately in the surrounding formulation.
- Notation: Each input field xk has |xk| tokens, and xki denotes the i-th token in field k.The formulation indexes fields from k = 1..|x|.
4 Structured Attention
The structured-attention model encodes tokens across multiple input fields, projects them into a common space, and computes attention weights conditioned on the decoder state. It extends standard attention to structured card inputs.
- Background: Standard attention predicts each output token from the previous output sequence and a single input sequence using an RNN state and softmax.The recurrent update uses the previous token, previous state, and input representation.
- Token attention: The attention representation zt is a weighted sum of encoded input tokens, with coefficients computed by a softmax over those tokens.The encoder maps tokens to continuous vectors before weighting them.
- Token attention: The affinity function v scores each input token against the current output context ht−1.A common implementation concatenates token and context representations before nonlinear projections.
- Structured attention: For multiple fields, the model uses character-level C2W representations, contextual Bi-LSTM encodings for text fields, and linear projections into a common dimensionality and range.These steps make attention over heterogeneous fields feasible.
- Structured attention: Structured attention assigns a scalar coefficient aki to each token xki and combines the resulting representations into the overall input representation zt.The coefficients are produced through tanh, linear, and softmax components.
5 Latent Predictor Networks
Latent Predictor Networks marginalize over both which predictor generates each segment and how much text it generates, enabling character generation and copying within one model. Training uses forward-backward inference over latent predictor sequences, while decoding uses beam search over predictor-segment states.
- Latent Predictor Networks: LPNs combine predictors with different segment granularities without requiring annotations identifying the predictor used at each output position.The model addresses the difficulty of combining pointer networks and character softmaxes when predictors generate segments of different lengths.
- Latent Predictor Networks: Each latent sequence ω contains predictor-segment pairs, and the objective marginalizes over all ω that generate the observed output.A predictor selects a segment-generation mechanism, while the segment specifies the emitted substring.
- Latent Predictor Networks: Generation first selects a predictor from R, then generates a variable-length segment conditioned on that predictor and the prior output context.The predictor distribution is computed with a softmax over predictors using the previous state and input representation.
- Predictor types: The model includes character generation, direct copying of singular fields, and pointer-based copying of words from text fields.Copied segments have lengths determined by the copied field or word, whereas character generation emits one character per timestamp.
- Inference: Forward-backward computation makes marginal training tractable despite exponentially many predictor paths, and likely paths receive stronger gradient updates.The algorithm associates predictor probabilities with edges and segment probabilities with nodes in a Semi-Markov chain.
- Decoding: Decoding uses a stack-based beam search whose states represent predictor-segment choices, merging states that share the same partial output by summing probabilities.Each state score combines segment probability, predictor probability, and the predecessor score.
6 Code Compression
The code compression method replaces frequently occurring code strings with learned non-terminal symbols to shorten sequences while preserving structure. Compression is repeated to a target average size, then reversed after decoding.
- 6 Code Compression: Compression targets frequent programming-language keywords, functions, and classes that need not retain character-level information.Examples include mapping “public class copy()” to “X1 X2 X3()”.
- 6 Code Compression: The method selects strings maximizing corpus-size reduction, measured as (len(v) −1)C(v), where C(v) is occurrence count and len(v) is string length.The search uses frequency bounds to prune candidates whose maximum possible compression is lower than an already found candidate.
- 6 Code Compression: Table 2 lists the first 10 compressed MTG units and represents newlines with ⇓ and spaces with a period.The caption identifies the table as a listing of the first 10 compressed units.
- 6 Code Compression: Selected strings are replaced by new non-terminal symbols repeatedly until the desired average code size is reached, then expanded during decoding.The first 10 MTG replacements reduce average code length from 1080 to 794.
7 Experiments
The experiments evaluate the proposed models on two trading-card-game code datasets and Django, using BLEU-4 and exact-match accuracy. The full system improves over the baselines, while compression and component choices affect performance and generated-code quality.
- Datasets and baselines: The evaluation covers MTG, HS, and the out-of-domain Django dataset, with sequence-to-sequence, attention, phrase-based, hierarchical, and retrieval baselines.The card datasets are in-domain, while Django tests generalization to another code-generation domain.
- Evaluation: BLEU-4 measures token-level closeness, while exact-match accuracy measures whether generated code exactly matches the reference.The authors note that both metrics can miss semantically correct code with a different implementation.
- Results: Retrieval obtains the strongest baseline BLEU scores on the card datasets, partly because returning existing entities guarantees well-formed output and preserves reference length.The hierarchical model performs better on card datasets than phrase-based translation because input fields must be extensively reordered.
- Results: The full system significantly outperforms all baselines across the three datasets and is the only system with non-zero accuracy on the card datasets.The system combines the proposed components evaluated in the experiments.
- Component comparison: Compression performs best at an 80% rate while maximizing processing time per card, although the reason for this result is uncertain.The compression-rate results compare regular softmax and LPN settings, with timing measured per card.
- Result analysis: Generated cards usually copy matching attributes correctly, whereas most errors arise when generating effects that differ substantially from seen examples.The examples include correct copying of card names and values, but unrelated or incorrect effects.
8 Related Work
The work builds on code generation, semantic parsing, natural-language programming, and reverse code-to-language generation. LPNs extend these directions by combining attention, pointer networks, and character-based embeddings while allowing predictors of differing granularity.
- Code and formal-language generation: Related work generates executable code such as regular expressions, document parsers, database queries, and programs from natural language.The paper also situates itself alongside work on formal languages and reverse mapping from code into natural language.
- Relation to neural models: LPNs extend character-based code generation by combining attention models, pointer networks, and character-based embeddings.The formulation generalizes a prior special case in which two predictors have the same granularity.
9 Conclusion
The paper introduces Latent Prediction Networks for efficient marginalization over multiple predictors and applies them to code generation from mixed specifications. Experiments show that combining different predictor types outperforms multiple benchmarks.
- Contribution: Latent Prediction Networks efficiently marginalize over multiple predictors during generation.The architecture supports a character-level softmax together with pointer networks that copy keywords from the input.
- Contribution: The code-generation model combines a character-level softmax with multiple pointer networks, structured attention, and code compression.It is evaluated on existing datasets and a newly created trading-card-game corpus.
- Conclusion: The experiments outperform multiple benchmarks, supporting the importance of combining different types of predictors.