Search papers, labs, and topics across Lattice.
This paper employs probabilistic model checking to evaluate autoregressive neural sequence models by quantifying the probability mass on constraint-violating outputs and assessing domain requirement satisfaction. The authors extract a discrete-time Markov chain from the model's token generation, utilize the PRISM model checker for formal verification, and construct a conservative coverage curve based on the results. Their findings reveal significant insights into the limitations of test-set accuracy, demonstrating that even models with high accuracy can have substantial probability mass on undesirable outputs and identifying critical thresholds for training data requirements.
Even models boasting 100% test accuracy can hide substantial probability mass on constraint-violating outputs, challenging our understanding of their reliability.
Test-set accuracy is silent on two issues that matter when deploying autoregressive neural sequence models: how much probability mass the system under test (SUT) places on constraint-violating alternatives that are reachable under sampling and what fraction of the input population satisfies a domain requirement. We answer both with probabilistic model checking. The pipeline extracts a discrete-time Markov chain (DTMC) from the SUT's token-by-token generation, verifies formal PCTL specifications with the PRISM model checker, and aggregates the per-input verdicts into a coverage curve over the input space. A soundness theorem establishes the DTMC as an under-approximation, so every verdict yields a certified interval on the SUT's true reachability probability. The coverage built from those verdicts is, therefore, conservative by construction. A counterexample-guided abstraction refinement (CEGAR) loop adaptively tightens the interval, and a maximum-likelihood algorithm extracts the most probable falsifying trace. Two case studies exercise the pipeline. On a GPT-2 computer-aided process-planning (CAPP) model with 100% test accuracy, the pipeline quantifies the probability mass greedy decoding hides, but that is reachable with sampling; and identifies the smallest training fraction at which an ordering requirement holds population-wide, neither of which test accuracy can report. We then verify the SMILES molecular generator with a 50x larger vocabulary. The only change is an external chemical-validity oracle, and the pipeline identifies the gap between structural completeness and chemical validity.
