Writing study: MaxSketch: Robust Distinct Counting in Streams via Random Projections

NeurIPS overviewCorpus atlasBy contribution typeVisual galleryRules & templateWriting patternsPaper studies

← NeurIPS 2026 oral writing corpus

Nikos Tsikouras, Constantine Caramanis, Christos Tzamos · Official NeurIPS 2026 oral record

Observed writing choices, not acceptance rules. This study examines the inspected manuscript version. It does not establish why the paper was accepted or that its presentation choices should be copied unchanged.

Figure, table and section ledger

Editorial contribution type: Theory & formal analysis (primary).

Layout extraction, not a required paper template. Counts are distinct caption labels; a multi-panel figure counts once. Section spans are estimated from heading positions, including floats and whitespace. Method and limitations.

Canonical PDF

30 physical pages

Before references / appendix

≈ 9.09 page-equivalents

Main figures / tables

1 / 2

Attached appendix figures / tables

1 / 0

Attached appendix span

≈ 12 page-equivalents

Before references / appendix: ≈ 30.3%References / intervening material: ≈ 29.7%Attached appendix: ≈ 40%Estimated layout envelopes, not text/artwork area. Unresolved appendix boundaries remain within the undivided post-body material.

Source-bound correction: Top-level heading and reference/appendix boundaries checked against source PDF text. Bibliography titles/author initials, numbered contribution/property bullets, diagram steps, equations and TOC entries are not substantive headings. Section spans are page-coordinate estimates, not ink area or prose-only length. This is an author manuscript mirror, not a verified accepted-version template. Source layout uses physical single-column y/page-height, including equation-heavy pages.

Section-by-section lengths and source pages

The title/abstract/front matter precede the first numbered heading. A span ends at the next detected top-level heading, not at the last sentence; end-page whitespace is included. References and statements are listed separately. These are not measurements of text-only or artwork area.

Top-level heading	Starts on PDF page	Estimated span	Share of entire PDF
1 Introduction	1	≈ 2.79 pp.	9.3%
2 Problem Setting	4	≈ 0.37 pp.	1.23%
3 MaxSketch: A Max-Linear Streaming Representation	4	≈ 0.44 pp.	1.47%
4 Theoretical Guarantees	5	≈ 1.46 pp.	4.87%
5 Experiments	6	≈ 2.68 pp.	8.93%
6 Limitations	9	≈ 0.2 pp.	0.67%
7 Conclusion	9	≈ 0.53 pp.	1.77%
References	10	≈ 2 pp.	6.67%
A Appendix: Extended Related Work	12	≈ 1.09 pp.	3.63%
B Proofs of Theorems 1–3	13	≈ 8.41 pp.	28.03%
C Experimental Details	21	≈ 2.5 pp.	8.33%
NeurIPS Paper Checklist	24	≈ 6.91 pp.	23.03%

All detected figure and table locations

Main text

• Table 1 · p. 7
• Table 2 · p. 8
• Figure 1 · p. 9

Attached appendix

• Figure 2 · p. 22

Argument and organization

1. Problem and contribution

   Recasts exact key counting as counting clusters in noisy learned representations, exposing the geometric assumption early.

2. Argument sequence

   Explains max aggregation, then stages the argument through Gaussian maxima, perturbations, separation and the resulting guarantee.

3. Evidence and verification

   Digit, object and face experiments test different representation regimes; limitations explain why exact accuracy falls when clusterability fails.

Problem, claim and contribution

Recasts exact key counting as counting clusters in noisy learned representations, exposing the geometric assumption early.

Sections 1–2 · Main paper

Argument and section order

Explains max aggregation, then stages the argument through Gaussian maxima, perturbations, separation and the resulting guarantee.

Sections 3–4 · Main paper

Figures, captions and visual explanation

The final identity-count plot gives separate curves for three absolute error tolerances, so high approximate accuracy is not presented as exact counting.

Figure 1, p. 9 · Main paper

Tables, comparisons and evidence

Digit, object and face experiments test different representation regimes; limitations explain why exact accuracy falls when clusterability fails.

Section 5; Section 6, p. 9 · Main paper

Appendix and reproducibility

Related work, technical proofs and experimental implementation are partitioned before the checklist.

Appendices A–C, pp. 12–23 · Main paper

Clarity and writing conventions

The proof roadmap names each intermediate obstacle before displaying lemmas, and the conclusion repeats the geometric qualification.

Section 4, p. 5; Section 7 · Main paper

What to reuse—and what not to infer

Transferable lesson: Use a proof roadmap and tolerance-labeled experiments to connect a formal abstraction to learned representations.

Boundary: Polylogarithmic sketch memory is conditional on clusterability; a learned embedding experiment does not establish that assumption generally.

Apply this lesson using the argument and evidence worksheet.

Inspection record and sources

Checked

2026-10-02

Reading status

Writing-focused manuscript scan + selected visuals inspected

Main text

Writing-oriented distributed manuscript scan of Sections 1–7, pp. 1–9; references pp. 10–11: abstract/framing, section sequence, substantive text windows, captions, evidence organization and conclusion; not exhaustive technical verification.

Appendix / supplement

Writing-oriented scan of Appendices A–C and checklist, pp. 12–30; code and experiments were not executed.

Visually inspected PDF pages

5, 9

This is a writing-focused scan of the manuscript and the stated supplementary scope: framing, organization, visual explanation, evidence presentation and wording. It is not a line-by-line proof audit, reproduction of results or exhaustive scientific review.

• Public author arXiv manuscript 2605.15571v1; not verified identical to the accepted or camera-ready OpenReview revision · 30 pages