Metraipolis › archive › dc_145b999912af

Ranking Function Generation with LLMs for Termination — arXiv:2610.35523

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.35523
License (as archived)
CC0-1.0
Archived
2026-10-27T08:03:13.714Z
SHA-256 of the archived text
aec0206598c460fb0da33efa8eb1d894c7457bb418f81782b89ce11b8e5769ee
Stable URL of this page
https://metraipolis.com/documento/dc_145b999912af

How to cite

Ranking Function Generation with LLMs for Termination — arXiv:2610.35523 — arXiv (en), https://arxiv.org/abs/2610.35523 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_145b999912af (Metraipolis archive dc_145b999912af, sha256 aec0206598c460fb0da33efa8eb1d894c7457bb418f81782b89ce11b8e5769ee)
BibTeX
@misc{dc145b999912af,
  title = {Ranking Function Generation with LLMs for Termination — arXiv:2610.35523},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.35523},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_145b999912af; sha256 aec0206598c460fb0da33efa8eb1d894c7457bb418f81782b89ce11b8e5769ee},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.35523. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Ranking functions are a fundamental technique for proving loop termination, but constructing them manually is challenging and requires substantial expertise. We propose RAINFALL, a neuro-symbolic framework which follows the generate-verify-refine paradigm and tightly integrates LLMs with symbolic verification. RAINFALL formulates ranking function synthesis as a code-completion task by inserting placeholders into the input program and constraining the LLM to fill four predefined slots for each loop. The completed program is then checked by a symbolic verifier. If verification succeeds, a valid ranking function is obtained; otherwise, the verifier's diagnostics are translated into natural-language feedback that guides iterative refinement of the LLM's output. We evaluate RAINFALL on two public benchmark suites comprising 358 terminating C programs. Using MiniMax V2.7, RAINFALL synthesizes verifiable ranking functions for 323 programs (90.22%), outperforming all promising baselines. In particular, it solves 12 more programs than PROTON 2.1, the best-performing baseline and winner of the SV-COMP 2026 Termination category. Furthermore, combining RAINFALL with PROTON 2.1 increases the success rate to 96.65% (346/358 programs). We also conduct ablation study confirming individual contributions of placeholder contracts, few-shot examples, symbolic verification, and diagnostic information feedback. Experiments across LLMs further confirm the effectiveness of RAINFALL. Our results suggest a generic, sound framework for ranking-function synthesis and, beyond termination, LLM-assisted synthesis of formally checkable liveness certificates, both of which represent new directions of software engineering research.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Software Engineering (cs.SE) ; Artificial Intelligence (cs.AI); Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2610.35523 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-27T07:55:30.996Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).