A method of processing a query in a multi-stage query processing system, comprising: retrieving a first set of document identifiers from an index in response to one or more query terms; generating a first set of relevancy scores for a first set of compressed documents corresponding to at least a subset of the first set of document identifiers; and decompressing at least a portion of the first set of compressed documents to recover a first set of information wherein the first set of recovered information is associated with positions in the first set of compressed documents corresponding to the first set of document identifiers; generating at least one additional query term based on the first set of information; formulating a new query using the at least one additional query term, the new query having a plurality of query terms; and processing the new query to identify query term tokens corresponding to the query terms and to retrieve a second set of document identifiers corresponding to the query terms, using the index containing a list of token positions, which directly correspond to token positions in a tokenspace repository storing tokens for a second set of compressed documents; generating a second set of relevancy scores for the second set of compressed documents corresponding to at least a subset of the second set of document identifiers; decompressing at least a portion of the second set of compressed documents, from tokens stored in the tokenspace repository to recover a set of tokens, wherein the set of recovered tokens are associated with positions of one or more query terms of the plurality of query terms in the second set of compressed documents corresponding to the second set of document identifiers; and generating a list of documents based on at least a portion of the second set of document identifiers, the list including information corresponding to at least a portion of the set of recovered tokens. retrieving a first set of document identifiers from an index in response to one or more query terms; generating a first set of relevancy scores for a first set of compressed documents corresponding to at least a subset of the first set of document identifiers; and decompressing at least a portion of the first set of compressed documents to recover a first set of information wherein the first set of recovered information is associated with positions in the first set of compressed documents corresponding to the first set of document identifiers; generating at least one additional query term based on the first set of information; formulating a new query using the at least one additional query term, the new query having a plurality of query terms; and processing the new query to identify query term tokens corresponding to the query terms and to retrieve a second set of document identifiers corresponding to the query terms, using the index containing a list of token positions, which directly correspond to token positions in a tokenspace repository storing tokens for a second set of compressed documents; generating a second set of relevancy scores for the second set of compressed documents corresponding to at least a subset of the second set of document identifiers; decompressing at least a portion of the second set of compressed documents, from tokens stored in the tokenspace repository to recover a set of tokens, wherein the set of recovered tokens are associated with positions of one or more query terms of the plurality of query terms in the second set of compressed documents corresponding to the second set of document identifiers; and generating a list of documents based on at least a portion of the second set of document identifiers, the list including information corresponding to at least a portion of the set of recovered tokens.