💻 computer science

Untrusted Authors, Trusted Answers: A Calculus of Fidelity-Graded Translations

This paper presents a Lean 4-mechanized calculus and a dual-plane system ("hurdy-gurdy") that enables untrusted LLMs to generate self-certifying, fidelity-graded translations between programming languages, ensuring that a continuously evolving, human-verified trust graph converges on decidable program questions with ever-increasing assurance.

Original authors: Christoph Kirsch

Published 2026-07-20

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Christoph Kirsch

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Detective's Dilemma: When You Can't Trust the Messenger

Imagine you are trying to solve a mystery about a complex machine, like a car engine or a video game character's behavior. You have a question: "Will this car crash if I press the gas at 50 mph?" To answer it, you can't just look at the car; you have to translate its messy, real-world mechanics into a language a super-smart computer solver understands, like a math equation. But here's the catch: the person translating the car into math might make a mistake. Maybe they forgot a gear, or maybe they misunderstood how the brakes work. If the translator is wrong, the math solver gives you a perfect answer to the wrong question.

In the world of computer science, this is the problem of "translation." We often have to move a program from one language (like C or Python) to another (like a logic puzzle for a solver) to check if it's safe. Traditionally, scientists tried to solve this by proving the translator was perfect once and for all, like certifying a bridge is safe before anyone drives on it. But that's incredibly hard, especially when the translators are complex or even written by artificial intelligence. This paper asks a different question: What if we stop trying to prove the translator is perfect, and instead build a system that catches the translator's mistakes while it's working? It's the difference between trusting a single guide to lead you through a forest and having a team of guides who check each other's maps, with a rule that if they disagree, you stop and figure out who is wrong.

The "Hurdy-Gurdy" Machine: A Factory for Trustworthy Answers

This paper introduces a system called hurdy-gurdy (named after a musical instrument that cranks out tunes, but here it cranks out answers). The authors, led by Christoph Kirsch, propose a new way to handle computer programs: treat them like a game of "telephone" where every step is checked, and every answer comes with a receipt.

The core idea is simple but powerful: Don't trust the translator; trust the process.

Imagine you have a question about a program written in C. Instead of just sending it to one translator, the system sends it down two different paths.

The Translation: The program is translated into a simpler logic language (like turning a novel into a math equation).
The Double-Check: The system runs the original program and the translated version side-by-side. It checks if they behave the same way. If they do, great! If they don't, the system points exactly to the step where they diverged, like a referee blowing a whistle at the exact moment a player fouled.
The "Witness" Trick: If the solver says, "Yes, a crash is possible," the system doesn't just take the solver's word. It takes the "proof" (the specific conditions that cause the crash) and runs it backwards through the translation. It feeds those conditions into the original program. If the original program actually crashes, then the answer is 100% real. The system has "replayed" the crime scene.

The Two Planes: Building and Using

The system has two distinct modes, like a factory floor and a showroom:

The Use Plane (The Showroom): This is where the answers happen. Here, an AI (or a human) asks questions. The system doesn't just guess; it picks a route, checks the translation, and if the answer is "Yes, it's possible," it runs the replay to prove it. If the answer is "No, it's impossible," the system relies on a stack of checks: multiple translators, multiple solvers, and even mathematically verified certificates to be sure.
The Evolution Plane (The Factory): This is where the system grows. If the system can't answer a question, it doesn't just give up. It writes down why it failed (e.g., "We don't have a translator for this specific type of loop"). It then uses an AI to build a new translator to fill that gap. Once built, the new translator is tested against the old ones. If it passes, it gets added to the registry. If it fails, it's fixed. This loop runs indefinitely, making the system smarter and more trustworthy over time, but crucially, the growth process never answers questions itself. It only builds the tools to answer them.

The "Untrusted Authors" Twist

The most surprising part of the paper is that the translators themselves were built by untrusted AI agents. The authors didn't hand-code the translators; they asked AI models to write them based on a one-page description. Usually, this would be a disaster. But because the system checks every step, the AI's mistakes were caught immediately.

For example, in one test, an AI translator missed a specific instruction, causing it to behave differently than the original program. The system's "square check" (the side-by-side comparison) spotted the error instantly, pinpointing the exact line and the exact variable that was wrong. The system then fixed the translator. The paper shows that even with AI authors who might be wrong, the architecture of the system ensures the final answers are trustworthy.

