Adequate Losses via Quantitative Linear Logic

arXiv:2605.13348 · cs.LO, math.LO · Submitted 2026-05-13 · Read on arXiv

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

Where the paper says it

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.

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

Where the paper says it

1 The problems optimisation satisfaction provability adequacy completeness justification Fig. The three facets a differentiable logic must reconcile.

The central idea is that verification of machine learning models should be founded on a quantitative reconception of logic. p. 3
Where the paper says it

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.

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

Where the paper says it

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 is denoted as [0, ∞]⊕p,⊗, where different choices of p dictate the additives and multiplicative operations available. p. 5
Where the paper says it

The family of algebraic structures we collectively refer to as the multiplicative reals [0, ∞]⊕𝑝,⊗. Each 0 < 𝑝 ≤ ∞ gives a choice of additives.

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

Where the paper says it

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.

Soundness is proven by showing that the axioms of softales make each rule of pQLL into a valid reasoning scheme within a softale. Completeness is established by constructing classifying softales, LTp[T], whose order relation is defined by provability in the theory. p. 6
Where the paper says it

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.

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

Where the paper says it

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.

This allows every value of the loss JphiK to have an interpretation in terms of satisfaction by a model. p. 2
Where the paper says it

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.

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

Where the paper says it

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 .

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

Where the paper says it

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.

Future work involves extending pQLL with first-order quantification and studying the status of MIX∗ as a logical rule. The paper concludes that QLL can be interpreted as a calculus of conversion rates, where provability represents a conversion rate from resources in Γ to A. p. 6
Where the paper says it

𝑝QLL (Theorem 4. 4) or provability above 1 in ∞QLL (Theorem 4.

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

Where the paper says it

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 process of cut-elimination terminates because the metrics met(pi) are in a well-founded lexicographic order. This ensures that provability is realized by at least one proof (since there are finitely many proofs of potential maximal validity). p. 5
Where the paper says it

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.

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

Where the paper says it

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.

This semantic distinction concerns which arithmetic operation naturally aggregates such quantities when objects are combined ‘independently’. The isomorphism between additive and multiplicative reals is noted, where conjunctive multiplication ⊗ becomes ordinary addition. p. 4
Where the paper says it

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!

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

  1. 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.

  2. 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.

  3. 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,⊕.

  4. 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

Related papers