REVIEW 1 major objections 2 minor 13 references
Order-invariant cluster first-order logic has the same expressive power as plain first-order logic on bounded-degree graph classes.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.3
2026-07-01 08:04 UTC pith:OWFHHD46
load-bearing objection Cluster FO is new and its order-invariant version collapses to FO on bounded-degree graphs via an explicit similarity-preserving order construction. the 1 major comments →
Order-invariant cluster first-order logic on graph classes of bounded degree
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
On any class of graphs with bounded maximum degree, every property definable by an order-invariant formula of cluster first-order logic is already definable by a plain first-order formula without an order symbol.
What carries the argument
Similarity-preserving linear orders constructed so that local similarities between structures extend to global similarities after expansion by the order.
Load-bearing premise
It is possible to build linear orders on the structures such that similar structures stay similar after the orders are added.
What would settle it
A bounded-degree graph class together with an order-invariant cluster first-order formula that defines a property not definable by any plain first-order formula.
If this is right
- Order-invariant properties in cluster first-order logic coincide exactly with first-order definable properties on bounded-degree classes.
- The same collapse result holds for any logic whose formulas can be simulated inside cluster first-order logic.
- The construction technique transfers results about unordered structures to their ordered expansions on these classes.
Where Pith is reading between the lines
- The same local-to-global order construction might apply directly to plain first-order logic and resolve its order-invariance question.
- Similar techniques could separate or collapse other restricted fragments of first-order logic on bounded-degree graphs.
- The result suggests testing whether bounded degree is the precise boundary where order invariance adds no power in cluster first-order logic.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces cluster first-order logic, a restricted fragment of first-order logic designed to study order invariance. It claims that order-invariant cluster FO can exceed plain FO in general but is contained in FO on bounded-degree graph classes, proved by explicitly constructing similarity-preserving linear orders via a local-to-global extension that maintains FO-similarity after expansion with the order.
Significance. If the inclusion holds, the result is significant for order-invariant logics: it supplies an explicit, constructive technique on bounded-degree classes that could serve as a stepping stone toward resolving the open question for plain order-invariant FO. The paper's emphasis on an explicit construction (rather than non-constructive arguments) is a strength that supports potential generalization.
major comments (1)
- [Main construction / proof of the inclusion theorem] Main theorem proof (the similarity-preserving construction): the inclusion order-invariant cluster FO ⊆ FO on bounded-degree classes rests entirely on the claim that the local-to-global linear-order construction extends FO-similar neighborhoods without introducing new distinctions detectable by cluster FO. The bounded-degree hypothesis is invoked to control neighborhoods, but the manuscript must explicitly verify (via the precise inductive or recursive definition of the order) that no global propagation creates an FO-definable separation that the cluster restriction would have forbidden; any gap here directly falsifies the inclusion.
minor comments (2)
- [Abstract] Abstract: the phrase 'technically involved and somewhat counterintuitive' could be replaced by a one-sentence indication of the key mechanism (e.g., 'using bounded degree to ensure local cluster similarity lifts to a global linear order without new FO distinctions').
- [Definition section] Notation: confirm that the abbreviation 'cluster FO' is introduced once and used uniformly after the definition section.
Simulated Author's Rebuttal
We thank the referee for the detailed reading and for highlighting the importance of an explicit verification in the main construction. We address the single major comment below.
read point-by-point responses
-
Referee: Main theorem proof (the similarity-preserving construction): the inclusion order-invariant cluster FO ⊆ FO on bounded-degree classes rests entirely on the claim that the local-to-global linear-order construction extends FO-similar neighborhoods without introducing new distinctions detectable by cluster FO. The bounded-degree hypothesis is invoked to control neighborhoods, but the manuscript must explicitly verify (via the precise inductive or recursive definition of the order) that no global propagation creates an FO-definable separation that the cluster restriction would have forbidden; any gap here directly falsifies the inclusion.
Authors: We agree that the proof relies on showing the construction preserves cluster-FO equivalence and does not introduce new distinctions. The inductive definition in Section 4 proceeds by extending partial orders on neighborhoods while maintaining identical FO-types (including cluster quantifiers) at each finite stage; bounded degree ensures neighborhoods remain finite and the extension is uniform across isomorphic components. Nevertheless, we acknowledge that a dedicated lemma isolating the invariance property under global propagation would strengthen the argument. We will insert such a lemma (with a short proof by induction on the construction stages) in the revised version. revision: yes
Circularity Check
No circularity: inclusion proved by explicit construction of similarity-preserving orders
full rationale
The paper defines cluster first-order logic and proves that its order-invariant fragment is contained in plain FO on bounded-degree classes. The load-bearing step is an explicit construction of linear orders that preserve FO-similarity locally-to-globally. No equations reduce a claimed prediction to a fitted parameter, no self-citation chain justifies the central inclusion, and the construction is presented as a direct, technically involved argument rather than a renaming or self-definition. The result is therefore self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard Tarskian semantics for first-order logic
invented entities (1)
-
cluster first-order logic
no independent evidence
read the original abstract
We introduce a new logic, called \emph{cluster first-order logic}, a restricted fragment of first-order logic specifically designed to study order invariance. An order-invariant formula is one on a vocabulary that contains an order; however, whether a structure satisfies it or not is independent of the interpretation of the order. We show that while order-invariant cluster first-order logic can define properties outside the scope of plain first-order logic in general, its expressive power is included in that of first-order logic when it comes to classes of bounded degree. We establish this result by explicitly constructing linear orders such that similar structures remain similar when they are expanded with these orders. This similarity-preserving, local-to-global approach is technically involved and somewhat counterintuitive, since adding an order usually reveals distinctions that are otherwise hidden due to the locality of first-order logic. We believe that this work can be a stepping stone toward applying such techniques to plain first-order logic and toward settling the question of the expressive power of order-invariant plain first-order logic.
Reference graph
Works this paper leans on
-
[1]
Precise zero-shot dense retrieval without rel- evance labels. InProceedings of the 61st Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pages 1762–1777. Yubin Ge, Salvatore Romeo, Jason Cai, Raphael Shu, Yassine Benajiba, Monica Sunkara, and Yi Zhang
-
[2]
Memory in the Age of AI Agents
Tremu: Towards neuro-symbolic temporal rea- soning for llm-agents with memory in multi-session dialogues. InFindings of the Association for Compu- tational Linguistics: ACL 2025, pages 18974–18988. Bernal Jiménez Gutiérrez, Yiheng Zhu, Zhiwei Huang, Shivani Kamez, and Huan Sun. 2024. HippoRAG: Neurobiologically inspired long-term memory for large language...
work page internal anchor Pith review Pith/arXiv arXiv 2025
-
[3]
Evaluating Very Long-Term Conversational Memory of LLM Agents
Evaluating very long-term conversational memory of llm agents.Preprint, arXiv:2402.17753. Siru Ouyang, Jun Yan, I-Hung Hsu, Yantei Chen, Ke Jiang, Zifeng Wang, Rujun Han, Long T Le, Samira Daruki, Xiangru Tang, and 1 others. 2025. Reasoningbank: Scaling agent self-evolving with rea- soning memory.arXiv preprint arXiv:2509.25140. Charles Packer, Vivian Fan...
work page internal anchor Pith review Pith/arXiv arXiv 2025
-
[4]
Corrective Retrieval Augmented Generation
Corrective retrieval augmented generation. arXiv preprint arXiv:2401.15884. Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi. 2020. Bertscore: Evaluating text generation with bert.Preprint, arXiv:1904.09675. Wanjun Zhong, Lianghong Guo, Qiqi Gao, and Yan- lin Wang. 2023. Memorybank: Enhancing large language models with long-ter...
work page internal anchor Pith review Pith/arXiv arXiv 2020
-
[5]
EXACT_MATCH: Can answer precisely? (yes/no)
-
[6]
INFERRABLE: Can reasonably infer the answer? (yes/no)
-
[7]
PARTIAL_MATCH: Related but insufficient? (yes/no)
-
[8]
MISSING: what specific information is missing? (or "none") Respond in EXACTLY this format: EXACT: yes/no INFERRABLE: yes/no PARTIAL: yes/no CONFIDENCE: 0.0-1.0 MISSING: <missing information or "none"> PROMPTTEMPLATE FORQUERYREFINEMENT(IRIS) �������You are a helpful assistant that refines search queries. ����� Original question: {original_question} Current...
work page 2023
-
[9]
The prediction must convey the same core information as the ground truth
-
[10]
Different wording is acceptable if the meaning is preserved
- [11]
- [12]
-
[13]
Partial answers that miss the key point are WRONG. **Output Format**: Return ONLY a JSON object: {"score": 1 or 0, "reason": "Brief explanation"}
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.