How to write (conference) papers

Many Computer Science students don't seem to get taught how to write research papers.  I suppose this is because we focus on producing evidence (working software) everyone can download.  I wrote the below advice originally for a review, but then realised two of my own PhD students had the same problem, so now it's a blog post...

Every individual paper has to focus on something.  It has to have a thesis, a statement that could be true or false, that it proves or disproves. In general, for AI, the thesis will be something like
  1. proving that a particular approach is more efficient or provides more accurate predictions than existing approaches for a problem or class of problems.
  2. proving that a particular approach is tractable for a problem or class of problems. This is only interesting if the problem was previously unsolved, otherwise you should be doing something like 1.
  3. some venues will accept something called "a position paper" or "white paper" which just presents a novel idea without proof, but such papers should always be presented as such from the beginning, and they still need evidence e.g. an extremely good literature review or careful reasoning, and normally would also present a research programme for proving or disproving the claims of the paper.
A paper structure should start with a motivation: what is the problem that needs to be solved?  Why does this work need to be done?  Who benefits?   Next, still in the introduction and abstract, you should say what you have achieved.  Let people know there's a good reason to read the paper, so they can decide whether this reason applies to them, or if it doesn't, so they might send it to someone who needs it.   The thesis of the paper should have a form something like "X is a great system, because Z, but it has a problem Y.  Here we present an extension to X that addresses Y.  We have found costs and benefits C & B."

AI (especially ALife) papers sometimes bounce back and forth between two justifications: biological plausibility and efficiency.  Don't do this.  Each paper is only about one topic, its primary contribution can only be to one discipline.  Note that your overall research programme can be about both, and you can have chapters in a dissertation or other book about each.  But any one paper needs to stand up to a single, clear set of criteria.

In the papers that motivated this blog post, the abstract never said what the current state-of-the-art system OR its extension were for.  The "Introduction" did not contain the motivation, or the results, or the roadmap, which are the three things that every Introduction needs.  Rather the introductions wandered through background information on the older systems.  Actually, this is also a common failure mode in talks.  Information on history should go, if anywhere  in a "Background" section, after the Introduction.  In general, the Background section should establish the state of the art so you can prove you have gone beyond it.

Order of writing: Don't try to polish the introduction & abstract before you finish the results.  The first time you write the Introduction it's just to have an outline for the rest of the paper, then you go back and make sure it's the outline of the actual paper after you've really written it.  Focus first on the Results after that outline, as they determine the content of the rest of the paper.  Results, then method that explains the results, then background to set up the method, then conclusion/discussion, THEN the intro again, & abstract.

Update May 2016: see also a newer post, Demonstrating that a paper ought to be published

Acknowledgements:  Ian Horswill taught me about the ALife paragraph when I was a PhD student. Emma Norling pointed out the Introduction vs Background paragraph was still too rooted in the original paper, so I've fixed that now. 
0