Loop termination proofs stop relying on templates alone: RAINFALL has an LLM fill assertions and solves 323 of 358 C programs
Synopsis
Proving loop termination usually means hand-designing ranking-function templates, and a poor template choice struggles with nonlinear updates and complex control flow. RAINFALL recasts ranking-function synthesis as code-assertion completion: four placeholder slots are inserted into the program, an LLM fills them, a symbolic verifier checks the result, and diagnostics from failed checks are fed back for iterative refinement. On 358 terminating C programs, RAINFALL with MiniMax V2.7 synthesized verifiable ranking functions for 323 programs (90.22%), 12 more than PROTON 2.1, the SV-COMP 2026 Termination category winner; combined, the two reach 346 programs (96.65%).
Interpretation
Ranking-function construction shifts from relying on predefined templates to having an LLM fill assertion slots in the program, with a symbolic verifier deciding validity. Classical methods reduce synthesis to constraint solving over predefined templates, so effectiveness depends on having a suitable template and is limited on nonlinear updates and complex control flow. On two public benchmark suites totaling 358 terminating C programs, RAINFALL with MiniMax V2.7 solves 323 (90.22%), versus 311 (86.87%) for PROTON 2.1, 282 (78.77%) for AProVE, 283 (79.05%) for UAutomizer, and 264 (73.74%) for LOOPY.
Each loop receives four placeholder slots: declaring auxiliary variables that record ranking values, saving the previous value at the start of the loop body, updating the current value at the end, and writing assertions. The LLM is thus a constrained slot filler rather than a free-form code generator, reducing the risk of altering the original program logic. The verification pipeline first runs a syntactic equivalence check that the original code was not modified, then checks that assertions cover strict decrease, non-negativity and termination conditions, and finally runs a safety check with UAutomizer; any failure writes diagnostics back into the prompt.
Diagnostics from the verifier are translated into natural-language feedback for the next prompt, forming a generate-verify-refine loop. The earlier LOOPY re-queried the model when a candidate ranking function was incorrect without carrying verification feedback into the next round. On BS-F, RAINFALL solves 129 programs with 6 LLM queries and 156 with 12; LOOPY solves 124 with 12 queries and drops to 107 when limited to 6.
Perspective
The evaluation covers two public benchmark suites from LOOPY and FreqTerm, totaling 358 terminating C programs, with programs modeled as a single while loop and for loops transformed into equivalent while loops; experiments use Clang for abstract-syntax-tree construction and manipulation and UAutomizer as the backend safety verifier.
Of the 14 BS-F programs RAINFALL leaves unsolved, 3 are cases where the model gives correct loop bounds instead of ranking functions, 4 are cases where the model returns nothing under the initial prompt, 5 are UAutomizer timeouts at 60 seconds, and 2 remain unsolved after 12 LLM queries. With Qwen-Plus, RAINFALL performs worse than ddlTerm and PROTON. The authors note that benchmarks may appear in LLM training data and that evaluation on more benchmarks and real-world programs remains future work.
