Eidoku: A Neuro-Symbolic Verification Gate for LLM Reasoning via Structural Constraint Satisfaction

• URL: http://arxiv.org/abs/2512.20664v1
• Date: Fri, 19 Dec 2025 05:29:43 GMT
• Title: Eidoku: A Neuro-Symbolic Verification Gate for LLM Reasoning via Structural Constraint Satisfaction
• Authors: Shinobu Miya,
• Abstract summary: Large Language Models (LLMs) frequently produce hallucinated statements that are assigned high likelihood by the model itself.<n>This suggests that hallucination is often not a low-confidence phenomenon, but a failure of structural consistency.<n>We reformulate the verification of LLM reasoning as a Constraint Satisfaction Problem (CSP) operating independently of the generation likelihood.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Language Models (LLMs) frequently produce hallucinated statements that are assigned high likelihood by the model itself, exposing a fundamental limitation of probability-based verification. This suggests that hallucination is often not a low-confidence phenomenon, but a failure of structural consistency. In this work, we reformulate the verification of LLM reasoning as a Constraint Satisfaction Problem (CSP) operating independently of the generation likelihood. Rather than optimizing for statistical plausibility, we model verification as a feasibility check based on structural violation cost -- the computational cost required to embed a candidate reasoning step into the contextual graph structure. We define a total cost function composed of three proxies: (i) graph connectivity (structural), (ii) feature space consistency (geometric), and (iii) logical entailment (symbolic). Crucially, verification is performed via a lightweight System-2 gate, Eidoku, which rejects candidates exceeding a context-calibrated cost threshold. The threshold is not learned but is derived from the intrinsic statistics of the context, avoiding ad hoc heuristics. We demonstrate that this approach successfully rejects ``smooth falsehoods'' -- statements that are highly probable yet structurally disconnected -- that probability-based verifiers are principally incapable of detecting. Our experiments on a controlled diagnostic dataset show that explicitly enforcing structural constraints allows for the deterministic rejection of this specific class of hallucinations, serving as a neuro-symbolic sanity check for generative reasoning.

Related papers

• Interpretable Logical Anomaly Classification via Constraint Decomposition and Instruction Fine-Tuning [0.17722218114340835]
  We introduce Logical Anomaly Classification (LAC), a task that unifies anomaly detection and fine-grained violation classification in a single inference step.<n>To tackle LAC, we propose LogiCls, a vision-language framework that decomposes complex logical constraints into a sequence of verifiable subqueries.
  arXiv  Detail & Related papers  (2026-02-03T13:48:09Z)
• Think Locally, Explain Globally: Graph-Guided LLM Investigations via Local Reasoning and Belief Propagation [5.191980417814362]
  LLM agents excel when environments are mostly static and the needed information fits in a model's context window.<n>ReAct-style agents are especially brittle in this regime.<n>We propose EoG, a framework in which an LLM performs bounded local evidence mining and labeling (cause vs symptom) while a deterministic controller manages, state, and belief propagation to compute a minimal explanatory frontier.
  arXiv  Detail & Related papers  (2026-01-25T17:27:19Z)
• VIRO: Robust and Efficient Neuro-Symbolic Reasoning with Verification for Referring Expression Comprehension [51.76841625486355]
  Referring Expression (REC) aims to localize the image region corresponding to a natural-language query.<n>Recent neuro-symbolic REC approaches leverage large language models (LLMs) and vision-language models (VLMs) to perform compositional reasoning.<n>We introduce VIRO, a neuro-symbolic framework that embeds lightweight operator-level verifiers within reasoning steps.
  arXiv  Detail & Related papers  (2026-01-19T07:21:19Z)
• Towards Unsupervised Causal Representation Learning via Latent Additive Noise Model Causal Autoencoders [1.9732490977700972]
  Unsupervised representation learning seeks to recover latent generative factors.<n>Disentangling causal variables from observational data is impossible without supervision.<n>We propose the Latent Additive Noise Model Causal Autoencoder (LANCA) as a strong inductive bias for unsupervised discovery.
  arXiv  Detail & Related papers  (2025-12-15T10:52:30Z)
• SeSE: A Structural Information-Guided Uncertainty Quantification Framework for Hallucination Detection in LLMs [43.76748192880071]
  This paper presents a principled UQ framework that quantifies the inherent semantic uncertainty of large language models.<n>We develop an adaptively sparsified directed semantic graph construction algorithm that captures directional semantic dependencies.<n>We then exploit latent semantic structural information through hierarchical abstraction.
  arXiv  Detail & Related papers  (2025-11-20T11:54:12Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• Controllable Logical Hypothesis Generation for Abductive Reasoning in Knowledge Graphs [54.596180382762036]
  Abductive reasoning in knowledge graphs aims to generate plausible logical hypotheses from observed entities.<n>Due to a lack of controllability, a single observation may yield numerous plausible but redundant or irrelevant hypotheses.<n>We introduce the task of controllable hypothesis generation to improve the practical utility of abductive reasoning.
  arXiv  Detail & Related papers  (2025-05-27T09:36:47Z)
• FactTest: Factuality Testing in Large Language Models with Finite-Sample and Distribution-Free Guarantees [41.78390564658645]
  Large Language Models (LLMs) to generate hallucinations and non-factual content undermines their reliability in high-stakes domains. We introduce FactTest, a novel framework that statistically assesses whether a LLM can confidently provide correct answers to given questions. We show that FactTest effectively detects hallucinations and improves the model's ability to abstain from answering unknown questions, leading to an over 40% accuracy improvement.
  arXiv  Detail & Related papers  (2024-11-04T20:53:04Z)
• To Believe or Not to Believe Your LLM [51.2579827761899]
  We explore uncertainty quantification in large language models (LLMs) We derive an information-theoretic metric that allows to reliably detect when only epistemic uncertainty is large. We conduct a series of experiments which demonstrate the advantage of our formulation.
  arXiv  Detail & Related papers  (2024-06-04T17:58:18Z)
• Fact-Checking the Output of Large Language Models via Token-Level Uncertainty Quantification [116.77055746066375]
  Large language models (LLMs) are notorious for hallucinating, i.e., producing erroneous claims in their output. We propose a novel fact-checking and hallucination detection pipeline based on token-level uncertainty quantification.
  arXiv  Detail & Related papers  (2024-03-07T17:44:17Z)
• Identification of Causal Structure in the Presence of Missing Data with Additive Noise Model [24.755511829867398]
  We find that the recent advances additive noise model has the potential for learning causal structure under the existence of self-masking missingness. We propose a practical algorithm based on the above theoretical results on learning the causal skeleton and causal direction.
  arXiv  Detail & Related papers  (2023-12-19T14:44:26Z)
• Neuro-Symbolic Entropy Regularization [78.16196949641079]
  In structured prediction, the goal is to jointly predict many output variables that together encode a structured object. One approach -- entropy regularization -- posits that decision boundaries should lie in low-probability regions. We propose a loss, neuro-symbolic entropy regularization, that encourages the model to confidently predict a valid object.
  arXiv  Detail & Related papers  (2022-01-25T06:23:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.