Adequate Losses via Quantitative Linear Logic
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Adequate Losses via Quantitative Linear Logic".
Jane: Here's the gist of the paper. Adequate Losses via Quantitative Linear Logic presents a novel logic that unifies qualitative and quantitative aspects of neural network specifications by introducing a family of calculi indexed by a hardness degree and establishing quantitative adequacy for neuro-symbolic loss functions.
Tom: The Core Logical Framework The paper introduces a logic, pQLL, which is a family of calculi indexed by a hardness degree p, proving a cut-elimination theorem for them and establishing completeness with respect to enriched residuated ‘soft’ lattices.
Jane: This logic aims to reconcile the three facets required for logical semantics based on loss functions: adequacy, completeness, and justification.
Tom: The central idea is that verification of machine learning models should be founded on a quantitative reconception of logic.
Title and authors: Tom: So we're looking at this paper called "Adequate Losses via Quantitative Linear Logic". Jane, what's the big picture here?
Jane: Well, Tom, it sounds like they are trying to get something right about how we connect the qualitative side of logic with the quantitative side of machine learning loss functions.
Tom: Exactly. I mean, we have these neural networks that are becoming so common in safety-critical systems now. The paper suggests that for those models to be safe, we need a way to check them against a specification, and this paper is proposing a new logic framework for that checking process.
Lu: They introduce something called pQLL, which is a family of calculi indexed by some hardness degree p. It’s an attempt to unify the qualitative and quantitative aspects of these specifications into one structure.
Meng: So it’s not just about saying a neural network is good or bad, it’s about making sure the actual training process leads to that good result in a provable way? That sounds like something we deal with every day when we try to deploy models.
Lalam: I see how they are trying to reconcile the three facets of logical semantics: adequacy, completeness, and justification. It seems they think our current tools just don't handle all three at once when dealing with loss functions.
The paper's summary: Jane: They summarize it by saying that we need a logic that can handle the match between what the specification says and what the optimization of our loss function actually achieves. That match is called adequacy.
Tom: Right, so if the loss value goes down, we want to be confident that the model is actually satisfying the original requirement, and this paper tries to build that bridge formally.
Lu: They propose a new logical paradigm called quantitative logic where formulae have intended meanings in real numbers but still allow us to do quantitative proofs and judgments.
Meng: Quantitative proofs? That means we can't just use simple true or false statements; we need the math behind the proof to scale with the problem size, like a big O notation.
Lalam: They introduce quantitative sequent calculi that are enriched by these algebraic structures, which they call zero infinity plus p tensor where different choices of p change how you can do addition and multiplication <ref:2605.13348#pg1>.
Tom: It’s interesting because it says that verification of machine learning models should be founded on a quantitative reconception of logic, not just standard Boolean logic.
Jane: It seems like they are trying to make the logical structure itself quantitative, so that when we look at a loss function, we can interpret it as satisfaction by some kind of model.
The paper's improvements: Lu: One big improvement they lay out is a crucial quantitative adequacy theorem. Theorem six point four states that for a differentiable logic, the loss function J q K can be interpreted as satisfaction by a model.
Tom: That’s significant because it gives us a concrete way to link the actual loss value to whether the model satisfies the specification. They show that if the loss function J q K decreases, then our logical formula p QLL increases, which is what we want for training.
Meng: So this gives us a formal justification for property-driven training because it shows that minimizing that differentiable loss actually improves satisfaction of the specification after training.
Jane: That connects the dots between optimizing the network and satisfying the original safety requirements in a mathematically sound way, which is really what we need for deployment.
Lalam: They also show how this works by defining an algebraic model called softales, which generalizes residuated lattices by enriching the order structure in the multiplicative reals.
Tom: So they've got a mechanism where every value of that loss function J q K has an interpretation in terms of satisfaction by a model, which is a strong step forward for us.
Conclusion: Tom: So to wrap up, this whole paper on "Adequate Losses via Quantitative Linear Logic" is about giving a formal logical meaning to neuro-symbolic methods by rethinking the fundamentals of calculi and proof validity in a quantitative way.
Jane: They set out to provide a formal account of why property-driven training succeeds by showing that the loss function J q K decreases as the provability in p QLL increases.
Lu: The long term goal is to give a formal account of why success in property-driven training should assist success in the latter, which means linking logical loss minimization to improving specification satisfaction after training.
Meng: From my side, what I'm hearing is that this could give us the first real way to formally justify why our model optimization process actually helps us meet the safety requirements we specified upfront.
Lalam: I think they conclude that QLL can be interpreted as a calculus of conversion rates, where provability represents a conversion rate from resources in gamma to alpha. It’s a very abstract way of saying that proof is just about how much improvement you get for the effort you put in.
Tom: It’s definitely a deep dive into the mechanics, and it gives us a solid theoretical foundation to start building systems where we can prove safety through loss minimization instead of just hoping it works.
MATTEO CAPUCCI, ROBERT ATKEY, CHARLES GRELLOIS, EKATERINA KOMENDANTSKAYA, MATTHEW DAGGITT
University of Strathclyde · University of Sheffield · Heriot-Watt University and Southampton University · University of Western Australia
cs.LO, math.LO
Submitted: 2026-05-13
Updated: 2026-11-13
Comments: Numerous tweaks and small corrections. To appear at POPL 2027
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 88/100
The gist: Adequate Losses via Quantitative Linear Logic presents a novel logic that unifies qualitative and quantitative aspects of neural network specifications by introducing a family of calculi indexed by a…
Key concepts
- pQLL
- A family of logical calculi indexed by a hardness degree 'p'. It aims to reconcile qualitative and quantitative aspects of logic, providing a rigorous foundation for verifying machine learning models by grounding them in quantitative reconception.
- Quantitative Logic
- A new logical paradigm dealing with formulae having intended semantics in the real numbers but maintaining quantitative proofs and judgments. This is achieved through 'enriched' sequent calculi defined over algebraic structures like [0, ∞]⊕p,⊗.
- Softales
- A notion of algebraic model generalizing residuated lattices by enriching the order structure with multiplicative reals. Semantic validity in these models is determined by the value assigned to a sequent via this enriched order relation.
- Quantitative Adequacy Theorem
- A theorem stating that for differentiable loss functions, the loss JqKp can be interpreted as satisfaction by a model. This means every possible value of the loss function has a corresponding interpretation in terms of logical satisfaction.
Terminology
Summary
Adequate Losses via Quantitative Linear Logic presents a novel logic that unifies qualitative and quantitative aspects of neural network specifications by introducing a family of calculi indexed by a hardness degree and establishing quantitative adequacy for neuro-symbolic loss functions. p. 0 Adequate Losses via Quantitative Linear Logic
MATTEO CAPUCCI∗
, University of Strathclyde and Independent Researcher, IT
ROBERT ATKEY∗
, University of Strathclyde, UK
CHARLES GRELLOIS, Department of Computer Science, University of Sheffield, UK
EKATERINA KOMENDANTSKAYA∗
, Heriot-Watt and Southampton Universities, UK
MATTHEW DAGGITT, University of Western Australia, AU
As “neural” components are increasingly embedded in existing “symbolic” software—including safetycritical systems—the question arises of how to specify and enforce the safety of the newly introduced neural
parts. Unlike traditional logical specifications, these must be amenable not only to the standard Boolean
interpretation, but also to training and optimisation.Where the paper says it
The Core Logical Framework
The paper introduces a logic, pQLL, which is a family of calculi indexed by a hardness degree p, proving a cut-elimination theorem for them and establishing completeness with respect to enriched residuated ‘soft’ lattices. This logic aims to reconcile the three facets required for logical semantics based on loss functions: adequacy, completeness, and justification. p. 2 1 The problems
optimisation
satisfaction provability
adequacy
completeness
justification
Fig. The three facets a differentiable logic
must reconcile. Our intuition tells us that there are
degrees to the violation of this spec, and it is somewhat unreasonable that two nearly identical
functions, like those in Figure 2, should receive completely opposite verdicts. The main thesis
of this paper is thus that
the verification of machine learning models should be
founded on a quantitative reconception of logic.Where the paper says it
Where the paper says it
Quantitative Calculus Definition
The authors propose a new logical paradigm called quantitative logic, which concerns formulae with intended semantics in the reals but maintains quantitative proofs and judgments. This is achieved by introducing quantitative sequent calculi, which are ‘enriched’ in one of the algebraic structures presented in Table 1. p. 4 Our first contribution is to propose a proof-theoretic counterpart to Lawvere’s ideas in the
quantitative realm. We introduce quantitative sequent calculi, which are calculi ‘enriched’ in
one of the algebraic structures presented in Table 1 (and later in Section 2). The family of algebraic structures we collectively refer to as the multiplicative reals [0, ∞]⊕𝑝,⊗. Each 0 < 𝑝 ≤ ∞ gives a choice of additives.Where the paper says it
Where the paper says it
Model Theory and Soundness
The paper develops a notion of algebraic model, softales, which generalizes residuated lattices by enriching the order structure in the multiplicative reals. The semantic validity of a sequent in S is its value as assigned by the enriched order relation ⊑ of S. p. 5 The annotations on the rules are then used to
define a quantitative notion of validity, in the form of a function |−| that evaluates proof trees by
traversing them and aggregating the constants in the leaves using the operations specified by the
rules. A sequent’s provability is then the supremum of the validity of all its proofs. We formulate a notion of algebraic model,
softales, which generalizes residuated lattices and metric spaces by enriching the order
structure in the multiplicative reals, and supports a ‘soft’ notion of lattice connectives: in
this way, for 𝑝 < ∞, the proof calculi 𝑝QLL provide the first instance in the literature
of additive rules with a differentiable semantics, specifically in the canonical model
V = [0, ∞]⊗. This also allows us to have a quantitative notion of satisfaction, for which we
prove a kind of completeness result (Theorem 5.Where the paper says it
Where the paper says it
Adequacy of Loss Functions
The paper establishes a crucial quantitative adequacy theorem, stating that for a differentiable logic, the loss function JphiK can be interpreted as satisfaction by a model. Theorem 6.4 states that given ftheta as above, given (x,ˆ yˆ) ∈ D and for each a ≤ x ≤ b, we have x,ˆ y, x, f ˆ theta = pphi = ⊢pTx,y,f ˆ thetaphi. p. 1 This paper is motivated by the latter class of systems, and studies propertydriven training, a set of methods that train neural networks directly on a spec1
. These methods share a common computational abstraction: given an architecture 𝑓𝜃 : R
𝑚 → R
𝑛
parameterised by weights 𝜃 ∈ R
𝑣
, and a Boolean predicate 𝜑 : (R
𝑚 → R
𝑛
) → Prop over functions
expressed in some domain-specific DSL, it is then translated into a differentiable real-valued
function over the instances of the architecture J𝜑K : R
𝑣 → R. Adequate Losses via Quantitative Linear Logic 3
specification’s Boolean interpretation. From a logical perspective, this amounts to claiming adequacy of the differentiable logic (and hence of the real-valued semantics of the DSL) as a proxy
for satisfaction: the logic should be sound, in the sense that a low loss guarantees the model
satisfies the specification, and complete, in the sense that a satisfying model is reflected by a
correspondingly low loss.Where the paper says it
Where the paper says it
Practical Applications in Neuro-Symbolic AI
The theoretical framework is deployed in property-driven training, where the optimization objective is formulated as argmintheta E(x,ˆ yˆ)∼D Lpred (ftheta (xˆ),yˆ) ∩1lambda sup a≤x≤b JphiK(ftheta (x),ŷ). The results provide the first crucial step towards providing a formal justification for why success in the former compilation target should assist success in the latter. This correspondence allows logical loss minimisation to be formally motivated as a way to improve satisfaction of the specification after training. p. 1 In
contrast, systems such as Logic Tensor Networks [9], DL2 [30], and Vehicle [25, 26] compile
logical specifications into architectures or loss functions that push the network itself to satisfy the
specified properties. This paper is motivated by the latter class of systems, and studies propertydriven training, a set of methods that train neural networks directly on a spec1
.Where the paper says it
Conclusion and Future Work
The work sets out to supply logical meaning to neuro-symbolic methods by rethinking the fundamentals—calculi, proof validity, and satisfaction—in a quantitative way. The long-term goal is to give a formal account of why property-driven training succeeds. p. 0 CCS Concepts: • Theory of computation → Linear logic; Proof theory; Semantics and reasoning;
Logic and verification; • Computing methodologies → Machine learning approaches. Additional Key Words and Phrases: Linear Logic, Differentiable Logic, Fuzzy Logic, Sequent Calculus,
Neuro-Symbolic AI, Neural Network Verification, Property-Driven Training, Enriched Category Theory
∗Author supported by ARIA grant MSAI-PR01-P05. 𝑝QLL (Theorem 4. 4) or provability above 1 in ∞QLL (Theorem 4.Where the paper says it
Where the paper says it
Pruning redundant reasoning tokens
The authors prove cut-elimination for pQLL (Theorem 4.1) and show that the provability of a sequent is realized by at least one proof, which is computable up to any desired precision by real arithmetic. p. 5 In Section 4, we prove various proof-theoretic results: 𝑝QLL admits cutelimination (Theorem 4. 1 proven in Appendix B), with all its usual consequences; we show
provability of a sequent in MALL is equivalent to that sequent having positive provability in
3Note these are Yager’s ‘𝑠-norms’ from [57] but without truncation to [0, 1]. The annotations on the rules are then used to
define a quantitative notion of validity, in the form of a function |−| that evaluates proof trees by
traversing them and aggregating the constants in the leaves using the operations specified by the
rules. A sequent’s provability is then the supremum of the validity of all its proofs.Where the paper says it
Where the paper says it
How the training signal is built
The loss functions for neural models are most commonly given by additive quantities, such as logits and cross-entropy. When augmenting a loss function with a logical term JphiK as in (55), the authors adopt the additive semantics of QLL. p. 1 Systems such as Scallop [43] and DeepProbLog [44] treat the outputs of neural
networks as probabilistic inputs to a symbolic reasoning engine, so that logical inference can
be integrated into the learning pipeline without directly constraining the learned function. In
contrast, systems such as Logic Tensor Networks [9], DL2 [30], and Vehicle [25, 26] compile
logical specifications into architectures or loss functions that push the network itself to satisfy the
specified properties. prove a famous no-go result that no
logic can have connectives that are simultaneously idempotent, associative and shadow-lifting,
and propose to sacrifice associativity [54]. And yet, on the reals there are obvious candidate ‘additive’ and ‘multiplicative’ operations,
namely addition and multiplication themselves!Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Quantitative Adequacy for Loss Minimization: The improved system can formally justify logical loss minimization as a way to improve satisfaction of a specification, as Theorem 6.4 states that
JqKp decreases as x,ˆ y, x, fˆθ = p qll increases.
-
Neuro-Symbolic Verification via Quantitative Proof Validity: The system can translate neural network specifications into quantitative proofs in the pQLL calculus where provability is defined by a supremum of validity of all proofs, allowing for a formal notion of logical adequacy.
-
Robustness Property Formalization: The system can formally encode properties like robustness as first-order sequents within the grounded theory Txyfθ, linking them directly to quantitative satisfaction in the additive reals [−∞, +∞]∪p,⊕.
-
Training Objective Characterization: The system can characterize the relationship between minimizing the differentiable loss and satisfying a specification after training by showing that
JqKp decreases as x,ˆ y, x, fˆθ = p qll increases,
providing a formal justification for why property-driven training succeeds.
Abstract
As neural components are increasingly embedded in existing symbolic software -- including safety-critical systems -- the question arises of how to specify and enforce the safety of the newly introduced neural parts. Unlike traditional logical specifications, these must be amenable not only to the standard Boolean interpretation, but also to training and optimisation. The latter calls for a quantitative interpretation of the logical syntax, subject to further requirements such as smoothness and differentiability. Moreover, the qualitative and quantitative sides of the logic must share a unifying proof-theoretic and categorical semantics. Finally, the new logic should link cleanly to the substructural and program logics that underpin the verification of existing symbolic programs. In this paper, we present a logic that ticks all of these boxes. We introduce a family of calculi, p QLL, indexed by a hardness degree p, prove a cut-elimination theorem for them, and establish completeness with respect to enriched residuated `soft' lattices. At p = infinity, p QLL reduces to multiplicative additive linear logic (MALL), and provability in p QLL converges to provability in MALL as p to infinity. We express optimisation objectives in the syntax of this logic and prove the quantitative adequacy of neuro-symbolic loss functions -- a result that has eluded the neuro-symbolic machine learning community for nearly a decade.
Sources
- A Foundation for Differentiable Logics using Dependent Type Theory
- The multiplicative property characterizes $\ell_p$ and $L_p$ norms
- Propositional Logics for the Lawvere Quantale
- Polynomial Lawvere Logic
- Induction and Recursion Principles in a Higher-Order Quantitative Logic for Probability
- Logic Tensor Networks
- logLTN: Differentiable Fuzzy Logic in the Logarithm Space
- What is Entropy?
- On Quantifiers for Quantitative Reasoning
- Neural Network Robustness as a Verification Property: A Principled Case Study
- Quantitative Linear Logic for Neuro-Symbolic Learning and Verification
- A multiplicative characterization of the power means
- Logit Pairing Methods Can Fool Gradient-Based Attacks
- Analyzing Differentiable Fuzzy Logic Operators
- Marabou 2.0: A Versatile Formal Analyzer of Neural Networks
Related papers
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Interpolation via Generalized Splitting
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring