Research map / Learning theory and algorithms / Combinatorial and search optimization
Abductive Reasoning in Logical Credal Networks
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.
Defines MAP and Marginal MAP tasks for Logical Credal Networks (maximin/maximax) and proposes exact search (DFS, LDS, SA) and approximate schemes (message-passing AMAP, approximate LDS/SA) that scale to larger LCNs.
Problem
Abductive reasoning (MAP and Marginal MAP inference) in Logical Credal Networks, which encode sets of probability distributions over interpretations and previously supported only marginal inference.
Approach
Formally defines maximin and maximax MAP/MMAP tasks for LCNs, evaluates assignments via LCN marginal inference (exact or via an augmented-LCN approximation), and combines search strategies with a factor-graph message-passing approximation (ARIEL-based AMAP).
Key results
- Exact search methods (DFS, LDS, SA) solve only instances with up to about 8 propositions within the 2-hour limit.
- AMAP is the fastest and solves all instances across reported sizes, including factuality LCNs up to 100 atoms.
- Search-based approximate methods ALDS and ASA usually find better solutions than AMAP on size-10 LCNs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use approximate message passing (AMAP) instead of exact assignment evaluation during search | MAP/MMAP inference in LCNs · Random LCNs, MAP, n=10 | average CPU time (seconds): 12.21 vs - | Helped |
| Use approximate MAP assignment evaluation with simulated annealing | MAP inference in LCNs · Random LCNs, MAP, n=70 | instances solved: 7 vs 10 | Mixed |
| Use approximate message passing (AMAP) rather than approximate search | MMAP inference in realistic LCNs · Credit | CPU time (seconds): 204.77 -> 5.09 | Helped |
| Use approximate MAP assignment evaluations instead of exact evaluations | MMAP inference in realistic LCNs · Suicide | instances solved: - -> 5.99 | Helped |
| Continue from AMAP's assignment with limited discrepancy search or simulated annealing | MAP inference in random LCNs · Random LCNs, n=10 | number of wins | Helped |
| Increase the maximum discrepancy value δ (ablation) | ALDS(δ) · LCN instances in Figure 3 | average CPU time (seconds) | Hurt |
| Replace exact MAP evaluation with approximate MAP evaluation | DFS/LDS/SA versus AMAP/ALDS/ASA · Factuality LCNs, n=100, k=2 | instances solved: - -> 10 | Helped |
Surprising findings
- The message-passing AMAP returns only local optima, yet search refinement on top of it is needed for best quality.
Limitations
- Exact MAP evaluation requires solving NP-hard marginal inference, limiting exact search to small LCNs.
- AMAP assumes MAP propositions are independent and can converge to local optima.
Experimental setup
Datasets: random LCNs (polytree, dag, random graph) realistic LCNs derived from Bayesian networks factuality LCNs built from LLM outputs and NLI classifier scores
Benchmarks: random LCNs realistic Bayesian-network-derived LCNs factuality LCNs
Metrics: CPU time number of instances solved solution quality (wins)
Baselines: DFS LDS SA AMAP ALDS ASA
Builds on: Logical Credal Networks ARIEL message passing marginal MAP for credal networks limited discrepancy search simulated annealing
Closest papers by meaning
- Decomposing Constraint Networks for Calculating c-Representations (AAAI 2024 · similarity 0.87)
- Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Trace (NeurIPS 2026 · similarity 0.84)
- Boosting Inference with Guided Reasoning: Stochastic Exploration for Recursive Models (NeurIPS 2026 · similarity 0.83)
- Topology of Reasoning: Understanding Large Reasoning Models through Reasoning Graph Properties (NeurIPS 2025 · similarity 0.83)
- LogicCat: A Chain-of-Thought Text-to-SQL Benchmark for Complex Reasoning (AAAI 2026 · similarity 0.83)
- Pause and Reflect: Conformal Aggregation for Chain-of-Thought Reasoning (NeurIPS 2026 · similarity 0.83)
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.