← All AI/ML open problems

AI safety & alignment · Verification & proof search · Statistical inference / Open question

Can Finite Audits Certify an Adaptive Conversation?

Multi-turn certificates rely on worst-case transition and persistence properties, while practical audits observe only a finite selection of conversations. Efficiency payoff: Spend audits on safety-relevant states and transitions instead of repeatedly testing whole conversations without a coverage argument.

OpenEditorially scopedFramework needs definitionCompiled 2026-11-20

Seed catalog · Showing the bundled record.

Problem statement

Let conversational states lie in [0,1]d[0,1]^d, attacker messages in a known finite set of size AA, and the fixed model induce unknown kernels Pu(s,⋅)P_u(s,\cdot) that are LPL_P-Lipschitz in total variation. A known rational polytope is the safe set. With paid reset-and-query samples at chosen (s,u)(s,u), learn a partition into MM cells and a lower bound ρ^H\hat\rho_H on inf⁡νPr⁡ν(s1,…,sH are safe∣s0)\inf_\nu\Pr_\nu(s_1,\ldots,s_H\text{ are safe}\mid s_0), valid with probability 1−δ1-\delta against every history-adaptive attacker ν\nu. Determine the audit cost of accuracy ε\varepsilon.

Assumptions and scope

  • The queried kernel is the actual fixed conversational system, and the state is sufficient for its dynamics in this benchmark. Reset access to arbitrary states is an explicit strong assumption; a logs-only version needs separately proved coverage or impossibility bounds.
  • Choose the partition from a finite family of rational-polytope partitions supplied as input. Include selection complexity and within-cell variation; a representative state's empirical success rate does not bound the worst state in the cell.
  • Accuracy means 0<=rho_H-hat_rho_H<=epsilon on the confidence event. Known finite-state robust dynamic programming is a baseline. Charge state queries, partition search and certificate computation, and expose any exponential dependence on state dimension or horizon.

What would settle it?

A high-confidence adaptive audit/abstraction algorithm with tight sample and computational dependence, or an indistinguishability lower bound showing which uniform guarantees finite logs cannot support.

Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.

Status and evidence

MTCR already gives conditional mode/persistence composition and a dynamic-programming calculation; it explicitly limits formal certification to bounded perturbations. The residual target is learning and validating the required uniform quantities. The continuous-state reset model is an editorial mathematical benchmark, not a claim that deployed LLM hidden states are freely resettable or certified Markov. This is an editorial, source-motivated research target. The preliminary review through 2026-11-20 does not certify novelty or exclude an unlocated resolution.

Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.

Sources and further reading

  1. Liu et al. — Certified Multi-Turn Robustness for LLM Safety via Compositional Bounds and Safety Persistence ↗partial theory · source checked 2026-11-20

    HTML Sections 2–3 checked: conditional mode/persistence bounds, dynamic programming and an explicit bounded-perturbation scope. Proposition 3.7's sufficient conditions and empirical parameter estimates are distinct; finite sampling does not by itself verify infima over every state and adaptive input.

  2. Kumar et al. — Certifying LLM Safety against Adversarial Prompting ↗partial theory · source checked 2026-11-20

    HTML Sections 3–7 and Theorem 4.1 checked: erase-and-check inherits harmful-prompt detection guarantees from a base filter; general infusion enumerates erased subsets. Benign utility is evaluated empirically and the guarantee is not unrestricted semantic output safety.

  3. Seferis et al. — Randomized Smoothing Meets Vision-Language Models ↗partial theory · source checked 2026-11-20

    Primary search abstract checked: generated responses mapped to discrete classes by a bounded-error oracle, with sample/radius laws. Output-level smoothing already has theory conditional on the classifier assumptions.