cs.IRApr 8, 2026
SaveSubSearch: Intermediate Rewards for Unsupervised Guided Reasoning in Complex Retrieval
Organizations: IRLab, University of Amsterdam
Abstract
Large language models (LLMs) are probabilistic in nature and perform more reliably when augmented with external information. As complex queries often require multi-step reasoning over the retrieved information, with no clear or predetermined reasoning path, they remain challenging. Recent approaches train models using reinforcement learning on the model's outcome, showing promise in improving how models handle complex information. We introduce SubSearch, a specialized framework that shifts from outcome-only supervision to intermediate reward signals that incentivize planning high-quality reasoning. Unlike previous work on process reward modeling, which focuses on training a separate reward model with annotated trajectories by either human annotators or large LLM judges, SubSearch directly optimizes the generator using intrinsic process rewards, which we define as internally-derived rewards, eliminating the need for external supervision, and moving towards autonomous information-intensive reasoning. Experiments on seven benchmarks show that rewarding intermediate reasoning steps with intrinsic rewards leads to more robust reasoning traces in both QA and multi-hop QA datasets over using only outcome rewards. SubSearch can help in building reasoning traces that allow agents to better integrate search engines for complex query answering, while offering a data-efficient alternative to supervised process modeling.
Figures & tables
Figure 1: SubSearch query decomposition and intermediate reward computation. The rewards are calculated at different stages of the reasoning traces, but only after the entire reasoning trace has been generated.
| Answer the given question. You must conduct reasoning inside <think> and </think> first every time you get new information. After reasoning, if you find you lack some knowledge, you can call a search engine by <search> query </search> , and it will return the top searched results between <information> and </information> . |
| If the original query is complex or involves multiple parts, you are encouraged to decompose it into at most 3 smaller sub-questions, separated by ## . For example: <search> sub-question 1 ## sub-question 2 </search> and it will return the top searched results between <information> documents sub-question 1 ## documents sub-question 2 </information> . |
| You can search as many times as you want. Only decompose when the question has multiple independent parts (e.g., different entities, aspects, or comparisons). Do not decompose questions that do not need it. |
| If you find no further external knowledge needed, you can directly provide the answer inside <answer> and </answer> without detailed illustrations. For example, <answer> Beijing </answer> . |
| Question: {question} |
Table 1: Prompt template for SubSearch. The question is appended during training and inference.
| RL | |||||||
| Method | Evidence | SFT | Rewards | Type | Training data | Decomp. | Interm. |
| Direct Inference | – | – | – | – | – | – | – |
| CoT | – | – | – | – | – | – | – |
| SFT | – | ✓ | – | – | – | – | – |
| RAG | ✓ | – | – | – | – | – | – |
| Search-o1 | ✓ | – | – | – | – | – | – |
Table 2: Comparison of search agent methods. ✓/–: present/absent. Evidence : retrieved external documents. Decomp. : query decomposition. Interm. : subquery-level intermediate reward. 1g+2i : 1 global + 2 intermediate.
| Methods | Alg. | General QA | Multi-Hop QA | |||||
|---|---|---|---|---|---|---|---|---|
| NQ † | TriviaQA ∗ | PopQA ∗ | HotpotQA † | 2wiki ∗ | MuSiQue ∗ | Bamboogle ∗ | ||
| Baselines | ||||||||
| Direct Inference | – | 0.106 | 0.288 | 0.108 | 0.149 | 0.244 | 0.020 | 0.024 |
| CoT | – | 0.023 | 0.032 | 0.005 | 0.021 | 0.021 | 0.002 | 0.000 |
| SFT | – | 0.249 | 0.292 | 0.104 | 0.186 | 0.248 | 0.044 | 0.112 |
| RAG | – | 0.348 | 0.544 | 0.387 | 0.255 | 0.226 | 0.047 | 0.080 |
Table 3: Main results. Bold indicates the best performance within each supervision category. / represent in-domain/out-domain datasets. REINF. refers to the REINFORCE algorithm, and r. indicates a reproduced method. Our method (SubSearch) achieves state-of-the-art results among SFT-free RL agents.
| Model | NQ † | TriviaQA ∗ | PopQA ∗ | HotpotQA † | 2wiki ∗ | MuSiQue ∗ | Bamboogle ∗ |
|---|---|---|---|---|---|---|---|
| SubSearch- base | 0.463 | 0.597 | 0.435 | 0.362 | 0.351 | 0.101 | 0.263 |
| SubSearch- instruct | 0.325 | 0.523 | 0.353 | 0.300 | 0.294 | 0.110 | 0.219 |
Table 4: Performance comparison between base and instruct backbones for SubSearch.
Figure 2: Training Progress of Qwen2.5-3B-base (a) with and without query decomposition via prompting on NQ and HotpotQA, (b) using EM, answerability and decomposition as reward signals, and (c) using weighted sum, residual or adaptive residual reward aggregation.
Figure 3: Relative improvements on Qwen2.5-3B-base (a) with and without query decomposition via prompting on NQ and HotpotQA, (b) using EM, answerability and decomposition as reward signals, and (c) using weighted sum, residual or adaptive residual reward aggregation.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Training progress of Qwen2.5-3B-base on NQ with GRPO and EM as reward, with and without using a format signal.
Figure 5: SubSearch notation for query decomposition and intermediate rewards computation. denotes the decomposition layer (root = 0), denotes the index within each layer, represents a subquery at layer and index , and represents the retrieved documents for subquery .
Figure 6: Adaptive beta evolution over training steps. A higher value highlights more weight to the intermediate rewards, while a lower value shows the model becomes better at giving a correct answer and therefore gives priority to the binary outcome reward. Higher EMA highlights giving more weight to recent reasoning traces compared to older ones.
| Question: Which bank has more branches, China CITIC Bank or UniCredit? |
|---|
| Ground Truth: UniCredit |
| <think> First, I need to find information about China CITIC Bank. </think> |
| <search> how many branches does UniCredit have bank </search> |
| <information> Doc 1(Title: "UniCredit Bank Romania") UniCredit Bank Romania UniCredit Bank is a leading European Bank, member of UniCredit Group, with a network of 8.500 branches in 17 European countries and it is present in another 50 international markets Being one of the top 5 banks on the Romanian market, UniCredit Bank has 208 branches and almost 3000 employees. At the end of 2015, the bank had total assets in amount of 34,6 billion RON and included approximately 600.000 active customers. Among the offered services are: financial solutions for individuals, SMEs, companies and freelancers. UniCredit Bank is recognized for specializing in the real estate market and.. Doc 2(Title: UniCredit) UniCredit UniCredit S.p.A. is an Italian global banking and financial services company. Its network spans 50 markets in 17 countries, with more than 8,500 branches and over 147,000 employees. Its strategic position in Western and Eastern Europe gives the group one of the region’s highest market shares. The company is a component of the Euro Stoxx 50 stock market index. UniCredit Group was the outcome of the 1998 merger of several Italian banking groups, which the majority one were Unicredito (banks from Turin, Verona and Treviso) and Credito Italiano (consists of Rolo Banca, Banca Popolare di Rieti), hence the name.. Doc 3(Title: UniCredit) subsidiary Bank Austria). Until 2018 UniCredit was one of the UEFA Champions League’s main sponsors. UniCredit UniCredit S.p.A. is an Italian global banking and financial services company. Its network spans 50 markets in 17 countries, with more than 8,500 branches and over 147,000 employees. Its strategic position in Western and Eastern Europe gives the group one of the region’s highest market shares. The company is a component of the Euro Stoxx 50 stock market index. UniCredit Group was the outcome of the 1998 merger of several Italian banking groups, which the majority one were.. </information> |
| <think> Based on the information found, I need to compare the number of branches of China CITIC Bank and UniCredit. </think> |
| <search> how many branches does China CITIC Bank have </search> |
Table 5: SubSearch case study 1 (successful): SubSearch can decompose the initial information need into parallel subqueries and aggregate the retrieved documents to answer correctly.
| Question: Which team did Joe Buck’s father broadcast for? |
|---|
| Ground Truth: St. Louis Cardinals |
| <think> First, I need to find information about Joe Buck. </think> |
| <search> who is joe buck father broadcast </search> |
| <information> Doc 1(Title: "Joe Buck") but rather to vocal cord paralysis likely caused by anesthesia used during multiple hair transplantation procedures. From 1993 to 2011, Buck was married to Ann Archambault, with whom he had two children. He married NFL Network and now ESPN reporter and former Bronco cheerleader Michelle Beisner on April 12, 2014. On April 26, 2018 they welcomed twin sons Wyatt Joseph and Blake Andrew. Joe Buck Joseph Francis Buck (born April 25, 1969) is an American sportscaster and the son of sportscaster Jack Buck. He has won numerous Sports Emmy Awards for his work with Fox Sports, including his roles as.. Doc 2(Title: "Joe Buck") the team’s broadcasting crew. In 1994, Buck was hired by Fox, and at the age of 25 became the youngest man ever to announce a regular slate of National Football League games on network television. In , he was named Fox’s lead play-by-play voice for Major League Baseball, teaming with Tim McCarver, who had previously worked with his father on CBS. That year, he became the youngest man to do a national broadcast (for all nine innings and games, as a network employee as opposed to simply being a representative of one of the participating teams) for a World Series.. Doc 3(Title: "Joe Buck") Joe Buck Joseph Francis Buck (born April 25, 1969) is an American sportscaster and the son of sportscaster Jack Buck. He has won numerous Sports Emmy Awards for his work with Fox Sports, including his roles as lead play-by-play announcer for the network’s National Football League and Major League Baseball coverage, and is a three-time recipient of the National Sportscaster of the Year award. Since 1996, he has served as the play-by-play announcer for the World Series, each year, with the exceptions of 1997 and 1999. Since 2015, he’s hosted ""Undeniable with Joe Buck"" on Audience Network. Buck was born </information> |
| <think> I now need to find which team his father broadcast for. </think> |
| <search> who did jack buck broadcast for </search> |
Table 6: SubSearch case study 2 (successful): SubSearch can decompose the initial information need into sequential subqueries (we need the answer of one to formulate the other) and aggregate the retrieved documents to answer correctly.
| Question: In what year did the man who shot Chris Stockley, of The Dingoes, die? |
|---|
| Ground Truth: 1987 |
| <think> First, I need to find information about Chris Stockley. </think> |
| <search> when did Chris Stockley of The Dingoes die </search> |
| <information> Doc 1(Title: "The Dingoes") The Dingoes The Dingoes is an Australian country rock band initially active from 1973 to 1979, formed in Melbourne which relocated to the United States from 1976. Most stable line-up was John Bois on bass guitar, John Lee on drums, Broderick Smith on vocals and harmonica, Chris Stockley on guitar, and Kerryn Tolhurst on guitar. Mal Logan (who provided keyboards on the first LP) on keyboards joined after Stockley was hospitalised when shot in the stomach by Melbourne drug-dealer, Dennis Allen, who was attempting to gate crash a party. The Dingoes’ debut single, ""Way Out West"", was released in November.. Doc 2(Title: "The Dingoes") and Tolhurst although Bois’ book confirms that the song was written by Tolhurst alone. A week before the single was released Stockley received a serious gunshot wound during an incident at a party in Melbourne that resulted in a two-month stay in hospital, initially described as an ’accidental shooting’, according to music historian, Ian McFarlane’s ""Encyclopedia of Australian Rock and Pop"",… </information> |
| <think> Now, I need to find information about the man who shot him. </think> |
| <search> who shot Chris Stockley of The Dingoes </search> |
Table 7: SubSearch case study 3 (successful): SubSearch can decompose the initial information need into sequential subqueries (we need the answer of one to formulate the other) and aggregate the retrieved documents to answer correctly. However, compared to case study 2, we also see the model generated a search that is useless (see subquery 1).
| Case study: failed reasoning due to missing decomposition and spurious grounding |
|---|
| Question: At what theater is the composer and lyricist for the musical Big Fish a residential artist? |
| Ground Truth: Ars Nova Theater |
| <think> First, I need to find the composer and lyricist of Big Fish. </think> |
| <search> what is the theater of Big Fish musical composer lyricist residential artist </search> |
| <information> Doc 1(Title: "Big Fish (musical)") Big Fish (musical) Big Fish is a musical with music and lyrics by Andrew Lippa and book by John August. It is based on Daniel Wallace’s 1998 novel, """", and the 2003 film ""Big Fish"" written by John August and directed by Tim Burton. ""Big Fish"" revolves around the relationship between Edward Bloom, a travelling salesman, and his adult son Will, who looks for what is behind his father’s tall stories. The story shifts between two timelines. In the present-day real world, sixty-year-old Edward Bloom faces his mortality while Will prepares to become a father himself. In the storybook past.. Doc 2(Title: "Big Fish (musical)") ’Dirty Rotten Scoundrels.’ His ingratiating singing and dancing bespeak the rare man comfortable in his own skin, and he has that indefinable charismatic spark that defines a star. ""Variety"" reviewer Marilyn Stasio wrote: ""Norbert Leo Butz is cutting loose in another one of his don’t-dare-miss-this perfs in ’Big Fish,’ a show that speaks to anyone pining for a studiously heart-warming musical about the efforts of a dying man to justify a lifetime of lousy parenting to his alienated son."" Big Fish (musical) Big Fish is a musical with music and lyrics by Andrew Lippa and book by John August. It.. Doc 3(Title: "Big Fish: A Novel of Mythic Proportions") Big Fish: A Novel of Mythic Proportions Big Fish: A Novel of Mythic Proportions is a 1998 novel by Daniel Wallace. It was adapted into a film, ""Big Fish"", in 2003 by Tim Burton. A musical adaptation starring Norbert Leo Butz premiered in Chicago in April 2013. A young man (William Bloom), at the deathbed of his father (Edward Bloom), tries to reconcile his memories of his dad with the person he really is. Whereas he always saw his father as an irresponsible liar, he comes to understand his dad’s exaggerations and their roots in reality. The book is written.. </information> |
| <think> Now I need to find where Andrew Lippa is a resident artist. </think> |
Table 8: SubSearch case study 4 (unsuccessful): SubSearch gets stuck into generating the similar queries every time, finally reaching an answer that is not correct. While the reasoning goes well, the model fails in asking the correct 2nd question.
More in this topic
RL for Language Model Reasoning
Reinforcement learning for language model reasoning uses reward-driven training to improve multi-step problem solving, tool use, and reliable answers.
See all 1,094 papers