Opinion by Judge PREGERSON.

I. OVERVIEW

Samson Getachew, a native and citizen of Ethiopia, petitions for review of the Board of Immigration Appeals’s denial of his applications for asylum and withholding of deportation under 8 U.S.C. §§ 1158 and 1253(h). We have jurisdiction under 8 U.S.C. § 1105a(a)(l). We grant the petition for review.

II. BACKGROUND

Samson Getachew arrived on our shores from Ethiopia in March of 1985 at the age of .seventeen, initially entering the United States via a tourist visa. Six months later, he enrolled in community college and was granted a student visa.

In January of 1989, Getachew filed an application for asylum with the Immigration and Naturalization Service (“INS”). The INS denied his asylum application and a year later charged him with deportability for overstaying his visa. At his deportation hearing, in March of 1991, Getachew conceded deport-ability, but renewed his application for asylum and withholding of deportation. In his affidavit, and in testimony characterized by the Immigration Judge (“IJ”) as “credible and sincere,” Getachew explained the events that led to his arrival in the United States.

His departure from Ethiopia was preceded by two years of mistreatment at the hands of the Ethiopian government. In 1983, when he was fifteen years old, he was jailed by the government for 48 hours for refusing to attend monthly youth communist meetings. The meetings, organized by neighborhood security organizations called “Kebele,” consisted of indoctrination “about the system in Russia.” Getachew refused to attend because “I didn’t believe in it.” During his 48 hour detention, he was held under armed guard in a ten-by-six foot cell with eleven other older male prisoners. The cell was so crowded that he was initially forced to sleep sitting down in the corner, although a guard later relented and allowed him to sleep on a bench in the guard booth. He had to obtain permission to use the bathroom and was fed only twice (once each day). Upon his release, he was warned not to miss any more meetings.

Getachew further testified that despite the warning, he again refused to attend the meetings because he did' not believe in Marxist ideology. When the authorities confronted him for his failure to attend, he tried to convince them it was because he was sick, but they did not believe him. He was again jailed, this time for 24 hours, and he was also sentenced to several months of supervised work without pay to atone for his failure to attend the meetings. Getachew described this latter punishment as a “labor camp” where he was forced to work full-time under rough conditions picking up papers and cleaning the government-run printing factory.

He testified that these experiences convinced him to attend the meetings, if only to avoid even worse punishment. He resolved to work hard in order to obtain an exit visa, and when given the opportunity, he fled Ethiopia. ^[1] After his arrival in the United States, his mother warned him never to return to Ethiopia because the government-there considered him a traitor. Government officials had been asking his whereabouts, and many of his school friends with similar political views had fled Ethiopia.

[*844] Based primarily on this testimony, plus documentary evidence of conditions in Ethiopia, the IJ found that Getaehew “dreads the idea of returning to Ethiopia because he believes that the government there would view him as ‘a traitor basically.’ ” Nevertheless, despite crediting Getachew’s testimony and acknowledging the abhorrent conditions in Ethiopia, the IJ denied Getachew’s application, finding that Getaehew had not sufficiently established persecution or a well-founded fear of persecution. ^[2]

Getaehew appealed to the Board of Immigration Appeals (“Board”), complaining that the IJ’s decision was not supported by substantial evidence. The briefing schedule provided to the parties by the Board gave Geta-chew 25 days to file an appeal brief, after which the INS was granted 15 days to file an answer. Getaehew prepared a timely 40-page appeal brief critical of the IJ’s opinion. The INS reply brief was nearly a month late and its argument was one paragraph in length. In it, the INS adopted the reasoning set forth in the IJ’s opinion and asked the Board to “take administrative notice that the Marxist party no longer is in power in the Ethiopian government.”

Getaehew responded by submitting a one-page “reply-brief’ in which he pointed out that the INS’s brief was late, that it “assume[d] facts not in evidence,” and that the INS’s brief was “not supported by any documentary evidence that conditions are now safe for the Respondent in his home country.” The Board did not respond to Geta-ehew’s procedural objections.

More than a year later, the Board affirmed the IJ’s decision. The Board’s opinion neither adopted nor criticized the IJ’s reasoning. Instead, after reviewing the IJ’s factual findings, the Board turned immediately to a discussion of the changed circumstances in Ethiopia after the overthrow of the Marxist regime. The opinion provided, in relevant part:

