Order-invariant cluster first-order logic on graph classes of bounded degree

Fatemeh Ghasemi; Julien Grange

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 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

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 →

arxiv 2604.27693 v2 pith:OWFHHD46 submitted 2026-04-30 cs.LO

Order-invariant cluster first-order logic on graph classes of bounded degree

Fatemeh Ghasemi , Julien Grange This is my paper

classification cs.LO

keywords order-invariant logiccluster first-order logicbounded degree graphsexpressive powerfirst-order logicgraph classeslinear orders

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces cluster first-order logic, a restricted fragment of first-order logic tailored to study order invariance. It proves that while order-invariant formulas in this logic can define properties beyond plain first-order logic on arbitrary structures, the two logics coincide in expressive power on any class of graphs with bounded maximum degree. The argument proceeds by explicitly building linear orders on the structures such that any two similar structures remain similar after the orders are added. This local-to-global preservation technique shows that the added order does not create new definable distinctions on bounded-degree classes.

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.

Watch this falsifier — get emailed when new claim-graph text bears on it.

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

These are editorial extensions of the paper, not claims the author makes directly.

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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Cluster FO is new and its order-invariant version collapses to FO on bounded-degree graphs via an explicit similarity-preserving order construction.

read the letter

The main takeaway is that the authors define a new fragment called cluster first-order logic and prove that its order-invariant version has no more expressive power than plain first-order logic on any class of bounded-degree graphs. They do this by explicitly building linear orders that keep FO-similar structures similar after expansion.

What is new is the logic itself plus the inclusion result. The abstract positions cluster FO as a restricted fragment designed for studying order invariance, and the bounded-degree collapse is presented as a concrete step that does not appear in the cited prior work. The construction is the technical core: a local-to-global method that extends neighborhood similarities into a global linear order without creating extra distinctions.

The paper does a clean job of stating the general case where order-invariant cluster FO exceeds FO, then isolating the bounded-degree setting where the collapse holds. Targeting bounded degree to control neighborhoods is a reasonable move, and the claim that the construction is counterintuitive because orders usually reveal distinctions is fair.

The soft spot is the construction itself. The abstract calls it technically involved and sketches the similarity-preserving property, but supplies no proof details or verification steps. The stress-test concern is on point: if the local-to-global extension inadvertently lets the order distinguish structures that cluster FO cannot, the inclusion fails. Bounded degree is invoked to limit neighborhoods, yet the precise mechanism for preserving invariance globally is the unverified step. Until the full argument is checked, soundness stays at the level of a high-level claim.

This is for finite model theorists working on order-invariant logics and expressivity on sparse graphs. A reader already following fragments of FO and descriptive complexity results would find the new logic and the inclusion useful. It is coherent on its own terms and shows honest engagement with the literature, so it deserves a serious referee who can verify the order construction.

Referee Report

1 major / 2 minor

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

1 responses · 0 unresolved

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

0 steps flagged

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

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the newly introduced definition of cluster first-order logic and on the existence of the similarity-preserving order construction; both are internal to the paper and lack independent external verification in the abstract.

axioms (1)

standard math Standard Tarskian semantics for first-order logic
The new fragment is defined as a restriction of ordinary first-order logic.

invented entities (1)

cluster first-order logic no independent evidence
purpose: Restricted fragment of FO designed to study order invariance
Newly defined in the paper; no prior independent evidence supplied.

pith-pipeline@v0.9.1-grok · 5703 in / 1200 out tokens · 29307 ms · 2026-07-01T08:04:52.302252+00:00 · methodology

0 comments

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.

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

13 extracted references · 3 canonical work pages · 3 internal anchors

[1]

InProceedings of the 61st Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pages 1762–1777

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]

none") Respond in EXACTLY this format: EXACT: yes/no INFERRABLE: yes/no PARTIAL: yes/no CONFIDENCE: 0.0-1.0 MISSING: <missing information or

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...

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]

May 7, 2023

For dates: "May 7, 2023" and "7 May 2023" are equivalent

2023
[12]

I don�t know

If prediction says "I don�t know" but ground truth exists, it is WRONG
[13]

score": 1 or 0,

Partial answers that miss the key point are WRONG. **Output Format**: Return ONLY a JSON object: {"score": 1 or 0, "reason": "Brief explanation"}

[1] [1]

InProceedings of the 61st Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pages 1762–1777

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] [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] [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] [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] [5]

EXACT_MATCH: Can answer precisely? (yes/no)

[6] [6]

INFERRABLE: Can reasonably infer the answer? (yes/no)

[7] [7]

PARTIAL_MATCH: Related but insufficient? (yes/no)

[8] [8]

none") Respond in EXACTLY this format: EXACT: yes/no INFERRABLE: yes/no PARTIAL: yes/no CONFIDENCE: 0.0-1.0 MISSING: <missing information or

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...

2023

[9] [9]

The prediction must convey the same core information as the ground truth

[10] [10]

Different wording is acceptable if the meaning is preserved

[11] [11]

May 7, 2023

For dates: "May 7, 2023" and "7 May 2023" are equivalent

2023

[12] [12]

I don�t know

If prediction says "I don�t know" but ground truth exists, it is WRONG

[13] [13]

score": 1 or 0,

Partial answers that miss the key point are WRONG. **Output Format**: Return ONLY a JSON object: {"score": 1 or 0, "reason": "Brief explanation"}