What the System Found (and Didn't Find)

The authors ran this system on a snapshot of their work from July 2026. Here is what they measured:

Coverage: They successfully translated programs from 13 different languages (including C, Python, and even chemical reaction networks) into logic solvers. For the RISC-V processor language, they covered 96 out of 96 specific instruction types, meaning the system could handle every single instruction in that set without losing track.
Agreement: When they sent the same question down two different translation paths (one based on a manual, one based on a formal model), the answers agreed 100% of the time on the test cases.
Defects Caught: The system caught 24 specific defects in its own translators and tools. Some were simple typos, others were logic errors where the AI misunderstood how a computer instruction worked. Crucially, the system found these errors without a human looking at the code.
The "Blind Spot": The system also found a limit. If two different translators made the exact same mistake (because they both misunderstood the same rule), the system couldn't catch it. This is called a "common-mode failure." The paper admits this is a risk, but the system is designed to minimize it by using diverse sources for translations.
LLM Players: They tested if an AI could use the system to answer questions. In one experiment, an AI without tools got 7 out of 8 questions right but guessed on the hard one. The AI with the system got 8 out of 8 right, and every answer came with a machine-checked proof.

The Bottom Line

This paper doesn't claim to have solved all computer safety problems. It doesn't say that AI translators are now perfect. Instead, it proves that you can build a trustworthy system out of untrustworthy parts.

By treating every translation as a potential mistake and building a "ratchet" that only allows improvements to stick, the system creates a ladder of trust. If a question is "Can this happen?", the system can replay the event to prove it. If the answer is "No, this can't happen," the system uses a chain of independent checks and mathematically verified certificates to be sure.

The authors conclude that this approach—using a graph of routes, checking every step, and replaying the evidence—is a viable way to handle the complexity of modern software, even when the people (or AIs) building the tools are fallible. It's a shift from "trusting the author" to "trusting the architecture."

Technical Summary: Untrusted Authors, Trusted Answers

Problem Statement

The paper addresses the fundamental challenge of answering questions about programs (e.g., reachability, assertion validity) when the tools used to translate and analyze those programs are untrusted. Traditional approaches rely on either proving a single translator correct once (e.g., CompCert) or validating every run of a single translator. However, these methods assume a single "edge" of translation. The paper argues that in a complex ecosystem involving multiple source languages, diverse reasoning targets, and potentially untrusted authors (including LLMs), the translation process forms a graph of many languages and routes. In this graph, every translation is a potential point of failure. The core problem is how to compose these heterogeneous, independently built, and potentially untrusted translations into a system that provides trusted answers without requiring universal proof of every component.

Methodology: The Calculus of Fidelity-Graded Translations

The authors propose a formal calculus and a platform implementation called hurdy-gurdy. The methodology is built on two distinct "planes" meeting in a shared registry:

1. The Use Plane (Answering Questions)

This plane treats translation as a graph where nodes are languages and edges are translation pairs.

The Pair and the Square: The fundamental unit is a pair $(A, B)$ $(A, B)$ consisting of a translator $T$ $T$ , a target-to-source carry-back $\Lambda$ $Λ$ , and shared interpreters. A pair is validated via a directional commuting square:
- Exactness: The source behavior equals the target behavior carried back (a bisimulation on kept observables).
- Over-approximation: The source behavior is simulated by the target behavior (allowing spurious behaviors but preserving source behaviors).
- Decidability: For any specific program, the square is checked by running both sides and comparing projected traces. If they diverge, the failure is localized to a specific step and observable.
Composition and Contracts: Routes are composed paths through the graph. A route's contract is the componentwise meet of its hops' contracts, defined by four axes:
- Assurance Class: A hierarchy from none to replay, per-run, and universal.
- Direction: Exact or over-approximation.
- Kept Observables: The intersection of observables preserved by each hop (loss accumulates).
- Cost: Measured execution time.
Trust Mechanisms:
- Per-Run Re-establishment: Even a "trusted" hop can be dynamically validated if the square oracle passes for the specific run.
- Branch Corroboration: If two independently derived routes (diverse prefixes) agree on a verdict, the evidence is stronger than either route's individual grade.
- Existential/Universal Asymmetry:
  - Existential Answers (Reachable): Self-certifying. The solver's witness is carried back and replayed in the source interpreter. If the replay exhibits the behavior, the answer is true regardless of translator errors (Trust Base: Source Interpreter Adequacy).
  - Universal Answers (Unreachable): Not self-certifying. These rely on the composition of grades, branch agreement, and formal certificates (e.g., DRAT proofs checked by verified checkers).

2. The Evolution Plane (Growing the Graph)

This plane manages the growth of the translation graph.

Untrusted Generation: Pairs are implemented by independent LLM agents from briefs.
The Ratchet: The system enforces an additive growth model. New contributions must extend coverage without invalidating prior verdicts.
Demand and Registration: Unanswerable questions are recorded as "demand." Recommendations for new pairs are generated based on evidence. Human registration is the final gate; the system does not autonomously answer questions, only grow the capability to do so.

Key Contributions

A Calculus of Directional, Fidelity-Graded Pairs: A formal framework where exactness is a special case of over-approximation, and composition is defined by a "weakest link" meet across assurance, direction, loss, and cost.
The Contract Algebra: A mechanism to compose heterogeneous evidence. The paper formalizes how "per-run" checks and "universal" guarantees combine, and how loss (discarded observables) accumulates along a route.
The Existential/Universal Asymmetry: An architectural principle distinguishing between answers that carry witnesses (self-certifying via source replay) and those that do not (requiring graded trust and certificates).
The Two-Plane Architecture: A separation of the "use" (answering) and "evolution" (building) planes, allowing untrusted agents to build the system while the architecture ensures trust through cross-checks, diversity, and ratcheting.
Mechanization: The compositional core, including the pasting theorem, localization, and the end-to-end asymmetry theorems, is mechanized in Lean 4 (approx. 1,250 lines) with a clean axiom audit.

Results and Evaluation

The paper evaluates a "July 2026 snapshot" of the hurdy-gurdy platform, built entirely by LLM agents with no human semantic review of the code.

Coverage and Correctness: The system covers 13 languages and 15 registered pairs. It successfully composed routes for RISC-V, AArch64, eBPF, Wasm, EVM, Python, and others.
- Branch Agreement: Dual routes for RISC-V (manual-derived vs. Sail-derived) and AArch64 agreed on all 12 tested reachability questions, including universal (unreachable) verdicts.
- Compliance Benchmark: A derived benchmark of 78 questions from the RISC-V test suite was solved with 100% agreement between routes and 100% correctness against ground truth.
Defect Detection: The architecture caught 24 defects in the LLM-generated code, including:
- Silent mis-decoding of instructions (e.g., MUL as ADD) where both the interpreter and translator agreed (a "blind spot" caught only by external diversity).
- Malformed intermediate representations tolerated by one solver but rejected by others.
- Flaws in the platform's own instrumentation (e.g., a checker adapter that accepted bogus proofs).
Escape Rate Experiments: Seeded semantic mutations of the RISC-V translator were tested against the system's gates.
- The "square suite" (conjoined probes) caught 51/55 mutants.
- The remaining 4 were caught by the derived benchmark.
- Zero escapes were observed in the final round, though the authors note this measures the mutation family, not a zero escape rate for all possible errors.
- Common-mode failures (where both legs of a square are wrong identically) were caught only by the diverse branch (Sail route) or external differentials, validating the necessity of independent semantic anchors.
LLM Player Experiment: An LLM agent was tasked with answering questions using the platform.
- In a second iteration (v2), the LLM player achieved 8/8 correct answers on hard BTOR2 reachability questions, while an unaided LLM achieved 7/8.
- Crucially, the LLM player's answers were accompanied by machine-checked evidence artifacts (e.g., replayed witnesses, LRAT certificates), whereas the unaided LLM relied on "say-so" and confidence scores.
Performance: The overhead of the discipline (checking every hop, replaying witnesses) is small compared to the solver call. Translation takes milliseconds; the solver dominates the time.

Significance and Claims

The paper claims to demonstrate that trust in translation can be manufactured by architecture rather than by trusting the author.

Distributed Systems Stance: It treats translators as components that fail, containing failure through declared projections, decidable checks, and independent routes, rather than preventing it via universal proof.
The "Ratchet" of Trust: The system is designed to evolve. Coverage and assurance grow monotonically; prior verdicts are preserved even as the graph expands.
Modest Scope: The authors are explicit that the system is a "dated capability snapshot." It does not claim to solve undecidability or replace all formal verification. The "proved" tier is inhabited only for specific, bounded questions with formal certificates. The system relies on empirical discharge of interpreter adequacy and structural diversity assumptions.
The Asymmetry: The paper concludes that for existential answers, trust is "nearly free" (via replay), while for universal answers, the system must consciously "buy" assurance through graded tiers, branches, and certificates.

The work posits that a system built on these principles can allow untrusted authors (human or AI) to contribute to a verified reasoning infrastructure, provided the architecture enforces rigorous cross-checking and compositional contracts.