Synthetic Programming Elicitation for Text-to-Code in Very Low-Resource Programming and Formal Languages

Summary

Recent advances in large language models (LLMs) for code applications have demonstrated remarkable zero-shot fluency and instruction following on challenging code-related tasks, ranging from test case generation to self-repair. However, the authors note that these models struggle to compose syntactically valid programs in programming languages that were unrepresented during pre-training, known as very low-resource programming languages (VLPLs). VLPLs are critical in various settings, including domain-specific languages for internal tools and tool-chains, and legacy languages. Inspired by program elicitation, the authors propose creating a hallucinated library within a high-resource language that can be automatically compiled to the VLPL. This library enables the LLM to generate and self-repair code within the syntax of a familiar language. Specifically, the authors introduce Synthetic Programming Elicitation and Compilation (SPEAC), an approach that enables LLMs to generate syntactically valid code even for VLPLs. The authors empirically evaluate the performance of SPEAC in a case study and find that, compared to existing retrieval and fine-tuning baselines, SPEAC produces syntactically correct programs more frequently without sacrificing semantic correctness.

Strengths

+ Important area + Novel idea + Good performance

Weaknesses

- Missing some details - Fail to consider code generation approaches via self-repair or self-debugging - Only conducted experiments on UCLID5

Questions

Overall, I appreciate the idea presented in this paper. The research tackles a critical problem in the field of LLMs for code generation, particularly focusing on VLPLs, which are often overlooked but essential in many applications. The concept of using MAX-SAT to bridge the gap between high-resource and very low-resource languages is innovative and offers a new direction for future research. The empirical results demonstrate that SPEAC outperforms existing baselines in producing syntactically correct programs without losing semantic accuracy. However, the authors need to address some issues. 1. **Missing some details**: The authors omit important details about the semantic score. How is the semantic score computed? Is it done automatically or labeled manually? If labeled manually, how many people were involved, and what is the kappa score? 2. **Fail to consider code generation approaches via self-repair or self-debugging**: While the proposed SPEAC approach is promising, the paper does not adequately address how it compares to or integrates with existing methods that leverage self-repair or self-debugging capabilities in LLMs. These approaches are also relevant to this paper. 3. **Only conducted experiments on UCLID5**: The evaluation of SPEAC is limited to a single case study on UCLID5. Broader validation across multiple VLPLs would enhance the generalizability of the findings.

Rating

7

Confidence

4

Soundness

2

Presentation

3

Contribution

3

Limitations

See Questions, thanks.

Summary

In this paper, the authors present a novel approach called SPEAC (Synthetic Programming Elicitation and Compilation) to enable large language models (LLMs) to generate syntactically valid code for very low-resource programming languages (VLPLs). The approach involves creating a hallucinated library within a high-resource language, which can be compiled into the VLPL. The paper includes a case study demonstrating that SPEAC outperforms existing methods in producing syntactically correct programs. Evaluation results demonstrate that SPEAC outperforms all baselines on syntactic correctness (see “Parse Rate” in Tab 1), achieving full syntactic correctness on 78% of benchmarks.

Strengths

The paper addresses a novel problem of generating code for VLPLs by leveraging LLMs, which is a relatively unexplored area. The empirical evaluation demonstrates the effectiveness of SPEAC compared to other baselines.

Weaknesses

The claims made about the significant improvements achieved by SPEAC are not fully supported by a diverse set of experiments. The paper is poorly organized and lacks a clear, logical flow.

Questions

The first paragraph in Section 2 is very disorganized. If the authors aim to discuss LLMs for code generation, they should focus on them rather than the benchmarks. It would be beneficial to include more examples of LLMs and either remove the benchmarks discussion or introduce benchmarks in a separate section dedicated to the code generation area. The experimental section is weak. Reviewers can only find the experiment results on the eighth page. The authors should present the experimental setup, results, and analysis more prominently and earlier in the paper to support their claims better.

Rating

4

Confidence

4

Soundness

2

Presentation

1

Contribution

2

Limitations

NA

Summary

The paper presents a framework to generate programs given natural language and targeting very low-resource programming languages. They first choose a language well-represented in the training data (in this case Python), and then make the LLM generate in a subset of that language, and then compile the generated program to the target language. When the generated program is checked by formal techniques and found to be inconsistent, some parts of the program are replaced with holes and fixed with LLM again. They apply this method to a very low-resource language VLPL and show that it is able to generate programs that parse (24 out of 33 test problems) and 11 out of 24 have fully correct semantic meaning, while the baseline few-shot prompting and fine-tune methods obtain near zero parsable programs.

Strengths

* The results are very strong compared to the baseline few-shot prompting and fine-tune methods, which obtain near zero parsable programs. * The framework is described in a general way and potentially applicable to other low-resource programming languages as well. * The system integrating LLM program generation and formal methods for checking the program is very interesting and demonstrates the effectiveness of the method empirically.

Weaknesses

A major concern of the paper is that there should be other stronger and popular methods to use as baselines. For example, a common method is iterative fixing of unparsable code by prompting LLM with the parser feedback. Also, many-shot examples (more than one) and including language specification in the prompt may also help, which is also a very standard prompting technique among the community. The method presented here would likely still work better, but it would be more informative to compare with those methods and see how much improvement is made.

Questions

* Would few-shot prompting baseline methods with more than one example work better? * How does constraint decoding compare to the method here to get a parsable program in VLPL instead of Python subset? * How does the method compare with reflexion-style methods where iterative prompting is used to fix the problem by including feedback from the parser in the prompt at each iteration? * It is mentioned that there is a set of regression tests comprised of 317 tests taken directly from the UCLID5 GitHub repository. How are these tests used? Are they used to evaluate besides the results on the 33 test problems in Table 1? * How does the self-instruct with fine-tune method work specifically? How many synthetic programs are generated? * Can you provide the full prompt that is used for generation and fixing? Is the code in the appendix A included in the prompt in addition to the prompt template shown in Fig 4?

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

Limitations are addressed.

Summary

The paper addresses the challenges of LLMs in generating code for very low-resource programming languages (VLPLs), which are not represented in their pre-training data. Traditional methods to enhance LLM efficacy in this domain include prompting, constrained decoding, and fine-tuning. The authors propose a novel approach called SPEAC, which leverages natural programming elicitation to align with LLMs' tendencies, including their common hallucinations. The technique involves translating a high-resource language (P) into a target VLPL (T) using a subset of P and iterative error repair through LLMs. The largest consistent sub-tree of a generated program in P is identified using a MAX-SMT solver, and errors are iteratively fixed. The approach is demonstrated on the UCLID5 verification language, showing significant improvement in syntactic correctness compared to traditional fine-tuning methods .

Strengths

- The idea presented is novel, and the results are impressive, demonstrating significant improvements over traditional methods. - The paper is well-written and engaging. The introduction clearly explains the contributions and the problem being addressed. The running example in Section 3 is helpful for understanding the proposed method.

Weaknesses

I did not find any major weakness in the paper, however, the paper is focused on UCLID5 programs, which consist of a relatively narrow set of use cases, and it is not obvious how well this method will generalize to other VLPLs.

Questions

In the paper, the authors propose using a subset of the high-resource language P, referred to as C, which can be transformed into the target low-resource language T. How is the existence of C determined in general?

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

Section 5.1 discusses the process of defining the subset C of P at a high level, but it lacks rigorous detail. I would appreciate seeing a more elaborate theory developed around this process in future work.

Thanks for your response

Thank you for your response and explanation. Please include general guidelines and specific case studies in the next iterations of the paper. My question has been addressed, and I have no further inquiries.