Robot policies usually fail because two or three conditions coincide, not because of one bad condition. A grasp works under dim light and works with a shifted camera, but slips when both happen at once. Current failure analysis mostly labels individual episodes after the fact. It does not ask which combinations of conditions cause failure, and answering that by brute force means testing every pair and triple of perturbations, which quickly costs thousands of rollouts. We propose to treat this as a discrete signal recovery problem, meaning the reconstruction of an unknown vector whose entries are 0 or 1 from far fewer measurements than it has entries. Each rollout switches on a random subset of perturbations, the only outcome recorded is success or failure, and we recover the few failure-causing conjunctions from a number of rollouts that grows with how many causes there are, not with how many combinations exist.
The model of "failure as a sparse OR of ANDs" comes from biology. Transcription factors, the proteins that switch genes on, often act cooperatively: a gene turns on only when two factors are both bound (an AND gate), or when either one is present (an OR gate, which is redundancy). Loregic fits binarized expression data to all 16 two-input logic gates and shows that correlation alone cannot tell AND from OR. It also stops at two inputs because enumeration explodes. We carry that gate vocabulary over to robot failures and replace enumeration with recovery. The same machinery then gives a direct test of whether Loregic's triplet limit can be lifted.
Core Claim
Let the evaluator control $p$ binary perturbation factors, such as a lighting change, a distractor object, a camera shift, reduced friction, or action latency. Consider a dictionary of all conjunctions of up to $r$ factors, which has $N=\sum_{j\le r}\binom{p}{j}$ entries. Rollout $i$ draws a factor vector $z_i\in\{0,1\}^p$ and turns it into a row $a_i\in\{0,1\}^N$, where each entry is the product of that conjunction's factors. The outcome is
$$y_i = \mathbb{1}\left[a_i^\top x + w_i > \tfrac12\right],\qquad x\in\{0,1\}^N,\ \|x\|_0=k,$$
where $x$ marks the $k$ conjunctions that actually cause failure and $w_i$ is the rollout-to-rollout randomness of a stochastic policy.
We claim three things. First, the support of $x$ can be recovered exactly from on the order of $k\log N$ rollouts. Second, this beats exhaustive pairwise and triple testing by more than an order of magnitude at realistic $p$. Third, the binary prior matters most in the low-budget regime where continuous sparse regression mixes up an AND term with its two single-factor parents.
The theoretical starting point is Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements. That paper proves that a Top-$k$ correlation estimator, which correlates each column with the outcomes and keeps the $k$ largest, reaches the information-theoretic rate $O((k+1/\beta^2)\log n)$ for 1-bit and logistic measurements. The proof assumes Gaussian-like measurement matrices. Our dictionary is the opposite case: its columns are nested and correlated, because the column for "A and B" is contained in the column for "A". Extending that result to such dictionaries is the main technical contribution.
Research Program
The first part is design and theory. For conjunctive dictionaries, the probability $q$ that each factor is switched on controls a tradeoff. An order-$j$ term is active with probability $q^j$, so a large $q$ makes higher-order terms visible but raises the correlation between parents and children. We will derive the $q$ that minimizes the rollouts needed at each order $r$. We will then prove a recovery bound for a hierarchical estimator. This estimator first residualizes each candidate conjunction against its lower-order parents, so the parents' effect is removed from the outcomes, and then applies Top-$k$ correlation. The expected result is a $k\log N$ rate with a constant that grows like $q^{-r}$. That form follows from the variance of an indicator that fires with probability $q^r$.
The second part is estimation. The hierarchical Top-$k$ step proposes candidate conjunctions. A mixed-integer refinement then enforces integrality and a monotone OR-of-ANDs structure over the shortlisted candidates, following the integer-programming approach of Sparse recovery with integrality constraints. That paper solves $64\times256$ binary problems to optimality in seconds. It also establishes that integrality lets recovery go beyond the continuous limit of fewer than $m/2$ nonzeros, but its guarantees cover only noise-free data. Our setting is noisy by construction, so we test that gap empirically instead of assuming it closes. A Laplace-smoothed consistency score adapted from Loregic ranks the confidence of each recovered gate.
The third part is using the result. FIPER raises a failure alarm only when observation novelty and action entropy are both high. This is a single AND gate that the authors chose by hand, and it helps filter out harmless novelty. We replace that hand-chosen gate with the recovered conjunctions. The recovery loop then intervenes only when a known failure-causing combination is active.
This targets the "Correction Paradox" reported in Can VLMs Diagnose and Recover from VLA Manipulation Faults?. The paper describes it as frontier vision-language models over-intervening on runs that were actually succeeding, which lowers task success, and it finds that more conservative models do better. We do not try to fix that paper's separate finding that vision-language models get the magnitude of 3D corrections right less than 20% of the time. Our output is a trigger condition, not a correction vector.
Baselines
The naive reference is one-factor-at-a-time testing: perturb each factor alone, then extend to all pairs and triples. With repeats, it recovers every conjunction up to order $r$ at a cost of roughly $N$ times the number of repeats. It is the ground-truth procedure a practitioner would use by default. Compressed recovery beats it if it reaches the same exact-support recovery with at most 10% of its rollouts.
The strongest competitor is continuous sparse regression. This means $\ell_1$-penalized logistic regression, a continuous relaxation, on the same random designs and the same interaction features, followed by thresholding. It is the textbook answer, and it is the relaxation that tiSFM uses in its sparse prediction layer on top of pairwise motif interactions. It gets exactly the same rollouts, a regularization path tuned by cross-validation with the same compute budget as our estimator's hyperparameter search, and the same hierarchical feature construction. No reported result was found on Lacuna for this baseline on robot failure-combination recovery. We count it as beaten if our method reaches 90% exact support recovery with measurably fewer rollouts, or shows higher AND-versus-parent discrimination at a fixed budget.
A third baseline aggregates per-episode diagnoses from a vision-language model. We run AHA on each failed rollout and tally its failure-mode labels against the active factors. AHA-13B reports beating GPT-4o (5-shot) by 10.3% on failure reasoning. It therefore represents the best available per-episode diagnoser, and we give it the same rollouts.
Two ablations isolate the key ingredients. The first removes hierarchical residualization and applies plain Top-$k$ over the flat dictionary. The second drops the integer refinement and uses Top-$k$ alone.
Why not just…?
Why not just run lasso with interaction terms? This is the real threat. On well-conditioned designs, lasso with interaction terms may match us. The evidence against it is indirect. An algebraic perspective on integer sparse recovery reports that $\ell_1$ and greedy pursuits are suboptimal for integer signals under noise, because they ignore the minimum separation between integer points. Our specific concern is that $\ell_1$ splits weight between a conjunction and its parents. The head-to-head sweep over rollout budget and $q$ settles the question. If lasso matches us everywhere, the contribution shrinks to the design analysis, and we will report it that way.
Why not just test every pair exhaustively? When $p$ is 5 or 6, one should. At $p=15$ with order-3 terms, $N=575$, and each configuration needs repeated rollouts because the policy is stochastic, so the cost reaches tens of thousands of rollouts. The budget-sweep experiment below reports where the crossover falls.
Why not just ask a VLM what went wrong? A vision-language model labels what happened in one episode. Learning that failure requires both A and B needs comparisons across episodes, which a per-episode diagnoser does not make. BEAR also reports that 54.8% of multimodal-model failures on its embodied tasks are perceptual. The AHA-aggregation baseline tests this directly.
Proposed Experiments
The planted-ground-truth regime comes first. We wrap LIBERO policies and the FIPER tasks (PushT, sorting, stacking) with fault injectors in the style of AHA's FailGen, which perturbs keyframes of successful runs to create failures. Here the injectors fire only on chosen conjunctions of 2 to 4 factors out of $p=12$ to $20$. We sweep $k$, the rollout budget, and the stochasticity of the policy. Metrics are exact support recovery, precision and recall over conjunctions, and rollouts needed to reach 90% recovery.
The decisive check uses natural failures. We take an unmodified LIBERO policy with $p=10$ factors and run all $2^{10}$ configurations with repeats to get a gold-standard failure map. We then ask whether compressed recovery with 5% of that budget identifies the same conjunctions. The theory predicts that required rollouts scale as $\log N$ when $k$ is fixed, and that scaling is itself the test.
For the downstream check, we gate rollback-and-correct interventions on VLA-FixBench tasks by the recovered conjunctions and measure the false-intervention rate and task success. The paper reports that expert human rollback-and-correct instructions raise LIBERO success by 13%, which serves as the upper reference. FIPER's reported mean timestep-wise accuracy is 0.65, and we compare against it on its own tasks.
Finally, a transfer check addresses Loregic's triplet limit. We apply the same estimator to Loregic's yeast knockout data, subsampled, and ask whether it recovers the 871 AND-consistent triplets Loregic validated from a fraction of the samples. We then search for candidate three-input gates.
References
- Loregic: A Method to Characterize the Cooperative Logic of Regulatory Factors
- Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements
- Sparse recovery with integrality constraints
- Failure Prediction at Runtime for Generative Robot Policies
- Can VLMs Diagnose and Recover from VLA Manipulation Faults?
- An intrinsically interpretable neural network architecture for sequence-to-function learning
- AHA: A Vision-Language-Model for Detecting and Reasoning Over Failures in Robotic Manipulation
- An algebraic perspective on integer sparse recovery
- BEAR: Dissecting Embodied Abilities in Multimodal Language Models through Skill-level Evaluation and Diagnosis