Suppose you want to steer a large network, such as a gene regulatory circuit or a power grid, by attaching control inputs to some of its nodes. There is a classical, purely graph-based test for whether a chosen set of inputs can in principle drive the whole system: every node must be reachable from some input, and the nodes must be coverable by disjoint directed paths and cycles. A system that passes is called structurally controllable. The test only works if you know the wiring diagram. In practice you usually hold a probabilistic guess about which edges exist, and each edge can be confirmed only by an experiment whose price varies widely, from cheap literature lookups to costly knockouts. This note asks when it is worth paying to confirm an edge, and which edges to confirm, so that the total cost of experiments plus actuators is as small as possible while the final design still carries a hard controllability guarantee on the true network.
The proposal rests on one structural fact. Adding edges can never destroy this kind of controllability, because both reachability and the size of the best path-and-cycle cover can only grow as edges are added. So a guaranteed design is always available at zero experimental cost: treat every unconfirmed edge as absent and place actuators on what remains. Each experiment is therefore a bet that confirming edges will let you buy fewer or cheaper actuators. The difficulty is that these bets usually pay off only in combinations. A single confirmed edge typically saves nothing, while a whole chain of them saves an actuator. Greedy information-per-cost rules score such a chain as worthless. We propose a planner that reasons over bundles of edges, orders the tests inside each bundle, and stops early when a test fails.
Core Claim
We make three claims. First, in the monotone setting, the best certified decision at any moment is fixed: it is the minimum-cost actuator placement on the graph of confirmed edges, computable in polynomial time. The design problem therefore reduces entirely to choosing which experiments to buy. Second, myopic value-of-information rules are provably stuck at zero on a broad class of instances. These are the instances where every cost saving requires two or more uncertain edges to be present together, which happens routinely because matching improvements travel along alternating paths. Third, a planner that proposes candidate edge bundles with a cost-weighted matching and evaluates each one as a sequential test of a conjunction will get close to the optimal adaptive policy at a fraction of its compute. It will also beat both "reconstruct everything, then design" and "confirm nothing." The evaluation is a regime map showing where each alternative wins.
Setting and Relation to Prior Work
The actuator side comes from the structured-systems literature. A Structured Systems Approach for Optimal Actuator-Sensor Placement in Linear Time-Invariant Systems computes the minimum number of dedicated inputs on a known digraph from a maximum bipartite matching and a count of source strongly connected components. Minimum Cost Input/Output Design for Large Scale Linear Structural Systems extends this to heterogeneous actuator costs through a minimum-weight matching solved by the Hungarian algorithm. On a 7-state example it shows that the global minimum-cost design (cost 30) can beat the minimum-actuator design (cost 60) by adding one actuator. Minimum input selection for structural controllability handles states that may not receive inputs. We reuse these solvers as the inner oracle. All three assume the graph is fully known, and that assumption is exactly what we remove. We also restrict ourselves to the weak, generic notion of controllability. Minimizing Inputs for Strong Structural Controllability shows the strong version is NP-hard to minimize, and the strong version also lacks the monotonicity the method depends on. That constrains the scope rather than being ignored.
The experiment side motivates the gap. Active Learning based Structural Inference queries agents in directed dynamical systems of up to 1,505 nodes to reconstruct the wiring. Its query rule is greedy, it charges every query the same, and it targets reconstruction accuracy. Validation of gene regulatory network inference based on controllability shows that more accurate reconstructions do not reliably yield better control. That is direct evidence that reconstruction is the wrong target when control is the goal. Cost-Optimal Learning of Causal Graphs prices interventions heterogeneously and solves the problem through weighted colorings. Its guarantees need acyclic graphs with chordal skeletons, whereas the networks we care about have feedback cycles, and those cycles are exactly what let nodes be covered without inputs.
The planning side supplies the method and the cautionary results. A Nonmyopic Approach to Cost-Constrained Bayesian Optimization shows that expected-improvement-per-cost falls into cheap traps and repairs this with budget-aware rollouts. BINOCULARS for efficient, nonmyopic sequential experimental design approximates lookahead by optimizing a batch and executing its first element, and reports speedups of 10x to 100x over rollout. Constrained Bayesian Experimental Design via Online Planning plans under costs and budgets with differentiable scenario trees. All of these operate on continuous design spaces or scalar information objectives. Our design space is discrete, and our objective is a combinatorial certificate. We borrow the "plan a batch, execute one, replan" idea from BINOCULARS, but our batch is a structured edge bundle produced by a matching rather than a gradient-optimized point set.
Research Program
The model is as follows. There is a directed state graph with three kinds of edges: confirmed present, confirmed absent, and uncertain edges $e$, each with a prior probability $p_e$ of existing and a query cost $q_e$. Each state node $i$ has an actuation cost $a_i$. We also allow node-level experiments that reveal all outgoing edges of a node at a single price, which mirrors agent-level queries in ALaSI. A policy adaptively buys queries and eventually stops, placing the cheapest certified actuator set on the confirmed graph. It minimizes
$$\mathbb{E}[J] = \mathbb{E}\Big[\sum_{e \in Q} q_e + A^\star(G_{\text{conf}})\Big],$$
where $Q$ is the random set of queried edges, $G_{\text{conf}}$ is the confirmed-present graph at stopping, and $A^\star$ is the minimum actuator cost of Pequito et al.'s formulation. Because $A^\star$ can only fall as edges are confirmed, every stopping point yields a design that is guaranteed on the true graph.
The theory work has two parts. First, we will prove the monotonicity lemma and a zero-gain lemma. The zero-gain lemma characterizes when every single-edge expected saving vanishes: every improving augmentation of the confirmed matching, and every new reachability path from an existing input, uses at least two uncertain edges. Second, we will bound the suboptimality of the bundle policy when candidate bundles are edge-disjoint. In that case the problem looks like independent sequential tests of conjunctions.
The planner works like this. At each step we build an augmented bipartite graph in which uncertain edges are usable but carry a surcharge of $q_e + \lambda(-\log p_e)$. Solving the minimum-cost design on it proposes a bundle $S$: the uncertain edges the design relies on, together with the savings $\Delta_S$ it would achieve over the current certified cost. Sweeping $\lambda$ yields a small set of bundles. For each bundle, all edges must be present for the saving to materialize, so we test them in increasing order of $q_e/(1-p_e)$, which is the classical optimal order for sequentially testing a conjunction. This puts cheap, likely-to-fail tests first, and the bundle's expected net value is
$$V(S) = \Delta_S \prod_{e\in S} p_e \;-\; \sum_{k=1}^{|S|} q_{e_{(k)}} \prod_{j<k} p_{e_{(j)}},$$
where $e_{(k)}$ is the $k$-th edge in that order. We execute the first test of the bundle with the largest positive $V$, update, and replan. When no bundle has positive value, we stop. The Hungarian step costs $O(n^3)$. We will use incremental matching updates so the method stays practical at the 1,000 to 1,500 node scale of the bacterial networks.
Baselines
The naive reference point is the no-query design: Pequito et al.'s minimum-cost placement on the confirmed edges only. It spends nothing on experiments and is always certified. Any method that fails to beat its total cost has no reason to exist.
The idealized reference point is the full-information oracle, meaning the same placement on the true graph with no query cost. It lower-bounds every policy, and we report all totals as ratios to it.
The strongest existing competitor for active discovery is reconstruct-then-design. In its first variant we run ALaSI on dynamical benchmarks where it applies. In its second, which works everywhere, we query uncertain edges in cost-weighted uncertainty order until the posterior is resolved, then run the Hungarian design. The comparison uses the same priors, the same query costs, and the same query menu, and the design is certified on confirmed edges only. The only reported numbers on Lacuna for this family are reconstruction figures, for example an unsupervised AUROC of 23.4% for ALaSI against 19.5% for PID on E. coli in Active Learning based Structural Inference. There is no reported result on Lacuna for total query-plus-actuator cost under controllability certification, so we will run this baseline ourselves.
The strongest myopic competitor is the cost-normalized one-step rule. It queries the edge or node test that maximizes expected reduction in $A^\star$ divided by query cost, which is the discrete analogue of expected-improvement-per-cost. The strongest generic non-myopic competitor is a rollout policy in the style of A Nonmyopic Approach to Cost-Constrained Bayesian Optimization. It uses the myopic rule as its base policy and the remaining budget as state, and it gets the same wall-clock budget per decision as our planner.
On small instances with up to about twelve uncertain edges, we solve the exact Bellman recursion over edge states to obtain the optimal adaptive policy. The gap to this optimum is the cleanest measure of quality.
Two ablations isolate the key ingredients. The first keeps bundle proposal but tests every edge of a bundle at once, with no ordering and no early stopping. This isolates the sequential-conjunction component. The second replaces the cost-weighted surcharge with a uniform one. This isolates cost awareness.
We will count the proposal as beating a baseline if its mean total cost ratio is lower, with non-overlapping 95% bootstrap intervals across at least 200 random instances per setting. On exact-DP instances, we want it within 5% of the optimal adaptive cost.
Why not just…?
Why not just skip experiments and design against the confirmed graph? Because of monotonicity this baseline is genuinely strong, and when query costs are high relative to actuator costs it may be optimal. We treat that as a finding rather than a threat. The experiments sweep the ratio of median query cost to median actuator cost and report where the break-even lies. The proposal only claims an advantage in the regime where confirming structure is cheaper than buying actuators, and the 7-state example in Minimum Cost Input/Output Design for Large Scale Linear Structural Systems shows that a factor-of-two swing in actuator cost from the graph structure alone is plausible.
Why not just reconstruct the network first and then place actuators? Reconstruction pays to resolve every uncertain edge, while the certificate depends on a small matching and a few reachability paths. Validation of gene regulatory network inference based on controllability found that reconstruction accuracy and control quality diverge. We expect reconstruct-then-design to spend most of its budget on edges that never enter any cheaper design. The test is the fraction of query spend that lands on edges outside the final certificate, reported alongside total cost.
Why not just use a cost-weighted greedy rule, or a generic rollout? The zero-gain lemma predicts that the greedy rule stops immediately whenever savings require edge pairs. Generic rollout can escape this only if its base policy ever proposes the right pair, which a myopic base policy will not do reliably in a combinatorial space. We will measure this directly on planted instances where every saving requires alternating paths of length 2 to 5. A rollout that matches our planner there under equal compute would undercut the bundle mechanism, and we would report that.
Proposed Experiments
For the sanity check, we reproduce the 7-state instance of Pequito et al. with known costs 60 and 30. We then hide the edges that distinguish the two designs behind uncertain priors and verify that the planner recovers the cheaper design exactly when the expected query cost is below the gap of 30.
For controlled synthetic studies, we use directed Erdős–Rényi and scale-free graphs with 50 to 1,000 nodes and many cycles. Actuator and query costs are drawn from exponential and uniform distributions, following the cost models in Cost-Optimal Learning of Causal Graphs. Edge priors are calibrated at several noise levels. We add planted-trap instances in which all savings require multi-edge alternating paths.
For realistic topologies, we use the ESC (96 nodes), S. aureus (1,084), and E. coli (1,505) regulatory networks and the Springs systems from ALaSI. The true graph serves as ground truth, and edge priors come from ALaSI's own posterior on a held-out fraction of edges, so the prior reflects a real inference method's errors. We also use the IEEE 39-bus system from Minimal input selection for robust control as a sparse engineered network.
The metrics are total cost relative to the oracle, the fraction of query spend on certificate edges, the number of actuators, and decision latency. For the optimistic baselines we also report the failure rate of any variant that designs on the most-likely graph instead of the confirmed one. This quantifies what the certification guarantee is worth.
Four checks decide the claims. The planner must come within 5% of the exact adaptive optimum on small instances. It must reduce total cost substantially relative to both no-query and reconstruct-then-design in the regime where query costs are cheaper than actuator costs. The myopic rule must stall on planted traps, as the zero-gain lemma predicts. Removing ordering and early stopping must measurably raise query spend. If the first or the fourth check fails, the bundle-and-sequential-test mechanism is not doing the work, and the idea should be reframed as a regime study of when to query at all.
References
- A structured systems approach for optimal actuator-sensor placement in linear time-invariant systems
- Minimum Cost Input/Output Design for Large Scale Linear Structural Systems
- Minimum input selection for structural controllability
- Minimizing Inputs for Strong Structural Controllability
- Active Learning based Structural Inference
- Validation of gene regulatory network inference based on controllability
- Cost-Optimal Learning of Causal Graphs
- A Nonmyopic Approach to Cost-Constrained Bayesian Optimization
- BINOCULARS for efficient, nonmyopic sequential experimental design
- Constrained Bayesian Experimental Design via Online Planning
- Minimal input selection for robust control