Solver & Routing
JuGeo dispatches verification conditions to Z3 and CVC5 through a fragment-aware routing layer. The router classifies each formula into one of 13 SMT-LIB fragments and selects the strategy best suited to that fragment, managing solver sessions and jurisdiction boundaries automatically.
13 SMT-LIB Fragments
The SMT-LIB standard defines a set of logics (fragments) that describe which
theories and quantifier forms are used. JuGeo's FragmentClassifier
inspects each verification condition (VC) and assigns it to one of the following
13 fragments. The fragment determines which solver tactics and strategies are
applicable.
| Fragment | Full Name | Python Domain | Default Solver |
|---|---|---|---|
| QF_LIA | Quantifier-free linear integer arithmetic | Integer bounds, loop counters | Z3 |
| QF_LRA | Quantifier-free linear real arithmetic | Float refinements, rate constraints | Z3 |
| QF_BV | Quantifier-free bitvectors | Bitwise operations, overflow checks | Z3 |
| QF_AUFLIA | QF arrays + uninterpreted functions + LIA | List/dict read-write reasoning | Z3 |
| QF_S | Quantifier-free strings | String refinements, regex constraints | Z3 (str theory) |
| QF_NIA | Quantifier-free nonlinear integer arithmetic | Polynomial constraints, hash functions | Z3 (nlsat) |
| QF_NRA | Quantifier-free nonlinear real arithmetic | Numeric stability, ML weight bounds | CVC5 |
| UFLIA | Uninterpreted functions + LIA (with quantifiers) | Abstracted function calls | Z3 |
| AUFBVLIA | Arrays + UF + BV + LIA | Memory-mapped numeric data | Z3 |
| QF_DT | Quantifier-free datatypes | Algebraic types, enums, tagged unions | Z3 |
| QF_UFLIA | QF UF + LIA | Abstract function models with bounds | Z3 |
| ALL | All theories (full SMT-LIB) | Complex multi-theory judgments | Z3 (portfolio) |
| UNKNOWN | Fragment not classifiable | Opaque functions, H∞ candidates | None — escalated to FORMAL evidence |
QF_NRA and QF_NIA. Nonlinear arithmetic is decidable in principle (Tarski's theorem for reals, Presburger for integers), but practically hard. JuGeo routes QF_NRA to CVC5 by default and sets a tighter time budget. If the solver times out, the judgment is classified as UNKNOWN trust and the fragment is logged for manual inspection.
5 Routing Strategies
The routing layer can apply one of five strategies to decide how to handle each VC. Strategies differ in how aggressively they attempt multiple solvers and how they balance latency against completeness.
Fragment-First
Route to the solver known to perform best on the classified fragment. The default. Fast and reliable for well-typed formulas.
Portfolio
Run Z3 and CVC5 in parallel on a thread pool; return the first conclusive result. Higher resource use; best completeness.
Incremental
Reuse solver state from previous VCs via push/pop. Reduces overhead for large modules with many related VCs.
Fallback Chain
Try Z3; if UNKNOWN, try CVC5; if still UNKNOWN, escalate to FORMAL evidence channel. Maximises coverage at higher latency.
Budget-Aware
Respect a per-VC time and cost budget. Skips expensive fragments if budget is exhausted; reports BUDGET_EXCEEDED rather than UNKNOWN.
Z3Session, Z3Formula, and FragmentClassifier
The three core classes in jugeo.solver are
Z3Session, Z3Formula, and
FragmentClassifier. They form a thin, idiomatic Python wrapper
around the z3-solver library that integrates with JuGeo's trust and evidence
machinery.
from jugeo.solver import Z3Session, Z3Formula, FragmentClassifier
import z3
# FragmentClassifier: inspect a formula before solving
formula = z3.And(z3.Int("x") > 0, z3.Int("x") < 100)
clf = FragmentClassifier()
fragment = clf.classify(formula)
print(fragment) # SMTFragment.QF_LIA
print(fragment.solver) # "z3"
print(fragment.tactics) # ["linarith", "arith"]
# Z3Session: managed solver session with JuGeo integration
session = Z3Session(
timeout_ms=5000,
strategy="FRAGMENT_FIRST",
incremental=True,
)
session.push()
session.assert_formula(formula)
result = session.check()
print(result.status) # "UNSAT" | "SAT" | "UNKNOWN"
print(result.trust) # TrustLevel.SOLVER if UNSAT
print(result.model) # z3.ModelRef if SAT (counterexample)
session.pop()
# Z3Formula: wraps a z3 expression with metadata
zf = Z3Formula(
expr=formula,
fragment=fragment,
source_judgment=judgment,
label="price_bound_check",
)
print(zf.fragment) # SMTFragment.QF_LIA
print(zf.label) # "price_bound_check"
Jurisdiction Management
In a multi-solver setup, each solver operates within a jurisdiction: the set of fragments and formula shapes it is authorised to handle. JuGeo tracks jurisdictions to prevent a weaker solver from returning inconclusive results on formulas that a stronger solver could decide.
Jurisdiction boundaries are enforced by the SolverJurisdiction
class. When a formula is submitted to a session, the session checks that the
formula's fragment falls within the session's jurisdiction. If not, the formula
is escalated to the appropriate solver automatically.
from jugeo.solver import SolverJurisdiction, SolverRouter, SMTFragment
# Define custom jurisdiction
jur = SolverJurisdiction(
solver_name="z3",
fragments=[SMTFragment.QF_LIA, SMTFragment.QF_LRA, SMTFragment.QF_BV],
timeout_ms=10_000,
fallback="cvc5",
)
# Router: dispatches VCs to sessions based on jurisdiction
router = SolverRouter(
strategy="FALLBACK_CHAIN",
jurisdictions=[jur],
)
# Route a single formula
result = router.route_and_solve(formula, label="vc_001")
print(result.solver_used) # "z3" or "cvc5"
print(result.fragment) # the detected fragment
print(result.escalated) # True if escalated to fallback solver
print(result.duration_ms) # actual solving time
# Batch routing (parallel where strategy allows)
vcs = [Z3Formula(expr=f, label=f"vc_{i}") for i, f in enumerate(formulas)]
batch_result = router.route_batch(vcs)
print(f"Verified: {batch_result.verified_count}")
print(f"Unknown : {batch_result.unknown_count}")
print(f"SAT : {batch_result.sat_count}") # counterexamples found
Python Examples
End-to-end: from judgment to solver result:
import jugeo
from jugeo.solver import SolverRouter, RoutingStrategy
# Build site and run the encoding pipeline
site = jugeo.build_site("mymod")
report = jugeo.analyze_module("mymod", property="pure")
# Access the solver results for each judgment
for j in report.judgments:
vc = j.verification_condition
if vc is None:
print(f" {j.coordinate}: no VC (trivial or FORMAL)")
continue
fragment = vc.fragment
result = vc.solver_result
print(f" {j.coordinate} [{fragment.name}] -> {result.status}")
if result.status == "SAT":
print(f" Counterexample: {result.model_as_python_values()}")
# Configure and run the router directly
router = SolverRouter(strategy=RoutingStrategy.PORTFOLIO)
jugeo.set_solver_router(router)
# Re-run with portfolio strategy
report2 = jugeo.analyze_module("mymod", property="no_exceptions")
print(f"Closed: {report2.closed_count} / {report2.total_count}")
Inspecting fragment classification details:
from jugeo.solver import FragmentClassifier, SMTFragment
import z3
clf = FragmentClassifier(verbose=True)
# A mixed-theory formula: integers + uninterpreted function
x = z3.Int("x")
f = z3.Function("f", z3.IntSort(), z3.IntSort())
formula = z3.And(x > 0, f(x) == x + 1, f(f(x)) < 100)
fragment = clf.classify(formula)
print(fragment) # SMTFragment.UFLIA
print(clf.classification_trace) # step-by-step reasoning
# Check whether a formula is in a decidable fragment
print(clf.is_decidable(formula)) # True for UFLIA
print(clf.complexity_estimate(formula)) # "pspace" | "np" | "polynomial"
# Get the recommended tactics for a fragment
tactics = clf.recommended_tactics(SMTFragment.QF_AUFLIA)
print(tactics) # ["arrays", "arith", "qfauflia"]