Reliability via N-version programming?

Researchers replicated the classic 1986 Knight/Leveson N-version programming experiment using LLM-generated code, finding that coding mistakes remain correlated across implementations even when generated by different AI agents, challenging the reliability of N-version programming for safety-critical systems.

Home https://shape-of-code.com/ Uncategorized https://shape-of-code.com/category/uncategorized/ Reliability via N-version programming? Reliability via N-version programming? N-version programming https://en.wikipedia.org/wiki/N-version programming was first proposed in 1978 https://www.inf.pucrs.br/zorzo/cs/n-versionprogramming.pdf , probably the most known paper on the subject was published in 1986 https://dspace.mit.edu/server/api/core/bitstreams/1331578f-65c1-4665-a0be-1bc3cdc001d5/content , after which activity was mostly within safety-critical systems circles. Cost was a major issue, it’s expensive to create one version of a program, and producing independent versions is around times more expensive. Now that LLM have significantly reduced the cost of creating programs, people have started to experiment with creating many versions of a specification. In the past, interest in N-version programming focused on reliability. The idea is that independent implementations of the same specification will contain different coding mistakes, and that when a fault is experienced in one implementation the others will behave as intended, e.g., in a system with , a two-out-of-three vote is enough to ensure correct behavior. The 1986 Knight and Leveson paper https://dspace.mit.edu/server/api/core/bitstreams/1331578f-65c1-4665-a0be-1bc3cdc001d5/content found that coding mistakes were correlated, i.e., different implementations, written by different people, sometimes contained the same mistake https://libraopen.library.virginia.edu/entities/publication/b2095117-3a34-4b05-8f91-af93cb6a02ee so three systems might not be enough to ensure high reliability . The results were replicated, with varying percentages of total and common faults experienced. The possibility that using the same specification for all implementations might be a significant contributor to common mistakes is often raised, but I am not aware of any published studies. There are also implementations issues such as the fuzziness of floating-point arithmetic https://libraopen.library.virginia.edu/entities/publication/32871182-1d83-4662-8cbc-eb901336c094 . On Monday this week the paper: Do programming languages still matter to your AI coding agent teammate? Evidence at scale from chess engines https://arxiv.org/abs/2606.13763 discussed using LLMs to create 34 chess engines spanning 17 programming languages, and on Thursday the paper N-Version Programming with Coding Agents https://arxiv.org/abs/2606.20158 by Ron, Baudry, and Monperrus RBM replicated the Knight/Leveson KL paper using programs generated by a variety of LLMs from the specification used by KL originally used in my top, must-read paper on software fault analysis https://shape-of-code.com/2018/03/25/top-must-read-paper-on-software-fault-analysis/ . How did the KL and RBM results compare? The KL study involved 27 students each creating an implementation of the same specification in Pascal and had to pass an acceptance test containing 200 tests randomly generated for each implementation, to prevent filtering of shared faults . The RBM study created 69 implementations 23 in each of Pascal, Python and Rust of the same KL specification using different coding agents from five vendors. Implementations that failed the acceptance test 10 Pascal, 5 Python, 6 Rust were not given the opportunity to fix the code. Each implementation was given the same set of 1-million inputs, and the results compared against those obtained from an Oracle https://en.wikipedia.org/wiki/Test oracle . Based on the number of times each implementation failed i.e., produced incorrect output , and assuming that each implementation’s failures are independent of other implementations, it’s possible to calculate the expected number of cases where two or more distinct implementations fail on the same input. The expected number of multiple failures on the same input is the actual numbers are in brackets : KL 127 1,255 ; RBM Pascal 6 426 , Python 57 424 , Rust 6 424 . There are a lot more actual instances of two or more implementations failing on the same input, than would be the case if the failures were independent of each other the statistical analysis shows that the much larger values are extremely unlikely; code+data https://www.shape-of-code.com/code-data/KL-RBM.tgz . The implication is that similar coding mistakes are being made across implementations, leading to correlated failures. The error rates for the LLM generated programs look a lot lower than those in the KL study. Are the LLM generated programs more reliable than the human written programs? Later studies with human subjects also had a much lower error rate, suggesting that the higher error rate in the KL study was caused by the use of student subjects. Fans of a particular language will often claim that it has various desirable characteristics, e.g., readability, maintainability and reliability. There is no evidence for any of these claims, and I have always thought that, post-release of the program, programming language is essentially irrelevant. Mistakes and assumptions tend to be language independent. This small sample of programs for one problem don’t show any significant differences between languages perhaps there is one, but a much larger sample will be needed to see it . In the past, multi-language studies https://arxiv.org/pdf/1409.0252 have often used examples from Rosetta Code https://rosettacode.org/wiki/Rosetta Code also see sections 2.5 and 7.2.9 of my book http://knosof.co.uk/ESEUR/ . Given the perennial interest in comparing programming languages, I am expecting many papers on the subject over the next few years. A more interesting question is the variability in the source code generated by different LLMs, for the same specification. I am expecting that it will contain some of the patterns in human written code http://www.coding-guidelines.com/cbook/usefigtab.pdf , as well as some patterns of human variation https://shape-of-code.com/2013/09/20/how-many-ways-of-programming-the-same-specification/ . Perhaps LLM source code generation does not need to become as reliable as compiler machine code generation, vendors just have to make sure that the mistakes they make are not correlated. Statistical note: KL uses the Wald interval https://en.wikipedia.org/wiki/Wald test to estimate the statistical significance and RBM replicates . There are issues with this approximation https://en.wikipedia.org/wiki/Binomial proportion confidence interval Wald interval when the probability of failure is close to zero it does not matter here because the difference between theory and practice is so large . These days libraries implementing the complicated, technically correct, approach https://en.wikipedia.org/wiki/Binomial proportion confidence interval are available, e.g., binomtest https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.binomtest.html is in Python’s scipy.stats package and binomial.test is included in R’s base system. Uncategorized https://shape-of-code.com/category/uncategorized/ error rate https://shape-of-code.com/tag/error-rate/ , experiment https://shape-of-code.com/tag/experiment/ , human https://shape-of-code.com/tag/human/ , LLM https://shape-of-code.com/tag/llm/ , N-version https://shape-of-code.com/tag/n-version/ , Pascal https://shape-of-code.com/tag/pascal/ , programming language https://shape-of-code.com/tag/programming-language/ , variation https://shape-of-code.com/tag/variation/