CS Paper Radar

Compiling Sufficient Governance Context from Declared Losses and Reachable States: Exact Observation-Contract Synthesis with Cardinality and Cost Objectives

Gaston Besanson

cs.SE cs.AIcs.LO ·submitted 2026-09-22 11:20 UTC · v1
code/data

Abstract

We call the object this paper derives and certifies a minimal sufficient governance context: given a finite reachable-state model, a deterministic declared verdict, and candidate observable attributes, we compute sufficient observation sets, distinguish attributes that are individually indispensable from contracts that are jointly sufficient, and select among sufficient contracts under a cardinality or declared-cost objective. An observation contract is a set of candidate attributes whose values determine the declared verdict on every reachable state; an authority contract is one selected under an objective and bound to a gate schema. We synthesize every inclusion-minimal sufficient contract where exhaustive enumeration is affordable, and a minimum-cardinality or minimum-cost contract by SAT/MaxSAT encoding otherwise, checking sufficiency directly. On a constructed code/cloud domain, the individually-indispensable core is not sufficient as an observation contract and two distinct reducts exist; a preregistered cost model separates them exactly. On a second, larger, constructed domain, the same pattern recurs, but that domain's cost model does not separate the alternatives: a fully explained cost tie, reported as found. We measure discernibility-family scaling where exhaustive enumeration is confirmed infeasible within a registered timeout, while SAT/MaxSAT synthesis solves in well under a second; MaxSAT showed no measured cardinality advantage over plain SAT. AuthorityBench compares four baselines across three domains; the declared-only baseline is not exactly sufficient on any. Every selected contract is checked for sufficiency, with a counterexample on failure and a check summary, not a portable certificate, on success -- the compiler-focused scope of a two-scope table; an independently specified end-to-end case study is registered follow-up work, not claimed here.

