Marmaragan — results and conclusion (excerpt)

| n=4, r=2 | 3 | 4 | 7 | 3 | 7 | 24 | | n=3, r=3 | 2 | 4 | 7 | 0 | 7 | 20 | | n=2, r=5 | 2 | 4 | 6 | 0 | 6 | 18 |

5.2 Experiment Setup

Adjusting for these new possibilities, a large scale experiment to test the capabilities of Marmaragan was devised. The aim was to derive the effectiveness of the N -Solutions and Retries parameters. Various combinations of each of the parameters were conceived to test this. A central goal of these tests was to determine what balance between n ( N -Solutions) and r (Retries) was ideal in order to get the best results given a fixed amount of computational resources available for completing the verification of a program.

Given the values n and r for the N -Solutions and Retries parameters, the number of solutions generated by the program is limited to a maximum of n(r+1) , because n solutions are generated for the first attempt and n further ones for each of the r retries. The total number of solutions to be generated per benchmark program was set to 12, as this made various combinations of n and r possible, while keeping costs within the limits set. The resulting combinations were the following:

(n, r) combinations:

(12, 0), (6, 1), (4, 2), (3, 3), (2, 5)

5.3 Experiment Results

Table 1 details the results of each of the five experiments on each of the five benchmarks.

In total 36 programs out of 71 were solved across all five benchmarks, meaning a solution was found for 50.7% of all benchmark problems.

Figure 4 is a graphical interpretation of Table 1.

Figure 4: Comparison of the number of programs solved per experiment. The bar is composed of the stacked number of solutions per benchmark.

A further graphical representation of the data is Figure 5. The number of successfully solved programs, compared to the total number of programs in the benchmark, is depicted through a 100% bar chart, to contrast performance on each of the benchmarks, per experiment.

Table 2: Breakdown of the number of programs solved in total, for each benchmark. The bottom row is the number of programs in the benchmark.

All pragmasLast invariant all loopsOne assertAll pragmas one loopLast invariant one loopSum
Total solved567414
Total in benchmark141271622

Figure 5: Summary of the total amount of programs solved, per benchmark, across all five experiments. The chart is a 100% bar chart, thus the y-axis represents the amount of programs that were solved, as a percentage of the total number of programs in the benchmark.

Figures 6 and 7 contrast the effectiveness of successive retries and N-Solutions. Important to note here is that while one parameter is varied, the other is kept constant. In essence, each of the selected experiments was analyzed and the number of successful solutions was counted at each step, keeping one of the two parameters constant.

Figure 6: An overview of the efficacy of N-Solutions, between n=1 and n=6. The retries parameter is kept constant

Figure 7: An overview of the efficacy of successive retries, between r=0 and r=5 (N-Solution parameter constant).

5.4 Argu Results

The programs that originate from Argu (see Section 4.1) are of high significance, as the programs cannot be part of GPT-4o’s training data111If we take the statistics from Open AI’s website to be up-to-date, at the time of writing, and provided the information is reliable.. Thus, this makes it a notable benchmark, as the solutions could not have been learned, but had to be produced by the LLM without having seen the full program during pre-training.

Along with the programs being completely new for the LLM, the subject matter of the programs is also niche. Abstract argumentation theory is likely not among the major fields of academic research, and literature surrounding this topic is likewise uncommon. This makes the programs from the Argu repository potentially the most challenging in the benchmark. With these premises in place, the results achieved by Marmaragan are surprising. Argu programs comprised just over half of the programs in the benchmark, totaling 36 out of 71. Out of these 36 programs, 16 were solved.

5.5 Verification of Results

Despite additional API costs, a replication of the two most successful experiments was conducted to attempt to show reproducibility. The two most successful runs were n=6 , r=1 and n=4 , r=2 , each reaching 24/71 solutions. These two were rerun, in order to check reproducibility. The results from this rerun were more successful than the initial runs, leading to a total of 25/71 successfully solved programs for n=4 , r=2 and 26/71 for n=6 , r=1 .

5.6 Chain of Thought Experiment

The Chain-of-Thought experiment refers to a further experiment conducted, which differentiates itself from the main experiment in its prompting strategy. See section 3.4.4 for an explanation.

Using the set of parameters with the highest rate of successfully generated solutions: n=6 , r=1 , the experiment was conducted. In total, 25/71 programs were solved, equaling the average of the success rates from the original experiment and the verification run.

6 DISCUSSION

This section analyses the results of the experiments conducted with Marmaragan.

6.1 General observations

Experiments on the benchmark demonstrate Marmaragan’s competence in generating annotations, both in the case of Assert statements and in the case of loop invariants, with a higher level of competence for Assert statements than for loop invariants. Overall, it generated correct annotations for 36 out of 71 (50.7%) of the benchmark cases. These results highlight the potential for integrating formal verification into AI-assisted development, paving the way for safer and more reliable AI-generated software.

6.2 N-Solutions and Retries Parameters

Increasing the N-Solutions parameter, which determines the number of initial solution attempts, generally led to improved success rates in solving benchmark problems. The retry mechanism, which allows Marmaragan to attempt corrections based on error feedback, also proved to be an effective strategy. In many cases, experiments that incorporated retries outperformed those that relied solely on generating new solutions. This suggests that the model can effectively use error information to refine its approach.

The experiments reveal a complex interplay between N-Solutions and retries. The combinations of n=6,r=1 and n=4,r=2 yielded the best results, solving 24 out of 71 programs each. This suggests that a balance between initial solution attempts and correction opportunities is more effective than relying on either approach alone.

As can be seen in Figures 6 and 7, higher values of the N -Solutions end Retries parameters have deminishing returns. This is not surprising, as the model exhausts its most promising approaches in the first few attempts, with subsequent attempts becoming less likely to yield new solutions.

We are not aware of any work that brings LLMs and formal software verification together in the same way as we have proposed in this paper. But there is related work on leveraging LLMs for theorem proving and autoformalization in mathematics, from which valuable insights can be drawn for applying these techniques to the verification of software. This section reviews key works that inform our approach. These studies provide context for the capabilities and limitations of LLMs in formal reasoning, which Marmaragan seeks to extend to software verification.