OPINION OF THE COURT

Petitioner Daniel Duarte, a native and citizen of Venezuela, seeks review of the September 7, 2005, Order of the Board of Immigration Appeals (“BIA”), affirming without opinion the April 28, 2004, Order of the Immigration Judge (“IJ”). The IJ denied Duarte’s claims for asylum, withholding of removal, and relief under the United Nations Convention Against Torture (“Convention Against Torture”). We have jurisdiction to review the petition pursuant to 8 U.S.C. § 1252(a)(1), and for the reasons set forth below, we will deny the petition.

I.

Because we write solely for the benefit of the parties, we will set forth only those facts necessary to our analysis.

Duarte last entered the United States at Miami, Florida on November 13, 2002. He filed an application for asylum, withholding of removal, and relief under the Convention Against Torture on April 12, 2003. On July 1, 2003, the former Immigration and Naturalization Service 1 (“INS”) served Duarte with a Notice to Appear, charging him with removability under Section 237(a)(1)(B) of the Immigration and Nationality Act, 8 U.S.C. § 1227(a)(1)(B), as an alien who overstayed his authorized admission period.

At an appearance before the IJ on August 7, 2003, Duarte conceded removability but sought asylum, withholding of removal, and relief under the Convention Against Torture. At a merits hearing on Novem *156 ber 5, 2003, Duarte testified that he is homosexual, and that police officers in Venezuela subjected him to arbitrary detention, beatings, sexual assault, extortion, and harassment on account of his homosexuality.

Duarte testified that the first incident of police persecution occurred in 1990, when police stopped Duarte and a friend as they were leaving a gay bar. After making disparaging comments about homosexuals, the officers drove Duarte and his friend around the city, stole their money and valuables, and left them stranded on the highway.

Duarte next testified that on December 4, 1995, he and his then-boyfriend Duarte da Silva (“da Silva”) were confronted by two police officers outside Duarte’s home. He testified that the officers assaulted them, drove them to an abandoned field and took their money, and then took them to the police station. At the police station, Duarte testified that police placed him in a cell with three inmates and said, “here you have a little girlfriend for the evening. Take care of her for me.” J.A. at 52. Duarte stated that one of the inmates punched him in the stomach and he was then sodomized by two of the inmates. He testified that the police were aware of what was happening in the cell. Duarte and da Silva were released a few hours later, and da Silva told Duarte that he was forced, at gunpoint, to perform oral sex on the two officers.

Duarte testified that the next morning he went to a hospital to receive treatment for injuries he suffered as a result of the rape. 2 Duarte also testified that he and da Silva filed a complaint with the General Prosecutor’s Office of the Republic (“the complaint”) against these police officers on January 23,1996. 3

Duarte testified to two additional instances in which the same police officers extorted money from him. In addition, Duarte testified that he received numerous threatening phone calls at work from the end of January through February 1996.

Duarte testified that da Silva went missing in March 1996 and was later found dead in his car due to hemorrhaging from a weapon injury to his liver. Duarte testified that he learned the details of da Silva’s death from Carlos Araujo, a mutual friend who received the information from da Silva’s family.' 4 He testified that he did not attend da Silva’s funeral. Believing da Silva was killed by police officers, Duarte testified that he went into hiding at a friend’s house until he came to the United States on April 9,1996.

Duarte testified that he first came to the United States in June of 1995 for a vacation. He further testified that, on April 9, 1996, he fled Venezuela to the United States to escape persecution and lived in the United States until he returned to Venezuela approximately five months later on September 22, 1996. When asked why he returned, Duarte gave the following reasons: “I was very depressed. I was very down. I felt very alone. I had no social life. I had no support. I had no *157 family members nearby---- I could not find a way to deal with this situation. Back then, I was only 23, 24.” J.A. at 71. Duarte testified that upon his return to Venezuela, one of the police officers called him at work and threatened to find Duarte no matter where he tried to hide. Duarte left Venezuela and returned to the United States on November 2, 1996. He lived in the United States from 1996 until October 2002, when he again returned to Venezuela. He testified that the purpose of this trip was to renew his eligibility to apply for asylum and to renew his passport. He also testified that he did not experience any problems with the police during this trip because he stayed at a friend’s house and rarely left the house. 5 He returned to the United States on November 13, 2002.

Duarte admitted he entered into a sham marriage with a United States citizen in 1997 in an attempt to obtain a green card. He also admitted he left the United States in October 2002, returned to Venezuela, and re-entered the United States in November 2002 for the sole purpose of renewing the one-year deadline for filing an application for asylum. In order to regain entry into the United States, he admitted paying an immigration official at the airport in Venezuela to alter his passport so that it appeared he had been living in Venezuela from 1996 through 2002.

