CS Paper Radar

Inference Equivalence and Quotient Coding

Zibo Meng, Andrew C. M. Austin, Alin Achim

cs.AI cs.LG ·submitted 2026-11-16 13:42 UTC · v1

Abstract

Incomplete observations can admit multiple physical interpretations without making every task conclusion ambiguous. Recovering all compatible scenes is often unnecessary, whereas indiscriminate compression may change which claims are justified. We ask which distinctions among observation-compatible interpretation sets must be retained to preserve every valid conclusion of a specified task. We first define inference validity as truth across all physically compatible states and characterize it, under a closedness condition, by distances to physically realizable falsifying measurements. For a finite semantic claim family ordered by specificity, the Exact Inference Frontier forms the unique minimal antichain generating all valid claims. We then define inference equivalence between compatibility sets and construct a canonical quotient code from their frontiers. Among deterministic codes admitting exact inference decoding, it induces the coarsest partition, minimizing the number of distinguishable code values rather than storage or computation. Finally, we characterize inference errors from learned compatibility sets, derive conditions for exact inference preservation despite set errors, and evaluate an asymmetric learning surrogate under distribution shifts. On a registered finite bank, 145 compatibility sets yield 31 quotient codes with unchanged valid-claim sets. Across geometry, mechanism, and joint shifts, learned estimates exhibit different accuracy-specificity trade-offs. On 1,962 official HRSID test images, 1,913 distinct candidate sets induce only 36 seven-claim inference signatures, while a visual 3-NN baseline achieves 87.31% precision on issued claims.

Closest papers

Nearest neighbours by meaning across the whole index.

claimcheck: Measuring and Improving Specification Faithfulness

cs.CL cs.AIcs.PL ·2026-10-12 ·Martin Amster, One An, Holly Baker, Fernanda Graciolli, Simon Henniger +1 more
benchmarktheory similarity 0.60
Abstract

Formal verification proves that a program satisfies its specification, but says nothing about whether the specification captures what the author meant. As LLMs increasingly write both code and specifications, a gap between the author's natural-language requirement and the specification becomes a live risk. A machine-checked proof of a property narrower than the one requested is worthless but passes every check. Closing this gap is solving the spec formalization problem: given a natural-language requirement, produce a formal artifact whose meaning matches it. To measure the gap, we curate an end-to-end benchmark for spec formalization spanning four formal languages: Dafny contracts and Lean 4, Isabelle and Rocq theorem statements. Each of its 3,234 rows pairs a natural-language requirement with a formal artifact and a label established by execution, by proof, or by the benchmark it is drawn from. A third of the rows are meaning-preserving rewrites of the artifact that keep the faithful label, so a judge cannot score by detecting that a row was edited. We introduce claimcheck, a tool that detects incorrect formalizations: the formal artifact is translated back into plain English by a model that never sees the requirement, and a separate model, the judge, decides whether the informalization and the requirement express the same guarantee. On all four languages it gains 8.2 to 9.8 points of macro recall over a single call shown the requirement and the artifact, and 4.2 to 6.0 over that call handed the same list of meaning-preserving rewrites. Showing the judge the artifact as well costs 1.4 to 4.5 points. Across four judges that also see the artifact, the gain shrinks as the judge gets stronger, to within a point of the informed single call for the strongest.

0.15

Decomposition-Induced Context-Memory Conflict: An Instruction-Induced Failure and a Probing Case Study

cs.CL ·2026-08-11 ·Yu-Feng Yen
theory similarity 0.58
Abstract · v2: substantially revised after a full regeneration of all results. Conclusions changed: DI-CC is largely instruction-induced; the probe-tra…

Decompose-then-verify pipelines (FActScore-style fact-checkers, hallucination detectors) first split a passage into atomic claims and treat this step as neutral preprocessing. We ask whether a decomposer can substitute its own parametric belief for what the passage says, producing a claim that contradicts its source, and call this Decomposition-Induced Context-Memory Conflict (DI-CC). On biographies with a deliberately altered year, Qwen2.5-7B-Instruct does so in 4.3% of claims when the instruction licenses self-correction, but in only 0.2-0.5% under a neutral instruction, a FActScore-style few-shot prompt, a "use only the passage" instruction, a formatting instruction, or a knowledge-filling instruction (an upper bound: in the neutral and FActScore-style runs only 1 of 13 flagged claims is a real override); context-aware decoding removes only half. DI-CC here is therefore instruction-induced. We then test whether a linear probe trained only on classical context-memory conflict data (NQ-Swap) detects DI-CC zero-shot. Its AUC is high (up to 0.94 against legit claims, 0.98 under a position- and instruction-matched control), but random directions reach AUCs between about 0.1 and 0.9 on these contrasts, probes fit directly on the claims reach 0.96-1.00 everywhere (even on a control that separates only the text variant), and after multiplicity correction the NQ-Swap probe beats random directions only at the last layer, and only for two of three random-direction families. A direct NLI check between source and claim reaches AUC 0.998. High probe AUC on such small contrasts is not evidence of a shared mechanism without nulls, and two pitfalls, pair leakage in probe training and duplicated BOS tokens, can change such conclusions.

