TL;DR
The Formal Context Protocol (FCP) breaks the circular logic of LLMs writing both code and the tests meant to verify it. By using independent formalizers to translate prose requirements into logic and applying off-the-shelf formal verification engines, FCP can detect contradictions in prompts before code is even written and catch subtle bugs that traditional LLM-generated test suites miss.
What Problem Does This Paper Address?
We are increasingly relying on Large Language Models (LLMs) to generate complex artifacts: hardware designs (RTL), tool-using agents, and software. To verify these, we often ask the same LLMs to write test suites or act as "judges."
The authors argue this creates a dangerous circularity: if a model misinterprets a prompt, it will produce a faulty artifact and a test suite that mistakenly confirms the artifact is correct. Current safeguards like LLM-judges or self-correction are often unreliable or easily manipulated. While formal verification (proving a property holds for all inputs) offers a solution, it suffers from the "fidelity" problem: how do we know the formal property we proved actually matches the original prose requirement?
Methods
FCP introduces a structured protocol to verify AI-generated artifacts against the original request, independent of any AI-written tests. Its core innovation is the separation of two concerns:
- Conformance: Does the artifact satisfy a formal reading of a requirement? (Decided by SMT solvers and model checkers).
- Fidelity: Does the formal reading actually mean what the prose means? (Refutable by presenting a human with a concrete "witness" or example).
The process, illustrated in Figure 2, works as follows:
- Decomposition: An LLM breaks a request into atomic requirements.
- Independent Formalization: Two isolated LLM "formalizers" translate these requirements into FCP-PL, a past-time temporal logic.
- Pre-Artifact Analysis: Before any code is written, FCP checks the requirements for internal contradictions (unrealizability) or under-specification.
- Adapters: FCP uses "adapters" to treat different artifacts (text, agents, code, hardware) as circuits that can be fed into formal engines like Z3 or SymbiYosys.
- Witness Generation: If the two formalizers disagree on a behavior, FCP generates a concrete "witness" (e.g., a specific function call or waveform) and asks the human author: "Is this behavior allowed?"
Datasets
The authors evaluated FCP using a custom corpus designed to test various domains:
- Hardware: 4 IP specifications (e.g., a synchronous FIFO, round-robin arbiter) with 13 planted defects.
- Prompt/Text: A product launch email with 10 instructions.
- Agent: An online store returns assistant with 11 rules and planted conflicts.
- Code: 10 tasks (e.g., a checkout function, card masking, rate limiter) featuring 10 planted conflicts and 23 ambiguities.
- HumanEvalComm: 20 problems used for end-to-end automation testing.
Key Insights and Ideas
- Agreement $\neq$ Correctness: One of the most striking findings is that multiple LLMs (and even independent formalizers) often resolve ambiguities or conflicts in the exact same incorrect way. Relying on "consensus" among models is not a substitute for formal proof.
- Bugs in the Prompt: FCP can identify "unrealizable" requirements—where two rules in a prompt cannot both be true—before a single line of code is generated. For example, in a checkout function, a rule for "free shipping over $50" might conflict with a "monotonicity" rule (adding items should never lower the total price) at the $50 threshold.
- The Agent "Cut Point": To verify agents, FCP treats the LLM's proposal as a "free input" to a formal scaffold. This allows them to prove that the scaffold will enforce certain rules (like "never refund more than $150") regardless of what the LLM suggests.
Key Results
- Hardware: Trusting AI-written assertions led to a 23% false assurance rate (certifying buggy designs). FCP certified zero violated requirements.
- Code: In 10 tasks, LLM-generated code passed its own extensive test suites (up to 745 tests) despite violating the original prompt in every single case. FCP caught these violations.
- Conflict Detection: FCP successfully identified 9 out of 10 planted conflicts in the code tasks before any code was written.
- Efficiency: Hardware verification tasks typically took less than a second per obligation, while full code studies ranged from minutes to hours.
Limitations and Future Work
- Correlated Errors: If an ambiguity in the prose is so strong that all formalizers and models misinterpret it the same way, FCP can still provide false assurance (as seen in the "gift card" task).
- Scale: The current study focused on designs with a few hundred state bits and relatively short functions. Scaling to large, multi-module software packages remains a challenge.
- Language Expressivity: FCP-PL currently lacks support for certain complex arithmetic and regular expressions, which caused some HumanEvalComm tasks to time out.
- Human in the Loop: While FCP reduces the human's job to answering concrete questions, it still requires a "request author" to resolve the ambiguities surfaced by the protocol.
Future work aims to test the protocol on larger programs and develop more robust "variant" rules to further reduce the risk of shared misreadings between formalizers.
Summary updated