In an oral decision dated April 23, 2004, the IJ denied relief on all grounds. First, the IJ found Duarte’s background information on police persecution of homosexuals to be insufficient because it was either not specifically related to persecution of homosexuals or because it lacked reliability. The IJ credited two Internet articles submitted by the government that detailed accommodations for gay individuals traveling to Venezuela. In addition, the IJ found nothing in the 2002 State Department Country Report to support a claim of persecution of homosexuals in Venezuela.

Despite the insufficient background material, the IJ stated that, if true, Duarte’s story would have established past persecution by police in Venezuela. However, the IJ concluded “that credibility is fatally lacking in this case.” J.A. at 14. Moreover, in discussing Duarte’s immigration fraud, the IJ posited that even if he had found Duarte credible, he “would deny this asylum application simply on the basis of the respondent’s flagrant and improper attempt to get around the Immigration laws of asylum.” J.A. at 15.

Duarte filed a timely appeal with the BIA, which issued a per curiam Order affirming the IJ without opinion.

II.

Where the BIA affirms the IJ’s decision without opinion, this Court reviews the decision of the IJ. Partyka v. Attorney General, 417 F.3d 408, 411 (3d Cir. 2005). We review agency findings of fact, including an adverse credibility determination, under the substantial evidence standard. Gao v. Ashcroft, 299 F.3d 266, 272 (3d Cir. 2002). Under this standard, we look to whether the decision is “supported by reasonable, substantial, and probative evidence on the record considered as a whole.” Balasubramanrim v. INS, 143 F.3d 157, 161 (3d Cir. 1998) (quoting INS v. Elias-Zacarias, 502 U.S. 478, 481, 112 S.Ct. 812, 117 L.Ed.2d 38 (1992)) (internal quotations omitted). An agency’s factual findings will be upheld unless a “reasonable adjudicator would be compelled to conclude to the contrary.” 8 U.S.C. *158 § 1252(b)(4)(B); see also Gao, 299 F.3d at 272.

III.

A. Credibility

Duarte contends the IJ’s credibility determination is not supported by substantial evidence. Foremost, Duarte argues he provided detailed, consistent, plausible, and corroborated testimony that the IJ ignored. In addition, Duarte challenges the reliability of the evidence the government introduced to prove that several pieces of Duarte’s corroborating evidence were fraudulent.

The IJ provided the following reasons for the adverse credibility determination: (1) Duarte admitted entering into a sham marriage to obtain a green card; (2) Duarte admitted altering his passport to regain entry in the United States; (3) Duarte admitted leaving the United States in 2002 for the sole purpose of renewing the one-year period to apply for asylum; (4) a letter from the U.S. Embassy in Caracas (“the consulate letter”) was persuasive evidence that some of Duarte’s corroborating documents were fraudulent; (5) the consulate letter and the Assessment to Refer memorandum prepared by asylum officer J. Goldstein (“Assessment to Refer”) contradicted Duarte’s testimony that his boyfriend was murdered in 1996; and (6) Duarte returned to Venezuela where he claimed to have been persecuted in 1996 and in 2002.

An adverse credibility finding must be supported by “specific cogent reasons” that “bear a legitimate nexus to the finding.” Gao, 299 F.3d at 276. “We look at an adverse credibility determination to ensure that it was appropriately based on inconsistent statements, contradictory evidences, and inherently improbable testimony in view of the background evidence on country conditions.” Dia v. Ashcroft, 353 F.3d 228, 249 (3d Cir. 2003) (internal citation and quotations omitted). Adverse credibility findings based on “speculation or conjecture, rather than on evidence in the record, are reversible.” Gao, 299 F.3d at 272. Furthermore, the underlying basis of an adverse credibility determination must go to the heart of the alien’s claims. 6 Id.

We find the IJ’s reliance on the consulate letter to be error. To contradict Duarte’s documentary evidence, the government submitted a report from the U.S. Embassy in Caracas concluding that several of Duarte’s documents were fraudulent. The consulate letter states that national identification numbers for individuals listed on da Silva’s death certificate and the complaint filed against police “do not pertain to these individuals” and, therefore, the documents are “counterfeit.” J.A. at 398-99. The consulate letter also questions the authenticity of the medical report based on speculation that laser printing was not available at that medical clinic in 1995. And, the letter reports that a non-immigrant visa was issued to Duarte Lorenzo da Silva Montero on October 3, 1997, calling into question Duarte’s testimony that da Silva was murdered by police in 1996.

