Search papers, labs, and topics across Lattice.
This paper introduces completion semantics for program reasoning in Large Language Models (LLMs), addressing the challenges posed by incomplete code fragments. By formalizing the correctness of inferences based on an implicit completion model, the authors demonstrate that many LLM-generated reports are context-dependent rather than strictly correct or incorrect. The proposed witness-generation workflow effectively validates reasoning by distinguishing plausible completions from those based on unrealistic assumptions, showcasing its utility on real-world bug reports and program-analysis tasks.
LLMs can produce context-dependent bug reports that are neither simply correct nor incorrect, revealing the hidden assumptions behind their reasoning.
Due to token and cognitive limits, Large Language Models (LLMs) typically perform program reasoning over incomplete code fragments/prompts rather than complete programs. Such reasoning therefore must rely on {assumptions about omitted code and context. As a result, the meaning of an inference over a program fragment is not absolute, but depends on an implicit completion model describing how the fragment may be refined into a complete program. In this paper, we introduce completion semantics for LLM-based program reasoning. We formalize incomplete programs as denoting a space of possible refinements and define the correctness of existential inferences relative to a completion model. Under this view, a reported bug is correct whenever there exists a completion within the model that witnesses the bug. This perspective explains why many LLM-generated reports are neither simply correct nor incorrect, but instead depend on assumptions about omitted context. We have instantiated our approach in the form of a witness-generation workflow that concretizes completions underlying an inference by constructing executable refinements of the original program fragment. Witnesses serve both as evidence for existential claims and as a mechanism for exposing the assumptions required to support them. We evaluate our approach on real-world LLM-generated bug reports and program-analysis tasks. Our results show that witness generation effectively distinguishes inferences supported by plausible completions from those requiring unrealistic assumptions, providing a practical mechanism for validating reasoning over incomplete programs.
NUS