{"id":"e984739f-f370-4c6f-89cb-ae5834c37f42","arxiv_id":"2507.11897","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Work-in-progress report proposing a lattice-based set-theoretic model for context-sensitive rewrites in relational equality saturation, with case studies in query optimization, conditionals, and lambda applications.","lead":"Contextual equality saturation lets program optimizers apply rewrites only where they are valid, such as inside a conditional branch. This paper summarizes existing techniques and proposes a set-theoretic model to bring this capability to the relational equality-saturation engine egglog, but stops short of an implementation.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The §4 space-for-time claim assumes q can be computed from stored lower-bound e-graphs, but Proposition 4.5 only proves q exists; computing q may require materializing the very per-context equivalence data the scheme aims to avoid.","rationale":"Read in good faith, this is an explicitly incomplete proposal. Its formal propositions are standard and correct as stated (modulo the missing congruence requirement and minor notational slips), and the case studies are reasonable illustrations. The central claim, however, is the practical assertion in §4 that lower-bound storage plus on-demand canonicalization via q gives a space-time tradeoff. I examined what must be true for that claim: q must be representable and computable from the stored lower-bound data without materializing the target context's full equivalence relation. This is nowhere defined. The existence of q is a trivial fact about quotient maps; it does not imply an efficient way to obtain q's graph. The reader's weakest_assumption (lattice/monotonicity of real contexts) is a genuine concern, but it is a condition on the input model; the q-computability gap is a condition on the framework itself and is more directly load-bearing. If q requires materializing φ(c), the paper's main promise—no e-graph per context—is not established. I would keep the CONDITIONAL verdict: the paper is a useful roadmap, but the central practical claim needs a concrete relational encoding of q and at least a microbenchmark before it can be treated as a result.","tokens_in":7376,"tokens_out":13665,"duration_ms":165417,"concrete_test":"Formalize the storage scheme for the simplest nontrivial case: contexts {⊥,s} with φ(s) adding exactly one equality between two e-classes. Specify the relations stored for the lower-bound e-graph and the query/algorithm that computes q : R/φ(⊥) → R/φ(s). Then measure (or, analytically, count) the size of the intermediate relation needed to define q. If q's table must enumerate the s-only equality (i.e., the same data that distinguishes φ(s) from φ(⊥)), the §4 space-for-time claim is not supported by Proposition 4.5 alone; if q can be computed by uniform relabeling with no per-context relation, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The practical payload of §4 is the claim that 'databases can store e-graphs for a lower-bound of contexts' and recover any requested context by applying the factor map q from Proposition 4.5 on demand, trading space for time. Proposition 4.5 only asserts that if ∼1⊆∼2 then q exists; it says nothing about how q is represented or computed from the data actually stored. To apply q to a stored lower-bound e-graph R/∼1, the system must know, for every pair of ∼1-classes, whether they are identified in the target context ∼2. That information is exactly the contextual equivalence relation φ(c). The paper does not specify where φ(c) is stored or how it is derived from the lower-bound context plus the rewrite rules. If computing q requires first materializing φ(c) as a relation on class ids, then the per-context data has not been eliminated; it has only been moved from full e-graph copies to a relation that must be populated, maintained, and joined. The claimed 'trading space for time' therefore rests on an unstated assumption about the availability and cost of q, and no complexity argument or benchmark is given. This is the least secure condition for the central claim: without a concrete relational encoding of q, the framework is a statement about quotient sets, not a recipe for avoiding per-context duplication.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper argues that contextual equalities—rewrites valid only in certain syntactic or semantic contexts—are poorly supported by existing egg/egglog equality saturation systems. It reviews three existing approaches (ASSUME e-nodes, top-down contextual copying, and colored e-graphs) and identifies three motivating applications: relational query optimization, conditional simplification, and lambda application. The main technical proposal is a set-theoretic model in which a context-annotated equivalence relation maps a lattice of contexts to equivalence relations over terms, with more informative contexts yielding more equalities. Proposition 4.5 observes that if ∼1 ⊆ ∼2, the quotient map to ∼2 factors through the quotient map to ∼1 via a map q, and the paper suggests that this enables storing e-graphs for a lower-bound context and recovering a requested context by applying q, trading space for time. The paper concludes by framing the work as early and outlining directions toward a relational implementation in egglog and Datalog-style engines.","tokens_in":7542,"tokens_out":5327,"duration_ms":64315,"significance":"If the proposed model were made computationally precise, it would provide a principled foundation for contextual equality saturation in relational engines and connect e-graph maintenance to classical database cost estimation. The paper is honest about its early status, the three case studies are instructive, and the basic set-theoretic facts are standard and correctly stated; there are no fitted parameters or circular arguments. However, the central practical claim—that q can be used to avoid per-context e-graph duplication—is not established: the paper proves only the existence of q, not how q is represented, computed, or maintained without materializing the contextual equivalence relation it is meant to avoid. The lack of implementation or benchmarks is acceptable for a position paper, but the performance narrative should be clearly labeled as a research hypothesis rather than a derived trade-off.","major_comments":[{"comment":"The central space-for-time claim is not supported by Proposition 4.5. That proposition proves only that if ∼1 ⊆ ∼2 then a map q : A/∼1 → A/∼2 exists; it says nothing about how q is represented or computed from stored data. To apply q to a stored lower-bound e-graph, the engine must know, for every pair of ∼1-classes, whether the target context ∼2 merges them; that information is exactly the contextual equivalence relation φ(c), and the paper does not say where φ(c) is stored or how it is derived from the lower-bound context plus the rewrite rules. Without a concrete relational encoding of q and an argument about its size and update cost, the promised trade-off remains an existence statement about quotient sets rather than a recipe for avoiding per-context duplication.","section":"Section 4 (paragraph after Proposition 4.5)"},{"comment":"The model assumes that contexts form a lattice with bottom and that φ preserves order, but the paper does not show that its motivating contexts—sort order, partitioning, data location, branch predicates, and lambda bindings—satisfy lattice laws or monotonicity. If for two contexts l1 and l2 the equivalence relation is not monotone (for example, when a physical property is destroyed by a rewrite), then the lower-bound storage discipline and the recovery via q would be unsound for those contexts. The paper should either prove or cite such lattice and monotonicity structure for the case-study contexts, or explicitly restrict the framework to contexts where monotonicity is guaranteed.","section":"Definition 4.4"},{"comment":"The claimed difficulty of 'cleaving apart' e-classes in lambda application is hard to reconcile with footnote 1, which states that existing equality saturation can implement beta-reduction and even entire interpreters by using e-graph analyses to track free and bound variables. The paper should explain what the proposed contextual framework adds over that existing mechanism, or it should weaken the corresponding motivation and the statement that 'there is no way to cleave apart an e-class'.","section":"Section 3.3 (footnote 1)"}],"minor_comments":[{"comment":"Typos: 'there as been' should be 'there has been', and 'to an program' should be 'to a program'; the same section's running example would benefit from a comma after 'the ternary'.","section":"Section 1"},{"comment":"In the second numbered item, 'Under the then branch of the ternary' should be 'Under the else branch', since the branch condition is ¬(a > b); the current wording makes the example confusing.","section":"Section 3.2"},{"comment":"Notation is inconsistent between Example 4.2 and Proposition 4.5: the quotient construction is introduced as R/∼, but Proposition 4.5 switches between A and R; please use a single symbol throughout.","section":"Section 4"},{"comment":"These propositions are stated without proof; since they are standard lattice-theoretic facts, one-line proofs or explicit references would make the paper more self-contained.","section":"Propositions 4.3 and 4.5"},{"comment":"The phrase 'a lower-bound of contexts' is ambiguous: it should be clarified whether the stored context is a single context l that is below all materialized contexts in the lattice order, or a set of lower bounds, since the storage and recovery scheme depends on this choice.","section":"Section 4 (lower-bound contexts)"}],"recommendation":"major_revision","confidential_remarks":"I would not reject this as a position paper: the topic is timely, the case studies are useful, and the set-theoretic framing is a reasonable starting point. However, the central technical argument—the space-for-time benefit of storing lower-bound e-graphs and recovering them via q—needs to be made precise before publication. The stress-test concern about q is the key issue: existence of a factor map does not imply that it can be computed cheaply or without materializing the very per-context equivalence data the scheme aims to avoid."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — this is a WIP, not a results paper. The useful part is the survey of existing contextual e-graph approaches (ASSUME nodes, top-down annotations, colored e-graphs) and the three case studies (query plans, conditionals, lambda). If you want a quick map of that area, it's a good read. The paper's own contribution is a set-theoretic definition of contexts as order-preserving maps from a lattice to equivalence relations, plus the observation that Propositions 4.3 and 4.5 (lattice of equivalence relations, factoring of quotient maps) can frame the design. The math is standard and correct as far as it goes, though the propositions are unproved.\n\nSoft spots. The load-bearing practical claim in Section 4 is that you can store e-graphs for a lower-bound context and recover any coarser context on demand by the factor map q, trading space for time. That claim assumes q is available and cheap. Proposition 4.5 only gives you existence. To compute q you need the contextual equivalence relation φ(c) on class ids, and the paper doesn't say where that relation lives or how it is derived. The stress-test note is right: unless you have a concrete relational encoding of q, you have not avoided per-context duplication, you have just moved it. The lattice assumption on real contexts (sort order, partitioning, conditions) is also unexamined; the case studies are consistent with it, but that is not evidence. Finally, the Section 3.3 footnote admits lambda beta-reduction can already be handled by e-graph analyses, which takes most of the novelty out of that case study.\n\nProportion: these are soft spots for a proposal, not fatal flaws. The paper is honest about being early work, and the failure mode is not wrong math but missing implementation and evaluation.\n\nRecommendation: send it to peer review, but with the expectation that the authors add either a formal treatment of q or a small prototype. It deserves referee time as a vision paper, and the DB/PL cross-pollination angle is real. I wouldn't cite it as a result, but I'd put it in a reading group to discuss the research agenda.","headline":"An honest work-in-progress report that usefully surveys contextual equality saturation and offers a set-theoretic framing, but its central space-for-time proposal is unvalidated and the math is standard.","tokens_in":8168,"tokens_out":3287,"would_cite":false,"duration_ms":34870,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Contextual rewrites need not duplicate e-graphs per context.","keywords":["e-graphs","equality saturation","contextual rewrites","relational equality saturation","query optimization","equivalence relations","context lattices","program analysis"],"falsifier":"Instrument a rewrite engine to record, for every context it visits, the exact equivalence relation it induces on terms; if two contexts with $c_1 \\leq c_2$ are found where $\\varphi(c_1)$ contains an equality not present in $\\varphi(c_2)$, or if a pair of real contexts has no least upper bound in the context lattice, the order-preserving lattice premise of Definition 4.4 fails for that application.","tokens_in":7090,"feed_emoji":"🧮","tokens_out":10152,"duration_ms":118658,"temperature":0.7,"pith_summary":"Equality saturation normally proves rewrites that hold everywhere, but many optimizations are only valid in a part of the program, such as inside a branch, below a sort enforcer, or within a lambda body. This paper argues that contextual equality saturation has a set-theoretic structure: contexts form a lattice of equivalence relations, ordered so that more context can only add equalities, never remove them. Its central claim is that a relational equality-saturation engine can store e-graphs for the most restrictive contexts and canonicalize to a requested context on demand through a factor map, avoiding duplication of the e-graph for every context. If this holds, contextual rewrites become practical in relational engines without the e-graph explosion seen in earlier approaches, using database-style cost estimation to choose how to answer each matching query.","feed_headline":"Contextual rewrites need not duplicate e-graphs per context","feed_subtitle":"A lattice of equivalence relations lets equality saturation canonicalize on demand and borrow database cost tricks.","key_machinery":"The load-bearing object is a context-annotated equivalence relation (Definition 4.4): a map $\\varphi$ from a lattice of contexts, with bottom element $\\bot$, to equivalence relations on the set of terms, required to be order-preserving so that $l_1 \\leq l_2$ implies $\\varphi(l_1) \\leq \\varphi(l_2)$. The workhorse result is Proposition 4.5, which says the quotient map into a coarser equivalence relation factors through the quotient map into any finer one, yielding a map $q$ that sends each fine equivalence class to its containing coarse class. This $q$ is what lets a framework store only lower-bound-context e-graphs and canonicalize to the requested context at e-match time; the lattice meet and join of equivalence relations (Proposition 4.3) are what let branch conditions be combined as contextual equalities are intersected.","core_discovery":"On the paper's own terms, the discovery is that contextual equality saturation can be described by a context-annotated equivalence relation: a map from a lattice of contexts, with a bottom element, to equivalence relations on the set of terms, where moving to a more specific context yields at least as many equalities. The key result is Proposition 4.5: if one equivalence relation is finer than another, the quotient map into the coarser relation factors through the quotient map into the finer one, giving a map $q$ that sends each fine equivalence class to its containing coarse class. Consequently, an engine can store canonicalized e-graphs for lower-bound contexts and, at e-match time, either match directly against them or apply $q$ to canonicalize a copy, trading space for time under the guidance of database cardinality estimation. The paper also shows that the proof-by-cases step used to combine branch contexts corresponds to taking the meet of equivalence relations, while lambda application highlights a missing operation: cleaving a subterm out of an e-class when a bound variable must not escape its scope.","pith_inferences":["The lattice assumption is untested on real context sets; a natural next step is to check whether contexts like sort order, partitioning, data location, and branch predicates form true lattices or whether they need a richer structure such as a product of lattices or a Galois connection.","If the factor-map model is implemented, a concrete benchmark would compare on-demand canonicalization against both explicit assumption nodes and layered colored relations on the ternary and query-plan examples; the paper reports no measurements yet.","The proof-by-cases rule suggests a general design: expose contextual equivalence relations as first-class values, letting rewrites query the lattice rather than encoding context in special e-nodes; this could make other inference rules expressible as relational queries.","A long-range consequence the paper leaves implicit is that the same model may apply to program analysis beyond optimization, such as context-sensitive dataflow facts that are monotone as paths are extended."],"forward_implications":["A relational equality-saturation engine could answer contextual e-matching queries without keeping a separate canonicalized e-graph per context, choosing instead between joining on the stored equivalence relation and applying the factor map $q$ to canonicalize on demand.","Database-style cardinality estimates become directly relevant: if the context adds many equalities, canonicalizing a copy up front is likely cheaper; if it adds few, joining on the equivalence relation is likely cheaper.","Rules that combine contexts, such as drawing a global conclusion from what holds in both branches of a ternary, can be expressed as lattice meet and join operations on context-annotated equivalence relations.","Because the number of equivalence classes can shrink as more equalities are added, a relational engine must hide this non-monotonicity from users, just as existing single-relation engines hide it for one equivalence relation.","Of the three case studies, query-plan rewriting under physical properties and conditional simplification fit the model directly, while lambda application remains open until an operation exists to recover the subset of a body's e-class that avoids the bound variable."],"supporting_citations":[{"why":"Introduces equality saturation, the optimization technique this paper extends to contextual rewrites.","marker":"[Tate et al. 2009]"},{"why":"Presents the e-graph library whose non-relational e-matching limits colored e-graphs and motivates the relational extension.","marker":"[Willsey et al. 2021]"},{"why":"Supplies relational equality saturation and the canonicalized-database/find model that Definition 4.4 and Proposition 4.5 are designed to extend.","marker":"[Zhang et al. 2023]"},{"why":"Demonstrates the ASSUME-node approach to contextual rewrites whose e-graph expansion motivates the space/time tradeoff.","marker":"[Coward et al. 2023]"},{"why":"Provides the copy-the-context approach that can cause combinatorial e-graph explosion, another baseline for the proposed model.","marker":"[Drewery 2022]"},{"why":"Gives colored e-graphs with layered equivalence relations and the proof-by-cases intersection rule reused in Section 3.2.","marker":"[Singher and Itzhaky 2023]"},{"why":"Establishes physical properties and sort enforcers, the setting of the query-plan case study.","marker":"[Graefe and McKenna 1993]"},{"why":"Provides database cardinality estimation, the cost model the paper invokes for choosing whether to canonicalize with $q$ or join.","marker":"[Gray et al. 2007]"}],"fun_headline_variants":["Contextual e-graphs: a lattice of equivalences to avoid duplication","One e-graph per context? Use a quotient map instead","Relational equality saturation borrows database cost tricks","Canonicalize on demand with a context lattice"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The framework assumes that the contexts a rewrite engine cares about form a lattice ordered so that moving up the lattice only adds equalities, and that real context properties such as sort order, partitioning, data location, and branch predicates satisfy that ordering.","fun_headline_variants_meta":{"raw":{"variants":["Contextual e-graphs: a lattice of equivalences to avoid duplication","One e-graph per context? Use a quotient map instead","Relational equality saturation borrows database cost tricks","Canonicalize on demand with a context lattice"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000218,"raw_usage":{"total_tokens":1376,"prompt_tokens":815,"completion_tokens":561,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":431,"completion_tokens_details":{"reasoning_tokens":492}},"tokens_in":431,"tokens_out":561,"duration_ms":6808,"temperature":1.0,"reasoning_tokens":492,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:59:36.785189+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instrument a rewrite engine to record, for every context it visits, the exact equivalence relation it induces on terms; if two contexts with $c_1 \\leq c_2$ are found where $\\varphi(c_1)$ contains an equality not present in $\\varphi(c_2)$, or if a pair of real contexts has no least upper bound in the context lattice, the order-preserving lattice premise of Definition 4.4 fails for that application.","supporting_citations":[],"review_version":1}