🔢 mathematics

Quantitative Linear Logic

This paper introduces quantitative sequent calculi (pQLL) that assign real-valued semantics to additive connectives in linear logic by revising the sequent calculus framework, thereby enabling differentiable specifications for probabilistic and machine learning systems while proving cut-elimination and completeness for a family of calculi that converge to standard MALL as the hardness parameter approaches infinity.

Original authors: Matteo Capucci, Robert Atkey, Charles Grellois, Ekaterina Komendantskaya

Published 2026-05-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Matteo Capucci, Robert Atkey, Charles Grellois, Ekaterina Komendantskaya

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a computer to make decisions, like a self-driving car deciding whether to brake or accelerate. In the old days, logic was like a light switch: a statement was either ON (True/1) or OFF (False/0). But the real world isn't a light switch; it's a dimmer. Things are "mostly true," "barely true," or "somewhat risky."

For decades, mathematicians have tried to build a "dimmer switch" logic (called Fuzzy Logic) to handle these gray areas. However, there was a major snag: when you try to make these dimmer switches smooth enough for modern AI (which learns by sliding down a hill of errors, a process called gradient descent), the logic breaks. The "smooth" versions lose their logical structure, and the "logical" versions are too jagged for the AI to learn from.

This paper, "Quantitative Linear Logic," by Capucci, Atkey, Grellois, and Komendantskaya, solves this puzzle by inventing a new kind of logic that is both smooth (good for AI) and structured (good for math).

Here is the breakdown of their solution using simple analogies:

1. The Problem: The "Rigid" vs. "Slippery" Dilemma

Think of traditional logic connectives (like "AND" and "OR") as rigid Lego bricks. You snap them together, and they fit perfectly.

The Problem: To make them work with AI, you need to turn them into playdough. You need them to be smooth and stretchy so the AI can nudge them slightly to improve its performance.
The Catch: If you turn the Lego bricks into playdough, they lose their shape. They stop snapping together correctly. In math terms, the "smooth" versions of "AND" and "OR" stop behaving like logic (they lose properties like associativity or idempotency).

The authors found a "No-Go" theorem in previous research: You couldn't have a connective that was smooth, logical, and repeated itself perfectly all at once.

2. The Solution: The "Hardness Dial" ( $p$ )

The authors introduce a new family of logic operations controlled by a dial called $p$ (the "hardness" parameter).

When $p$ is infinite ( $\infty$ ): The logic is Hard. It acts exactly like traditional Lego bricks (standard Linear Logic). It's rigid, perfect, but not smooth enough for AI training.
When $p$ is finite (e.g., $p=1$ ): The logic is Soft. It acts like playdough. It is smooth and differentiable, meaning an AI can learn from it.
The Magic: As you turn the dial from 1 up to infinity, the "playdough" slowly hardens back into "Lego bricks." The logic doesn't break; it just changes its texture.

They achieved this by redefining how "AND" and "OR" work using special mathematical formulas (called $p$ -sums and harmonic $p$ -sums) that look like averages but behave like logic gates.

3. The New Rulebook: "Quantitative Sequent Calculi"

In traditional logic, a proof is a binary thing: it's either Valid (True) or Invalid (False).
In this new system, a proof has a score.

The Analogy: Imagine a courtroom. In the old system, a judge says "Guilty" or "Not Guilty." In this new system, the judge gives a score from 0 to 100.
- A perfect proof scores 100.
- A "soft" proof might score 85.
- A broken proof scores 0.
Why this matters: The authors show that even if a proof isn't perfect (score < 100), it still carries meaning. They can calculate exactly how much truth a proof holds. This allows them to keep the logical rules (like "Cut-Elimination," which ensures proofs are clean) even while the scores are floating numbers.

4. The "Efficiency" of Proofs

One of the coolest discoveries is that this system measures the efficiency of a proof.

In standard logic, proving "A and B" is the same as proving "A" and proving "B" separately.
In this new "Soft" logic, combining them might cost you a little bit of "truth" (your score drops slightly).
The Metaphor: It's like carrying two heavy boxes. If you carry them separately, you are 100% efficient. If you try to carry them together in a "soft" way, you might slip a little, and your efficiency drops to 90%. The math tells you exactly how much efficiency you lost.

5. Real-World Applications Mentioned in the Paper

The paper explicitly connects this theory to two specific areas:

