PaperlayerView exact revision on arXiv

Source-linked AI summary

PRIMUS: Identity, Governance, and Verification for Multi-Agent Federations

Sasank Annapureddy, Anjaneya Prasad Thamatani

arXiv:2609.07910v1cs.AI

TL;DR

Multi-agent federations require adversarially robust answers about identity, conformance, and authority, while verification systems may also be used to guide search. PRIMUS combines prime-indexed identity with BLS certificates, calibrated enforcement, governance mechanisms, and a graded verifier evaluation. It reports zero false kills under tested noise, a model-dependent governance crossover, useful but weakened ranking on real LLM candidates, and scope limits including objective saturation and unresolved verifier robustness.

  • Problem

    PRIMUS studies how to make prime-algebraic agent identity adversarially sound and when singleton governance is economically preferable to Byzantine quorum, while testing whether artifact verification can guide search.

  • Method

    The paper combines prime-indexed BLS aggregate certificates, noise-calibrated deviation thresholds, VRF succession with leases and fencing, and a binary-covering-code evaluation of graded artifact verification.

  • Results

    The safe-kill threshold reduces false kills from 80% to 0.0000 at ε = 0.10, while the verifier ranks candidates usefully within its scope but correlates less with real LLM candidates than with injected faults.

  • Takeaways & Limitations

    PRIMUS provides bounded adversarial governance and a useful but scope-limited verification signal, with governance choices determined by an explicit economic boundary.

  • Takeaways & Limitations

    The paper identifies model, synchrony, registry, and verifier limitations, including objective saturation after one honest answer and five problems provably unfixable within the model.

Abstract

from arXiv · show

Multi-agent federations need governance that answers three questions under adversarial conditions: who participated (identity), did they conform (enforcement), and who decides (authority). A separate question is whether the verification machinery that polices a federation's outputs can also steer a generate-and-test loop toward better answers. Part I. PRIMA introduced prime-power agent identity and a consensus token whose factorization indexes participation, but assumed honest agents. We present PRIMUS, which couples prime-power identity with BLS aggregate signatures (PIAC), derives a safe-kill threshold that reduces false-positive agent termination from 80% to 0.00% under 10% channel noise, gives the closed-form economic boundary where singleton governance outperforms Byzantine quorum ($γ^* \approx 9f$, verified flat across n = 50 to 10,000), and specifies VRF succession with lease and fencing that makes safety unconditional under partial synchrony. Five problems are identified as provably unfixable within the model and stated as scope boundaries. Part II. A verifier is not a solver. We ask whether PRIMA's binary artifact-fidelity verdict can be converted into a graded fitness signal, and measure the conversion on binary covering codes. Calibration against injected fault burden is strong ($ρ$ = 0.676 deterministic, 0.819 full); against real LLM-generated candidates the same scores fall to 0.158 and 0.406, roughly a quarter of the calibration value (the same-designer confound, measured). As a pre-filter it beats a random-score control convincingly and a binary gate narrowly. Under 400 iterations of explicit optimization it was not gamed, but only because the objective saturated after one honest answer. A cross-family judge preserves the burden-ordering signal while destroying individual judgments. No covering-code record resulted. Measured program cost: USD 164.78.

1 Introduction

PRIMUS extends PRIMA’s prime-based identity into adversarial governance, combining cryptographic participation records, bounded enforcement, and explicit limits under stated system assumptions.

  • 1 Introduction: PRIMUS addresses adversarial governance by asking who participated, whether agents conformed, and who decides.The model covers heterogeneous agents and services, Byzantine behavior, and succession constraints.
  • 1 Introduction: PRIMA’s prime-power identity and factorized consensus token are publicly forgeable because the original setting assumes honest agents.PRIMUS therefore adds cryptographic binding to the participation record.
  • 1.1 Contributions: PIAC couples the prime factorization of the consensus token to BLS aggregate-signature verification, making one algebraic index serve identity and cryptographic participation checking.The construction relies on proof-of-possession and a trusted registry of cluster primes and keys.
  • 1.1 Contributions: 0.0000 false kills replace the naive rule’s 80% destruction of a conforming federation at 10% channel noise.The threshold is feasible when θ < 1/(1 − λ) and was verified over 30 trials, 500 rounds, and 200 agents.
  • 1.1 Contributions: γ∗ ≈ 9f marks the economic boundary below which singleton governance is correct and above which quorum governance dominates.The boundary is model-dependent and was verified across n = 50 to 10,000.
  • 1.2 Non-contributions: PRIMUS applies existing BLS, VRF, EWMA, lease, fencing, and quorum techniques rather than inventing new cryptography.Its guarantees depend on partial synchrony, authenticated channels, a trusted registry, and economic rationality for self-inflation mitigation.