*159 In Ezeagwuna v. Ashcroft, we held that reliance on a similar letter from the Department of State violated due process because it did not satisfy the standards of reliability and trustworthiness. 325 F.3d 396, 405-06 (3d Cir. 2003). Specifically, the letter contained multiple levels of hearsay and was devoid of information “about what the ‘investigation’ consisted of, or how the investigation was conducted.” Id. at 408. Moreover, we expressed concern that “the INS is attempting to use the prestige of the State Department letterhead to make its case and give credibility to the letter’s contents.” Id. at 407. We concluded that the nature of such an investigation “is a matter of pure conjecture and can provide no basis for a finding of falsification on the part of [petitioner].” Id. at 408.

We find the same is true of the consulate letter here. The letter, signed by Consul General Daniel F. Keller, reports hearsay statements from Foreign Service National fraud specialist Tesalio Martin. In addition, the consulate letter does not provide documentary evidence that actually shows the purported discrepancy among identification numbers. Duarte, on the other hand, submitted downloaded reports showing matching identification numbers and an affidavit from an attorney stating that the method by which she obtained that information is the standard practice in Venezuela.

The consulate letter also questions the authenticity of the December 5,1995 medical report, expressing uncertainty over whether laser printing technology would have been available at that clinic in 1995. However, it offers no basis for such skepticism and even acknowledges that the doctor who signed the report is a doctor at that clinic.

Furthermore, Ezeagwuna warned that the BIA cannot “justify its decisions simply by invoking assertions by the State Department that themselves provide no means for evaluating their validity.” 325 F.3d at 407 (citing Galina v. INS, 213 F.3d 955, 958-59 (7th Cir. 2000)). Yet, that is exactly what the IJ did here when he said, “this Court on the whole is going to place more reliability on the reports of the State Department than it is going to on the reports of the evidence that has been supplied by the respondent.” J.A. at 16. The IJ credited the government’s evidence merely because it came from the State Department and summarily rejected Duarte’s evidence merely because it came from a paralegal working for Duarte’s attorney, notwithstanding the fact that both pieces of evidence were produced from independent Internet sources.

Despite this erroneous reliance on the consulate letter, we find the IJ properly based his credibility determination on two other factors, which taken together, provide substantial evidence for his finding.

First, we find the IJ properly considered the Assessment to Refer memorandum as evidence contradicting Duarte’s testimony that da Silva was killed in 1996. We have found that contradictory evidence is a proper basis for an adverse credibility finding. See Chen v. Gonzales, 434 F.3d 212, 221 (3d Cir. 2005) (quoting Abdulai v. Ashcroft, 239 F.3d 542, 551 n. 6 (3d Cir. 2001)). Duarte testified that da Silva disappeared in March of 1996, and that he learned from a mutual friend that da Silva was found dead in his car from a weapon injury to his liver. Duarte testified that he believed the same police officers responsible for the December 4, 1995 incident had murdered da Silva, and, as a result, Duarte went into hiding shortly thereafter. The Assessment to Refer memorandum provided evidence that da Silva was issued a nonimmigrant visa in October of 1997, approximately a year and *160 a half after his alleged murder. This evidence directly contradicts Duarte’s testimony. Furthermore, this inconsistency goes to the heart of Duarte’s claim because it calls into question his testimony regarding his relationship with da Silva and the facts of the December 4, 1995 incident involving Duarte and da Silva.

Second, Duarte’s return to Venezuela in September of 1996, after having suffered numerous incidents of persecution at the hands of police, supports the IJ’s adverse credibility finding. The IJ found Duarte’s claim of persecution implausible in light of “the fact that the respondent returned to his country where he had been persecuted on numerous occasions.” J.A. at 17. When asked why he returned, Duarte testified that he felt depressed and alone in the United States. This explanation is difficult to reconcile with the brutality of the incident of persecution he alleges he suffered in December 1995 and the murder of his boyfriend in March 1996. We cannot conclude that any reasonable adjudicator would be compelled to find Duarte credible despite his return to Venezuela shortly after these incidents. 7 See Berishaj v. Ashcroft, 378 F.3d 314, 324 (3d Cir. 2004) (finding that an adverse credibility determination may be based on the implausibility of an applicant’s story).

Despite the deficiencies in the IJ’s analysis of Duarte’s credibility, under our deferential standard, we find the adverse credibility determination was supported by substantial evidence. 8

B. Due Process

Duarte claims he was denied due process of law because the IJ refused to allow two of his witnesses to testify. First, Duarte claims the IJ erred when he limited the testimony of Amalfi Baldo, a Venezuelan lesbian who had been granted asylum in the United States. Second, Duarte argues the IJ denied him due process by refusing to allow his former attorney, Milagros Vera, to testify telephonically from Venezuela. The government argues this Court is precluded from considering Duarte’s due process argument because Duarte did not appeal these rulings to the BIA, thereby failing to exhaust administrative remedies. Our review of Duarte’s brief to the BIA reveals that he challenged the ruling as to Vera but not as to Baldo. Therefore, we address only the due process argument with respect to the IJ’s refusal to allow Vera to testify. We exercise plenary review over an asylum applicant’s procedural due process claim. Singh v. Gonzales, 432 F.3d 533, 541 (3d Cir. 2006).

