Neurosymbolic systems combine a neural network that reads raw inputs (it turns an image of a digit into a probability for each digit) with a symbolic reasoner that turns those probabilities into the probability of a logical query, such as "these fifteen digits sum to 83,210". Today both halves are all-or-nothing. The network runs to full depth, and the reasoner runs exact weighted model counting (summing the weights of every world that satisfies the query) to completion. If time runs out first, the system returns nothing. Separately, the probabilistic inference community has built anytime reasoners, which can be stopped at any moment and still return a guaranteed lower and upper bound on the query probability, with the bounds tightening as compute grows. Machine learning has built anytime classifiers with early exits. No one has joined the two into a pipeline whose query-level bounds tighten smoothly under a single compute budget. The anytime classifiers that exist also sit on backbones whose exit placement and widths were chosen by hand.
This note proposes to build that joined pipeline and to automate its design. The perception network is a multi-exit backbone whose exits emit probability intervals for each symbol. These intervals are pushed through a compiled logic circuit to give an interval on the query. The backbone's topology is then searched to make that query interval shrink as fast as possible per unit of compute. The claim is that the search objective is the new ingredient. A backbone chosen for good average per-symbol accuracy at each exit is not the one that tightens query bounds fastest. Query bounds compound across many symbols, so they are dominated by the worst-resolved inputs rather than the average one. If this claim is false, the searched architecture will match a hand-designed early-exit backbone, and the experiments below are built to detect that outcome.
Core Claim
Two things would be new. The first is an end-to-end anytime neurosymbolic pipeline with an explicit soundness statement. The second is architecture search driven by the anytime profile of the downstream query, meaning how quickly its bound narrows as compute accumulates. The prior pieces each cover one side.
The reasoner side comes from existing anytime inference methods, which assume fixed, hand-given input probabilities:
- Anytime Inference in Probabilistic Logic Programs with Tp-Compilation compiles a logic program forward, step by step, into a compact circuit. The partial circuit yields a guaranteed lower bound on the query probability.
- From Exact to Anytime Solutions for Marginal MAP uses weighted best-first search to return bounded answers early.
The perception side comes from existing anytime networks, which output confidence scores rather than bounds and use hand-built backbones:
- Towards Anytime Classification in Early-Exit Architectures by Enforcing Conditional Monotonicity combines exits after training as a product of experts. This stops later exits from getting worse than earlier ones. It is applied to fixed backbones.
- Improving Anytime Prediction with Parallel Cascaded Networks and a Temporal-Difference Loss adds propagation delays by hand to a ResNet-18.
Existing neurosymbolic systems use exact or truncated reasoning and do not make it interruptible:
- DeepProbLog: Neural Probabilistic Logic Programming feeds neural predictions into a probabilistic logic program and runs exact inference.
- Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning keeps only the top-$k$ proofs, with $k$ fixed.
- A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference replaces exact reasoning with a learned approximation and gives up bounds entirely.
Existing architecture search differs from this proposal in what it searches and what it optimizes:
- Anytime Neural Architecture Search on Tabular Data (ATLAS) makes the search process interruptible, but the model it finds is static.
- VINNAS: Variational Inference-based Neural Network Architecture Search uses variational inference as the search engine and also returns a static classifier.
This proposal reuses ATLAS's two-phase search: a cheap screen of many candidates, then successive halving (repeatedly giving more training budget to the better half of survivors). It changes what is being optimized.
Research Program
Interval-emitting exits. Each exit $e$ of the backbone produces, for each symbol, an interval that should contain the probability the full-depth network would assign. The intervals are calibrated on held-out data so that each one covers its target with probability at least $1-\delta$. The target is deliberately the full model's own answer, not the ground truth. The pipeline's anytime output is then an approximation, with known coverage, of what the complete pipeline would eventually say. This is a claim we can actually guarantee.
Interval propagation through the circuit. The logic program is compiled into a circuit with two properties. It is decomposable, meaning the factors of each product share no variables. It is deterministic, meaning the branches of each sum never both hold. Weighted model counting over such a circuit is multilinear in the symbol probabilities, so a single bottom-up pass gives sound outer bounds. At each product node, take the product of child minima and of child maxima, which is valid because all terms are nonnegative. At each sum node, take the sum of child minima and of child maxima. The pass is loose wherever a variable appears as $x$ in one branch and $1-x$ in another, and part of the study is measuring that looseness.
When the circuit itself is too large to compile, as with visual Sudoku, the Tp-compilation lower bound from the partial circuit is intersected with the propagated interval. By a union bound over symbols, the resulting query interval $[L_t, U_t]$ contains the full pipeline's answer with probability at least $1-n\delta$, where $n$ is the number of symbols.
Search objective. For a candidate architecture $a$, let $W_a(c)$ be the mean query-interval width $U_t - L_t$ at compute budget $c$ in floating-point operations. The search minimizes the area under this curve, normalized by the maximum budget $C$:
$$J(a) = \frac{1}{C}\int_0^{C} W_a(c)\,dc.$$
Candidates violating a coverage floor are rejected. The search space covers where the exits sit, stage widths and depths, head widths, and optional connections that let each exit read from the previous one.
The search runs ATLAS-style. A cheap training proxy screens many candidates, then successive halving uses $J$ computed through the actual reasoner. A matched control runs the identical search but scores candidates by mean per-exit symbol accuracy. This control isolates the central claim.
Baselines
The naive reference is the non-anytime pipeline: a full-depth backbone feeding exact reasoning, in the style of DeepProbLog. Before completion it returns the trivial interval $[0,1]$, so its curve $W(c)$ equals 1 until it finishes, or forever if it times out. The file reports that DeepProbLog times out beyond four-digit addition and that exact compilation fails within four hours on $9\times 9$ Sudoku.
The strongest existing competitor is a hand-designed anytime pipeline. We take a standard ResNet with evenly spaced exits, combined by Product Anytime from the conditional-monotonicity paper, or alternatively the cascaded temporal-difference ResNet. Its outputs go through our same interval calibration and circuit propagation. It is the real threat because it already delivers per-symbol anytime behavior without any search. The comparison is fair because both share the reasoner, the calibration data, the training recipe, and the parameter and floating-point budgets. We also give the hand-designed model a tuning budget of GPU hours equal to our search cost, which it spends on hyperparameters.
No reported result was found on Lacuna for query-level anytime bound width on multi-digit MNIST addition, visual Sudoku, or VQAR (multi-hop visual question answering over images and a commonsense knowledge base). For the conditional-monotonicity paper, the file reports near-zero drops in ground-truth probability across exits on CIFAR and ImageNet, without a figure we can quote.
The ablation is the same search scored by per-exit accuracy. A cheap-search baseline is a small grid over exit placement and a single width multiplier, given the same GPU hours.
Beating the strongest competitor means three things at once. The searched model must reduce $J$ by a margin larger than the spread across five seeds. It must keep empirical coverage at or above the target. It must not lose final-exit accuracy. Beating the ablation specifically is what supports the core claim.
Why not just…?
Why not just attach Product Anytime exits to a standard ResNet? This is the most serious alternative, and it is the strongest baseline above. Its designers chose exits for per-image quality, and its known weaknesses sit exactly where query bounds are fragile: calibration gaps at early exits and degradation on small label spaces. Those weaknesses matter here because Sudoku cells and digits have few plausible labels once context is used. If the searched backbone does not beat it on $J$, we will conclude that a hand-designed backbone suffices. The contribution would then shrink to the anytime pipeline itself.
Why not just sweep exit positions and widths by hand? For a single task this may well be enough. The grid baseline gets the same compute so the question is settled empirically. The search pays off only if the best designs are irregular, for example uneven exit spacing or connections between exits, in ways a coarse grid misses. That irregularity is the motivation behind Overcoming the Manual Architecture Design Bottleneck, and it echoes the finding in ANCRe: Adaptive Neural Connection Reassignment for Efficient Depth Scaling that default residual wiring leaves deep layers underused.
Why not just use an approximate neural reasoner like A-NeSI? A-NeSI scales to 15-digit addition, far past exact methods, and may well win on raw accuracy at a given budget. It cannot state any interval containing the full pipeline's answer. We report its accuracy against compute alongside ours. Where it wins on accuracy, that tells users how much the bound guarantee costs.
Why not just use Scallop's top-$k$ proofs? A fixed $k$ gives one operating point rather than a curve that keeps improving with time, and its error is not bounded. We sweep $k$ to trace a curve for comparison. On VQAR we check whether our pipeline at full budget stays near Scallop's reported 84.22% accuracy.
Proposed Experiments
The primary benchmark is multi-digit MNIST addition at $N=4$ and $N=15$ digits. At $N=15$, width compounding across many symbols should make the query-level and per-exit objectives diverge most. Visual Sudoku ($9\times 9$) stresses the partial-circuit lower bound. VQAR tests whether the gains transfer to scene perception and multi-hop reasoning.
Metrics are:
- $J$, the area under the width-versus-compute curve;
- empirical coverage of the full pipeline's answer at each budget;
- decision accuracy at fixed budgets, predicting from the interval's midpoint or from $L_t > 0.5$;
- the rate of query-level monotonicity violations, where the interval widens as compute grows.
The decisive check is the comparison between searched-by-$J$ and searched-by-accuracy architectures at $N=15$. If their $J$ curves overlap across seeds, the core claim is wrong. A second check separates two sources of looseness: interval calibration and circuit propagation. It compares propagated intervals against exact extrema of the multilinear function over the box of symbol intervals, which is feasible on small $N$ by evaluating the corners. This tells us whether search effort or a tighter propagation rule is the better investment.
References
- Anytime Inference in Probabilistic Logic Programs with Tp-Compilation
- From Exact to Anytime Solutions for Marginal MAP
- Towards Anytime Classification in Early-Exit Architectures by Enforcing Conditional Monotonicity
- Improving Anytime Prediction with Parallel Cascaded Networks and a Temporal-Difference Loss
- DeepProbLog: Neural Probabilistic Logic Programming
- Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning
- A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference
- Anytime Neural Architecture Search on Tabular Data
- VINNAS: Variational Inference-based Neural Network Architecture Search
- ANCRe: Adaptive Neural Connection Reassignment for Efficient Depth Scaling