0.04

Deterministic, Reproducible Inference in Exact Integer Arithmetic, and Verifiable Distributed Inference as Its Consequence

cs.LG cs.DCcs.SE ·2026-11-10 ·Sayed Amir Karim
publishedcode/datahot direction similarity 0.58
Abstract

Optimized floating-point inference is not reproducible across environments: the same model on different hardware, compilers or thread counts can produce different bits. We present tritify, an open-source runtime that executes the forward pass of real models -- decoder-only language models, Mixture-of-Experts decoders, and the Segment Anything 2.1 image/video stack -- with the entire run-time path in exact integer arithmetic; floating point is confined to offline quantization and the float reference used for verification. We make three separate claims and verify each. (1) Cross-hardware reproducibility: the integer path produces bit-identical output run to run, across CPU instruction-set architectures, and across CPU/GPU, carried by a reproducing SHA-256 of the output. (2) Decision fidelity: the integer path reproduces the float reference's decision on the models and inputs tested, with the numeric exceptions measured; per-layer fidelity through sixteen layers of OLMoE-1B-7B and of a 106-billion-parameter MoE shows no fidelity cliff. (3) Location independence: a model's computation can be split across instruction sets, CPU and GPU, and networked machines with zero effect on the output bits. GLM-4.5-Air (106,852,251,264 parameters, 427 GB of integer codes) generated its answer across three machines, none of which can hold its integer codes in RAM, bit-identically to a single-host reference. The consequence is verifiable distributed inference: an untrusted server or a fleet of devices runs the model while an open scalar oracle re-derives the exact bytes; a guarantee against a dishonest server is future work. We do not claim a per-device speed-up, bit-equality of floating-valued intermediates, or confidentiality. Code: https://github.com/pelloran-inc/tritify

0.49

Impact Is Not Invalidation: Ask About the Claim, Not the Diff

cs.CL cs.AIcs.LG ·2026-09-20 ·Atul Anand
similarity 0.57
Abstract · 9 pages, 3 figures, 6 tables

Memory systems for coding agents must decide, when a repository changes, which of their stored claims have become false. Content anchoring invalidates a claim whenever the artifact it came from changes, which fires constantly. Semantic-equivalence classification asks whether a diff preserves behavior, a question about the diff rather than about any stored claim. We show the second signal fails for a reason unrelated to model capability: asked whether a commit preserves behavior, five models spanning a 40x price range fire on 59-72% of real commits and reach precisions of only 0.291 to 0.329 against a 0.25 base rate. Asked instead whether one specific claim still holds, the same models on the same diffs reach 0.705 to 0.974. A control that hands the behavior-preservation judge the claim text, changing only the question, moves precision by 0.010 and 0.016; changing the question moves it by 0.49 and 0.65. We also compare against pytest-testmon, a deployed regression-test selector with coverage-derived dependency data: it reaches 0.868 recall at 0.415 precision, so near-complete knowledge of what a change can reach does not identify what it falsifies. Ground truth is execution, not annotation: a claim is a test function passing at commit t, and it has flipped if that same assertion text fails at t+1. Building this required an observation we did not find in prior work. On a CI-gated mainline a commit that leaves a pre-existing test failing cannot merge, so the naive construction has an empty positive class by design. We report 10,369 claims with 184 execution-verified flips mined from 23 Python libraries, splits held out by repository, a post-knowledge-cutoff split, a shuffled-diff null, a paraphrase control, and a leave-one-repository-out analysis over 17 repositories.

0.44

Actions with Receipts: Jointly Binding Claims, Evidence, and Execution for Replayable Tool-Agent Auditing

cs.CR cs.AIcs.CLcs.LG ·2026-09-29 ·Miaobo Hu, Shuhao Hu, Xiaobo Guo, Xin Wang, Bokun Wang +2 more
similarity 0.57
Abstract · 35 pages, 8 figures