3 PIAC: Prime-Indexed Aggregate Certificate

PIAC makes prime-indexed participation certificates verifiable by using token factorization to reconstruct the messages checked by BLS aggregate verification, while preserving explicit non-properties.

  • 3 PIAC: Prime-Indexed Aggregate Certificate: For each epoch, task, cluster prime, and BLS keypair, PIAC constructs a signed contribution that is aggregated into a certificate.The certificate combines the token, aggregate signature, noise parameter, and epoch or task context.
  • 3 PIAC: Prime-Indexed Aggregate Certificate: Verification first trial-divides T as an algebraic pre-filter, then reconstructs per-cluster messages and runs BLS AggregateVerify.The order is mandatory, and unauthorized factors produce attributable contamination evidence.
  • 3 PIAC: Prime-Indexed Aggregate Certificate: The factorization of T indexes the public-key set used to verify S, so the identity and cryptographic layers share one algebraic index.This supports participation unforgeability, epoch binding, and contamination detection under the stated assumptions.
  • 3 PIAC: Prime-Indexed Aggregate Certificate: PIAC proves who signed for an epoch, not whether the contribution was truthful, complete, or proportionate to the claimed work.Completeness additionally requires every honest cluster’s contribution to reach an honest verifier within the post-GST bound.
  • 3 PIAC: Prime-Indexed Aggregate Certificate: 27,669 bytes is the reported token size for (n, m) = (10,000, 100) with the stated mean-depth assumption, while S remains 48 bytes.Token size depends on mean contributed depth, not agent count alone.

4 Conformance Enforcement

PRIMUS combines EWMA-based deviation scoring with a theorem-derived kill threshold, certificates, audits, and layered defenses to enforce agent conformance under noise and adversarial behavior.

  • Safe-kill threshold: Theorem 4.1 sets a kill threshold that bounds false-kill probability at δ while retaining feasibility under θ < 1/(1 −λ).The threshold is derived using weighted Hoeffding and the conforming-agent deviation model.
  • Certificate enforcement: Kill certificates rejected 1000/1000 fabricated kills and accepted 1000/1000 legitimate kills.Certificates support recomputation of deviation scores, theorem compliance, aggregate signatures, and quorum size.
  • Adversarial defenses: A 5% statistical audit with permanent eviction reduced self-inflation by 99% over 2000 rounds.This defense is economic rather than cryptographic and depends on rational adversaries.
  • Adversarial defenses: Identity attribution remains Byzantine-resilient, but contribution-depth accuracy remains economically mitigated and fails against adversaries willing to pay any cost.The paper therefore treats A2 as mitigated, not closed cryptographically.

5 Governance Protocol

PRIMUS offers singleton and quorum governance regimes, derives their economic crossover, and adds VRF succession, leases, and fencing to preserve governance safety under partial synchrony.

  • Regime definitions: Regime A uses one Warden with O(n) per-round and O(1) per-kill costs, while Regime B uses q = 3f + 1 members and ≥2f + 1 signatures.Regime A has economic safety; Regime B is Byzantine-tolerant.
  • Regime crossover: Below γ∗ the singleton is economically correct; above γ∗, Byzantine quorum dominates.Closed form and simulation agree within 0.89–1.16×, while γ∗ remains 0.0181 across n = 50 to 10,000.
  • Regime crossover: Attack dilution is a precondition: if quorum members are individually as targetable as a lone Warden, γ∗→1.0 and quorum never pays.The paper presents this as a boundary condition rather than a universal rejection of leader-based coordination.
  • Succession: VRF succession with registry-bound identities limits a 5% minority to approximately 5% of Wardenships, versus 84% without registry binding.Eligibility also requires depth, deviation, and cooldown constraints.
  • Succession: Monotone epoch fencing produced 0.0 split-brain rounds versus 794.5 without fencing in a 5000-round simulation.Leases are time-bounded with jitter, and fencing is local, synchrony-free, and unconditional.
  • Warden enforcement: Quorum certification reduced Byzantine Warden over-enforcement from 99 honest agents killed to 0.Kill certificates plus a public log reduced the figure to 4.3, while rate-limiting alone left 99.
  • Warden enforcement: Deviation-state persistence limits free adversarial deviation to G∗= 10 rounds per succession gap, whereas without persistence the adversary remained undetected in 100% of trials.The persistence boundary was validated using D(9) = 6.126 and D(10) = 6.513 at λ = 0.9.