Bayesian Probability (The "Odds" Calculator):
The authors show that when you set the hardness dial to a specific setting ( $p=1$ ), this logic perfectly mimics Bayesian Probability.
- The Analogy: If you are betting on a horse race, the "AND" of two events (Horse A wins AND Horse B wins) is calculated by multiplying their odds. The "OR" is calculated by adding them. This new logic provides the mathematical engine that makes these probability calculations work seamlessly within a logical framework.
Neuro-Symbolic Learning (Teaching AI with Rules):
This is the "killer app" for the paper. Modern AI (Neural Networks) learns by trial and error. Sometimes we want to force the AI to follow strict rules (like "Don't drive through a red light").
- The Problem: Previous attempts to mix rules with AI failed because the rules were too jagged for the AI to learn from.
- The Fix: Because this new logic is smooth (differentiable), you can feed the rules directly into the AI's training process. The AI can "feel" when it is breaking a rule and adjust its behavior to minimize that "rule-breaking score."
- The paper mentions a companion study showing this works better than previous "fuzzy logic" attempts, which often failed to translate math performance into actual safety.

Summary

The authors built a universal translator between the rigid world of mathematical logic and the fluid world of machine learning.

They created a dial ( $p$ ) that lets you slide between "perfect logic" and "smooth, learnable logic."
They turned proofs from simple "Yes/No" switches into scores that measure how well a rule is followed.
They proved that this system can handle probability and AI training without breaking the fundamental laws of logic.

It's like inventing a new type of clay that is soft enough to mold into any shape (for AI) but hardens instantly into a perfect Lego brick (for math) whenever you need it to.

Technical Summary: Quantitative Linear Logic

1. Problem Statement

The paper addresses a fundamental tension in the application of real-valued logics (such as fuzzy logics and differentiable logics) to machine learning and probabilistic verification. While these logics allow truth values to range over the real line (specifically $[0, \infty]$ ) rather than the binary $\{0, 1\}$ , they struggle to reconcile logical properties with analytical requirements.

Specifically, standard fuzzy logics interpret additive connectives (conjunction $\land$ and disjunction $\lor$ ) as lattice operations (min and max). These operations are "hard": they lack smooth monotonicity and differentiability. In machine learning contexts, where gradients are essential for optimization, the non-differentiability of min/max results in non-informative gradients (zero derivatives almost everywhere).

Attempts to replace these with "soft" (differentiable) approximations, such as parameterized families of operations, encounter a "no-go theorem" (Varnai and Dimarogonas): a soft operation cannot simultaneously be associative, idempotent, and smoothly monotonic. Consequently, existing soft logics often sacrifice logical properties like associativity or idempotency, or they force additive connectives to behave multiplicatively (requiring context splitting), thereby breaking the structural principles of linear logic (specifically the distinction between additive and multiplicative connectives).

2. Methodology

The authors propose a radical revision of the proof-theoretic framework to accommodate "soft" connectives without sacrificing the structural integrity of linear logic. Their methodology rests on two pillars:

A. Algebraic Foundations: The Positive Reals

The logic is grounded in the extended positive reals $[0, \infty]$ equipped with a rich algebraic structure.

Multiplicative Structure: Standard multiplication ( $\otimes$ ) and its De Morgan dual, disjunctive multiplication ( $\otimes^*$ ), form a $\ast$ -autonomous monoidal poset.
Additive Structure: Instead of hard min/max, the authors introduce a family of $p$ -sums ( $\oplus_p$ $\oplus_{p}$ ) and harmonic $p$ -sums ( $\oplus_{-p}$ $\oplus_{- p}$ ), parameterized by a "hardness" degree $p \in (0, \infty]$ $p \in (0, \infty]$ .
- $a \oplus_p b = (a^p + b^p)^{1/p}$
- $a \oplus_{-p} b = (a^{-p} + b^{-p})^{-1/p}$
- As $p \to \infty$ , these operations converge pointwise to the hard lattice operations $\lor$ (max) and $\land$ (min).
- For finite $p$ , these operations are smooth, strictly monotone, and associative, but non-idempotent.

B. Quantitative Sequent Calculi

The paper introduces Quantitative Sequent Calculi, where the judgment of a sequent $\Gamma \vdash \Delta$ is not a Boolean truth value but a real number in $[0, \infty]$ .

Validity as a Quantity: The validity of a proof is a real number calculated by traversing the proof tree.
Structural Revision: In standard sequent calculus, the implicit "and" between premises in multi-premise rules is Boolean. In $p$ $p$ -QLL, this is replaced by explicit real-valued operations.
- For example, the additive conjunction rule ( $\land R$ ) combines the validity of two premises using the harmonic sum $\oplus_{-p}$ , rather than a Boolean conjunction.
- This allows the calculus to maintain the additive nature of the connectives (sharing context) while using smooth operations.
The Calculus ( $p$ -QLL): The system is indexed by $p$ . It generalizes hypersequent calculi (used for fuzzy logics) and deep inference. It includes structural rules like MIX and EFQ (Ex Falso Quodlibet), where EFQ allows constructing proofs of any sequent but with validity 0, ensuring consistency.

