Megrez: A Knowledge-Guided Agent for Formal Mathematics over MK Set Theory
Organizations: School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China.
Abstract
General-purpose coding agents equipped with proof-assistant tools have shown strong performance on standalone competition problems, yet cumulative textbook formalization inside a low-resource mathematical library still faces three obstacles: aligning textbook concepts with library declarations, keeping long-horizon search synchronized with live proof states, and integrating locally verified proofs reliably into a growing codebase. We present Megrez, a knowledge-guided formalization agent for Rocq libraries built on Morse--Kelley (MK) set theory. Megrez coordinates a general coding agent through three mechanisms: (1) a source-rebuildable knowledge graph merging formal declarations, compiler references, and curated metadata to support retrieval via Chinese aliases, concept clusters, proof dependencies, and multi-lane full-text ranking; (2) a feedback-driven 1--5 tactic short-burst proving loop paired with a goal-local branch ledger and exponential-interval structured reflection; and (3) a three-check acceptance pipeline (statement fidelity, axiom auditing, and full builds) coupled with a multi-corpus Provider stack and a candidate-bound recoverable batch state machine. Deployment and evaluation on a point-set topology corpus demonstrate effective cross-chapter formalization and scalable premise retrieval.
Figures & tables
| Category | Breakdown | Count |
| Source scale | .v source files / Total lines of completed proof script | 262 / 102,122 |
| Declarations ( ) | Theorem (652) / Lemma (1,718) / Corollary (97) / Prop. (59) / Fact (116) | 2,642 |
| Definition (903) / Abbreviation (189) / Notation (55) / Other (Instance, Ltac, etc. 105) | 1,252 | |
| Total nodes (with completed Qed proofs) | 3,894 (2,529) | |
| Reference edges ( ) | proof_uses / statement_mentions | 32,227 / 12,979 |
| uses_notation / uses_tactic / file_requires / dual_of & notation_of | 12,455 / 1,745 / 1,493 / 83 |
| Module / Chapter | Mathematical topic | Files | Decls | Proved | Proof lines |
|---|---|---|---|---|---|
| MK | MK set theory (axioms, ordinals, cardinals) | 3 | 437 | 284 | 2,517 |
| Real_Axioms + Real_Analysis | Real number axioms and basic analysis | 6 | 340 | 227 | 3,543 |
| Chapter1_NaiveSetTheory | Set operations, countability, AC & Tukey | 9 | 149 | 112 | 1,720 |
| Chapter2_MetricSpaces | Metric and topological spaces, continuity | 7 | 172 | 46 | 2,453 |
| Chapter3_SubspacesProducts | Subspaces, finite/arbitrary products, quotients | 4 | 117 | 47 | 1,628 |
| Chapter4_Connectedness | Connectedness, components, path/local conn. | 5 | 148 | 111 | 5,555 |
| Task & workload | Query example | 10,000 nodes (16.9 MB) | 100,000 nodes (170.4 MB) | ||
|---|---|---|---|---|---|
| legacy-v1 | fts-v1 | legacy-v1 | fts-v1 | ||
| Interactive: Exact identifier | Synthetic_000001 | 8.11 (7–24) | 0.71 (3) | 72.29 (7–24) | 1.23 (3) |
| Interactive: Chinese concept | conn. space (ZH) | 8.30 (16) | 6.21 (7) | 76.87 (16) | 19.73 (7) |
| Interactive: Formal operators | /\ -> := | 6.33 (6) | 6.12 (7) | 58.51 (6) | 18.10 (7) |
| Interactive: Common token | topology common | 40.11 (36) | 24.33 (7) | 410.80 (36) | 199.24 (7) |
| Interactive: Single CJK char | conn. char (ZH) | 8.99 (36) | 0.91 (5) | 82.55 (36) | 0.99 (5) |
| Test category | Files | Tests | Verified invariants and fault-injection scenarios |
|---|---|---|---|
| Source & ref parsing | 5 | 43 | .v declaration/proof boundary parsing, terminator detection after focused blocks, .glob extraction, proof-stripped context fingerprints |
| KG build & Providers | 10 | 80 | Idempotent rebuilds, fault injection with atomic .previous rollback, dual-schema support, Provider topological sort, single writable Workspace |
| Retrieval & scope safety | 11 | 69 | FTS5 injection-safe compilation, pinned navigation + RRF ranking, scope-before-cap filtering, self-reference masking, token budgeting |
| Batch & crash recovery | 7 | 120 | DAG readiness, CAS revisions, capability-token auth, same-file parallel claims, 4-way recovery ( redispatch / rewrite_candidate / reverify / manual ), candidate rejection |
| Workflow & packaging | 6 | 7 | Attention-budget line caps ( lines), cooperative read-only worker contracts, Gate 1 review before batch init, zero trajectory memory |
| Textbook item | Formal identifier | Kind | Lines | Key design or proof route |
|---|---|---|---|---|
| Defs. 1.8.1–1.8.4 | SelectionFun , FiniteChar , MaxMember / MinMember | definition | – | Local choice function, finite-character family, maximal/minimal members; Def. 1.8.2 reuses MK base Nest |
| Axiom 1.8.1 / Thm. 1.8.2 | Xiong_1_8_1 / Xiong_1_8_2 | theorem | 12 / 19 | Restricts global choice AxiomIX to and indexed family via MKT126a/b/c and MKT30 |
| (Helper lemmas) | remove_one_card / fin_chain_union | lemma | 16 / 40 | Removing one element reduces to ; explicit-predicate induction on over nests |
| Lemma 1.8.3 | Xiong_1_8_3 | theorem | 14 | Nonempty finite-character families are closed under subsets and nest unions (via fin_chain_union ) |
| Thm. 1.8.4 / Cor. 1.8.5 | Xiong_1_8_4 / Xiong_1_8_5 | thm / cor | 32 / 63 | Tukey’s Lemma via Hausdorff’s principle MKT143 on a maximal nest; Corollary on |
Autoformalization
Autoformalization converts natural-language mathematics, proofs, and specifications into machine-checkable formal languages.
See all 124 papers