Untrusted Authors, Trusted Answers: A Calculus of Fidelity-Graded Translations
Christoph Kirsch
cs.PL
Jul 10, 2026 · v1
cs.LO cs.SE
TL;DR
The compositional core of the fidelity-graded translation calculus, including pasting and route telescope theorems, is mechanized in Lean 4 with an axiom audit.
Abstract
Verified translation has two well-studied extremes: prove the translator once (certified compilation), or validate each run of one translator (translation validation). Both treat a single translation in isolation. We study translations as a graph – many source languages, several reasoning targets, multiple independently built routes – where the honest answer to "is this translation correct?" differs from edge to edge. We present a calculus of fidelity-graded translations: pairs of languages close commuting squares that are checkable per program and compose by pasting; declared fidelity grades compose by weakest link, are re-established per run by inline checking, and are exceeded by agreement between independently derived routes; and an end-to-end theorem isolates a fundamental asymmetry – witness-carrying answers are self-certifying at the source, while universal answers are where grades, branches, and certificates earn their cost. The compositional core is mechanized in Lean 4. The calculus is implemented in hurdy-gurdy, a platform of 13 languages and 13 pairs around two reasoning hubs, built as a two-directional experiment in LLM-generated correctness: independent LLM agents wrote every pair, largely unsupervised, with the architecture's cross-checks as the only semantic gate, and the platform's intended player is itself an LLM. All code, and most of this paper, is LLM-generated; the human contribution is the architecture. The same gate is the intended growth model: hurdy-gurdy scales in language support through pairs contributed by anyone – with LLMs, with agents, or by hand – admitted by architecture, not authorship. We report conjoined coverage, branch agreement, a compliance-derived benchmark with machine-derived ground truth, witness replay, certified unreachability, and escape-rate experiments for the gate.
Problem
Verified translation is typically studied for a single translator in isolation (certified compilation or per-run translation validation). Real reasoning pipelines form a graph of many source languages, several targets, and multiple independently built routes with honestly different trustworthiness.
Approach
A calculus of fidelity-graded translations is defined, where pairs of languages form commuting squares checkable per program and composed by pasting, with declared fidelity grades composing by weakest link and corroborated by agreement between independently derived routes. The compositional core, including the pasting theorem, localization, re-establishment, and the n-ary route telescope, is mechanized in Lean 4 with a clean axiom audit. The calculus is instantiated in hurdy-gurdy, a Python platform of 13 languages and 13 pairs around two reasoning hubs, with translators authored largely by LLM agents.
Results
The Lean mechanization discharges the core theorems (pasting, re-establishment, corroboration, self-certification, and universal-answer results) with recorded axiom dependencies. The platform reports per-pair coverage, branch agreement, a 78-question compliance-derived reachability benchmark decided along both RISC-V routes, and certified-unreachability runs using a formally verified checker.
| Result | Lean theorem | Axioms |
|---|
| Theorem 3.7 (pasting) | pasting | propext |
| Theorem 4.3 | reestablishment | propext |
| Theorem 4.8 | existential_self_certifying | — |
| Theorem 4.9 | universal_needs_machinery | propext |
| route telescope (n-ary) | route_pasting, route_localization | propext, Quot.sound |
Lean theorems and their axiom dependencies for the mechanized compositional core.