Assuming you are using a distributed architecture, there is no way to verify a user without at least one database lookup because the request could be coming into any API server. So in most cases we're not avoiding cookies and sessions just for the sake of it.

You don't need to do a database look up if you stuff some context into your token and encrypt it with a secret key. When the server receives the request it can simply decrypt the token and deserialize it into some sort of strongly typed usercontext

Doesn't this open you up to replay attacks though? Since you can't store that a token was already used..

I failed to say that your token context should have a "time based expiration", in that a new token is reissued periodically as defined by you and your needs. I would refer to the ASP.NET Forms Auth mechanism with its sliding expiration.

Sure you can. Just include a timestamp, and expire the token, at, say, time + 90 seconds, or whatever makes sense for the application.

I get that you can expire it, and that helps, but it's not the same as use-once. Of course, just using a timeout is probably fine in many cases, especially if it's used with SSL. But replay attacks are still possible since there's a windows where it can be re-used.

Replay attacks are always gonna be possible unless you use a one time token or signature, thems the break's..., unless you wish to get into the something you have and something you know model. How can you do a use once token making concurrent requests without a strong authentication mechanism client side such as issuing private keys to clients....and all the PKI admin overhead. I think its safe to say, that a restful api should be stateless, and bottlenecks such as session state are not necessary.

I'll take that as a "yes" ;)

AFAIK, neither signatures or "something you have, know" alone fixes replay attacks. Since this is a well known problem in cryptography, many solutions exists. All of which are probably overkill for this use.

At least with the use of a digital signature and nonce you can guarantee that the request hasn't been tampered with!

Use redis/memcache to avoid constant DB hits.

Alternatively, if a time limited token is practical, use a self-signed expiring token.

One reason to avoid sessions is security aspect of it. Cookies are handled automatically by the browser which opens the API up to XSS

Use an expiring token like mechanism.

The API user first gets a token using credentials. Future requests use the token for authentication.

A new token will be required periodically.

What are the benefits of doing this instead of just requiring authentication with every request?

Is it because the authentication part is a lot of work for the server or client?

Is it for the negligible (in this context) security benefits of not using the same secret-key for all traffic?

The hashing for the authentication is intentionally computationally slow (thus mitigating brute force validation). The token issued is basically like a session id - validating a session id is really just like string compare, so it's much much fast.

How is that fundamentally different from storing sessions in a database (which is common to be able to scale horizontally)?

Whether or not that is a lot of overhead depends also on how much work you were going to do to process the rest of the request. If your API allows sorting and filtering of a large data set, like the article suggests, then the authentication overhead is probably relatively small.

You don't need to do a database look up if you stuff some context into your token and encrypt it with a secret key.

When the server receives the request it can simply decrypt the token and deserialize it into some sort of strongly typed usercontext.

Others have already commented, but also keep in mind that subsequent requests should be pulling from cache. So the overhead is lighter than a full DB request.