We have reviewed the most recent Country Reports for Ethiopia and find that the Ethiopian Government as it existed when the respondent departed his homeland effectively has been dismantled. The report indicates that a coalition of ethnic-based insurgencies toppled that repressive Marxist regime of President Mengistu Haile-Mariam in late May 1991 bringing profound political changes to Ethiopia. The former president flew into exile. In July, a broad-based national conference adopted a charter establishing a multi-party transitional government. The report indicates that the new leadership dismantled the extensive military and security apparatus of the Mengistu government, including the political and surveillance operations by neighborhood committees known as Re-beles. Additionally, the new leaders stated their commitment to the establishment of multiparty democracy and the rule of law with full respect for human rights. Given this development, there no longer exists any basis for the respondent’s claim that he has a well-founded fear of persecution by the Ethiopian Government due to his failure to attend meetings of the Re-beles. The respondent has failed to make an effective response regarding these changed circumstances. We are in agreement with the immigration judge’s determination that the respondent failed to establish statutory eligibility for asylum relief.

AR at 3-4 (citations omitted) (emphasis added).

III. DISCUSSION

Getaehew makes two claims of error. First, he argues that the Board erred because it took into consideration the govern[*845] ment’s brief which was filed a month late, in violation of INS regulations. See 8 CFR § 3.3(c). Second, he claims that it was error for the Board to take administrative notice of changed conditions in Ethiopia without first giving him notice and an opportunity to respond to the evidence of changed conditions. We reject the first claim, but find merit in the second.

A. Late Brief:

Getachew’s contention that the Board erred in considering the INS’s late brief must fail. The Board is empowered to exercise its discretion regarding matters within its jurisdiction. See 8 CFR § 3.1(d)(1) (“in considering and determining cases before it as provided in this part the Board shall exercise such discretion and authority ... as is appropriate and necessary for the disposition of the case”). Such discretion is of course limited by due process considerations, see infra, but no such considerations are implicated here because Getachew has not shown how he has been prejudiced by the lateness of the INS’s brief. See United States v. Nicholas-Armenta, 763 F.2d 1089 (9th Cir.1985) (due process challenges to deportation proceedings require a showing of prejudice). We therefore proceed to the second, and more substantial, of Getachew’s contentions.

B. Scope of Administrative Notice:

1. Standard of Review:

Getachew contends that the Board violated due process by taking administrative notice of changed conditions in Ethiopia without giving him adequate notice and an opportunity to respond, and by inferring, on the basis of the changes, that he no longer had a well-founded fear of persecution. We generally review claims of due process violations in deportation proceedings de novo. See, e.g., Barraza-Rivera v. INS, 913 F.2d 1443 (9th Cir.1990). Despite this general rule, we review the procedures the Board uses to take administrative notice of facts not in the record for abuse of discretion. Acewicz v. INS, 984 F.2d 1056, 1060 (9th Cir.1993).

2. Analysis:

It is well-established that the due process clause applies to protect immigrants in deportation proceedings, and furthermore that due process for an immigrant threatened with deportation includes the right to a full and fair hearing. Landon v. Plasencia, 459 U.S. 21, 103 S.Ct. 321, 74 L.Ed.2d 21 (1982); Castillo-Villagra v. INS, 972 F.2d 1017, 1028 (9th Cir.1992). “The fundamental requirement of due process is the opportunity to be heard at a meaningful time and in a meaningful manner.” Mathews v. Eldridge, 424 U.S. 319, 333, 96 S.Ct. 893, 902, 47 L.Ed.2d 18 (1976) (internal quotation omitted). Corollary to the right to a hearing before deportation is the right to a deportation decision based on the record created during and before the hearing. Therefore, due process requires the Board to refrain from taking administrative notice of facts not in the record unless the procedures it follows are fair under the circumstances. Castillo-Villagra, 972 F.2d at 1027.

