Referring to the REST API developer guide, it is mentioned that the initial set of data is returned along with the initial REST call response and if there are more records, the next batch url will be provided in the response. But what is the criteria or limits which governs this, like is it like more that x number of records then next batch, or something else. Did not find any mention of any such criteria.
The maximum number of records that will be returned in a single response to the Query resource of the REST API is 2000 records.
This is covered by documentation on the Query Options header. From that page:
Header Field Name and Values
batchSize—A numeric value that specifies the number of records returned for a query request. Child objects count toward the number of records for the batch size. For example, in relationship queries, multiple child objects are returned per parent row returned.
The default is 2,000; the minimum is 200, and the maximum is 2,000. There is no guarantee that the requested batch size is the actual batch size. Changes are made as necessary to maximize performance.
Myself, I've run into a situation in a project I'm currently working on where Salesforce has adjusted the batch size down. In my case, I'm calling the REST API for my production org from a sandbox. I don't know if the 6MB/12MB callout response size limit comes into play here or not.