An Empirical Study of Conformal Prediction in LLM with ASP Scaffolds for Robust Reasoning

Navdeep Kaur & Lachlan McPheat, Alessandra Russo, Anthony G. Cohn, Pranava Madhyastha · 2025

Read An Empirical Study of Conformal Prediction in LLM with ASP Scaffolds for Robust Reasoning by Navdeep Kaur & Lachlan McPheat, Alessandra Russo, Anthony G. Cohn, Pranava Madhyastha (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-05439.txt.

Introduction

Language models can reason in code, but a single generated program is a coin flip. Navdeep Kaur and co-authors wrap the model in a method that returns a set of programs with a statistical promise attached, in a 2025 study. The task is spatial reasoning from a board-game-style data set, with answers written as logic programs.

The set-based method beat plain repeated sampling by a wide margin across reasoning depths, and adding a model-as-judge filter improved it further. Fresh calibration data did not rescue performance on the longest reasoning chains, marking a limit. The work shows how far guarantees can stretch open models today.

Catalog record

CREATORNavdeep Kaur & Lachlan McPheat, Alessandra Russo, Anthony G. Cohn, Pranava Madhyastha
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-05439

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Empirical Study of Conformal Prediction in LLM with ASP Scaffolds for Robust Reasoning Navdeep Kaur & Lachlan McPheat, Alessandra Russo, Anthony G. Cohn, Pranava Madhyastha Abstract In this paper, we examine the use of Conformal Language Modelling (CLM) alongside Answer Set Programming (ASP) to enhance the performance of standard open-weight LLMs on complex multi-step reasoning tasks. Using the StepGame dataset, which requires spatial reasoning, we apply CLM to generate sets of ASP programs from an LLM, providing statistical guarantees on the correctness of the outputs. Experimental results show that CLM significantly outperforms baseline models that use standard sampling methods, achieving substantial accuracy improvements across different levels of reasoning complexity. Additionally, the LLM-as-Judge metric enhances CLM’s performance, especially in assessing structurally and logically correct ASP outputs. However, calibrating CLM with diverse calibration sets did not improve generalisability for tasks requiring many more reasoning steps, indicating limitations in handling more complex tasks. 1 1 1 We thank Microsoft Research - Accelerating Foundation Models Research program, for the provision of Azure resources to access OpenAI models. AGC also acknowledges partial support from the Economic and Social Research Council (ESRC) under grant ES/W003473/1. 1 Introduction Building automated reasoning systems is one of the cornerstone goals of research in artificial intelligence, with wide-reaching applications in a variety of domains. LLMs have demonstrated remarkable capabilities in various natural language processing tasks Min et al. 2021 , yet exhibit critical limitations in a variety of reasoning-related tasks, particularly in multistep and spatially complex scenarios Yang et al. 2023 ; Li et al. 2024 . Although these models process and generate natural language with unprecedented fluency, their reasoning capabilities are still limited by several key constraints. Most LLMs frequently struggle with verifiable, robust and interpretable reasoning. Experimental studies have shown significant variability in LLM responses to identical reasoning related questions which highlights inherent instability Mirzaee & Kordjamshidi 2023 . For instance, sampling from an LLM’s responses to reasoning-based queries can produce widely varying answers with significantly divergent reasoning traces. This lack of robustness undermines their reliability in critical decision-making contexts Ji et al. 2023 . Moreover, tasks that require multiple sequential reasoning steps, such as complex spatial reasoning, often expose fundamental weaknesses in LLM’s systematic reasoning capabilities Shi et al. 2022 . Recent research has increasingly focused on neural-symbolic approaches that combine the strengths of LLMs in learning from data and rigorous reasoning capabilities of symbolic systems Mao et al. 2019 ; Yu et al. 2024 . Specifically, Answer Set Programming (ASP), a type of declarative logic programming, has emerged as a promising candidate for enhancing LLMs’ reasoning capabilities ( Yang et al. 2023 ) . Recent studies have explored integrating LLMs with ASP to transform natural language into logical representations, particularly for spatial reasoning tasks ( Yang et al. 2023 ; Li et al. 2024 ) . However, existing approaches face significant challenges in generating reliable intermediate scaffolds: the logical representations that bridge natural language inputs and systematic symbolic reasoning systems. The translation of natural language into formal logic programs introduces substantial uncertainty, as LLMs can produce inconsistent or semantically incorrect translations Li et al. 2024 . This variability may become a significant weakness in this reasoning pipeline, potentially compromising the reliability of downstream reasoning tasks Mirzaee & Kordjamshidi 2023 . In this paper, we present an approach that exploits the recently proposed Conformal Language Modelling (CLM) Quach et al. 2024 to systematically address these scaffold generation challenges. Conformal prediction (CP), the foundational framework for CLM, offers unique advantages in uncertainty quantification Vovk et al. 2005 ; Angelopoulos et al. 2022 . CLM has been applied to natural language generation tasks like summarisation and question-answering Quach et al. 2024 . Although recent advances in conformal prediction for language generation show promise, significant questions remain regarding the scalability, generalisability and robustness of these approaches across reasoning domains Campos et al. 2024 . In this paper, we present a thorough analysis of these open challenges through an empirical lens. We assess how calibration in CP affects generalisability on multi-hop reasoning tasks and evaluate the efficacy of adapting metrics for formal language generation (ASP). Additionally, we identify common error types in the ASP scaffolded LLM based reasoning pipelines and examine how these propagate. Our findings demonstrate the reliability and performance of neuro-symbolic reasoning systems, contributing to the development of more robust and interpretable reasoning frameworks. 2 Background In this section we introduce the main components used in our work: conformal prediction, conformal language modelling and answer set programming. Conformal Prediction is a statistical framework introduced by Vovk et al. 2005 that provides a method for constructing prediction regions with finite-sample guarantees under minimal assumptions. CP can be described as a sampling method which, under certain mild assumptions, guarantees that samples taken from any distribution using this method will be ‘correct’ with a controlled probability. This theory has been well-received in machine learning, where providing guarantees on the correctness of predictions helps improve performance, in particular since inference using neural networks involves sampling from theoretically unknown distributions Campos et al. 2024 . CP has already proven its utility and efficacy in various domains, such as in computer vision tasks Hechtlinger et al. 2018 and drug discovery Cortés-Ciriano & Bender 2019 . Conformal Language Modelling (CLM), developed in Quach et al. 2024 , is a recent generalisation of CP which allows conformal sampling of language models. CLM proposes a conformal approach to generating sets of responses with language models, allowing for statistical guarantees in the vast and complex output space of natural language generation. The main contribution of CLM is an algorithm that can control a specific risk: the expected indicator loss that the generated set contains at least one acceptable response according to a predefined admission function—while simultaneously maximising other quantities of interest such as quality, diversity, and confidence. However, it remains unclear how CLM affects generalisability, particularly because it has been primarily tested on natural language generation tasks like summarisation, and report generation, where verifying the accuracy of models is not always straightforward Campos et al. 2024 . Applying CLM to domains with rigorous notions of correctness, such as formal language generation, can provide better insights into its handling of generalisability and potential limitations. Answer set programming is a type of declarative programming which is commonly used in formal representations of knowledge, constraint satisfaction tasks, and formal common-sense reasoning. Answer set programs consist of finite sets of facts and rules that are used to generate answer sets under stable model semantics , which allows for efficient encoding of complex problems, notably in domains like graph search and combinatorial optimization Lifschitz 2019 . ASP’s utility extends to various industrial applications due to its expressive power and computational efficiency, for instance, in e-tourism Ricca et al. 2010 , high-performance computing scheduling Gamblin et al. 2022 , configuration management, diagnosis, and planning Erdem et al. 2016 . Further, ASP has been used to bolster spatial reasoning in LLMs through neural-symbolic integration Yang et al. 2023 . In the following section, we present a more formal introduction to Conformal Language Modelling (Section 3 ), which we then adapt to our purposes in Section 4 . With the adapted CLM, we set up an

Read the complete text