6 The Prime Layer: Load-Bearing or Decorative?

The prime layer structurally couples identity, participation evidence, and verification, but the paper finds it cleaner rather than uniquely necessary, while the verification-to-search question remains unresolved.

  • Load-bearing roles: The prime layer preserves unauthorized-prime evidence, enables a cheap residue pre-filter, and supports grinding immunity through registry-assigned identities.The pre-filter rejects outsider primes before pairings, while registry binding prevents self-expansion of the VRF input space.
  • Structural assessment: PRIMUS couples identity, participation evidence, and cryptographic verification in one algebraic object, reducing the number of independent mechanisms requiring consistency.The paper characterizes this as an engineering benefit, not a security proof.
  • Structural assessment: Standard participant lists with signed registry certificates and explicit outsider-detection logging can achieve comparable security at the cost of additional coordination.The paper claims the prime encoding is cleaner, not uniquely capable; Theorems 4.1 and 5.1 are independent of the encoding.
  • Verification signal: PRIMA’s original verifier returned binary FAULT_DETECTED / NO_FAULT_DETECTED verdicts without confidence, severity, or a sweepable threshold.The paper identifies this binary signal as a barrier to hill-climbing search.
  • Verification signal: Fidelity checks whether write-up numbers match artifacts, not whether the method is sound, so a graded transform cannot repair the target problem.A faithfully reported wrong or unambitious answer remains an attainable global optimum.
  • Open question: The graded-versus-binary question remains unresolved across literature arguing for density and literature arguing for binary scoring.The paper reports measuring five preregistered questions rather than claiming to settle the dispute.

9 Position on the Verification Ladder

The pilot reaches the top of its verification ladder for covering-code acceptance because it uses an exact deterministic oracle, but its domain and optimization evidence remain narrowly bounded.

  • Verification ladder: Only 1 of 9 surveyed closed agentic loops reaches an external oracle, placing the broader practice mostly below exact external verification.The survey organizes practice into eight tiers from machine-checked proof to LLM-judging-LLM.
  • Pilot placement: The pilot occupies the top of the ladder for acceptance because its oracle is deterministic, millisecond-scale, and independently recomputed in a fresh interpreter.Its scope is limited to artifact fidelity and covering-code acceptance, not method correctness or domains without exact oracles.
  • Oracle design: The frozen oracle supplies binary validity, native graded num_uncovered, and objective |C|, with every valid code ranked above every invalid code.The frozen fitness ranks validity strictly above size.
  • Evaluation scope: The pilot instance was binary covering codes with (n, R) = (12, 3), incumbent 30, census bound 28, and frozen tiers IMPROVE ≤29, MATCH = 28, and BEAT ≤27.A second (13, 3) instance was specified but never run.
  • Audit design: The audit decomposed PRIMA fault classes into 12 atomic checks, including nine deterministic checks and three judged checks across scripts, result JSON, and write-ups.The judged checks covered traceability, tier overclaiming, and related claims.
  • Audit results: Independent recomputation caught 39/39 result-tampering faults but only 21/52 process-fraud faults.The process-fraud injectors used genuinely valid codewords copied from the real base, so persisted results remained true.
  • Anti-gaming design: Anti-gaming clauses froze the harness, instances, tiers, and acceptance boundary, while oracle access was restricted to selection rather than acceptance.Only 20% of candidates received the exact oracle in the rationed regime, and it was hidden entirely in Step 4.

11 Results