The Board has wider authority to consider such facts than do the courts. The so-called “rule of convenience” provides that the Board is not limited, as are the courts, to considering extra-record adjudicative facts that are “not subject to reasonable dispute.” Castillo-Villagra, 972 F.2d at 1027 (quoting Federal Rule of Evidence 201(b)). On the other hand an “essential concomitant” of the informality permitted by the rule of convenience is the requirement that immigrants in deportation proceedings receive notice and an opportunity to respond to extra-record facts the Board intends to consider. Id. at 1028. This requirement is critical in order to “direct[ ] the asylum seeker’s presentation to the propositions likely to have a practical effect on the outcome.” Id.

We have recently delimited the rough parameters of the Board’s discretion about when, whether, and how to take administrative notice of extra-record facts. The Board need not notify applicants before considering events that occurred before the deportation hearing and that were presented and argued before the IJ during the deportation hearing. Acewicz, 984 F.2d at 1061. See Kahssai v. INS, 16 F.3d 323, 324 n. 3[*846] (9th Cir.1994) (distinguishing Acewicz from cases in which the change in government comes after the deportation hearing). By contrast, the Board must at least warn the asylum applicant before taking notice of significant events that occurred after the deportation hearing. Castillo-Villagra, 972 F.2d at 1029. A warning is all that is required where the facts in question are “legislative, indisputable, and general^” such as, for example, which party has won an election in the immigrant’s home country. Id. Other, more controversial or individualized facts, such as whether a particular group remains in power after an election, and whether the election has vitiated any previously well-founded fear of persecution, require more than mere notice. Such controversial or individualized facts require both notice to the applicant that administrative notice will be taken and an opportunity to rebut the extra-record facts or to show cause why administrative notice should not be taken of those facts. Id. Evidence of a change in government falls in this last category, requiring the Board to provide both notice and an opportunity to respond. Kahssai, 16 F.3d at 324 (Board’s assessment of asylum eligibility, based even partially on administrative notice of a post-hearing change in government, requires opportunity to rebut any disputable noticed facts).

In the ease before us, the Board took administrative notice of the change in government that took place after Getachew’s asylum hearing, and of the character of the new government. Therefore, the Board was required to give notice to Getachew of its intention to consider these extra-record facts, and to provide him with an opportunity to respond. It is undisputed that the Board did not do so.

Nevertheless, the INS argues that Getachew was adequately notified because the INS’s brief to the Board asked the Board to take notice that the Marxist government was no longer in power in Ethiopia. We hold that such a request by the INS is insufficient to satisfy the due process concerns expressed in Castillo-Villagra and its progeny for two reasons. First, only the Board may give notice of its intentions, not the INS, which is one of the parties to the action before the Board. Second, the information contained in the INS brief failed to apprise Getachew of the particular facts that would be used against him and of the source of those facts.

(1) An INS brief cannot provide adequate notice of Board intentions and an opportunity to respond:

As discussed above, the INS requested that the Board take administrative notice of the change in the Ethiopian government. The Board’s failure to respond to the INS request left Getachew uncertain about whether it would grant the INS’s request. The Board chose neither to confirm that it would consider the change in government (the notice requirement), nor to inform Geta-chew how and when to present any rebuttal evidence (the opportunity to rebut requirement).

Notice: In the INS’s view, the mere fact that it requested the Board to take administrative notice of certain extra-record facts should have been enough to notify Getachew that the Board would do so. But the INS’s function in deportation and political asylum proceedings is no more than that of a litigant before the Board. It has no 'authority or discretion to determine what evidence or arguments will be entertained by the Board. Therefore, at most the INS’s brief can alert the petitioner to the possibility that the Board will take administrative notice of the requested facts. The INS cannot give notice of the Board’s intention to consider extra-record matters because the INS does not determine whether its request will be granted.

Opportunity to respond: Two circumstances combined to prevent Getachew from forming an adequate response to the INS’s factual allegations. Procedurally, it is not clear from INS regulations how an applicant who desires to rebut completely new evidence or arguments made by the INS before the Board should proceed. In particular, the briefing schedule provided by the Board in this ease did not allow any further response by Getachew. The general rule is that the Board will not accept new evidence from a petitioner on appeal absent exceptional circumstances. See Gordon & Mailman, Immi[*847] gration Law and Procedure § 5.05[5][b] (1993). The Board gave no indication that this was an exceptional circumstance under which it would allow the introduction of evidence to refute the implications of the extra-record facts proffered by the INS. In fact, the Board failed to respond at all either to the INS’s request that it take administrative notice, or to Getachew’s objection to the INS’s request.

