TacTok: semantics-aware proof synthesis
Open accessThe DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
Abstract
Formally verifying software correctness is a highly manual process. However, because verification proof scripts often share structure, it is possible to learn from existing proof scripts to fully automate some formal verification. The goal of this paper is to improve proof script synthesis and enable fully automating more verification. Interactive theorem provers, such as the Coq proof assistant, allow programmers to write partial proof scripts, observe the semantics of the proof state thus far, and then attempt more progress. Knowing the proof state semantics is a significant aid. Recent research has shown that the proof state can help predict the next step. In this paper, we present TacTok, the first technique that attempts to fully automate proof script synthesis by modeling proof scripts using both the partial proof script written thus far and the semantics of the proof state. Thus, TacTok more completely models the information the programmer has access to when writing proof scripts manually. We evaluate TacTok on a benchmark of 26 software projects in Coq, consisting of over 10 thousand theorems. We compare our approach to five tools. Two prior techniques, CoqHammer, the state-of-the-art proof synthesis technique, and ASTactic, a proof script synthesis technique that models proof state. And three new proof script synthesis technique we create ourselves, SeqOnly, which models only the partial proof script and the initial theorem being proven, and WeightedRandom and WeightedGreedy, which use metaheuristic search biased by frequencies of proof tactics in existing, successful proof scripts. We find that TacTok outperforms WeightedRandom and WeightedGreedy, and is complementary to CoqHammer and ASTactic: for 24 out of the 26 projects, TacTok can synthesize proof scripts for some theorems the prior tools cannot. Together with TacTok, 11.5% more theorems can be proven automatically than by CoqHammer alone, and 20.0% than by ASTactic alone. Compared to a combination of CoqHammer and ASTactic, TacTok can prove an additional 3.6% more theorems, proving 115 theorems no tool could previously prove. Overall, our experiments provide evidence that partial proof script and proof state semantics, together, provide useful information for proof script modeling, and that metaheuristic search is a promising direction for proof script synthesis. TacTok is open-source and we make public all our data and a replication package of our experiments.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2019) · Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) · doi:10.18653/v1/n19-1423 · Cited by 54,325
Learning representations by back-propagating errors
Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986) · Nature · doi:10.1038/323533a0 · Cited by 31,892
Deep Contextualized Word Representations
Peters, M., Neumann, M., Iyyer, M., Gardner, M., Clark, C., Lee, K., & Zettlemoyer, L. (2018) · Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers) · doi:10.18653/v1/n18-1202 · Cited by 11,983
de Moura, L., & Bjørner, N. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78800-3_24 · Cited by 6,595 · cited 1×
“As in prior evaluations of automated verification tools that compare to CoqHammer [Yang and Deng 2019] our experiments configure CoqHammer to use four ATPs: Z3 [de Moura and Bjùrner 2008], Vampire [Kovács and Voronkov 2013], CVC4 [Barrett et al. 2011], and E Prover [Schulz 2013].”
MethodMoses: open source toolkit for statistical machine translation
Koehn, P., Zens, R., Dyer, C., Bojar, O., Constantin, A., Herbst, E., Hoang, H., Birch, A., Callison-Burch, C., Federico, M., et al. (2007) · Proceedings of the 45th Annual Meeting of the ACL on Interactive Poster and Demonstration Sessions - ACL '07 · doi:10.3115/1557769.1557821 · Cited by 4,735 · cited 1×
“When applied to natural languages, these models have aided speech recognition, machine translation, spelling correction, and other natural language processing tasks [Brill and Moore 2000; Koehn et al. 2007; Stolcke 2002].”
MethodImproved Semantic Representations From Tree-Structured Long Short-Term Memory Networks
Tai, K. S., Socher, R., & Manning, C. D. (2015) · Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers) · doi:10.3115/v1/p15-1150 · Cited by 3,081
LSTM neural networks for language modeling
Sundermeyer, M., Schlüter, R., & Ney, H. (2012) · Interspeech 2012 · doi:10.21437/interspeech.2012-65 · Cited by 1,963 · cited 5×
“Research on language modeling in natural language processing literature has focused on n-gram models [Katz 1987; Kneser and Ney 1995] and neural networks [Bengio et al. 2003; Mikolov et al. 2010; Sundermeyer et al. 2012], (recall Section 3.”
BackgroundMethodInfluentialDafny: An Automatic Program Verifier for Functional Correctness
Leino, K. R. M. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17511-4_20 · Cited by 940 · cited 1×
“Recently, there has been a growing interest in building high-assurance software using programming languages that are designed to support program verification from the ground up [Leino 2010; Swamy et al. 2016; The Coq Development Team 2017; Vazou 2016].”
BackgroundA Syntactic Neural Model for General-Purpose Code Generation
Yin, P., & Neubig, G. (2017) · Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/p17-1041 · Cited by 623
A Syntactic Neural Model for General-Purpose Code Generation
Yin, P., & Neubig, G. (2017) · arXiv · doi:10.48550/arxiv.1704.01696 · Cited by 585
Cited by
Baldur: Whole-Proof Generation and Repair with Large Language Models
First, E., Rabe, M. N., Ringer, T., & Brun, Y. (2023) · Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering · doi:10.1145/3611643.3616243 · Cited by 94
Self-citationTowards AI-Assisted Synthesis of Verified Dafny Methods
Misu, M. R. H., Lopes, C. V., Ma, I., & Noble, J. (2024) · Proceedings of the ACM on Software Engineering · doi:10.1145/3643763 · Cited by 38
“Several efficient proof synthesis tools have been developed based on precomputed facts reasoning, heuristic search and identifiers such as CoqHammer [Czajka and Kaliszyk 2018], TacTok [First et al. 2020], Passport [Sanchez-Stern et al. 2023].”
AutoVerus: Automated Proof Generation for Rust Code
Yang, C., Li, X., Misu, M. R. H., Yao, J., Cui, W., Gong, Y., Hawblitzel, C., Lahiri, S., Lorch, J. R., Lu, S., et al. (2025) · Proceedings of the ACM on Programming Languages · doi:10.1145/3763174 · Cited by 20
AutoVerus: Automated Proof Generation for Rust Code
Yang, C., Li, X., Misu, M. R. H., Yao, J., Cui, W., Gong, Y., Hawblitzel, C., Lahiri, S., Lorch, J. R., Lu, S., et al. (2024) · arXiv · doi:10.48550/arxiv.2409.13082 · Cited by 20
TacticZero: Learning to Prove Theorems from Scratch with Deep Reinforcement Learning
Wu, M., Norrish, M., Walder, C., & Dezfouli, A. (2021) · arXiv · doi:10.48550/arxiv.2102.09756 · Cited by 10
Aggarwal, P., Parno, B., & Welleck, S. (2024) · arXiv · doi:10.48550/arxiv.2412.06176 · Cited by 4
Evaluating the Ability of GPT-4o to Generate Verifiable Specifications in VeriFast
Rego, M., Fan, W., Hu, X., Dod, S., Ni, Z., Xie, D., DiVincenzo, J., & Tan, L. (2025) · 2025 IEEE/ACM Second International Conference on AI Foundation Models and Software Engineering (Forge) · doi:10.1109/forge66646.2025.00035 · Cited by 2
“For Coq, Sanchez-Stern et al. [42] improved on existing neural network based proof synthesis tools ASTactic [43] and TacTok [44] by modeling identifiers.”
Metadata
- Authors
- First, E., Brun, Y., & Guha, A.
- Venue
- Proceedings of the ACM on Programming Languages
- Published
- 2020-11-13
- Volume
- 4
- Issue
- OOPSLA
- Pages
- 1-31
- ISSN
- 2475-1421 (ISSN-L)
- OpenAlex
- W3080745458
- Cited by
- 41
- References
- 15
- FWCI
- 1.14
- Type
- journal article
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.