> For the complete documentation index, see [llms.txt](https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/back-matter/glossary.md). # Glossary Technical terms used in this book, with cross-references to the sections where each is first defined or used in depth. *** **Action Schema** — A parameterized template for an action in a planning domain. When variables are bound to specific objects, it becomes a *ground action*. Defined formally in Section 3.1. **Add Effects** — The set of fluents that become true after an action executes. Part of the STRIPS action model. See Section 3.1. **Affordance** — In robotics, the set of actions that a robot can physically perform in its current state and environment. SayCan (Section 2.2) combines LLM semantic knowledge with learned affordance functions. **AlphaProof** — DeepMind's neuro-symbolic system for formal mathematical theorem proving, combining neural MCTS with the Lean 4 formal proof assistant. Achieved silver-medal-equivalent performance at IMO 2024. Described in Sections 2.2 and 4.3.1. *A Search*\* — A best-first search algorithm that uses a heuristic function $h(s)$ to estimate distance-to-goal. Guaranteed to find optimal solutions when the heuristic is admissible. Central to classical planning; see Section 3.2. **Autoformalization** — The task of automatically translating informal mathematical statements (natural language or LaTeX) into formal proof assistant languages (Lean 4, Coq, Isabelle). A key bottleneck in scaling neural theorem proving. See Section 4.2.2. **Axiom (Planning)** — A derived predicate defined by Horn clauses in a PDDL domain. Allows implicit facts to be derived from explicit ones at planning time. **Backward Chaining** — A proof search strategy that works backward from the goal, asking "what premises would justify this conclusion?" Used in Prolog and in end-to-end differentiable proving (Section 4.2.1). **Belief State** — In POMDP planning, a probability distribution over the possible current states of the world. Updated via Bayes' rule after each observation. See Section 3.3. **Blocksworld** — A classic AI planning benchmark domain in which a robotic arm manipulates stacks of blocks. Used in STRIPS (1971) and still used in modern planning benchmarks. See Sections 3.1 and 4.2. **Bounded-Length Planning** — The problem of determining whether a plan of length ≤ k exists. NP-complete (see Section 3.2). **CASPER** — Continuous Activity Scheduling Planning Execution and Replanning. NASA's AI scheduler for the Earth Observing One satellite, demonstrating reactive replanning. See Section 2.1. **CBF (Control Barrier Function)** — A Lyapunov-like function used in safe control to provide formal invariance guarantees: if the system state is initialized within a safe set, a CBF-based controller guarantees it remains there. Used in safe robot control (Section 4.1.1). **CBM (Concept Bottleneck Model)** — A neural network architecture that first predicts a set of human-interpretable symbolic concepts from input features, then predicts the final label from those concepts. Provides interpretability and supports expert intervention at the concept layer. See Section 4.1.1. **Causal NeSy (Neuro-Symbolic Causal Reasoning)** — A class of neuro-symbolic architectures that combine neural network components (for learning causal mechanisms from data) with symbolic causal graphical models (Structural Causal Models, directed acyclic graphs) to enable formally correct interventional and counterfactual reasoning. Unlike purely neural systems, causal NeSy systems can answer "what if I had done X differently?" by performing do-calculus operations on the symbolic causal graph. Key systems: DECI (Geffner et al., NeurIPS 2022), CITRIS (Lippe et al., ICML 2022). See §4.3.13. **CDCL** — Conflict-Driven Clause Learning. The core algorithm in modern SAT solvers, which learns new clauses from conflicts to prune future search. Neural guidance (Section 4.2.2) can improve CDCL performance. **Chain-of-Thought Prompting** — A prompting technique that encourages LLMs to produce step-by-step reasoning traces before stating a final answer, improving performance on multi-step tasks. **Classical Planning** — Planning with deterministic actions, full observability, and a single goal that must be completely satisfied. Formally a 4-tuple $\langle F, A, I, G \rangle$. See Section 3.1. **Closed World Assumption (CWA)** — The assumption that any fluent not explicitly stated in the current state is false. Contrasted with the Open World Assumption used in knowledge graphs. Defined by Reiter (1978); see Section 3.1. **Code as Policies** — A neuro-symbolic approach that uses LLMs to generate Python programs that call robot primitive APIs, enabling hierarchical, compositional, verifiable robot behaviors. See Section 2.2. **ComplEx** — A knowledge graph embedding method using complex-valued entity and relation embeddings, capable of representing asymmetric relations. See Section 4.3.2. **Compound Task** — In HTN planning, an abstract task that must be decomposed into subtasks using methods before it can be executed. Contrasted with *primitive tasks*. See Section 3.4. **Concept Binding** — In neuro-symbolic concept learners, the learned mapping from continuous neural feature vectors to discrete symbolic concept assignments (e.g., "this feature vector → color: red"). See Section 4.1.2. **Conformant Planning** — Planning without observability, where the plan must succeed for all possible initial states. Harder than classical planning. See Section 3.3. **Constrained Decoding** — A §4.1 neuro-symbolic technique in which a formal grammar, schema, or type system constrains token-by-token generation of a language model at inference time. At each decoding step, tokens that would violate the symbolic constraint (e.g., syntactically invalid SQL, malformed JSON) are masked to −∞ logit before the softmax, enforcing that the generated sequence lies within the formal language. No gradient is required — the constraint is applied purely symbolically on the neural output distribution. Key system: PICARD (Scholak et al., EMNLP 2021). See §4.1. **Constraint Satisfaction** — The process of finding a solution that satisfies a set of hard constraints. Symbolic constraint layers enforce this at the output of neural networks. See Section 4.1.1. **Contingent Planning** — Planning with partial observability and sensing actions, producing a conditional policy rather than a linear sequence. See Section 3.3. **DeepProbLog** — A neuro-symbolic language that extends ProbLog with neural predicates whose truth probabilities are computed by neural networks. See Section 4.2.1. **Delete Effects** — The set of fluents that become false after an action executes. Part of the STRIPS action model. See Section 3.1. **Description Logic (DL)** — A family of formal knowledge representation languages, forming the theoretical basis for OWL. Supports decidable, expressive reasoning over class hierarchies and property restrictions. See Section 4.3.2. **∂ILP (Differentiable ILP)** — A differentiable approach to Inductive Logic Programming that learns Horn clause rules from examples via gradient descent over a continuous relaxation of the rule space. See Section 4.2.1. **Differentiable Abstract Interpretation (DAI)** — A fourth paradigm of neuro-symbolic AI in which the symbolic abstract domain is embedded directly into the neural architecture's representation space rather than existing as a separate external module. The canonical example is the Lattice Deduction Transformer (§4.4.1), which achieves 100% accuracy on Sudoku-Extreme with 800K parameters where frontier LLMs score 0%. **Differentiable Reasoning** — A class of neuro-symbolic approaches that implement logical reasoning as differentiable operations, enabling end-to-end training of systems that combine neural and logical components. See Section 4.2.1. **Domain File (PDDL)** — The PDDL file defining types, predicates, functions, and action schemas for a planning domain. Contrasted with the *problem file*. See Section 3.1. **Durative Action** — A PDDL 2.1 action with an explicit duration and invariant conditions (conditions that must hold throughout the action's execution). See Section 3.1. **Entity Linking** — The task of mapping a mention in text to a specific entity in a knowledge base, resolving ambiguity (e.g., "Paris" → Paris, France vs. Paris Hilton). A key step in KG construction. See Section 4.3.2. **Extended Thinking** — A class of LLM inference techniques (exemplified by OpenAI's o1/o3 models) that scale inference-time compute by generating and evaluating internal reasoning traces. Discussed in Section 1.5. **Fast Downward** — A widely used PDDL planner based on heuristic search (A\*, greedy best-first search) with powerful automated heuristic computation. See Appendix A. **Fluent** — A Boolean state variable in a planning problem. The set of all fluents $F$ defines the state space $2^{|F|}$. See Section 3.1. **Forward Chaining** — A proof/reasoning strategy that applies rules to known facts to derive new facts, working forward from premises toward the goal. **Grounding (Symbol)** — The process of connecting abstract symbols to perceptual or real-world referents. The neural-to-symbolic interface problem. See Sections 1.2, 4.1.2. **Grounding (Action)** — In planning, the instantiation of an action schema by binding all parameters to specific objects, yielding a ground action. **GraphRAG** — A retrieval-augmented generation approach that builds a knowledge graph from a document corpus and uses graph-based retrieval to answer queries requiring multi-document synthesis. See Section 4.3.2. **GreaseLM** — A neuro-symbolic language model that fuses LM and knowledge graph representations at each transformer layer. See Section 4.3.2. **HDDL** — Hierarchical Domain Definition Language. The standard input language for HTN planners, introduced at AAAI 2020. See Section 3.4. **Heuristic Function** — A function $h(s)$ estimating the distance from state $s$ to the goal. Admissible heuristics never overestimate, guaranteeing A\* optimality. Neural heuristics are discussed in Section 4.2.2. **Horn Clause** — A logical clause with at most one positive (head) literal. The basis of Prolog and many logic programming languages. ILP learns Horn clause rule sets. **HTN Planning** — Hierarchical Task Network planning. Plans by decomposing compound tasks into subtasks using methods, until all tasks are primitive. Formalized in Section 3.4. **Inductive Logic Programming (ILP)** — A machine learning approach that learns logical rules (Horn clauses) from examples. ∂ILP (Section 4.2.1) is the differentiable variant. **JEPA (Joint Embedding Predictive Architecture)** — A self-supervised learning paradigm developed by Yann LeCun's group at Meta AI, in which a model predicts abstract feature representations of future or masked inputs rather than reconstructing pixels. Forms the basis of the JEPA World Model paradigm (§4.4.2) for reward-free physical planning. **JEPA World Model (JEPA-WM)** — A three-stage pipeline for physical planning: (1) V-JEPA self-supervised representation learning from unlabeled video; (2) action-conditioned world model prediction in feature space; (3) model-predictive control (CEM/MPPI) to plan action sequences. Achieves +20 percentage points in real-robot grasping without reward annotation (V-JEPA 2.1, 2026). See Section 4.4.2. **Initial State** — In classical planning, the complete description of the world at time $t\_0$. Every fluent is either true or false (by CWA). See Section 3.1. **Knowledge Graph (KG)** — A structured representation of entities and typed relations as (entity₁, relation, entity₂) triples. Supports graph-based symbolic reasoning, query answering, and ontology inference. See Section 4.3.2. **Knowledge Graph Completion (KGC)** — The task of predicting missing triples in an incomplete KG. Neural embedding methods (TransE, RotatE) are standard approaches. See Section 4.3.2. **Knowledge-Infused Learning (KIL)** — A framework for incorporating symbolic knowledge (ontologies, KGs, logical constraints) into neural learning pipelines, described in Sheth et al. (2023). See Section 1.2. **KGLM** — Knowledge Graph Language Model. A language model conditioned on a KG that can copy entities and relations from the KG during text generation. See Section 4.3.2. **Lattice Deduction Transformer (LDT)** — An 800K-parameter recurrent transformer implementing Differentiable Abstract Interpretation. Trained on solution samples, it learns to approximate the optimal deduction operator on a formal lattice, achieving 100% accuracy on Sudoku-Extreme (where frontier LLMs score 0%) while remaining empirically sound — returning a correct answer or abstaining, never an incorrect one. See Section 4.4.1. **Lean 4** — A dependently typed functional programming language and interactive theorem prover. Its type checker is a sound, decidable formal verifier. Used in AlphaProof. See Sections 2.2, 4.2.2, 4.3.1. **LLM-Modulo** — Kambhampati's framework for using LLMs as proposal generators within a formal verification loop: LLM proposes, symbolic critic verifies. See Section 1.3. **LLM+P** — A neuro-symbolic system that uses an LLM to translate natural language task descriptions into PDDL, then solves with a classical planner. See Section 2.2. **Logic Tensor Networks (LTNs)** — A differentiable reasoning framework that grounds FOL symbols and quantifiers in a continuous, differentiable space. See Section 4.2.1. **Makespan** — The total time to complete a plan (from start of first action to end of last). A common optimization objective in temporal planning. **Markov Logic Network (MLN)** — A probabilistic first-order knowledge representation that combines Markov networks with first-order logic. Each formula is assigned a weight; the resulting joint distribution over possible worlds softens hard logical constraints into probabilistic tendencies. A foundational neuro-symbolic probabilistic reasoning framework. **MAPGEN** — Mixed-Initiative Activity Planning Generator. NASA's AI planning system for Mars Exploration Rover scheduling. See Section 2.1. **MCTS (Monte Carlo Tree Search)** — A tree search algorithm that uses random rollouts to estimate node values. Combined with neural policy and value networks in AlphaGo, AlphaZero, AlphaProof. See Section 4.2.2. **Method (HTN)** — A rule specifying how a compound task can be decomposed into a subtask network. HTN planning proceeds by method selection and application. See Section 3.4. **MDP** — Markov Decision Process. A stochastic planning model with full observability: $\langle S, A, T, R, \gamma \rangle$. See Section 3.3. **Neural Algorithmic Reasoning (NAR)** — A §4.2 paradigm in which graph neural networks are trained to execute classical symbolic algorithms (BFS, Dijkstra, sorting, dynamic programming) using the algorithm's intermediate states as step-level supervision. The symbolic algorithm's data-flow structure acts as a training scaffold that enforces procedural correctness and enables systematic generalization to unseen graph sizes. Evaluated on the CLRS Algorithmic Reasoning Benchmark (Veličković et al., ICML 2022). See §4.2.2. **Neural Heuristic** — A neural network trained to predict heuristic values for guiding a symbolic planner's search. STRIPS-HGN is the canonical example. See Section 4.2.2. **Neural Network Formal Verification** — A §4.1 technique in which a symbolic formal prover (SMT solver, abstract interpreter, or bound propagation algorithm) certifies that a trained neural network satisfies a formal specification (e.g., ε-adversarial robustness, output range constraints) across an infinite set of inputs. The verification problem is NP-complete for piecewise-linear networks. Key systems: Reluplex / Marabou (Katz et al.), α,β-CROWN (Wang et al.). See §4.1.4. **Neural Predicate** — In DeepProbLog, a predicate whose truth probability is computed by a neural network. Enables integration of neural perception into probabilistic logic programming. See Section 4.2.1. **Neuro-Symbolic AI** — A class of AI architectures that tightly integrate neural network components (for perception, approximation, and generation) with symbolic reasoning components (for correctness, constraint satisfaction, and explainability). The subject of this book. **NeuroSAT** — A graph neural network trained to predict SAT instance satisfiability and provide warm-starts for DPLL/CDCL solvers. See Section 4.2.2. **NS-CL** — Neuro-Symbolic Concept Learner. An architecture combining neural perception with symbolic concept binding and reasoning for visual question answering. See Section 4.1.2. **Open World Assumption (OWA)** — The assumption that absence of a known fact does not imply its falsity — it implies unknown. Used in KGs; contrasted with the Closed World Assumption in planning. See Section 4.3.2. **Oversubscription Planning (OSP)** — Planning when not all goals can be achieved; goals have utilities and a budget constrains plan cost. NP-hard. See Section 3.3. **OWL** — Web Ontology Language. A formal language for defining ontologies over RDF, supporting Description Logic inference. Used in medical KGs, ontology-based reasoning. See Section 4.3.2. **PDDL** — Planning Domain Definition Language. The standard input format for classical AI planners, separating domain and problem specifications. See Section 3.1. **Physics-Informed Neural Networks (PINNs)** — Neural networks that embed physical laws (PDEs) directly in the training loss, enforcing physical consistency from limited data. See Section 4.1.1. **Plan Repair** — The modification of an existing plan to restore validity after unexpected events, rather than full replanning from scratch. Used in CASPER (Section 2.1) and modern agents. **PLOI** — Planning with Learned Object Importance. A neuro-symbolic system that uses a neural classifier to identify relevant objects, reducing planning problem size. See Section 4.3.4. **PlanBench** — A benchmark for evaluating LLM planning capabilities, showing that LLMs fail at even simple planning tasks. Described in Section 1.1. **POMDP** — Partially Observable Markov Decision Process. A stochastic planning model with partial observability, requiring belief-state planning. See Section 3.3. **Preconditions** — The set of fluents that must hold in the current state for an action to be applicable. Part of the STRIPS action model. See Section 3.1. **Primitive Task** — In HTN planning, a task that directly corresponds to an executable action (with preconditions and effects). Contrasted with *compound tasks*. See Section 3.4. **Process Reward Model (PRM)** — A symbolic oracle trained on human step-level annotations that assigns correctness labels to individual reasoning steps in a chain-of-thought, rather than only to the final answer. PRMs are used during beam search to steer neural generation toward chains with valid intermediate steps, significantly improving performance on mathematical reasoning benchmarks. Distinguished from Outcome Reward Models (ORMs) which verify only final answers. Key reference: Lightman et al. (NeurIPS 2024). See §4.3.14. **RAP** — Reasoning via Planning. A neuro-symbolic approach that uses an LLM both as a world model and as an action proposer within MCTS. See Section 2.2. **RDF** — Resource Description Framework. A W3C standard for representing knowledge as subject–predicate–object triples, each entity identified by a URI. The data model underlying knowledge graphs. See Section 4.3.2. **ReAct** — Reason + Act. A neuro-symbolic agent pattern that interleaves LLM reasoning traces (Thought) with tool calls (Action) and observations (Obs). See Section 2.3. **Remote Agent** — NASA's autonomous planning system for Deep Space One (1998–1999), demonstrating autonomous spacecraft control for the first time. See Section 2.1. **RotatE** — A knowledge graph embedding method representing relations as rotations in complex space, handling symmetric, antisymmetric, and transitive relations. See Section 4.3.2. **SayCan** — A neuro-symbolic robot planning system combining LLM semantic scoring with learned affordance functions for grounded instruction following. See Section 2.2. **Scene Graph** — A structured representation of a visual scene as a graph of objects (nodes) and spatial/semantic relations (edges). The output of neuro-symbolic concept learners; the input to symbolic reasoning engines. See Section 4.1.2. **Self-Taught Reasoner (STaR)** — A §4.1 self-improvement pattern in which a language model generates reasoning chains, a symbolic answer-correctness oracle filters correct chains, and the model is fine-tuned on the filtered chains. The symbolic oracle (ground-truth label comparison) prevents error amplification and enables bootstrapped improvement of reasoning ability from a small seed of labeled examples. Generalized in PRMs (step-level oracle) and AlphaProof (formal proof checker as oracle). Key reference: Zelikman et al. (NeurIPS 2022). See §4.1. **Semantic Loss** — A loss function that embeds logical constraints into neural training, penalizing outputs that violate symbolic knowledge. See Section 4.1.1. **SHOP2** — Simple Hierarchical Ordered Planner 2. A widely deployed HTN planning system using top-down, total-order decomposition. See Section 3.4. **Skill Library** — In Voyager (Section 2.3), a persistent store of executable skill programs that the agent accumulates over its lifetime — a symbolic long-term procedural memory. **SPARQL** — A query language for RDF triple stores, analogous to SQL for relational databases. Supports multi-hop graph queries for structured knowledge retrieval. See Section 4.3.2. **SPIKE** — The AI scheduling system for the Hubble Space Telescope, operational since 1993. One of the longest-running AI planning deployments. See Section 2.1. **State Space** — The set of all possible world states, $2^{|F|}$ in classical planning. Exponential in the number of fluents. **STRIPS** — Stanford Research Institute Problem Solver. The original AI planning language (1971) introducing the fluent/precondition/add-effect/delete-effect action model that underlies PDDL. See Section 3.1. **Symbolic Regression** — The task of searching for a mathematical expression (formula) that best fits a dataset, in terms of both accuracy and simplicity. Unlike standard regression (which fits parameters of a fixed functional form), symbolic regression searches over the space of possible expression trees. Key systems: AI Feynman, PySR. See Section 4.2.2. **Symbol Grounding Problem** — The question of how abstract symbolic representations acquire meaning by being connected to perceptual or physical referents. Addressed architecturally by NS-CL, SayCan, and KG-LLM integration. See Section 1.2. **System 1 / System 2** — Kahneman's dual-process theory of human cognition: fast/automatic/neural vs. slow/deliberate/symbolic. Used as an architectural metaphor for neuro-symbolic AI in Section 4.3.1. **Task Network (HTN)** — An ordered or partially-ordered set of tasks that represents a plan fragment in HTN planning. Decomposed iteratively by method application until all tasks are primitive. See Section 3.4. **Toolformer** — A neuro-symbolic approach where LLMs learn to call external APIs (calculators, search engines, calendars) via self-supervised training on API call annotations. See Section 2.3. **TransE** — A knowledge graph embedding method representing relations as translations in embedding space: $\mathbf{h} + \mathbf{r} \approx \mathbf{t}$. See Section 4.3.2. **Tree of Thoughts (ToT)** — A neuro-symbolic prompting approach that structures LLM reasoning as a tree search, with the LLM evaluating the quality of each partial solution. See Section 2.2. **Unification** — In logic programming, the process of finding variable bindings that make two logical terms identical. Used in backward chaining and ILP rule application. **Value Network** — In MCTS, a neural network that estimates the win probability or goal proximity of a given state, replacing expensive random rollouts. See Section 4.2.2. **Voyager** — An open-ended Minecraft agent with LLM-driven curriculum, a persistent symbolic skill library, and iterative code generation with execution feedback. See Section 2.3. **World Model** — A learned or specified model of how actions change the state of the world: $T(s, a) \rightarrow s'$. Used in model-based planning (RAP, Guan et al.); discussed in Sections 2.2, 2.3. *** *For definitions of specific algorithms and planners (Fast Downward, LAMA, LPG, Madagascar, Pyperplan, Powerlifted/Scorpion), see Appendix A.* --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/back-matter/glossary.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.