Rango: Adaptive Retrieval-Augmented Proving for Automated Software Verification

Formal verification has long been regarded as the gold standard for ensuring software correctness, especially in safety-critical systems. Early tools relied heavily on manual proof construction, which was time-consuming and required expert knowledge. The advent of interactive proof assistants like Coq, Isabelle, and Agda improved reliability but still depended on human intervention. Recent developments include integrating machine learning models to automate proof synthesis, exemplified by tools such as Tactician, Proverbot9001, and Graph2Tac. These systems utilize learned tactics and environment retrieval but often lack project-specific adaptability and struggle with complex proofs. The emergence of large language models (LLMs) like GPT-3 and Codex has further pushed the frontier, enabling more flexible proof generation. However, most approaches rely on static data or limited context, which hampers performance in real-world, large-scale projects. This paper situates itself within this evolution, proposing a dynamic, retrieval-augmented framework that leverages project-specific knowledge at every proof step.

Despite progress, current automated proof systems face significant limitations in handling complex, long proofs and project-specific variations. Static retrieval methods cannot adapt to the evolving proof state, leading to lower success rates in industrial-scale applications. Moreover, existing models often hallucinate or retrieve irrelevant information, reducing reliability. The core challenge is to develop a system capable of dynamically incorporating relevant proof knowledge, including similar proofs and lemmas, in real-time, while maintaining efficiency and accuracy. Addressing this gap is crucial for making formal verification practical and scalable in software engineering, especially for safety-critical systems where correctness is non-negotiable.

The primary innovation is the integration of a multi-modal retrieval mechanism with a fine-tuned LLM, enabling real-time, proof-specific knowledge incorporation. Rango employs BM-25 to retrieve proofs with similar proof states, and TF-IDF to select relevant lemmas, both at each proof step. This dynamic retrieval feeds into a decoder-only LLM, which generates tactics conditioned on the current proof context, proof state, and retrieved resources. Unlike prior static approaches, Rango continuously adapts its proof strategy, effectively learning local proof tactics. The creation of CoqStoq, a large-scale dataset, supports this approach, providing diverse, project-specific proof data for training and benchmarking. The architecture demonstrates how to leverage limited context efficiently, significantly improving proof automation success rates.

• �� Fine-tune DeepSeek-Coder (1.3B parameters) on CoqStoq dataset, using prompt-based supervised learning. • At each proof step, use BM-25 to compare current proof state with proof states in the proof bank, selecting top-k relevant proofs. • Use TF-IDF to score and retrieve the most relevant lemmas from the lemma bank based on current proof context. • Concatenate retrieved proofs, lemmas, theorem statement, proof script, and proof state into a prompt for the decoder-only LLM. • Generate the next tactic conditioned on this prompt, ensuring the model remains context-aware. • Employ rollout search, sampling tactics with temperature 1.0, executing tactics in Coq to verify correctness. • Iterate until proof completion or timeout, updating retrievals dynamically based on proof progress. • Optimize hyperparameters such as token limits, learning rate, and batch size for efficiency and accuracy.

The model is trained on CoqStoq, comprising 2226 projects and nearly 200,000 theorems, with evaluation on a held-out benchmark including CoqGym, CompCert, and long-term projects. Baselines include Tactician, Proverbot9001, and Graph2Tac. Metrics include proof success rate, total proofs, and proof time. Hyperparameters involve a 10-minute timeout, batch size 16, learning rate 10^-3, and GPU acceleration. Ablation studies compare the impact of different retrieval algorithms and the inclusion of proofs versus only lemmas. The evaluation demonstrates Rango’s superior performance, especially in industrial and complex proofs, validating the effectiveness of dynamic, retrieval-augmented proof synthesis.

Rango achieves a proof success rate of 32%, outperforming Tactician (29%) by 29%. In the CompCert project, success rate reaches 37.2%, surpassing previous tools. Incorporating relevant proofs increases proof count by 47%, confirming the importance of dynamic knowledge retrieval. Compared with Proverbot9001 and Graph2Tac, Rango proves 66% and 29% more theorems respectively. Ablation results show that combining proof and lemma retrieval yields the best performance, emphasizing the synergy of multi-modal retrieval. These results demonstrate the system’s robustness across diverse projects and proof complexities.

Rango can be integrated into industrial software verification pipelines, automating proof generation for critical components, reducing manual effort, and increasing reliability. It is suitable for formal verification in safety-critical domains like aerospace, automotive, and medical devices. The system can also serve as an intelligent assistant for proof engineers, providing suggestions and automating routine proofs. Long-term, it could enable fully automated verification workflows, significantly accelerating software development cycles and ensuring higher standards of correctness.

The system’s performance diminishes with very large or highly complex proofs, especially when relevant proofs or lemmas are missing. Its reliance on BM-25 and TF-IDF may limit semantic understanding, leading to retrieval errors in paraphrased or semantically similar cases. High computational costs for training and inference pose practical challenges, especially for smaller teams or real-time applications. Future work needs to address these issues by exploring neural retrieval methods and model compression techniques.