Source-linked AI summary
Certified Task-Conditioned Active Observability
Linzhe Zhang, Changming Xu
TL;DR
Classical observability asks whether a microscopic state can be reconstructed, while practical systems may require perturbation and task-relevant distinctions rather than full inversion. The paper formalizes certified task-conditioned interaction, derives minimal representations and adaptive guarantees, and reports state recovery with zero false acceptances and reduced resource use.
Problem
Classical observability requires unique microscopic reconstruction, although passive observations may leave latent degeneracies and task-irrelevant distinctions can consume interaction resources.
Source: §1 · p. 1Method
The paper formalizes task-conditioned active observability, proves a minimal task-predictive quotient and adaptive guarantees, and develops a staged observer with evidence-triggered fallback and score-shell compression.
Source: §1 · pp. 1–2Results
Across high-dimensional systems and operational trials, the staged observer recovered task-relevant states with zero false acceptances, safely abstaining under ambiguity while reducing sensor queries and model computation.
Source: §1 · p. 2Takeaways & Limitations
Task-predictive quotienting preserves active observability complexity while removing task-irrelevant distinctions, and the observer demonstrates staged certified recovery in operational trials.
Source: §1 · p. 2The guarantees cover finite controlled models with known representations under deterministic policies, not unanchored cold-start identification or unmodeled process faults.
Source: §7 · p. 7
Abstract
from arXiv · showhide
Before acting upon an unobservable physical system, an autonomous agent must determine which latent distinctions govern downstream tasks, how many active interventions are necessary to certify them, and when to abstain to prevent catastrophic errors. Classical observability treats state reconstruction as an unconditioned binary predicate, failing when passive observations cannot break latent degeneracies without perturbation, full microscopic inversion is prohibitively costly, and distinguishing task-irrelevant degrees of freedom wastes interaction budgets. We formalize task-conditioned active observability complexity: the minimum worst-case expected interaction cost required to identify task-relevant states under certified error and safe abstention guarantees. We prove that task-predictive equivalence induces the unique minimal sufficient quotient $\mathcal{H}/\!\sim_\tau$, leaving active observability complexity strictly invariant while eliminating superfluous distinctions. In deterministic regimes, this complexity is characterized by an optimal adaptive distinguishing tree and Bellman recursion; in noisy regimes, it obeys a stopped-transcript relative-entropy lower bound and adaptive martingale certificates that compose without independence assumptions. We instantiate a prospective certified observer with staged recovery: a nominal verifier defers candidate compilation, triggering active probing only upon evidence, while a history-measurable score shell prunes hypotheses without sacrificing risk bounds. Stress audits across high-dimensional physical systems and thousands of operational trials demonstrate certified state recovery with zero false acceptances and substantial reductions in sensor reads and model steps.
1. Introduction
The paper reframes observability around identifying task-relevant states under certified error and safe abstention, rather than reconstructing every microscopic state. It develops the theory, an operational observer, and a scheduling result, then reports successful recovery with fewer sensor queries and model steps.
1. Introduction
- Task-conditioned active observability complexity measures the minimal adaptive-experiment cost of distinguishing task-relevant states, separately from the complexity of representing relevant distinctions.The formulation requires certified error and safe abstention guarantees.Source: §1 · p. 1
- Task-predictive equivalence yields a unique minimal sufficient quotient that removes task-irrelevant distinctions without changing active observability complexity.Deterministic cases admit an exact adaptive distinguishing-tree characterization; stochastic cases have a stopped-transcript relative-entropy lower bound and adaptive martingale certificates.Source: §1 · p. 2
- The observer verifies a lightweight nominal state first, triggers fallback compilation when evidence warrants, and uses score-shell compression while preserving conditional safety.It certifies transitions on independent forward measurements and maps unresolved ambiguity to abstention.Source: §1 · p. 2
- When candidate compilation yields no useful intermediate sensing outputs, interleaving reads with partial compilation is pathwise weakly dominated by atomic fallback compilation.The result supports compiling fallback candidates atomically upon a certified trigger.Source: §1 · p. 2
- The staged observer recovered task-relevant states across high-dimensional systems and operational trials, with zero false acceptances and safe abstention under ambiguity.The reported trials also showed substantial reductions in sensor queries and model computation.Source: §1 · p. 2
2. Problem formulation
The formulation models a finite set of controlled hypotheses, a fixed task map, and nonanticipating policies that return a task label or abstain. Task-predictive equivalence then defines the minimal representation that preserves both task labels and future experimental evidence.
2.1. Finite controlled hypothesis model
- A completed operation history yields a finite candidate set whose hypotheses specify candidate endpoints and known future transition and observation models.The observer chooses actions, receives observations, and updates each candidate's propagated state.Source: §2.1 · p. 2
- Policies are deterministic measurable maps of observed history, with stopping and output nonanticipating; the output is a task label or abstention.All probability comes from the observation process, not exogenous randomization.Source: §2.1 · p. 2
- A fixed task map specifies which distinctions matter, including exact operation endpoints, active/inactive labels, or another task-relevant quotient.When reporting a current state, the operation-end label can be propagated through confirmation actions before output.Source: §2.1 · p. 2
- The formulation assigns each action a positive physical interaction cost and evaluates policy validity uniformly over hypotheses.The worst-case task-conditioned active observability complexity is defined separately from computation; computation can be folded into generalized cost when serial and action-independent.Source: §2.1 · p. 2
2.2. Task-predictive equivalence
- Task-predictive equivalence groups hypotheses with the same task label and the same induced finite transcript law under every finite deterministic nonanticipating experimental policy.For standard controlled Markov kernels, equality can be checked on finite open-loop action words, with adaptive equality following by conditioning and induction.Source: §2.2 · p. 2
- Any representation sufficient to recover task labels and all future experimental laws must refine the task-predictive quotient, making that quotient uniquely minimal up to relabeling.The quotient isolates distinctions that can affect the answer or future evidence and justifies quotienting before optimization.Source: §2.2 · pp. 2–3
- If different task labels have identical transcript laws under every policy, no valid observer exists when 2α+β < 1.Source: §2.2 · p. 3
3. Active observability theory
The section characterizes deterministic task distinction through exact adaptive trees and treats noisy observation through information bounds and certified trees. Certified composition requires no independence between node tests.
3.1. Exact deterministic characterization
- In deterministic systems, the minimum exact distinguishing cost equals the optimal task-separating tree cost, characterized by a Bellman recursion.The equivalence is exact: every exact policy unfolds into a separating tree, and every such tree is executable.Source: §3.1 · p. 3
3.2. Noisy information lower bound
- For noisy observations, every task-inequivalent pair imposes a stopped-transcript relative-entropy necessity under the condition 2α + β < 1.A zero information rate for any task-inequivalent pair makes the complexity infinite.Source: §3.2 · p. 3
3.3. Certified-tree upper bound
- Certified distinguishing trees provide an upper bound on active-observability cost, and their adaptive composition requires no independence between node tests.In the deterministic noiseless specialization, the certified-tree optimum reduces to the exact deterministic quantity.Source: §3.3 · pp. 3–4
4. Certified observer construction
The observer first verifies a nominal candidate and defers fallback compilation; evidence can trigger fallback early. History-measurable score-shell pruning preserves the false-accept bound, while compilation can be performed atomically under stated assumptions.
4.1. Nominal-first staged confirmation
- The nominal-first observer verifies one expected candidate before compiling the generic fallback bank, using separate risk budgets for nominal and fallback certification.If the nominal candidate is confirmed, it is accepted immediately; otherwise, the union bank is compiled and verified on subsequent independent measurements.Source: §4.1 · p. 4
4.2. Readwise evidence-triggered fallback
- Strong discordant evidence against the nominal candidate can trigger fallback before the nominal testing budget is exhausted, without compromising conditional safety.The trigger monitors the verification transcript readwise, and fallback certification uses disjoint subsequent data.Source: §4.2 · p. 4
4.3. Score-shell compression and exact compilation
- A history-measurable candidate bank fixed before fresh confirmation preserves the verifier’s conditional false-accept bound, though candidate omission can reduce coverage.Calibration with m = 100 gives the frozen J = 8 choice next-block marginal coverage of at least 100/101.Source: §4.3 · pp. 4–5
- The hybrid compiler returns the same endpoint-score candidate map as exhaustive filtering while bypassing unviable branches when its certificate succeeds.If the certificate fails, it falls back to exact exhaustive enumeration.Source: §4.3 · p. 5
- When compilation has no usable intermediate output and the stated cost and timing assumptions hold, interleaved reads and partial compilation are pathwise weakly dominated by atomic fallback.The proof moves useful compilation to the point when the completed bank is used and deletes unused work.Source: §4.3 · p. 5
5. Empirical evaluation
Across three benchmark domains, the evaluations test prospective controller policies, score-shell compression and compiler exactness, and theoretical invariants. Nominal-first staging reduces model computation and sensor reads while preserving correct task confirmations; score-shell compression sharply reduces candidate and verifier costs, and exact compilation preserves the full candidate map.
5.1. Experimental setup and evaluation metrics
- The prospective testbed uses 72 tasks across six families, while the confirmatory compression benchmark spans 2,000 operations and the synthetic suite tests 600 automata and 5,000 noisy policies.All hyperparameters were frozen before evaluation; the audit covers physical interaction, computation, certification reliability, compiler exactness, candidate coverage, and conditional false-accept safety.Source: §5.1 · p. 5
5.2. Closed-loop interaction and computation trade-offs
- All six policies correctly confirm 72 tasks; nominal-first staging reduces model computation from 8.62 million to 1.65 million steps and mean future reads from 104.25 to 88.76.Eager compilation incurs computation across 52 inactive tasks.Source: §5.2 · p. 5, Table 1 · p. 6
- With λ = 1000, readwise switching reduces mean future reads from 88.76 to 87.71 while compiling the same 20 active tasks; λ = 10 reaches 86.22 reads but adds 16 unnecessary compilations.Across 52 inactive tasks, nominal confirmation uses 82.67 future reads and zero compilations; among 20 active tasks, conservative readwise triggering reduces average reads from 104.60 to 100.80 and shifts the median fallback trigger from 9 reads to 4.Source: §5.2 · p. 6
5.3. Representation compression and exact compilation
- Across 2,000 operations, the top-J = 8 score shells reduce candidate states from 7,520,508 to 1,090,024 and verifier model steps from 140,052,481 to 20,210,639, with physical reads reduced by 2.19%.Figure 2 shows candidate-state and verifier-computation costs at about 14.5% of full-bank values, while physical interaction changes much less; one omitted endpoint resulted in safe abstention and there were zero false acceptances.Source: §5.3 · p. 6, Figure 2 · p. 6, Table 3 · p. 7
- Direct score-shell compilation matches exhaustive enumeration state by state across all 2,000 operations; early certified search reduces total evaluations by 104,699,068, or 1.04%.Direct certificates occur in 38 operations and reduce compilation evaluations by 28.19% on those instances; branch pruning introduces zero approximation error into state verification.Source: §5.3 · p. 6
- Across 600 deterministic automata, task-predictive quotienting preserves exact distinguishing depth and reduces representations in 75; the stated information lower bound holds in all 461 nonvacuous risk-constrained noisy instances.The stochastic audit also covers 5,000 adaptive noisy policies.Source: §5.3 · p. 7
6. Related work
The paper positions task-conditioned active observability alongside classical observability, active state estimation, sequential experimental design, and finite-state-machine testing. Its emphasis is task-relevant state recovery with finite candidate representations, interaction costs, certified error, and safe abstention.
Related work
- Unlike classical observability or active state estimation, this formulation makes task equivalence, finite candidate representations, interaction cost, error, and abstention explicit, seeking an exact finite-system characterization rather than a rank condition or estimator design.Classical observability addresses reconstruction from input-output behavior; active state-estimation work selects inputs to improve estimation quality (Hu & Ersson, 2004).Source: §6 · p. 7
- Sequential experimental design and controlled sensing study hypothesis discrimination under sample or decision-risk constraints; this work emphasizes their interface with evolving controlled states, task-conditioned quotients, certified node tests, candidate compilation, and safe abstention.The paper places its KL lower bound in this information-theoretic lineage (Naghshvar & Javidi, 2013; Nitinawarat et al., 2013).Source: §6 · p. 7
- The deterministic distinguishing tree is related to adaptive experiments in finite-state-machine testing, but is coupled here to a risk-controlled noisy observer and history-dependent candidate representations.Automata learning reconstructs unknown state machines from query responses (Angluin, 1987; Vaandrager, 2017), whereas this setting optimizes recovery within a known dynamical representation.Source: §6 · p. 7
- The framework complements physical representation learning: after a continuous physical ontology is discovered and frozen, task-conditioned quotienting avoids resolving task-irrelevant fluctuations while retaining guarantees against erroneous state assertions.The cited series concerns discovering continuous coordinate geometry, Lie group gauge symmetries, and thermodynamic contact structures through interventions (Zhang & Xu, 2026a;b;c).Source: §6 · p. 7
7. Limitations
The theoretical guarantees are scoped to finite controlled models with known representations under deterministic policies. The atomicity analysis concerns sequential evaluation; parallel execution, deadlines, and incremental candidate generation remain practical extensions.
Limitations
- The theoretical guarantees cover finite controlled models with known representations under deterministic policies, not unanchored cold-start identification or unmodeled process faults.Distribution-free conditional coverage across arbitrary covariates remains an open theoretical direction.Source: §7 · p. 7
- The atomicity analysis covers sequential evaluation; parallel execution, execution deadlines, and incremental candidate generation remain deployment directions.Source: §7 · p. 7
8. Conclusion
Task-conditioned active observability separates minimal predictive representation from the interaction needed to identify a task-relevant state. The remaining open direction is narrowing the noisy-information-bound to certified-tree gap within a fixed representation.
8. Conclusion
- The predictive quotient is uniquely minimal and leaves active-observability complexity unchanged; deterministic systems have an exact adaptive-tree characterization, while noisy systems have information lower bounds and certified-tree upper bounds.The observer defers expensive candidates, triggers fallback from evidence, uses fresh confirmation data, and compresses representations without conflating safety and coverage.Source: §8 · p. 8
- Within a fixed representation, tightening the gap between the noisy information lower bound and executable certified trees remains the primary open direction.Source: §8 · p. 8
A.1. Proof of the minimal predictive quotient theorem
The proofs establish that task-predictive equivalence is the minimal sufficient quotient, deterministic complexity equals the optimal separating-tree cost, and noisy guarantees compose under adaptive testing and staged recovery.
A.1. Proof of the minimal predictive quotient theorem
- Any sufficient representation must refine the task-predictive quotient, and policies on the original hypotheses and quotient lift or descend with unchanged transcript, cost, error, and abstention laws.Source: §A.1 · p. 10
- Identical transcript laws for states with different task labels contradict the required validity and error bounds when 1 −α −β > α.Source: §A.1 · p. 10
A.2. Proof of the deterministic closure theorem
- Every exact deterministic policy induces a task-separating tree, and every such tree executes an exact policy, proving AO0,0(S) = D(S) and yielding the Bellman recursion.With positive action costs, the least extended Bellman solution is +∞ exactly when no finite separating tree exists.Source: §A.2 · p. 10
A.3. Proof of the KL lower bound
- The noisy lower-bound proof uses monotonicity of binary relative entropy and the chain rule; shared history-based action-selection kernels cancel in the likelihood ratio.Source: §A.3 · p. 10
A.4. Proof of certified adaptive composition
- Adaptive node tests compose by conditioning on each entry history and summing misrouting risks and costs along realized paths, without cross-node independence.Source: §A.4 · p. 10
A.5. Proof of history-measurable sub-bank safety
- A history-measurable sub-bank preserves the verifier’s conditional safety bound, while omission can remove the completeness premise for acceptance; exchangeability bounds the calibration failure probability by 1/(m + 1).Source: §A.5 · p. 10
A.6. Proof of atomic fallback dominance
- When compilation yields no sensing outputs and does not change the plant, useful compilation steps can be moved into one contiguous block before first use without increasing pathwise cost.Source: §A.6 · p. 10
B.1. Staged risk accounting
- Staged risk accounting bounds the probability of a wrong acceptance by α1 + α2, conditional on fresh stage-2 data after the stage-1 history.The bound does not require the full or compressed bank to contain truth.Source: §B.1 · p. 11
C. Additional empirical results
The additional results report developmental replay savings and a deployment-sensitive comparison of compilation strategies. The measured timing crossover is specific to the frozen compiler and traces.
C.1. Parallel speculation sensitivity
- 0.258% wall-clock advantage at 1 ms/read and 0.085% at 10 ms/read favored full speculation, while readwise switching was faster at 100 ms/read.The aggregate crossover was 12.78 ms/read; full speculation used 1.95 and 5.36 times as much compilation CPU at 1 and 10 ms/read, respectively, and the crossing is specific to the frozen compiler and traces.Source: §C.1 · p. 11
C.2. Development replay
- 72/72 inherited controller tasks remained correct; the J = 8 replay reduced fallback candidates by 62.20%, model steps by 62.02%, and saved 98 physical reads.This replay was developmental; the frozen independent split is the primary evidence.Source: §C.2 · p. 11