The experiments measure calibration, candidate selection, adversarial optimization, and cross-family judging. Graded scoring tracks injected burden strongly but transfers weakly to real candidates, while selection gains are narrow and optimization results are inconclusive beyond an honest optimum.

  • 11 Results: 146/146 judged artifacts received scores, with $13.115 spent on judged scoring.
  • 11.1 Step 2: Calibration: 0.819 full-score correlation with injected fault burden exceeded the deterministic-only value of 0.676, with both preregistered tests passing.The corresponding burden-ordering sequences were 1.000 / 0.830 / 0.691 / 0.641 for full scoring and 1.000 / 0.893 / 0.798 / 0.766 for deterministic-only scoring.
  • 11.2 Step 3: Baseline duel: 28.8% of 250 LLM-generated candidates crashed, while 56.8% were verified valid and 17.5% of claimed covers=True results were oracle-invalid.Algebraic construction-style mutations fabricated covers=True at 23.5%, compared with 5–7% for local search.
  • 11.2 Step 3: Baseline duel: Graded pre-filtering beat random and binary controls on wasted-oracle fraction, but the binary comparison passed narrowly and best-size differences were not significant.The A-vs-B confidence interval was [0.020, 0.220], with B tying A in 2 of 5 pools; no best-size confidence interval excluded 0.
  • 11.2 Step 3: Baseline duel: 0.406 full-score correlation with true oracle fitness fell below 0.158 for deterministic-only scoring, far below calibration results.The evaluation excluded 72 no-result candidates, leaving n = 178.
  • 11.3 Step 4: Adversarial optimization: 0/380 fabricated covers=True claims occurred during optimization, but all 380 valid artifacts had |C| = 32 after reaching score 1.0 within 1–3 iterations.The experiment therefore found an honest optimum rather than testing exploitation above a saturated objective.
  • 11.4 Step 5: Cross-family verifier: 0.767 cross-family burden-ordering correlation remained near Claude’s 0.819, while individual-check agreement was only 37–68%.The Qwen judge passed every J03 check and penalized 69.6% of clean artifacts, so it was not a drop-in verifier.

12 Findings That Generalize

The paper identifies generalizable boundaries for repurposing artifact verifiers: calibration can flatter real-candidate performance, judged scoring has a measurable economic break-even, and cross-family ordering does not imply reliable individual judgments.

  • 12 Findings That Generalize: 0.676 versus 0.158 deterministic correlation, and 0.819 versus 0.406 full correlation, quantify the same-designer calibration confound.Faults injected by the checks’ designers are shaped like those checks, inflating calibration relative to real generator quality.
  • 12 Findings That Generalize: $2.69, $2.35, and $6.27 are the break-even exact-oracle prices against random selection, no pre-filter, and a binary gate, respectively.Judged scoring cost $0.150 per candidate, or $7.52 for a 50-candidate pool; deterministic-only pre-filtering reduced wasted calls from 0.340 to 0.200 at no scoring cost.
  • 12 Findings That Generalize: All 380 valid artifacts converged to |C| = 32 against an incumbent of 30 because the checklist lacked a size term.The fidelity-only objective rewarded honest reporting but did not pursue more ambitious covering codes.
  • 12 Findings That Generalize: 0.767 versus 0.819 burden-ordering correlation transferred across judge families, but individual agreement remained only 37–68%.The cross-family judge penalized 69.6% of flawless artifacts, limiting substitution despite preserved ordering.
  • 12 Findings That Generalize: 100% of FC6 result fraud was caught by the audit, while roughly 40% of FC5 process fraud remained because the results themselves were true.Script-inspection checks cover the fidelity axis, whereas the audit addresses result-level process fraud.
  • 12 Findings That Generalize: A targeted search found no prior art for lineage-EWMA eviction with audit rate q defending an artifact-level fidelity verifier under adversarial generation.The paper permits only the narrower claim that this was the first such measurement found and found nothing to defend against at this budget.

13 Non-Contributions and Honest Scope

The study produced no covering-code record and supports only narrow conclusions about pre-filtering, optimization, and lineage eviction in one problem class.

  • 13 Non-Contributions and Honest Scope: 32 was the best valid size in every run, against a verified incumbent of 30 and a census bound of 28; zero IMPROVE candidates appeared in 650 artifacts.The graded-versus-binary result concerns one metric, one fault regime, and five pools; the honest-generator regime was untested.
  • 13 Non-Contributions and Honest Scope: Zero evictions fired because honesty cost the adversary one call to greedy_cover, so lineage eviction was untested rather than vindicated.The pilot used a free exact oracle and one problem class.

14 Threats to Validity

