Double Lift-Off: Learning to Reason Without Ever Building the Model

Opening — Why this matters now

We are living through an odd moment in AI.

On one side, large language models confidently narrate reasoning chains. On the other, real-world decision systems—biomedical trials, environmental monitoring, financial risk controls—require something less theatrical and more sober: provable guarantees under uncertainty.

Most probabilistic relational systems still follow a familiar two-step ritual:

1. Learn a full probabilistic model from data.
2. Perform inference on that model.

The paper Lifted Relational Probabilistic Inference via Implicit Learning (Ge, Juba, Nilsson, Shao, 2026) fileciteturn0file0 asks a sharper question:

What if we never build the model at all?

Instead of learning an explicit distribution and then reasoning over it, the authors merge first-order logic, partial observations, and sum-of-squares (SOS) optimization into a single polynomial-time framework that learns just enough to refute (or certify) a query.

No explicit graphical model. No sampling. No symmetry-breaking approximations.

Just algebraic proof certificates.

Quietly radical.

Background — Where Classical Systems Struggle

1. Model-Based Probabilistic Logic

Frameworks like MLNs or PRMs attempt to define full joint distributions over relational structures. They are expressive—but:

• Learning is often NP-hard.
• Partial observations distort dependencies.
• Approximate models destroy symmetry, undermining lifted inference.

In other words: the part that makes reasoning scalable (symmetry) is often broken during learning.

2. Lifted Inference

Lifted inference exploits renaming symmetries among individuals. Instead of grounding every object, it collapses equivalent ones.

Elegant.

But it assumes the model is already known.

3. Implicit Learning (Propositional)

Previous work showed that you can avoid constructing a full probabilistic model by embedding empirical estimates directly into a sum-of-squares relaxation.

However, that worked only for propositional systems.

Relational domains introduce an additional explosion:

• Individuals (grounding problem)
• Possible worlds (uncertainty over distributions)

This paper solves both.

The Core Innovation — Double Lifting

The authors introduce what we might call a two-dimensional lift.

Instead of constructing a distribution $D$, they:

1. Represent logical and expectation constraints as polynomial inequalities.
2. Embed them into a bounded-degree Sum-of-Squares (SOS) semidefinite program.
3. Integrate empirical bounds from partial observations directly into the same program.

If the resulting system admits a degree-$d$ SOS refutation:

$$ \sigma_0 + \sum_i \sigma_i g_i + \sum_j r_j b_j = -1, $$

then the knowledge base is inconsistent.

Inference becomes:

“Can we algebraically prove that no distribution satisfies these constraints?”

This converts probabilistic reasoning into a certificate-producing convex optimization problem.

For fixed degree $d$ and quantifier rank $k$, the procedure runs in polynomial time.

That’s the theoretical headline.

Learning Under Partial Observations

The truly nontrivial step is integrating masked data.

Real data is incomplete. Sensors fail. Labels are hidden. Privacy removes fields.

The paper formalizes this via a masking process $\Theta$ over full relational models. Observations become partial assignments.

Two mechanisms enable learning:

1. Witnessing (Logical Constraints)

A polynomial constraint is “witnessed” if, under worst-case substitution of unknown values consistent with bounds, it remains nonnegative.

This ensures robustness under missing data.

2. Empirical Expectation Bounds

For moment constraints $e(\mu)$, empirical averages are combined with Hoeffding confidence intervals:

$$ \Pr[\bar{X} - E[X] \ge \varepsilon] \le \exp\left(-\frac{2m\varepsilon^2}{(b-a)^2}\right). $$

This converts partial data into certified expectation bounds.

The algorithm then:

• Computes upper/lower bounds for each monomial via SOS per sample.
• Aggregates them.
• Adds statistically corrected bounds.
• Runs a single lifted SOS program.

If feasible → consistent. If refutable → query disproved.

No generative model ever constructed.

Guarantees — Soundness, Completeness, Polynomial Time

The authors prove:

Soundness

If a true distribution satisfies the system, the algorithm accepts with probability $1 - \delta$.

Completeness

If a bounded-degree SOS refutation exists and constraints are sufficiently testable, the algorithm finds it with probability $1 - \delta$.

Polynomial Bit-Complexity

For fixed $d$ and $k$:

$$ \text{Runtime} = O\big((B + b)^{c(d+k)}\big) $$

Where:

• $B$ = encoding size of knowledge base
• $b$ = query size

The key is that both:

• Infinite domains
• Number of partial samples

enter only polynomially—not exponentially.

That is the practical meaning of “double lift.”

What This Means for Business Systems

Let’s translate.

This framework is particularly relevant when:

• Data is relational (entities + relationships).
• Observations are partial.
• Guarantees matter more than predictive scores.

Examples:

Instead of learning a fragile probabilistic graph and hoping inference remains tractable, one can:

Encode structural knowledge + empirical bounds → ask refutation queries → obtain proof certificates.

This aligns more with assurance engineering than predictive modeling.

And in regulated industries, that distinction is not academic.

Limitations — And Why They Matter

This is not a silver bullet.

1. Bounded Variables Required Explicit compactness assumes finite bounds.

2. SOS Degree Must Be Small Complexity grows quickly with $d$.

3. SDP Solvers Remain Heavy Practical scalability depends on advances in semidefinite optimization.

The authors openly admit they do not claim empirical scalability.

But the structural advance is foundational:

Learning and inference are no longer separate modules.

They are algebraically fused.

Conclusion — From Models to Certificates

Most modern AI systems optimize likelihood.

This one optimizes provability.

Instead of asking:

“What is the most likely world?”

It asks:

“Can any world exist that satisfies these constraints?”

That shift—from prediction to certification—may define the next generation of high-stakes AI systems.

Because in biomedical trials, climate policy, financial compliance, and safety-critical AI, the question is rarely:

“What does the model think?”

It is:

“Can you prove it?”

This paper offers a path toward answering that question without ever building the model in the first place.

Subtle.

And potentially transformative.

Cognaptus: Automate the Present, Incubate the Future.