Comment
Code, data, preregistration tags, review record, and independent reproduction (repository issue #3): https://github.com/besanson/sarc-authority-derivation. Artifact DOI: 10.5281/zenodo.22884173

Closest papers

Nearest neighbours by meaning across the whole index.

Probabilistic Sensing, Deterministic Authority: Admitting Model-Produced Observations into Sufficiency-Checked Governance Contracts

cs.SE cs.AI ·2026-10-07 ·Gaston Besanson
code/data similarity 0.63
Abstract · 23 pages. Sixth paper of the SARC series. Preregistered; external reviews and an independent reproduction are committed in the repository. C…

When a field that an authority contract needs exists only in unstructured evidence, a model can sense it. We admit the model's output only as an observation record with a score. An admission policy, with thresholds fitted on a held-out split at a declared false-positive ceiling, maps each score to true, false or unknown. Unknown denies. A deterministic, sufficiency-checked contract decides. The probability that sensing changes the verdict is bounded by the sum, over the contract's sensed fields, of the admitted-wrong and unknown rates. This is an instantiation of union-bound reasoning, indexed by the contract. Minimising the estimated bound is a valid cost model for choosing among sufficient contracts. In a registered study on two constructed domains with two sensor families (36,000 model calls), no cell refuted the bound. Deny-to-allow changes from sensing appeared for the first time in this programme: 13 of 21,000 test verdicts, all from 3 contradictory records; each flip in a cell with a registered bound lay under it. Sensing-aware selection picked the lower-exposure contract in 4 of 4 registered tests. Both sensors' scores were informative but not calibrated. Correctness is relative to the declared loss model, candidate representation and reachable states; all domains are constructed.

0.44

Contract-Based Decomposition of Temporal Logic Specifications for Networked Systems under Arbitrary Partitions

eess.SY ·2026-09-20 ·Kodai Kanno, Kenta Hoshino, Takeshi Hatanaka
similarity 0.61
Abstract

Computational complexity is an inherent limitation of formal synthesis for networked systems, and decomposing the global specification into local ones relaxes this limitation at the cost of conservatism. Since the granularity of the partition governs this trade-off, it is reasonable to treat the partition as a design variable, which calls for local specifications that remain correct for every partition. To this end, this paper gives each agent a local specification, written as an assume-guarantee contract that the agent can establish from local information. We first derive a necessary and sufficient condition for these contracts to decompose the global specification under a given partition. Building on this, we then present a condition under which the decomposition is correct for every partition, so that the partition becomes a free design variable. For linear dynamics and signal temporal logic formulas with affine predicates, we further synthesize a controller for each coalition by a tube-based approach. Finally, simulations on a network of input-coupled tanks show how the choice of partition trades computational cost against conservatism.

0.19

Minimum-Cost Robust Evidence Certificates for Horn Reasoning under Correlated Source Failures

cs.AI ·2026-10-19 ·Yukun Yang
theory similarity 0.60
Abstract · 9 pages, 2 figures

A small justification for a rule-based conclusion may disappear when a source is withdrawn, and multiple derivations need not provide independent evidence. We study minimum-cost certificates that preserve a Horn conclusion under every withdrawal of at most k source domains. Evidence records remain distinct from asserted facts, supporting replicated attestations and overlapping failure dependencies. Transversals of minimal-support footprints characterize robustness and explain why disjoint-proof requirements can reject valid certificates. An exact procedure alternates weighted evidence selection with a source-failure oracle. A rule-closed counterinterpretation yields a globally valid selection cut without enumerating supports or failure scenarios. We prove correctness, finite termination, and cost optimality, establish coNP-completeness of unrestricted verification and NP-completeness of synthesis for every fixed budget, and identify a tractable reachability restriction. Experiments on controlled benchmarks, reachability graphs, and ontology-derived instances demonstrate that our counterinterpretation-guided synthesis achieves up to 92% optimum coverage within practical resource bounds, outperforming scenario expansion and general abduction while confirming the necessity of transversal-based reasoning over proof-packing heuristics.

0.22

Two-Variable Logic with Arbitrarily Many Successor Relations

cs.LO ·2026-10-07 ·Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.59
Abstract

We study two-variable first-order logic with a finite, input-dependent number of distinguished successor relations and arbitrary additional unary and binary predicates. Each distinguished relation must be the exact immediate-successor relation of some linear order on the common domain; the orders themselves are not available in the language and may have arbitrary order types. We prove that satisfiability belongs to 2NEXPTIME, uniformly in the number of successors. The proof gives finite certificates for possibly infinite models. A closure operation separates local neighbourhood descriptions, called star types, into those of bounded multiplicity and those that can be realized infinitely often. The bounded part is represented explicitly. Outside it, integer height vectors allow overlapping successor requirements to be matched without creating cycles or unintended identifications. Ordering the resulting path components densely then recovers exact successor relations. Consistent assignments of the additional binary predicates handle witnesses involving the bounded part. The same certificates decide infinite satisfiability in 2NEXPTIME and give a doubly exponential threshold above which a finite model guarantees an infinite model. A doubly exponentially large finite core can be forced with only two successors and unary predicates. For finite models, we prove that satisfiability subject to a bound on the total number of reference adjacencies lost by the other orders is NEXPTIME-complete, even when the budget is encoded in binary and the number of successors is part of the input.

0.50

Bonded Recourse for Smart-Contract Settlement of Compensable Agent Side Effects

cs.CR cs.DCcs.MA ·2026-09-01 ·Laurent Bindschaedler, Quentin Botha, Christoph Siebenbrunner
published similarity 0.57
Abstract · 9 pages, 3 figures, 8 tables. Accepted at BCCA 2026 (IEEE International Conference on Blockchain Computing and Applications)

Autonomous agent runtimes execute tool actions that mutate databases, repositories, and cloud services across organizational boundaries. Authorization and local compensation cover pre-action admission and in-runtime rollback, but neither settles the residual harm left after a permitted action fails. We design Recourse, a smart-contract settlement protocol for compensable agent side effects that binds each admitted action to scope, recovery, evidence, payout, and collateral. Recourse separates ex ante eligibility from ex post objective settleability: typed receipts make objective residual claims computable under an optimistic-oracle challenge pattern, while subjective or incomplete claims route to ERC-792 arbitration or exclusion. We implement the contract suite, deploy it on Base Sepolia, build adapters against Postgres, Git, and cloud-compatible local sandboxes, and evaluate the system on a deterministic harness, sandbox traces, adversarial sweeps, and property-based fuzzing. Against authorization-only and local-compensation baselines, bonded coverage cuts uncompensated harm. The on-chain tier supplies neutral custody, public challenge, non-cooperative payout, and portable history under cross-organizational trust assumptions.

0.63

Beyond Policy Engines: Binding-Complete Execution Admission

cs.CR ·2026-10-21 ·Lin Wang, Mengting Wu, Yong Zhang, Jiang Deng
similarity 0.57
Abstract · 74 pages, 1 figure, 2 tables

Policy engines determine whether evaluated policies permit a request, but a correct ALLOW decision does not establish complete governance-source participation, exact context binding, or sufficient grounds for execution admission. This paper examines the gap between policy evaluation and execution admission. We introduce the Binding-Complete Execution Admission Contract (BCEAC), a governance-relative contract for independently determined source obligations, exact policy and contextual binding, and typed admission outcomes under explicit trust assumptions. We propose a conditionally engine-agnostic architecture in which participating backends must satisfy declared semantic profiles, adapter contracts, and contextual correspondence obligations; an Execution Boundary Language (EBL) authoring syntax remains optional. The architecture separates governance resolution, policy evaluation, independent admission verification, and downstream execution mediation. We investigate two distinct experimental tracks: a finite Governance Source Completeness study and an OPA/Cedar experiment with archived native-engine records examined by offline review. The OPA/Cedar archive comprises 72 scenarios and 144 strict case-engine records (120 native-invoked and 24 pre-native), with eight additional permissive controls outside the strict denominator. The offline review did not rerun the original native OPA/Cedar executables. The results provide bounded evidence while retaining historical failures and unresolved implementation defects. The work does not establish constitutional adequacy, general semantic refinement, authenticated currentness, machine-checked execution-safety theorems, or protected external effects. Its contribution is an explicit, falsifiable framework for determining what must be established between a policy decision and an execution-admission judgment.

0.17

A Contract-Centered Architecture for Scalable and Manageable Agentic Runtimes

cs.AI cs.MAcs.SE ·2026-08-27 ·Yaxiao Liu, Pengbo Liu, Yiwen Liu, Yihua Guan, Zhenghe Hou +1 more
similarity 0.57
Abstract · 52 pages, 8 figures; revised data-use contracts with an executable reference model and finite synthetic conformance artifact; updated relate…

Enterprise agentic systems must coordinate changing capabilities, execution capacity, and independently governed data. We define Skill, Harness, Scaffold, and an external data substrate as responsibility contracts. The central hypothesis, cost-aware capability-capacity separability, asks whether compatible capacity changes preserve semantic outcomes while capability changes preserve the capacity-response relationship within declared margins and enforcement budgets. We operationalize the data boundary through a source-oriented Data Wiki, an output-oriented Theme Wiki, and a versioned Intermediate Relation. Executable 5W1H+Which predicates bind source identity, validity, authorization, semantics, operations, relations, and evidence requirements. Request-bound tickets add execution-time revalidation and typed rejection. A conditional soundness argument states the required trust and atomicity assumptions; dependency invalidation makes change propagation explicit. A single-process reference model agrees with a declared specification oracle on all 1,024 combinations in a finite synthetic fault domain and passes five lifecycle checks. These are conformance results, not measurements of retrieval quality, production safety, or scaling. We specify a held-out data study and a cluster-period crossover with distinct supported, falsified, conditional-engineering, and inconclusive verdicts. The core separability hypothesis remains empirically untested.

0.27

Fault-Tolerant Budget Conservation in Distributed Multi-Agent Delegation

cs.AI cs.CRcs.DC ·2026-09-29 ·Genliang Zhu, Chu Wang
theory similarity 0.57
Abstract · 67 pages, 3 figures, 17 tables, 4 algorithms, and 3 listings. Includes formal proofs, bounded model checking, mutation analysis, and crash-i…

Resource limits are becoming an authorization boundary for AI agents that delegate work across concurrent and failure-prone workers. Parent-child allocation constraints, affine objects, and distributed escrow do not by themselves prevent overspend when replies are lost, effects complete after timeout, messages repeat, branches partition, or DAG joins alias one lineage. We formalize fault-tolerant budget conservation for distributed multi-agent delegation. Budgets are quantized resource vectors represented by exclusive escrow credits that move through a delegation DAG. Before dispatch, a branch converts credit into an operation reservation bound to lineage, epoch, normalized effect, maximum charge, receiver, and idempotency key. It persists a signed dispatch permit with quarantine; the gateway verifies that permit before first acceptance. Uncertain effects remain charged until authenticated settlement, a fenced authoritative no-effect proof, or permanent retirement. We prove ownership partition, ledger and effect conservation, descendant non-amplification, at-most-once settlement, late-completion safety, and partition confinement under explicit mediation, durability, authentication, normalization, and gateway assumptions. An indistinguishability result shows that partition-local availability requires exclusive preallocation. Bounded TLA+ checking, an independent JavaScript explorer, and crash-injected two-process SQLite experiments exercise the declared scope and detect timeout-refund and historical-certificate-validation mutants. The mechanism preserves the issued budget bound across the evaluated crash, retry, duplicate, partition, join, and late-completion schedules.

0.17