Research map / Label-efficient and robust learning / Recognition and long-tail
Verification Learning: Make Unsupervised Neuro-Symbolic System Feasible
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Verification Learning, a label-free neuro-symbolic paradigm that replaces label-based reasoning with verifying unlabeled predicted symbol sequences against a rule-verification function, using dynamic combinatorial sorting and distribution alignment.
Problem
Neuro-symbolic learning relies heavily on labeled data; without labels, the symbol solution space grows, shortcuts multiply, and existing NeSy methods become infeasible.
Approach
Formalize unsupervised NeSy as a constraint optimization problem solved by verifying candidate symbol assignments in descending score order (Dynamic Combinatorial Sorting with a heap), plus a prior-based distribution alignment to curb shortcuts; theory based on symmetry groups of the verification function.
Key results
- VL with independent score reaches 100% symbol recognition accuracy on the addition task for base 2 while DeepProbLog, DeepStochLog, NeurASP, Ground ABL and A3BL drop to roughly 20-55% on the same settings.
- On the Sort task with length 4-8, VL (non-independent with TTC) reaches 99.25-99.90% accuracy versus at most 97.28% for the best baseline (A3BL at length 8) and often much lower for baselines.
- On Addition, VL's runtime is roughly 80-120 seconds across settings, compared with thousands of seconds for DeepProbLog and NeurASP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use verification learning instead of the strongest reported baseline | VL_notperp TTC vs DeepProblog · Addition (10) | symbol recognition accuracy: 21.47 -> 51.40 | Helped |
| use verification learning instead of the strongest reported baseline | VL_notperp TTC vs DeepProblog · Sort (8) | symbol recognition accuracy: 45.97 -> 99.90 | Helped |
| use verification learning instead of the strongest reported baseline | VL_notperp TTC vs DeepStochlog · Match (10) | symbol recognition accuracy | Helped |
| use verification learning instead of Ground ABL | VL_perp · Chess (6) | symbol recognition accuracy: 33.95 -> 95.15 | Helped |
| add test-time correction to VL_notperp (ablation) | VL_notperp · Addition | symbol recognition accuracy: 48.80 -> 51.40 | Mixed |
| add test-time correction to VL_notperp (ablation) | VL_notperp · Sort | symbol recognition accuracy: 98.71 -> 99.90 | Helped |
| add test-time correction to VL_notperp (ablation) | VL_notperp · Match | symbol recognition accuracy: 97.08 -> 99.68 | Mixed |
| add test-time correction to VL_perp (ablation) | VL_perp · Chess | symbol recognition accuracy: 95.15 -> 92.55 | Hurt |
| use non-independent consistency-and-confidence score instead of independent confidence score (ablation) | VL · Addition | symbol recognition accuracy: 98.28 -> 48.80 | Mixed |
| use non-independent consistency-and-confidence score instead of independent confidence score (ablation) | VL · Sort | symbol recognition accuracy: 98.23 -> 98.71 | Mixed |
| use non-independent consistency-and-confidence score instead of independent confidence score (ablation) | VL · Chess | symbol recognition accuracy: 95.15 -> 95.15 | No clear effect |
Surprising findings
- Baselines adapted to unsupervised settings (using True/False verification as labels) often perform near chance, and NeurASP and DeepStochLog hit timeouts or memory limits.
- Theory argues that tasks like Sudoku have an inherent 100% upper-bound task error without distribution priors, since all symbol permutations satisfy the rules.
Limitations
- Experiments are limited to four toy-scale symbol recognition tasks using LeNet on MNIST-style digits.
- Monotonicity/independence assumptions are needed for the sub-exponential guarantee; without monotonicity, only sampling-based approximations are possible.
- Baselines were adapted by using True/False verification labels, which may not reflect their intended use.
Experimental setup
Datasets: handwritten digit addition (MNIST-based, extended from DeepProbLog) sort (extended from DeepProbLog) match (extended from DeepStochLog anbncn) chess (8-Queens-based)
Benchmarks: Addition Sort Match Chess
Metrics: symbol recognition accuracy time consumption (seconds)
Baselines: DeepProbLog DeepStochLog NeurASP Ground ABL A3BL
Builds on: DeepProbLog DeepStochLog NeurASP abductive learning A3BL
Closest papers by meaning
- A learnability analysis on neuro-symbolic learning (NeurIPS 2025 · similarity 0.89)
- Concise and Logically Consistent Conformal Sets for Neuro-Symbolic Concept-Based Models (NeurIPS 2026 · similarity 0.88)
- Right for the Right Reasons: Avoiding Reasoning Shortcuts via Prototypical Neurosymbolic AI (NeurIPS 2025 · similarity 0.87)
- Deciphering Raw Data in Neuro-Symbolic Learning with Provable Guarantees (AAAI 2024 · similarity 0.87)
- Learning Better Representations From Less Data For Propositional Satisfiability (NeurIPS 2024 · similarity 0.87)
- Training Verification-Friendly Neural Networks via Neuron Behavior Consistency (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.