Aliens are entitled to procedural due process in removal proceedings consisting of “the opportunity to be heard at a meaningful time and in a meaningful manner.” Abdulai, 239 F.3d at 549 (quoting Mathews v. Eldridge, 424 U.S. 319, 333, 96 S.Ct. *161 893, 47 L.Ed.2d 18 (1976)) (internal quotations omitted). We have held that aliens are entitled to “a Ml and fair hearing of [their] claims and a reasonable opportunity to present evidence.” Singh, 432 F.3d at 541 (quoting Chong v. Dist. Dir., INS, 264 F.3d 378, 386 (3d Cir. 2001)) (internal quotations omitted). To prevail on a due process claim, an asylum applicant must show that denial of the right resulted in substantial prejudice. Id.

In Singh v. Gonzales, we rejected an asylum applicant’s claim that the IJ’s refusal to allow two of his witnesses to testify violated due process because, inter alia, the applicant did not establish that the testimony “would have been anything other than cumulative.” Id. Duarte claims Vera’s testimony would have been relevant to corroborate his claim that he filed a complaint against the Venezuelan police and to confirm da Silva’s identification number. But just as in Singh, Vera’s testimony would have amounted to cumulative evidence in light of the fact that Duarte had submitted a signed letter from Vera attesting to this very same information. Because the IJ already had this evidence before him in the form of Vera’s letter, her testimony would have been cumulative. Accordingly, we cannot see how the IJ’s refusal to allow Vera to testify could have substantially prejudiced Duarte’s case.

C. Wellr-Founded Fear of Future Persecution

Duarte claims the IJ failed to consider relevant background evidence he submitted that establishes a pattern or practice of persecution against homosexuals in Venezuela. The government claims the IJ addressed only the credibility issue and, therefore, Duarte is precluded from raising the well-founded fear of persecution issue on appeal. The IJ’s decision focused on the issue of Duarte’s credibility. However, as we read the IJ’s opinion, his adverse credibility finding lead him to reject both the past persecution and well-founded fear of future persecution claims. Therefore, we will address this claim.

In Lie v. Ashcroft, we held that to establish a well-founded fear of Mure persecution, an asylum applicant must first demonstrate “a subjective fear of persecution through credible testimony that [his] fear is genuine.” 396 F.3d 530, 536 (3d Cir. 2005). Next, an applicant must make an objective showing that a reasonable person in his circumstances would fear persecution if returned to his native country. Id. To satisfy the objective prong, an applicant “must show [he] would be individually singled out for persecution or demonstrate that ‘there is a pattern or practice in his or her country of nationality ... of persecution of a group of persons similarly situated to the applicant on account of race, religion, nationality, membership in a particular social group, or political opinion____’” Id. (quoting 8 C.F.R. § 208.13(b)(2)(iii)(A)).

Addressing the objective prong of a well-founded fear of persecution claim, the IJ stated, “respondent has not provided very compelling evidence that persecution or ill treatment of homosexuals in Venezuela is a significant social problem.” J.A. at 13. However, it appears the IJ also denied Duarte’s claim because he failed to establish that his subjective fear of future persecution was genuine. The IJ stated:

The respondent’s story may still be true despite the absence of very much to suggest in the way of background material that there is a problem with being a homosexual in Venezuela, but the respondent’s story has multiple problems of its own that require this Court to conclude that credibility is fatally lacking—

J.A. at 14. We read the IJ’s reference to “[t]he respondent’s story” as encompassing *162 his claim of past persecution as well as his claim that he fears being persecuted if returned to Venezuela. Thus, even if we agree with Duarte that his background evidence was sufficient to satisfy the objective prong of the well-founded fear test, the IJ’s credibility finding undercuts his claim that he had a subjectively well-founded fear of future persecution in Venezuela. See J.A. at 18 (“the Court is inclined to believe that the respondent did not have any real fear of returning to Venezuela in 1996 or in 2002”). As discussed above, that credibility finding was supported by substantial evidence. Thus, we agree with the IJ that Duarte failed to establish a well-founded fear of future persecution.

IV.

We have considered all other arguments made by the parties on appeal, and conclude that no further discussion is necessary. For the foregoing reasons, we conclude that substantial evidence supports the IJ’s decision to deny relief and we will accordingly deny the petition for review.