Tool-using agents can expose citations and execution logs while leaving a critical association unaudited: whether the claim shown to a user is the claim emitted by the committed execution and supported by the cited source. A valid citation and a valid trace can therefore remain individually well formed while being transplanted across claims, actions, runs, or source versions. We introduce a claim-anchored execution contract that jointly binds the emitted claim, its exact source span, the ordered execution prefix that produced it, and the source version and access state observed by that execution. Each receipt contains an emission anchor that deterministically locates the claim inside a committed answer or claim-bearing action, together with source identifiers, offsets, hashes, quotes, and a domain-separated execution commitment. A deterministic integrity verifier reconstructs these bindings before semantic or task labels are joined. We separate this integrity plane from a pluggable support plane, so structural validity is not used as a proxy for entailment. The contract exposes seven independently testable properties: claim-emission binding, source binding, ordered-execution binding, oracle separation, persisted-object replay, execution-rerun consistency, and version/access binding. Across 1,280 cross-object attacks, the joint contract detects 1,275 substitutions (0.9961). Removing a targeted property reduces its attack-detection rate to 0.0156-0.0625. On an independently adjudicated 384-pair split, the conflict-aware support guard reaches F1 0.8865 and false acceptance 0.0729; on unseen failure families, these rates are 0.8679 and 0.0938.

0.24

Structure-Aware Equivalence for Evaluating Autoformalized Statements

cs.PL ·2026-10-18 ·Yi Yu, Yu-Hsuan Wu, Guang Lin, Yuhui Zhang, Yuxiang Peng
benchmarkhot direction similarity 0.57
Abstract

Evaluating autoformalized mathematical statements requires determining whether a candidate preserves the mathematical claim intended by a trusted reference. Existing methods approach this problem from complementary directions: reference-free learned evaluators estimate semantic agreement but are not constrained to a formal equivalence relation, while reference-based proof methods typically employ whole-statement logical equivalence to provide formal certificates, which is too coarse for translation fidelity and may identify mathematically unrelated statements. We introduce Structure-Aware Equivalence (SAE), a role-preserving formal equivalence relation between syntactic and whole-statement logical equivalence that allows formally justified reformulations while preserving translation-relevant mathematical structure. We operationalize SAE in the Autoformalization Correctness Evaluator (ACE), which provides certified equivalence or inequivalence judgments and reports Inconclusive otherwise. On ProofNetVerif, a benchmark introduced with BEq+, ACE retains substantial equivalent-case coverage while remaining highly conservative in certifying disputed or inequivalent pairs. On targeted diagnostics, BEq+ accepts 94-96% of unrelated but whole-statement logically equivalent pairs, while Mathesis LeanScorer accepts 42% of localized meaning-changing perturbations; ACE accepts none of either set as equivalent.

0.23

Beyond Solver Verdicts: Generative Reward Models for Autoformalization

cs.LG cs.CL ·2026-09-10 ·Vikash Singh, Debargha Ganguly, Aman Goel, Ali Torkamani, Xiaoxue Han +3 more
similarity 0.57
Abstract

Neurosymbolic systems rely on mathematical solvers to guarantee reasoning correctness, yet solvers are fundamentally blind to whether a formal translation maintains strict reference-equivalence to a designated formalization. We formalize this vulnerability as Verdict-Preserving-Unfaithfulness (VPU): a failure mode where an incorrect encoding executes successfully and matches the expected verdict. We theoretically prove that structural, verdict-only verification heuristics are mathematically bounded to chance-level detection on these deceptively valid traces. To resolve this, we introduce Generative Verification (GenV), which distills an offline Z3-equivalence oracle into a reference-free, continuous reference-equivalence score by repurposing the language model's native vocabulary space. Mechanistic analysis via decision-projected logit lenses and sparse autoencoders shows this generative readout natively extracts precise spatial error coordinates without explicit localization training. Empirically, our oracle-mined verifier (GenV+HN) achieves 0.961 AUROC in reference-equivalence verification, generalizes zero-shot across unseen translators and divergent formal styles, and yields an 11.3-point downstream accuracy gain in agentic test-time compute allocation.

0.34

Endogenous Interpretation

cs.CR ·2026-09-20 ·Antonio Nappa
similarity 0.57
Abstract · 15 pages. Working paper; comments welcome. Sections 6-8 contain the formal results; Section 7.5 describes proposed experiments not yet carri…

We propose endogenous interpretation: program, interpreter, machine, and derived execution language are not disjoint semantic objects but different parameterizations of one executable state-transition relation. Each realization carries an implicit constraint bias, the structural restrictions imposed by its instruction basis, state encoding, control transfers, and finite substrate. From this viewpoint the "semantic gap" metaphor is misleading for operational semantics: a semantics-preserving transformation cannot remove the computation required for execution; it redistributes it over another state space and transition granularity (semantic diffusion). Reverse engineering is then the recovery of a lower-complexity semantic contraction. We give a first quantitative instance. For finite-state realizations observed up to bisimulation, the contraction is canonical and computable in almost-linear time, yielding an abstraction-independent diffusion ratio; for deterministic realizations this extends to trace equivalence. For nondeterministic realizations observed up to traces, minimal contraction is

0.25