In addition to these procedural difficulties, practical considerations also prevented Geta-chew from responding. The INS’s request to the Board to take administrative notice was contained in its short reply brief after Getachew had prepared and submitted a 40-page brief responding solely to the facts in the record developed pursuant to his hearing. Although only one sentence in length, the INS’s request brought up an entirely new line of argument and requested the Board to consider completely new evidence not previously addressed by the parties. Fairness is the ultimate test of the Board’s discretion. Castillo-Villagra, 972 F.2d at 1027. It was not fair to expect Getachew to prepare a new response to the INS’s one-sentence administrative notice request when he was in doubt about whether or not the Board would grant the INS’s request.

The INS puts great stress on the fact that its brief was filed fourteen months before the Board issued its decision, implying that Geta-chew could have responded at any time during this period. But this long delay did nothing to alleviate Getachew’s uncertainty about whether the INS’s request would be granted, and about how he should respond. Such uncertainty is the very problem that the Castillo-Villagra notice requirement was intended to alleviate.

(2) Adequacy of information:

Besides coming from the wrong party, the INS’s purported notice did not adequately apprise Getachew of the facts that were eventually used against him and of their source. Although there have been no cases as of yet on the adequacy of notice in the immigration context, we take guidance from Banks v. Schweiker, 654 F.2d 637 (9th Cir.1981), the social security case on which Castillo-Villagra relied for its determination that the Board must give notice before considering extra-record facts. In Banks, the court explained that adequate notice requires the agency to “indicate the facts noticed and their source with a degree of precision and specificity. Without such information, a party cannot be expected to offer an objection.” Id. at 642 (citation omitted).

The INS’s request to the Board to take administrative notice that the Marxist government in Ethiopia was no longer in power clearly fails the test put forward in Banks. The INS did not specify its source, nor, critically, did it include the details necessary to explain the relevance of the overthrow of the Marxist government to Getachew’s case.

Moreover, the INS’s request was deficient because the Board’s opinion took notice of a catalogue of facts that were not even included in the INS’s brief. Facts noted by the Board included its glowing description of the “multiparty” democracy that had replaced the former repressive regime, a government, according to the Board, whose leaders were committed to human rights. According to the Board, the former security apparatus had been dismantled. In particular, the Kebele, whose meetings Getachew had avoided, had been disbanded. Even if Getachew had notice that the Board might take into account the change in government, he did not have notice of these controversial and specific facts. In short, without adequate notice Ge-taehew did not have an opportunity to respond.

Given an opportunity, Getachew may well have been able to show that he was still in danger from the new government. It is notable that the most recent country report paints a far less rosy picture of the situation in Ethiopia than does the Board’s opinion. The report describes violent clashes between rival political parties, flawed elections, “including fraud, harassment, intimidation” and “numerous, gruesome, politically motivated killings” and human rights abuses. Department of State, Country Reports on Human Rights Practices for 1992, at 84-85 (1993). “[Government weakness means that those responsible are seldom, if ever held legally accountable for human rights abuses.” Id. at[*848] 85. Arbitrary arrest and detention, by a variety of groups, is common, although theoretically prohibited by the new government’s charter. Id. at 86. Although systematic torture has abated since the Marxist government left power, there were many credible allegations that detainees were beaten while in detention. Id. at 86.

In sum, although conditions have improved in Ethiopia since the 1980’s, this certainly does not preclude a finding that Getachew still has a well-founded fear of persecution. Given the opportunity, Getachew may well be able to tie his particular situation to the general human rights abuses in Ethiopia in order to establish such a claim.

IV. CONCLUSION

Where the Board improperly relies, in whole or in part, on extra-record facts for its determination of whether an asylum applicant has demonstrated a well-founded fear of persecution, we must grant the applicant’s petition for review. Kahssai 16 F.3d at 325. Here the Board’s decision appears to have relied entirely on administratively noticed facts without providing the required notice and opportunity to be heard. The petition for review is therefore GRANTED.