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

Shinobu Miya · 2025

Read Eidoku: A Neuro-Symbolic Verification Gate for LLM Reasoning via Structural Constraint Satisfaction by Shinobu Miya (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-20664.txt.

Introduction

Shinobu Miya builds a gate that rejects fluent nonsense. Language models often rate their own made-up claims as highly likely, so checking by score cannot catch them; the flaw is one of structure, not of confidence. Eidoku recasts the checking task as a constraint problem that ignores how likely a claim sounds.

Each step of reasoning is scored by what it costs to fit that step into the graph of the context around it. The score mixes how well the step links into the graph, how well it fits the feature space, and whether logic carries it. Steps whose cost passes a limit drawn from the context's own spread are refused outright. On a controlled test set, the gate turns away smooth falsehoods, claims that sound likely yet hang loose from the context, which score-based checks cannot in principle catch.

Catalog record

CREATORShinobu Miya
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-20664

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Eidoku: A Neuro-Symbolic Verification Gate for LLM Reasoning via Structural Constraint Satisfaction Shinobu Miya 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. Code Availability: A reference implementation and reproduction logs are available at https://github.com/ShinobuMiya/Eidoku . 1 Introduction Large Language Models (LLMs) have demonstrated remarkable performance in natural language generation and multi-step reasoning. However, they remain prone to producing hallucinated statements: fluent, confident outputs that are factually or logically incorrect. Crucially, such hallucinations are often assigned high likelihood by the model itself, rendering probability-based confidence measures unreliable for verification. This exposes a fundamental mismatch between generation and verification. Likelihood, attention weights, and decoding probabilities are optimized for plausibility under the model distribution, not for semantic or logical feasibility within a given context. As a result, high-probability outputs may still violate structural constraints, break transitive relations, or introduce unsupported entities, while appearing locally coherent. Most existing approaches attempt to mitigate hallucinations by refining generation strategies, incorporating external knowledge, or estimating uncertainty from probabilistic signals [ 8 ] . 1 1 1 The source code for our Optimization-Independent verification gate, Eidoku , is open-sourced at https://github.com/ShinobuMiya/Eidoku . Eidoku operates on an evaluation axis that is optimization-independent to the generation objective. While System 1 optimizes for plausibility (likelihood P_{\theta}(y|x) ), System 2 evaluates structural feasibility (score J(S) ). These two objectives are independent; a high-likelihood output can have high structural Violation Cost (low feasibility). Thus, “Independence” here refers to the independence of the optimization landscapes, not necessarily the absence of probabilistic components in the scalar definitions of Violation Cost proxies. In contrast, we argue that hallucination is better understood as a structural failure : a candidate reasoning sequence cannot be embedded into the contextual semantic structure without incurring excessive deformation. In this work, we propose to reformulate verification as an Optimization-Independent optimization problem over semantic structure. Rather than estimating how probable an output is, we evaluate how much semantic Violation Cost is required to accommodate it. Semantic Violation Cost is defined as the cost of deforming contextual structure to integrate a candidate reasoning step. Verification is then performed by minimizing accumulated Violation Cost under a calibrated critical threshold, enforcing closure of the semantic system. We instantiate this formulation as Eidoku , a lightweight System-2 verification gate that operates independently of the generation process. Eidoku evaluates candidate reasoning sequences produced by an LLM (System 1), rejects those that exceed a context-calibrated Violation Cost threshold, and selects the lowest-score accepted candidate. A minimal proof-of-concept implementation demonstrates that Eidoku can reject trivial hallucinations that remain highly probable under standard decoding. Our contributions are threefold: (1) we propose an Optimization-Independent formulation of verification based on semantic structural Violation Cost; (2) we introduce an additive score model composed of independent structural, geometric, and logical proxies; and (3) we present a context-calibrated rejection mechanism that avoids fixed or learned thresholds. Finally, we clarify our design scope: Eidoku does not attempt to model any underlying physical or semantic dynamics. Instead, it adopts a pragmatic engineering assumption: treating the verification window as an isolated evaluation context functions as a regularization mechanism. Note on Terminology: Throughout this work, we use the term Optimization-Independent to strictly denote independence of the optimization objective , distinct from statistical independence of variables. While internal components (e.g., NLI) may derive from probabilistic models, Eidoku utilizes them as scalar proxies for structural Violation Cost within a feasibility constraint ( J(S)\leq\tau_{c} ), rather than for maximizing generative plausibility ( P(S)\to\max ). Thus, “Independence” asserts that the verification axis is not aligned with the gradient of the generation likelihood. 2 Why Likelihood Is Insufficient for Structural Verification Verification is commonly treated as a problem of confidence estimation. Under this view, a model output is considered reliable if it is assigned high likelihood, low entropy, or strong attention alignment. However, this assumption conflates statistical plausibility with semantic feasibility. Likelihood reflects how well an output matches the model’s learned distribution, not whether it is structurally compatible with the given context. A language model may confidently produce a statement that is locally consistent in form yet globally incompatible with prior constraints. For example, given a context encoding a transitive relation A\rightarrow B\rightarrow C , the statement “ A is a fish” may be assigned non-negligible probability if it matches common syntactic and semantic patterns, despite having no structural support in the context. This failure mode is not incidental. Probability-based decoding optimizes for continuation plausibility, not for global consistency. Attention mechanisms, similarly, indicate relevance within the model’s internal computation but do not constitute a semantic metric. As such, neither likelihood nor attention alone provides a principled criterion for rejecting structurally unsupported reasoning steps. Importantly, hallucinations are not necessarily low-probability events. Empirically, many hallucinated statements are generated with high confidence and persist under temperature scaling or beam search. This suggests that hallucination cannot be reliably detected by thresholding probabilistic scores alone. We therefore argue that verification requires a different axis. Rather than asking how likely a statement is, verification should ask whether a statement can be embedded into the contextual semantic structure without violating its constraints. This reframes verification as a feasibility problem: does there exist a low-cost deformation of the semantic structure that accommodates the candidate? Under this view, inconsistency manifests as excessive deformation cost. A reasoning step that cannot be integrated without incurring high structural, geometric, or logical Violation Cost should be rejected, regardless of its likelihood. This perspective motivates a verification mechanism that operates outside the probabilistic generation loop and evaluates candidates based on accumulated semantic Violation Cost. The remainder of this paper develops this formulation and demonstrates its implications through a minimal System-2 verification gate. 3 Geometric Cost Formulation We formalize verification by defining a Cost-Based Formulation over the semantic structure of reasoning chains. Instead of relying on probabilistic likelihoods, we map the reasoning process onto a geometric embedding space. Eidoku instantiates this framework as follows: • The discrete vocabulary set \mathcal{V} (tokens) serves as the state space. • The embedding function \phi:\mathcal{V}\to\mathbb{R}^{d} maps discrete tokens

Read the complete text