TL;DR
NSAI-FUZZ is the first unified fuzzing framework designed specifically for Neuro-Symbolic AI (NSAI), bridging the gap between neural perception and symbolic reasoning. By using adaptive, semantics-aware guidance signals, it discovers over 2.5x more unique failures than traditional neural fuzzers while maintaining superior computational efficiency.
What Problem Does This Paper Address?
Neuro-Symbolic AI (NSAI) is a powerful hybrid: it uses neural networks for perception (e.g., identifying digits in an image) and symbolic logic for reasoning (e.g., solving a Sudoku puzzle based on those digits). However, this combination creates a "sharp reliability boundary." A tiny, imperceptible change in an input image might cause a neural module to flip a grounded symbol, leading to a catastrophic reasoning failure downstream.
Testing these systems is notoriously difficult. Traditional "neural fuzzers" focus on maximizing neuron coverage or exploring representation space, which often fails to capture high-level reasoning risks like symbolic constraint violations. Furthermore, NSAI systems are heterogeneous—there is no common interface to test a Sudoku solver and a visual question-answering system using the same tool.
Methods
The authors introduce NSAI-FUZZ, a framework that decouples what to mutate from how to search. It uses a common adapter to map various NSAI internal states into five unified, rank-normalized "risk signals":
- Boundary Pressure: How close is the model to making a different discrete decision?
- Grounding Uncertainty: How unstable is the neural-to-symbolic interface?
- Representation Drift: How much has the internal latent state changed?
- Constraint Violation: Does the current state break any symbolic rules (e.g., Sudoku constraints)?
- Archive Novelty: Is this a state the fuzzer hasn't seen before?
To handle the fact that different signals matter more for different tasks, the paper proposes two adaptive weighting mechanisms:
- Reliability-Calibrated Weighting (RCW): Learns static signal weights for a specific model/dataset pair based on initial calibration runs.
- Contextual Signal Gating (CSG): Dynamically adjusts weights during the search process based on the current pool of candidates.
Datasets
The framework was evaluated across nine "dataset-model cells" involving four distinct reasoning tasks:
- Sort-of-CLEVR: Relational Visual Question Answering (VQA).
- Visual Sudoku: Solving 9x9 puzzles rendered from digit images.
- HWF-7: Solving handwritten arithmetic expressions.
- ReaSCAN: Compositional visual grounding and navigation.
The study tested four representative NSAI architectures: ISED, DOLPHIN, NASR, and NeSyCoCo.
Key Insights and Ideas
- Neural Coverage is a Poor Proxy for Reasoning: Traditional fuzzing metrics like neuron coverage are surprisingly weak at finding the "discontinuous" failures typical of NSAI systems. Guidance designed around the neural-symbolic interface is far more effective.
- Signal Importance is Heterogeneous: There is no "silver bullet" signal. While Boundary Pressure is often the strongest single signal, Grounding Uncertainty or Representation Drift can be more critical depending on the specific model and task. This justifies the need for adaptive weighting.
- Efficiency without Sacrifice: Adaptive guidance doesn't just find more failures; it finds them faster. Because the "heavy lifting" is in signal extraction (which baselines also do), the overhead of adaptive weighting (RCW/CSG) is negligible, leading to much higher failure throughput per second of wall-clock time.
Key Results
- Superior Failure Discovery: RCW and CSG achieved 16.17% and 16.06% aggregate failure discovery rates, respectively, compared to just 6.06% for the strongest neural-fuzzing baseline (TensorFuzz).
- Better Diversity: After deduplicating similar failures, NSAI-FUZZ retained roughly 2x more unique failure clusters than baselines, proving it explores the failure space more thoroughly.
- Wall-Clock Performance: TensorFuzz required 1.11x the runtime of RCW while delivering only 0.45x its failure throughput.
- Qualitative Impact: As shown in Figure 2, different search policies lead the fuzzer into entirely different regions of the valid mutation space, with adaptive policies successfully finding "pockets" of failure that random search misses.
Limitations and Future Work
- Grey-Box Requirements: The framework requires "grey-box" access to output scores and some intermediate representations, which might not always be available in proprietary or highly encapsulated systems.
- Semantic Oracles: The fuzzer relies on task-specific mutators and oracles that guarantee the "correct" answer shouldn't change. Creating these for highly open-ended or subjective tasks remains a challenge.
- Future Directions: The authors suggest extending this unified interface to even more complex reasoning chains and exploring how these discovered failures can be used for automated model repair or "adversarial fine-tuning" specifically for neuro-symbolic robustness.
Summary updated