Paper Types Beyond Empirical ML
Guide for writing non-standard paper types: theory papers, survey/tutorial papers, benchmark/dataset papers, and position papers. Each type has distinct structure, evidence standards, and venue expectations.
Contents
- - Theory Papers
- - Survey and Tutorial Papers
- - Benchmark and Dataset Papers
- - Position Papers
- - Reproducibility and Replication Papers
- - The main contribution is a theorem, bound, impossibility result, or formal characterization
- - Experiments are supplementary validation, not the core evidence
- - The contribution advances understanding rather than achieving state-of-the-art numbers
- - State all assumptions explicitly (numbered, with names)
- - Include the formal bound, not just "converges at rate O(·)"
- - Add a plain-language corollary: "In particular, this means..."
- - Compare to known bounds: "This improves over [prior work]'s bound of O(·) by a factor of..."
- - A subfield has matured enough that synthesis is valuable
- - You've identified connections between works that individual papers don't make
- - Newcomers to the area have no good entry point
- - The landscape has changed significantly since the last survey
- - Be meaningful: Categories should correspond to real methodological differences, not arbitrary groupings
- - Be exhaustive: Every relevant paper should fit somewhere
- - Be mutually exclusive (ideally): Each paper belongs to one primary category
- - Have informative names: "Attention-based methods" > "Category 3"
- - Be visualized: A figure showing the taxonomy is almost always helpful
- - By technique: chain-of-thought, tree-of-thought, self-consistency, tool use
- - By training requirement: prompting-only, fine-tuned, RLHF
- - By reasoning type: mathematical, commonsense, logical, causal
- - Cite every relevant paper — authors will check if their work is included
- - Be fair — don't dismiss methods you don't prefer
- - Synthesize, don't just list — identify patterns, trade-offs, open questions
- - Include a comparison table — even if qualitative (features/properties checklist)
- - Update before submission — check arXiv for papers published since you started writing
- - Existing benchmarks don't measure what you think matters
- - A new capability has emerged with no standard evaluation
- - Existing benchmarks are saturated (all methods score >95%)
- - You want to standardize evaluation in a fragmented subfield
- - You have an argument about how the field should develop
- - You want to challenge a widely-held assumption
- - You want to propose a research agenda based on analysis
- - You've identified a systematic problem in current methodology
- - Lead with the strongest version of your argument — don't hedge in the first paragraph
- - Engage with counterarguments honestly — the best position papers address the strongest objections, not the weakest
- - Provide evidence — a position paper without evidence is an editorial
- - Be concrete — "the field should do X" is better than "more work is needed"
- - Don't straw-man existing work — characterize opposing positions fairly
- - You attempted to reproduce a published result and succeeded/failed
- - You want to verify claims under different conditions
- - You've identified that a popular method's performance depends on unreported details
Theory Papers
When to Write a Theory Paper
Your paper should be a theory paper if:
Structure
`
1. Introduction (1-1.5 pages)
- Problem statement and motivation
- Informal statement of main results
- Comparison to prior theoretical work
- Contribution bullets (state theorems informally)
2. Preliminaries (0.5-1 page)
- Notation table
- Formal definitions
- Assumptions (numbered, referenced later)
- Known results you build on
3. Main Results (2-3 pages)
- Theorem statements (formal)
- Proof sketches (intuition + key steps)
- Corollaries and special cases
- Discussion of tightness / optimality
4. Experimental Validation (1-2 pages, optional but recommended)
- Do theoretical predictions match empirical behavior?
- Synthetic experiments that isolate the phenomenon
- Comparison to bounds from prior work
5. Related Work (1 page)
- Theoretical predecessors
- Empirical work your theory explains
6. Discussion & Open Problems (0.5 page)
- Limitations of your results
- Conjectures suggested by your analysis
- Concrete open problems
Appendix:
- Full proofs
- Technical lemmas
- Extended experimental details
`
Writing Theorems
Template for a well-stated theorem:
`latex
\begin{assumption}[Bounded Gradients]\label{assum:bounded-grad}
There exists $G > 0$ such that $\|\nabla f(x)\| \leq G$ for all $x \in \mathcal{X}$.
\end{assumption}
\begin{theorem}[Convergence Rate]\label{thm:convergence}
Under Assumptions~\ref{assum:bounded-grad} and~\ref{assum:smoothness},
Algorithm~\ref{alg:method} with step size $\eta = \frac{1}{\sqrt{T}}$ satisfies
\[
\frac{1}{T}\sum_{t=1}^{T} \mathbb{E}\left[\|\nabla f(x_t)\|^2\right]
\leq \frac{2(f(x_1) - f^*)}{\sqrt{T}} + \frac{G^2}{\sqrt{T}}.
\]
In particular, after $T = O(1/\epsilon^2)$ iterations, we obtain an
$\epsilon$-stationary point.
\end{theorem}
`
Rules for theorem statements:
Proof Sketches
The proof sketch is the most important part of the main text for a theory paper. Reviewers evaluate whether you have genuine insight or just mechanical derivation.
Good proof sketch pattern:
`latex
\begin{proof}[Proof Sketch of Theorem~\ref{thm:convergence}]
The key insight is that [one sentence describing the main idea].
The proof proceeds in three steps:
\begin{enumerate}
\item \textbf{Decomposition.} We decompose the error into [term A]
and [term B] using [technique]. This reduces the problem to
bounding each term separately.
\item \textbf{Bounding [term A].} By [assumption/lemma], [term A]
is bounded by $O(\cdot)$. The critical observation is that
[specific insight that makes this non-trivial].
\item \textbf{Combining.} Choosing $\eta = 1/\sqrt{T}$ balances
the two terms, yielding the stated bound.
\end{enumerate}
The full proof, including the technical lemma for Step 2,
appears in Appendix~\ref{app:proofs}.
\end{proof}
`
Bad proof sketch: Restating the theorem with slightly different notation, or just saying "the proof follows standard techniques."
Full Proofs in Appendix
`latex
\appendix
\section{Proofs}\label{app:proofs}
\subsection{Proof of Theorem~\ref{thm:convergence}}
We first establish two technical lemmas.
\begin{lemma}[Descent Lemma]\label{lem:descent}
Under Assumption~\ref{assum:smoothness}, for any step size $\eta \leq 1/L$:
\[
f(x_{t+1}) \leq f(x_t) - \frac{\eta}{2}\|\nabla f(x_t)\|^2 + \frac{\eta^2 L}{2}\|\nabla f(x_t)\|^2.
\]
\end{lemma}
\begin{proof}
[Complete proof with all steps]
\end{proof}
% Continue with remaining lemmas and main theorem proof
`
Common Theory Paper Pitfalls
| Pitfall | Problem | Fix |
| --------- | --------- | ----- |
| Assumptions too strong | Trivializes the result | Discuss which assumptions are necessary; prove lower bounds |
| No comparison to existing bounds | Reviewers can't assess contribution | Add a comparison table of bounds |
| Proof sketch is just the full proof shortened | Doesn't convey insight | Focus on the 1-2 key ideas; defer mechanics to appendix |
| No experimental validation | Reviewers question practical relevance | Add synthetic experiments testing predictions |
| Notation inconsistency | Confuses reviewers | Create a notation table in Preliminaries |
| Overly complex proofs where simple ones exist | Reviewers suspect error | Prefer clarity over generality |
| Venue | Theory Acceptance Rate | Notes |
| ------- | ---------------------- | ------- |
| NeurIPS | Moderate | Values theory with practical implications |
| ICML | High | Strong theory track |
| ICLR | Moderate | Prefers theory with empirical validation |
| COLT | High | Theory-focused venue |
| ALT | High | Algorithmic learning theory |
| STOC/FOCS | For TCS-flavored results | If contribution is primarily combinatorial/algorithmic |
| JMLR | High | No page limit; good for long proofs |
| Venue | Notes | |
| ------- | ------- | |
| TMLR (Survey track) | Dedicated survey submissions; no page limit | |
| JMLR | Long format, well-respected | |
| Foundations and Trends in ML | Invited, but can be proposed | |
| ACM Computing Surveys | Broad CS audience | |
| arXiv (standalone) | No peer review but high visibility if well-done | |
| Conference tutorials | Present as tutorial at NeurIPS/ICML/ACL; write up as paper | |
| Criterion | What Reviewers Check | |
| ----------- | --------------------- | |
| Novelty of evaluation | Does this measure something existing benchmarks don't? | |
| Construct validity | Does the benchmark actually measure the stated capability? | |
| Difficulty calibration | Not too easy (saturated) or too hard (random performance) | |
| Annotation quality | Agreement metrics, annotator qualifications, guidelines | |
| Documentation | Datasheet, license, maintenance plan | |
| Reproducibility | Can others use this benchmark easily? | |
| Ethical considerations | Bias analysis, consent, sensitive content handling | |
| Venue | Notes | |
| ------- | ------- | |
| NeurIPS Datasets & Benchmarks | Dedicated track; best venue for this | |
| ACL (Resource papers) | NLP-focused datasets | |
| LREC-COLING | Language resources | |
| TMLR | Good for benchmarks with analysis | |
| Venue | Notes | |
| ------- | ------- | |
| ICML (Position track) | Dedicated track for position papers | |
| NeurIPS (Workshop papers) | Workshops often welcome position pieces | |
| ACL (Theme papers) | When your position aligns with the conference theme | |
| TMLR | Accepts well-argued position papers | |
| CACM | For broader CS audience | |
| Venue | Notes | |
| ------- | ------- | |
| ML Reproducibility Challenge | Annual challenge at NeurIPS | |
| ReScience | Journal dedicated to replications | |
| TMLR | Accepts reproductions with analysis | |
| Workshops | Reproducibility workshops at major conferences |