3. Key Contributions

A. The $p$ -QLL Calculus

The authors define a family of calculi, $p$ -QLL, which serves as a "soft" version of Multiplicative-Additive Linear Logic (MALL).

Soft Additives: The additive connectives are defined via $\oplus_p$ and $\oplus_{-p}$ .
Isomix Property: The units for tensor ( $\otimes$ ) and par ( $\&$ ) coincide (unlike standard MALL), a feature inherited from the underlying algebraic structure.
Quantitative Proofs: Proofs are not merely valid or invalid; they possess a degree of validity. A proof is "efficient" if its validity is high (close to 1 or $\infty$ depending on the mode).

B. Proof-Theoretic Results

Cut-Elimination: The authors prove a cut-elimination theorem for $p$ -QLL. Crucially, the transformation of proofs during cut-elimination is shown to be non-decreasing in validity. This means that removing cuts does not degrade the "quality" of the proof; in some cases, validity increases.
Consistency and Decidability: The system is consistent (there exist sequents with provability 0) and decidable (the supremum of provability is a maximum, achievable by a finite proof).
Hard Limit ( $p=\infty$ ): As $p \to \infty$ , the calculus converges to a "hard" logic ( $\infty$ -QLL) which is equivalent to MALL (specifically the isomix variant).

C. Phenomenology of Soft Additives

The paper reveals new phenomena unique to the quantitative setting:

Loss of Idempotency: While soft additives are not idempotent, the "cost" of this loss is quantified. For instance, the idempotency of a soft conjunction holds only up to a factor of $2^{-1/p}$ .
Inefficiency of Expansion: $\eta$ -expansion (reducing an axiom to propositional variables) is shown to decrease validity in the soft setting. This quantifies the "inefficiency" of decomposing soft additive proofs, suggesting that soft additives are non-decomposable in a way multiplicatives are not.
Prelinearity: The paper investigates the role of prelinearity (a property familiar in fuzzy logic) in restoring efficiency to proofs, though a full axiomatization is left for future work.

D. Algebraic Semantics: Softales

The authors introduce softales, which are $[0, \infty]^\otimes$ -enriched preorders equipped with monoidal structure and "soft $p$ -joins."

Soundness and Completeness: They prove that $p$ -QLL is sound and complete with respect to softales.
Syntactic Softales: They construct a syntactic softale where the order relation is defined by the provability of sequents, establishing a free model for the logic.

4. Results and Applications

A. Connection to Bayesian Probability

The paper demonstrates that $1$-QLL (where $p=1$ ) naturally models Bayesian probability.

In this setting, the multiplicative structure corresponds to conjunction (probability of intersection), and the additive structure corresponds to disjunction (odds).
The provability of a sequent $A \vdash B$ corresponds to the conditional probability $P(B|A)$ (or odds), providing a logical foundation for probabilistic reasoning.

B. Neuro-Symbolic Learning and Differentiable Logic

The paper positions $p$ -QLL as a solution to the tension between logical properties and differentiability in machine learning.

Differentiable Semantics: By mapping the multiplicative reals to additive reals via Napier's isomorphism ( $-\log$ ), the operations $\oplus_p$ and $\oplus_{-p}$ become smooth log-sum-exp and harmonic log-sum-exp functions.
Gradient Flow: These operations have non-vanishing partial derivatives, making them suitable for gradient-based optimization (e.g., training neural networks with logical constraints).
Continuous Verification: The authors reference a companion study showing that $p$ -QLL can bridge the gap between property-driven training and formal verification, offering a logic where the training objective (loss function) and the verification metric are aligned.

5. Significance and Claims

The paper claims to solve the "soft connective" conundrum by redefining the very nature of logical judgment.

Generalization: It presents $p$ -QLL as a natural generalization that unifies linear logic and fuzzy logic, showing that MALL is a limit case of a family of quantitative logics.
Proof-Theoretic Integrity: Unlike previous attempts that sacrificed associativity or idempotency, $p$ -QLL preserves the structural rules of linear logic (exchange, contraction, etc.) by shifting the "cost" of softness into the quantitative validity of the proof rather than the structural rules themselves.
Practical Utility: The framework offers a mathematically rigorous foundation for differentiable logics, enabling the integration of logical specifications directly into the training objectives of machine learning models without the gradient pathologies found in standard fuzzy logics.

The authors conclude that while the loss of idempotency is a necessary trade-off for smoothness, this loss is precisely quantifiable and manageable within the proof-theoretic framework, opening new avenues for connecting linear logic with neuro-symbolic AI.