Validity is constrained by the experiment’s saturated objective, fixed-pool replay, model-family coverage, judged-check reference, and explicit federation assumptions and scope boundaries.

  • 14 Threats to Validity: The Step 4 null shows only that this model, given this objective, did not cheat; it does not establish checklist robustness.The adversary reached score 1.0 with one honest call, leaving no gradient for exploit exploration.
  • 14 Threats to Validity: Paired replay ranks candidates on a fixed pool rather than measuring selection feeding later generations.This design was about four times cheaper than a separate pool per arm but does not model sequential search dynamics.
  • 14 Threats to Validity: Step 5 covers only 3 of 12 checks on 146 of 650 artifacts, with the rest using the same model family.The evidence does not separate small-model limitations from broader cross-family judgment non-transfer.
  • 14 Threats to Validity: Claude verdicts are the reference rather than ground truth for judged checks, and deterministic checks inspect source text rather than execution traces.A reference in a dead branch can satisfy checks D02, D06, D07, or D08.
  • 14 Threats to Validity: The model excludes state-machine replication and treats consensus asymmetrically, so the 3f + 1 bound applies to decisions, not PIAC aggregation.Conflating quorum decisions with parallel signature aggregation is identified as a likely reviewer error.
  • 14 Threats to Validity: Attack dilution is a precondition, and deployments with individually targetable quorum members violate it.The economic boundary γ* is model-dependent and assumes a linear cost model.
  • 14 Threats to Validity: Part II used a free exact oracle, so nothing demonstrates the method where correctness is not available as a function call.Proposed follow-ups include domains without exact oracles, sequential loops, and larger cross-family judges.

18 Conclusion

Part I frames governance mechanisms as safeguards for identity, enforcement, and authority under adversarial conditions, while Part II finds that verifier-guided search is useful only within a bounded fidelity scope. The paper reports both positive results and explicit deployment and generalization boundaries.

  • Part I: Part I couples prime-algebraic identity with BLS aggregate signatures, noise-calibrated enforcement, and fault-tolerant governance for adversarial federations.The paper presents these mechanisms as the conditions under which PRIMA’s identity substrate becomes load-bearing.
  • Part II: Part II finds that a fidelity verifier can rank candidates usefully within its own scope, but that scope limits the search it steers.Its correlation with real generator quality is roughly a quarter of its correlation with self-authored faults.
  • Cross-part conclusion: The paper’s shared discipline is to state falsifiable claims, report negative results alongside positive ones, and mark unsupported boundaries explicitly.This principle is stated as applying across both parts.
  • Future deployment: A proposed StatePlane integration would use PRIMUS for auditable participation attribution and bounded enforcement, but that integration remains production work outside this paper.The proposed connection concerns episodic-state consolidation and candidate-artifact lineage.
  • Incident boundary: The incident discussion illustrates the target failure class, but PRIMUS was not deployed in that environment and cannot replace service-specific vulnerability remediation.The environment lacked registry-governed participants, and implementation defects remain outside the governance layer’s scope.

A Unverified Numbers

This section distinguishes analytical projections, model-dependent objections, implementation costs, and reproducibility controls from measured results. It also records where the paper’s guarantees remain limited by assumptions about costs, adversary classes, and workload openness.

  • Analytical projections: 150–1970 rounds is the projected succession gap, while m ≈200, ∼50×, ∼$0.005/query, ∼28.4 h, and ∼$39 are unbenchmarked analytical estimates.The passage explicitly labels these figures as analytical projections rather than measured results.
  • Objections: The prime layer is not uniquely necessary: standard PKI could match several properties, while the strongest distinction depends on retaining or reconstructing the integer token.The objection concedes weaknesses in some claimed differentiators and narrows the remaining distinction to unauthorized-participant coordinates.
  • Objections: The 0.89–1.16× crossover agreement holds within one linear cost model; congestion and correlated damage could shift the boundary, and no deployment data exists.Congestion would shift γ∗ upward, while correlated damage would shift it downward; the latter is not modeled.
  • Objections: PIAC proves who signed, but it does not establish contribution magnitude; deterministic workloads are auditable, whereas open-ended generation is not.The passage separates attribution from magnitude and distinguishes the Byzantine threat model from rational-agent self-inflation.
  • Accounting and verification: $164.92 is the reported total including Step-1 samples, while frozen artifacts, hashes, and independent recomputation support the audit trail.The measured program cost before Step-1 samples is $164.78, and the artifact integrity checks were applied throughout Steps 1–5.
Loading 2609.07910v1…